Algorithms and Data Structures II, 2007

Exam results

For exam results and comments, see here. Some of you will need an oral exam, you will get an email from Arne A.

Course News

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.

Quick Links: Assignments, Deadlines, Schedule, Material, Examination

Teachers

Practical questions: jonathan.morndal [at] it.uu.se

Schedule

Day Date Time Type Room Lecturer Subject Book chapters
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 Tutorial 1311 Jonathan Mörndal
Tue 25-09-07 10:15-12:00 Tutorial 1311 Jonathan Mörndal
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
15:15-17:00 Tutorial 1111 Jonathan Mörndal
Thu 11-10-07 13:15-15:00 Lecture 1111 Arne Andersson Summary
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)
Mon 15-10-07 10:15-12:00 Lecture 1111 Jonathan Mörndal Summary
Tue 16-10-07 10:15-12:00 Tutorial 1111 Jonathan Mörndal Old exam
Mon 22-10-07 14:00-19:00 Exam Polaksbacken, skrivsal

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

Assignments

Deadlines

Day Assignment
Thu Sep 13 10.00 Hand in Assignment 1
Thu Sep 27, at your seminar or 17:00 Hand in Assignment 2
Fri Oct 12, at your seminar or 10:00 Hand in Assignment 3

Course Material

Slides chapters 1 - 3
Slides chapter 4
Slides chapter 28
Slides chapter 15
Slides chapter 22
Slides chapter 26
Slides chapter 32

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

See schedule

Examination

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!

What to know to pass the exam (pdf).

Example exams

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.