line art

Algorithms and Data Structures, Spring 2008

line art
Description Textbook Assignments Newsgroup Schedule
line art

Breaking News

Practicalities

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.

Textbook:

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

Assignments

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.

Newsgroup

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.

Schedule

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]