Algorithms and Data Structures (Fall 2019)

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

	Name	Email	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

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 27, 2019. Note: The lecture Friday September 6 is moved to Auditorium E.

Exercise classes (TØ = teoretiske øvelser)

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.

Study Café

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

Course plan

Week	Day	Lecture	Literature	Slides & 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 1-3
	Friday 30/8	Introduction to 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 3/9	Evaluating a polynomial Maximum sum	[Polynomial] [Bentley] Ch. 8	maxsum.pdf ▶1 ▶2	[Bentley] 8.7.6, 8.7.11, 8.7.12 Handin 2: [Bentley] 8.7.13 (2D maximum sum)
36	Friday 6/9	Maximum sum (continued) Note: Lecture is in Auditorium E	[Bentley] Ch. 8	▶1
37	Tuesday 10/9	Analysis tools, Insertion Sort	[CLRS] Ch. 1-3.1	rammodel.pdf ▶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
37	Friday 13/9	Meeting with TA class representatives in Nygaard 395, 11:15-12:00 MergeSort, HeapSort, Priority Queues	[CLRS] Ch. 2.3, 6	heaps.pdf ▶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 17/9	QuickSort, Median, Randomized Selection	[CLRS] Ch. 7, 9.1-9.2	quicksort.pdf ▶1 ▶2	[CLRS] Exercises 7.1-2, 7.2-3, 7.3-2, Problem 9-1 Quiz: Merge Sort and Quicksort
38	Friday 20/9	Introduction to Programming Exercises	See "Programming exercises" in menu	code.pdf ▶1 ▶2	[CLRS] Problem 3-4 a.-e. Handin 4: [CLRS] Problem 6-3 (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 ▶1 ▶2	[CLRS] Exercises 8.1-1, 8.1-3, 8.2-4, 8.3-4
39	Friday 27/9	Stacks and Queues Lecture by Kasper Green Larsen	[CLRS] Ch. 10.1-10.2, 10.4	stacks.pdf ▶1 ▶2	[CLRS] 10.1-2, 10.1-5, 10.2-7, (10.2-8), Problems 10-1
40	Tuesday 1/10	Hashing Lecture by Kasper Green Larsen	[CLRS] Ch. 11.1-11.4	hashing.pdf ▶1 ▶2	[CLRS] Exercises 11.2-2, 11.2-5, 11.4-1
40	Friday 4/10	Search trees (an unbalanced search tree implementation: Node.java, SearchTree.java)	[CLRS] Ch. 12.1-12.3	searchtrees.pdf ▶1 ▶2	[CLRS] Exercises 12.1-5, 12.2-4 Handin 5: Problems 12-2 (radix trees) Quiz: Search trees
41	Tuesday 8/10	Red-black trees (a red-black tree implementation: RedBlackNode.java, RedBlackTree.java)	[CLRS] Ch. 13	redblack.pdf ▶1 ▶2	[CLRS] Exercises 13.1-5, 13.1-6, 13.2-2, 13.3-2, Problems (13-2)
41	Friday 11/10	Augmented search trees: Dynamic rank, Interval trees	[CLRS] Ch. 14	augmented.pdf ▶1 ▶2	[CLRS] Exercises 14.1-5, 14.1-7, 14.3-4, 14.3-6, Problems 14-1 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): Self-Adjusting Heaps (DOI: 10.1137/0215004)	[CLRS] Ch. 17	amortized.pdf	[CLRS] Exercises 17.2-3, 17.3-3 Quiz: Amortized analysis
43	Friday 25/10	Divide-and-Conquer	[CLRS] Ch. 2.3, 4.2-4.5, Problem 30-1.c	divide.pdf ▶1 ▶2	[CLRS] Exercises 4.3-1, 4.3-2, Problem 4-1 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 ▶1 ▶2	[CLRS] Exercises 9.3-1, 17.3-7
44	Friday 1/11	Dynamic programming (CutCord.java)	[CLRS] Ch. 15.1, 15.3, 15.4, Problem 15-4	dp.pdf ▶1 ▶2	[CLRS]: 15.1-2, 15.1-3, 15.4-1, 15.4-2, 15.4-4, 15.4-5 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	▶1 ▶2	[CLRS]: 15.5-2, 15.5-3, Problem 15-2, (15-3)
45	Friday 8/11	Greedy algorithms	[CLRS] Ch. 16.1-16.3	greedy.pdf ▶1 ▶2	[CLRS] Exercises 16.1-4, 16.2-5, 16.3-6
46	Tuesday 12/11	Graph algorithms: Graph representation, Breadth first search, Depth first search	[CLRS] Ch. 22.1-22.2	graphs.pdf ▶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
46	Friday 15/11	Graph algorithms: Topological sorting, Strongly connected components	[CLRS] Ch. 22.3-22.5	topsort.pdf ▶1 ▶2	[CLRS] Exercises 22.4-2, 22.5-7 Handin 8: [CLRS] Problem 22-4 (reachability)
47	Tuesday 19/11	Graph algorithms: Single source shortest path problem	[CLRS] Ch. 24.1-24.3	sssp.pdf ▶1 ▶2	[CLRS] Exercises 24.1-1, 24.1-3, 24.2-4, 24.3-2, 24.3-4, Problems 24-3
47	Friday 22/11	Graph algorithms: All pairs shortest path problem	[CLRS] Ch. 25	apsp.pdf ▶1 ▶2	[CLRS] Excersies 25.1-9, 25.1-10, 25.2-4, 25.2-6 Problem 25-1 Handin 9: exercise 6(a-c) (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 ▶1 ▶2	[CLRS] Exercises 23.1-3, 23.1-4, (23.1-11), 23.2-2, 23.2-4
48	Friday 29/11	Disjoint set union-find Invariants	[CLRS] Ch. 21.1-21.3 [HS] Ch. 2.2-2.3	unionfind.pdf invariant.pdf ▶1 ▶2	[CLRS] 21.3-3, 21.3-4, 21.3-5 invariant-ex.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/0020-0190(89)90071-9)		attritions.pdf ▶1 ▶2
49	Friday 6/12	Course evaluation follow up, Discussion of exam		eksamen.pdf ▶1 ▶2
January		Questions & Answers sessions		▶1 ▶2
January		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.
	[Bentley] Programming Pearls, Second Edition, Jon Bentley. Addison-Wesley, Inc., 2000. ISBN 0-201-65788-0. 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. DAIMI-FN-64, 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 brush-up course on high school math A at "Brush-up matematik 2019 - Online".

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.

