SylabUZ
| Course name | Algorithms and Data Structures |
| Course ID | 11.3-WK-MATP-ADS-S22 |
| Faculty | Faculty of Exact and Natural Sciences |
| Field of study | WMIiE - oferta ERASMUS |
| Education profile | - |
| Level of studies | Erasmus programme |
| Beginning semester | winter term 2022/2023 |
| Semester | 1 |
| ECTS credits to win | 5 |
| Course type | optional |
| Teaching language | english |
| 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 |
| Lecture | 30 | 2 | - | - | Exam |
| Laboratory | 30 | 2 | - | - | Credit with grade |
Gaining knowledge and skills in basics of analysis of algorithms. Learning how to implement sorting and selection algorithms, searching algorithms and elementary graph algorithms. Getting to know the NP-completeness theory.
Basic knowledge in analysis and linear algebra. Advanced computer operating skills. Skills in computer programming.
Lecture
1. Algorithms. Computational complexity of algorithms. Correctness of algorithms. Asymptotics.
2. Techniques of constructing effective algorithms: divide and conquer , greedy methods, dynamic programming.
3. Sorting and searching algorithms.
4. Data structures for dictionaries: characteristic vector, binary search trees, hashing.
5. Graph algorithms: computer representations of graphs, graph searching, minimum spanning trees, shortest paths in graphs, flows in networks.
6. Text algorithms: pattern matching.
7. NP-completeness: the classes P, NP and NP-complete.
Laboratory
1. Determination of the computational complexity of algorithms.
2. Recursive algorithms.
3. Testing of the correctness of algorithms.
4. Sorting and searching algorithms.
5. Linked data structures. Data structures for dictionaries.
6. Graph algorithms.
7. Text algorithms.
Lecture: problem lecture.
Laboratory: laboratory tasks in computer lab – implementation and testing of selected algorithms.
Each student is supposed to work on four projects during the semester. In each project the student will implement and test the selected algorithms. Moreover, for two projects also a report will be required. On two out of the four projects the students will work in 2-3 person groups. Furthermore the students during the classes will write programs implementing other algorithms.
| Outcome description | Outcome symbols | Methods of verification | The class form |
Lecture. Examination of learning outcomes in terms of knowledge and skills. The exam consists of two parts, written and oral. The condition of joining the oral part is obtaining 30% of points from the written part. Obtaining 50% of the points from the written part guarantees a positive assessment.
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 projects.
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. Cormen T.H., Leiserson C.E., Rivest R.L., Introduction to Algorithms Third Edition, The MIT Press, 2009.
1. Aho A., Hopcroft J.E., Ullman J.D., The Design and Analysis of Computer Algorithms, Addison‐Wesley Publ. Comp., 1974.
1. Wirth N., Algorithms and Data Structured, 1985.
2. Błażewicz J., Złożoność obliczeniowa problemów kombinatorycznych, WNT, Warszawa 1988.
3. Wróblewski P., Algorytmy, struktury danych i techniki programowania, wyd. II popr., Helion, 2001.
4. Banachowski L., Diks K., Rytter W., Algorytmy i struktury danych, WNT, Warszawa 1996.
Modified by dr Katarzyna Jesse-Józefczyk (last modification: 25-04-2022 12:22)
