Algorithms and Data Structures II, 2007
For exam results and comments, see here. Some of you will need an oral exam, you will get an email from Arne A.
O71023: Assignment 4 and course evaluation now online.
071001: Assignment 3 is now online.
070914: Assignment 2 is now online. It also contains some recommended exercises for the first part of the course.
070906: Slides for chapters 1-4 are added.
070904: The tutorial on Friday 7/9 10-12 has been moved to 13-15.
070903: Some modifications to the schedule.
070903: E-mail sent to all who signed up on the first lecture. However, some of the addresses bounced. People with the following dates of birth should contact me if you want to receive the information: 850801, 870209, 831113, 840625
070830: Assignment 1 is added.
070829: This page is created.
Visit this page often for updated information and important news.
|Thu||30-08-07||10:15-12:00||Lecture||1311||Arne Andersson||Introduction, rehearsal of previous course, growth of functions||1-3 + chapters covered in first algorithms course|
|Tue||04-09-07||10:15-12:00||Lecture||1311||Arne Andersson||Growth of Functions, recurrences, more rehearsal||4 (Except 4.4)|
|13:15-15:00||Lecture||1311||Arne Andersson||Recurrences||4 (Except 4.4)|
|Thu||06-09-07||13:15-15:00||Lecture||1311||Arne Andersson||Example of using recurrences: Strassen's algorithm for matrix multiplication||28.2|
|Fri||07-09-07||10:15-12:00||Tutorial||1311||Jonathan Mörndal||Introduction to Assignment 1, examples|
|Tue||11-09-07||10:15-12:00||Tutorial||1211||Jonathan Mörndal||Examples, practice|
|Thu||13-09-07||10:15-12:00||Seminar||1212||Jonathan Mörndal||Assignment 1 (held in Swedish)|
|13:15-15:00||Seminar||1311||Jonathan Mörndal||Assignment 1 (held in English)|
|Tue||18-09-07||13:15-15:00||Lecture||1311||Arne Andersson||Dynamic Programming||15|
|Wed||19-09-07||10:15-12:00||Lecture||1111||Arne Andersson||Dynamic Programming||15|
|Fri||21-09-07||10:15-12:00||Lecture||1311||Arne Andersson||Greedy algorithms||16.1, 16.2, 16.3, pp. 370-392|
|13:15-15:00||Lecture||1311||Arne Andersson||Elementary Graph Algorithms||22.1 - 22.5|
|Thu||27-09-07||10:15-12:00||Lecture||1311||Arne Andersson||Minimum spanning trees. Kruskal's algorithm, Dijkstra's algorithm||23, 24.3 (pp. 595-600)|
|13:15-15:00||Seminar||1213||Jonathan Mörndal||Assignment 2 (held in Swedish)|
|15:15-17:00||Seminar||1213||Jonathan Mörndal||Assignment 2 (held in English)|
|Tue||02-10-07||10:15-12:00||Lecture||1111||Arne Andersson||Maximum Flow||26.1 - 26.3|
|Wed||03-10-07||13:15-15:00||Lecture||1311||Arne Andersson||String matching||32|
|Thu||04-10-07||13:15-15:00||Lecture||1311||Arne Andersson||Computational geometry||33|
|Mon||08-10-07||13:15-15:00||Lecture||1111||Arne Andersson||Computational geometry|
|Fri||12-10-07||10:15-12:00||Seminar||1212||Jonathan Mörndal||Assignment 3 (held in Swedish)|
|13:15-15:00||Seminar||1212||Jonathan Mörndal||Assignment 3 (held in English)|
|Tue||16-10-07||10:15-12:00||Tutorial||1111||Jonathan Mörndal||Old exam|
Explanation for schedule
- "Lecture" means an ordinary lecture, where new concepts are introduced
- "Tutorial" means a session where there might be concrete examples, questions or time to work on the exercises
- "Seminar" means a session to which one must register in advance, and where there will be a discussion about the assignment
Literature and Notes
Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms, 2nd edition, MIT Press, 2001 (last available printing: 4th). Visit the book's web site at http://mitpress.mit.edu/algorithms/ (errata etc.)
Reading instructions for the written exam
i. Assignments (+ seminars)
ii. Written Exam
Rules for exam:
In addition to the normal stuff (pens, pencils, eraser, ruler and so forth), you are allowed to bring ONE standard A4 sheet of notes to the exam, with whatever notes you find useful. Remember that this will in no way help you if you have not practiced the application of the techniques already. So keep on studying!
- Example exam (by Arne)(pdf).
- Last year exam (by Arne)(pdf).
- Old Exam 1 (not by Arne)(pdf).
- Old Exam 2 (not by Arne)(pdf).
The unacceptable quality of the last two exams is due to the fact that there were no digital version of them, and they thus had to be redigitalised. This is a lesson to you all. The more you print, the more analogue the world gets.