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!!!
Midterm
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!)
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.