Algorithms and Data Structures (ESE)
Design, analysis and implementation of algorithms (IEMS)
Junior Prof. Dr. Olaf Ronneberger
This lecture introduces basic algorithms and data structures. You will learn to analyze the resource consumption (especially runtime) of a given program, both theoretically (asymptotic analysis) and practically (concrete runtime estimation). You will also learn to judge the optimality of a program, both theoretically (lower bounds) and practically (the program runs as fast as it could).
Lectures: (2 SWS)  Thursdays 1012, Room: 101 SR 00010 / 14 
Exercises: (1 SWS)  Mondays, 1314, Room: 101 SR 00010 / 14 (as required) Contact: Claudius Korzen 
Start:  Thursday, October 23, 2013 
ECTS points:  ESE: 4; IEMS: 6 
Semester according to the curriculum:  ESE: 3 
Exam:  Friday, February 27th, 2015, 4 p.m.  6 p.m., "cinema auditorium" under the cafeteria (building 082, room HS 00006) PDF of the exam with sample solution & assessment key 
Requirements:  Basic knowledge of an objectoriented higher programming language (Java or C ++) 
Left: 

Exercises
No  output  Levy (ESE)  Submission (IEMS)  Materials & Links 

1  22.10.2014  30.10.2014  13.11.2014  Insertion sort; Heaps; Daphne, SVN, Jenkins exercisesheet01.pdf 
2  30.10.2014  6.11.2014  20.11.2014  Induction Proofs, Implementation Heapsort exercisesheet02.pdf 
3  6.11.2014  13.11.2014  27.11.2014  O notation, theta and omega exercisesheet03.pdf, Recording of the exercise lesson on November 17th: Exercise_AlgoDatESE + IEMS_03.mp4 
4  13.11.2014  20.11.2014  4.12.2014  associative arrays, most common city name exercisesheet04.pdf, and allCountries.zip (269MB). Code from the lecture: spike.cpp, Makefile 
5  20.11.2014  27.11.2014  11.12.2014  universal hashing exercisesheet05v2.pdf (update from November 22nd, 2014 in red), Result table hashing 
6  27.11.2014  4.12.2014  18.12.2014  Implement PriorityQueue exercisesheet06.pdf PriorityQueueItem_PseudoCode.h PriorityQueue_PseudoCode.h 
7  4.12.2014  11.12.2014  8.1.2015  Implement dynamic array, amortized analysis exercisesheet07.pdf DynamicArrayTest.cpp DynamicArray.h DynamicArray.cpp DynamicArrayMain.cpp DynamicArrayTest.java DynamicArray.java DynamicArrayMain.java MagicSystem.java 
8  11.12.2014  18.12.2014  15.1.2015  Cache efficiency exercisesheet08.pdf Code to do this: ArraySumMain.java 
9  18.12.2014  8.1.2015  22.1.2015  Master theorem exercisesheet09.pdf 
10  8.1.2015  15.1.2015  29.1.2015  Implement binary search tree exercisesheet10.pdf lecture10.zip (Example code for a doubly linked list) BinarySearchTreeNode.H (Pseudocode template for the exercise) BinarySearchTree.H 
11  15.1.2015  22.1.2015  5.2.2015  Proof O (n) for (4,9) trees exercisesheet11.pdf 
12  22.1.2015  29.1.2015  12.2.2015  Graph class, Largest Connected Component exercisesheet12.pdf Graph.H (Pseudocode template), code_vorlesung_12.zip (Code from the lecture) saarland.graph (16MB), Results table LCC 
13  29.1.2015  5.2.2015  19.2.2015  Dijkstra's algorithm exercisesheet13.pdf bawue_bayern.zip (102MB), Result table of Dijkstra's algorithm 
14  5.2.2015  12.2.2015  19.2.2015 (only 2 weeks processing time, so that the sample solutions can be put online in time for exam preparation)  Dynamic programming, editing distance exercisesheet14.pdf Code from the lecture aolquerylog.zip (8.6MB), Result table for editing distance 
lectures
No  date  subjects  Foils  Recordings (approx. 105MB each) 

1  Thursday, October 23, 2014  Introduction, organizational matters, sorting  Lecture_AlgoDatESE + IEMS_01.pdf, Lecture_AlgoDatESE + IEMS_01_handout.pdf  Lecture_AlgoDatESE + IEMS_01.mp4 
2  Thursday, October 30, 2014  Runtime analysis MinSort and HeapSort, induction proof  Lecture_AlgoDatESE + IEMS_02.pdf  Lecture_AlgoDatESE + IEMS_02.mp4 
3  Thursday, November 6, 2014  O notation, theta, omega  Lecture_AlgoDatESE + IEMS_03.pdf  Lecture_AlgoDatESE + IEMS_03.mp4 
4  Thursday, November 13, 2014  Medium runtime, associative arrays aka maps  Lecture_AlgoDatESE + IEMS_04.pdf  Lecture_AlgoDatESE + IEMS_04.mp4 
5  Thursday, November 20, 2014  How to build a hash map, universal hashing  Lecture_AlgoDatESE + IEMS_05.pdf  Lecture_AlgoDatESE + IEMS_05.mp4 
6  Thursday, November 27, 2014  Hashing, collision handling, priority queues  Lecture_AlgoDatESE + IEMS_06.pdf  Lecture_AlgoDatESE + IEMS_06.mp4 
7  Thursday, December 4th, 2014  Dynamic fields and amortized analysis  Lecture_AlgoDatESE + IEMS_07.pdf  Lecture_AlgoDatESE + IEMS_07.mp4 
8  Thursday, December 11, 2014  Cache efficiency, "divide and conquer"  Lecture_AlgoDatESE + IEMS_08.pdf  Lecture_AlgoDatESE + IEMS_08.mp4 
9  Thursday, December 18, 2014  Divide and conquer, master theorem  Lecture_AlgoDatESE + IEMS_09.pdf  Lecture_AlgoDatESE + IEMS_09.mp4 
10  Thursday, January 8th, 2015  Linked lists, binary search trees  Lecture_AlgoDatESE + IEMS_10.pdf  Lecture_AlgoDatESE + IEMS_10.mp4 
11  Thursday, January 15, 2015  Balanced search trees  Lecture_AlgoDatESE + IEMS_11.pdf  Lecture_AlgoDatESE + IEMS_11.mp4 
12  Thursday, January 22nd, 2015  Graphs, breadthfirst search, depthfirst search, connected components  Lecture_AlgoDatESE + IEMS_12.pdf  Lecture_AlgoDatESE + IEMS_12.mp4 
13  Thursday, January 29th, 2015  Shortest paths, Dijkstra's algorithm  Lecture_AlgoDatESE + IEMS_13.pdf (Update 2.3.2015: Slide 23)  Lecture_AlgoDatESE + IEMS_13.mp4 
14  Thursday, February 5th, 2015  Editing distance, dynamic programming  Lecture_AlgoDatESE + IEMS_14.pdf  Lecture_AlgoDatESE + IEMS_14.mp4 
15  Thursday, February 12, 2015  Evaluation, exam, presentation of the working group  Lecture_AlgoDatESE + IEMS_15.pdf  Lecture_AlgoDatESE + IEMS_15.mp4 
last changed: 20150121 by Olaf Ronneberger