HW3
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] A detachment of n soldiers must cross a wide and deep river with no bridge in sight. They notice two 12-year-old boys playing in a rowboat by the shore. The boat is so tiny, however, that it can only hold two boys or one soldier. How can the soldiers get across the river and leave the boys in joint possession of the boat? How many times need the boat pass from shore to shore?
2. [Written 10pt] Apply the source-removal algorithm to the digraphs (see below).
3. [Written 10pt] Write the (complete) pseudocode of the source-removal algorithm for topological sorting. What is the running time? (Review the graph representation of a digraph and include graph representation in your codes.)
4. [Written 10pt] Design a decrease-and-conquer algorithm for generating all combinations of k items chosen from n, i.e., all k-element subsets of a given n-element set.
5. [Written 10pt] A stick n inches long needs to be cut into n 1-inch pieces. Outline an algorithm that performs this task with the minimum number of cuts if several pieces of the stick can be cut at the same time. Also, give an exact formula for the minimum number of cuts.
6. [Written 10pt] You need to search for a given number in an n × n matrix in which every row and every column is sorted in increasing order. Design an O(n) algorithm for this problem.
7. [Written 9pt]
a. Write pseudocode for a divide-and-conquer algorithm for finding the largest element in an array of n numbers.
b. Setup and solve a recurrence relation for the number of key comparisons made by your algorithm (You can assume the size is n = 2k).
c. How does this algorithm compare with the brute-force algorithm for this problem?
8. [Written 9pt] Find the order of growth for solutions of the following recurrences.
a. T(n) = 4T(n/2)+n, T(1) = 1
b. T(n) = 4T(n/2)+n2, T(1) = 1
c. T(n) = 4T(n/2)+n3, T(1) = 1
9. [Written 10pt] Apply quicksort to sort the list E, X, A, M, P, L, E in alphabetical order. Show the step-by-step running of the algorithm.
10. [Written 10pt] Design an algorithm to rearrange elements of a given array of n real numbers so that all its negative elements precede all its positive elements. Your algorithm should be both O(n) time-efficient and space-efficient.
11. [Written 9pt] Traverse the following binary tree (see below).
a. in preorder
b. in inorder
c. in postorder
12. [Written 9pt] Write pseudocode for the following traversal algorithms for binary trees.
a. in preorder
b. in inorder
c. in postorder
13. [Written 10pt] Write pseudocode for multiplying two n-digit numbers using the divide and conquer approach presented in class. You can assume that n = 2k. (Hint: revisit Section 5.4 of the book)
14. [Written 10pt] Write pseudocode for multiplying two n by n matrices using the divide and conquer approach presented in class. You can assume that n = 2k. (Hint: revisit Section 5.4 of the book)
15. [Written 10pt] Give a specific example of inputs that make quickhull (that we discussed in class) run in quadratic time. (Discuss why!)
******************************************** Coding ********************************************
1. [Coding + Simulation 20pt] Consider ternary search — the following algorithm for searching in a sorted array A[0..n − 1]. If n = 1, simply compare the search key K with the single element of the array; otherwise, search recursively by comparing K with A[⌊n/3⌋], and if K is larger, compare it with A[⌊2n/3⌋] to determine in which third of the array to continue the search.
a. Implement both binary search and ternary search (either recursively or iteratively).
b. Set up recurrences for the number of key comparisons in the worst case in your implementations (for both binary search and ternary search)
c. Solve the recurrences assuming n = 2k and n = 3k for the binary search recurrence and ternary search recurrence, respectively.
d. Measure the running time (as the number of basic operations) of the two searches by generating 100 random instances of size S = {10, 50, 100, 500, 1000, 5000, 10000, 50000} (e.g., random integers of sorted arrays of the given size and some search keys). Report the average running time of each instance averaging over the 100 instances of a given size. Plot the running time with the x-axis labeled as size and the y-axis labeled as running time.
For example, when the size is 10, you generate a random integer array of 10 elements [50, 90, 40, 30, 33, 34, 55, 9, 100, 8] and some search keys. You then run the same instance on binary search and ternary search. Repeat this 100 times and report the average and standard deviations.
e. Discuss your findings.
