|
Lecturer(s)
|
|
|
|
Course content
|
1. Introduction, problem solution design, alternative ways of writing algorithms, time complexity and space complexity 2. Brute-force, back-tracking 3. Divide and conquer 4. Dynamic programming I 5. Dynamic programming II 6. Greedy algorithms and the optimality of a solution 7. Graph algorithms design principles I (Dijkstra, Bellman-Ford, Floyd-Warshall, Kruskal) 8. Graph algorithms design principles II 9. Tree data structures - representation of intervals, prefix-sums and disjoint sets 10. Text processing algorithms - string-matching 11. NP-complete problems, satisfiability of logical circuit, proof of NP-completeness 12. Possible approaches to solving NP-complete problems 13. Solving problems requiring a combination of multiple principles
|
|
Learning activities and teaching methods
|
- unspecified
- 30 hours per semester
- Contact hours
- 52 hours per semester
- Preparation for formative assessments (2-20)
- 12 hours per semester
- Preparation for comprehensive test (10-40)
- 20 hours per semester
- Preparation for an examination (30-60)
- 42 hours per semester
|
| prerequisite |
|---|
| Knowledge |
|---|
| asymptotic complexity |
| fundamental knowledge how basic data structures work (array, heap, stack, queue, linked list, tree) and the complexity of related operations |
| representation of graphs and basic graph search algorithms |
| Skills |
|---|
| basic programming skills |
| recursive function call |
| common use of basic data structures |
| Competences |
|---|
| N/A |
| N/A |
| N/A |
| N/A |
| N/A |
| learning outcomes |
|---|
| Knowledge |
|---|
| general methods for algorithm design |
| principles of algorithms and data structures discussed in the course |
| complexity classes P and NP, NP-completeness, polynomial transformation, solution methods |
| Skills |
|---|
| utilization of general methods for algorithm design |
| analysis of computational complexity |
| the ability to actually program an algorithm |
| the ability to classify an algorithm with respect to the general design methods |
| to recognize NP-complete problems |
| Competences |
|---|
| N/A |
| N/A |
| teaching methods |
|---|
| Knowledge |
|---|
| Lecture with visual aids |
| E-learning |
| Task-based study method |
| Skills demonstration |
| Self-study of literature |
| One-to-One tutorial |
| Discussion |
| Lecture |
| Skills |
|---|
| Lecture |
| Lecture supplemented with a discussion |
| Interactive lecture |
| Task-based study method |
| Skills demonstration |
| One-to-One tutorial |
| Discussion |
| Competences |
|---|
| Lecture |
| Lecture supplemented with a discussion |
| Interactive lecture |
| Task-based study method |
| Skills demonstration |
| One-to-One tutorial |
| Discussion |
| assessment methods |
|---|
| Knowledge |
|---|
| Oral exam |
| Written exam |
| Skills |
|---|
| Written exam |
| Test |
| Continuous assessment |
| Competences |
|---|
| Oral exam |
| Written exam |
| Test |
| Continuous assessment |
|
Recommended literature
|
-
Halim, Steven; Halim, Felix. Competitive programming 3 : the new lower bound of programming contests : handbook for ACM ICPC and IOI contestants. [3.ed.]. [S.l.] : Lulu, 2013.
-
Thomas H. Cormen, Charles E. Leiserson, Ronald R. Rivest and Clifford Stein:. Introduction to Algorithms, 3rd Edition.
|