# Design and Analysis of Algorithms (Winter 2018/2019)

Announcements Monday, Jan 7, 5 pm:
Friday, Jan 11: |
Design and analysis of efficient algorithms are omnipresent and thus their study is an important topic in computer science and beyond. This course provides a comprehensive overview of algorithmic questions and design techniques. We strive to convey an approach to algorithmics that begins with the systematic analysis of the problem, builds on an understanding of the common techniques to design algorithms, and results in an efficient solution to the problem. This course is the basis for further studies in the field of algorithmics including graph algorithms. It provides advice on how to identify algorithmic problems in complex issues and how to design efficient and sophisticated algorithms for the resulting problems. |

## General Information

Lecture (S. Cornelsen) | Mon 11:45 - 13:15, M 630 Mon 15:15 - 16:45, M 630 |

Tutorial | Fri 13:30 - 15:00, M 628 |

Oral Exam: |
1st date: Monday, 11th of February 2019 in PZ 1006 2nd date: Monday, 8th of April 2019 in PZ 1006 (please register in the StudIS and sign into the list available in PZ 1002) |

## Homework Assignments

The assignments are made available on this webpage as a PDF-file every **Monday** after the lecture.

The editing time for each homework is almost one week.

- It is due on the next
**Monday at 11:30**. - The assignments have to be delivered in written form either in English or German.
- You have to submit them electronically to
**ea_u_W18@inf.uni-konstanz.de**(one PDF only!!). - Please follow the naming schema
**uXX_name1_name2.pdf**, where**XX**indicates the number of the assignment.

The requirements for the admittance to the final exam are 50 percent of the total score of the assignments and an active participation at the tutorials. In writing up your assignments, be as clear, precise, and concise as possible. Understandability will be an important factor in the scoring of the assignments. Regular attendance is considered especially for borderline cases.

*You are permitted and encouraged to work in groups of two.*

No. | Post Date | Due Date | Tutorial | Download | Material (local access only) | |
---|---|---|---|---|---|---|

01 | 22.10.2018 | 29.10.2018 | 02.11.2018 | Assignment 1 | ||

02 | 29.10.2018 | 05.11.2018 | 09.11.2018 | Assignment 2 | ||

03 | 05.11.2018 | 12.11.2018 | 16.11.2018 | Assignment 3 | ||

04 | 12.11.2018 | 19.11.2018 | 23.11.2018 | Assignment 4 | ||

05 | 19.11.2018 | 26.11.2018 | 30.11.2018 | Assignment 5 | ||

06 | 26.11.2018 | 03.12.2018 | 07.12.2018 | Assignment 6 | ||

07 | 03.12.2018 | 10.12.2018 | 14.12.2018 | Assignment 7 | ||

08 | 10.12.2018 | 17.12.2018 | 21.12.2018 | Assignment 8 | ||

09 | MONDAY 07.01.2019 5:00 pm | Replaced by Mini-Presentations in P601 Please send your slides/mindmaps as a pdf until Jan 7th, 11:45 am |
||||

10 | 07.01.2019 | 14.01.2019 | 18.01.2019 | Assignment 10 | ||

11 | 14.01.2019 | 21.01.2019 | 25.01.2019 | Assignment 11 | ||

12 | 21.01.2019 | 28.01.2019 | 01.02.2019 | Assignment 12 | ||

13 | 28.01.2019 | 04.02.2019 | 08.02.2019 | Assignment 13 |

Note that some links are only locally accessible.

## Some Lecture Notes and Supplemental Course Materials (locally accessible)

## Textbooks

- T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms. McGraw-Hill, 2001 (2nd ed.)
- R.K. Ahuja, T.L. Magnanti, J.B. Orlin: Network Flows. Prentice Hall, 1993.
- T. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen. BI-Wissenschaftsverlag, 1993
- D. Jungnickel: Graphen, Netzwerke und Algorithmen. BI-Wissenschaftsverlag, 1994
- J. Kleinberg, E. Tardos: Algorithm Design. Addison-Wesley, 2006
- M.T. Goodrich, R. Tamassia: Algorithm Design. Wiley, 2002