Data Structures and Algorithms

Lecturer: M. Böhlen
Teaching assistant: R. Kasperovics (English), M. Innerebner (Italian, German)
Teaching language: English
Prerequisites: Basic programming skills and mathematical knowledge
Office hours: FR 12:30 - 14:00 (prior notification by email required)
Academic Year 2008/9, 2nd semester

Home | Syllabus | Lectures | Assignments | Exam

General

Start date: Monday, February 23, 2008
Lectures:  MO 10:30-12:30 && WE 10:30 - 12:30, Room D003
Labs:  TH 8:30-10:30 (English) - Room E431 || 8:30-10:30 (Italian) - Room E531 || 14:00-16:00 (German) - Room E531

Office hours: FR 12:30-14:00 (prior notification by email required)

Objectives: Acquire an in-depth understanding of a broad set of computer science techniques to solve algorithmic problems. These techniques are fundamental building blocks that re-occur in many areas of computer science. Become familiar with the design and analysis of divide and conquer algorithms. Learn how to be precise and mathematically rigorous when designing and verifying algorithms.

Teaching Format: Lectures and exercises with assignments. The assignments are a very important part of the course. Each week an assignment has to be solved. After the exercise class you have one week to solve the assignment and hand it in at the beginning of the next exercise class (or send it by mail/fax). Late hand-ins are not accepted. The assignments will be checked. A number of assignments involve programming in C. Although the programming language is not a crucial part of this course it is strongly recommended that you implement and run all programming exercises. The recommended way to do this is to use the server of the university. The details will be explained in the first lab session.

Assessment: The assessment is either based on the assignments and the final written exam or on the final written exam only. You are strongly encouraged to solve and hand in the weekly assignments. There is no midterm. Successfully solved assignments contribute 1/2 point toward your final grade. Each student can earn at most 5 credit points. The total number of assignments are 11 (10 of them are evaluated). The points from the assignments are valid until the next version of the course is taught, i.e., they apply to the following three exam sessions. Assignment points earned in connection with previous versions of this course do not count. The final written exam follows the standard grading system, i.e., 30 is the highest grade and 18 is lowest passing grade.

Syllabus

Learning Outcome: A toolbox with the most important techniques for solving algorithmic problems. Ability to use a systematic, precise, and mathematically rigorous approach to design and reason about algorithms. Basic understanding of algorithmic complexity. Basic understanding of C and dynamic memory management.

Reading List: The course textbook is the 2nd edition of Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein (CLRS). Sample copies of the book are available at our library. Online resources for buying the book: MIT Press and Amazon and Google Books. The lecture notes will be created as we progress through the semester. There is a set of lecture notes for each week. It is recommended that you download and print the lecture notes immediately before the respective lectures.

Lectures

  1. MO 23.2.09, WE 25.2.09; Introduction, recursion, sorting, Hilbert curve; 1up, 4up
  2. MO 2.3.09, WE 4.3.09; Algorithmic complexity, correctness, asymptotic analysis, special case analysis; 1up, 4up
  3. MO 9.3.09, WE 11.3.09; Divide and conquer, tiling, binary search, recurrences; 1up, 4up
  4. MO 16.3.09, WE 18.3.09; Complete binary trees, heapsort, quicksort, randomized quicksort; 1up, 4up
  5. MO 23.3.09, WE 25.3.09; Pointers, lists, abstract data types, queues; 1up, 4up
  6. MO 30.3.09, WE 1.4.09; Trees, binary search trees, red-black trees; 1up, 4up
  7. MO 6.4.09, WE 8.4.09; Hash tables, hash functions, conflict resolution; 1up, 4up
  8. WE 15.4.09, MO 20.4.09; Dynamic programming, matrix multiplication, longest common subsequence; 1up, 4up
  9. WE 22.4.09, MO 27.4.09; Graphs, DFS, BFS, topological sort; 1up, 4up
  10. WE 29.4.09, MO 4.5.09; Weighted graphs, minimum spanning trees, Kruskai, Prim, shortest path, Dijkstra, Bellman-Ford; 1up, 4up
  11. WE 6.5.09, MO 11.5.09; Tractable and intractable problems, NP problems, NP complete problems 1up, 4up
  12. WE 13.5.09, MO 18.5.09; repetition of course material, preparation for exam

Assignments

Assignments have to be submitted every thursday before 8:30am;

Credit points table: Results

  1. TH 25.2.09; Introduction to labs, environment and C programming. Algorithm design, fractals, recursion:
    Assignment 01: 1up, 4up. Solution 01: 1up, 4up
    A graphical hello world program using glut ghello.c
  2. TH 3.3.09; Complexity of algorithms:
    Assignment 02: 1up, 4up. Solution 02: 1up, 4up
  3. TH 12/3/2009; Divide-and-conquer, recurrences:
    Assignment 03: 1up, 4up. Solution 03: 1up, 4up
  4. TH 17.3.09; Recurrences, quicksort:
    Assignment 04: 1up, 4up. Solution 04: 1up, 4up
  5. TH 26.3.09; Priority queues, linked lists:
    Assignment 05: 1up, 4up. Solution 05: 1up, 4up
  6. TH 2.4.09; Radix trees, binary search tree:
    Assignment 06: 1up, 4up. Solution 06: 1up, 4up
  7. TH 9.4.09; Red-black trees, double hashing:
    Assignment 07: 1up, 4up. Solution 07: 1up, 4up
  8. TH 16.4.09; Hash tables, experimental analysis:
    Assignment 08: 1up, 4up. Solution 08: 1up, 4up
  9. TH 23.4.09; Word wrap, matrix chain multiplication:
    Assignment 09: 1up, 4up. Solution 09: 1up, 4up
  10. TH 30.4.09; Wireless Network, DFS, BFS:
    Assignment 10: 1up, 4up. Solution 10: 1up, 4up
  11. TH 7.5.09; Minimum spanning trees, shortest paths:
    Assignment 11: 1up, 4up

Exam

A number of exams from previous sessions are available. Solving them is a good preparation for the exam. When doing so it is important that you choose a setup that resembles the one of the exam, i.e., solve the exams on your own and do so without auxiliary material (except one A4 two-sided sheet with your notes as allowed at the exam).

Academic year 2003/4: 2004.06.23, 2004.09.21, 2005.02.07
Academic year 2004/5: 2005.06.22, 2005.09.16, 2006.02.13
Academic year 2005/6: 2006.06.22, 2006.09.22, 2007.02.16
Academic year 2006/7: 2007.06.22, 2007.09.21, 2008.02.12
Academic year 2007/8: 2008.07.10, 2008.09.10, 2009.02.03

Disclaimer: the information on this page is tentative and subject to change. It comes without any warranty.