# Subject description - A4B33ALG

Summary of Study | Summary of Branches | All Subject Groups | All Subjects | List of Roles | Explanatory Notes               Instructions
A4B33ALG Algorithms
Roles:P, V Extent of teaching:2P+2C
Department:13133 Language of teaching:CS
Guarantors:  Completion:Z,ZK
Lecturers:  Credits:6
Tutors:  Semester:L

Anotation:

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 affectivity.

Study targets:

Semester project consists from empirical evaluation of searching and sorting algorithms, comparison of iterative and recursive algorithms and debugging of graphical output of selected algorithms of linear algebra and mathematical analysis. Three phases of supervision associated to constituted subtask of project with closing demonstration and defense

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 1

Webpage:

http://cw.felk.cvut.cz/doku.php/courses/a4b33alg/start

Keywords:

Asymptotic complexity, recursive algorithms, binary trees, searching, hashing, sorting, dynamic programming.

Subject is included into these academic programs:

 Program Branch Role Recommended semester BPOI1 Computer Systems P 2 BPOI_BO Common courses P 2 BPOI3 Software Systems P 2 BPOI2 Computer and Information Science P 2 BPKYR1 Robotics V 2 BPKYR_BO Common courses V 2 BPKYR3 Systems and Control V 2 BPKYR2 Sensors and Instrumentation V 2 BPKME1 Communication Technology V 2 BPKME5 Komunikace a elektronika V 2 BPKME_BO Common courses V 2 BPKME4 Network and Information Technology V 2 BPKME3 Applied Electronics V 2 BPKME2 Multimedia Technology V 2 BPEEM1 Applied Electrical Engineering V 2 BPEEM_BO Common courses V 2 BPEEM2 Electrical Engineering and Management V 2 BMI(ECTS) Manager Informatics V 2 BWM(ECTS) Web and Multimedia V 2 BIS(ECTS) Intelligent Systems V 2 BSI(ECTS) Software Engineering V 2

 Page updated 14.6.2021 19:52:31, semester: L/2021-2, L/2020-1, Z,L/2022-3, Z/2021-2, Send comments about the content to the Administrators of the Academic Programs Proposal and Realization: I. Halaška (K336), J. Novák (K336)