SylabUZ
| Course name | Algorithms and Data Structures |
| Course ID | 11.3-WK-MATP-ASD-L-S14_pNadGenGC85Q |
| Faculty | Faculty of Mathematics, Computer Science and Econometrics |
| Field of study | Mathematics |
| Education profile | academic |
| Level of studies | First-cycle studies leading to Bachelor's degree |
| Beginning semester | winter term 2019/2020 |
| Semester | 5 |
| ECTS credits to win | 5 |
| Course type | optional |
| Teaching language | polish |
| Author of syllabus |
|
| The class form | Hours per semester (full-time) | Hours per week (full-time) | Hours per semester (part-time) | Hours per week (part-time) | Form of assignment |
| Laboratory | 30 | 2 | - | - | Credit with grade |
| Lecture | 30 | 2 | - | - | Exam |
The knowledge and skills in basics of analysis of algorithms. The knowledge of and ability to implement sorting and selection algorithms, searching algorithms and elementary graph algorithms. The knowledge of NP-completeness problem and its practical aspects.
Gaining of basic competences in analysis and linear algebra. Advanced computer operating skills. Skills in computer structured programming.
Lecture
1. Algorithms. Computational complexity of algorithms. Correctness of algorithms. Asymptotics. (4 h)
2. Techniques of constructing effective algorithms: divide and conquer , greedy methods, dynamic programming. (2 h)
3. Algorithms of sorting and searching. (4 h)
4. Data structures for dictionaries: characteristic vector, binary search trees, hashing. External searching - B-trees. The union problem for disjoint sets and its applications. (6 h)
5. Graph algorithms: computer representations of graphs, graph searching, minimum spanning trees, shortest paths in graphs, flows in networks. (4 h)
6. Text algorithms: pattern matching, suffix trees. (4 h)
7. Computational geometry: point localization, convex hull, sweeping. (4 h)
8. NP-completeness: the classes P, NP and NP-complete.
Laboratory
1. Determination of the computational complexity of algorithms. (4 h)
2. Testing of the correctness of algorithms. (4 h)
3. Algorithms of sorting and searching. (4 h)
4. Data structures for dictionaries. (6 h)
5. Graph algorithms. (6 h)
6. Text and computational geometry algorithms. (6 h)
Lecture: problem lecture.
Laboratory: laboratory exercises in computer lab – implementation and testing of selected algorithms.
Each student is supposed to realize four projects during the semester. Each project will consist in implementation of the selected algorithm to solve a concrete practical task, writing a program for it, testing it and presenting a documentation in accordance with the assigned specification. On two out of the four projects the students will work in 2-3 person groups. Furthermore the students will write on classes programs implementing other algorithms.
| Outcome description | Outcome symbols | Methods of verification | The class form |
Lecture. Written examination verifying the education outcome in area of knowledge and skills.
Laboratory. Final grade is granted based on number of points received during studies. Points are received for written tests, active participation in classes and completed project.
Final course grade consists of laboratory classes’ grade (50%) and examination grade (50%). Positive grade from laboratory classes is the necessary condition for participation in examination. The positive grade from examination is the necessary condition for course completion.
1. Aho A., Hopcroft J.E., Ullman J.D., : Projektowanie i analiza algorytmów komputerowych, PWN, Warszawa 1983.
2. Banachowski L., Diks K., Rytter W., Algorytmy i struktury danych, WNT, W-wa 1996.
3. Cormen T.H., Leiserson C.E., Rivest R.L., Wprowadzenie do algorytmów, WNT, Warszawa 1997.
1. Aho A., Hopcroft J.E., Ullman J.D., : The Design and Analysis of Computer Algorithms.
2. Aho A., Hopcroft J.E., Ullman J.D., : Data structures and algorithms
3. T.H. Cormen, Ch.E. Leiserson, R.L. Rivest: Introduction to Algorithms, 2001, MIT Press.
4. Knuth D. E. : The Art of Computer Programming.
5. N. Wirth: Algorithms and Data Structured, 1985.
6. Błażewicz J. : Złożoność obliczeniowa problemów kombinatorycznych, WNT, Warszawa 1988.
7. P. Wróblewski: Algorytmy, struktury danych i techniki programowania, wyd. II popr., Helion, 2001.
Modified by dr Robert Dylewski, prof. UZ (last modification: 20-09-2019 09:57)
