Exercises

The exercise sheets appear weekly every Wednesday on this web-page. Solutions can be submitted electronically to algtheory08@informatik.uni-freiburg.de until the following Monday 11:59:59 am. Please note also the submission formatting rules stated below.
  1. Exercise Divide and Conquer: Closest-Pair (pdf version 2008-10-21, submission deadline 2008-10-27)
  2. Exercise Line Segment Intersection, Polynomials (pdf version 2008-10-29, submission deadline 2008-11-03)
  3. Exercise Fast Fourier Transform (pdf version 2008-11-05, submission deadline 2008-11-10)
    • proposal for a solution: pdf (version 2008-11-12)
  4. Exercise Randomized Quicksort, Primalty Test (pdf version 2008-11-14 [first version had a typo], submission deadline 2008-11-17)
  5. Exercise RSA, Universal Hashing (pdf version 2008-11-19)
  6. Exercise Treap (pdf version 2008-11-26)
  7. Exercise Greedy (pdf version 2008-12-03)
  8. Exercise Bin Packing (pdf version 2008-12-10)
  9. Exercise Dynamic Programming (pdf version 2008-12-17)
  10. Exercise Approximate String Matching (pdf version 2009-01-07)
  11. Exercise Suffix Trees (pdf version 2009-01-14)
  12. Exercise Implicit Suffix Trees, KMP Algorithm (pdf version 2009-01-21)
  13. Exercise Dijkstra, Bellman & Ford (pdf version 2009-01-28)
  14. Exercise Binomial Queue, Fibonacci Heap (pdf version 2009-02-04)

Registration

In addition to the HIS-System you must register for your exercise class within the corresponding message thread in the forum by entering your name. Do not publish your matriculation number because of data protection.

Important: when asked ignore the visual code and type Schindelhauer instead. This measure has been designed to fight spam-bots attacking our forum ((c) Arne Vater).


Bonus points

  • 1 bonus point for each correct solution of an exercise task (where stated)
  • 1 bonus point for the correct presentation of the solution of an exercise
  • 1 extra bonus point for an excellent solution of an exercise task
The maximum reachable number of  bonus points is 15. This corresponds to 1/6 of the exam points.

Submission Guidelines

  • PDF submissions mandatory: We accept only electronical submissions in PDF (e.g. scanned, photographed handwritten documents are allowed as well as Word or LaTeX documents exported in PDF).
  • Correct subject required: XX-Y-MMMMMMM Firstname Lastname
    where XX = sheet number, Y = group letter,  MMMMMMMM = matriculation number.
    • 03-C-7654321 John McCain
      is a correct subject line for the third week exercise solution of John McCain in the group C (of Stefan Rührup) with matriculation number 7654321
    • Ralph Nader group A exercise 3
      will be ignored since our autmatic forwarding mechanism cannot handle this format
  • Only original work is accepted
    • if a copied submission shows up, both, the original and copied submission will be rejected
  • Deadline of Monday, 11:59:59 am must be obeyed
    • later submissions will be forwarded to the tutor, but are not eligible for bonus points