Algorithms and Data Structures 3, 2009, 1DL030

Visit this page often for updated information and important news.

Teacher

Practical questions: Call Arne: 0733 66 55 15

Important!

  • Written Exam, 2009-03-13, 8:00 - 13:00, Siegbahnsalen Ångström.
  • Oral Exam, book you time slot here http://ad3.booru.net
    • Location, Arne's office, house 1, room 1354

Guest Lecture

Friday the 13th, room 1211, 14:15 - 15:00

Assignments

See schedule.
At the end of the course, each student will have an oral examination, where you
must bring solutions to

(i) all mandatory assignments, and

(ii) at least half of the other assignments.

Your solutions must be nicely printed (not handwritten, but it is ok to include handmade figures if they are nicely done)
The level of detail should be roughly as the explanations in the book.

Schedule

Day Time Room Topic Book Chapter Assignment
Thu Jan 22 13.15-15.00 Pol_1245 Review of old knowledge, Probabilistic Analysis, Randomized Algorithms 1-4, 5
Mon Jan 26 15:15-15:00 Pol_1245 Sorting in linear time, Median and Order statistics 8, 9
Thu Jan 29 15:00-17:00 Pol_1245 CANCELED 13
Mon Feb 2 15:15-17:00 Pol_1245 Variants of Balanced trees, red-black trees, etc 13 Problems 9-1, 9-2 a,b,c
Wed Feb 4 10:15-12:00 Pol_1245 Augmenting data structures 14
Thu Feb 5 15:15-17:00 Pol_1245 Amortized Analysis 17 Answer the questions on the last slide of the handout on radix sort. Do Exercises 14-3.1, 14-3.2, 14-3.3
Tue Feb 10 15:15-17:00 Pol_1245 B-Trees, 18
Thu Feb 12 13:15-15:00 Pol_1245 B-trees, Sorting Networks 18, 27 Problem 17-3 (mandatory)
Fri Feb 13 14:15-15:00 Pol_1211 Guest Lecture by Professor Peter Bro Miltersen
Tue Feb 24 13:15-15:00 Pol_1145 Universal hashing Perfect Hashing, Tries, van Emde Boas-trees 11.3, 11.5, Handout Problem 18-2 (mandatory) Exercise 27.1-4
Wed Feb 25 10:15-12:00 Pol_1245 Tries, van Emde Boas-trees, Packed computation, very fast sorting and searching Handout "New bounds on sorting and searching,", sections 1-4 Exercise 11.5-1, Problem 11-4* (It is mandatory to do at least one of these two)
Thu Fe 26 13:15-15:00 CANCELED
Tue Mar 3 13:15-15:00 Pol_1145 Linear Programming and Integer Programming, NP-completeness 29, 34, see also the wikipedia article http://en.wikipedia.org/wiki/Linear_programming Problem 3 in the handout on sorting and searching. Exercises 29.2-2, 29.2-4, 29.2-6
Wed Mar 4 13:15-15:00 Pol_1245 NP-completeness, Polynomials and Fast Fourier Transforms, rehearsal 34, 30
Fri Mar 6 10:15-12:00 Pol_1145 Exam preparation Exercises 30.2-2, 30.2-3, 34.1-4, 34.2-6, 34.2-7 (Hint, use topological sorting), 34.2-10, 34.4-6, 34.5-2
Thu Mar 12 10:15-12:00 CANCELED
Fri Mar 13 08:00-13:00 Siegbahnsalen Ångström Written Exam

Course Material

Old Exams

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

Prepare yourself by

  • reading and understanding all material (textbook chapters and handouts)
  • solving more exercises in the book
  • refresh your memory of the book chapters covered by earlier courses. (Altogether, the AD1, AD2, and AD3, have covered chapters 1 - 18, 21 - 30, 32 - 34)

Examination

i. Written Exam
ii. Oral examination, each student will have an oral exam, after the written exam. At the oral exam, you must bring written solution (not handwritten, but nicely formatted)
solutions to at least half of the assignments.)

Rules for exam:
In addition to the normal stuff (pens, pencils, eraser, ruler and so forth), you should bring the textbook. At the exam, you will also be provided with a copy of sections 1-4 of "New bounds on sorting and searching".