02105 Algorithms and Data Structures 1

General Info

Teachers

Philip Bille, office hours Fridays 12.30-13.00 on Zoom id: 677 3898 7472.
Inge Li Gørtz.

Teaching Assistants

Schedule

Materials

"Introduction to Algorithms", 4th edition (CLRS), Cormen, Leierson, Rivest, and Stein
"Competitive Programmer's Handbook" (CSES), Chap. 11-15, Laaksonen. Python version and Java version. See book homepage for other programming languages.
"Algorithms, 4th edition", Chap. 1.5 + 3.3, Sedgewick and Wayne. Available in Learn under materials.
"Introduction to Programming: an Interdisciplinary Approach" (IPP), Chap 4.3, Sedgewick, Wayne, and Dondero. Available in Learn under materials.

Weekplan

The weekplan below is preliminary It may be updated during the course.

Week	Topics	Slides	Weekplans	Materials
	Warmup: Preparation, Programming Prerequisites, and Puzzles.		Warmup	Survival Guide · Programming Prerequisites
	Basic Concepts I: Introduction, Algorithms, Data Structures, Peaks.	1x1 · 4x1	Introduction	CLRS chap. 1
	Basic Concepts II: Searching, Sorting.	1x1 · 4x1	Searching and Sorting	CLRS chap. 2
	Basic Concepts III: Complexity, Asymptotic Notation, Empirical Analysis.	1x1 · 4x1	Analysis of Algorithms	CLRS chap. 3
	Data Structures I: Stack, Queues, Linked Lists, Trees.	1x1 · 4x1	Introduction to Data Structures	CLRS intro to part III + chap. 10 + IPP chap. 4.3
	Graph Algorithms I: Undirected Graphs, Representation, Searching, Modelling.	1x1 · 4x1	Introduction to Graphs	CLRS intro to part VI + chap. 20.1-20.4 + appendix B.4-B.5. + CSES chap. 11-12.
	Graph Algorithms II: Directed Graph, Topological Sorting, Implicit Graphs.	1x1 · 4x1	Directed Graphs	CLRS intro to part VI + chap. 20.1-20.4 + appendix B.4-B.5 + CSES chap. 11-12.
	Data Structures II: Priority Queues, Heaps.	1x1 · 4x1	Priority Queues and Heaps	CLRS chap. 6 + appendix B.5
	Data Structures III: Union Find, Dynamic Connected Components.	1x1 · 4x1	Union Find	CLRS chap. 19 except 19.4 + Algorithms, 4ed. chap. 1.5
	Graph Algorithms III: Minimum Spanning Trees, Prims' Algorithm, Kruskal's Algorithm.	1x1 · 4x1	Minimum Spanning Trees	CLRS chap. 21 + CSES chap. 15.
	Graph Algorithms IV: Dijkstra's Algorithm, Shortest Paths in Weighted Graphs, Shortest Paths in DAGs.	1x1 · 4x1	Shortests Paths	CLRS chap. 22 except 22.1 and 22.4 + CSES chap. 13.
	Data Structures IV: Binary Search Trees, Balanced Search Trees.	1x1 · 4x1	Search Trees	CLRS chap. 12. + Algorithms, 4ed. chap. 3.3
	Data Structures V: Partial Sums, Segment Trees, Dynamic Range Minimum Queries.	1x1 · 4x1	Segment Trees	Notes - Chap. 1, 1.1, and 1.3.
	Course Wrap-Up: Questions, Exam, and Algorithms Courses and Projects.

Hand-in Exercises

The course features a number of non-mandatory/voluntary hand-in exercises posted throughout the semester and evaluated by TAs. The guidelines for preparing these exercises are as follows.

Work together on the exercises with other students if possible. This will help you to come up with better solutions. Pick a single group member that submits on DTU Learn. Do not submit multiple copies for a group.
Be precise and brief in your answer to the questions. Write you algorithms and data structure descriptions in natural language unless otherwise specified. Separate your description of algorithms, analysis, and correctness.
Use the toolbox of known algorithms and data structures from the course as "black-boxes" in your solutions if applicable. Do not repeat description and/or analysis of known algorithms and data structures.
Prepare a single pdf-file of your write-up. Write your full names and study IDs on the top of the page. Do not repeat problem statement in your write up. Like this template. The final file should consist of a single page.
Use Danish or English for your write up depending on which language you are most proficient in.

Mandatory Exercise

The course has a single individual mandatory exercise towards the end of the course. The exercise is an individual exercise (see collaboration policy below) to be handed through the Learn platform. You can hand in the exercise as many times as you want before the deadline and the last hand in is the one that is evaluated. Remember to press the "submit" button to hand in. The exercise features multiple-choice questions and short answer format questions. In the short answer format, write only the solution (typically a single number). Do not add punctuation, whitespace, other information, etc.

Collaboration Policy The exercise is individual and you are not allowed to discuss the solutions to the exercise with others, except for discussing the text of the exercise with teachers. Under no circumstances is it allowed to exchange, hand-over or in any other way communicate solutions or parts of solutions to the exercises to other people. It is not allowed to seek out solutions from previous years, solutions from similar courses, or solutions found on the internet or elsewhere.

Exam

Frequently Asked Questions

What programming and mathematics requirements do I need for the course? In general, you need an introductory course in programming and mathematics. We use basic programming extensively to implement algorithms and discrete mathematics to analyse algorithms. See the materials on this page to clarify how this applies to your current competencies in programming and mathematics.

What is the language of the course? The official language of the course is English. Hence the spoken language in lectures and the exam is in English. There are Danish exercise classes and your are free to hand in the exercises and the exam in Danish.

What is the programming language used in the course? You can use the following standard imperative programming languages: Python, Java, C, and C++.

I need to quickly refresh my programming skills. What do you recommend? We suggest the book "Introduction to Programming in Python", Sedgewick and Wayne (or the Java version "Introduction to Programming in Java"). The book is compact, concise, and focused on the core technical aspects of programming used in algorithms. The books covers essentially all relevant material for the course in chapter 1.

Which supplementary books/materials do you recommend? We suggest the following:

"Algorithm Design", Kleinberg and Tardos. Focus on algorithm design.
"Algorithms", Sedgewick and Wayne. Focus on implementation and many code examples.
"Algorithms", Jeff Erickson. Excellent freely available online book.

When and where is the exam? Please see the DTU exam schedule.