Welcome to the course on the Algorithms and Data Structures.
Course Objectives: The participants will after the course have insight into algorithms as the model for sequential computational processes, and as the basis for formal proofs of correctness and the analysis of resource consumptions of computations, and have detailed knowledge of several concrete implementations of fundamental data structures, graph algorithms, and applications of algorithm design paradigms. The participants will also have experience with implementing and evaluating the performance of algorithms for simple algorithmic problems.
Name  Office  

Lecturer  Gerth Stølting Brodal  gerth@cs.au.dk  Nygaard 321 
Note: "TA" is an abbreviation for "teaching assistant" that in Danish is called an "instruktor". A lecturer is in Danish called "forelæser" (blackboard refers to lecturers as "instructors" which can cause some confusion).
Lectures take place in the Peter Bøgh Andersen Auditorium (Nygaard/5335 016) on Tuesdays 10:1512:00 and Fridays 12:1514:00. The first lecture is Tuesday September 1, 2020.
Lectures will be streamed and recorded using Zoom, see videos folder.
Important: Due to the Covid19 situation only a limited number of students will be allowed in the auditorium.
TA sessions start Monday August 31, 2020.
During your exercise classes you will go over the solutions to a number of theoretical exercises. The exercises you should cover in a TA session are the exercises on the "Course Plan" which are associated with the lectures that have taken place since your last exercise session. You and your study group are expected to have tried to solve all the exercises before showing up. If you cannot solve all the exercises before showing up within a reasonable time frame, make sure that you at least have spend some time on each exercise. During the TA session, the students will present the solutions to each other guided with input from the TA. Between the TA sessions you can always seek help in the study café and by posting questions on the discussion board on the course webpage.
Coronavirus: If you aren’t able to come to campus due to a situation that’s directly related to the coronavirus, you can apply for an academic assistant.
There is a study café available two hours every weekday. The idea of the study café is that you can solve exercises, with a TA available for questions. Since you are expected to spend at least two hours preparing for exercise session, this would be a great opportunity. You can also use the time to work on your theoretical handins or coding exercises. It is entirely up to you whether you want to attend or not, but having a TA around is a great way of getting quick feedback. Note that you are free to show up in whatever study café session that fits you the best  not only during the session where your regular TA is assigned. You can find general information about the study café here.
Due to the COVID19 situation, the study café will this year be conducted online using Zoom. To keep an overview of the waiting line we use a Google sheet document  please sign up in this document if you need help.
Prior to the exam in January (and reexam in May) there will be a sequence of Questions and Answer sessions. You are welcome to show up for any of the sessions, not just those with your own TA  but please inform the TA in advance to be able to obey Covid19 regulations. Please try to send any questions to the TAs in advance.
Below is an estimation of the time consumption of this course.
Lectures  4 hours pr week  56 
Theoretical exercises  3 hours pr week  42 
Study Café  1 hour pr week  14 
Handins  3 hours pr week  42 
Preparation for lectures  2 hours pr week  28 
Preparation for theoretical exercises  2 hours pr week  28 
Preparation for the exam  45  
Exam  2  
Grand total  257 
Note: A 10 ECTS course corresponds to an expected total student workload of 250280 hours.
The current course was run the first time as a first semester 10 ECTS course on the Computer Science education in the Fall 2017.
This course replaces two previously offered 5 ECTS courses, Algorithms and Data Structures 1 (dADS1) and Algorithms and Data Structures 2 (dADS2), which were taught 20042017 on the second semester on the Computer Science education in the 3rd and 4th quarter, respectively.
Until 2003 the course was a 10 ECTS Spring course, Algorithms and Data Structures (dADS).
On the above pages you will be able to find the exam exercises from 1991 until today.
Videos of lectures from previous years: On the course pages for Algorithms and Data Structures in 2018 and 2019 you find links to videos of the lectures in the Course Plans. The lectures were recorded with LifeSize. Due to the instability of LifeSize, some videos are missing, some videos have bad resolutions, sometimes the camera points in the wrong directions etc.
Lecture videos: Zoom recordings.
Slides and exercises: Will be added as the course progresses. Slides from last year can be found on the 2019 course page.
Week  Day  Lecture  Literature  Slides  Exercises 

36  Monday 31/8 
First TA sessions  Basic math test Blackboard registration of TA class and handin group (if known) Subscribe to discussion board forums [B] Problems 1.11.7 

