Subject description - B4B33ALG
Summary of Study |
Summary of Branches |
All Subject Groups |
All Subjects |
List of Roles |
Explanatory Notes
Instructions
B4B33ALG | Algorithms | ||
---|---|---|---|
Roles: | P, PV | Extent of teaching: | 2P+2C |
Department: | 13133 | Language of teaching: | CS |
Guarantors: | Genyk-Berezovskyj M. | Completion: | Z,ZK |
Lecturers: | Genyk-Berezovskyj M., Průša D. | Credits: | 6 |
Tutors: | Too many persons | Semester: | Z |
Web page:
https://cw.fel.cvut.cz/wiki/courses/B4B33ALGAnotation:
In the course, the algorithms development is constructed with minimum dependency to programming language; nevertheless the lectures and seminars are based on Java. Basic data types a data structures, basic algorithms, recursive functions, abstract data types, stack, queues, trees, searching, sorting, special application algorithms, Dynamic programming. Students are able to design and construct non-trivial algorithms and to evaluate their effectivity.Study targets:
The goal of the course is to learn the ability to implemet various kinds of basic tasks of computer science. Main topics are sorting and searching algorithms and corresponding data stractures for these tasks. The emphasis is given to the algorithmical aspect of the tasks and efectivity of the practical solution.Course outlines:
1. | Order of growth of functions, asymptotic complexity of an algorithm | |
2. | Recursion, recurrence, Master theorem | |
3. | Trees, binary trees, backracking | |
4. | Queue, graph, Depth-first and Breadth-first search in a tree and in a general graph | |
5. | Searching in arrays, binary search trees | |
6. | AVL trees and B-trees | |
7. | Sorting, Insert Sort, SelectionSort, Bubble Sort, QuickSort | |
8. | Sorting, Merge Sort, Halda, Heap Sort | |
9. | Sorting, Radix sort, Counting Sort, Bucket Sort | |
10. | Hashing, open and chained tables, double hashing | |
11. | Hashing, coalesced hashing, universal hashing | |
12. | Dynamic programming, optimal solution structure, memoization, optimal BST | |
13. | Dynamic programming, longest common subsequence, optimal matrich chain multiplication, knapsack problem | |
14. | Sorting multidimensional data, realistic sorting algorithms performance |
Exercises outline:
1. | Introductory test, repeating of the ways of program construction in development environment, examples of functions and procedures, parameters, simple classes, assignment of semester task | |
2. | One-dimensional array processing | |
3. | Sorting and searching in 1D array algorithms | |
4. | Multidimensional array processing algorithms | |
5. | Text and string algorithms | |
6. | Experimentation with space and complexity of algorithms | |
7. | Sequential files | |
8. | Implementation of abstract data types | |
9. | Recursion and iteration | |
10. | Linked lists, linearly-linked list | |
11. | Tree construction, tree search | |
12. | Test, consultation to semester task | |
13. | Algorithms of linear algebra and geometry, mathematical analysis | |
14. | Credit |
Literature:
[1] | T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms, 3rd ed., MIT Press, 2009, | |
[2] | S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani: Algorithms, Mcgraw-Hill Higher Education, 2006, | |
[3] | Robert Sedgewick: Algoritms in v C, parts 1-4, Addison-Wesley Professional; 3rd edition (1997) |
Requirements:
Programming 1Keywords:
Asymptotic complexity, recursive algorithms, binary trees, searching, hashing, sorting, dynamic programming. Subject is included into these academic programs:Program | Branch | Role | Recommended semester |
BPOI1_2016 | Computer and Information Science | P | 3 |
BPOI_BO_2016 | Common courses | P | 3 |
BPOI4_2016 | Computer Games and Graphics | P | 3 |
BPOI3_2016 | Software | P | 3 |
BPOI2_2016 | Internet of Things | P | 3 |
BPBIO_2018 | Common courses | PV | 5 |
BPOI_BO_2018 | Common courses | P | 3 |
BPOI4_2018 | Computer Games and Graphics | P | 3 |
BPOI3_2018 | Software | P | 3 |
BPOI2_2018 | Internet of Things | P | 3 |
BPOI1_2018 | Artificial Intelligence and Computer Science | P | 3 |
Page updated 14.10.2024 17:51:34, semester: Z/2025-6, Z,L/2024-5, L/2023-4, Send comments about the content to the Administrators of the Academic Programs | Proposal and Realization: I. Halaška (K336), J. Novák (K336) |