| Course Unit Code | 460-2022/03 |
|---|
| Number of ECTS Credits Allocated | 4 ECTS credits |
|---|
| Type of Course Unit * | Optional |
|---|
| Level of Course Unit * | First Cycle |
|---|
| Year of Study * | Third Year |
|---|
| Semester when the Course Unit is delivered | Winter Semester |
|---|
| Mode of Delivery | Face-to-face |
|---|
| Language of Instruction | Czech |
|---|
| Prerequisites and Co-Requisites | Course succeeds to compulsory courses of previous semester |
|---|
| Name of Lecturer(s) | Personal ID | Name |
|---|
| SAW75 | doc. Ing. Zdeněk Sawa, Ph.D. |
| Summary |
|---|
The subject is devoted to design, analysis and verification of algorithms with emphasis on finding of efficient algorithms
from the point of view of computational complexity. The aim of the course is to learn different techniques commonly used
in the design of algorithms, such as dynamic programming, greedy algorithms, and some metheds used for a searching in
a state space. The use of these techniques is illustrated on many problems from different areas of computer science. |
| Learning Outcomes of the Course Unit |
|---|
Students will be able to design and implement efficient algorithms for solving different problems, they will be able to analyse computational complexity of algorithms and to use different techniques such as dynamic programming, greedy algorithms and different techniques of searching. Student will know algoritms for solving of some classical combinatorial problems. One of the goals of the seminar is to prepare students for ACM programming contest, so the emphasis will be put on implementation of algorithms in programming languages C/C++ and Java.
- the knowledge of different programming techniques that can be used in design of algoritms
- the ability to analyse computational complexity of algorithms
- the ability to implement algorithms efficiently
|
| Course Contents |
|---|
Lectures:
1. Introduction. Time complexity. Asymptotic notation.
2. Data structures.
3. Recursive algorithms.
4. Greedy algorithms.
5. Dynamic programming.
6. Dynamic programming (cont).
7. Graph algorithms.
8. Graph algorithms (cont.).
9. Number theory.
10. Combinatorics.
11. Games.
12. Permutations and their usage for solving of puzzles.
13. Computational geometry.
Tutorials:
(Remark: The topics of tutorials correspond to the topics of lectures.)
1. Introduction. Time complexity. Asymptotic notation.
2. Data structures.
3. Recursive algorithms.
4. Greedy algorithms.
5. Dynamic programming.
6. Dynamic programming (cont).
7. Graph algorithms.
8. Graph algorithms (cont.).
9. Number theory.
10. Combinatorics.
11. Games.
12. Permutations and their usage for solving of puzzles.
13. Computational geometry. |
| Recommended or Required Reading |
|---|
| Required Reading: |
|---|
- Skiena, S. S., Revilla, M. A.: Programming Challenges: The Programming Contest Training Manual, Springer, 2003.
- Cormen, T. H., Leiserson, R. L., Rivest, R. L., Stein, C.: Introduction to Algorithms, MIT Press 2001.
- Dasgupta, S., Papadimitriou, C., Vazirani, U.: Algorithms, McGraw-Hill, 2006. |
| - Sawa Z.: Seminář z programování - prezentace k předmětu, dostupná na adrese http://www.cs.vsb.cz/sawa/spr/spr.pdf |
| Recommended Reading: |
|---|
- Skiena, S. S.: The Algorithm Design Manual, Springer, 1998.
- Knuth, D. E.: The Art of Computer Programming, Volumes 1-3, (2nd edition), Addison-Wesley Professional, 1998.
- Graham, R. L., Knuth, D. E., Patashnik, O.: Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley Professional, 1994.
- Sedgewick, R.: Algorithms in C (3rd edition), Addison-Wesley Professional, 1997. |
- Skiena, S. S., Revilla, M. A.: Programming Challenges: The Programming Contest Training Manual, Springer, 2003.
- Cormen, T. H., Leiserson, R. L., Rivest, R. L., Stein, C.: Introduction to Algorithms, MIT Press 2001.
- Dasgupta, S., Papadimitriou, C., Vazirani, U.: Algorithms, McGraw-Hill, 2006.
- Skiena, S. S.: The Algorithm Design Manual, Springer, 1998.
- Knuth, D. E.: The Art of Computer Programming, Volumes 1-3, (2nd edition), Addison-Wesley Professional, 1998.
- Graham, R. L., Knuth, D. E., Patashnik, O.: Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley Professional, 1994.
- Sedgewick, R.: Algoritmy v C, SoftPress s.r.o., 2003. |
| Planned learning activities and teaching methods |
|---|
| Seminars, Project work |
| Assesment methods and criteria |
|---|
| Task Title | Task Type | Maximum Number of Points
(Act. for Subtasks) | Minimum Number of Points for Task Passing |
|---|
| Graded credit | Graded credit | 100 | 51 |