It provides a comprehensive understanding of fundamental concepts, crucial for correct and efficient algorithmic problem-solving. The course covers specification, design, implementation, and computational complexity. It introduces abstract data types recursively and presents techniques for algorithm analysis and design. Additionally, it involves practical exercises, laboratory sessions, and projects where learned tools and techniques are applied, including sequential file handling. Most lessons were adapted from Introduction to Algorithms.
1. Abstract Data Types and Problems
- Abstract Data Types: Such as Sequence, Stack, Queue, Array, Binary Tree, Set, Dictionary.
- Specification: Problem description using abstract types, modularization.
- Recursion: Function axiomatization through recursion, structural induction.
2. Design, Data Structures, and Algorithms
- Design: Concepts, modules, implementation relationship, representation invariant, abstraction function, commutative diagrams.
- Algorithm Complexity: Asymptotic worst-case and average-case analysis, Big O notation, upper and lower bounds.
- Data Structures: Representations for sequences, stacks, and queues; representations for dictionaries/sets: sequences, arrays, pointers, binary trees, binary search trees; advanced representations: balanced trees, AVL trees, open addressing hashing, closed addressing hashing, tries; priority queues: heaps. Searching and sorting in secondary memory. Other data structures for dictionaries.
- Sorting Algorithms: Basic methods: insertion, selection. Elaborate methods: quicksort, mergesort, heapsort. Sorting algorithms for specific inputs.
3. Algorithmic Techniques
- Divide & Conquer
- Function Generalization
- Recursion Elimination: Folding/unfolding; parameter immersion.
- Application of Algorithms and Data Structures to Other Problems