HW4
Submit a single .pdf for the written problems and .java codes for the coding problems to me via email by the date of the deadline (11:59 pm)
(1) Please show ALL of your work (Step by Step).
(2) Provide as many details as possible for the designed algorithms (exact pseudocode) from now on.
******************************************** Written ********************************************
1. [Written 10pt] Consider the problem of finding the distance between the two closest numbers in an array of n numbers. (The distance between two numbers x and y is computed as |x − y|.)
a. Design a brute-force algorithm for solving this problem and determine its efficiency class.
b. Design a presorting-based algorithm for solving this problem and determine its efficiency class.
2. [Written 10pt] Let A={a1,...,an} and B ={b1,...,bm} be two sets of numbers. Consider the problem of finding their intersection, i.e., the set C of all the numbers that are in both A and B.
a. Design a brute-force algorithm for solving this problem and determine its efficiency class.
b. Design a presorting-based algorithm for solving this problem and determine its efficiency class.
3. [Written 10pt] Given a list of n distinct integers and a sequence of n boxes with pre-set inequality signs inserted between them, design an algorithm that places the numbers into the boxes to satisfy those inequalities. For example, the numbers 4, 6, 3, 1, 8 can be placed in the five boxes as shown below. Please make sure your algorithm is not exponential time.
4. [Written 10pt] Write pseudocode for the back-substitution stage of Gaussian elimination and show that its running time is in O(n2).
5. [Written 6pt] Which of the following binary trees (see below) are AVL trees? Why?
6. [Written 10pt] Draw diagrams of the single L-rotation and of the double RL-rotation in their general form (show the intermediate step).
7. [Written 10pt] For each of the following lists, construct an AVL tree by inserting their elements successively, starting with the empty tree.
a. 1, 2, 3, 4, 5, 6 (in this order)
b. 6, 5, 4, 3, 2, 1 (in this order)
c. 3, 6, 5, 1, 2, 4 (in this order)
8. [Written 10pt] For an AVL tree containing real numbers, design an algorithm for computing the range (i.e., the difference between the largest and smallest numbers in the tree) and determine its worst-case efficiency.
9. [Written 10pt] Construct a 2-3 tree for the list C,O,M,P,U,T,I,N,G. Use the alphabetical order of the letters and insert them successively starting with the empty tree.
10. [Written 10pt]
a. Construct a heap for the list 1, 8, 6, 5, 3, 7, 4 by the bottom-up algorithm.
b. Construct a heap for the list 1, 8, 6, 5, 3, 7, 4 by the top-down algorithm.
11. [Written 10pt] Outline an algorithm for checking whether an array H[1..n] is a heap and determine its time efficiency.
12. [Written 10pt] Indicate the time efficiency classes of the three main operations (e.g., searching, deletion, and insertion) of the priority queue (see its definition) implemented as (explain why)
a. an unsorted array
b. a sorted array
c. a binary search tree
d. an AVL tree
e. a heap
13. [Written 10pt] You are given a list of numbers for which you need to construct a min-heap. (A min-heap is a complete binary tree in which every key is less than or equal to the keys in its children.) How would you use an algorithm for constructing a max-heap to construct a min-heap?
14. [Written 10pt] Design an algorithm with a time efficiency better than cubic for checking whether a graph with n vertices contains a cycle of length 3.
15. [Written 10pt] The graph-coloring problem is usually stated as the vertex-coloring problem: Assign the smallest number of colors to vertices of a given graph so that no two adjacent vertices are the same color. Consider the edge-coloring problem: Assign the smallest number of colors possible to edges of a given graph so that no two edges with the same endpoint are the same color. Explain how the edge-coloring problem can be reduced to a vertex-coloring problem (and how we can use the solution for one to solve the other, and vice versa).
16. [Written 10pt] Let x1 < x2 < . . . < xn be real numbers representing coordinates of n villages located along a straight road. A post office needs to be built in one of these villages. Find the post-office location minimizing the average distance between the villages and the post office. (Hint: Consider n=1, n=2, n=3, ...)
17. [Written 10pt] Given n points (x1, y1), . . . , (xn, yn) in the Cartesian plane, find a location (x, y) for a post office that minimizes 1/n \sum_{i=1}^n (|xi − x| + |yi − y|), the average Manhattan distance from the post office to these points. Explain how this problem can be efficiently solved by the problem reduction technique, provided the post office does not have to be located at one of the input points. (Hint: Solve 16 first)
18. [Written 10pt] The assignment problem introduced in Section 3.4 can be stated as follows: There are n people who need to be assigned to execute n jobs, one person per job. (That is, each person is assigned to exactly one job and each job is assigned to exactly one person.) The cost that would accrue if the ith person is assigned to the jth job is a known quantity C[i,j] for each pair i,j =1,...,n. The problem is to assign people to jobs to minimize the total cost of the assignment. Express the assignment problem as a 0-1 integer linear programming problem (where the domain of the variables is in {0, 1}).
