You are here: Home Teaching Summer Term 2012 Theory I

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 PodelskiMarco 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

Admission criteria for the final exam are the successful participation in the exercises.  We will correct your solutions but we will not grade them.  There will be no 50% rule or such. The formal criterion for evaluating the successful participation in the exercises is that you have handed in a signed sheet with the solutions of 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.

The final exam will take place on the 30.08.2012 in room Kinohörsaal 082 at 14:00 to 15:30.  You are allowed
to bring a non-programmable calculator and an A4 sheet with notes. Here, a Mock exam
 
You can review your final exam on Tuesday the 11.09.12 at 15:00 to 16:00 in building 052, room 00-016.  
 

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.