Criteria	Very good	Good, some shortcomings	Some, but many shortcomings	None
	Levels of Achievement
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 Judge

Information on how to submit Java code to the judge
Exercise example maxdelsum
Status of the judge domjudge.cs.au.dk
Data structures in the Java standard library useful for coding exercises

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 red-black tree insertion method
// <name 2> implemented red-black tree deletions
// For the rest of the code <name 1> and <name 2> contributed equally

Avoid using special characters, like 'æ', 'ø', 'å', in your comments - since this might cause trouble with the judge. Use 'ae', 'oe', 'aa' etc. instead.

Exercises

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

Full points 5/7

Max (1 point)
Closest (2 points)
Ball (2 points)
Inversions (2 points)

Full points 5/7

RPN (1 point)
Queue (1 point)
Dyck (1 point)
Median (2 points)
Dodge (2 points)

Full points 3/4

Min-gap (1 point)
Order-statistic tree (1 point)
Longest increasing subsequence (1 point)
Longest palindrome subsequence (1 point)

Full points 4/6

Maze routing (1 point)
Maze multirouting (2 points)
Short shortest paths (1 point)
Eastwards travel (2 points)

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

exam-questions-v0.1.pdf (questions without answers)
exam-questions-answers-v0.1.pdf (questions with answers)
exam-questions-selftest-v0.1.pdf (PDF form - if you use Acrobat Reader you should be able to verify your answers using "compute score" on the first page)

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.

Algorithms and Data Structures 1 (ADS, Fall 2017-)

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 front page 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_2279342_1%26course_id%3D_130942_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

L^AT_EX 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^AT_EX 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 L^AT_EX. 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^AT_EX !!!