Table of contents
Welcome
Welcome to Algorithms II! This unit is a direct continuation of the algorithms part of Object-Oriented Programming and Algorithms from last year. The focus will be on three key algorithm design skills, which will be useful to you no matter which language or programming paradigm you end up working with:
- Greedy algorithms. In other words, when can you replace a complicated algorithm that carefully considers the whole situation with a simple algorithm that just repeatedly does whatever seems like a good idea at the time?
- Graphs and networks. You were briefly introduced to these in Imperative Programming last year, and perhaps in school before that, but in this unit you will learn to use them effectively to model and solve unfamiliar problems.
- Reductions. In other words, rather than writing your own algorithm to solve a problem, either making clever use of a library function or proving that no fast algorithm exists. This will include learning how to apply dynamic programming techniques, which you were introduced to in Algorithms last year, to unfamiliar problems.
Schedule and links to materials
Most of the material below (especially recordings of Q&As and problem classes) will require you to log in to University of Bristol systems.
| Week 1 | Monday 2023/09/25 Videos released | 1-1: Unit introduction (Video, slides, handout) | 1-2: Induction (Video, slides, handout) |
| Optional resources | 1-3: Defining O-notation (Video, slides, handout) Errata here! | 1-4: Using O-notation (Video, slides, handout) | |
| Friday 2023/09/29 Quiz 1 due | Thursday 2023/09/28 Q&A 1 (Padlet, board, recording) | Monday 2022/10/02 Problem class 1 (Sheet, solutions) | |
| (Optional: Dummy quiz to test your browser works.) | |||
| Week 2 | Monday 2023/10/02 Videos released | 2-1: Greedy algorithms and interval scheduling (Video, slides, handout) | 2-2: Correctness proofs for interval scheduling (Video, slides, handout) |
| Optional resources | 2-3: The bridges of Königsberg (Video, slides, handout) | 2-4: When does a graph have an Euler walk? (Video, slides, handout) | |
| Monday 2023/10/09 Quiz 2 due | Thursday 2023/10/05 Q&A 2 (Padlet, board, recording) | Monday 2023/10/09 Problem class 2 (Sheet, solutions) | |
| Week 3 | Monday 2023/10/09 Videos released | 3-1: Directed Euler walks (Video, slides, handout) Errata here! | 3-2: Hamilton cycles (Video, slides, handout) |
| Optional resources | 3-3: Shaking hands (Video, slides, handout) | 3-4: Trees (Video, slides, handout) Errata here! | |
| Friday 2023/10/13 Quiz 3 due | Thursday 2023/10/12 Q&A 3 (Padlet, board, recording) | Monday 2023/10/16 Problem class 3 (Sheet, solutions) Recordings: early, late | |
| Week 4 | Monday 2023/10/16 Videos released | 4-1: Graph Representations (Video, slides, handout) | 4-2: Depth-first Search (Video, slides, handout) |
| Optional resources | 4-3: Breadth-first Search (Video, slides, handout) | 4-4: Dijkstra’s algorithm (Video, slides, handout) | |
| Friday 2023/10/20 Quiz 4 due | Thursday 2023/10/19 Q&A 4 (Padlet, board, recording) | Monday 2023/10/23 Problem class 4 (Sheet, solutions) Recordings: early, late | |
| Week 5 | Monday 2023/10/23 Videos released | 5-1: Matchings I: Definitions (Video, slides, handout) | 5-2: Matchings II: Finding the maximum (Video, slides, handout) |
| Optional resources | 5-3: MSTs I: Prim’s algorithm (Video, slides, handout) Errata here! | 5-4: MSTs II: Kruskal’s algorithm (Video, slides, handout) Errata here! | |
| Friday 2023/10/27 Quiz 5 due | Thursday 2023/10/26 Q&A 5 (Padlet, board, recording) | Friday 2023/11/10 Problem class 5 (Sheet, solutions) Recordings: early, late | |
| Week 6 | Reading week! | No videos! | No quiz! |
| No resources! | No Q&A! | No problem class! | |
| Week 7 | Monday 2023/11/06 Videos released | 6-1: Making Kruskal’s algorithm fast (Video, slides, handout) | 6-2: The union-find data structure (Video, slides, handout) |
| Optional resources | 6-3: 2-3-4 trees I: Search and insertion (Video, slides, handout) | 6-4: 2-3-4 trees II: Deletion and alternative forms (Video, slides, handout) Errata here! | |
| Friday 2023/11/10 Quiz 6 due | Thursday 2023/11/09 Q&A 6 (Padlet, board, recording) | Monday 2023/11/13 Problem class 6 (Sheet, solutions) Recordings: early, late | |
| Week 8 | Monday 2023/11/13 Videos released | 7-1: Linear programming (Video, slides, handout) Errata here! | 7-2: How the simplex algorithm works (Video, slides, handout) |
| Optional resources | 7-3: Flow networks (Video, slides, handout) Errata here! | 7-4: The Ford-Fulkerson algorithm (Video, slides, handout) Errata here! | |
| Friday 2023/11/17 Quiz 7 due | Thursday 2023/11/16 Q&A 7 (Padlet, board, recording) | Monday 2023/11/20 Problem class 7 (Sheet, solutions) Recordings: early, late | |
| Week 9 | Monday 2023/11/20 Videos released | 8-1: Why Ford-Fulkerson looks so familiar (Video, slides, handout) Errata here! | 8-2: Applications of Ford-Fulkerson (Video, slides, handout) |
| Optional resources | 8-3: SAT and the class NP (Video, slides, handout) Errata here! | 8-4: NP-completeness of 3-SAT (Video, slides, handout) | |
| Friday 2023/11/24 Quiz 8 due | Thursday 2023/11/23 Q&A 8 (Padlet, board, recording) | Monday 2023/11/27 Problem class 8 (Sheet, solutions) Recordings: early, late | |
| Week 10 | Monday 2023/11/27 Videos released | 9-1: Independent sets and vertex covers (Video, slides, handout) Errata here! | 9-2: Non-examinable sketch proof of the Cook-Levin theorem (Video, slides, handout) |
| Optional resources | 9-3: NP versus Co-NP (Video, slides, handout) | 9-4: Dealing with NP-hard problems (Video, slides, handout) | |
| Friday 2023/12/01 Quiz 9 due | Thursday 2023/11/30 Q&A 9 (Padlet, board, recording) | Monday 2023/12/04 Problem class 9 (Sheet, solutions) Recordings: early, late | |
| Week 11 | Monday 2023/12/04 Videos released | 10-1: Weighted interval scheduling (Video, slides, handout) | 10-2: Dynamic programming (Video, slides, handout) |
| Optional resources | 10-3: The Bellman-Ford algorithm (Video, slides, handout) Errata here! | 10-4: The real Bellman-Ford algorithm (Video, slides, handout) | |
| Friday 2023/12/08 Quiz 10 due | Thursday 2023/12/07 Q&A 10 (Padlet, board, recording) | Monday 2023/12/11 Problem class 10 (Sheet, solutions) Recordings: early, late | |
| Week 12 | No more material! | Thursday 2022/12/14 Q&A 11 (Padlet, board, recording) | Friday 2023/12/15 Quizzes reopened here for revision purposes. (Not for credit!) |
What’s in the unit
For more details on any of this, take a look at the first lecture video above.
Video lectures will be released every Monday morning, at a rate of four 15-25 minute videos per week. Everything in these lectures will be examinable unless explicitly stated otherwise, so you should watch them all carefully and make sure you understand them well. You should aim to watch all of them before the quiz deadline that Friday. Please do actually watch them rather than just skimming through the slides - some things are much easier to understand when someone’s talking through them!
Textbook readings will be released at the same time as the video lectures, if you’d like more information or more detailed proofs. They are all completely optional and non-examinable, but they’re a good place to try if you want another explanation of something.
Blackboard quizzes are weekly summative exercises covering that week’s material. Each quiz will be released on Monday morning, and due at noon on Friday. They will be automatically marked as soon as you submit them, and you will immediately be able to see what you got wrong and why. Together, they will account for 10% of your unit mark. However, any mark of 50% or more on a quiz will count as 100% in this calculation - in other words, everyone who makes a reasonable attempt will receive full marks. All the material you need for these quizzes will be covered in the video lectures, but you are encouraged to use any other resources you find helpful, and to work on them together with your friends. They’re not timed, and you can leave the page after starting and come back later. In addition to being worth marks in and of themselves, these quizzes will be good preparation for the short-answer portion of the exam.
Q&A sessions are weekly hour-long sessions in which I answer any questions about the unit you might have - for example, questions about the video lectures, the problem classes, the Blackboard quizzes or the exam. These will be run online with Padlet and Teams, allowing you to ask questions anonymously or in advance (with TA moderation). I’m running them online not because of covid, but because I’ve tried running them both online and in-person and I sincerely think they work better online. Attendance is optional, but encouraged if you’re having difficulty with any part of the week’s material.
Drop-in sessions with TAs will run several times per week. These are similar to “office hours” - you can come along without booking in advance to talk to someone one-on-one. The times are the following:
Monday 1pm-2pm: MVB 2.59
Tuesday 1pm-2pm: MVB 4.01
Wednesday 3pm-4pm: MVB 4.01
Thursday 11am-noon: MVB 4.01
Friday 4pm-5pm: MVB 4.01
Problem sheets are weekly formative exercises covering the previous week’s material. Each sheet will be discussed in an in-person problem class the week after it is released. These will be ~100-person classes led by John, and they won’t quite follow the typical model of students doing problems while TAs wander around helping people. You don’t have to try the sheet before the class, or even look at it. You do have to bring a copy of the sheet and make an effort to understand the previous week’s material via the videos, Blackboard quizzes, Q&A, and asking questions on the unit team. The classes will then be a split between interactive lectures on how to solve problems and trying the ideas out for yourselves (either on your own or with your friends).
It’s also worth noting that you should not try to finish the problem sheets! They contain far too much work to finish them in a week without neglecting your other units, and normally we’ll only pick out a few questions to discuss during problem classes. The reason there are so many questions is that they’ll also be good preparation for the long-answer portion of the exam, so you can double back later on and use them for practice while you’re revising.
While I can’t require that you wear a mask, I would still ask you to do so. When the government stopped bothering to keep track in March 2023, 2.9% of the UK population (1.9 million people) were experiencing long COVID symptoms according to the official data, over 90% of them for 12 weeks or more. It is true that being vaccinated reduces the risk of long COVID, but “only” by about half, and there’s not much protection from having been infected in the past. My own anecdotal experience agrees with this - four of my friends have life-altering symptoms from long COVID, including three who caught omicron while fully vaccinated. In my opinion, it’s just not a smart risk to take when you can avoid it by wearing a good mask. Unfiltered or poorly-fitting cloth masks and surgical masks are a nice gesture to protect others, but will do very little to protect you. I’ll be wearing one of these - a decently-fitting cloth mask with insertable FFP2 filters. It’s not perfect protection, but it’s good enough to massively cut your risk without being overly bulky or muffling. If you are especially worried about COVID (e.g. due to immunosuppression) and would otherwise not come to the problem classes, I would recommend one of these masks with these FFP3 filters - they have a completely airtight seal and will give you absolutely perfect protection, at the cost of making you look and sound a bit silly.
I don’t take attendance at problem classes, and I’d encourage anyone who is feeling ill or who has tested positive not to attend - recordings will be made available on the unit page after the fact, so you can catch up easily.
Planning your time
The baseline expectation is that as a Bristol student, you should be spending 40 hours per week on your course, i.e. the same amount of time you’d spend with a full-time job. This unit is worth 10 credit points out of 60 for the term, so you should aim to spend about 7 hours per week on it. Roughly speaking, that will divide into:
- 2 hours per week on video lectures;
- 2.5 hours per week on self-study getting to grips with the material;
- 1 hour per week on the Blackboard quiz; and
- 1.5 hours per week on attending the problem classes.
The self-study might involve e.g. going back over the lecture notes, or attending the Q&A, or looking at the textbook readings, or asking questions on the unit team, or trying questions from the problem sheet - the important thing is that you put the time in, and that you work in the way that suits you best.