CUH500CMD Advanced Algorithms
Module Introduction
Mark Elshaw and Muhammad Aleem
- What CUH500CMD is about
- Assessment
- What are algorithms?
- Relevance of the module to your degree and career
- Programming!
- It’s an advanced programming module
- It is the only ‘pure’ programming module at Level 5 / Year 2
- There is other programming, but at application level e.g. (this semester)
- It builds on the two ‘pure’ programming modules at
Level 4 / Year 1: Programming and Algorithms and Object Oriented Programming
Algorithms
- A series of steps to solve a problem. For computing, code that enables a computer to solve a problem
- More later in this lecture (because this is where we’ll start on the module)!
Computability
- Intractable problems:
- Problems for which there is no efficient algorithm
- Methods to estimate solutions for intractable problems
- Intractable problems:
Complexity and Profiling
- Profiling: Analysing code for time and space complexity
- Includes Big O
Concurrency
- Broadly, simultaneous processing:
- e.g. web servers which run multiple instances of the same process on unique data (think about your Facebook, Instagram or Twitter account)
- e.g. web crawler that uses multithreading to retrieve results from a range of news sites at the same or near-same time
- Understand and select appropriate algorithms for solving a range of problems and reason about their complexity and efficiency.
- Design and implement algorithms and data structures for novel problems.
- Specify and implement methods to estimate solutions to intractable problems.
- Describe the issue of data consistency in multi-threaded applications.
- Design and implement a concurrent application.
相关信息
The ILOs may look a bit scary to begin with.
We will be working with you to make sure you’re on top of them.
What About Programming Languages?
CUH500CMD uses two languages:
Python
C++
Some material may require you to use one or the other language
But on most, you can decide
For non-assessed work, we will provide solutions in both languages
You can decide what language to use to implement the assessed task solutions
If you like, this can be a mix.
How Is CUH500CMD Assessed?
Coursework (66.66%)
Exam (33.33%)
- 33.33% Exam
- 2 hour unseen TCA (Week 13)
- Revision and prep in Weeks 11 and 12
- If you cover all the tasks, and have submitted your coursework, you will be well prepared
- If you have not done one or both these, you are less likely to be well prepared
- We will take you through appropriate / past papers and set example questions
- You will become familiar with the structure of the paper and what different types of questions are asking for
66.66% Coursework
- Code Submission (see Mod Doc on Aula, as well as CW spec)
- Each week you will have a range of programming challenges to complete.
- Some of these are non-assessed. 2 types: standard and advanced.
- Solutions to non-assessed exercises will be given two weeks later.
- Some of them are assessed. 2 types: standard and advanced.
- No solutions will be given for the assessed exercises (for obvious reasons!)
- You must submit of 5 the assessed exercises as a codebase.
- This will be in a folder of code
- There will be EIGHT in total. I recommend you complete them all.
Code Submission
Report
- Along with the code, you will submit a report of 3000 words max.
- The report should explain and critique each of your solutions.
- Explain:
- How your code works
- Critique:
- How effective your implementation is and why. Alternative implementation possibilities.
- Examples of good code write-ups will be provided, as well as a simple report template.
Explaining code is something that can be thought about in terms of a 3 level model:
functional (what it does)
------------------------------
syntactic (how it does it)
------------------------------
notional machine (what the computer is doing)
Critiquing code means evaluating its quality.
There are lots of things to think about here:
Effectiveness (does it work)
Efficiency (does it make best use of resources)
Complexity (what are the time and space requirements)
Readability (can someone else make sense of it)
Reusability (and generalisability)
Alternatives (and why they might be preferred)
- ILOs:
- Understand and select appropriate algorithms for solving a range of problems and reason about their complexity and efficiency.
- Design and implement algorithms and data structures for novel problems.
- Describe the issue of data consistency in multi-threaded applications.
Design and implement algorithms and data structures for novel problems.
Specify and implement methods to estimate solutions to intractable problems.
Design and implement a concurrent application.
- We will make sure you are prepared for all assessment
- We will:
- Give clear guidance on what the assessment is and what the marking criteria are
- Give frequent reminders of how the assessment works
- Show when and how work you are doing relates to assessment
- Support you as far as possible in teaching sessions to make sure you are on top of the material
- Of course, this is also up to you.
- Get you ready for the exam
- Again, this is depends on your being on top of the material.
You must achieve:
A mark of 40% or more on the Coursework
A mark of 40% or more on the Exam
An overall mark of 40% or more
Attend.
Engage.
Do all the tasks, non-assessed and assessed
- Don’t wait for solutions to come out
- Solutions don’t tell you how to arrive at the solution – that is what any programmer must learn, and that takes work
- So you should use the solutions to evaluate your own attempts
Be aware of support beyond the module (see later slide)
Do not attend.
Do not engage.
Do few or none of the tasks.
Do not make use of other support.
It’s simple: most people who attend (show up) and engage (do the work) pass. Most who do not attend are not engaging in other ways either, and they fail.
Sometimes it’s about having the courage to let us know when you’re struggling. Please do!
It is very easy to find code online.
Also, now, it is easy to find AIs to write it. And to write your report.
If we find code that is close or identical to online sources when you submit, or we suspect unacknowledged use of AI, we may have to bring an ACO case (academic conduct).
Pasted code / text with an attribution (i.e., you give the URL or other source) is not plagiarism.
But it’s still not a good thing to do, because the whole point is to to produce your own solutions. Code / text pasted off the web / from an AI verbatim / wholesale is not going to be worth credit
Becoming a programmer means doing the work; it is about knowing how to come up with a solution yourself.
If you have taken code you do not understand and presented it to us for assessment, and / or produced an explanation you did not write, even if you tell us where these came from (which you must), this is not becoming a programmer.
You will likely do badly in both the coursework and exam.
As ever, the solution is attendance and engagement.
Lab sessions
Tutors’ support sessions
CUH500CMD Aula page
And now…
- A ‘guaranteed procedure’
- i.e., if you follow the series of steps defined by the algorithm, it is guaranteed to solve the problem it’s been written for
- An algorithm is language-independent
- So code implements an algorithm
- Algorithms are often specified as pseudocode
Find the smallest number in a list
For each number n in the list A, compare it to min
If n is smaller, set min to n
Min is now set to the smallest number in the list
FIND_MIN(A)
min ← ∞
FOR n IN A:
IF n < min:
min ← n
RETURN min
A = [5, 89, 2, 7, 19, 2001, 1]
- Start with 5
- 5 is less than
∞
- So min is 5
FIND_MIN(A)
min ← ∞
FOR n IN A:
IF n < min:
min ← n
RETURN min
A = [5, 89, 2, 7, 19, 2001, 1]
- Next is 89
- 89 is not less than 5
- So min stays 5
FIND_MIN(A)
min ← ∞
FOR n IN A:
IF n < min:
min ← n
RETURN min
A = [5, 89, 2, 7, 19, 2001, 1]
- Next is 2
- 2 is less than 5
- So min is 2
FIND_MIN(A)
min ← ∞
FOR n IN A:
IF n < min:
min ← n
RETURN min
A = [5, 89, 2, 7, 19, 2001, 1]
Next is 7
7 is not less than 2
So min stays 2
FIND_MIN(A)
min ← ∞
FOR n IN A:
IF n < min:
min ← n
RETURN min
A = [5, 89, 2, 7, 19, 2001, 1]
Next is 19
19 is not less than 2
So min stays 2
FIND_MIN(A)
min ← ∞
FOR n IN A:
IF n < min:
min ← n
RETURN min
Guaranteed procedure: will work for a list of integers of any size
Language-independent: can be implemented in many languages
Does the algorithm have defined inputs and outputs?
Yes / No Why?
Can we guarantee that it terminates?
Yes / No Why?
Is it clear and concise?
Yes / No Why?
Does it produce the correct result?
Yes / No Why?
FIND_MIN(A)
min ← ∞
FOR n IN A:
IF n < min:
min ← n
RETURN min
Formally define a sorting problem
Input: a sequence of n numbers (a1, a2… an)
Output: a permutation (i.e. reordering) (a1’, a2’… an’) of the input sequence such that a1’ < a2’… <n’)
We still need to define an algorithm…
But don’t worry, we’ll be covering classic sorts soon
An algorithm is correct if for every instance of the input the output is correct
Solves a problem
A problem is a general description of what needs to be solved
e.g., Find z, where z = x + y; and x and y are both positive integers greater than zero
An instance is a specific case of the problem
e.g., Find 2 + 2
Add two input integers X and Y
Declare and initialise a variable Z which will be our result
Add the two integers X and Y and assign the result to Z
Return Z
ADD_UP(X, Y)
Z ← 0
Z ← X + Y
RETURN Z
Hard to think of what problems in CS are not solved by algorithms
Sorting and searching
Social Media
E-commerce
Wayfinding
Weather forecasting
Vehicle control / navigation
Etc., etc..
As a developer, you will be presented with computational problems
These problems will require solutions
Those solutions will be algorithms
On 5003CEM we will teach you a range of classic known algorithms
The aim is not just to be able to implement these (altho’ that is massively important)…
… but also to develop skills in algorithmic thinking
This skill is key to being a good programmer
Knowing programming concepts
Knowing programming languages
Thinking algorithmically
Evaluating complexity
For example, what kind of sort algorithm is faster (given the same input and hardware)
Is a merge sort faster than an insertion sort?
Complexity starts in Week 3 as a running theme, with a full lecture in week 8
- So essential skills as a programmer are:
- Knowing programming concepts
- Knowing programming languages
- Thinking algorithmically
- Evaluating complexity
CUH500CMD is an advanced programming module about implementing and evaluating algorithms
Building on first year modules, it aims to promote further essential skills, to enable you to make further progress towards being a professional developer
Read through the module document and the assignment specifications to be fully aware of CUH500CMD
Let’s have a look now | Any questions at this stage?
公众号:AI悦创【二维码】

C:::
AI悦创·编程一对一
AI悦创·推出辅导班啦,包括「Python 语言辅导班、C++ 辅导班、java 辅导班、算法/数据结构辅导班、少儿编程、pygame 游戏开发、Web、Linux」,全部都是一对一教学:一对一辅导 + 一对一答疑 + 布置作业 + 项目实践等。当然,还有线下线上摄影课程、Photoshop、Premiere 一对一教学、QQ、微信在线,随时响应!微信:Jiabcdefh
C++ 信息奥赛题解,长期更新!长期招收一对一中小学信息奥赛集训,莆田、厦门地区有机会线下上门,其他地区线上。微信:Jiabcdefh
方法一:QQ
方法二:微信:Jiabcdefh
