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.
For the lecture locations please look at timeedit. The timeedit schedule is always correct. If there are any discrepancies between this page and timeedit, then please inform me.
| Lecture/Assignment | Date | Topic |
|---|---|---|
| 1 | 2024-11-04 15:15-17:00 | Introduction to the course and revision of Algorithm analysis |
| 2 | 2023-11-05 13:15-15:00 | Divide and Conquer and Algorithm analysis |
| 3 | 2024-11-06 10:15-12:00 | Revision of Graphs, and the Python API for the assignments (Frej Knutar Lewander) |
| 4 | 2024-11-12 13:15-15:00 | Dynamic Programming - Introduction |
| Help 1a | 2024-11-13 15:15-17:00 | |
| 5 | 2024-11-15 10:15-12:00 | Dynamic Programming - Knapsack |
| Help 1b | 2024-11-19 08:15-10:00 | |
| Help 1c | 2024-11-21 10:15-12:00 | |
| Deadline Assignment 1 | 2024-11-22 13:00 | |
| 6 | 2024-11-22 10:15-12:00 | Greedy Algorithms |
| 7 | 2024-11-26 13:15-15:00 | Minimal Spanning Trees |
| Help 2a | 2024-11-29 08:15-10:00 | |
| Grading session Assignment 1 | 2024-11-29 15:15-17:00 | By invitation only |
| 8 | 2024-12-02 10:15-12:00 | Network flows |
| Help 2b | 2024-12-02 15:15-17:00 | |
| Solution Session Assignment 1 | 2024-12-03 13:15-14:00 | Obs only 45 mins |
| 9 | 2024-12-04 10:15-12:00 | Networks flows, Bipartite matching |
| Help 2c | 2024-12-06 08:15-10:00 | |
| Deadline Assignment 2 | 2024-12-06 15:00 | |
| 10 | 2024-12-09 13:15-15:00 | P vs NP (Pierre Flener) |
| Help 3a | 2024-12-10 10:15-12:00 | |
| 11 | 2024-12-11 13:15-15:00 | P vs NP (Pierre Flener) |
| Help 3b | 2024-12-12 10:15-12:00 | |
| Solution Session Assignment 2 | 2024-12-16 11:15-12:00 | Obs only 45 mins |
| 12 | 2024-12-16 13:15-15:00 | Union Find |
| Help 3c | 2024-12-18 10:15-12:00 | |
| 13 | 2024-12-19 10:15-12:00 | String Matching |
| Deadline Assignment 3 | 2025-01-02 13:00 | |
| Exam | 2025-01-08 | TBA |
Chapter 3 and 4 (except 4.6) of CLRS3 or Chapter 3 and 4 (except 4.6 and 4.7) of CLRS4.
You might find the following slides useful: Divide and Conquer I which has some more examples on algorithm analysis, and Divide and Conquer II that has information on the master theorem.
You should know much more about the Big O notation. In particular
Further you should know about divide and conquer an algorithm design technique and the Analysis of Divide and Conquer using recurrence relations. You should understand and be able to reproduce a simple divide and conquer analysis of an algorithm such as binary search or merge sort. You should understand how to go from recurrence relations such as $$ T(n) = aT(n/b) + f(n) $$ to asymptotic analysis of the function $T(n)$. For which functions $g$ is the following statement true: $$ T(n) \in O(g(n)) $$
Although I do not expect expect you understand the proof, you should try to get an intuition of the different cases of the master theorem.
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
Bipartite matching slides 1-17 of NetworkFlow II.
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
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
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.
The specification and the grading rules for assignment 1 can be found in the following document. You are advised to read the grading rules carefully.
All skeleton code can be found here. You must use this years skeleton code, as it has changed from previous years.
A Zip file with all the assignments and the source of the demo report. If that link does not work then try copying and pasting the following link into your browser: http://user.it.uu.se/~justin/Assets/Teaching/AD2/ad2_source.zip
Don’t forget that your code must pass all the provided test cases. If not all test cases are passed then you will get score of 0 on that part of the question.
The specification and the grading rules for assignment 2 can be found in the following document. You are advised to read the grading rules carefully.
All skeleton code can be found here. You must use this years skeleton code, as it has changed from previous years.
A Zip filewith all the assignments and the source of the demo report. If that link does not work then try copying and pasting the following link into your browser: http://user.it.uu.se/~justin/Assets/Teaching/AD2/ad2_source.zip
Don’t forget that your code must pass all the provided test cases. If not all test cases are passed then you will get score of 0 on that part of the question.
The specification and the grading rules for assignment 3 can be found in the following document. You are advised to read the grading rules carefully.
All skeleton code can be found here. You must use this years skeleton code, as it has changed from previous years.
A Zip filewith all the assignments and the source of the demo report. If that link does not work then try copying and pasting the following link into your browser: http://user.it.uu.se/~justin/Assets/Teaching/AD2/ad2_source.zip
Don’t forget that your code must pass all the provided test cases. If not all test cases are passed then you will get score of 0 on that part of the question.
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. You must earn at least 3 points (of 10) on each assignment until the end of its grading session, including at least 1 point (of 5) on each problem.
| 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\\}$ |
Note that previous instances of the course and versions of this web-page had the exam marked out of 30. At some point actual exam was re-scaled to have 20 questions, with each question being worth 1.5 points. To get to the original scale some rounding up or down (usually up and in the student favour) had to be done. This new version of the table is much simpler and gives the student the same marks as before.
The overall grade is a weighted sum as follows when you have earned the assignment credits with total score $a=a_1+a_2+a_3$ (out of 30) and the exam credits with score $e$ (out of 20), following table gives the overall grade:
| Grade | Condition |
|---|---|
| 5 | $2\cdot a + 3\cdot 1.5 \cdot e \in \\{121\ldots 150\\}$ |
| 4 | $2\cdot a + 3\cdot 1.5 \cdot e \in \\{96\ldots 120\\}$ |
| 3 | $2\cdot a + 3\cdot 1.5 \cdot e \in \\{75\ldots 95\\}$ |
Note that you must pass both the assignments and the exam to get a final grade. If the resulting grade is lower than your exam grade, then the overall grade is the exam grade.
Note that the extra factor of $1.5$ for the exam grade is to calibrate a 20 point exam to a 30 point exam. Future version of this course web page will simply recalibrate the intervals, but I have left them this year (2020) in order not to confuse students.
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.
Will I get rich after passing this course? Some of the wealthiest people on the planet made their fortunes from clever algorithms and data structures, witness Sergey Brin and Larry Page, inventors of the Google web search engine (valued at many gazillions of sek). Some of the wealthiest people in Sweden studied at Uppsala University and went on to develop software needing clever algorithms and data structures, witness some of the founders of OnGame (acquired by bwin for about 4.5 billion sek), MySQL (acquired by Sun Microsystems for about 6.3 billion sek), and Skype (acquired by eBay for at least 17 billion sek). There is no limit to the need for efficient algorithms and data structures.
What are the practical applications of the discussed algorithms and data structures? Most batches of slides list a lot of practical applications. Each algorithm and data structure has an abstract name so that one does not risk thinking its scope is restricted to a particular application.
Why all this theory in the course? Why is it at the beginning of the course? Is it useful? In order to discuss in a scientific way the relative merits of alternative algorithms or data structures for a given purpose, we need an analytic way of predicting their performance, rather than experimentally and inaccurately measuring it in milliseconds or bytes. The (few!) notions seen are among the most celebrated of computing science and will transcend the rest of your studies as well as any programmer career.
Why are there not more examples and solved exercises in lectures? Like every course, AD2 has a required theoretical content (which is not decided by the head teacher) and the standard time budget (students are 33% fulltime on AD2, and no teacher is anywhere near fulltime on AD2): the balance of theory and practice in the lectures simply follows from these data and is not a sign of our bad will. On the contrary, if allocated more time (but this is impossible), then we would love to offer additional practical problem solving sessions.
Why are there not more assistants? Why are there not more examples and solved / supervised exercises by assistants in lessons? Like every course, AD2 has the standard time budget (students are 33% fulltime on AD2, and no teacher is anywhere near fulltime on AD2): the number of scheduled events simply follows from these data and is not a sign of our bad will. On the contrary, if allocated more time (but this is impossible), then we would love to offer additional practical problem solving sessions.
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. If you think a programming task is insufficiently described in terms of its pre- and post-conditions, then contact the teachers: we vet problem descriptions with utmost care and no flaws are due to purpose or sloppiness.
Why are the assignment questions neither in sync with the lecture contents, nor closer to them? See the previous question. The assignment questions are at most within the order of difficulty of the questions tackled in the lectures, and the lecture material helps in solving them, but the data structures and algorithms to be designed in assignments are new compared to the lectures, and they have been selected as examples of the infinite variety of interesting algorithmic questions that occur in real life.
Why are there not a lot of small assignments rather than the few bigger ones? Algorithm and data structure design is best practised not by drill of small questions with no relation to each other or real life, but by tackling bigger assignments, which have been selected as examples of the infinite variety of interesting algorithmic questions that occur in real life.
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 do I not get a reply to my emailed query? On working days and hours, you can normally expect a reply within a few hours, provided the question is brief, unanswered in this FAQ, answerable in a short time (and not about programming issues), and sent to all the assistants at the same time.
Are you interested in additional links to great internet resources? Yes, absolutely! Send us an email with links, and we will add the best ones to the course web-pages.