20240110
*******************************************************

Algorithm Analysis Exercises
++++++++++++++++++++++++++++++++++++++++++++

Properties of Growth-rate Functions
1. Ignore lower order terms
   E.g., O( 9N^2 + 800N - 70000000 ) = O( 9N^2 )
2. Ignore the multiplicative constant for the highest order term
   E.g., O( 9N^2 ) = O( N^2 )
3. O( f(n) ) + O( g(n) ) = O( f(n) + g(n) )
   E.g. O( N^2 ) + O( N ) = O( N^2 + N ) = O( N^2 )
4. O( f(n) ) * O( g(n) ) = O( f(n) * g(n) )
   E.g. O( N^2 ) * O( N ) = O( N^2 * N ) = O( N^3 )

Big-Oh:
Determine the Big-Oh of the growth functions below:
5N + 4 = O( N ) Linear
9N^2 + 8N - 7 = O( N^2 )
2 log N = O( log N )
3N log 4N = O( N log N )
6*2^(7N) = O( 2^N )
3N! + 1/2*N^3 = O( N! )
42 = O( 1 )
2*N^3 + 999 * N^2 + 123456789*N = O( N^3 )

Stuck? Plug in some numbers to get a better idea.

Rank the the preceding growth functions in ascending order based on their Big-Oh
Common Growth Rates:
Big-Oh	Names           Examples
O( 1 )  Constant        Any code that doesn't depend on the input size
O( log N ) Logarithmic	
O( N ) Linear           
O( N log N) Linear Logarithmic
O( N^2 ) Quadratic
O( N^3 ) Cubic
O( 2^N ) Exponential
O( N! )	Factorial
 
Discuss with your neighbor(s) the Big-Ohs of Sequential Search and Binary Search
Linear/Sequential search - O( N )
Binary Search - O( log N )


Recursion
=================================
What is a recursive function?  A function that calls itself
Base case: The circumstances/scenario when the recursion stops

Typical structure of a recursive function
~~~~~~~~~~~~~~~~~~~~~~
ReturnType  functionName( parameterList ){

    if( base_case_condition ){
        final_calculations
    }else{
	returnValue = functionName( modifiedParameterList )
    }

    return returnValue
}


Iteration vs. Recursion
~~~~~~~~~~~~~~~~~~~~~~
Overhead / costs:
+ Iterative (looping):
  * increment instruction
  * test instruction
  * jump instruction
+ Recursion (function calls):
  * Copy argument(s) to the stack
  * Update the stack pointer
  * Update the next instruction register
  * Copy the return value (if any)
  * Update stack pointer
  * Update the next instruction register
  
Iterative generally has less overhead
Recursive solution is often a "cleaner" implementation
+ more clear
+ easier to understand
+ easier to maintain
+ simpler / shorter
Sometimes recursion is the only solution


What does the acronym GNU mean?
GNU
Not 
Unix


Divide and Conquer
=================================
1. Discuss with your neighbor(s) the three main parts of a divide and conquer algorithm and the roles of each one.
   Divide: Divide the problem into subproblems
   Conquer: Solve each of the subproblems
   Combine: Pair/incorporate/merge/join the solutions together

2. Name some divide and conquer algorithms.
   Map reduce
   Binary search
   Mergesort
   Quicksort
   Closest pair of points

3. How would determine which two points are the closest together from the following points:
   O( N log N)

   1) Make a list of the points sorted by the x values [O(N log N)]
   2) Make a list of the points sorted by the y values [O(N log N)]
   3) Choose the point with the median x value to divide the space where the closest pair of points is:
      1) Both points have x values < than the median
      2) Both points have x values > than the median
      3) One point has an x value < than the median and the other has an x value > than the median

      Recursively solve 1 & 2
      For #3 Get the minimum from #1 & #2 (d_l and d_r respectively)
          Let sigma = min( d_l, d_r)
	  Iterating through the points sorted by their y-values, we only have to look at the point that are within sigma
   

20240117
*******************************************************


Algorithm Analysis
++++++++++++++++++++++++++++++++++++++++++++
Largest number of inputs (n) that can be computed in 1 second is the algorithm requires O(n^2) and each input can be processed in 1 cycle on a 1 GHz machine.

Cycles duration: 1/1E9 =

         1      1
1/1E9 = ---- = ----
        1E9    1*10^9

Cycles per second = 1*10^9 = 1,000,000,000
n^2 = 1,000,000,000
sqrt(n^2) = sqrt(1,000,000,000)
n = 31622.77660168379332


Heaps
++++++++++++++++++++++++++++++++++++++++++++


Heaps Exercises
=================================
Discuss the following with your neighbor:
-----------
What are the advantages of using a heap data structure?
Minimal overhead

Name several scenarios where a heap is advantageous.
Fast for max/min elements

Name some scenarios where a heap is not advantageous.
Finding something in the middle (or anything that is not the maximum)
Average
Finding a range
min (if a max-heap) / max (if a min-heap)

Are the following heaps valid? If not, do they violate the structure and/or heap-order property?
-----------
Structure property: Complete binary tree
Heap-order property: Value of a node >= value of its children
A.	Yes
B.	No (but it is a min-heap)
C.	No: Heap-order property (3 is a child of 2); Violates structure property
D.	Yes
E.	No: Heap-order property (12 is a child of 8)


Insertions and Deletions
-----------
Draw the resulting heap after inserting 10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13 and 2 into an initially empty binary heap and show its array representation.

    Step 1) Add a new value to the last index in the array (resize if necessary) [structure property]
    Step 2) Bubble (percolate) up [heap order property]

    Array representation of heap:
    -----------
    Index:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
    Value: 
       
    Visual representation of heap (with indices shown)
    -----------
                0
               / \
              /   \
             /     \
            /       \
           /         \
          /           \
         1             2
        / \           / \
       /   \         /   \
      3     4       5     6
     / \   / \     / \   / \
    7   8 9  10   11 12 13 14

Inserting 10:
Index:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
Value: 10

Inserting 12:
Index:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
Value: 12 10

Inserting 1:
Index:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
Value: 12 10  1

Inserting 14:
Index:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
Value: 14 12  1 10

Inserting 6:
Index:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
Value: 14 12  1 10  6

Inserting 5:
Index:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
Value: 14 12  5 10  6  1

Inserting 8:
Index:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
Value: 14 12  8 10  6  1  5

Inserting 15:
Index:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
Value: 15 14  8 12  6  1  5 10

Inserting 3:
Index:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
Value: 15 14  8 12  6  1  5 10  3

Index:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
Value: 15 14 13 12  9  8 11 10  3  6  7  1  4  5  2

Using the heap from the previous question, what does top() return?  15

Using the heap from the previous question, draw the heap and its array after a call to pop().
Step 1) Replace the top value with the item in the last index
Step 2) Bubble (percolate) down
Index:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
Value:  2 14 13 12  9  8 11 10  3  6  7  1  4  5
Value: 14 12 13 10  9  8 11  2  3  6  7  1  4  5

