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 August 27, 2019. Note: The lecture Friday September 6 is moved to Auditorium E.
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 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.
There is a study café available every weekday. The idea of the study café is that you can sit there solving 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. The study café takes place in the Bush building.
Week  Day  Lecture  Literature  Slides & Videos (all videos)  Exercises 

35  Monday 26/8 
First TA sessions  Basic math test Blackboard registration of TA class and group 

Tuesday 27/8 
Introduction to Algorithms and Data Structures Not curriculum: More information about random permutations can be found in David J.C. MacKay, Information Theory, Inference, and Learning Algorithms, addendum on "Random Permutations". 
[Puzzle]  intro.pdf  [Puzzle] Exercises 13  
Friday 30/8 
Introduction to Algorithms and Data Structures (continued) During the lecture we solved "The longest increasing subsequence problem" [CLRS] Exercise 15.46 ☆ 
Exercises 17 Handin 1: searching 

36  Tuesday 3/9 
Evaluating a polynomial Maximum sum 
[Polynomial] [Bentley] Ch. 8 
maxsum.pdf  [Bentley] 8.7.6, 8.7.11, 8.7.12 Handin 2: [Bentley] 8.7.13 (2D maximum sum) 
Friday 6/9 
Maximum sum (continued) Note: Lecture is in Auditorium E 
[Bentley] Ch. 8  
37  Tuesday 10/9 
Analysis tools, Insertion Sort  [CLRS] Ch. 13.1  rammodel.pdf  [CLRS] Exercises 1.22, 1.23, 3.11, 3.14, Problems 11, 33 (without functions involving lg*) Quiz: Asymptotisk notation: Funktioner og Summer 
Friday 13/9 
Meeting with TA class representatives in Nygaard 395, 11:1512:00 MergeSort, HeapSort, Priority Queues 
[CLRS] Ch. 2.3, 6  heaps.pdf  [CLRS] 6.14, 6.15, 6.16, 6.32, Problems 21, (24), 61 Handin 3: [CLRS] Problem 62 (dary heap) Quiz: Heaps 

38  Tuesday 17/9 
QuickSort, Median, Randomized Selection  [CLRS] Ch. 7, 9.19.2  quicksort.pdf  [CLRS] Exercises 7.12, 7.23, 7.32, Problem 91 Quiz: Merge Sort and Quicksort 
Friday 20/9 
Introduction to Programming Exercises  See "Programming exercises" in menu  code.pdf  [CLRS] Problem 34 a.e. Handin 4: [CLRS] Problem 63 (Young tableaus) Programming Exercises I Due by Friday 4/10, 23:59. 

39  Tuesday 24/9 
Lower Bound for Comparison Based sorting, Counting Sort, Radix Sort, Bucket Sort  [CLRS] Ch. 8  sorting.pdf  [CLRS] Exercises 8.11, 8.13, 8.24, 8.34 
Friday 27/9 
Stacks and Queues Lecture by Kasper Green Larsen 
[CLRS] Ch. 10.110.2, 10.4  stacks.pdf  [CLRS] 10.12, 10.15, 10.27, (10.28), Problems 101  
40  Tuesday 1/10 
Hashing Lecture by Kasper Green Larsen 
[CLRS] Ch. 11.111.4  hashing.pdf  [CLRS] Exercises 11.22, 11.25, 11.41 
Friday 4/10 
Search trees (an unbalanced search tree implementation: Node.java, SearchTree.java) 
[CLRS] Ch. 12.112.3  searchtrees.pdf  [CLRS] Exercises 12.15, 12.24 Handin 5: Problems 122 (radix trees) Quiz: Search trees 

41  Tuesday 8/10 
Redblack trees (a redblack tree implementation: RedBlackNode.java, RedBlackTree.java) 
[CLRS] Ch. 13  redblack.pdf  [CLRS] Exercises 13.15, 13.16, 13.22, 13.32, Problems (132) 
Friday 11/10 
Augmented search trees: Dynamic rank, Interval trees  [CLRS] Ch. 14  augmented.pdf  [CLRS] Exercises 14.15, 14.17, 14.34, 14.36, Problems 141 Programming Exercises II Due by Monday 28/10 23:59. 

42  Fall break  
43  Tuesday 22/10 
Amortized analysis Not curriculum (example of using amortization in data structure design): SelfAdjusting Heaps (DOI: 10.1137/0215004) 
[CLRS] Ch. 17  amortized.pdf  [CLRS] Exercises 17.23, 17.33 Quiz: Amortized analysis 
Friday 25/10 
DivideandConquer  [CLRS] Ch. 2.3, 4.24.5, Problem 301.c  divide.pdf  [CLRS] Exercises 4.31, 4.32, Problem 41 exercise 3 (nuts and bolts) Handin 6: exercise 4 (skyline) Quiz: Recurrences 

