1. SylabUZ
2. Wydział Matematyki, Informatyki i Ekonometrii
3. semestr zimowy 2022/2023
4. WMIiE - oferta ERASMUS - Program Erasmus
5. Algorithms and Data Structures

Wygeneruj PDF dla tej strony

Algorithms and Data Structures - opis przedmiotu

Cel przedmiotu

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.

Wymagania wstępne

Zapisz zmiany

Basic knowledge in analysis and linear algebra. Advanced computer operating skills. Skills in computer programming.

Zakres tematyczny

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. 

Metody kształcenia

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.

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. 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.

Literatura podstawowa

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.

 

Literatura uzupełniająca

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.

Uwagi

Zmodyfikowane przez dr Katarzyna Jesse-Józefczyk (ostatnia modyfikacja: 25-04-2022 12:22)