Using the heap from the previous question, what does top() return?  14

Using the heap from the previous question, draw the heap and its array after a call to pop().
Index:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
Value:  5 12 13 10  9  8 11  2  3  6  7  1  4 
Value: 13 12 11 10  9  8  5  2  3  6  7  1  4 

Using the heap from the previous question, what does top() return?  13

Using the heap from the previous question, draw the heap and its array after a call to pop().
Index:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
Value:  4 12 11 10  9  8  5  2  3  6  7  1 
Value: 12 10 11  4  9  8  5  2  3  6  7  1 


What are the following Big-Ohs for Heaps?
-----------
           Average-case  Worst-case
Insertion  O(1)*         O(log n)
Top        O(1)          O(1)
Pop        O(log n)      O(log n)
*2.607 comparisons are needed to get a node in the right place, so 1.607 swaps

                0
               / \
              /   \
             /     \
            /       \
           /         \
          /           \
         1             2
        / \           / \
       /   \         /   \
      3     4       5     6
     / \   / \     /
    7   8 9  10   *

Sorting Algorithms
++++++++++++++++++++++++++++++++++++++++++++

Sorting Exercises
=================================

1. Describe how the algorithm works
   Insertion sort: Iterative insert values into the sorted portion of the array
   Heapsort: Consider an array as a complete binary tree (structure property).  For the heap order property: Start at the bottom and bubble down from each position. Iteratively, swap the value at the top position (the largest value) with the last value.  Bubble down from the root.
   Mergesort: Divide the array in half.  Mergesort the left half.  Mergesort the right half.  Merge the two value.  
   Quicksort: Pick a pivot.  Then, get all of the values < the pivot to the left of the pivot and all of the values >= the pivot to the right of the pivot. Recursively call quicksort on the two partitions. 
   Bucket sort: Put values in the right bucket.  Iterate through all buckets.
   Radix sort: Go through each placeholder/digit, right to left, and sort them by that value/digit.

2. Trace the following algorithms sorting the following array:
        2152 3180  725 1781 1248 4590 2990  633
   by writing the contents of the array according to the specified criterion:
   
   Bubble sort (after each swap)
   2152 3180  725 1781 1248 4590 2990  633
   2152 725  3180 1781 1248 4590 2990  633
   2152 725  1781 3180 1248 4590 2990  633
   2152 725  1781 1248 3180 4590 2990  633
   2152 725  1781 1248 3180 2990 4590  633
   2152 725  1781 1248 3180 2990  633|4590
   725 2152  1781 1248 3180 2990  633|4590
   725 1781  2152 1248 3180 2990  633|4590
   725 1781  1248 2152 3180 2990  633|4590
   725 1781  1248 2152 2990 3180  633|4590
   725 1781  1248 2152 2990  633|3180 4590
   725 1248  1781 2152 2990  633|3180 4590
   725 1248  1781 2152  633|2990 3180 4590
   725 1248  1781  633|2152 2990 3180 4590
   725 1248   633|1781 2152 2990 3180 4590
   725  633 |1248 1781 2152 2990 3180 4590
   633| 725  1248 1781 2152 2990 3180 4590


20240124
*******************************************************

   Insertion sort (at the end of each iteration of the outer loop)
   2152 3180  725 1781 1248 4590 2990  633
   2152 3180| 725 1781 1248 4590 2990  633
    725 2152 3180|1781 1248 4590 2990  633
    725 1781 2152 3180|1248 4590 2990  633
    725 1248 1781 2152 3180|4590 2990  633
    725 1248 1781 2152 3180 4590|2990  633
    725 1248 1781 2152 2990 3180 4590| 633
    633  725 1248 1781 2152 2990 3180 4590|


   Heapsort (at the end of each iteration of each loop)
      0    1    2    3    4    5    6    7
   2152 3180  725 1781 1248 4590 2990  633
   2152 3180  725 1781 1248 4590 2990  633 (heapify, i=3)
   2152 3180 4590 1781 1248  725 2990  633 (heapify, i=2)
   2152 3180 4590 1781 1248  725 2990  633 (heapify, i=1)
   4590 3180 2990 1781 1248  725 2152  633 (heapify, i=0)
   3180 1781 2990  633 1248  725 2152|4590 (i=7)
   2990 1781 2152  633 1248  725|3180 4590 (i=6)
   2152 1781  633 1248  725|2990 3180 4590 (i=5)
   1781  633 1248  725|2152 2990 3180 4590 (i=4)
   1248  633  725|1781 2152 2990 3180 4590 (i=3)
    725  633|1248 1781 2152 2990 3180 4590 (i=2)
    633| 725 1248 1781 2152 2990 3180 4590 (i=1)


   Mergesort (at the end of each merge)
   2152 3180  725 1781 1248 4590 2990  633
   2152 3180 -    -    -    -    -    -
   -    -     725 1781 -    -    -    -
    725 1781 2152 3180
   -    -    -    -    1248 4590 -    -
   -    -    -    -    -    -     633 2990
   -    -    -    -     633 1248 2990 4590
    633  725 1248 1781 2152 2990 3180 4590


   Quicksort (after each swap, including swapping the same element in the same place and the swap for the pivot)
   + Choose a pivot (median of three)
   + Partition: get all of the values less than the pivot, to the left of the pivot and all values greater than the pivot to the right of the pivot
   + Recursively, call quicksort on the left partition and right partition
   
      0     1      2     3     4     5     6     7
   2152  3180    725  1781  1248  4590  2990   633
   1248  3180    725  1781  2152  4590  2990   633 (Pivot chosen from median of three values)
   1248   725:  3180 |1781  2152  4590  2990   633
   1248   725:  3180  1781 |2152  4590  2990   633
   1248   725:  3180  1781  2152 |4590  2990   633
   1248   725:  3180  1781  2152  4590| 2990   633
   1248   725:  3180  1781  2152  4590  2990 | 633
   1248   725    633: 1781  2152  4590  2990  3180|
    633   725   1248  1781  2152  4590  2990  3180
    633:  725   -     -     -     -     -     -
    633:  725|  -     -     -     -     -     -
    633   725   -     -     -     -     -     -
   -     -      -     3180:|2152  4590  2990  1781
   -     -      -     3180  2152:|4590  2990  1781
   -     -      -     3180  2152: 4590 |2990  1781
   -     -      -     3180  2152  2990: 4590 |1781
   -     -      -     3180  2152  2990  1781: 4590|
   -     -      -     1781  2152  2990  3180  4590
   -     -      -     2152  1781  2990  3180  4590
   -     -      -     2152  1781: 2990| -     -
   -     -      -     1781  2152  2990  -     -
   -     -      -     -     2152  -     -     -
   -     -      -     -     -     2990  -     - 
   -     -      -     -     -     -     -     4590

   Bucket sort (show the buckets)
   Index  Present or not
       0  0
     ...  0
     633  1  
     ...  0
     725  1       
     ...  0
    1248  1
     ...  0
    1781  1
     ...  0
    2152  1
     ...  0
    2990  1
     ...  0
    3180  1    
     ...  0
    4590  1    

   Radix sort (at the end of each iteration)
   (shown vertically instead of horizontally)
      v    v   v   v
   2152  3180 0725 2152 0633
   3180	 4590 0633 3180	0725
   0725	 2990 1248 1248	1248
   1781	 1781 2152 4590	1781
   1248	 2152 3180 0633	2152
   4590	 0633 1781 0725	2990
   2990	 0725 4590 1781	3180
   0633  1248 2990 2990	4590


