1. SylabUZ
2. Wydział Matematyki, Informatyki i Ekonometrii
3. semestr zimowy 2022/2023
4. Mathematics - pierwszego stopnia z tyt. licencjata
5. Algorithms and Data Structures

Wygeneruj PDF dla tej strony

Algorithms and Data Structures - opis przedmiotu

Cel przedmiotu

Gaining knowledge and skills in the analysis of algorithms. Knowledge and ability to implement sorting and selection algorithms, search algorithms, basic graph algorithms.

Wymagania wstępne

Zapisz zmiany

Knowledge of the basic analysis and linear algebra course. Basic knowledge of computer programming.

Zakres tematyczny

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)

Metody kształcenia

Lecture: problem lecture.

Laboratory: laboratory exercises in the computer lab - implementation and tests of selected algorithms. Each student has to complete four projects during the semester. In each of the projects the algorithm(s) indicated by the teacher must be implemented and tested. For two of the projects, students will also have to prepare a documentation in accordance with the given specification. Students will work on two of these four projects in groups of 2-3. In addition, during the classes students will write programs that implement various other algorithms.

Efekty uczenia się i metody weryfikacji osiągania efektów uczenia się

Opis efektu	Symbole efektów	Metody weryfikacji	Forma zajęć

Warunki zaliczenia

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. The final grade is issued on the basis of the points obtained during the classes. Points are obtained for: tests, projects and activity during the classes.

 Final course grade. The final grade consists of the laboratory grade (50%) and exam grade (50%). The condition of taking the exam is a positive grade from the laboratory. The condition of passing the subject is a positive grade from the exam.

 

Literatura podstawowa

1. Aho A., Hopcroft J.E., Ullman J.D.: The Design and Analysis of Computer Algorithms, Addison-Wesley Publishing Company, 1974.
2. Cormen T.H., Leiserson C.E., Rivest R.L.: Introduction to Algorithms, MIT Press, 1990.
3. R. Sedgewick, K. Wayne, Algorithms (4th Edition), Addison-Wesley Professional, 2011.

Literatura uzupełniająca

1. M. Weiss, Data Structures and Algorithm Analysis in Java, 3rd Edition, Pearson, 2012.

Uwagi

Zmodyfikowane przez dr Ewa Sylwestrzak-Maślanka (ostatnia modyfikacja: 21-02-2024 13:24)