Algorithms and Data Structures (Fall 2020)

Welcome

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.

Staff

NameEmailOffice
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

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 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.

Exercise classes (TØ = teoretiske øvelser)

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.

Study café

There is a study café available two hours every week-day. 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.

Q & A sessions

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.

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 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 250-280 hours.

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.

Course plan

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.1-1.7
Tuesday
1/9		 Introduction to Algorithms and Data Structures
10.15-11.00 IT+Hold 2+DV+DA4
11.15-12.00 DA1+DA5+DA6+DA7
12.15-13.00 DA2+DA3+DA8 		[B] Section 1.1 intro.pdf|pptx
Friday
4/9		 Sorting with swaps, selection sort [B] Section 1.2-1.3 puzzle.pdf|pptx [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.4-1.7 binarysearch.pdf|pptx [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.pdf|pptx [B] Exercises 1.9, 1.10, 1.11, 1.12
38 Tuesday
15/9		 Induction, invariants [B] Section 1.9-1.10 induction.pdf|pptx [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:15-12:00
Analysis tools, RAM model, insertion sort, O-notation		 [CLRS] Ch. 1-3.1 ram.pdf|pptx [CLRS] Exercises 1.2-2, 1.2-3, 3.1-1, 3.1-4, Problems 1-1, 3-3 (ignore functions involving lg*), 3-4(a-e)
39 Tuesday
22/9		 Mergesort, heapsort, priority queues
Introduction to programming exercises 		[CLRS] Ch. 2.3, 6 heaps.pdf|pptx
code.pdf|pptx 		[CLRS] Exercises 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)
Programming Exercises I
Due Monday 5/10, 23:59.
Friday
25/9		 Quicksort, median, randomized selection [CLRS] Ch. 7, 9.1-9.2 quicksort.pdf|pptx [CLRS] Exercises 7.1-2, 7.2-3, 7.3-2, Problem 9-1
40 Tuesday
29/9		 Lower bound for comparison based sorting, counting sort, radix sort, bucket sort [CLRS] Ch. 8 sorting.pdf|pptx [CLRS] Exercises 8.1-1, 8.1-3, 8.2-4, 8.3-4
Friday
2/10		 Stacks and queues [CLRS] Ch. 10.1-10.2, 10.4 stacks.pdf|pptx [CLRS] Exercises 10.1-2, 10.1-5, 10.2-7, Problems 10-1
41 Tuesday
6/10		 Hashing [CLRS] Ch. 11.1-11.4 hashing.pdf|pptx [CLRS] Exercises 11.2-2, 11.2-5, 11.4-1
Handin 4: [CLRS] Problem 6-3 (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.1-12.3 searchtrees.pdf|pptx [CLRS] Exercises 12.1-5, 12.2-4
42 Fall break
43 Tuesday
20/10		 Balanced search trees: Red-black trees
(a red-black tree implementation: RedBlackNode.java, RedBlackTree.java) 		[CLRS] Ch. 13
[B] Section 2.1 		redblack.pdf|pptx [CLRS] Exercises 13.1-5, 13.1-6, 13.2-2, 13.3-2, Problem (13-2)
Handin 5: [CLRS] Problems 12-2 (radix trees)
Friday
23/10		 Augmented search trees: Dynamic rank, interval trees, Fenwick trees [CLRS] Ch. 14
[B] Section 2.2		 augmented.pdf|pptx ncpc20.pdf|pptx [CLRS] Exercises 14.1-5, (14.1-7), 14.3-4, 14.3-6, Problem 14-1
Programming Exercises II
Due Wednesday 4/11 23:59.
44 Tuesday
27/10		 Disjoint set union-find [CLRS] Ch. 21.1-21.3 unionfind.pdf|pptx [CLRS] Exercises 21.3-3, 21.3-4, 21.3-5
Friday
30/10		 Amortized analysis
Example of using amortization in data structure design: Self-Adjusting Heaps (DOI: 10.1137/0215004)		 [CLRS] Ch. 17 amortized.pdf|pptx [CLRS] Exercises 17.2-3, 17.3-3
([B] Ch. 3 quizzes)
45 Tuesday
3/11		 Divide-and-conquer [CLRS] Ch. 2.3, 4.2-4.5, Problem 30-1.c divide.pdf|pptx [CLRS] Exercises 4.3-1, 4.3-2, Problem 4-1
[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.pdf|pptx [CLRS] Exercises 9.3-1, 17.3-7
46 Tuesday
10/11		 Dynamic programming
(CutCord.java)		 [CLRS] Ch. 15.1, 15.3, 15.4, Problem 15-4 dp.pdf|pptx [CLRS] Exercises 15.1-2, 15.1-3, 15.4-1, 15.4-2, 15.4-4, (15.4-5)
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.pdf|pptx [CLRS] Exercises 15.5-2, 15.5-3, Problems 15-2, (15-3)
Programming Exercises III
Due Wednesday 25/11 23:59.
47 Tuesday
17/11		 Greedy algorithms [CLRS] Ch. 16.1-16.3 greedy.pdf|pptx [CLRS] Exercises 16.1-4, 16.2-5, 16.3-6
Friday
20/11		 Graph algorithms: Graph representation, breadth first search (BFS) [CLRS] Ch. 22.1-22.2 graphs.pdf|pptx [CLRS] Exercises 22.1-1, 22.1-5, 22.1-6, 22.2-1, 22.2-6
48 Tuesday
24/11		 Graph algorithms: Depth first search (DFS), topological sorting, strongly connected components [CLRS] Ch. 22.3-22.5 dfs.pdf|pptx [CLRS] Exercises 22.3-1, 22.3-2, 22.4-2, 22.5-7
Handin 8: [CLRS] Problem 22-4 (reachability)
Friday
27/11		 Graph algorithms: Minimum spanning trees (MST) [CLRS] Ch. 23 mst.pdf|pptx [CLRS] Exercises 23.1-3, 23.1-11, 23.2-2, 23.2-4
49 Tuesday
1/12		 Graph algorithms: Single source shortest path problem (SSSP) [CLRS] Ch. 24.1-24.3 sssp.pdf|pptx [CLRS] Exercises 24.1-1, 24.1-3, 24.2-4, 24.3-2, 24.3-4, Problems 24-3
Handin 9: [B] Problem B.4 (grid graphs)
Friday
4/12		 Graph algorithms: All pairs shortest path problem (APSP) [CLRS] Ch. 25 apsp.pdf|pptx [CLRS] Excersies 25.1-9, 25.1-10, 25.2-4, 25.2-6 Problem 25-1
Programming Exercises IV
Due Wednesday 16/12 23:59.
50 Tuesday
8/12		 Course evaluation follow up, discussion of exam eksamen.pdf|pptx
Friday
11/12		 No lecture
January Questions & answers sessions
Exam

Course literature


[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.
Supplementary Lecture Notes

[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.

Handins

Rubric for feedback

The theoretical handins are graded accepted / re-handin. 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 / re-handin.

Levels of Achievement
CriteriaVery goodGood, some shortcomingsSome, but many shortcomingsNone
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 pseudo-code 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.

Note on plagiarism

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/.

Programming exercises

Programming exercises vs Theoretical handins

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.

Grading

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.

The code Judge

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 red-black tree insertion method
// <name 2> implemented red-black tree deletions
// <name 3> implemented red-black 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.

Exercises

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
Due by December 16, 23:59

Full points 5/7

Full points 5/7

 Full points 3/4

Full points 4/6

Exam

The final exam is a two hour multiple-choice 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 multiple-choice 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 ads20exam-draft.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.

Grading

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 (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%

Curriculum

The course curriculum is the material covered during the lectures and listed in the course plan.

Exam - standard questions

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 exam-questions-v0.2.pdf, exam-questions-v0.2answers.pdf, exam-questions-v0.2selftest.pdf)

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. "/%" 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 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

The nerdy corner

Bookmark link to Blackboard

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:

https://blackboard.au.dk/webapps/bb-auth-provider-shibboleth-BBLEARN/execute/shibbolethLogin?returnUrl=https%3A%2F%2Fblackboard.au.dk%2Fwebapps%2Fblackboard%2Fcontent%2FlistContentEditable.jsp%3Fcontent_id%3D_2727645_1%26course_id%3D_136331_1&authProviderId=_102_1

Free software licenses for Aarhus University students

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/it-support/software/.

LaTeX and Overleaf

LATEX 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 LATEX source code to e.g. PDF locally on your computer. Read more at www.latex-project.org. There is also online collaboration services like www.overleaf.com that makes it easier getting started with LATEX. 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 LATEX !!!