Algorithm Design and Analysis I

Syllabus

• Algorithmic solvability; time and space complexity; asymptotic notation and growth rates.
• Abstract programming concepts: state space, task vs program, correctness; construction methods and proofs.
• Data abstraction: ADTs and data structures; representation methods (array-based vs linked).
• Core structures: arrays, stacks, queues, priority queues, lists, trees, and typical applications.
• Selection problems: max, simultaneous min/max, k-th smallest in linear time; adversary lower-bound arguments.
• Lower bounds for comparison sorting (worst-case and average-case); classification of sorting methods.
• Sorting by selecting maxima (tournament/heap ideas); one-element-to-place methods; quicksort.
• Sorting trees (binary/ balanced binary sorting trees); insertion sort and Shell sort.
• Exchange sorts and data-independent sorting networks (bubble, heap/pyramid, Batcher networks).
• Mergesort in arrays and as external sorting.
• Searching in associative structures: linear and binary search; search trees; optimal BST; AVL trees; B-trees.