1. SylabUZ
2. Faculty of Mathematics, Computer Science and Econometrics
3. winter term 2020/2021
4. Mathematics - Second-cycle studies leading to MS degree
5. Algorithmical Methods

Generate PDF for this page

Algorithmical Methods - course description

Aim of the course

Extensive knowledge of algorithms’ constructing and analysis. The ability to implement typical algorithms in practice and also the skills in adapting and modifying of those in extraordinary situations.

Prerequisites

Save changes

Gaining of competences in computer structured programming. Basic course in algorithms and data structured.

Scope

Lecture
1. NP – complete problems. (2 h)
2. Approximation algorithms. Optimization and decision problems. Optimum and approximate solutions. Absolute performance guarantee and relative performance guarantee of approximation algorithm. Approximation schemes: PTAS, FPTAS. (3 h)
3. Some approximation algorithms. Vertex Cover, Set Cover, Bin Packing, Knapsack, Multiprocessor Scheduling, Graph Coloring, Traveling Salesman. (4 h)
4. Algorithmic methods. Greedy algorithms. Backtracking algorithms. Branch-and-Bound (BB) method. Dynamic programming. Genetic algorithms. Probabilistic algorithms. (6 h)
 

Laboratory
1. Generating random number. Generating random graphs. (2 h)
2. Selected combinatorial algorithms for practical applications (4 h)
3. Approximation algorithms. (8 h)
4. Testing of algorithms that use selected algorithmic methods. (6 h)
5. Probabilistic algorithms. (4 h)
6. Selected algorithms with numbers. (6 h)

Teaching methods

Lecture: problem lecture.
Laboratory: laboratory exercises in computer lab – implementation and testing of selected algorithms.
Each student is supposed to realize three 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 one out of the three projects the students will work in 2-3 person groups. Furthermore the students will test other algorithms.

Learning outcomes and methods of theirs verification

Outcome description	Outcome symbols	Methods of verification	The class form

Assignment conditions

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.

Recommended reading

1. Aho A., Hopcroft J.E., Ullman J.D.: Projektowanie i analiza algorytmów komputerowych, PWN, Warszawa 1983.
2. Błażewicz J. : Złożoność obliczeniowa problemów kombinatorycznych, WNT, Warszawa 1988.
3. Cormen T.H., Leiserson C.E., Rivest R.L., Wprowadzenie do algorytmów, WNT, Warszawa 1997.
4. Vazirani V. V. : Algorytmy aproksymacyjne, WNT, 2004.

Further reading

1. Aho A., Hopcroft J.E., Ullman J.D., : The Design and Analysis of Computer Algorithms.
2. T.H. Cormen, Ch.E. Leiserson, R.L. Rivest: Introduction to Algorithms, MIT Press, 2001.
3. Knuth D.E.: The Art of Computer Programming.
4. Vazarni V. V. : Approximation Algorithms, Springer, 2003.

Notes

Modified by dr Alina Szelecka (last modification: 18-09-2020 13:46)