Tuesday 1/9 
Introduction to Algorithms and Data Structures 10.1511.00 IT+Hold 2+DV+DA4 11.1512.00 DA1+DA5+DA6+DA7 12.1513.00 DA2+DA3+DA8 
[B] Section 1.1  intro.pdfpptx  
Friday 4/9 
Sorting with swaps, selection sort  [B] Section 1.21.3  puzzle.pdfpptx  [B] Exercises 1.1, 1.2, 1.3, 1.4, 1.5, 1.6  
37  Tuesday 8/9 
Binary and linear search, longest increasing subsequence, Erdös & Szekeres Theorem, logarithms  [B] Section 1.41.7  binarysearch.pdfpptx  [B] Exercises 1.7, 1.8, Problems 1.9, 1.10 Handin 1: [B] Problem 1.8 (searching infinte list) 
Friday 11/9 
Integer arithmetic: Binary and decimal numbers, addition, subtraction, multiplication, division Not curriculum: [B] Section 1.11 on "Fast integer division" 
[B] Section 1.8  numbers.pdfpptx  [B] Exercises 1.9, 1.10, 1.11, 1.12  
38  Tuesday 15/9 
Induction, invariants  [B] Section 1.91.10  induction.pdfpptx  [B] Exercises 1.13, 1.14, 1.15, 1.16, 1.18 Handin 2: [B] Exercise 1.19 (squared) 
Friday 18/9 
Meeting with TA class representatives in Nygaard 395, 11:1512:00 Analysis tools, RAM model, insertion sort, Onotation 
[CLRS] Ch. 13.1  ram.pdfpptx  [CLRS] Exercises 1.22, 1.23, 3.11, 3.14, Problems 11, 33 (ignore functions involving lg*), 34(ae)  
39  Tuesday 22/9 
Mergesort, heapsort, priority queues Introduction to programming exercises 
[CLRS] Ch. 2.3, 6 
heaps.pdfpptx code.pdfpptx 
[CLRS] Exercises 6.14, 6.15, 6.16, 6.32, Problems 21, (24), 61 Handin 3: [CLRS] Problem 62 (dary heap) Programming Exercises I Due Monday 5/10, 23:59. 
Friday 25/9 
Quicksort, median, randomized selection  [CLRS] Ch. 7, 9.19.2  quicksort.pdfpptx  [CLRS] Exercises 7.12, 7.23, 7.32, Problem 91  
40  Tuesday 29/9 
Lower bound for comparison based sorting, counting sort, radix sort, bucket sort  [CLRS] Ch. 8  sorting.pdfpptx  [CLRS] Exercises 8.11, 8.13, 8.24, 8.34 
Friday 2/10 
Stacks and queues  [CLRS] Ch. 10.110.2, 10.4  stacks.pdfpptx  [CLRS] Exercises 10.12, 10.15, 10.27, Problems 101  
41  Tuesday 6/10 
Hashing  [CLRS] Ch. 11.111.4  hashing.pdfpptx  [CLRS] Exercises 11.22, 11.25, 11.41 Handin 4: [CLRS] Problem 63 (Young tableaus). Note: In c) you can analyze the running time directly without introducing a "recurrence". 
Friday 9/10 
Search trees (an unbalanced search tree implementation: Node.java, SearchTree.java) 
[CLRS] Ch. 12.112.3  searchtrees.pdfpptx  [CLRS] Exercises 12.15, 12.24  
42  Fall break  
43  Tuesday 20/10 
Balanced search trees: Redblack trees (a redblack tree implementation: RedBlackNode.java, RedBlackTree.java) 
[CLRS] Ch. 13 [B] Section 2.1 
redblack.pdfpptx  [CLRS] Exercises 13.15, 13.16, 13.22, 13.32, Problem (132) Handin 5: [CLRS] Problems 122 (radix trees) 
Friday 23/10 
Augmented search trees: Dynamic rank, interval trees, Fenwick trees  [CLRS] Ch. 14 [B] Section 2.2 
augmented.pdfpptx ncpc20.pdfpptx  [CLRS] Exercises 14.15, (14.17), 14.34, 14.36, Problem 141 Programming Exercises II Due Wednesday 4/11 23:59. 

44  Tuesday 27/10 
Disjoint set unionfind  [CLRS] Ch. 21.121.3  unionfind.pdfpptx  [CLRS] Exercises 21.33, 21.34, 21.35 
Friday 30/10 
Amortized analysis Example of using amortization in data structure design: SelfAdjusting Heaps (DOI: 10.1137/0215004) 
[CLRS] Ch. 17  amortized.pdfpptx  [CLRS] Exercises 17.23, 17.33 ([B] Ch. 3 quizzes) 

