6 EC
Semester 2, period 4
5062ALCO6Y
Computers are always becoming faster and more powerful. On the other hand, we also want to use computers to tackle increasingly large and complicated problems. These two developments balance each other out, meaning that our annoyance (objective or otherwise) about the slowness of computers remains among us. Impressive savings in computing time and memory use can be achieved not only through better, faster and more powerful hardware, but especially through better thought-out software that is more tailored to the problem. Simple observations can often make the difference between days of computing time and minutes. In this lecture we will pay attention to a number of such programming methods that have been widely used. Examples of this are: greedy algorithms, dynamic programming, backtracking, branch & bound. We also will look at the concept of network flows, and how to use network flows to solve a wide range of problems. Some problems are provably so difficult that there no fast algorithms for them exist. In that case it is permissible to settle for solutions that provide only an approximation of the correct or optimal solution, or with programs that are only averagely fast. In the second part of the course we will pay attention to these proofs - which is a topic called complexity theory.
We will use the book "Algorithms" by Jeff Erickson, freely available online at http://algorithms.wtf/ . A paper version of the book can also be ordered for a reasonable price at bookstores.
The exercises will be made available on Canvas each week.
Slides will be made available after the lecture (within a few days).
The lectures will introduce the covered topics. These will be practiced in the exercise class (with a teaching assistant present), and tested as group homework exercise. Additionally, there are individual programming exercises for a practical test of the material. The material will also be tested at a mid-term and final exam.
There is no attendance requirement - however students are of course encouraged and recommended to attend all sessions.
|
Activity |
Hours |
|
Lectures |
24 |
|
Exercise class |
14 |
|
Exams |
6 |
|
Self study |
124 |
Additional requirements for this course:
We will schedule a mid-term test, and a final exam, for which you should be present. Other than that, there is no attendance requirement (except that we of course recommend attendance of the classes).
| Item and weight | Details |
|
Final grade | |
|
4% Programming assignment 1 | |
|
4% Programming assignment 2 | |
|
4% Programming assignment 3 | |
|
4% Programming assignment 4 | |
|
4% Programming assignment 5 | |
|
7.5% Serie 1 | |
|
7.5% Serie 2 | |
|
7.5% Serie 3 | |
|
7.5% Serie 4 | |
|
50% Exam average | Must be ≥ 5.5 |
|
10% 05-03-2026 Mid-term exam | |
|
40% 27-03-2026 Final exam |
There are four group assignments, a mid-term test, a final exam, and five programming assignments. Group assignments will be done in groups of a maximum of three students. Programming exercises are done individually and graded (partially) automatically.
The group assignments, taken together, form 30% of the final grade. They will be graded in the range 1-10. The programming exercises are graded in the range 1-10 and form 20% of the final grade. The mid-term will form 10% of the final grade, and final exam will form 40% of the final grade.
A passing (weighted) average for the mid-term and exam is required to pass the course. The scheduled retake is used only for the 50% of the final grade comprising the mid-term and final exam, and will replace the average grade for both these tests.
Feedback on the theoretical assignments will be provided through the digital learning environment. Additionally, a student or group can contact the teacher through the digital learning environment to request a more detailed explanation.
weekly theory assignments (homework) about the lecture material, to be done in small groups
A different topic each week. To be done individually.
In-class individual test mid-way in the course
Over het algemeen geldt dat elke uitwerking die je inlevert ter verkrijging van een beoordeling voor een vak je eigen werk moet zijn, tenzij samenwerken expliciet door de docent is toegestaan. Het inzien of kopiëren van andermans werk (zelfs als je dat hebt gevonden bij de printer, in een openstaande directory of op een onbeheerde computer) of materiaal overnemen uit een boek, tijdschrift, website, code repository of een andere bron - ook al is het gedeeltelijk - en inleveren alsof het je eigen werk is, is plagiaat.
We juichen toe dat je het cursusmateriaal en de opdrachten met medestudenten bespreekt om het beter te begrijpen. Je mag bronnen op het web raadplegen om meer te weten te komen over het onderwerp en om technische problemen op te lossen, maar niet voor regelrechte antwoorden op opgaven. Als in een uitwerking gebruik is gemaakt van externe bronnen zonder dat een bronvermelding is vermeld (bijvoorbeeld in de rapportage of in commentaar in de code), dan kan dat worden beschouwd als plagiaat.
Deze regels zijn er om alle studenten een eerlijke en optimale leeromgeving aan te kunnen bieden. De verleiding kan groot zijn om te plagiëren als de deadline voor een opdracht nadert, maar doe het niet.
Elke vorm van plagiaat wordt bestraft. Als een student ernstige fraude heeft gepleegd, kan dat leiden tot het uitschrijven uit de Universiteit.
Zie voor meer informatie over het fraude- en plagiaatreglement van de Universiteit van Amsterdam: www.student.uva.nl
The planning is tentative, and determined by how fast we progress through the material. If we have extra time, we will treat an extra advanced topic in the final week, such as probabilistic algorithms.
Week 1: Complexity measures, worst case, average case. Recursion (Master theorem), divide & conquer.
Week 2: Divide and conquer (continued), fast fourier transform. Dynamic programming.
Week 3: Dynamic programming (continued). Greedy algorithms.
Week 4: Graph algorithms and network flows.
Week 5: Mid-term week (no new topic).
Week 6: Complexity theory start. Machine models, definitions P, EXP, NP, reductions.
Week 7: Complexity theory (continued). Comparison sort lower bound. One advanced topic to be decided (for instance space complexity, PSPACE).
There are homework exercises most weeks, that are done in groups.
There is a programming exercise most weeks, which is done individually.
Prerequisites: Some programming experience in imperative languages is required. A basic knowledge of graphs and graph properties is helpful. Mathematical knowledge (how to prove something) will be useful for this course.
We are expanding the opportunity to practice with implementing the algorithms we see in the lectures, based on student feedback.
Lecturers:
Exercise lab teachers: