Table of contents
Welcome
Welcome to Algorithms and Data! In TB1 we’ll be in the algorithms half of the unit, which 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. In any given week, you should:
- Watch the videos. (Don’t just skim the slides!)
- Do the weekly quiz to check your understanding of the basic material.
- Come to the problem class the following week to learn how to apply the material to unfamiliar problems - these are half-lecture half-lab, not just a place to work on the problem sheet.
If (and only if!) there’s part of the material you’re having trouble with in steps 2 or 3, first make sure this isn’t a mistake in the video other people have already noticed - if it is, it will be posted as errata and linked directly from the video below. After that, your best options are:
- Come to the weekly Q&A, where you can ask the lecturer questions either directly or anonymously via Padlet (linked below).
- Come to the drop-in sessions, which will hopefully be near-daily Monday to Friday, to ask a TA.
- Ask on the unit Team, which is monitored by both TAs and the lecturer and should get a response within a day.
- Check out the recommended reading for another perspective on the same material.
| Week 1 | Monday 2024/09/16 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) | 1-4: Using O-notation (Video, slides, handout) Errata here! | |
| Monday 2024/09/23 Quiz 1 due | Friday 2024/09/20 Q&A 1 (Padlet, recording) | Monday 2024/09/23 Problem class 1 (Sheet, solutions, recordings 1, 2) | |
| (Optional: Dummy quiz to test your browser works.) | |||
| Week 2 | Monday 2024/09/23 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 2024/09/30 Quiz 2 due | Friday 20243/09/27 Q&A 2 (Padlet, recording) | Monday 2024/09/30 Problem class 2 (Sheet, solutions, recordings 1, 2) | |
| Week 3 | Monday 2024/09/30 Videos released | 3-1: Directed Euler walks (Video, slides, handout) | 3-2: Hamilton cycles (Video, slides, handout) |
| Optional resources | 3-3: Shaking hands (Video, slides, handout) | 3-4: Trees (Video, slides, handout) | |
| Friday 2024/10/07 Quiz 3 due | Friday 2024/10/04 Q&A 3 (Padlet, recording) | Monday 2024/10/07 Problem class 3 (Sheet, solutions) | |
| Week 4 | Monday 2024/10/07 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) | |
| Monday 2024/10/14 Quiz 4 due | Thursday 2024/10/11 Q&A 4 (Padlet, recording) | Monday 2024/10/14 Problem class 4 (Sheet, solutions, recordings 1, 2) | |
| Week 5 | Monday 2024/10/14 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) | 5-4: MSTs II: Kruskal’s algorithm (Video, slides, handout) Errata here! | |
| Monday 2024/10/28 Quiz 5 due | Friday 2024/10/18 Q&A 5 (Padlet, recording) | Monday 2024/10/28 Problem class 5 (Sheet, solutions, recordings 1, 2) | |
| Week 6 | Reading week! | No videos! | No quiz! |
| No resources! | No Q&A! | No problem class! | |
| Week 7 | Monday 2024/10/28 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! | |
| Monday 2024/11/04 Quiz 6 due | Friday 2024/11/01 Q&A 6 (Padlet, recording) | Monday 2024/11/04 Problem class 6 (Sheet, solutions, recordings 1, 2) | |
| Week 8 | Monday 2024/11/04 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! | |
| Monday 2024/11/11 Quiz 7 due | Friday 2024/11/08 Q&A 7 (Padlet, recording) | Monday 2024/11/14 Problem class 7 (Sheet, solutions, recordings 1, 2) | |
| Week 9 | Monday 2024/11/11 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) | 8-4: NP-completeness of 3-SAT (Video, slides, handout Errata here!) | |
| Monday 2024/11/18 Quiz 8 due | Friday 2024/11/15 Q&A 8 (Padlet, recording) | Monday 2024/11/18 Problem class 8 (Sheet, solutions, recordings 1, 2) | |
| Week 10 | Monday 2024/11/18 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) | |
| Monday 2024/11/25 Quiz 9 due | Friday 2024/11/15 Q&A 9 (Padlet link in Teams) | Monday 2023/12/04 Problem class 9 (Sheet) |
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 by Monday morning, and due at noon the following Monday. 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 in-person, but supported by Padlet, allowing you to ask questions anonymously during the session or or in advance before it (with TA moderation). 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 will be determined later, and we expect to announce them in week 1.
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.
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.
COVID policy
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 - five of my friends have life-altering symptoms from long COVID, including four who caught omicron while fully vaccinated. In my opinion, it’s just not a smart risk to take when you can mostly 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.
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.
3:45 — 1:02:30