45  Tuesday 3/11 
Divideandconquer  [CLRS] Ch. 2.3, 4.24.5, Problem 301.c  divide.pdfpptx  [CLRS] Exercises 4.31, 4.32, Problem 41 [B] Problem B.1 Handin 6: [B] Problem B.2 (skyline) 
Friday 6/11 
Deterministic selection (an inplace implementation: DeterministicSelection.java) 
[CLRS] Ch. 9.3  selection.pdfpptx  [CLRS] Exercises 9.31, 17.37  
46  Tuesday 10/11 
Dynamic programming (CutCord.java) 
[CLRS] Ch. 15.1, 15.3, 15.4, Problem 154  dp.pdfpptx  [CLRS] Exercises 15.12, 15.13, 15.41, 15.42, 15.44, (15.45) Handin 7: [B] Problem B.3 (merging words) 
Friday 13/11 
Dynamic programming (continued) Not curriculum: Hirsberger's linear space LCS algorithm, CACM 1975 (DOI: 10.1145/360825.360861) 
[CLRS] Ch. 15.2, 15.5  dp.pdfpptx  [CLRS] Exercises 15.52, 15.53, Problems 152, (153) Programming Exercises III Due Wednesday 25/11 23:59. 

47  Tuesday 17/11 
Greedy algorithms  [CLRS] Ch. 16.116.3  greedy.pdfpptx  [CLRS] Exercises 16.14, 16.25, 16.36 
Friday 20/11 
Graph algorithms: Graph representation, breadth first search (BFS)  [CLRS] Ch. 22.122.2  graphs.pdfpptx  [CLRS] Exercises 22.11, 22.15, 22.16, 22.21, 22.26  
48  Tuesday 24/11 
Graph algorithms: Depth first search (DFS), topological sorting, strongly connected components  [CLRS] Ch. 22.322.5  dfs.pdfpptx  [CLRS] Exercises 22.31, 22.32, 22.42, 22.57 Handin 8: [CLRS] Problem 224 (reachability) 
Friday 27/11 
Graph algorithms: Minimum spanning trees (MST)  [CLRS] Ch. 23  mst.pdfpptx  [CLRS] Exercises 23.13, 23.111, 23.22, 23.24  
49  Tuesday 1/12 
Graph algorithms: Single source shortest path problem (SSSP)  [CLRS] Ch. 24.124.3  sssp.pdfpptx  [CLRS] Exercises 24.11, 24.13, 24.24, 24.32, 24.34, Problems 243 Handin 9: [B] Problem B.4 (grid graphs) 
Friday 4/12 
Graph algorithms: All pairs shortest path problem (APSP)  [CLRS] Ch. 25  apsp.pdfpptx  [CLRS] Excersies 25.19, 25.110, 25.24, 25.26 Problem 251 Programming Exercises IV Due Wednesday 16/12 23:59. 

50  Tuesday 8/12 
Course evaluation follow up, discussion of exam  eksamen.pdfpptx  
Friday 11/12 
No lecture  
January  Questions & answers sessions  
Exam 
[CLRS] Introduction to Algorithms (Third Edition), Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein. MIT Press, 2009. ISBN:9780262533058. The primary textbook for the course. It is the standard algorithms text book for many courses on algorithm around the world, e.g. the MIT Open Course Ware on "Introduction to Algorithms". The book will be available at Stakbogladen at the beginning of the course. 

[B] Algorithms and Data Structures  Supplementary Lecture Notes, Gerth Stølting Brodal, Fall 2020. For some weeks these notes will be the primary lecture material and contain the relevant exercises. There are two versions of the notes:
WARNING: The notes will be updated regularly as the course progresses. 
The theoretical handins are graded accepted / rehandin. Additionally feedback is given in textual form in Blackboard and a secondary evaluation according to the below rubric. The rubric score is for you to get an overall idea of the strong and weak parts in your handin. There is no fixed rubric score threshold for when a handin is graded accepted / rehandin.
Levels of Achievement  

