Data Structures and Algorithms

Group 2

Instructor: Laszlo Ferenc Szabo, Assistant: Istvan Andras Seres

Location: D-0.221, Time: Tuesday 12:00-14:00

NOTE: Participation is mandatory! You can miss 3 sessions at max!

1st week exercises

3rd week exercises Big O notation in a nutshell :)

4th week exercises Proof for the constant soundness error of Freivald's algorithm can be found here!!!

5th week exercises At the end of the session I introduced interactive zero-knowledge proofs (IZKP) to motivate randomized algorithms. A really fun read to have a high-level overview of IZKPs. Fun fact: the author listed all his children as co-authors! :) You can read it by clicking here!!!


7th week exercises

8th week exercises A neat write-up from Boldizsar Poor on Problem 219 from Project Euler. See here!!!

9th week exercises

10th week exercises

11th week exercises

Highly suggested programming exercises

If you want to have a better understanding of the underlying algorithmic ideas, how the choice of an algorithm affects running time and for related questions, please refer to these exercises. These are not graded, you should complete them as practicing exercises.
Brute force: Project Euler Problem 18 (You could solve this using dynamic programming, would be interesting to compare running times for the two approaches!)
Break this code: Fun Project Euler exercise to break a XOR encryption function :)
Dynamic programming: Project Euler Problem 67,81,82,83
Huffman codes: Project Euler Problem 219 This exercise is closely related to Huffman codes. You need to use the fact here that Huffman codes are optimal.