Foundations of Algorithms and Data Structures (Fall 2018)
Welcome
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
Lectures take place in the Peter Bøgh Andersen Auditorium (Nygaard/5335 016) on Tuesdays 10:15-12:00 and Fridays 12:15-14:00. The first lecture is Tuesday August 28, 2018. Note: The lecture Friday September 7 is moved to Auditorium E.
Exercise classes (TØ)
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.
Course plan
| 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.pdf|pptx ▶1 ▶2 |
Exercises 1-3 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.4-6 ☆ |
▶1 ▶2 | Exercises 1-7 Handin 1: searching |
||
| 36 | Tuesday 4/9 | Evaluating a polynomial Maximum sum |
polynomial.pdf [Bentley] Ch. 8 |
maxsum.pdf|pptx ▶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. 1-3.1 | rammodel.pdf|pptx ▶1 ▶2 |
[CLRS] Exercises 1.2-2, 1.2-3, 3.1-1, 3.1-4, Problems 1-1, 3-3 (without functions involving lg*) Quiz: Asymptotisk notation: Funktioner og Summer |
| Friday 14/9 | MergeSort, HeapSort, Priority Queues | [CLRS] Ch. 2.3, 6 | heaps.pdf|pptx ▶1 ▶2 |
[CLRS] 6.1-4, 6.1-5, 6.1-6, 6.3-2, Problems 2-1, (2-4), 6-1 Handin 3: [CLRS] Problem 6-2 (d-ary heap) Quiz: Heaps |
|
| 38 | Tuesday 18/9 | QuickSort, Median, Randomized Selection | [CLRS] Ch. 7, 9.1-9.2 | quicksort.pdf|pptx ▶1 ▶2 |
[CLRS] Exercises 7.1-2, 7.2-3, 7.3-2, Problems 9.1 Quiz: Merge Sort and Quicksort |
| Friday 21/9 | Introduction to Programming Exercises | csaudk-submitj maxdelsum |
code.pdf|pptx ▶ |
[CLRS] Problem 3-4 a.-e. Handin 4: [CLRS] Problem 6-3 (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.pdf|pptx ▶1 ▶2 |
[CLRS] Exercises 8.1-1, 8.1-3, 8.2-4, 8.3-4 |
| Friday 28/9 | Stacks and Queues | [CLRS] Ch. 10.1-10.2, 10.4 | stacks.pdf|pptx ▶1 ▶2 |
[CLRS] 10.1-2, 10.1-5, 10.2-7, (10.2-8), Problems 10.1 | |
| 40 | Tuesday 2/10 | Hashing | [CLRS] Ch. 11.1-11.4 | hashing.pdf|pptx ▶1 ▶2 |
[CLRS] Exercises 11.2-2, 11.2-5, 11.4-1 |
| Friday 5/10 | Search trees | [CLRS] Ch. 12.1-12.3 | searchtrees.pdf|pptx ▶1 ▶2 |
[CLRS] Exercises 12.1-5, 12.2-4 |
|
| 41 | Tuesday 9/10 | Red-black trees | [CLRS] Ch. 13 | redblack.pdf|pptx ▶1 ▶2 |
[CLRS] Exercises 13.1-5, 13.1-6, 13.2-2, 13.3-2, Problems (13-2) |
| Friday 12/10 |
Augmented search trees: Dynamic rank, Interval trees |
[CLRS] Ch. 14 Data structures in Java standard library (for coding exercises) |
augmented.pdf|pptx ▶ |
[CLRS] Exercises 14.1-5, 14.1-7, 14.3-4, 14.3-6, Problems 14-1 For full grade: 5/7 points. |
|
| 42 | Fall break | ||||
| 43 | Tuesday 23/10 | Amortized analysis | [CLRS] Ch. 17 | amortized.pdf|pptx ▶ |
[CLRS] Exercises 17.2-3, 17.3-3 Quiz: Amortized analysis |
| Friday 26/10 | Divide-and-Conquer | [CLRS] Ch. 2.3, 4.2-4.5, Problem 30-1.c | divide.pdf|pptx ▶1 ▶2 |
[CLRS] Exercises 4.3-1, 4.3-2, Problem 4.1 |
|
| 44 | Tuesday 30/10 | Deterministic selection | [CLRS] Ch. 9.3 | selection.pdf|pptx induction.pdf|pptx ▶1 ▶2 |
[CLRS] Exercises 9.3-1, 17.3-7 |
| Friday 2/11 | Dynamic programming | [CLRS] Ch. 15.1, 15.3, 15.4, Problem 15-4 | dp.pdf|pptx ▶1 ▶2 |
[CLRS]: 15.1-2, 15.1-3, 15.4-1, 15.4-2, 15.4-4, 15.4-5
For full grade: 3/4 points. |
|
| 45 | Tuesday 6/11 |
Dynamic programming |
[CLRS] Ch. 15.2, 15.5 | ▶1 ▶2 |
[CLRS]: 15.5-2, 15.5-3, Problem 15-2, (15-3) |
| Friday 9/11 | Greedy algorithms | [CLRS] Ch. 16.1-16.3 | greedy.pdf|pptx ▶1 ▶2 |
[CLRS] Exercises 16.1-4, 16.2-5, 16.3-6 | |
| 46 | Tuesday 13/11 | Graph algorithms: Graph representation, Breadth first search, Depth first search | [CLRS] Ch. 22.1-22.2 | graphs.pdf|pptx ▶1 ▶2 |
[CLRS] Exercises 22.1-1, 22.1-5, 22.1-6, 22.2-1, 22.2-6, 22.3-1, 22.3-2 |
| Friday 16/11 | Graph algorithms: Topological sorting, Strongly connected components | [CLRS] Ch. 22.3-22.5 | topsort.pdf|pptx ▶1 ▶2 |
[CLRS] Exercises 22.4-2, 22.5-7 |
|
| 47 | Tuesday 20/11 | Graph algorithms: Single source shortest path problem | [CLRS] Ch. 24.1-24.3 | sssp.pdf|pptx ▶1 ▶2 |
[CLRS] Exercises 24.1-1, 24.1-3, 24.2-4, 24.3-2, 24.3-4, Problems 24-3 |
| Friday 23/11 | Graph algorithms: All pairs shortest path problem | [CLRS] Ch. 25 | apsp.pdf|pptx ▶1 ▶2 |
[CLRS] Excersies 25.1-6, 25.1-9, 25.1-10, 25.2-4, 25.2-6 Problem 25-1
For full grade: 4/6 points. |
|
| 48 | Tuesday 2711 | Graph algorithms: Minimum spanning trees | [CLRS] Ch. 23 |
[CLRS] Exercises 23.1-3, 23.1-4, (23.1-11,) 23.2-2, 23.2-4 |
|
| Friday 30/11 | Disjoint set union-find Invariants |
[CLRS] Ch. 21.1-21.3 | unionfind.pdf|pptx invariant.pdf|pptx ▶1 ▶2 |
[CLRS] 21.3-3, 21.3-4, 21.3-5 invariant-ex.pdf |
|
| 49 | Tuesday 4/12 | Invariants Not curriculum (example of using invariants in data structure design): Priority Queues with Attrition (DOI: 10.1016/0020-0190(89)90071-9) |
|||
| Friday 7/12 | Course evaluation follow up, Discussion of exam | evaluation.pdf|pptx | |||
| January | Questions & Answers sessions | ||||
| Thursday 24/1 | Exam | ||||
Expected work load
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 250-280 hours.
Basic literature
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. Addison-Wesley, Inc., 2000. ISBN 0-201-65788-0. You do not need to buy this book, a pdf of the relevant parts is made available out.
Historic information
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 2004-2017 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.
Exam
The final exam is a two hour written exam mostly consisting of multiple-choice 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.
Grading
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 (2008-2017, 5 ECTS) | 3% | 13% | 13% | 18% | 24% | 19% | 9% |
| Algorithms and Data Structures 2 (2008-2017, 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% |
Curriculum
The course curriculum is the material cover during the lectures and listed in the course plan.
Previous exams
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 2004-2017)
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 2004-2017)
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