3. Write down the following properties for the stated sorting algorithms:
                Average-case  Worst-case             Extra  Distinguishing   
                Running Time  Running Time  Stable?  Space  Features
                ------------  ------------  -------  -----  ---------------
Bubble sort     O(n^2)        O(n^2)        Y        O(1)   Adaptive, simple
Insertion Sort  O(n^2)        O(n^2)        Y        O(1)   Adaptive, simple
Heapsort        O(n log n)    O(n log n)    N        O(1)   Not adaptive    
Mergesort       O(n log n)    O(n log n)    Yes      O(n)   Best case is also O(n log n), so not adaptive    
Quicksort       O(n log n)    O(n^2)        No       O(1)*  Most commonly used
Bucket sort     O(n)          O(n)          Y        O(n)    
Radix sort      O(d(n+k))     O(d(n+k))     Y        O(n)
* and the stack, with is O(n)
d = make # of digits
k = # of possible values

Stacks and Queues Exercises
++++++++++++++++++++++++++++++++++++++++++++

For the following data structures:
  Stack
    Use PUSH() for INSERT()
    Use POP() for DELETE()
  Queue
    Use ENQUEUE() for INSERT()
    Use DEQUEUE() for DELETE()
show the array elements after each of the following operations:
  INSERT( 1 )
  INSERT( 2 )
  DELETE()
  INSERT( 3 )
  DELETE()
  DELETE()

Stack         Queue	    
-----------   ----------- 
INSERT( 1 )   INSERT( 1 ) 
1             1
INSERT( 2 )   INSERT( 2 ) 
1 2           1 2
DELETE()      DELETE()    
1               2
INSERT( 3 )   INSERT( 3 ) 
1 3             2 3
DELETE()      DELETE()    
1                 3
DELETE()      DELETE()



20240131
*******************************************************

Linked Lists Exercises
++++++++++++++++++++++++++++++++++++++++++++

1. Inserting and Removing from a Linked List

   A. Make a (traditional) linked list with the following instructions and draw the resulting linked list with nodes like:

      +------------+
      | element    |
      | next       |
      +------------+


      Insert 5

      head
       |
       v
      +------------+
      | element: 5 |
      | next: null |
      +------------+
      
      Insert 3

      O( n )
      head
       |
       v
      +------------+  +------------+
      | element: 5 |  | element: 3 |
      | next: -----+->| next: null |
      +------------+  +------------+

      O( 1 )
      Steps:
      1) Create a new node/link
      2) Set the element's value to the new value
      3) Set the new node/link's next value to head's current value
      4) Update head to new node/link
      
      head
       |
       v
      +------------+  +------------+
      | element: 3 |  | element: 5 |
      | next: -----+->| next: null |
      +------------+  +------------+
      
      Insert 9
      head
       |
       v
      +------------+  +------------+  +------------+
      | element: 9 |  | element: 3 |  | element: 5 |
      | next: -----+->| next: -----+->| next: null |
      +------------+  +------------+  +------------+
      
      Insert 7
      head
       |
       v
      +------------+  +------------+  +------------+  +------------+
      | element: 7 |  | element: 9 |  | element: 3 |  | element: 5 |
      | next: -----+->| next: -----+->| next: -----+->| next: null |
      +------------+  +------------+  +------------+  +------------+
      
      Remove 9
      Steps:
      1) Start at the link that is referenced by head
      2) While not null
      3) Check the element if it matches the key
      4) If it matches,
         1) Set the previous node's next to node to remove's next
      
      head
       |
       v
      +------------+  +------------+  +------------+
      | element: 7 |  | element: 3 |  | element: 5 |
      | next: -----+->| next: -----+->| next: null |
      +------------+  +------------+  +------------+
      
      Remove 5
      head
       |
       v
      +------------+  +------------+
      | element: 7 |  | element: 3 |
      | next: -----+->| next: null |
      +------------+  +------------+
      
      Remove 7
      head
       |
       v
      +------------+
      | element: 3 |
      | next: null |
      +------------+
      
      Remove 3
      head
       |
       v
      null

      Remove 5
      head
       |
       v
      null

   B. Enumerate the steps taken to build the linked list by labeling each of the actions with a consecutive number
         

2. What are the "special cases" or scenarios to test for for each operation (for adding, retrieving or deleting an item)?
   A. Empty list
   B. Single element
   C. Beginning of the a list (of 1+ nodes)
   D. Tail of the list
   E. Middle of the list


Binary Search Trees Exercises
++++++++++++++++++++++++++++++++++++++++++++

Binary Search Tree (BST)
=================================
3 properties of each node n:
1) n's value >  all values in the left  subtree (T_l)
2) n's value <= all values in the right subtree (T_r)
3) T_l and T_r are BST

1. Draw the resulting Binary Search Tree after inserting the following strings (in the order provided):
   BS,  AVL,  TT,   TTF,   RB,  Splay


   Inserting BS
   root
    |
    v
   +-------------+
   | key: BS     |
   | left: null  |
   | right: null |
   +-------------+

   Insert AVL
     BS
    /
   AVL
   
   Insert TT
     BS
    /  \
   AVL  TT
   
   Insert TTF
     BS
    /  \
   AVL  TT
          \
          TTF
   
   Insert RB
     BS
    /  \
   AVL  TT
       /  \
      RB  TTF
   
   Insert Splay
     BS
    /  \
   AVL  TT
       /  \
      RB  TTF
       \
       Splay
       
2. Given the following Binary Search Tree, draw the resulting Binary Search Tree after removing B, then E.

       B
      / \
     /   \
    /     \ 
   A       E
          / \
         /   \
        C     F
         \
          D


   Remove B:
       C
      / \
     /   \
    /     \ 
   A       E
          / \
         /   \
        D     F
	
   Remove E:
       C
      / \
     /   \
    /     \ 
   A       F
          /
         /
        D


3. Draw the resulting Binary Search Tree after inserting the following strings (in the order provided):
   AVL,  BS,   RB,  Splay,  TT, TTF

   AVL
     \
     BS
       \
       RB
         \
         Splay
	   \
	   TT
	     \
	     TTF
	 