44  Tuesday 29/10 
Deterministic selection (an inplace implementation: DeterministicSelection.java) 
[CLRS] Ch. 9.3  selection.pdf induction.pdf 
[CLRS] Exercises 9.31, 17.37 
Friday 1/11 
Dynamic programming (CutCord.java) 
[CLRS] Ch. 15.1, 15.3, 15.4, Problem 154  dp.pdf  [CLRS]: 15.12, 15.13, 15.41, 15.42, 15.44, 15.45 Handin 7: exercise 5 (merging words) Programming Exercises III Due by Monday 18/11 23:59. 

45  Tuesday 5/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  [CLRS]: 15.52, 15.53, Problem 152, (153)  
Friday 8/11 
Greedy algorithms  [CLRS] Ch. 16.116.3  greedy.pdf  [CLRS] Exercises 16.14, 16.25, 16.36  
46  Tuesday 12/11 
Graph algorithms: Graph representation, Breadth first search, Depth first search  [CLRS] Ch. 22.122.2  graphs.pdf  [CLRS] Exercises 22.11, 22.15, 22.16, 22.21, 22.26, 22.31, 22.32 
Friday 15/11 
Graph algorithms: Topological sorting, Strongly connected components  [CLRS] Ch. 22.322.5  topsort.pdf  [CLRS] Exercises 22.42, 22.57 Handin 8: [CLRS] Problem 224 (reachability) 

47  Tuesday 19/11 
Graph algorithms: Single source shortest path problem  [CLRS] Ch. 24.124.3  sssp.pdf  [CLRS] Exercises 24.11, 24.13, 24.24, 24.32, 24.34, Problems 243 
Friday 22/11 
Graph algorithms: All pairs shortest path problem  [CLRS] Ch. 25  apsp.pdf  [CLRS] Excersies 25.19, 25.110, 25.24, 25.26 Problem 251 Handin 9: exercise 6(ac) (grid graphs) Programming Exercises IV Due by Monday 9/12 23:59. 

48  Tuesday 26/11 
Graph algorithms: Minimum spanning trees  [CLRS] Ch. 23  mst.pdf  [CLRS] Exercises 23.13, 23.14, (23.111), 23.22, 23.24 
Friday 29/11 
Disjoint set unionfind Invariants 
[CLRS] Ch. 21.121.3 [HS] Ch. 2.22.3 
unionfind.pdf invariant.pdf 
[CLRS] 21.33, 21.34, 21.35 invariantex.pdf ex. 1, (2), 3 

49  Tuesday 3/12 
Invariants Not curriculum (example of using invariants in data structure design): Priority Queues with Attrition (DOI: 10.1016/00200190(89)900719) 
attritions.pdf  
Friday 6/12 
Course evaluation follow up, Discussion of exam  eksamen.pdf  
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. 

[Bentley] Programming Pearls, Second Edition, Jon Bentley. AddisonWesley, Inc., 2000. ISBN 0201657880. We will be using parts of Chapter 8 during the first weeks of the course. Chapter 8 is available for download for course participants. You do not need to buy this book. 

[Puzzle] Puslespil ved Ombytninger, Gerth Stølting Brodal. January 2006, 4 pages. Note used in the first lecture in the course. 

[Polynomial] Evaluating a Polynomial, Kasper Green Larsen. August 2017, 2 pages. Note used in the second week of the course. 

[HS] Transition Systems, Mikkel Nygaard Hansen and Erik Meineche Schmidt. DAIMIFN64, February 2014. The lectures on invariants us notation and terminology from [HS]. 

[CheatSheet] Algoritmer og Datastrukturer  Matematisk notation og regneregler. Mathematical cheat sheet for the course summarizing the essential math used throughout the course. Note: The Department of Mathematics also offers an online brushup course on high school math A at "Brushup matematik 2019  Online". 
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:
// 201900001 name 1
// 201900002 Name 2
// Contributions:
// <name 1> implemented the redblack tree insertion method
//
Avoid using special characters, like 'æ', 'ø', 'å', in your comments  since this might cause trouble with the judge. Use 'ae', 'oe', 'aa' etc. instead.
Round I Due by October 4, 23:59 
Round II Due by October 28, 23:59 
Round III Due by November 18, 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 ordinary exam is in January. The reexam is in May.
A prerequisite for attending the exam (and possibly the reexam), is the approval of 13 weekly mandatory 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 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 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. These were manually generated. I have tried to make a program to automatically generate 22 of these types of questions. Below you find find a PDF file with 10 instances of each of these questions. About 2/3 of the final exam can be expected to be a subset of these types of questions.
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. Be aware that the curriculum has changed (slightly) over the years.
Algorithms and Data Structures 1 (ADS, Fall 2017)
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 front page 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 !!!