Algorithms and Data Structures

Wintersemester 2017/2018

Carsten.Schneider@risc.jku.at



First lecture: Thursday   5.10.2017   08:30 - 10:00  room: K 033C (exception: November 30 in 269D)

Algorithms and data structures will be presented that enable one to represent basic mathematical objects with the computer. Ideally, these algorithms/data structures can be combined in order to solve complex mathematical problems.

Content of the lecture:


The lecture follows in parts the books
Datenstrukturen und Algorithmen: Güting
In addition, the following classical books might be useful for further reading:
Algorithmen und Datenstrukturen: Wirth,
The Design and Analysis of Algorithms: Aho, Hopcroft und Ullman.


Any kind of questions are welcome.

Exercises

Meetings: Wednesdays 17:00-18:00 (Oct: S3 048; Nov-Jan: S2 054) or Thursdays 13:45-14:45 (HS 13)
Start: October 11 or October 12

Exercise instructor: Mario Gobrial (k1555470ATstudentsDOTjkuDOTat)

Exercise 0 (05.10.2017) date when the exercise is posed in the lecture

Implement the algorithm contains and the slightly improved version contains2 (terminate if the element is found) in C++. Test your implementation with the numbers stored in IntegerWerte.txt.
How do two algorithms behave with respect to time when you execute them 300000 times with randomly chosen numbers from the file?

Exercise 1 (12.10.2017)

Implement the algorithm contains_3 sketched in the lecture.
Test your implementation taking the data from Exercise 0.

Exercise 2 (19.10.2017)

Implement the data structure stack with the help of an array. Bonus problem: Use your implementatation in order to evaluate arithmetic expressions (it is sufficient that your program can read integers together with the binary operations +, -, *). Demonstrate your code with some examples.

Exercise 3 (09.11.2017)

Implement the algebra List2 with the help of doubled linked lists. Here it is sufficient to implement the functions empty, insert and find.
Produce the list l=<2,4,6,...,100> and execute find(l,50) and find(l,51) to test your function find.

Exercise 4 (16.11.2017)

Implement the Algebra Set with ordered linked lists. It is sufficient to implement the functions empty, insert and intersection. Check your implemented functions with appropriate input tests.

Exercise 5 (23.11.2016)

Implement the data structure binary search tree with the functions empty, member and insert. Check your implemented functions with appropriate input tests.