# 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 algorithmsSorting 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 algorithmsBuilding 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

- 0
- 0
- 0
- 0
- 0
- 0