Criteria  Very good  Good, some shortcomings  Some, but many shortcomings  None 
Description  should give a good overview of the solution Weight 25 % 
100 % The description contains a clear overview of the basic ideas of the proposed solution. Figures illustrate basic concepts. Overview guides the understanding of the details. 
66 % Description contains a good overview, but some ideas could have been more clearly presented. 
33 % Some overview is given, but the general idea is ambiguously described. 
0 % The description contains no overview of the solution or the basic ideas. 
Precision  is the solution clearly described ? Weight 25 % 
100 % The details of the proposed solution are described clearly. No ambiguity. Progress of algorithms is e.g. clearly captured by formal invariants and/or figures. Complementary pseudocode can in some cases be used to eliminate potential ambiguities in algorithm descriptions. 
66 % Good level of detail in the described solution, but with minor ambiguities or details missing. 
33 % A general outline of the solution is described. Many details are missing. The solution described is ambiguous. 
0 % No details provided. Very unclear what the proposed solution actually is. 
Correctness  is the described solution actually correct? Weight 25 % 
100 % The solution described handles all cases correctly for the problem asked. 
66 % In general a correct solution, but some minor cases not handled correctly. 
33 % The presented solution partly solves the problem asked, but many details are not handled correctly. 
0 % The presented solution is far from solving the problem asked. 
Analysis  arguments about correctness of the proposed solution Weight 25 % 
100 % Clear arguments support the correctness of the proposed solution. Formal reasoning is used to structure the argumentation. The arguments are logically sound. 
66 % Some argumentation given about the correctness using formal argumentation, but some shortcomings. Describes the general ideas in the argumentation but some details are missing. 
33 % Some hints are given about the correctness of the proposed solution, but formal argumentation is missing. 
0 % No arguments given, or very unconnected reasoning is provided. 
Since the evaluation of the handins and code will be part of the final grade in the course / prerequisite to go to the exam, plagiarism in your handins will be considered cheating. Whenever adopting code or text from elsewhere you must state this and give a reference/link to your source. It is perfectly fine to search information and adopt partial solutions from the internet – actually, this is encouraged – but always state your source in your handin. Also discussing your problems with your handins with other students is perfectly fine, but remember each group should handin their own solution. If you are in doubt if you solution will be very similar to another group because you discussed the details, please put a remark that you have discussed your solution with other groups.
For more Aarhus University information on plagiarism, please visit library.au.dk/en/students/plagiarism/.
In addition to the 9 theoretical group handins (which are handed in on Blackboard and corrected by TAs), the course contains 4 rounds of practical group programming exercises which are evaluated instantaneously by an online server. Whereas approval of the theoretical exercises is only a prerequisite to go to the exam (and do not count towards the final grade), the handins for the programming exercises count towards the final grade.
The purpose of the programming exercises is to get practical experiences with coding selected topics from the course, and to support the learning of the theoretical curriculum.
The final grade for the course is an overall assessment of the programming handins done during the course and the final multiple choice exam, where the final exam counts for most of the grade.
For the automatic grading each correct programming exercise gives 1 or 2 points (see below for the weight of the individual exercises). For each round the obtained points is the sum of the points obtained by the deadline. You can resubmit your solutions as many times you like (ideally until your solution is accepted by the server). For each round there is assigned a threshold full points. All points obtained up to full points count 1 point towards the round score. Any additional obtained point in a round only counts 1/3 point towards the round score. I.e., the round score is calculated as:
round score = min(obtained points, full points) + 1/3 * max(0, obtained points  full points)
The total programming score is the sum of the round scores.
To obtained the top grade 12 in the course it is sufficient to have a perfect MCQ and a total programming score equal to the sum of full points. A higher score can count positively towards the final grade, but as stated above the final grade for the course is an overall assessment of the programming handins done during the course and the final multiple choice exam.
Incentive for scoring: Programming and debugging can be a time sink. To avoid students spending exorbitant amounts of time trying to get the maximum score in all programming exercises, the "full points" threshold has been introduced and the limited influence on the score of the last points possible in each round.
Your group's password for the judge will be provided by your TA.
In the uploaded code you must include a comment stating the names of the authors and who contributed to the different parts of the code. If everybody stated equally to all parts of the code, then state this.
// Handin done by: // <id 1> <name 1> // <id 2> <name 2> // <id 3> <name 3> // Contributions: // <name 1> implemented the redblack tree insertion method // <name 2> implemented redblack tree deletions // <name 3> implemented redblack tree left and right rotations
Avoid using special characters, like 'æ', 'ø', 'å', 'é', in your comments  since this might cause trouble with the judge. Use 'ae', 'oe', 'aa', 'e' etc. instead.
Round I Due by October 5, 23:59 
Round II Due by November 4, 23:59 
Round III Due by November 25, 23:59 
Round IV 
Full points 5/7

Full points 5/7 
Full points 3/4

Full points 4/6