4. Write in the Big-Oh for the following operations on a Binary Search Tree.
              Average Case  Worst Case  
              ------------  ----------
   Retrieval  O( log n )*   O( n )
   Insertion  O( log n )*   O( n )
   Deletion   O( log n )*   O( n )
   Traversal  O( n )        O( n )
   *height of the tree


Hash Table Exercises
++++++++++++++++++++++++++++++++++++++++++++

Hash Table Basics
=================================
1. Describe how hash tables work (including what is the underlying data structure and what is a hash function)

   Data structure: an array
   Hash function: Hashes the input (a key) to determine the location to start to look in the hash table for the key


20240207
#############################################################################

3. What are the requirements for a good hash function?

   1) Fast (and easy) to compute (O(1))
   2) Minimize mapping to the same location (evenly distribute items throughout the hash table)
   3) Involves the entire search key
   4) Uses a prime base, if it uses modulo arithmetic

Default hash function (Table size of 10007);
  h(x) = x % 10007
  h(23) = 23
  h( 10006 ) = 10006
  h( 10007 ) = 0
  h( 10008 ) = 1
  h( 10009 ) = 2
  h( 10030 ) = 23

2. What would the hash function look like if a string is used as the key?

   E.g.: "Hi, Mom!"
   First, convert the string to a (single) number, then modulo arithmetic
   

4. Identify multiple scenarios when it is appropriate to use a hash table

   A compiler identifying keywords or looking up identifiers
   Password verification
   Pattern matching in strings (including plagiarism detection)
   Determine if two arrays contain the same contents (potentially in different orders)
   Histograms (include word frequencies)

   Not ideal for:
   Min, max or range
   

Handling Collisions
=================================
1. Using the following strategies, and given a hash table with 7 entries, draw the hash table and it's contents after inserting the following keys: 7, 11, 71, 42, 13, 49:

   h(x) = x % 7

   A. Separate chaining
      0: 49 -> 42 -> 7
      1: 71
      2: 
      3: 
      4: 11
      5: 
      6: 13
   
   B. Linear probing
      0: 7
      1: 71
      2: 42
      3: 49
      4: 11
      5: 
      6: 13

      Remove 71:
      0: 7
      1: Tombstone
      2: 42
      3: 49
      4: 11
      5: 
      6: 13

      Retrieve 49:
      0: 7
      1: Tombstone
      2: 42
      3: 49
      4: 11
      5: 
      6: 13


   C. Quadratic probing
      0: 7
      1: 71
      2: 42
      3: 
      4: 11
      5: 
      6: 13

      f(i) = i^2
      h(42) = h(x) + f(i) % tableSize
            = 0 + 0 % 7 = 0 (i = 0)
            = 0 + 1^2 % 7 = 1 (i = 1)
            = 0 + 2^2 % 7 = 4 (i = 2)
            = 0 + 3^2 % 7 = 2 (i = 3)

      h(49) = h(x) + f(i) % tableSize
            = 0 + 0 % 7 = 0 (i = 0)
            = 0 + 1^2 % 7 = 1 (i = 1)
            = 0 + 2^2 % 7 = 4 (i = 2)
            = 0 + 3^2 % 7 = 2 (i = 3)
            = 0 + 4^2 % 7 = 2 (i = 3)
            = 0 + 5^2 % 7 = 4 (i = 3)
            = 0 + 6^2 % 7 = 1 (i = 3)
	    ...
	    = 0 + 500^2 % 7 (collision still)

   D. Double hashing
      0: 7
      1: 71
      2: 49
      3: 42
      4: 11
      5: 
      6: 13

      f(i) = i * h_2(x)
      h_2(x) = R - (x % R) (where R is the prime number just smaller than tableSize)
      h_2(42) = 5 - (42 % 5) = 3
      
      h(42) = h(x) + f(i) % 7
            = 0 + i*3 % 7 = 0 (i=0)
            = 0 + i*3 % 7 = 3 (i=1)
	    
      h_2(49) = 5 - (49 % 5) = 1 // during lecture was erroneously calculated as 4
      
      h(49) = h(x) + f(i) % 7
            = 0 + i*1 % 7 = 0 (i=0)// updated f(i) after the lecture
            = 0 + i*1 % 7 = 1 (i=1)// updated f(i) after the lecture
            = 0 + i*1 % 7 = 2 (i=2)// updated f(i) after the lecture
      
	    
2. Calculate the load factor α for each of the previous strategies in the example above.
   load factor α = # items / hash table size
                 = 6 / 7


Rehashing
=================================
1. What is rehashing and what are the major steps of rehashing?

   Increasing the hash table size
   Create a new hash table with a tableSize that is the next prime starting larger than twice the previous tableSize 
   Each item needs to be re-hashed into the new hash table

2. Why do we rehash?

   To avoid collisions
   

3. When do we rehash?

   Collision rate is too high
   Separate Chaining: α > ~1
   Linear probing: α > ~1/2
   Quadratic probing: α > ~2/3


