Gurantor department | Department of Computer Science | Credits | 4 |

Subject guarantor | doc. Ing. Zdeněk Sawa, Ph.D. | Subject version guarantor | doc. Ing. Zdeněk Sawa, Ph.D. |

Study level | undergraduate or graduate | Requirement | Optional |

Year | 3 | Semester | winter |

Study language | English | ||

Year of introduction | 2019/2020 | Year of cancellation | |

Intended for the faculties | FEI | Intended for study types | Bachelor |

Instruction secured by | |||
---|---|---|---|

Login | Name | Tuitor | Teacher giving lectures |

SAW75 | doc. Ing. Zdeněk Sawa, Ph.D. |

Extent of instruction for forms of study | ||
---|---|---|

Form of study | Way of compl. | Extent |

Full-time | Graded credit | 2+2 |

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

Seminars

Project work

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.

- 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.: Algorithms in C (3rd edition), Addison-Wesley Professional, 1997.

To obtain credits, a student must work actively on seminars and solve enough problems to get at least 51 point for solved problems. (Remark: Some point can be also obtained for problems solved in the programming contest CTU Open). By solving the problems the students show their ability to find and implement efficient algorithms.

No additional requirements are placed on the student.

Subject has no prerequisities.

Subject has no co-requisities.

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.

Task name | Type of task | Max. number of points
(act. for subtasks) | Min. number of points |
---|---|---|---|

Graded credit | Graded credit | 100 | 51 |

Show history

Academic year | Programme | Field of study | Spec. | Zaměření | Form | Study language | Tut. centre | Year | W | S | Type of duty | |
---|---|---|---|---|---|---|---|---|---|---|---|---|

2020/2021 | (B0613A140010) Computer Science | P | English | Ostrava | 3 | Optional | study plan | |||||

2020/2021 | (B0541A170009) Computational and Applied Mathematics | P | English | Ostrava | 3 | Optional | study plan | |||||

2019/2020 | (B0613A140010) Computer Science | P | English | Ostrava | 3 | Optional | study plan | |||||

2019/2020 | (B0541A170009) Computational and Applied Mathematics | P | English | Ostrava | 3 | Optional | study plan |

Block name | Academic year | Form of study | Study language | Year | W | S | Type of block | Block owner |
---|