codingprolab@gmail.com

- Home
- Uncategorized
- CS180 Homework 2

$30.00

Order Now
Category: Uncategorized

Description

5/5 - (4 votes)

1. You are given n songs {1, 2, . . . , n} and 2 preference lists A = {a1

, a2

, . . . , an

} and B = {b1

, b2

, . . . , bn

}. Each ai

is a

positive integer and ai = k means the song k is ranked at i

th position in list A. An inversion between A and B is a pair

(i, j) such that song i is ranked before song j in list A, but song j is ranked before song i in list B. In the lecture, we

showed that to count the number of inversions, we can permute the songs in both lists according to the index of list

A. More specifically, the permutation is defined by ai

7→ i for all i. We claimed that the number of inversions after

applying the permutation does not change. Actually, this claim works for any permutation. Prove that the number

of inversions does not change if we apply an arbitrary permutation.

2. Suppose you are given two sets of n points in the plane, one set {p1

, p2

, …, pn

} on the line y = 0 and the other set

{q1

, q2

, …, qn

} on the line y = 1. Create a set of n line segments by connecting each point pi

to the corresponding

point qi

. The number of intersections is the number of how many pairs of these line segments are crossing.

An example with 11 intersections

(a) Consider the two sets of n points are two preference lists of n songs. The value of pi and qi

represents how song

i is ranked in two preference lists. Prove that the number of inversions in two preference lists is equivalent to

the number of intersections.

(b) Describe an algorithm to calculate the number of intersections in O(n log n) time.

3. A celebrity among n persons is someone who is known by everyone but does not know anyone. Give an iterative

algorithm to find the celebrity among n people.

4. The diameter of a tree is the number of edges in the longest path in the tree.

(a) Given a rooted directed tree, find the diameter of the underlying undirected tree using a recursion, computes

the result of the original problem given that we removed the root and solved the problem for the remaining

rooted trees.

(b) Write the iterative version of this algorithm, and analyze its complexity, which should be linear in n, the number

of nodes in the tree.

Æ Homework assignments are STRICTLY due on the exact time indicated. Please submit a hard copy of your homework

solution with your Name, Bruin ID, Discussion Number, clearly indicated on the first page. If your homework

consists of multiple pages, please staple them together. Email attachments or other electronic delivery methods are

not acceptable.

Æ We recommend to use LATEX, LYX or other word processing software for submitting the homework. This is not a

requirement but it helps us to grade the homework and give feedback. For grading, we will take into account both

the correctness and the clarity. Your answer are supposed to be in a simple and understandable manner. Sloppy

answers are expected to receive fewer points.

Æ Unless specified, you should justify your algorithm with proof of correctness and time complexity.

WhatsApp us