1. The following problem is known as the Dutch Flag Problem. In this problem, the task is to rearrange an array of characters R, W, and B (for red, white, and blue, which are the colors of the Dutch national flag) so that all the R’s come first, all the W’s come next, and all the B’s come last. Design a linear, in-place algorithm that solves this problem.
2. Give an O(nlgk)-time algorithm to merge k sorted lists into one sorted list, where n is the total number of elements in all the input lists. (Hints: Use a heap for k-way merging.)

(a) Note this is a Collaborative Problem

Consider the following algorithm for doing a postorder traversal of a binary tree with root vertex root.

Algorithm 1 Postorder Traversal function Postorder(root) if root 6= null then

Postorder(root.left) Postorder(root.right) visit root

end if end function

Prove that this algorithm run in time Θ(n) when the input is an n-vertex binary tree.

(b)

We define an AVL binary search tree to be a tree with the binary search tree property where, for each node in the tree, the height of its children differs by no more than 1. For 1

this problem, assume we have a team of biologists that keep information about DNA sequences in an AVL binary search tree using the specific weight (an integer) of the structure as the key. The biologists routinely ask questions of the type, “Are there any structures in the tree with specific weight between a and b, inclusive?” and they hope to get an answer as soon as possible. Design an efficient algorithm that, given integers a and b, returns true if there exists a key x in the tree such that a ≤ x ≤ b, and false if no such tree exists in the tree. Describe your algorithm in pseudocode and English. What is the time complexity of your algorithm? Explain.

4. [50 points] Note this is a Collaborative Problem

(a)

Using either the Radial Basis Neural Network, Feed Forward Neural Network or Probabilistic Neural Network, classify the IRIS data set and the data generated in Problem 3 from HW 4 to determine how well your classifier works on both data sets.

(b)

Using the Support Vector Machine, classify the IRIS data set and the data generated in Problem 3 from HW 4 to determine how well your classifier works on both data sets.

5. [10 Bonus Points]

Using your implementation of EM or the built-in EM algorithm add the Bayes Classifier of Equation 8 in the Machine Learning I document. Use the IRIS data set and the data generated in Problem 3 from HW 4 to determine how well your classifier works. Compare the results against the Neural Network algorithm and the Support Vector Machine.