Syllabus
* Algorithms and their efficiency.
- Algorithm - properties, correctness, efficiency comparison.
- Time and space complexity, asymptotic complexity, Big O notation.
- Worst case, best case and average case analysis.
* Basic algorithms and techniques.
- Divisibility - Euclid's algorithm, prime factorization.
- Prime numbers - primality testing, the sieve of Eratosthenes.
- Decomposing numbers into digits, numeral systems conversion.
- Higher-precision arithmetic ("long numbers").
- Horner's scheme, fast exponentiation.
* Basic data structures.
- Array searching - sequential, binary.
- Abstract data types: stack, queue, priority queue, dictionary.
- Hash tables - principle, resolving collisions.
- Heap. Binary search tree, balancing principle.
* Sorting.
- Internal sorting - direct methods (SelectSort, InsertSort, BubbleSort).
- HeapSort, QuickSort.
- Lower bounds for sorting.
- Sorting in linear time (CountingSort, BucketSort, RadixSort).
- Note about external sorting.
* Recursion.
- Recursion - principle, examples, efficiency.
- Binary tree - representation, searching, applications.
- Representing arithmetic expressions through binary trees.
- Infix, prefix and postfix notations - evaluation, conversion.
- General trees - representation, traversal, applications.
* State space search.
- Backtracking.
- Depth first search (DFS) and breadth first search (BFS) - principle, applications, implementation.
- Improving performace through pruning and heuristics.
- Game tree, minimax, alpha-beta pruning.
* Basic graph algorithms.
- Representation of graphs.
- DFS, BFS and their applications.
* General methods of algorithms design.
- Speeding by precomputation.
- Greedy algorithm.
- Divide and conquer.
- Memoization.
Annotation
An introductory course on fundamental algorithms, algorithmic complexity and data structures for first-year students of computer science and computer science education.