Where and when: Thursdays and Fridays 9:00-12:00, Room 4A16
| Teachers | Office |
| Andrzej Wąsowski (wasowski at itu.dk) | 3C08 |
| Rasmus Resen Amossen (resen at itu.dk) | 3C09 |
You are welcome with any problems, concerns, questions etc. regarding the contents, organization, style etc. of the course. Contact the teachers any time you can catch them.
[GT] Michael T. Goodrich and Roberto Tamassia. Algorithm Design. John Wiley & Sons 2001. Available in IT-bogladen in the atrium.
The book has an informative website.
This course requires systematic work, and we prepare many assignments for you — all are mandatory. The only way to succeed in the exam is to solve all kinds of practical assignments. Just reading the book will not help you much!!!
Homeworks: We post tasks for written homeworks every week. The deadline for handing in your solution is normally on Thursday, before 9:00 in the week following the publication of the homework, unless announced differently. Deadlines are strict. Put your solution in the course pigeon hole, in front of the study administration. We only accept hard copies (manuscripts or printouts), no email. Assignments can be written in Danish. Homeworks should be prepared in two person groups. Other configurations need an explicit permission from Rasmus. Please talk to Rasmus during exercise classes.
Quizes: Every week there is written test during class activities. These tests are graded pass/fail by Andrzej and Rasmus. Try not to come late for the lectures, as these decreases your chances to pass.
Mid-term: There will be a written 2h mid-term "exam" scheduled early April. Results are graded by the lecturer.
Programming assignments: Every week there is a new programming assignment. These are allocated to students on a rotating basis. Every week 4 students (2 groups of 2) are supposed to implement a programming task. The precise matching of groups to weeks is done during exercises classes. Each student must agree to accept such a programming assignment at least once during the semester.
You are expected to use 15 hours a week on average on this course.
Please post questions and comments to the BADS newsgroup (it-c.courses.BADS) so that others may answer your questions and/or share your insights. Feel free to answer each other's questions and comment on messages. The newsgroup is our discussion forum. Sending and receiving news messages is very similar to sending and receiving e-mails. You can use mozilla, the standard mail&news client at ITU, to read the newsgroups. Ask SysAdm if you need help setting up your software for reading news. There is also this information about newsgroups, available from SysAdm.
The following schedule is permanently tentative. Please report any errors you can see in the schedule or in the course material to Andrzej.
| Week | Date | Time | Learning Activity | |
| 1 | Jan 31 | 9:00—12:00 | Lecture [AW]: Introduction and Organization | |
| Lecture [AW]: Analyzing Algorithms | ||||
| Exercises [AW+RRA] | ||||
| Feb 1 | 9:00-12:00 | Lecture [AW]: Examples of Analysis | ||
| Lecture [AW]: Stacks and Queues | ||||
| A brainstorm session [AW+RRA] | ||||
| 2 | Feb 7 | 9:00—12:00 | Quiz [AW] | |
| Lecture [AW]: Vectors, lists, sequences | ||||
| Exercises [AW+RRA] | ||||
| Feb 8 | 9:00-12:00 | Lecture [AW]: Trees | ||
| Lecture [AW]: Priority queues and simple sorting | ||||
| A brainstorm session [AW+RRA] | ||||
| 3 | Feb 14 | 9:00—12:00 | Quiz [AW] | |
| Lecture [AW]: Heaps and Heap-Sort | ||||
| Exercises [AW+RRA] | ||||
| Feb 15 | 9:00-12:00 | Lecture [AW]: Hashing | ||
| Lecture [AW]: Amortization and Dynamic Hashing | ||||
| A brainstorm session [AW+RRA] | ||||
| 4 | Feb 21 | 9:00—12:00 | Quiz [AW] | |
| Lecture [AW]: Amortization revisited | ||||
| Exercises [AW+RRA] | ||||
| Feb 22 | 9:00-12:00 | Lecture [AW]: Binary Search Trees | ||
| Lecture [AW]: Balanced Trees (AVL) [read GT 3.2, without Theorem 3.2 and Section 3.2.2] | ||||
| A brainstorm session [AW+RRA] | ||||
| 5 | Feb 28 | 9:00—12:00 | Quiz [AW] | |
| Lecture [AW]: Search Trees Revisited | ||||
| Exercises [AW] | ||||
| Feb 29 | 9:00-12:00 | Lecture [AW]: Merge-Sort | ||
| Lecture [AW]: Performance of Merge-Sort | ||||
| A brainstorm session [AW] | ||||
| 6 | Mar 6 | 9:00—12:00 | Quiz [AW] | |
| Lecture [AW]: Performance of Quicksort | ||||
| Exercises [AW] | ||||
| Mar 7 | 9:00-12:00 | Lecture [AW]: Characterization of sorting I | ||
| Lecture [AW]: Characterization of sorting II | ||||
| A brainstorm session [AW] | ||||
| 7 | Mar 13 | 9:00—12:00 | Quiz [AW] | |
| Lecture [AW]: Graphs, BFS, DFS | ||||
| Exercises [AW+RRA] | ||||
| Mar 14 | 9:00-12:00 | Lecture [AW]: Shortest paths (Dijkstra) [read GT 6.4.0, 6.4.1,7.1.0, 7.1.1] | ||
| Lecture [AW]: Heuristic search (A*) | ||||
| A brainstorm session [AW] | ||||
| Easter Vacation | ||||
| 8 | Mar 27 | 9:00—12:00 | Lecture [AW]: Minimum Spanning Trees | |
| Exercises [AW+RRA] | ||||
| "Hvad nu" møde [Anne Marie Kranc] | ||||
| Mar 28 | 9:00-12:00 | Quiz [AW] | ||
| Lecture [AW]: Text Compression | ||||
| A brainstorm session [AW] | ||||
| 9 | Apr 3 | 10:00—12:00 | Mid-term exam [RRA] 10:00-12:00! | |
| Apr 4 | No classes: Programming Contest launched electronically | |||
| 10 | Apr 10 | 9:00—12:00 | Quiz [AW] | |
| Lecture [AW]: Network Algorithms (leader election) [read pp. 511—523, up to 90 minutes] | ||||
| Exercises [AW+RRA] | ||||
| Apr 11 | 9:00-12:00 | Lecture [AW]: Distributed BFS & MST algorithms [read GT 11.2.3–11.2.4 pp. 523–529, up to 60 minutes] |
||
| Exam preparation [AW+RRA] | ||||
| 11 | Apr 17 | 9:00—12:00 | Quiz [AW] | |
| Exam preparation [AW+RRA] | ||||
| Apr 18 | Store Bededag | |||
| 12 | Apr 24 | 9:00—12:00 | Quiz [AW] | |
| Exercises + exam training [AW+RRA] | ||||
| Apr 25 | 9:00—12:00 | "Hvad nu?" & Exam preparation [AW+RRA] | ||