# Theory I

The goal of this course is to improve your knowledge on data structures and algorithms, as well as database systems. To achieve this goal, some basic knowledge of standard data structures and algorithms are required. Mathematical tools and methods, usually taught in the first two years of a bachelor program in computer science, are frequently used in this lecture.

Course type | Lecture |
---|---|

Instructors | Andreas Podelski, Marco Muñiz, Christian Herrera |

Lecture | Monday, 16:00–18:00, Geb. 101 - SR 00-010/14 Wednesday, 16:00–18:00, Geb. 101 - SR 00-010/14 |

Exercise | Every Monday 16:00-17:00, Geb. 101 - SR 00-010/14, starting on the second week of the lecture. |

Language of instruction | English |

Credits | 6 |

Exams | written exam |

## Description

Central topics of this lecture include:

- Introduction to algorithm design and analysis

- Introduction to complexity theory

- Introduction to principles of programming languages

- Introduction to database algorithms

The goal of this course is to improve your knowledge on data structures, algorithms, foundations of programming languages and database systems. To achieve this goal, some basic knowledge of standard data structures and algorithms are required. Mathematical tools and methods, usually taught in the first two years of a bachelor program in computer science, are frequently used in this lecture.

## Formalia

At the beginning of each week, we will hand out an exercise sheet with exercises on material that you will acquire in that week. I.e., the lectures of each week will cover the material that you need in order to be able to solve the exercise sheet that you received at the beginning of the week.

### Exercise submission scheme

- You will have one week to hand in the solutions of the exercises, i.e., the time from the beginning of the week until the monday of the following week. There will be a designated lockbox in building 051 floor 00 which we will empty it at 16h10 sharp. You can also hand in the solutions at the beginning of the exercise group at 16h15.
- You will hand in a signed sheet with the solutions of
**every**exercise sheet. You will hand in whatever you have been able to do, possibly nothing if you were sick. In case you have been sick, you just mark this on your signed solution sheet. - The first hour of the lecture on tuesday is the exercise group. In this exercise group, we will discuss the exercises for which you have just handed in the solutions.
- We will adapt the above scheme where needed (initialization, holidays, ...).

### Admission to final exam

**every**exercise sheet. As said above, you will hand in whatever you have been able to do, possibly nothing if you were sick. In case you have been sick, you just mark this on your signed solution sheet.

### Schedule

Week | Monday | Wednesday |
---|---|---|

1 (23.04 - 28.04) | Lecture | Lecture |

2 (29.04 - 05.05) | Tutorial - Lecture | Lecture |

3 (06.05 - 12.05) | Tutorial - Lecture | Lecture |

4 (13.05 - 19.05) | Tutorial - Lecture | Lecture |

5 (20.05 - 26.05) | Tutorial - Lecture | Lecture |

6 (27.05 - 02.06) | No Lecture (Pfingstpause) | No Lecture (Pfingstpause) |

7 (03.06 - 09.06) | Tutorial - Lecture | Lecture |

8 (10.06 - 16.06) | Tutorial - Lecture | Lecture |

9 (17.06 - 23.06) | Tutorial - Lecture | Lecture |

10 (24.06 - 30.06) | Tutorial - Lecture | Lecture |

11 (01.07 - 07.07) | Tutorial - Lecture | Lecture |

12 (08.07 - 14.07) | Tutorial - Lecture | Lecture |

13 (15.07 - 21.07) | Tutorial - Lecture | Lecture |

14 (22.07 - 28.07) | Tutorial - Lecture | Lecture |

## Resources

### Slides

Title | Slides |
---|---|

01 Algorithms and complexity: introduction | 01_introduction.pdf |

02 Algorithms and complexity: search trees | 02_Search_trees.pdf |

03 Algorithms and complexity: tree traversal analysis | 03_Tree_traversal_analysis.pdf |

04 Algorithms and complexity: balanced trees AVL | 04_balanced_trees_AVL.pdf |

05 Algorithms and complexity: AVL trees delete | 05_AVL_trees_delete.pdf |

06 Algorithms and complexity: hashing | 06_hashing.pdf |

07 Algorithms and complexity: hashing chaining | 07_hashing_chaining.pdf |

08 Algorithms and complexity: hashing open addressing | 08_hashing_open_addressing.pdf |

09 Algorithms and complexity: dynamic tables | 09_dynamic_tables.pdf |

10 Algorithms and complexity: randomized algorithms | 10_randomization.pdf |

11 Algorithms and complexity: text search | 11_text_search.pdf |

12 Algorithms and complexity: edit distance | 12_edit_distance.pdf |

13 Programming languages: basic terms | 13_PLSE_basic_terms.pdf |

14 Programming languages: abstract data types | 14_abstract_data_types.pdf |

15 Programming languages: the word problem | 15_PLSE_word_problem.pdf |

16 Programming languages: satisfiability | 16_PLSE_unification.pdf |

17 Database foundations: introduction | 17_DB_introduction.pdf |

18 Database foundations: relational algebra | 18_DB_relational_algebra.pdf |

19 Database foundations: relational calculus | 19_DB_relational_calculus.pdf |

20 Database foundations: formal design | 20_DB_formal_design.pdf |

### Exercise sheets

Sheet | Submission date |
---|---|

sheet1.pdf | 30.04.12 |

sheet2.pdf | 07.05.12 |

sheet3.pdf | 14.05.12 |

sheet4.pdf | 21.05.12 |

sheet5.pdf | 04.06.12 |

sheet6.pdf | 11.06.12 |

sheet7.pdf | 18.06.12 |

sheet8.pdf | 25.06.12 |

sheet9.pdf | 02.07.12 |

sheet10.pdf | 09.07.12 |

sheet11.pdf | 16.07.12 |

sheet12.pdf | 23.07.12 |

### Final exam date, location and allowed items.

### Curriculum

Master of Science (Applied Computer Science)

### Acknowledgments

This lecture is based on materials developed by Prof. Dr. Th. Ottman, Prof. Dr. P. Thiemann and Prof. Dr. G. Lausen. Prof. Dr. R. Elsässer and Prof. Dr Jan-Georg Smaus. Wolfgang Paulat has provided substantial assistance in the production of the slides.