Algorithms (WiSe 2015)

Welcome to the Wiki of the MSc lectures Algorithms (VL: 19400501, UE: 19400502)

General Information

SWS: 2+2 ECTS: 6
Lecturers: Alexander Bockmayr, Oliver Serang
Exercises: Christopher Pockrandt (christopher.pockrandt[at]fu-berlin.de)
Language: English

News

Results of the second exam ("Nachklausur") are online.

Requirements for Aktive Teilnahme

You have to hand in 75% of all programming exercises. (You have to show reasonable programms and can explain them). And further have to hand in your solutions for the theoretical part at the beginning of the exercise. (You don't need to have an exact solution, it is sufficient to show that you tried to solve the problem and sketched your ideas). In addition, you need to reach a minimum of 50% of all points in both reviews.

Times and Places

• The lecture will start October 13th and end on December 8th, 2015.
• The exercises will start October 23th (Please note that attendance on both exercises is mandatory. See below for details)

Event	Day	Time	Address	Room
Lecture	Tue	10-12	Takustr. 9	SR 006
Lecture	Thu	10-12	Takustr. 9	SR 006
Exercise	Fri	12-14	Arnimallee 6	SR 032
Exercise	Fri	14-16	Arnimallee 6	SR 032

Lecture schedule

Date	Lecture	Lecturer
13.10.-15.10.	Analysis Methods and algorithm design
13.10.2015	Lecture 1: Types of algorithms	Serang
15.10.2015	Lecture 2: Different types of analysis	Serang
20.10.-27.10.	Graph algorithms
20.10.2015	Lecture 3: Shortest paths	Bockmayr
22.10.2015	Lecture 4: Maximum flow	Bockmayr
27.10.2015	Lecture 5: Matching	Bockmayr
29.10.-17.11.	Hashing, Skiplists and tree decomposition
29.10.2015	Lecture 6: Hashing I	Serang
03.11.2015	Lecture 7: Hashing II	Serang
05.11.2015	Lecture 8: Skiplists I	Serang
06.11.2015	Review 1 (during exercises)
10.11.2015	Lecture 9: Skiplists II	Serang
12.11.2015	Lecture 10: Tree decomposition I	Serang
13.11.2015, room 032/A6	Lecture 11: Tree decomposition II	Serang
19.11.-04.12.	Computability and Complexity
19.11.2015	Lecture 12: Computability I	Bockmayr
24.11.2015	Lecture 13: Computability II	Bockmayr
26.11.2015	Lecture 14: Complexity I	Bockmayr
27.11.2015	Review 2 (during exercises)
01.12.2015	Lecture 15: Complexity II	Bockmayr
03.12.2015	Rehearsal	Bockmayr / Serang
04.12.2015	First lecture "Optimization"	Bockmayr
08.12.2015	Exam

Additional Material

In this wiki you find additional material for the lectures and exercises (send your wiki (zedat) login name to Christopher Pockrandt to get access): Additional Material

Exercises

Sign up for the mailing list https://lists.fu-berlin.de/listinfo/algooptiWS15

Nr.	Exercise (WiSe15)	Discussion	Comment
1	exercise 1	23.10.	No. 1 updated (19.10.)
1	exercise 2	30.10.
3	exercise 3	06.11.
4	exercise 4	13.11.
5	exercise 5	20.11.
6	exercise 6	27.11.

The exercises will be split into a theoretical and a programming part. During the first exercise the theoretical exercise sheets will be discussed while on the second exercise we will discuss questions and problems related to the programming assignments. The accepted programming language for practical assignments is C++ and you will implement them in groups of three students. Every group will have their own subversion directory and the version of your code at deadline will be considered as your solution.

Programming Exercises

Exams and Reviews

Results Exam 2

Matrikelnummer	points	mark
xxx0598	45,50	4,0
xxx1189	47,50	4,0
xxx2207	49,00	3,7
xxx2427	40,50	5,0
xxx2710	49,00	3,7
xxx4280	51,50	3,7
xxx5950	37,00	5,0
xxx7263	53,00	3,3
xxx7500	59,00	3,0

Results Exam 1

Matrikelnummer	points	mark
xxx411	71,04	2,3
xxx439	47,77	4,0
xxx559	45,23	4,0
xxx598	35,00	5,0
xxx768	62,69	3,0
xxx827	50,23	3,7
xxx1362	78,35	1,7
xxx1684	50,69	3,7
xxx1779	52,31	3,7
xxx1813	48,15	4,0
xxx2164	55,92	3,3
xxx2207	41,65	5,0
xxx2250	67,65	2,3
xxx2427	40,35	5,0
xxx2453	62,62	3,0
xxx2669	55,46	3,3
xxx3144	73,65	2,0
xxx3227	76,92	1,7
xxx3618	46,19	4,0
xxx4181	51,88	3,7
xxx4280	39,15	5,0
xxx4398	57,96	3,3
xxx5950	36,35	5,0
xxx6359	48,08	4,0
xxx6546	50,46	3,7
xxx7263	38,31	5,0
xxx7927	68,04	2,3
xxx8229	50,65	3,7
xxx8378	69,96	2,3
xxx8390	75,96	2,0
xxx8427	48,81	4,0
xxx8437	49,92	3,7
xxx8476	54,23	3,3
xxx8685	50,19	3,7
xxx9539	81,42	1,3