4.5 Credit Points
Course Outline
This course provides a detailed introduction to data structures, algorithm design and analysis. The main emphasis is on algorithmic complexity, recursion approaches, graph, sorting and searching algorithms. The purpose of tutorial sessions is to consolidate understanding of the material.
Prerequisites
Basic math skills and some programming background.
Requirements
The course will be examied as part of the general Infotech exam on Friday, March 22nd, 9:00. Also see here.
Time Slots and Locations
| Type | Day | Time | Location |
|---|---|---|---|
| Lecture | Monday every week, starting 15.10.2012. | 15:45-17:15 | V38.02 |
| Tutorial | Wednesday every other week, starting 24.10.2012 | 09:45-11:15 | 0.124 |
Tentative Outline
- Introduction, Basic Models and Tools
- Sorting and Order Statistics
- String Matching
- Data Structures for Ordered Items
- Data Structures for Unordered Items
- Shortest Paths
- Minimum Spanning Trees
- Maximum Flow
- Maximum Matching
- Planar Graphs
- Approximation Algorithms (e.g. Minimum Steiner Tree, Travelling Salesman Problem etc.)
Handouts
Lecture notes. These will be updated as the class progresses, and often without prior notice. Because of this, try to use the electronic version whenever you can (i.e., don’t print). Also, we would appreciate it if you could report to us any errors that you find.
Written notes are provided here (note, though that not everything that was said in the lecture is reflected in the notes; so you need to take your own notes, too):
Some notes from the Q&A session here
Information regarding the exam
There will be an Q&A session on March, 13th, 4pm in V38.01. Everything covered in the lecture is relevant for the exam unless explicitly excluded in the exclusion list of the lecture on Feb. 4th.
Exercises
- Please visit https://eclaus.informatik.uni-stuttgart.de/ and register your account. The registration will be open from the 16. to the 21. oct (incl.)
- Registration is mandatory if you wish to submit any exercise solutions.
- Group I starts at the 24. and Group II at the 31. of october. In your own interest, please try to ballance out the size of both groups.
| Exercise | Remarks |
|---|---|
| Exercise 0 | Due to 23.10. 12:00 |
| Exercise 1 | Due to 06.11. 12:00 |
| Exercise 2 | Due to 20.11. 12:00 – pretty pictures (Rev II 28.Nov.) |
| Exercise 3 | Due to 04.12. 12:00 |
| Exercise 4 | Due to 18.12. 12:00 |
| Exercise 5 | Due to 15.01. 12:00 |
| Exercise 6 | Due to 29.01. 12:00 |
EClaus in Pictures
A small pictured guide for submitting your exercises in EClaus.
Literature
All course topics will be covered in the lecture notes, unless otherwise noted. However, you are free to use the following textbooks for reference/additional reading. Note that none of these covers all topics.
- T. E. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms. MIT Press and McGraw-Hill. 2001. More information will be posted soon.
- R. Motwani, P. Raghavan. Randomized Algorithms. Cambridge University Press. 1995.
- V. V. Vazirani. Approximation Algorithms. Springer. 2001.
- C. H. Papadimitriou, K. Steiglitz. Combinatorial Optimization. Dover. 1998.