Algorithm Analysis
Opis przedmiotu/Course description
| Semestr/Semester |
Wykład/Lecture |
Laboratorium/Laboratory |
Ćwiczenia/Class |
Egzamin/Exam |
| 7 |
2 |
-- |
2 |
E |
The course provides both a comprehensive introduction to algorithmics and a thorough discussion of selected advanced topics.
Tematyka/Topics
- The notion of computational complexity
- Sorting
- Basic sorting algorithms
- Quicksort and k-selection
- Bucket sort and radix sort
- Searching
- Linear and binary search
- Binary search trees
- Hashing: open addressing, hashing with chaining, perfect hashing
- Heap and its applications: priority queues, heap sort
- Design of new algorithms
- Divide and conquer
- Greedy approach
- Dynamic programming
- Exhaustive search
- Backtracking and backjumping
- Branch and bound
- Min-max prunning
- Graph algorithms: BFS, DFS, shortest path, minimal spanning tree
- Pattern matching: brute force, KMP, BM
Zaliczenie/Credits and examination method
- The exam consists of two parts: theory and excercises (both written).
Regulamin/Regulations
- The course consists of lectures and classes.
- Classes are obligatory. Two unjustified absences cause lack of attestation.
According to the Regulations of Studies in Silesian Technical University, the fact of absence will be presented
to the Dean.
- In all cases stated neither in these Regulations nor in the Regulations of Studies
at Silesian University of Technology, the lecturer will decide.
Literatura/Bibliography
TBA