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