Last day review problems and extra practice.

Amortizing:
   binary counter for arbitrarily large integers:
     operations: 
        add 1
        reset to 0
   Show an individual operation may NOT be O(1)
   Show any combination of operations can be amortizes to O(1)

Hints below...





















   Hints: 
     A:  You cannot assume O(1) addition with arbitrarily long integer.  For instance a given machine may only do 32 bit addition in O(1).  Given the limitations, the simplest thing to imagine is a linked list of single bits.  Assume creating or destroying a node amortizes to O(1) 
     B:  adding 1 can change any number of 1 bits to 0, but always changes exactly one 0 bit to 1.
 
Union-Find:  Do Kruskal with union find, showing ranks, assuming the EARLIER letter in the alphabet becomes the root with a union between two intrees of the same rank. Indicate edges tried, and edges added.

         6     9                 
      A --- B --- F                            
    1/|    /     /|\2
    / |8  /     / | \   11                           
   C  |  /4  12/  |  H --- I       
    \ | /     / 10| /                  
    5\|/     /    |/7                     
      D --- E --- G
         13    3                
                              
recursion/dynamic
  1. Longest increasing subsequence: (done in DasGupta ch 6, second page)  Given numbers a1, a2, ... , an, find the longest strictly increasing subsequence.  For example, given 5, 2, 8, 6, 3, 6, 9, 7,  some increasing subsequences are 5, 6 ,7  and 2, 3, 6, 9, which is one of the the longest ones.
    Dynamic solution.  Illustrate with memoizing


  2. Edit distance An a sequence of single actions you can insert a character, delete a character or replace a character.  What is the minimum number of steps to go from one string to another?   (DasGupta ch6, 4th page)
    Notation:
    '_' in original word means letter from final word inserted,
    '_' in final word means letter from original word deleted,
    corresponding letters either naturally the same, original replaced by final.

 
P-NP
   vertex cover problem:  In a graph G(E, V), Is there a set C of no more than k vertices, such that all other vertices are a neighbor of a member of C?
   Is this problem in NP? Explain.  If it is, give an algorithm that shows it is in NP.

   Partition problem:  given a set of integers C = {c1, c2, ...cn}, can C be partitioned into two subsets, each with the same sum?
   Find a polynomial reduction of the partition problem to the subset sum problem.
   If the subset sum problem is NP complete, does this reduction show the partition problem is NP complete?

   Das Gupta 8.21

B- trees - insert, delete, review property: consistent depth.


Das Gupta 2.19, 2.22 (better algorithm: O(log k))

Das Gupta 5.3, 5.6, 5.7, 5.8, rest of 5.9, 5.11, 5.13, 5.14, 5.15, 5.17
, 5.20,
Das Gupta 6.3, 6.5, 6.6, 6.12, 6.13 (25th page)