The final exam is a two hour multiplechoice exam. No aids are allowed at the exam (also not the text book of the course).
The exam will be performed as an online exam, with all aids allowed, including internet. It is not allowed to communicate with others during the exam.
For the exam you will have to download a pdf file from https://eksamen.au.dk/, fill out the pdf with your answers, and upload the pdf again. The pdf contains a multiplechoice exam that has must filled out using Adobe Acrobat (that can be downloaded from https://get.adobe.com/reader/). Do not use any other pdf viewer, since they might not be compatible with the subsequent evaluation process! A pdf file for testing the exam format is available as ads20examdraft.pdf (solutions).
The ordinary exam is in January. The reexam is in May. The date and time of the exam is announced at the study portal.
A prerequisite for attending the exam (and possibly the reexam), is theapproval of 9 mandatory assignments and submission of 4 programming assignments. The handins can be done in groups of up to three persons.
The final grade is on the 7 step scale. The grade reflects an overall assessment of the mandatory programming handins done during the course and the written examination, where the written examination counts for most of the grade.
Below are the grade statistics from exams the previous years:
Grade  3  00  02  4  7  10  12 
Algorithms and Data Structures (January 2020, 10 ECTS)  1%  4%  1%  6%  26%  26%  35% 
Algorithms and Data Structures (January 2019, 10 ECTS)  1%  4%  10%  16%  30%  27%  12% 
Algorithms and Data Structures (January 2018, 10 ECTS)  0%  6%  10%  24%  28%  19%  13% 
Algorithms and Data Structures 1 (20082017, 5 ECTS) 
3% 
13%  13%  18%  24%  19%  9% 
Algorithms and Data Structures 2 (20082017, 5 ECTS )  2%  20%  14%  20%  26%  11%  6% 
The course curriculum is the material covered during the lectures and listed in the course plan.
When you look at the previous exams, you will realize many questions recur year after year, but typically with different example inputs. Below you find find a PDF file with 10 instances of each of these questions. About 3/4 of the final exam can be expected to be a subset of these types of questions.
(earlier version examquestionsv0.2.pdf, examquestionsv0.2answers.pdf, examquestionsv0.2selftest.pdf)
Below are the exam questions from the exams in the first year introduction to algorithms and data structure courses since 1991. A suffix of "j", "a" or "m" indicates a reexam in January, May or August, respectively. "/s" is the solution to the exams. "/%" is the answer statistics from the exam. "/i" is an interactive PDF for Adobe Acrobat. Be aware that the curriculum has changed (slightly) over the years.
Algorithms and Data Structures (ADS, Fall 2017)
21m/s/i 20/s/i 20m/s 19/s/% 19m/s 18/s 18m/s 17
Algorithms and Data Structures 1 (dADS1, Spring 20042017)
17a/s 17/s 16a/s 16/s 15a/s 15/s 14a/s 14/s 13a/s 13/s 12a/s 12/s 11a/s 11/s 10a/s 10/s 09a/s 09/s 08a/s 08/s 07a/s 07/s 06a/s 06/s 05a/s 05/s 04a/s 04/s
Algorithms and Data Structures 2 (dADS2, Spring 20042017)
17a/s 17/s 16a/s 16/s 15a/s 15/s 14a/s 14/s 13a/s 13/s 12a/s 12/s 11a/s 11/s 10a 10/s 09a 09/s 08a/s 08/s 07a 07/s 06a 06/s 05a 05/s 04a 04/s
Algorithms and Data Structures (dADS, Spring 2003)
04a 03a 03 02a 02 01a 01 00a 00 99a 99 98a 98 97a 97 96a 96 96j 95a 95 95j 94a 94 94j 93 93j 92 92j 91
The below is a link you can use as a bookmark for you browser to get directly to the coure plan of the course page after providing WAYF login cridentials:
Aarhus University provides free licenses to students for various software, incl. Windows 10 Education, Microsoft Office 365, and MatLab. See http://studerende.au.dk/en/itsupport/software/.
L^{A}T_{E}X is the primary typesetting language used for computer science literature, e.g. research papers and course books, including [CLRS]. There are several software packages available that you can download for translating L^{A}T_{E}X source code to e.g. PDF locally on your computer. Read more at www.latexproject.org. There is also online collaboration services like www.overleaf.com that makes it easier getting started with L^{A}T_{E}X. See e.g. the Overlead Documentation for a tutorial on how to get started.
Handins in the course are by no means required to be done in L^{A}T_{E}X !!!