Algorithms

Vztahy:

Předmět BE5B33ALG nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět B4B33ALG (vztah je symetrický)

Podmínkou zápisu na předmět BE5B33ALG je, že student si nejpozději ve stejném semestru zapsal příslušný počet předmětů ze skupiny BEZBM

Předmět BE5B33ALG může být splněn v zastoupení předmětem B4B33ALG

Garant předmětu:

Daniel Průša

Přednášející:

Robert Pěnička

Cvičící:

Robert Pěnička, Daniel Průša, Martin Zoula

Předmět zajišťuje:

katedra kybernetiky

Anotace:

In the course, the algorithms development is constructed with minimum dependency to programming language; nevertheless the lectures and seminars are based on Python. Basic data types a data structures, basic algorithms, recursive functions, abstract data types, stack, queues, trees, searching, sorting, special application algorithms. Students are able to design and construct non-trivial algorithms and to evaluate their affectivity.

Požadavky:

Programming 1

Osnova přednášek:

1. Order of growth of functions, asymptotic complexity of an algorithm

2. Trees, binary trees, recursion

3. More recursion and backtracking examples

4. Graph, graph representation, basic graph processing

5. Queue, stack, breadth/depth first search

6. Array search, binary search tree

7. AVL trees and B-trees

8. Sorting, Insertion Sort, Selection Sort, Bubble Sort, Quick Sort

9. Sorting, Merge Sort, Heap, Heap Sort, Radix Sort, Counting Sort

10. Dynamic programming, tabulation, longest path in a DAG, optimal matrix multiplication

11. Dynamic programming, longest common subsequence, optimal BST, knapsack problem

12. Complexity of recursive algorithms, Master theorem

13. Hashing, open and chained tables, double hashing, coalesced hashing

14. Reserve

Osnova cvičení:

1. Order of growth of functions, asymptotic complexity of an algorithm

2. Trees, binary trees, recursion

3. More recursion and backtracking examples

4. Graph, graph representation, basic graph processing

5. Queue, stack, breadth/depth first search

6. Array search, binary search tree

7. AVL trees and B-trees

8. Sorting, Insertion Sort, Selection Sort, Bubble Sort, Quick Sort

9. Sorting, Merge Sort, Heap, Heap Sort, Radix Sort, Counting Sort

10. Dynamic programming, tabulation, longest path in a DAG, optimal matrix multiplication

11. Dynamic programming, longest common subsequence, optimal BST, knapsack problem

12. Complexity of recursive algorithms, Master theorem

13. Hashing, open and chained tables, double hashing, coalesced hashing

14. Reserve

Cíle studia:

The course is concerned with the ability to implement effectively solutions of various problems arising in elementary computer science. Main topics of the course include sorting and searching algorithms and related data structures. The course stresses correct algorithms choice and effective implementation as an unique tool for successful problems solving.

Studijní materiály:

[1] Sedgewick, R: Algorithms (Fundamentals, Data structures, Sorting,

Searching), Addison Wesley, 2003

[2] Weiss, M: Data structures and Algorithm Analysis in Java, Addison Wesley, 1999

[3] Keogh, J: Data Structures Demystified, McGraw-Hill, 2004

[4] Wróblevski, P: Algorytmy, Helion, 2003

Poznámka:

Rozsah výuky v kombinované formě studia: 14p+6c

Další informace:

https://cw.fel.cvut.cz/wiki/courses/BE5B33ALG

Rozvrh na zimní semestr 2025/2026:

Rozvrh není připraven

Rozvrh na letní semestr 2025/2026:

Rozvrh není připraven

Předmět je součástí následujících studijních plánů:

• Electrical Engineering and Computer Science (EECS) (povinný předmět programu)
• Electrical Engineering and Computer Science (EECS) (povinně volitelný předmět)