Faculty subject Algorithms and Data Structures 1.
notion of algorithm, problem, instance and solution, problem kinds, algorithm description, algorithm trace, design methods, correctness of algorithms
computational resources, models of computation, RAM, asymptotic notation O, Ω, Θ, limits, complexity classes
abstract data type (ADT), set, bag, stack, queue, double-ended queque, priority queue, dictionary, array for implementing ADTs, linked list for implementing ADTs, implicit and explicit data structures
rooted tree, binary and k-ary trees, tree traversals, tree representations (implicit, pointers), heap Array sorting: selection sort, insertion sort, bubble sort, heapsort, mergesort, quicksort, bucket sort, counting sort, radix sort
k-th smallest element, finding minimum and maximum at the same time, quickselect, median of medians
overview, brute force, closest pair of points, substring search, exhaustive search, generating permutations and combinations
backtracking, branch and bound, maze, knights tour, optimization problems, 0/1 knapsack, pruning search tree
analysis of recursive algorithms and recurrence equations, master theorem, closest pair of points
exchanging coins, arranging files to track, scheduling records and tasks, Huffman codding, standard knapsack, k-center problem
graph representation with adjacency lists, adjacency matrix, incidence matrix, depth-first search, breadth-first search, reachability, topological sorting of vertices and cycles, connectivity, strongly connected components
small and big numbers,
arithmetic operations, modular arithmetic,
multiplication of big integers with Karatsuba's
algorithm, matrix multiplication with Strassen's
algorithm, greatest common divisor
Selected topics
Student learns to choose suitable algorithm and data structure for solving computational and algorithmic problems. Additionally, student learns basics of algorithms and data-structures design, checking their correctness, and analyzing their quality.
- abstract and analytical thinking,
- use of algorithms and data structures terminology,
- capability to define and formalize the problem,
- knowledge of selected algorithms,
- knowledge of selected data structures,
- knowledge of selected algorithm design methods,
- solving problems algorithmically,
- evaluation of the solution quality,
- checking correctness of algorithms,
- estimation of algorithm complexity,
- implementation of selected algorithms.
Student learns basic knowledge of methods for quality evaluation of algorithms and data structures. (S)he learns how to analyze problems and then combine solutions into a general solution, and evaluate their quality.