Hashing Efficiency
=================================
1. Discuss the advantages and disadvantages of the following implementations for hash tables (use efficiency as evidence to support your claims):
   A. Separate chaining
      Advantages: Simple, less rehashing and/or more insertions for a given table size
      Average case efficiency (inserting and searching): O( 1 )
      Worst case efficiency (inserting and searching): O(1) + O(n) (we had to rehash before inserting)
      
   B. Linear probing
      Better cache performance (because we're analyzing neighboring location) than quadratic or double hashing, but subject to clustering
      Average case efficiency (inserting and searching): O( 1 )
      Worst case efficiency (inserting and searching): O(1) + O(n) (we had to rehash before inserting)
      
   C. Quadratic probing
      Disadvantage: Subject to secondary clustering 
      Average case efficiency (inserting and searching): O( 1 )
      Worst case efficiency (inserting and searching): O(1) + O(n) (we had to rehash before inserting)
      
   D. Double hashing
      Poor cache performance, but virtually no clustering
      Average case efficiency (inserting and searching): O( 1 )
      Worst case efficiency (inserting and searching): O(1) + O(n) (we had to rehash before inserting)

Misc
=================================
Need to be careful about the constants in hash function (to avoid various issues like collisions, not cycling through all of the slot for open addressing, etc.)


20240214
*******************************************************
Greedy Algorithms Exercises
++++++++++++++++++++++++++++++++++++++++++++

1. Discuss with your neighbor:
   A. How a greedy algorithm works
      A way to optimize to get to the solution
      Each decision is made by choosing the currently best-looking path/choice
      or
      Greedy algorithms make decisions to maximally improve their current state, not necessarily with regard to the global maximum
      
   B. How they differ from a dynamic programming algorithms
      Dynamic programming algorithms explore all possibilities and determine the best solution
      Greedy algorithms (typically) only explore a subset of a problem

   C. Give some examples of greedy algorithms
      "Myself"
      Making change
      Activity selection
      (fractional) Knapsack
      Distance calculations
      Huffman encoding (trees)
      Packing problem

      Any problem can have a greedy algorithm to provide at least an approximation of the optimum

   D. Is earning a Master's degree a step in a greedy algorithm?

      Student's Responses:
      Yes - optimal for getting/changing a job

   
2. Discuss with your neighbor:
   A. What are the conditions so that a greedy algorithm yields the optimal solution
      Greedy-choice property: Each locally optimal choice leads to the globally optimum solution.
      Optimal substructure property: "An optimal solution to the problem contains within it optimal solutions to subproblems" (CLRS, p379)
      
   B. Can we still use a greedy algorithm that doesn't always provide the optimal solution?
   
3. What are the steps to developing a greedy algorithm?
   (Note: Assumes the greedy-choice property)
   1. Redefine the optimization problem so that each choice we're left with one subproblem to solve
   2. Prove that making the greedy choice is always an optimal solution
   3. Show that the optimal subproblem property applies

4. What is the activity selection problem and what is a greedy solution to it?
   Maximize the number of activities that require a single resource
   Greedy solution:
       Sort the activities by their completion times
       Choose the activity with the earliest completion time
       Iteratively choose the activity (from the sort list) that starts after the current activity

   Dynamic Programming solution:
       For each activity, look at each sub problem that is not mutually exclusive with that activity


5. What is the (fractional) knapsack problem? Does a greedy algorithm provide the optimal solution?
   Maximize the "worth" of the items fit in to a knapsack, where there's a limit to the number of items in or the total weight of the items in the knapsack.
   For 0-1 knapsack: dynamic programming for the optimal solution
   For fractional knapsack: greedy algorithm will provide an optimal solution


6. Discuss with your neighbor(s) how Huffman Codes are calculated. Be sure to include in your discussion:
   Why they are used: File compression
   Why the algorithm is greedy?
     1. Assign each character to a node (making each on their own tree).  Assign the frequency of the character as a weight
     2. Combine the 2 trees with the smallest weights as children into a new tree.
        Assign the weight of the new tree to the sum of the weight of its children
     3. Repeat step 2 until all trees are combined


Here are the most common characters in the King James Version of the Bible (ignoring case):
Character	Count	Code	Total Bits
(space)	745,903
e	411,755
t	317,486
h	283,478
a	276,021
o	242,007
n	224,235
i	193,035
s	189,502
Subtotal	2,883,422

Sort by frequency:
189,502	s	
193,035	i	
224,235	n	
242,007	o	
276,021	a	
283,478	h	
317,486	t	
411,755	e	
745,903 (space)	

Combine 2 least frequent
382537 (si)
 / \
s   i

224,235	n	
242,007	o	
276,021	a	
283,478	h	
317,486	t	
411,755	e	
745,903 (space)	

Next two smallest:
382537 (si)
 / \
s   i

466242	(no)
 / \
n   0

276,021	a	
283,478	h	
317,486	t	
411,755	e	
745,903 (space)

Next two smallest:
382537 (si)
 / \
s   i

466242	(no)
 / \
n   0

559499	(ah)
 / \
a   h

317,486	t	
411,755	e	
745,903 (space)	

Next two smallest:
700023	(t-si)
   /
 (si)
 / \
s   i

466242	(no)
 / \
n   0

559499	(ah)
 / \
a   h

411,755	e	
745,903 (space)	

Next two smallest:
700023	(t-si)
   / \
 (si) t
 / \
s   i

877997 (e-no)
  /  \
(no)  e
 / \
n   0

559499	(ah)
 / \
a   h

745,903 (space)	

Next two smallest:
1259522 ah-t-si
     /   \
  (t-si)  (ah)
   / \     / \
 (si) t   a   h
 / \
s   i

877997 (e-no)
  /  \
(no)  e
 / \
n   0

745,903 (space)	

Next two smallest:
1259522 ah-t-si
     /   \
  (t-si)  (ah)
   / \     / \
 (si) t   a   h
 / \
s   i

1623900 (e-no-space)
   /     \
 (e-no)   (space)
  /  \
(no)  e
 / \
n   0

Next two smallest:

         2883422 (all)
       /0             \1
    ah-t-si        (e-no-space)     
     /0  \1	     /0     \1	  
  (t-si)  (ah)	   (e-no)   (space) 
   /0 \1  /0 \1	    /0 \1		  
 (si) t   a   h	  (no)  e		  
 /0 \1		   /0 \1		  
s   i		  n   o		  




What are the codes that produce the minimum total bits (and what is the minimum total bits)? What is the total number of bits by assigning each character a 4-bit code?
  code    Total bits
s 0000    4 (the length of "0000") * 189,502 (# of counts for s) = 758,008
i 0001
t 001
a 010
h 011
n 1000
o 1001
e 101
space 11  2 * 745,903 = 1,491,806

8. Given the following jobs and their required execution times, in what order should they run to minimize the average time to completion?
What algorithm did you use to schedule the jobs?
  Job  	  j1  	  j2  	  j3  	  j4  
  Time  	  7  	  8  	  2  	  1

 Greedy (optimal) solution: Choose the job with the shortest time remaining: j4, j3, j1, j2


Given the following jobs and their required execution times, in what order should they run to minimize the average time to completion if they're allowed to run on 4 cores?
What algorithm did you use to schedule the jobs?
  Job  	  j1  	  j2  	  j3  	  j4  	  j5  	  j6  	  j7  	  j8  	  j9  	  j10  	  j11  
  Time  	  7  	  8  	  2  	  1  	  9  	  8  	  4  	  5  	  1  	  7  	  2  

9. You've been hired by an international web-ordering company, Nile, to design an algorithm to fit their various-sized products into boxes. Lucky for you, there's only box size. What algorithm are you going to use to determine which product goes into which box? Will it produce the optimal (minimum) number of boxes?


20240221
*******************************************************

Graphs Exercises
++++++++++++++++++++++++++++++++++++++++++++

What other graphs appear in your life?
https://archive.nytimes.com/bits.blogs.nytimes.com/2013/10/28/spotting-romantic-relationships-on-facebook/


1. Identify as many of the graph terms as you can that apply to the following graph:
graph - a graph G is a collection of two sets: V, a set of vertices and E, a set of edges that connect the vertices
directed graph or digraph - {v1, v2} - graph in which each edge is associated with an ordered pair of vertices
adjacent - a vertex v1 in a digraph G is adjacent to v2 if there is a directed edge from vertex v1 to vertex v2
path - sequence of vertices v1, v2, v3,...vn where there is an edge from vi to vi+1
simple path - path in which all vertices are distinct
cycle - a path in which first and last vertices are the same
simple cycle - a cycle that begins and ends at the same vertex and does not pass through other vertices more than once
weakly connected - there is a path from vertex I to vertex J or from vertex J to vertex I
outdegree of a vertex - number of edges extending from the vertex (digraph)
indegree of a vertex - number of edges entering a vertex (digraph)
weighted graph - graph in which the edges represent numeric values
directed path - sequence of directed edges between two vertices
network - graph in which each edge has an associated positive numerical weight

Implementing Graphs
=================================
Options:
1) Adjacency list
2) Adjacency matrix


