Unit 1: Complexity Analysis LH 4
Computational and Asymptotic Complexity. Big-O Notation. Properties of Big-O Notation Ω and
- Possible Problems. Examples of Complexities. Finding Asymptotic Complexity: Examples. The Best, Average, and Worst Cases 66. Amortized Complexity 69. NP-Completeness 73.
Unit 2: Linked Lists LH 5
Singly Linked Lists: Insertion, Deletion, Search. Doubly Linked Lists: Circular Lists, Skip Lists, Self-Organizing Lists. Sparse Tables. Case Study: A Library.
Unit 3: Stacks and Queues LH 4
Stacks, Queues, Priority Queues. Case Study: Existing a Maze.
Unit 4: Recursion LH 4
Recursive Definitions. Method Calls and Recursion Implementation. Anatomy of a Recursive Call. Tail Recursion. Nontail Recursion. Indirect Recursion. Nested Recursion. Excessive Recursion. Backtracking.
Unit 5: Binary Trees LH 9
Trees, Binary Trees, and Binary Search Trees. Implementing Binary Trees. Searching a Binary Search Tree. Tree Traversal. Breadth-First Traversal. Depth-First Traversal. Insertion, Deletion, Deletion by Merging, Deletion by Copying. Balancing a Tree. The DSW Algorithm. AVL Trees. Self-Adjusting Trees. Self-Restructuring Trees, Splaying. Heaps: Heaps as Priority Queues, Organizing Arrays as Heaps, Polish Notation and Expression Trees. Operations on Expression Trees. Case Study: Computing Word Frequencies 280.
Unit 6: Multiway Trees LH 5
The Family of B-Trees. B-Trees, B*-Trees, B+-Trees. Case Study: Spell Checker
Unit 7: Graphs LH 6
Graph Representation. Graph Traversals, Shortest Paths, All-to-All Shortest Path Problem, Cycle Detection. Spanning Trees. Connectivity. Connectivity in Undirected Graphs, Connectivity in Directed Graphs. Topological Sort, Networks.
Unit 8: Sorting LH 6
Elementary Sorting AlgorithmsInsertion Sort, Selection Sort, Bubble Sort. Efficient Sorting Algorithms: Heap Sort, Quicksort, Mergesort, Radix Sort. Case Study: Adding Polynomials
Unit 9: Hashing LH 5
Hash Functions: Division, Folding, Mid-Square Function, Extraction. Collision Resolution: Open Addressing, Chaining, Bucket Addressing, Deletion. Case Study: Hashing with Buckets.