Welcome to the course on the Foundations of 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.
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 28, 2018. Note: The lecture Friday September 7 is moved to Auditorium E.
TA sessions start Monday August 27, 2018.
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 forum on the course webpage.
Week  Day  Lecture  Literature  Slides & Videos (▶) 
Exercises 
35  Monday 27/8  First TA sessions  Basic math test  
Tuesday 28/8  Introduction to Foundations of Algorithms and Data Structures Lecture starts 10:30 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.pdf  intro.pdfpptx ▶1 ▶2 
Exercises 13 in puzzle.pdf  
Friday 31/8  Introduction to Foundations of Algorithms and Data Structures (continued) During the lecture we solved "The longest increasing subsequence problem" [CLRS] Exercise 15.46 ☆ 
▶1 ▶2  Exercises 17 Handin 1: searching 

36  Tuesday 4/9  Evaluating a polynomial Maximum sum 
polynomial.pdf [Bentley] Ch. 8 
maxsum.pdfpptx ▶1 ▶2 
[Bentley] 8.7.6, 8.7.11, 8.7.12 Handin 2: [Bentley] 8.7.13 (2D maximum sum) 
Friday 7/9  Maximum sum  [Bentley] Ch. 8  ▶1 ▶2  
37  Tuesday 11/9  Analysis tools, Insertion Sort Lecture moved to Auditorium E 
[CLRS] Ch. 13.1  rammodel.pdfpptx ▶1 ▶2 
[CLRS] Exercises 1.22, 1.23, 3.11, 3.14, Problems 11, 33 (without functions involving lg*) Quiz: Asymptotisk notation: Funktioner og Summer 
Friday 14/9  MergeSort, HeapSort, Priority Queues  [CLRS] Ch. 2.3, 6  heaps.pdfpptx ▶1 ▶2 
[CLRS] 6.14, 6.15, 6.16, 6.32, Problems 21, (24), 61 Handin 3: [CLRS] Problem 62 (dary heap) Quiz: Heaps 

38  Tuesday 18/9  QuickSort, Median, Randomized Selection  [CLRS] Ch. 7, 9.19.2  quicksort.pdfpptx ▶1 ▶2 
[CLRS] Exercises 7.12, 7.23, 7.32, Problems 9.1 Quiz: Merge Sort and Quicksort 
Friday 21/9  Introduction to Programming Exercises  csaudksubmitj maxdelsum 
code.pdfpptx ▶ 
[CLRS] Problem 34 a.e. Handin 4: [CLRS] Problem 63 (Young tableaus) Programming Exercises I Due by Friday 5/10, 23:59.
Status: domjudge.cs.au.dk 

39  Tuesday 25/9  Lower Bound for Comparison Based sorting, Counting Sort, Radix Sort, Bucket Sort  [CLRS] Ch. 8  sorting.pdfpptx ▶1 ▶2 
[CLRS] Exercises 8.11, 8.13, 8.24, 8.34 
Friday 28/9  Stacks and Queues  [CLRS] Ch. 10.110.2, 10.4  stacks.pdfpptx ▶1 ▶2 
[CLRS] 10.12, 10.15, 10.27, (10.28), Problems 10.1  
40  Tuesday 2/10  Hashing  [CLRS] Ch. 11.111.4  hashing.pdfpptx ▶1 ▶2 
[CLRS] Exercises 11.22, 11.25, 11.41 
Friday 5/10  Search trees  [CLRS] Ch. 12.112.3  searchtrees.pdfpptx ▶1 ▶2 
[CLRS] Exercises 12.15, 12.24 

41  Tuesday 9/10  Redblack trees  [CLRS] Ch. 13  redblack.pdfpptx ▶1 ▶2 
[CLRS] Exercises 13.15, 13.16, 13.22, 13.32, Problems (132) 
Friday 12/10 
Augmented search trees: Dynamic rank, Interval trees 
[CLRS] Ch. 14 Data structures in Java standard library (for coding exercises) 
augmented.pdfpptx ▶ 
[CLRS] Exercises 14.15, 14.17, 14.34, 14.36, Problems 141 For full grade: 5/7 points. 

