Syllabus
- algorithm, time and space complexity
- divisibility of numbers, Euclid algorithm
- prime number test, Eratosthenes sieve
- decomposition of numbers into digits
- higher precision arithmetic ("long numbers")
- Horner's scheme, positional number systems
- searching algorithms (sequential, binary, breakpoint)
- sorting - direct methods, heapsort, mergesort, quicksort
- complexity of the sorting problem
- bucket sorting
- external sorting
- data representation in memory - memory allocation, garbage collector
- stack, queue, dictionary, heap
- linked list
- recursion - principle, examples, complexity
- binary and general tree
- arithmetic notation - evaluation, conversions
- binary search tree, balancing principle
- hash table
- data representation of graphs
- graph searching, basic graph algorithms
- DFS and BFS in state space
- backtracking acceleration methods - cutting, heuristics
- game programming, minimax algorithm
- Divide and Conquer method
- dynamic programming
Knowledge in the scope of the lecture NMIN111 Programming 1 is expected.
Annotation
The second part of basic course of programming for first-year students of mathematics. The course covers programming in Python, basic algorithms and data structures and practical program design and debugging.
The knowledge of the course NMIN111 Programming 1 is expected.