Homework Assignments:

1. Due Jan 17:
   • Give an example of BFS and DFS on a simple graph which distinguishes them
   • Give an example of Dijkstra's shortest path algorithm and Prim's minimum spanning tree algorithm on a graph which distinguishes them. Show the steps of the algorithm
2. Due Jan 24:
   • Show what would happen after running the Floyd-Warshall algorithm on the graph on page 5 of Jan 19 notes for j=1,2,3. Show the arrays d_i,k and p_i,k.
   • Consider the two variants of the Floyd-Warshall algorithm:
     1. p_i,k = j     if     d_i,k > d_i,j + d_j,k
     2. p_i,k = p_i,j     if     d_i,k > d_i,j + d_j,k
     
     In both cases, p_i,k remains the same if d_i,k ≤ d_i,j + d_j,k
     
     Illustrate the differences on a simple graph. Which gives p_i,k as the first node in the path to k?
3. Due Feb 2:
   • What is the difference between a set and a sequence?
   • Given conditions A, B, and C, if A ⇒ B and B ⇒ C and C ⇒ A, then the three conditions are equivalent. True or False? Why?
   • Problem 1: We want to maximize F(x) subject to the constraint that x ∈ S₁
     Problem 2: We want to maximize F(x) subject to the constraint that x ∈ S₂, where S₁ ⊂ S₂
     Then the maximum value of F(x) in Problem 1 is less than or equal to the maximum value of F(x) in Problem 2. True or False? Why?