| Course code |
02 53 5182 00 |
| Number of ECTS points |
4 |
| Course title in the language of instruction |
Advanced Algorithms (Zaawansowane algorytmy) |
| Course title in Polish |
Advanced Algorithms (Zaawansowane algorytmy) |
| Course title in English |
Advanced Algorithms (Zaawansowane algorytmy) |
| Language of instruction |
English |
| Form of classes |
|
Lecture |
Tutorials |
Laboratory |
Project |
Seminar |
Other |
Total of teaching hours during semester |
| Contact hours |
15 |
|
45 |
|
|
0 |
60 |
| E-learning |
No |
No |
No |
No |
No |
No |
|
| Assessment criteria (weightage) |
0.35 |
|
0.65 |
|
|
0.00 |
|
|
| Unit running the course |
Instytut Informatyki Stosowanej |
| Course coordinator |
dr hab. Szymon Grabowski |
| Course instructors |
dr inż. Tomasz Jaworski, dr inż. Tomasz Kowalski, dr inż. Robert Susik |
| Prerequisites |
Skills of programming in C or Java/C#, and in Python. |
| Course learning outcomes |
- define fundamental computational models, their advantages and drawbacks, and recognize the cases of their successul application
- analyze selected advanced algorithms and data structures, with respect to their computational complexities
- implement selected advanced algorithms and data structures and discuss the resulting tradeoffs, e.g. space-time ones
- design algorithms for previously unknown problems, using the learned techniques and components
|
| Programme learning outcomes |
|
| Programme content |
Students get acquired with selected advanced algorithmic techniques and advanced data structures. Popular computational models are explained (comparison/decision tree mode, Word-RAM model, I/O model, streaming model, etc.). The topics include, i.a., sorting in the RAM model (radix sort and its variants), the Bloom filter with its variants and applications, compact and compressed data structures (e.g., the sparse suffix array, the FM-index), bit-parallelism, succinct representation of integers and graphs with fast access and selected graph algorithms. |
| Assessment methods |
Ad 1: oral exam.
Ad 2: tutorial test, oral exam.
Ad 3: assessment of lab exercises (implementation of chosen algorithms/data structures), tutorial test, oral exam.
Ad 4: assessment of lab exercises (implementation of chosen algorithms/data structures).
|
| Grading policies |
Oral exam, lab work (including acceptance of small projects), presence at laboratory classes. |
| Course content |
LECTURE:
Computational complexity (definitions and notation -- recalling and extending the knowledge from the basic A&DS course). Computational models. Advanced sorting algorithms. Modern algorithms and data structures based on hashing and their applications. The Bloom filter, its variants and applications. Techniques of bit-parallelism. Succinct data structures, including text indexes (e.g., sparse suffix array, FM-index). Selected graph algorithms (e.g. for the shortest path from a single source).
LABORATORIES:
Students implemented selected algorithms and data structured in a given programming language: either an efficient/compiled language (C/C++, Java, C#) is required for a given problem, or a scripting language (Python). Stress is imposed on the code efficiency, its complience with the theoretical computational complexities, and its flexibility. Relatively simple applications may be required (e.g., a simple text editor, spreadsheet, small database, a problem in bioinformatics). |
| Basic reference materials |
- Dasgupta S., Papadimitriou C.H., Vazirani U.V.: Algorithms, McGraw-Hill Education, 2006. Freely available at authors' URL: http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf
- Cormen T., Leiserson Ch., Rivest R., Stein C.: Introduction to Algorithms, MIT Press, 2009
|
| Other reference materials |
- Knuth D.: The Art of Computer Programming, 3rd Edition, Addison-Wesley, 1997
- Navarro G.: Compact Data Structures. A practical approach, Cambridge University Press, 2016
|
| Average student workload outside classroom |
51 |
| Comments |
|
| Updated on |
2022-02-18 15:08:11 |
| Archival course yes/no |
no |