2.  Given the above graph, draw the resulting:

Adjacency list
~~~~~~~~~~~~~~~~~~~~~~
Array of linked lists

+---+
| A | -> B,1 -> C,10 -> F,5
+---+
| B | -> C,8 -> D,7 -> F,2
+---+
| C | -> E,6
+---+
| D | -> C,4
+---+
| E | -> D,3 
+---+
| F | -> D,9 -> E,11
+---+


Adjacency Matrix
~~~~~~~~~~~~~~~~~~~~~~
2D array of adjacencies
edges[ from ][ to ]
        To
From     |
|        v
v  A  B  C  D  E  F
A     1 10        5
B        8  7     2
C              6
D        4
E           3
F           9 11

3. Discuss with your neighbor the advantages and disadvantages of storing the above graph with each of the following:
   Adjacency list
      Advantages:
      Less memory / compact storage
      Efficient to find adjacent vertices
      
      Disadvantages:
      Inefficient to find edges TO a given vertex

      
   Adjacency matrix
      Advantages:
      Simpler design
      Efficient retrieval of edges TO & FROM vertices
      
      Disadvantages:
      Potential for sparse storage (memory usage)


  Internally, (for either implementation) vertices are usually stored as indices

   For each implementation, how could you store the vertex labels?
   
      Adjacency list
      In a separate array (using the same indices as the matrix)
	 
      Adjacency matrix
      In a separate array (using the same indices as the matrix)


   How could you store weights?
      Adjacency list
      Add a value to each linked list node

      Adjacency matrix
      Use weights as entries in the matrix


  G = {V, E}
4. Discuss with your neighbor the advantages and disadvantages of performing the following common operations on graphs for each implementation:
   A. Determine whether there is an edge from vertex i to vertex j
      Adjacency list: Look at (up to) all of the edges from i;  O( |E| )
      Adjacency matrix: matrix[ i ][ j ]; O( 1 )
   
   B. Find all vertices adjacent to a given vertex i
      Adjacency list:  Look through each list;  O( |V + E| )
      Adjacency matrix:  Iterate through 1 column;  O( |V| )


20240228
*******************************************************

5. Given digraph G = (V, E) with an adjacency list representation how long does it take to determine the outdegree for v ∈ V (for a single vertex)?
   Traverse the linked list for v: O( |E| )
   
5b. Given digraph G = (V, E) with an adjacency list representation how long does it take to determine the outdegree for ALL v ∈ V?
   For each v, traverse the linked list for v: O( |V + E| )


6. Given digraph G = (V, E) with an adjacency list representation how long does it take to determine the indegree for v ∈ V?
   For each vertex u, traverse the linked list for u (and count each adjacent edge to v): O( |V + E| )
   
6b. Given digraph G = (V, E) with an adjacency list representation how long does it take to determine the indegree for ALL v ∈ V?
   For each vertex u, traverse the linked list for u (and count each adjacent edge for each vertex): O( |V + E| )
   

7. When an adjacency matrix representation is used, most graph algorithms require time Ω(|V|^2), but there are some exceptions. Show that determining whether a directed graph G contains a universal sink - a vertex with indegree |V| - 1 and outdegree 0-can be determined in time O(V), given an adjacency matrix for G. (Note: Big-Ω means the best case running time)

   Let A be an adjacency matrix
   Set S_i = 1 for i .. |V| // potential sinks
   f = 1    // from vertex
   t = 2    // to vertex
   for i = 2 .. |V|
       if( A[f][t] == 0 ){
           // no edge from f to t
           S_t = 0 // there's not edge from f to t, so t can not be a universal sink
	   t = i + 1
       }else{
           // there is an edge from f to t
	   S_f = 0  // f can not be a universal sink
	   f = i + 1
       }
   }

   if( t <= |V| ){
       s = t
   }else{
       s = f
   }
   indegreeS = 0
   for i = 1 .. |V|
       indegreeS += A[i][s]

   if( indegreeS == |V| - 1  &&  A[s][s] == 0){
       return s
   }else{
       return -1
   }

Trace the execution of such an algorithm on the following graphs:
		To					
		A	B	C	D	E	F
From	A	1	0	1	1	0	0
	B	0	1	0	1	1	1
	C	1	1	0	1	1	0
	D	0	0	0	0	0	0
	E	0	1	0	1	0	0
	F	0	1	1	1	1	0

		1	2	3	4	5	6        
		A	B	C	D	E	F
        S	1	1	1	1	1	1 (i = 2)
	        f	t
		
        S	1	0	1	1	1	1 (i = 3)
	        f		t
		
        S	0	0	1	1	1	1 (i = 4)
	        		t	f
		
        S	0	0	0	1	1	1 (i = 5)
	        			f	t
		
        S	0	0	0	1	0	1 (i = 6)
	        			f		t
		
        S	0	0	0	1	0	0 (i = 7)
	        			f			t
					s

		To					
		A	B	C	D	E	F
From	A	1	0	1	1	0	0
	B	0	1	0	1	1	1
	C	1	1	0	1	1	0
	D	0	0	0	0	0	1
	E	0	1	0	1	0	0
	F	0	1	1	1	1	0
(Only the edge from D to F is changed from the previous graph)

		1	2	3	4	5	6        
		A	B	C	D	E	F
        S	1	1	1	1	1	1 (i = 2)
	        f	t
		
        S	1	0	1	1	1	1 (i = 3)
	        f		t
		
        S	0	0	1	1	1	1 (i = 4)
	        		t	f
		
        S	0	0	0	1	1	1 (i = 5)
	        			f	t
		
        S	0	0	0	1	0	1 (i = 6)
	        			f		t
		
        S	0	0	0	0	0	1 (i = 7)
	        					t	f
							s
		

Graph Traversals
=================================
Traversals only visit all of the vertices if the graph is connected
Cycles -> infinite loop (BAD)
+ Mark each vertex as they're queue

Depth-First Search (DFS) Traversal
~~~~~~~~~~~~~~~~~~~~~~
Proceeds along a path from the vertex v as deeply into the graph as possible before backing up

DFS( Vertex v ){
    mark v // visited
    for( each unvisited vertex u adjacent to v){
        DFS( u )
    }
}
    

Iterative version:
iterativeDFS( Vertex v ){
    Stack s
    s.push( v )
    mark v // queued
    while( ! s.empty() ){
        Vertex w = s.pop() // visiting now
        for( each unvisited vertex u adjacent to w [reverse alphabetical order]){
	    s.push( u )
	    mark u // queued
	}
    }
}

