# 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.

### Written exam : 15.02.2017, 09:30-11:00, HS 5

No auxilary means (except pencil and paper) are allowed.

### Content of the lecture:

• Fundamental terms (algorithm, data structure, data type, abstract data type)
• Basic data structures (stack, queue, linked list, tree)
• Representation of sets (linked list, hash function, binary search tree, AVL tree)
• Representation of polynomials (dense, sparse)
• Sorting algorithms
• Graph algorithms

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.2017)

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

## Exercise 6 (30.11.2017)

Implement the data structure AVL tree with the functions empty, member and insert. Test your functions and output the hight of your constructed tree.

## Exercise 7 (07.12.2017)

Implement the addition and multiplication of two polynomials from Z[x] in dense (or in sparse) representation with the help of linked lists. Test your code by concrete examples.

## Exercise 8 (15.12.2017)

Implement the algorithm MergeSort which transforms an integer array to an ordered array. Test your program with the numbers given in the file sortdaten.txt.

## Exercise 9 (11.01.2018)

Implement the algorithm QuickSort which transforms an integer array to an ordered array. Test your program with the numbers given in the file sortdaten.txt.