All material for the course Algorithms and Data Structures II (course 1DL231) including slides, lecture plan, assignments and exam information. Management of groups, handing in of assignments, and discussion forums will be handled by studium. All slides and other material can be found on this website.
This page is an elaboration of the learning outcome of course plan
Specifically we will cover the following topics and sections of the book (for a CLRS4 reading guide see the individual lecture pages):
| Topic | CLRS3 Textbook |
|---|---|
| Reminder, growth of functions, big-Oh notation, recurrences and divide and conquer. | Chapters 1-4, except Section *4.6 |
| Dynamic Programming | Chapter 15 |
| Reminder Elementary Graph Algorithms | Chapter 22 Except 22.4 |
| Greedy Algorithms | Chapter 16, except Sections *16.4 and *16.5 |
| Minimum Spanning Trees (MST) | Chapter 23 (we only study Prim’s algorithm) |
| Single-Source Shortest Paths | Chapter 24: pages 643-650 and Section 24.3 |
| (we only study Dijkstra’s algorithm) | |
| Maximum Flow | Chapter 26, except Sections *26.4 and *26.5 |
| Disjoint Sets/Union Find | These notes or Chapter 21 |
| Strings Matching | Chapter 32, except Sections 32.3 and *32.4 |
| P versus NP | Chapter 34 |
In Lectures you can find a more detailed lecture plan with links to additional resources. The timing of the assignments has been done quite carefully. By the time you are to start the each assignment we should have covered the material in the assignments.
There is a menu item for each lecture where you can find a reading guide for the textbook, and links to additional material.
Please note that this timetable is still preliminary and is subject to change. The official timetable is in timeedit.
For the lecture locations please look at timeedit timeedit schedule is always correct. If there are any discrepancies between this page and timeedit, then please inform me.
| Lecture/Assignment | Date | Topic |
|---|---|---|
| 1 | 2026-11-03 8-10 | Introduction to the course and revision of Algorithm analysis |
| 2 | 2026-11-04 10-12 | Revision of Graphs, and the Python API for the assignments (Frej Knutar Lewander) |
| 3 | 2026-11-06 10-12 | Dynamic Programming - Introduction |
| Help 1a | 2026-11-06 13-15 | |
| 4 | 2026-11-09 13-15 | Dynamic Programming - Knapsack |
| Help 1b | 2026-11-10 13-15 | |
| Help 1c | 2026-11-11 8-10 | |
| 5 | 2026-11-13 10-12 | Greedy Algorithms |
| Deadline Assignment 1 | 2026-11-14 15:00 | |
| 6 | 2026-11-17 10-12 | Minimal Spanning Trees |
| Help 2a | 2026-11-18 13-15 | |
| Grading session Assignment 1 | TBA | By invitation only |
| 7 | 2025-11-20 13-15 | Network flows |
| Help 2b | 2025-11-23 10-12 | |
| Solution Session Assignment 1 | 2026-11-25 09-10 | Obs only 45 mins |
| 8 | 2025-11-25 13-15 | Networks flows, Bipartite matching |
| Help 2c | 2025-11-26 10-12 | |
| Deadline Assignment 2 | 2026-12-27 15:00 | |
| 9 | 2026-12-02 10-12 | Union Find |
| Help 3a | 2026-12-07 8-10 | |
| 10 | 2026-12-9 8-10 | P vs NP |
| Help 3b | 2026-12-14 10-12 | |
| 11 | 2026-12-15 13-15 | P vs NP |
| Solution Session Assignment 2 | 2026-12-18 9-10 | Obs only 45 mins |
| Help 3c | 2026-12-18 13-15 | |
| Exam | 2027-01-08 | For time and place please check Ladok |
| Deadline Assignment 3 | 2027-01-?? 15:00 |
Guest Lecture by Frej Knutar Lewander
Revision on Digraphs/Digraphs: Slides 1-24 Although some of this will be revision, you should pay attention to how the graph representation effects the time complexity.
The textbook does not say that much about pseudo-polynomial time and the 0-1 Knapsack problem, even though it is an important concept. There there is plenty of material on the internet. I suggest that you start with the Wikipedia entries on Pseudo-polynomial time and the Knapsack problem. You also might find these notes useful.
When I do these lectures live, it normally takes me 3 lectures to go through the material slowly and do lots of examples. This is a list of topics that are needed to under network flows. You goal should be to understand each topic.
Alternative mathematical API. Flows that are Skew Symmetric flows, that is $f(u,v)= - f(v,u)$. We’ll do this on the blackboard, but skew symmetric flows are a bit counter intuitive, but they make the proofs and implementation easier. Take a look at the presentation at Wikipedia. This is not examined, and I won’t go into much detail.
Min-Cut Max-Flow duality slides 25-36 of NetworkFlow I
Choosing the wrong paths: Exponential worst case slides 37-41 of NetworkFlow I
Summary of complexity results 73-74 of NetworkFlow I
Bipartite matching slides 1-17 of NetworkFlow II.
I used slides 1 to 41 from UnionFind.
Both William Fist and Josh Hug cover the same material, although Josh Hug takes it much more slowly.
What is the union-find API?
What are some of the applications of union-find?
How can I use trees to represent sets?
How do I represent sets of trees as a forest?
What are the different strategies for combining trees? Link by Size and Link by Rank.
What is path compression? How does this improve the complexity of union-find? Note that if you go deeply into the analysis of union-find you will come to amortised analysis. This is the analysis of the complexity of an algorithm over multiple-runs. Amortised analysis is not part of this course, but it is part of AD3 - 1DL481 that is normally taught by Pierre Flener
This will be a not so formal introduction to P and NP. Every computer scientist should know something about NP complete problems. If you know that a problem is NP complete, then you know that it is very hard to find an optimal solution.
This material is examined.
These lectures will given by Pierre Flener.
The slides for the lecture can be found here
There are 3 mandatory assignments, to be done in alone, worth 2 higher-education credits (ECTS credits) in total.
The main objective of the assignments is to exercise the theoretical knowledge gained in the lectures. You are to hand in the code and a report. The code should follow the coding convention and the report must follow the structure and content of the demo report
For each assignment, the assistants supervise 3 help sessions for troubleshooting in the preparation of your reports.
Each assignment has 2 independent problems, each yielding a problem score in $0..5$, hence there is a maximum of 30 points to earn. For each problem, a skeleton code in Python 3 with test cases is provided. Insufficiently good reports can be defended orally to an assistant in scheduled grading sessions. Solutions are discussed by the assistants in solution sessions.
You must submit :
The skeleton code comes with an extensive set of test cases. Your submitted code must pass all test cases. If you code does not pass all test cases, then we will not read your report and you will receive a mark of 0 for that part of the assignment. Your implementation should be correct, and if it is correct then you should be able to pass all the provided test cases.
The objective of a help session is only for the assistants to help you prepare an acceptable solution for the assignment with the closest upcoming deadline. Also, the necessary course material will normally have been presented in lectures at least a week prior to the first help session. You are thus able and even strongly encouraged to prepare your solution as far as possible until the help sessions and to attend them, in order to make best use of that reserved time span of personal attention by the assistants.
The objective of a solution session is only for the assistants to discuss acceptable solutions to the assignment of the previous deadline. No code will be handed out. The first two solution sessions are merged with the initial help sessions to the next assignment. For timetable reasons, the third assignment has no solution session.
Comments on your submitted report can be found on Studium; more detailed comments can be obtained orally from the assistants upon appointment.
All assignment reports, with imposed structure must be submitted electronically via Studium, whose clock may be different from yours. Submission deadlines are hard. Grading will only start after a deadline, so you can submit multiple times until then.
Please see the Ethics Guidelines in the FAQ.
We reserve the right to give different assignment scores to the teammates of a team, depending on the performance at the grading session.
Please report any problems within a team to the head teacher, who will handle the case in confidence, in the best interest of both teammates, keeping the ethics dimension in mind.
One higher-education credit (ECTS credit) translates under Swedish university law into an expected 26.67 hours of work for the average student. Hence 133.33 hours are expected on this 5-credit course.
The assignments are worth 2 credits in total. Not counting the 19.5 hours spent on the 13 lectures, the 3 assignments are calibrated to take an average of 30 hours each, for the average student, for each teammate, including the corresponding help, grading, and solution sessions, and this time counts also as exam preparation.
All this does not clash with other courses you are taking, as university studies are legally defined to take 400 hours of work per study period (normally 10 weeks), and the standard 15 credits targeted in a study period are calibrated to reach that total.
Do not expect the 3 assignments to be equally labour-intensive, and do not expect the 2 problems of each assignment to be equally labour-intensive. Assignment 3 is calibrated somewhat shorter due to the proximity of the exam.
Students from previous academic years who have not yet been awarded the credit point(s) for the assignments contact the head teacher.
All assignments are to be written in Python 3. Your assignments will be partially tested by an automated system, and the exact version of Python that will be used will be specified on the assignments.
The learning of sufficient Python skills is within your time budget for this course, and this should not take more than a couple hours.
We highly recommend you learn or use LaTex for typesetting your assignment reports in a professional way, but this is optional. The learning of LaTeX is outside your time budget for this course, but very well-invested as you will find out during the course or later.
A program for insertion sort that is fully annotated according to the coding convention is given on page 3 of the AD2 demo report which also contains examples of all LaTeX2e commands you need for this course.
The first two pages of the AD2 demo report contain a checklist that you must follow before submitting and the coding convention that you must follow.
The main objective of the assignments is to exercise the theoretical knowledge gained in the lectures, on carefully selected problems of our choice. We are not just interested in sufficiently correct and efficient programs, but also in explanations and a runtime analysis, hence a report is also required for each assignment and its quality has an impact on the score for your assignment.
See the demo report and LaTeX source for the imposed document structure and an indication of the expected quality of content. Our expectations are higher than at the exam, as the aims are to learn something and to prepare for the exam: we expect at least a high degree of correctness, completeness, and compliance with the coding convention of this course.
There is an individual, written, closed-book exam at the end of the course.
Some old exams can be found here.
One higher-education credit (ECTS credit) translates under Swedish university law into an expected 26.67 hours of work for the average student. Hence 133.33 hours are expected on this 5-credit course.
The exam is worth 3 credits. In addition to the exam preparation performed while working (during 90 hours) for the 2 credits for the assignments the remaining preparation and the taking of the exam are expected to take 24 hours. Recall that 19.5 hours are spent on the 13 lectures.
All this does not clash with other courses you are taking, as university studies are legally defined to take 400 hours of work per study period (normally 10 weeks), and the standard 15 credits targeted in a study period are calibrated to reach that total.
The exam grade is determined by a published scale depending on the exam score.
The overall grade is determined by a published scale, depending on the assignment and exam scores.
Recommended exercises from the CLR3 book for exam preparation. Don’t forget the book is available online at the University library. All these exercises are from the third edition. I don’t have the answers to the questions, and some of the exercises are non-trivial but will give you a deeper understanding of the material in book.
Chapter 15
Chapter 16
Chapter 21
Chapter 23
Chapter 23, 26.1-26.2
Chapter 32
The three assignments are worth 2 higher-education credits (ECTS credits). The assignment grade is as follows when $a_i$ is your final score (out of 10) on Assignment $i \in 1..3$, and $a = a_1 + a_2 + a_3$ is your total score. Each assignment is divided into two Problems with sub parts. On each of the problems you must have a score of at least 1 (out of 5) to pass the course. If you have a 0 on any of the two problems any assignment, then you will fail the assignments.
You must earn at least 3 points (of 10) on each of the assignments.
| Grade | Condition |
|---|---|
| 5 | $a \in \\{25\ldots 30\\}$ |
| 4 | $a \in \\{20\ldots 24\\}$ |
| 3 | $a \in \\{15\ldots 19\\}$ |
The exam is worth 3 higher-education credits (ECTS credits). The exam is marked out of 20. The exam is constructed in such a way to have no marks that are fractions of a point. The following table gives your grade assignment. Let $e$ be your total exam score:
| Grade | Total Score |
|---|---|
| 5 | $e \in \\{17 \ldots 20\\}$ |
| 4 | $e \in \\{14\ldots 16\\}$ |
| 3 | $e \in \\{10\ldots 13\\}$ |
| U | $e \in \\{0\ldots 9\\}$ |
There is no longer a bonus point scheme combining the assignment and the exam mark for the final grade. Your final grade is now your exam grade. You are strongly encouraged to aim for a 5 on the assignments. In the past there is a strong correlation between students who got a 5 no the assignments and a 5 on the exam. There is an overlap on material examined in the assignments and material examined in the exam. Aiming for a 5 on the assignments is good preparation for some of the exam.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (fourth edition) The MIT Press, 2022. This will be referred to as CLRS4.
The second edition errata or third can also be used. The third edition will be referred to as CLRS3.
Note that it is now possible to access library resources online without being on the University network or using a VPN. You will be prompted for you CAS login. You need to go through the library search system. For the fourth edition follow this CLRS4 and for the third edition follow this CLRS3.
Even when the book is available for free via the University library I recommend that you buy the book. It is one of the best textbooks on algorithms available.
At the moment most of the reading guides refer to the third edition, but I will update the reading guide for the fourth edition as I go along.
The following book, underlying most of the slides that have been used in previous years, can also be used but does not cover Section 4.3 and Chapters 21 and 32 of CLRS3:
Some useful books and links
Algorithm Design: Foundations, Analysis, and Internet Examples, a textbook by Michael T. Goodrich and Roberto Tamassia, published by John Wiley & Sons in 2001
Algorithms, a textbook by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani, published by McGraw-Hill in 2007
VisuAlgo, visualising data structures and algorithms through animation, a project led by Steven Halim
Data Structure Visualizations by David Galles
Dictionary of Algorithms and Data Structures by Paul E. Black
The Stony Brook Algorithm Repository by Steven Skiena, based on his textbook The Algorithm Design Manual, second edition, published by Springer-Verlag in 2008
The learning of sufficient skills on the Python programming language is within your time budget for this course, but this should not take more than a couple hours. To the best of our knowledge, almost no student on this course has officially learned Python at UU, so nobody is at a disadvantage.
We highly recommend you learn or use LaTeX for typesetting your assignment reports in a professional way, but this is optional. The learning of LaTeX is outside your time budget for this course, but very well-invested as you will find out during the course or later. Here are some LaTeX resources:
The demo report and LaTeX source, which also contain examples of all LaTeX commands you need for this course.
The LaTeX wikibook a gentle but thorough introduction.
Don’t know the LaTeX code for that mathematical symbol you need? Draw it by hand at Detexify, and the applet will find the code for you.
clrscode3e package for typesetting algorithms as in CLRS3.
When Pierre Flener taught the course he used slides by Kevin Wayne. For some of the lectures I use Kevin Wayne’s slides, but for lectures where I do not, you are still encouraged to look at Kevin Wayne’s slides. They contain a number of useful examples.
| Topic | Slides | Extra Material (recommended) | CLRS3 Textbook |
|---|---|---|---|
| Introduction and Logistics | slides numbered 1-7 of Introduction.pdf; | Chapters 1-2 | |
| Reminders: Growth of Functions, Recurrences, and Divide & Conquer | slides numbered 1-3, 6-23, 30-32, 35, 39, 42-43, 46-49 of AlgorithmAnalysis.pdf; slides 1-14 of DemoMerge.pdf; DemoBinarySearch.pdf; slides 1-13 of DivideAndConquerI.pdf; slides 1-13, 26-41 of DivideAndConquerII.pdf | AD1-excerpts.pdf (some slides from when I taught AD1) | Chapters 3-4, except Section *4.6 |
| Dynamic Programming | slides numbered 1-18, 30-38, 54 of DynamicProgramming.pdf | slides 39-51 of DynamicProgramming.pdf | Chapter 15; the slides have other examples: you are encouraged to self-study the textbook examples |
| Reminder: Elementary Graph Algorithms | slides 1-24, 33-43 of Graphs.pdf | Chapter 22, except Section 22.4 (which is not needed for AD2) | |
| Greedy Algorithms | slides 1-8 of GreedyAlgorithmsI.pdf | slides 9-15 of GreedyAlgorithmsI.pdf plus DemoEarliestFinishTimeFirst.pdf
(corresponding to Section 16.1); slides 16-23 of GreedyAlgorithmsI.pdf plus DemoEarliestStartTimeFirst.pdf | Chapter 16, except Sections *16.4 and *16.5; the slides have other examples: you are encouraged to self-study the textbook examples |
| Minimum Spanning Trees (MST) | slides numbered 21, 23-24, 28-34, 36, 43-45, 57 of GreedyAlgorithmsII.pdf; slides 23-40 of DemoMST.pdf | visualisation of Prim's algorithm | Chapter 23 (we only study Prim's algorithm) |
| Single-Source Shortest Paths | slides 1-15 of GreedyAlgorithmsII.pdf; DemoDijkstra.pdf | visualisation of Dijkstra's algorithm | Chapter 24: pages 643-650 and Section 24.3 (we only study Dijkstra's algorithm) |
| Maximum Flow | slides 1-42, 48-49, 56-57, 73-79 of NetworkFlowI.pdf; DemoFordFulkerson.pdf; slides numbered 1-12, 17-20, 24-44 (all without the proofs) of NetworkFlowII.pdf | visualisation
of Ford-Fulkerson's algorithm; slides 42-57 of NetworkFlowI.pdf if you are interested; slides numbered 45-81 of NetworkFlowII.pdf if you are interested | Chapter 26, except Sections *26.4 and *26.5 |
| Disjoint Sets | slides 1-42, 46 of UnionFind.pdf | visualisation; section 5.1.4 of another textbook | Chapter 21, except Sections 21.2 and *21.4 |
| String Matching | slides 1-14, 27 of StringMatching-A.pdf; StringMatching-B.pdf | Chapter 32, except Sections 32.3 and *32.4 | |
| P versus NP | PversusNP.pdf | talk by Prof. Michael Sipser | Chapter 34 |
Before contacting anyone for help, please check whether your question has an answer in the FAQ list below. If not:
If you have a question about the lecture material or course organisation, then contact the head teacher.
If you have a question about the assignments or infrastructure, then contact the assistants at a help or solution session for an immediate answer. Short clarification questions (that is: not about programming issues) that are emailed to the AD2 helpdesk are answered as soon as possible during working days and hours. No answer means that you should go to a help session: almost all the assistants’ budgeted time is allocated to grading and to the help, grading, and solution sessions.
The legislation on plagiarism and cheating and Pierre Flener’s summary of Uppsala University will be rigorously applied, without exceptions. This disallows using a public repository (such as GitHub), where you should use a free private student repository for code management. We reserve the right to use plagiarism detection tools and point out that they are extremely powerful.
On this course you are not allowed to use LLMs or coding assistants when doing your assignments. Explicitly: LLM coding assistants when writing your code, and no use of generative AI for your report. You are allowed to use tools such as grammar checkers to improve your report. All the the work should be completely your own.
The only way to master material in the course is to think and implement the solutions yourself. LLMs are useful only when you can understand the code that they produce.
How do I best use my time, and yours, in order to solve an assignment? Prepare your solution as far as possible until the corresponding help sessions, in order to make best use of that reserved timespan of personal attention by the assistants. This is much more effective than going to a help session, printing out the assignment (which was published at least a week before the first help session and often does not require any material taught in the meantime), and not meeting all the difficulties until the end of the two session hours.
Why is there not more email support for the assignments? We have scheduled almost all the standard time budget for the lectures, help sessions, grading sessions, solution sessions, grading, and preparation. This is why we can only answer to emailed short questions that trigger brief reply times, and this is a more personal and rational way of spending the standard time budget: more email support would inevitably result in fewer help sessions.
I am lost! Why do the assignment instructions not tell us how to solve the questions? Stating only what output has to be computed from the inputs is a pedagogical choice. In real-life engineering problems, you are not asked to solve a problem by using method m on page p of textbook t. Come to some of the help sessions of an assignment in order to get advice on what is wrong with your current solution or get hints on how to proceed.
Why are the assignment questions neither in sync with the lecture contents, nor closer to them? They are. The lecture schedule is carefully planned so that the relevant material has been covered in time for you to start the assignment. Quite often in a lecture I will work through a similar problem to one of the assignment questions. Come to the lectures.
Why are the assignments to be programmed in Python rather than in any language of my choice? We have no resources for offering skeleton programs and simple test cases for more than one programming language. A lot of students prefer those features over the freedom of choice of a programming language. Besides, our semi-automated grading system is language-specific for the same reason: it allows us to grade assignments faster and to dedicate more of the standard time budget to actual teaching.
Why do we need to hand in reports in addition to programs? This is an algorithms course and the algorithms underlying your programs have to be analysed, hence a report is needed, as we are not just interested in knowing the complexity you claim your algorithm has, but also in how you made that claim. Also note that this course was chosen in order to fulfil the curriculum goal of the ability to communicate in writing: see the course goals
Why do we not get more finegrained feedback on our assignment reports and programs? Our solution sessions are a more rational way to use the standard time budget: we give collective feedback instead of finegrained team-wise feedback. More detailed comments can be obtained orally from the assistants upon appointment.
Why do I need to spend so much time on the assignments when they are only worth 2 credits? Any time spent on the assignments reduces the amount of time needed to prepare for the exam, so it pays off.
When will the exam be graded? It was a multiple-choice exam, so why are “the” answers not published right away? The head teacher will first read the starred comments, if any, about the questions in the handed-in answer sheets and then only grade, as such comments may affect his judgement about which answers can be acceptable with full or partial credit. He will grade as soon as he finds the time after getting the answer sheets. Please be patient.
Where are model answers to the questions of previous exams? Nowhere, except for the multiple-choice exams. The head teacher does not believe in making such answers available (on-line or otherwise) without discussing solution processes or any alternative correct answers in person at the same time. This is the pedagogical approach taken also for the assignments, where you can contact the assistants for this purpose.
Will there be algorithm design questions in the exam? Will exam questions be similar to the assignment questions? Algorithmic skills are mostly tested in the assignments. Any algorithms for exam questions will be a handful lines long, but algorithm design experience from the assignments ought to be useful for such exam questions. Analytic skills tested in the assignments also ought to be useful for exam questions.
Will we have multiple-choice exam questions? The head teacher has the right for any form of examination and decides as he sees fit. Note that a multiple-choice question saves you the time of tidying up your answer notes explaining how you reached your chosen answer. Further, if you think a question is unclear or wrong, then you are free to explain on the answer sheet what your difficulty with the question is and what assumption underlies the answer you have chosen or the other answer you indicate. Also, partial credit can be given to some answers in exceptional circumstances.
What will the exam questions be? What should I focus on when preparing the exam? Try and come to the lectures, as the head teacher makes it very clear there what the most important elements of the course material are.
I nearly passed the exam. What can I do to avoid taking the next exam? No make-up opportunities will be created for near-passes, as the head teacher evaluates those cases very carefully before announcing the exam results.
Why is there no bonus point scheme for the assignments and the exam? There is no longer a bonus point scheme combining the assignment and the exam mark for the final grade. Your final grade is now your exam grade. You are strongly encouraged to aim for a 5 on the assignments. In the past there is a strong correlation between students who got a 5 no the assignments and a 5 on the exam. There is an overlap on material examined in the assignments and material examined in the exam. Aiming for a 5 on the assignments is good preparation for some of the exam.