Introduction to Algorithms.pdf

CS 146 – Week 8 – Oct 9, 2023 midterm review What to know about Binary Search Trees Randomly built binary search trees (BST) • Expected node depth • Analyzing height Binary Search Tree vs Binary Tree Complete Tree vs Binary Tree Balanced Binary Tree vs Binary Tree Perfect Binary Tree vs Binary Tre...

CS 146 – Week 8 – Oct 9, 2023 midterm review What to know about Binary Search Trees Randomly built binary search trees (BST) • Expected node depth • Analyzing height Binary Search Tree vs Binary Tree Complete Tree vs Binary Tree Balanced Binary Tree vs Binary Tree Perfect Binary Tree vs Binary Tree Know difference between above trees (Oct 2 lecture has details) Inorder vs Preorder vs Postorder Traversal What is height of this valid BST? Zero Is this valid BST? If so what is height? Yes, it is valid. Height is 3. Is this valid BST? If so what is height? NOT valid BST. Valid binary tree, height 4. Is this valid BST? If so what is height? This is a valid tree, but it is not a Binary tree. Height is 2. Is this valid BST? If so what is height? Yes, valid BST. Lousy performance though – worst possible. Instead of O(log n) like for random data, this is O(n) for totally sorted (ascending or desc). This has 7 nodes, height is 6. Valid binary trees, not BSTs. Heights are 3, 2. Perfect Binary Tree A perfect binary tree is a special type of binary tree in which all the leaf nodes are at the same depth, and all non-leaf nodes have two children. In simple terms, this means that all leaf nodes are at the maximum depth of the tree, and the tree is completely filled with no gaps. (NOTE: This is not “sorted”, not a BST) Complete Binary Tree A complete binary tree is a binary tree where nodes are filled in from left to right. In a complete binary tree: Every level except the last one is full. The last level's nodes are as far left as possible. Is this a Balanced Binary Tree? Yes. In a balanced binary tree, the height of the left and right subtree of any node differ by no more than 1. The left subtree has height 1, the right subtree has height 2. Is this a Complete Binary Tree? No. A complete binary tree is a binary tree where nodes are filled in from left to right. In a complete binary tree: Every level except the last one is full. The last level's nodes are as far left as possible. Is this Perfect Binary Tree? Is this Perfect Binary Search Tree? Yes, and Yes This is a BST Inorder vs Preorder vs Postorder • For Inorder, you traverse from the left subtree to the root then to the right subtree. • For Preorder, you traverse from the root to the left subtree then to the right subtree. • For Postorder, you traverse from the left subtree to the right subtree then to the root. • Be able to show tre nodes in al three traversal orders Self-Balancing trees What are AVL Trees? Self-balancing BSTs What are 2-3 Trees? Self-balancing trees (not BSTs) What are 2-3-4 Trees? Self-balancing trees (not BSTs) What are B-trees? Self-balancing BSTs What are red-black trees? Self-balancing BSTs We’ll just cover red-black trees. But know the names of these other self-balancing trees (What are Splay trees? Self-optimizing trees, different idea, not on test) Ω-notation (lower bounds) O-notation is an upper-bound notation. It makes no sense to say f(n) is at least O(n2). Ω(g(n)) = { f(n) : there exist constants c > 0, n0 > 0 such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0 } EXAMPLE: n = Ω(lg n) (c = 1, n0 = 16) Substitution method The most general method: 1. Guess the form of the solution. 2. Verify by induction. 3. Solve for constants. Example of recursion tree Solve T(n) = T(n/4) + T(n/2) + n2: n2 (n/2)2 (n/4)2 (n/8)2 (n/8)2 (n/4)2 5 n2 16 25 n2 256 … (n/16)2 n2 Θ(1) 2 ( ( ) +( ) 2 5 5 1 + 16 + 16 Total = n = Θ(n2) 5 3+ 16 ) geometric series The Master Method The master method applies to recurrences of the form T(n) = a T(n/b) + f (n) , where a ≥ 1, b > 1, and f is asymptotically positive. Three common cases Compare f (n) with nlogba: 1. f (n) = O(nlogba – ε) for some constant ε > 0. • f (n) grows polynomially slower than nlogba (by an nε factor). Solution: T(n) = Θ(nlogba) . Three common cases Compare f (n) with nlogba: 1. f (n) = O(nlogba – ε) for some constant ε > 0. • f (n) grows polynomially slower than nlogba (by an nε factor). Solution: T(n) = Θ(nlogba) . 2. f (n) = Θ(nlogba lgkn) for some constant k ≥ 0. • f (n) and nlogba grow at similar rates. Solution: T(n) = Θ(nlogba lgk+1n) . Three common cases (cont.) Compare f (n) with nlogba: 3. f (n) = Ω(nlogba + ε) for some constant ε > 0. • f (n) grows polynomially faster than nlogba (by an nε factor), and f (n) satisfies the regularity condition that a f (n/b) ≤ c f (n) for some constant c < 1. Solution: T(n) = Θ( f (n)) . Be able to solve recurrences with Master Theorem (or know if it doesn’t apply) Quicksort: Divide and conquer Quicksort an n-element array: 1. Divide: Partition the array into two subarrays around a pivot x such that elements in lower subarray ≤ x ≤ elements in upper subarray. ≤x x ≥x 2. Conquer: Recursively sort the two subarrays. 3. Combine: Trivial. Key: Linear-time partitioning subroutine. Show how Quicksort partitioning examples work Know which sorts are and are not stable Counting sort is a stable sort: it preserves the input order among equal elements. A: 4 1 3 4 3 B: 1 3 3 4 4 Stable sorts: Bucket sort, merge sort, insertion sort, bubble sort, Timsort Unstable sorts: Quicksort, heap sort, selection sort Know operation of radix sorts 329 457 657 839 436 720 355 720 355 436 457 657 329 839 720 329 436 839 355 457 657 329 355 436 457 657 720 839 Quickselect Quicksorting an n-element array: 1. Divide: Partition the array into two subarrays around a pivot x such that elements in lower subarray ≤ x ≤ elements in upper subarray. ≤x 2. 3. 4. 5. x ≥x Do NOT Recursively sort the two subarrays. Ignore one half, recur on the interesting half Then ignore half of that, recur until x == k For example, if k is 10 and x is 8 just want upper half Heaps (Know the 1-based array indexes) 26 24 20 18 17 19 13 12 14 11 1 2 3 4 5 6 Max-heap as a binary tree. 7 8 12 20 17 14 11 10 26 24 18 9 Max-heap as an array. 19 13 Last row filled from left to right. Heap Procedures for Sorting MaxHeapify BuildMaxHeap HeapSort O(lg n) O(n) O(n lg n) Heaps most often used for Priority Queues Asymptotic Notation • O-, Ω-, and Θ-notation Recurrences • Substitution method • Iterating the recurrence • Recursion tree Substitution method The most general method: 1. Guess the form of the solution. 2. Verify by induction. 3. Solve for constants. Find loop Invariants, know where they apply Review: Recursion, Stacks, Queues Question 1: Is it possible to implement a stack using queue(s)? YES https://leetcode.com/problems/implement-stack-usingqueues/description/ How many queues do you guess for natural solution? Answer: 2 Question 2: Is it possible to implement a queue using stack(s)? YES https://leetcode.com/problems/implement-queue-using-stacks/ How many stacks do you guess for natural solution? Answer: 2 Be comfortable coding, identifying, analyzing recursion, understand helper functions too Stacks, Queues Stack - LIFO  Singly linked list without tail reference suffices Queue - FIFO Singly linked list with tail reference suffices Deque  Need doubly linked list Big O Linear search is "on the order of n", which can be written as O(n) to describe the upper bound on the number of operations This is called big O notation Orders of magnitude: O(1) constant (the size of n has no effect) O(n) linear O(log n) logarithmic O(n log n) linear logarithmic O(n2) quadratic O(n3) cubic O(2n) exponential Asymptotic Notation O-notation (upper bounds): We write f(n) = O(g(n)) if there exist constants c > 0, n0 > 0 such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0. EXAMPLE: 2n2 = O(n3) (c = 1, n0 = 2) Substitution Method The most general method: 1. Guess the form of the solution. 2. Verify by induction. 3. Solve for constants. EXAMPLE: T(n) = 4T(n/2) + n • [Assume that T(1) = Θ(1).] • Guess O(n3) . (Prove O and Ω separately.) • Assume that T(k) ≤ ck3 for k < n . • Prove T(n) ≤ cn3 by induction. Assume: Perfect tree of height h has nodes = 2h+1 – 1 Each node of the tree is filled. So total number of nodes can be calculated as 20 + 21 + . . . + 2h = 2h+1 – 1 Can we prove this by induction? Perfect tree of height 0: How many nodes? 1 Perfect tree of height 1: How many nodes? 3 Perfect tree of height 2: How many nodes? 7 Perfect tree of height 3: How many nodes? 15 Assume: Tree of height h has total nodes = 2h+1 – 1 Perfect tree of height 0: How many nodes? 1 20+1 – 1 = 2-1 = 1 Perfect tree of height 1: How many nodes? 3 21+1 – 1 = 4-1 = 3 Perfect tree of height 2: How many nodes? 7 22+1 – 1 = 8-1 = 7 Perfect tree of height 3: How many nodes? 15 23+1 – 1 = 16-1 = 15 This shows examples, then need to show general case, but not quite to level of detail of next page