460-2022/03 – Programming Seminar (SPR)
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 | Czech |
Year of introduction | 2019/2020 | Year of cancellation | |
Intended for the faculties | FEI | Intended for study types | Bachelor |
Subject aims expressed by acquired skills and competences
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
Teaching methods
Seminars
Project work
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.
Compulsory literature:
- 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.
Recommended literature:
- 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.
Way of continuous check of knowledge in the course of semester
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.
E-learning
Other requirements
No additional requirements are placed on the student.
Prerequisities
Subject has no prerequisities.
Co-requisities
Subject has no co-requisities.
Subject syllabus:
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.
Conditions for subject completion
Occurrence in study plans
Occurrence in special blocks
Assessment of instruction