42  Fall break  
43  Tuesday 23/10  Amortized analysis  [CLRS] Ch. 17  amortized.pdfpptx ▶ 
[CLRS] Exercises 17.23, 17.33 Quiz: Amortized analysis 
Friday 26/10  DivideandConquer  [CLRS] Ch. 2.3, 4.24.5, Problem 301.c  divide.pdfpptx ▶1 ▶2 
[CLRS] Exercises 4.31, 4.32, Problem 4.1 

44  Tuesday 30/10  Deterministic selection  [CLRS] Ch. 9.3  selection.pdfpptx induction.pdfpptx ▶1 ▶2 
[CLRS] Exercises 9.31, 17.37 
Friday 2/11  Dynamic programming  [CLRS] Ch. 15.1, 15.3, 15.4, Problem 154  dp.pdfpptx ▶1 ▶2 
[CLRS]: 15.12, 15.13, 15.41, 15.42, 15.44, 15.45
For full grade: 3/4 points. 

45  Tuesday 6/11 
Dynamic programming 
[CLRS] Ch. 15.2, 15.5  ▶1 ▶2 
[CLRS]: 15.52, 15.53, Problem 152, (153) 
Friday 9/11  Greedy algorithms  [CLRS] Ch. 16.116.3  greedy.pdfpptx ▶1 ▶2 
[CLRS] Exercises 16.14, 16.25, 16.36  
46  Tuesday 13/11  Graph algorithms: Graph representation, Breadth first search, Depth first search  [CLRS] Ch. 22.122.2  graphs.pdfpptx ▶1 ▶2 
[CLRS] Exercises 22.11, 22.15, 22.16, 22.21, 22.26, 22.31, 22.32 
Friday 16/11  Graph algorithms: Topological sorting, Strongly connected components  [CLRS] Ch. 22.322.5  topsort.pdfpptx ▶1 ▶2 
[CLRS] Exercises 22.42, 22.57 

47  Tuesday 20/11  Graph algorithms: Single source shortest path problem  [CLRS] Ch. 24.124.3  sssp.pdfpptx ▶1 ▶2 
[CLRS] Exercises 24.11, 24.13, 24.24, 24.32, 24.34, Problems 243 
Friday 23/11  Graph algorithms: All pairs shortest path problem  [CLRS] Ch. 25  apsp.pdfpptx ▶1 ▶2 
[CLRS] Excersies 25.16, 25.19, 25.110, 25.24, 25.26 Problem 251
For full grade: 4/6 points. 

48  Tuesday 2711  Graph algorithms: Minimum spanning trees  [CLRS] Ch. 23 
[CLRS] Exercises 23.13, 23.14, (23.111,) 23.22, 23.24 

Friday 30/11  Disjoint set unionfind Invariants 
[CLRS] Ch. 21.121.3  unionfind.pdfpptx invariant.pdfpptx ▶1 ▶2 
[CLRS] 21.33, 21.34, 21.35 invariantex.pdf 

49  Tuesday 4/12  Invariants Not curriculum (example of using invariants in data structure design): Priority Queues with Attrition (DOI: 10.1016/00200190(89)900719) 

Friday 7/12  Course evaluation follow up, Discussion of exam  evaluation.pdfpptx  
January  Questions & Answers sessions  
Thursday 24/1  Exam 
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 hours 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 work load of 250280 hours.
In the course, we will be using the [CLRS] book:
Introduction to Algorithms (Third Edition), Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein. MIT Press, 2009. ISBN: 9780262533058. The book will be available at Stakbogladen at the beginning of the course.
We will also be using parts of Chapter 8 from [Bentley]:
Programming Pearls, Second Edition, Jon Bentley. AddisonWesley, Inc., 2000. ISBN 0201657880. You do not need to buy this book, a pdf of the relevant parts is made available out.
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.
The final exam is a two hour written exam mostly consisting of multiplechoice questions. 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 statistics  3  00  02  4  7  10  12 
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% 
Foundations of Algorithms and Data Structures (January 2018, 10 ECTS)  0%  6%  10%  24%  28%  19%  13% 
Foundations of Algorithms and Data Structures (January 2019, 10 ECTS)  1%  4%  10%  16%  30%  27%  12% 
The course curriculum is the material cover during the lectures and listed in the course plan.
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.
Foundations of Algorithms and Data Structures 1 (FADS, 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