How do I learn to analyze algorithm complexity

 

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 10-12, Room: 101 SR 00-010 / 14
Exercises:
(1 SWS)
Mondays, 13-14, Room: 101 SR 00-010 / 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 00-006)
PDF of the exam with sample solution & assessment key

Requirements: Basic knowledge of an object-oriented 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
exercise-sheet-01.pdf
2 30.10.2014 6.11.2014 20.11.2014 Induction Proofs, Implementation Heapsort
exercise-sheet-02.pdf
3 6.11.2014 13.11.2014 27.11.2014 O notation, theta and omega
exercise-sheet-03.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
exercise-sheet-04.pdf, and allCountries.zip (269MB). Code from the lecture: spike.cpp, Makefile
5 20.11.2014 27.11.2014 11.12.2014 universal hashing
exercise-sheet-05v2.pdf (update from November 22nd, 2014 in red), Result table hashing
6 27.11.2014 4.12.2014 18.12.2014 Implement PriorityQueue
exercise-sheet-06.pdf
PriorityQueueItem_PseudoCode.h
PriorityQueue_PseudoCode.h
7 4.12.2014 11.12.2014 8.1.2015 Implement dynamic array, amortized analysis
exercise-sheet-07.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
exercise-sheet-08.pdf Code to do this: ArraySumMain.java
9 18.12.2014 8.1.2015 22.1.2015 Master theorem
exercise-sheet-09.pdf
10 8.1.2015 15.1.2015 29.1.2015 Implement binary search tree
exercise-sheet-10.pdf
lecture-10.zip (Example code for a doubly linked list)
BinarySearchTreeNode.H (Pseudo-code template for the exercise)
BinarySearchTree.H
11 15.1.2015 22.1.2015 5.2.2015 Proof O (n) for (4,9) trees
exercise-sheet-11.pdf
12 22.1.2015 29.1.2015 12.2.2015 Graph class, Largest Connected Component
exercise-sheet-12.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
exercise-sheet-13.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
exercise-sheet-14.pdf
Code from the lecture
aol-query-log.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, breadth-first search, depth-first 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: 2015-01-21 by Olaf Ronneberger