s (top to bottom):  
Queued: A B C D E F
w: F
Visited: A B D C E F


20240306
*******************************************************


Breadth-First Search (BFS)
~~~~~~~~~~~~~~~~~~~~~~
BFS "first visited, first explored" strategy
Queue

Iterative version:
iterativeBFS( Vertex v ){
    Queue q
    q.push( v )
    mark v // queued
    while( ! q.empty() ){
        Vertex w = q.deque() // visited
        for( each unvisited vertex u adjacent to w ){
            q.enqueue( u )
	    mark u // queued        
        }
    }
}

q (front to back): 
Queued: A B C F D E
w: E


8. List the vertices in the order that the respective search will visit them (starting with vertex A):
   Depth-first search: 
   Breadth-first search: 


9. Discuss with your neighbor what is the run time for Breadth-First Search, in terms of E and V.
  Adjacency List:  O( |V| + |E| )
  In the worst-case, for a connected graph, we're going to end up visiting every v ∈ V and every edge, but not more than each one.

  Adjacency Matrix:  O( |V|^2 )
  In the worst-case, for a connected graph, we're going to end up looping at every possible edge from every vertex, but not more than one each time.


Topological Sorting
=================================

Topological order: A list of vertices in a directed graph without cycles such that vertex x precedes vertex y if there is a directed edge from x to y in the graph

It's possible to have multiple topological orders for a graph

topoSort1( Graph g, List topoOrderList ){
    for each vertex v that has no successor
        topoOrderList.push_front( v )
    delete v and its edges from g
}

topoOrderList:


10. Given the list of directed edges below, draw the directed graph:
    Dress & groom            -> Buy flowers
    Buy flowers              -> Pick-up date
    Select activity          -> Pick-up date
    Make dinner reservations -> Select activity
    Pick-up date             -> Activity
    Activity                 -> Dinner

    

11. For this graph, determine the topological order. To find the next vertex that does not have a successor, iterate over vertices in the order that they appear in the input, starting at the top of the list each time.

topoOrderList:
    Make dinner reservations
    Select activity
    Dress & groom
    Buy flowers
    Pick-up date
    Activity
    Dinner

topoSort1( Graph g, List topoOrderList ){
    for each vertex v that has no successor (outdegree is 0)
        topoOrderList.push_front( v )
    delete v and its edges from g
}



Spanning Trees
++++++++++++++++++++++++++++++++++++++++++++

