Python算法分析代写 | EECS 325 Analysis of Algorithms Homework 2


• You must submit your written solutions as a single .pdf file on Canvas with your name at
the top. Typesetting your written solutions using L ATEX is strongly encouraged. You must
submit your programming solutions to Question 6 as a single .cpp, .java, or .py file depending
on your choice of language.

• You are welcome and encouraged to discuss the problems in groups of up to three people, but
you must write up and submit your own solutions and code. You must also write the
names of everyone in your group on the top of your submission.

• The primary resources for this class are the lectures, lecture slides, the CLRS and Erickson
algorithms textbooks, the teaching staff, your (up to two) collaborators, and the class Piazza
forum. We strongly encourage you only to use these resources. If you do use another resource,
make sure to cite it and explain why you needed it.

• Scoring: The total score is 50 points, with the possibility of up to 5 extra credit points.

• You must justify all of your answers unless specifically stated otherwise.

Question 1 (Counting inversions, 9 points.) CLRS Problem 2-4.

Question 2 (Recurrences, 9 points.) CLRS Problem 4-1. Draw recursion trees for parts (a) and
(b). You may use any method that you wish for solving the remaining parts, but you must justify
your answers.

(Hint: CLRS Appendix A.1 contains a helpful formula for solving part (g).)

Question 3 (Closest pair in Manhattan distance, 5 points.) CLRS Exercise 33.4-3.

(Hint: Modify the algorithm that we saw in class. Your main change should be to modify the number of
points below the current point looked at in the \combine” phase. Make sure to justify your answer. What
is the shape of the set of point within Manhattan distance ff of a given point?)

Question 4 (Graph coloring and register allocation, 9 points.) In the graph coloring problem, the
input is a simple graph G = (V;E), represented by an adjacency list, and the goal is to find a
labeling of the vertices c : V –  {1,….,k} for some k >= 1 such that c(u) = c(v) if fu; vg 2 E. Such