|
Lecturer(s)
|
-
Kohout Josef, Doc. Ing. Ph.D.
|
|
Course content
|
- The evaluation of algorithms, time and memory complexity. Master theorem. - Common redundant, time-consuming operations in the code and their elimination. - The robustness of algorithms, singular cases, and the accuracy of numerical calculations. - Matrix and vector operations (Strassen formula, dot and cross product). Linear and non-linear systems of equations (including overdetermined systems). - Memory management. Memory allocation, deallocation, garbage collector, memory leaks. Too large data sets (they do not fit the memory). - Cache in the current computers and its efficient use (bricking technique) - Divide and Conquer. Binary vs. interpolation search, median. Space partitioning. - Big data processing. Reduction of problem space dimension. Data sampling, Sobolov sequences. Custom SW cache. Compression. Checksums (LUHN, CRC, Adler32, MD5). - Graph representations, Dijkstra and Floyd-Warshall algorithms. - Heuristics approach. State machines, pruning. The problem of optimal assignment - Hungarian marriage.
|
|
Learning activities and teaching methods
|
Interactive lecture, One-to-One tutorial, Seminar classes, Individual study
- Individual project (40)
- 40 hours per semester
- Contact hours
- 26 hours per semester
- Preparation for an examination (30-60)
- 30 hours per semester
|
| prerequisite |
|---|
| Knowledge |
|---|
| describe computer program execution |
| describe the principles of imperative programming, i.e., control flow, methods, etc. |
| be familiar with mathematical concepts at the level of secondary school mathematics |
| Skills |
|---|
| create a computer program in any programming language to solve a simple problem (e.g., deciding whether there are duplicities in an array of numbers) |
| Competences |
|---|
| N/A |
| learning outcomes |
|---|
| Knowledge |
|---|
| assessment of time and memory complexity of both recursive and non-recursive programs |
| basic principles used in the design of the effective algorithms (such as sorting, divide & conquer, space partitioning) |
| basic principles used to increase the effectivity or robustness of concrete implementation (e.g., elimination of constant calculations in loops, data alignment to better fit the cache, data compression, etc.) |
| Skills |
|---|
| design of an algorithm solving a non-trivial problem (such as optimal choice of supermarkets in a city) |
| assess the expected algorithmic complexity of the designed algorithm |
| Competences |
|---|
| N/A |
| teaching methods |
|---|
| Knowledge |
|---|
| Interactive lecture |
| Individual study |
| One-to-One tutorial |
| Seminar classes |
| Skills |
|---|
| Interactive lecture |
| Individual study |
| Competences |
|---|
| Interactive lecture |
| Discussion |
| One-to-One tutorial |
| assessment methods |
|---|
| Knowledge |
|---|
| Written exam |
| Seminar work |
| Skills |
|---|
| Written exam |
| Seminar work |
| Competences |
|---|
| Written exam |
| Seminar work |
|
Recommended literature
|
-
Alsuwaiyel, M. H. Algorithms: Design Techniques and Analysis (Revised Edition). 2016. ISBN 978-981-4723-64-0.
-
Alsuwaiyel, M. H. Algorithms: design techniques and analysis. 1st pub. Singapore : World Scientific, 1999. ISBN 981-02-3740-5.
-
McConnell, Jeffrey. Analysis of algorithms: an active learning approach. Jones & Bartlett Publishers, 2007. ISBN 978-0763707828.
|