Algorithms and data structures


Aim of the course

Overview of basic algorithms and data structures. Design and analysis of algorithms.

Lecture programme

Introduction to complexity: computational complexity, memory complexity and time complexity (pessimistic, optimistic, expected). Sorting: simple, QuickSort, MergeSort, HeapSort, positional. Selection: Hoare’s algorithm, magic fives. Basic data structures (stack, queue, list, skiplist). Binary trees: AVL, red-black trees, splay trees. Hash tables. Algorithm design and analysis methods: divide-and-conquer, dynamic programming, greedy method. Graph algorithms: DFS, BFS, minimal spanning tree, shortest path.

Overview of the course elements

The exercises are carried out in auditorium. The content of the course consolidates and extends the knowledge gained at the lectures.

Reading list

1. Wprowadzenie do algorytmów, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Wydawnictwa Naukowo - Techniczne, 2004.
2. Algorytmy + struktury danych = programy, Niklaus Wirth, Wydawnictwa Naukowo - Techniczne, 2004.
3. Projektowanie i analiza algorytmów komputerowych, A. Aho, J. Hopcroft, J. Ullman, Helion Wydawnictwo, 2003.

Copyright © 2010 Department of Computer Science   |   AGH University of Science and Technology   |   Created by Creative Bastards