Algorithms and Complexity
6 EC
Semester 2, periode 4
5062ALCO6Y
| Eigenaar | Bachelor Informatica |
| Coördinator | Florian Speelman |
| Onderdeel van | Minor Logic and Computation, jaar 1Bachelor Informatica, jaar 2Dubbele bachelor Wiskunde en Informatica, jaar 2 |
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/
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.
Except for the short tests, there is no attendance requirement - however students are of course encouraged and recommended to attend all sessions.
|
Activity |
Hours |
|
Lectures |
28 |
|
Exercise class |
14 |
|
Self study |
126 |
Aanwezigheidseisen opleiding (OER-B):
Aanvullende eisen voor dit vak:
Some lectures will start with a small test - attendance is required to make the test. We will announce which lectures on the digital learning environment - it will be approximately every other week. Other than that, there is no attendance requirement.
| Onderdeel en weging | Details |
|
Eindcijfer |
There are six group assignments, five tests, and five programming assignments. Group assignments will be done in groups of a maximum of three students. Tests are done individually during the lecture. Programming exercises are done individually and graded (largely) automatically.
The group assignments, taken together, form 50% of the final grade. They will be graded in the range 1-10. The tests will be graded in the range 1-5 and form 25% of the final grade. The programming exercises are graded in the range 1-10 and form 25% of the final grade.
A passing average, i.e. a 5.5 after renormalization, for the tests is required to pass the course. The scheduled retake is used only for the tests, and will replace the average grade for the tests. There will be an option to only retake a subset of the tests (chosen beforehand when registering for the retake).
| group assignment 1 | group assignment 2 | group assignment 3 | group assignment 4 | group assignment 5 | group assignment 6 | |
| test 1 | test 2 | test 3 | test 4 | test 5 | ||
| prog. assn. 1 | prog. assn. 2 | prog. assn. 3 | prog. assn. 4 | prog. assn. 5 | ||
| Retake 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
Five times a short test, during the start of the lecture.
A different topic each week. To be done individually.
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: Network flows continued. Linear programming.
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 each week that are done in groups.
There is a programming exercise each week, 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.
Lecturers:
Exercise lab teachers: