Skip to content

Latest commit

 

History

History
235 lines (156 loc) · 6.85 KB

11.md

File metadata and controls

235 lines (156 loc) · 6.85 KB
title
Transform and Conquer

Instance Simplification: Transform to simpler instance of same problem.

Example — Presorting an array will make many problems easier (searching, median, uniqueness).

  • This applies also to topological sort and many geometric algorithms.

Representation Change: Different representation of same instance.

Problem Reduction:

More on Presorting

Sorting is important for lots of algorithms, which means the efficiency of the sort is super important.

Factoid — The fastest sorting algorithm in the world is $n \log n$

Example: Searching with presorting

Q: Search for $k$ in $A[0..n-1]$

A:

We can first sort A, and then do a binary search.

$$ \text{Sort} + \text{Binary Search} = n \log n + \log n $$

Example: Element uniqueness

Q: Determine if A[0..n-1] has unique elements.

A:

Sort, then scary array to check pairs of adjacent elements.

$$ \text{Sort} + \text{Check Pairs} = O(n \log n) + O(n) $$

Example: Search (advanced)

Q: Given a set of keys $S$ and a search key$k$, find and occurrence of $k$ in $S$, if any.

Real-World Uses — File size, dynamic of data.

A: ???

Taxonomy of Searching Algorithms

Binary Search Tree

Suppose we implement a dictionary with a BST.

  • Searching: Straightforward
  • Insertion: Search for key, insert where search terminate.
  • Deletion: Three cases
    1. Delete key at leaf (simple)
    2. Delete key at node with single child (easy, just connect child to parent)
    3. Delete key at node with two children (harder)

Recall — Efficiency depends on tree's height.

Efficiency:

  • All 3 operations have worst-case $O(n)$ and avg-case $O(\log n)$

Recall — BST works worst on unbalanced trees. This is problematic if our operations gradually make our tree worse.

Solutions:

  • AVL
  • red-black
  • 2-3
  • 2-3-4
  • ???

Binary Balanced Tree

AVL Trees

AVL Tree: BST in which, for every node, balance factor is at most $1$.

  • Balance Factor: Difference between height of left and right subtrees (left height - right height)

Note — Height of empty tree defined as -1.

Balance Factor Examples:

  • 0 : Both same
  • -1 : Right subtree is heavier
  • 1 : Left subtree is heavier

TODO Drawing of AVL Tree

Rotations

When adding a new node to a BST, we can balance the addition via one of the four rotations.

TODO I don't really get this. Single rotations look normal. Double rotations are apparently two single rotations, but I can't see it, it look like you're just swapping nodes? Arghhhhh.

TODO Drawings and examples of every rotation

TODO Example of constructing an AVL tree from a list (5,6,8,3,2,4,7)

  • When you add a new node, if it causes unbalance, you apply rotation to the nearest unbalanced node (nearest to the new node).

Multiweight Balanced Tree

Multiweight Search Trees

MST is a search tree that allows more than one key in the same node of the tree.

  • Still must follow search key properties.

Lets us overcome some of the issues with binary search trees.

2-3 Tree

Search tree that may have 2-nodes and 3-nodes.

  • Must be height-balanced (all leaves on same level).
  • Constructed by successive insertion of keys given, following rules.

Insertion

  • Add nodes as usual, simply growing 2-nodes to 3-nodes.
  • If you stop at a 3-node, replace it with two 2-nodes, promoting the middle value to be the parent.

Why? — Not as fast, but easier to keep balanced.

  • In, you unbalance a binary tree when you add height to one path significantly more than other possible paths.
  • On 2-3, you can only add height when creating a new root, which adds a unit of height to all paths simultaneously.

Analysis — Search, insertion, and deletion are $\theta (\log n)$

Heaps and Heapsort

Heap: Binary tree with keys at its nodes (one key per node) such that it is essentially complete.

Definition: Essentially Complete: All levels full except possibly last level, where only some rightmost keys may be missing.

Remember — This is a binary tree, [not]{.underline} a binary search tree! The property is parents are bigger than children, so it's ordered top-down, but not left-right.

Important Properties:

  • Root is the largest element.
  • Any subtree is also a heap.
  • Easily represented as array.

Heap as Array

We can represent heaps as arrays by storing elements in level-order.

TODO Drawing

Accesses:

  • Left Child of Node $j$: $2j$
  • Right Child of Node $j$: $2j + 1$
  • Parent of Node: $\lfloor j/2 \rfloor$
  • Parental nodes are in the first half of the array.

Priority Queue

Heaps are really good at representing priority queues.

TODO Definition

Heap Construction

AVL and 2-3 we've done top-down, but heap we can do two methods.

Bottom-Up: Put everything in and then fix it.

Top-Down: Construct by successively inserting elements into an initially empty heap.

Which is Better? — Top-down is more straightforward, especially for inserting a new key; but bottom-up is more efficient.

Bottom-Up

  1. Intiialize structure with keys in order given.
  2. Starting at last (rightmost) parental node, fix the heap rooted at it.
    • If not a heap, keep exchanging it with its largest child until it becomes one.
  3. Repeat previous step for preceding parental node.

TODO Pseudocode

Analysis — Parental node at level $i$ does at most 2(h-i) comparisons. Thus, efficiency of bottom-up construction $\theta(n)$

Top-Down

  1. Insert elemnt at last position in heap.
  2. Compare with parent and exchange if needed.
  3. Continue comparing new element with nodes up the tree.

Analysis — Although it looks more straightforward, efficiency ends up being $\theta(n \log n)$.

Heapsort

Strategy:

  1. Delete root (note the value).
  2. Reconstruct heap so that root is max again.
  3. Do step 1 again.

Algorithm:

  1. Build heap
  2. Remove root (exchange with last (rightmost) leaf.
  3. Fix-up heap (excluding last leaf).
  4. Repeat Steps 2 and 3 until only one node left.

TODO I don't understand how the root removal and fix-up works?

TODO Pseudocode

Analysis — Creation of heap is $\Theta (n)$, root removal portion is $\Theta( n \log n)$, so efficiency class is $\Theta( n \log n)$

Problem Reduction

Solve problem by transforming it into differnt problem for which an algorithm is already available.

Note — To be of practical value, the combined time of the transformation and solving of the reduced problem should be smaller than solving the problem as by another method.

Examples:

  • We could get lcm via gcd.
  • TODO

Least Common Multiple

We know:

$$ lcm(m,n) = \frac{m \times n}{gcd(m,n)} $$

TODO Example of Simple middle school math, 24 and 60.

Thus, we could just use an efficient method like Euclid's algorithm to quickly get LCM.

Counting Paths in a Graph

TODO Something to do with nth power.