Teachers
Exercise classes Thursdays 8.00-10.30.
| Class | Room | Study line | Type | Teaching Assistant |
|---|---|---|---|---|
| 1 | 308/exercise area 1. floor south | BEng | Group Work/Danish | Marcus Pagh |
| 2 | 308/exercise area 1. floor north | BEng | Group Work/Danish | Katrine Thoft |
| 3 | 324/020 | BEng/BSc | Presentation and Discussion/English | Simon Søkilde |
| 4 | 324/030 | BSc | Group Work/English | Tord Joakim Stordalen |
| 5 | 324/040 (+ 303/aud. 43 at 10.00-10.30) | BSc | Group Work/Danish | Mads Okholm Bjørn |
| 6 | 324/050 | BSc | Group Work/Danish | Benjamin Lam |
| 7 | 324/060 | BSc | Group Work/Danish | Johan Bloch Madsen |
The areas in the common area in 324 (F003, F004, F005, F008) are also reserved for the course. See overview map of all exercise rooms in 308 and 324. Additionally, Nina Nielsen and Rikke Langhede will be "floating TAs" that move around and help where needed.
Lectures Thursdays 10.45-12.00 in 303/42 (live) 303/43 (streamed).
Materials "Introduction to Algorithms", 3rd edition (CLRS), Cormen, Leierson, Rivest, and Stein + notes. We recommend getting a physical version of the book to bring to the exam. We encourage using supplementary books and other sources for algorithms. Se suggestions here.
CodeJudge We use CodeJudge for testing code. Access CodeJudge here.
Piazza We use Piazza for online discussions. Access Piazza here.
The weekplan is preliminary and may be updated during the course. The exercises class in week x covers the exercises on weekplan x-1.
| Week | Topics | Slides | Weekplan | Material | Algorithm Demos | Programming Demos |
|---|---|---|---|---|---|---|
| 0 | Warmup: Preparation, Programming Prerequisites, and Puzzles. | Warmup | Survival Guide · Programming Prerequisites | Factorial function | ||
| 1 | Basic Concepts I: Introduction, Algorithms, Data Structures, Peaks. | 1x1 · 4x1 | Introduction | CLRS chap. 1 | Recursive Peak Algorithm | Peaks |
| 2 | Basic Concepts II: Searching, Sorting. | 1x1 · 4x1 | Searching and Sorting | CLRS chap. 2 | Binary Search · Insertion Sort · Merge · Mergesort | Binary Search |
| 3 | Basic Concepts III: Complexity, Asymptotic Notation, Empirical Analysis. | 1x1 · 4x1 | Analysis of Algorithms | CLRS chap. 3 | ||
| 4 | Data Structures I: Stack, Queues, Linked Lists, Trees. | 1x1 · 4x1 | Introduction to Data Structures | CLRS intro to part III + chap. 10 | Stack with Array · Queue with Array · Dynamic Array 1 · Dynamic Array 2 | Linked List |
| 5 | Data Structures II: Priority Queues, Heaps. | 1x1 · 4x1 | Priority Queues and Heaps | CLRS chap. 6 + appendix B.5 | Bubble up and down | Heap |
| 6 | Graph Algorithms I: Undirected Graphs, Representation, Searching, Modelling. | 1x1 · 4x1 | Introduction to Graphs | CLRS intro to part VI + chap. 22.1-22.4 + appendix B.4-B.5. | DFS · BFS | DFS |
| 7 | Graph Algorithms II: Directed Graph, Topological Sorting, Implicit Graphs. | 1x1 · 4x1 | Directed Graphs | CLRS intro to part VI + chap. 22.1-22.4 + appendix B.4-B.5. | Topological Sort | Topological Sort |
| 8 | Data Structures III: Union-Find, Dynamic Connected Components. | 1x1 · 4x1 | Union-Find | CLRS chap. 21 except 21.4 + Algorithms, 4ed. chap. 1.5 | Quick Union · Weighted Quick Union | |
| 9 | Graph Algorithms III: Minimum Spanning Trees, Prims' Algorithm, Kruskal's Algorithm. | 1x1 · 4x1 | Minimum Spanning Trees | CLRS chap. 23. | Prims' Algorithm · Kruskal's Algorithm | |
| 10 | Graph Algorithms IV: Dijkstra's Algorithm, Shortest Paths in Weighted Graphs, Shortest Paths in DAGs. | 1x1 · 4x1 | Shortests Paths | CLRS chap. 24 except 24.1 and 24.4. | Dijkstras' Algorithm | |
| 11 | Data Structures IV: Dictionaries, Hashing. | 1x1 · 4x1 | Hashing | CLRS chap. 11 except 11.5. | Chained Hashing · Linear Probing | |
| 12 | Data Structures V: Algorithm on Trees, Predecessor Problem, Binary Search Trees. | 1x1 · 4x1 | Binary Search Trees | CLRS chap. 12 except 12.4. | Binary Search Trees | |
| 13 | Course Wrap-Up: Questions, Selected Exercises from an Old Exam, Advanced Courses in Algorithms. |
The course has mandatory exercises that must be passed inorder to attend the final exam. There are two types of mandatory exercises:
Written exercises These exercises consist of algorithmic challenges that must be answered in writing. You need to hand these in to your teaching assistant who then evaluates them and provides oral feedback (ie. you should ask the TA questions about their corrections). There are 9 of these exercises and you need to pass at least 3 of them to meet the requirements for these exercises. The exercises will appear on DTU Inside as an assigment when they are posed. The mandatory exercise from week x will be available after the lecture in week+1 and your solution must be handed in through DTU Inside before week x+2 on Wednesday at 20.00. You only need to pass 3 out of 9 exercises but we highly recommend that you hand-in all of them and get feedback.
Your hand-ins for the written exercises should be short and precise. Most hand-ins can be answered optimally in 1-2 pages. The hand-in must clearly mark your name, student-id, and the name of the teaching assistant in your class. Do not make a titlepage and do not repeat the text of the exercise. We recommend that you use the following LaTeX-template template.tex to prepare your hand-in (see http://www.latex-tutorial.com/ for an introduction to LaTeX).
Implementation exercises These exercises consist of 4 programming challenges that must be implemented and submitted to the CodeJudge system. You need to pass at least 2 of the exercises to meet the requirements for these exercises. The deadline for submitting the exercises is during exercise classes in week 10 (the same as the deadline for the last written exercise) but you can submit at any time before that. You can find the exercises here.
Collaboration policy All mandatory exercises are subject to the following collaboration policy. The exercises are individual. It is not allowed to collaborate on the exercises, except for discussing the text of the exercise with teachers and fellow students enrolled on the course in the same semester. Under no circumstances is it allowed to exchange, hand-over or in any other way communicate solutions or part of solutions to the exercises. It is not allowed to use solution from previous years, solutions from similar courses, or solutions found on the internet or elsewhere.
What programming and mathematics requirements do I need for the course? In general, you need an introductory course in programming and mathematics. Specifically, for programming you need only basic constructions such as conditional execution, loop, function calls, etc. See the programming prequisites under week 0 to test your programming skills. You can freely choose among standard imperative programming languages for the implementation exercises. For mathematics, the course uses and introduces basic topics from discrete mathematics and hence it is an advantage to have a course in it, but not a requirement.
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 mandatory exercise and the exam in Danish.
I need to quickly refresh my programming skills. What do you recommend? We suggest the book "Introduction to Programming in Java", Sedgewick and Wayne. The book is compact, concise, and focused on the core technical aspects of programming. The books covers essentially all relevant material for the course in chapter 1, which is freely available at the homepage for the book.
Which supplementary books/materials do you recommend? We suggest the following:
What does "give an algorithm" mean? It means, that you describe your solution in a short, precise, and unambigious manner, argue corretness of your solution, and analyse the complexity of your solution. Unless specified otherwise, the description should be in natural language and not pseudocode.
I get error X when I submit my program to CodeJudge. What should I do?/How do I find the bug?/Help! CodeJudge is for a final check of your code (does it produce the correct output for a given input (efficiently)?). To debug your code, construct small test examples and run them on your own computer.
I didn't make the deadline for a mandatory exercise. Can I hand in later? No. In special cases (e.g. illness) we can give an exemption. Talk to the course responsible during class or office hours.
Are there solutions to exercises? Yes! A large portion of the old exams have example solutions (see above).
When and where is the exam? Please see the DTU exam schedule.
I've successfully passed the mandatory assignments at an earlier point in time. Will I have to do them again? Yes and no. You do not need to redo the exercises if you are taking the summer exam and passed them during the spring of the same year. In all other cases, you must (and we highly recommend it) pass them again.
How does the re-exam work? The precise format is subject to change depending on the number of students and the current rules. Typically, the exam and mandatory assignments are very similar to those in the regular semester.
How do I sign up for the re-exam? Please see the DTU pages for how to sign up for a course or exam or ask relevant staff.