CSE 5311: Design and Analysis of Algorithms.

All exercies and problems refer to the textbook. Version 3.

Homework 1 (due Nov 2)

Exercies 1 (Sorting).
 
Exercises 6.1-1 through 6.1-7.
Exercises 6.2-1, 6.2-2, 6.2-3, 6.2-4.
Exercises 6.3-1 through 6.3-3.
Exercises 7.1-1 through 7.1-4.
Exercises 7.2-2 through 7.2-4.
Exercises 7.4-5.
Exercises 8.1-1, 8.1-3.
Exercises 8.2-1, through 8.2-4.

Notes: The concept of algorithm stability is explained in top of page 170. Using example of Figure 8.2, show that all three "3" elements
from A moved to B in the same order, which means the algorithm is "stable".
Is merge sort stable? Is quicksort stable? Is there a way to fix the problem?
Algorithm stability is crucial for the correctness of Radix sort.

Exercises 8.3-1, through 8.3-4.
Notes: Show that if you sort the most significant bit first, the result is wrong. Use the example in Figure 8.3

Problem 1 (Sorting ).
 
Problem 8.2, subproblem (a)
(Hint: modify the parition algorithm in quicksort)

Homework 2 (due Nov 2):

Exercises 2 (Median Finding).
 
Exercises 9.3-1 through 9.3-3, .9.3-5, .9.3-7.

Dynamic Programing Exercises
 
The presentation of rod-cutting problem (Section 15.1) could be simplified.
Recurrence Eq.(15.1) is the key relation. Recurrence Eq.(15.2) is not necessary.
(a) Modify "Cut-Rod" subroutine on p.363 so that it implements Recurrence Eq.(15.1)
(b) Similarly, modify "Bottom-Up-Cut-Rod" subroutine on p.366 and "Extended-Bottom-Up-Cut-Rod" subroutine on p.369.
[[Currently, these 3 subroutines implement Recurrence Eq.(15.2)]]
(c) Implements both versions of the "Extended-Bottom-Up-Cut-Rod" subroutine in any language. Give several examples of price list. Run the algorithms on these price lists to test whether they give same results, i.e., the revenue list r[0...n] .
[[Recurrence Eq.(15.2) is a simplified version of Recurrence Eq.(15.1): it reduces the original problem to 1 subproblem in each iteration whereas Eq.(15.1) has 2 subproblems. But, as you see from the modified codes, this difference is small. Recurrence Eq.(15.1) is more intuitive; it is the version most dynamic programming algorithm design first arrives at. ]]

Exercises 15.1-3. This problem is closer to real life.

Exercises 15.2 (Matrix Chain multiplication).
 
Exercises 15.2-1

Exercises 15.4 (Longest Common Subsequence).
 
Modify "LCS-length" and "Print-LCS" subroutines (page 394-395) so that they traceback all optimal solutions. [Current version only traceback 1 optimal solution]

Using the LCS algorithm to find all optimal solutions on
(a) between ABDEDFB and ADFFB.
(b) between AABCDAEF and DEADF.

Exercises 15.4-5. (We discussed this problem in class)

Exercises 16.1 (Greedy Algorithms).
 
Exercises 16.1-2.(Hint: Start selecting activities backwards in time)
Exercises 16.1-4.(Hint: find the maximum number of required lecture halls, and show your algorithm will never use more than that)
Exercises 16.1-5. (Hint: using dynamic programming technique)

Homework 3 (due Nov 23)

Exercises 22.2 (Breadth First Search).
 
Exercises 22.2-1 - 22.2-4.

Exercises 22.3 (Depth First Search).
 
Exercises 22.3-2 , 22.3-11.

Exercises 22.4 (Topological sort).
 
Exercises 22.4-1 , 22.4-3.

Problems 3
 
Problem 22-3. Euler Tour

Exercises 22.5 (Stronlgly Connected Component)
 
Exercises 22.5-1 through 22.5-3, 22.5-6

Exercises 23 (Minimum Spanning Trees)
 
Exercises 23.1-8, 23.2-1

Homework 4 (due Dec 14)

Exercises 24 (Single-source shortest path).
 
Exercises 24.1-1
Exercises 24.3-1, 24.3-3, 24.3-4, 24.3-5

Exercises 25 (All-pair shortest path).
 
Exercises 25.1-2
Exercises 25.2-1, 25.2-6

Exercises 26 (Network Maximum Flow).
 
Exercises 26.2-1, 26.2-2, 26.2-3