What is a spanning tree for a graph G = (V, E)?
Connected graph with no cycles
T = (V, E') where E' is a subset of E and T is a connected graph

What is the relationship between |V| and |E'|?
|E'| = |V| - 1
More edges -> introduce a cycle
Less edges -> not connected

3
7

To remove cycles, remove edges along cycles until |E'| = |V| - 1

DFS Spanning Tree
=================================

DFS( Vertex v ){
    mark v // visited
    for( each unvisited vertex u adjacent to v){
        make the edge from u to v (meaning that this edge will be part of the spanning tree)
        DFS( u )
    }
}


BFS Spanning Tree
=================================
BFS( Vertex V ){
  Queue q;
  q.push(v);
  mark v as queued
  while( ! q.isEmpty()){
    w = q.pop(); // visited
    for( all Vertex u adjacent to w that have not been queued){
      make the edge from u to v (meaning that this edge will be part of the spanning tree)    
      q.enqueue(u);
      mark u as queued
    }
  }
}


Spanning Trees Exercises #1
~~~~~~~~~~~~~~~~~~~~~~
For each of the following trees, calculate a DFS spanning tree and a BFS spanning tree (starting at A):

Graph with edges: A-B, A-F, A-G, B-C, B-G, C-D, C-G, D-E, D-G, E-F, E-G, F-G
-----------
DFS: Graph with edges: A-B, B-C, C-D, D-E, E-F, F-G
BFS: Graph with edges: A-B, A-F, A-G, B-C, E-F, D-G

Graph with edges: A-B, A-D, A-F, B-C, B-G, C-D, D-E, E-F, F-G
----------- 
DFS: Graph with edges: A-B, B-C, C-D, D-E, E-F, F-G
BFS: Graph with edges: A-B, A-D, A-F, B-C, D-E, F-G

Minimum Spanning Trees (MSTs)
=================================
What is a minimum spanning tree for a graph G = (V, E)?
T_m = (V, E'), where E' is a subset of E and (V, E') is a connected graph that minimizes:
   w( T_m ) = Σ_{(u,v) ∈ T_m} w(u,v)
   or
   w( T_m ) = \sum_{(u,v) \in T_m} w(u,v)

Prim's Algorithm (for MSTs)
~~~~~~~~~~~~~~~~~~~~~~
Iteratively, add the lowest cost edge that adds a vertex that's not in T_m
Greedy? Yes

primsMST( Graph G, Vertex v ){
   Create a empty graph gMST
   mark v as visited
   add v to gMST
   while( unvisited vertices in G ){
       find the least-case edge (w, u) from a visited Vertex w to an unvisited Vertex u // could be a minheap
       mark u as visited
       add u and edge (w, u) to gMST
   }
}

What kind of algorithm is Prim's?
Greedy

Kruskal's Algorithm (for MSTs)
~~~~~~~~~~~~~~~~~~~~~~
Add the lowest-cost edge that connects to a previously unconnected component

Kruskal( Graph G, Weights w){
    gMST = (G.V, null)         // O( V )
    for v in G.V{              // O( V )
        MakeSet( v )
    }
    sort G.E by w              // O( E log E )
    for edge (u,v) in G.E (in sorted order) // O( E ) * O( α(V) ) 
        if( FindSet( u ) != FindSet( v ) ){
	   // u and v are from distinct sets/graphs/trees
           add (u,v) to gMST
           Union( u, v )
        }
    }
}
\alpha(V) is a very slowly growing function (see Section 19.4)

Because G is connected: |E| >= |V| - 1
O( V ) * O( α( V ) ) = O( E α(V) )
α(V) = O(log V) = O(log E)
O(E log E) or O( E log V ) (because |E| < |V|^2)

What kind of algorithm is Kruskal's?
Greedy

Spanning Trees Exercise #2
~~~~~~~~~~~~~~~~~~~~~~
Interpret the vertices below as cities and the edges as the cost to lay down fiber optic cable.
What is the least cost to connect every city (starting with city A) for each graph?
Draw all of the edges that are part of the solution.

Graph with edges (with weights): A-B (9), A-F (8), A-G (5), B-C (2), B-G (3), C-D (7), C-G (4), D-E (2), D-G (1), E-F (5), E-G (6), F-G (7)
-----------

Prim's
Visited vertices: A
Edges included:

Visited vertices: A G
Edges included: A-G

Visited vertices: A D G
Edges included: A-G G-D

Visited vertices: A D E G
Edges included: A-G G-D D-E

Visited vertices: A B D E G
Edges included: A-G G-D D-E G-B

Visited vertices: A B C D E G
Edges included: A-G G-D D-E G-B B-C

Visited vertices: A B C D E F G
Edges included: A-G G-D D-E G-B B-C E-F

Kruskal's
Weight	Edge	Include	Forests
			⟨A⟩ ⟨B⟩ ⟨C⟩ ⟨D⟩ ⟨E⟩ ⟨F⟩ ⟨G⟩
1	D-G	Y	⟨A⟩ ⟨B⟩ ⟨C⟩ ⟨D,G⟩ ⟨E⟩ ⟨F⟩
2	B-C	Y	⟨A⟩ ⟨B,C⟩ ⟨D,G⟩ ⟨E⟩ ⟨F⟩
2	D-E	Y	⟨A⟩ ⟨B,C⟩ ⟨D,E,G⟩ ⟨F⟩
3	B-G	Y	⟨A⟩ ⟨B,C,D,E,G⟩ ⟨F⟩	
4	C-G	N
5	A-G	Y	⟨A,B,C,D,E,G⟩ ⟨F⟩	
5	E-F	Y	⟨A,B,C,D,E,F,G⟩
6	E-G	N
7	C-D	N
7	F-G	N
8	A-F	N
9	A-B	N

Graph with edges (with weights): A-B (2), A-C (5), A-F (2), B-G (3), B-H (4), C-E (6), D-E (8), D-F (6), D-G (1), E-F (5), G-H (2)
-----------

Prim's

Kruskal's
⟨ ⟩	


Spanning Trees Exercise #3
~~~~~~~~~~~~~~~~~~~~~~
Given graph G = (V, E) with an adjacency matrix representation, discuss with your neighbor what is the run time to calculate a minimum spanning tree.

Naive:
Search over all edges for each vertex:
   adjacency matrix: O( |V|^2 ) = O( V*V/2 )
   adjacency list:   O( |V|*|E| )

Priority queue / binary minheap:
Storing edges in a binary minheap and after removing each edge updating the minimum distinct to grow MST: O( |E| log |V| )

Prim's algorithm with Fibonacci heap: O( |E| + |V| log |V| )


Single-Source Shortest Paths (Chapter 22, 4th Edition)
++++++++++++++++++++++++++++++++++++++++++++

Definition
=================================
G = (V, E), which is weighted and directed
weights function, w : E -> ℝ
w( p ) is the sum of the weights of all of the edges
𝛿( u, v )
∞

Examples
~~~~~~~~~~~~~~~~~~~~~~


Related Algorithms / Variants
=================================
Reversed: single-destination multiple starting points


Single-pair shortest path


All-pairs shortest paths



Negative-weight Edges
=================================


Negative-weight Cycles
=================================

𝛿( u, v ) = -∞

Cycles
=================================



Initialization
=================================

∞
π


Relaxation
=================================



Exercise
=================================
Choose a random group assignment:
    Bellman-Ford (Section 22.1)
    Single-source shortest paths in DAGs (directed acyclic graphs) (Section 22.2)
    Dijkstra's (Section 22.3)
In your group, do the following to explain your assigned algorithm:
    Give a description of your algorithm (in English). Include any constraints that the algorithm has.
    Provide pseudocode for your algorithm
    Detail the execution of your algorithm for each of the three graphs (with A as the source)
    Explain what the run-time of your algorithm is and why.


Bellman-Ford (Section 22.1)
~~~~~~~~~~~~~~~~~~~~~~
Description:

    Constraints:
    
    
Pseudocode:

Examples:

Run-time:


Single-source shortest paths in DAGs (directed acyclic graphs) (Section 22.2)
~~~~~~~~~~~~~~~~~~~~~~
Description:

    Constraints:
    
Pseudocode:


Example:

Run-time:


Dijkstra's (Section 22.3)
~~~~~~~~~~~~~~~~~~~~~~
Description:

    Constraints:

    
Pseudocode:


Example:

Run-time:


20240403
*******************************************************

Standard Form → Slack Form Exercise
++++++++++++++++++++++++++++++++++++++++++++

Standard Form
=================================

Maximize:

  2x_1 - 6x_3

Subject to:

  x_1 + x_2 - x_3 ≤ 7

  -3x_1 + x_2  ≤ -8

  x_1 - 2x_2 - 2x_3 ≤ 0

  x_1, x_2, x_3 ≥ 0


Slack Form:
=================================

  z = 2x_1 - 6x_3
  
  x_4 = 7 - x_1 + x_2 - x_3
  x_5 = -8 + 3x_1 - x_2
  x_6 = -x_1 + 2x_2 + 2x_3
  
  x_1, x_2, x_3, x_4, x_5, x_6 ≥ 0
  


Exercise
++++++++++++++++++++++++++++++++++++++++++++
Apply the simplex algorithm to solve the following program:
Maximize:
18x_1 + 12.5x_2

Subject to:
x_1 + x_2 ≤ 20
x_1 ≤ 12
x_2 ≤ 16
x_1, x_2 ≥0

Change to:
z = 18x_1 + 12.5x_2

x_3 = 20 - x_1 - x_2
x_4 = 12 - x_1
x_5 = 16 - x_2

x_1, x_2, x_3, x_4, x_5 ≥0

x_e = ?
x_e = x_1
x_l = ?

x_3 = 20 - x_1 - x_2
x_1 ≤ 20

x_4 = 12 - x_1
x_1 ≤ 12 (more restrictive)

x_5 = 16 - x_2
x_1 ≤ ?


x_l = x_4
x_1 = 12 - x_4

z = 216 - 18x_4 + 12.5x_2

x_3 = 20 - 12 + x_4 - x_2
x_3 = 8 + x_4 - x_2
x_4 = 12 - (12 - x_4)
x_1 = 12 - x_4
x_5 = 16 - x_2



z = 216 - 18x_4 + 12.5x_2

x_1 = 12 - x_4
x_3 = 8 + x_4 - x_2
x_5 = 16 - x_2

x_e = ?
x_e = x_2

x_1 = 12 - x_4
x_2 ≤ ?

x_3 = 8 + x_4 - x_2
x_2 ≤ 8 (more constraining)

x_5 = 16 - x_2
x_2 ≤ 16

x_l = x_3
x_2 = 8 + x_4 - x_3


z = 216 - 18x_4 + 100 + 12.5x_4 - 12.5x_3
z = 316 - 5.5x_4 - 12.5x_3

x_1 = 12 - x_4
x_2 = 8 + x_4 - x_3
x_5 = 16 - 8 - x_4 + x_3
x_5 = 8 - x_4 + x_3



z = 316 - 5.5x_4 - 12.5x_3

x_1 = 12 - x_4
x_2 = 8 + x_4 - x_3
x_5 = 8 - x_4 + x_3