Homework 1
算法课业代写 1 Largest Interval Overlap An interval on the real number line can be defined as a pair of starting and ending coordinates.
0 Logarithms and Asymptotic Notation
Let b, c, ∈ R>0.
a. (2 points) Prove that logbn = Θ(logcn).
Answer starts here!
Claim 1. If b, c ∈ R>0, then logb n = Θ(logc n).
Proof.
This means that we can generally ignore the base of logarithms when using asymptotic notation.
1 Largest Interval Overlap 算法课业代写
An interval on the real number line can be defined as a pair of starting and ending coordinates. For example, the interval (−4, 6) represents the set of real numbers between -4 and 6. We define the overlap between two intervals (x1, y1) and x2, y2 is defined as (max(x1, x2), min(y1, y2)), and the size of an interval (x, y) is defined as max(y −x, 0) (i.e. if y < x, the size of the interval is 0).
a. (6 points) Write pseudocode for a divide-and-conquer algorithm which takes an arrayA[1 . . . n], where each A[i] = (xi , yi) represents an interval, and returns the size of the largest overlap between any pair of intervals in A. Your algorithm should run in O(n log n) time.
Algorithm 1 MyAlgorithm(A[1 . . . n])
Require: You can use REQUIRE statements for assumptions {e.g. binary search requires sorted input}
1: if you need a conditional then
2: Use IF, but don’t forget ENDIF!
3: else if you need a loop then
4: You can use either FOR/ENDFOR or WHILE/ENDWHILE
5: while it’s raining do
6: Bring an umbrella
7: end while
8: for each person at the party do
9: Cut a slice of cake
10: end for
11: else
12:Use STATE for regular statements.
13: It’s okay to use English, like “Sort A with insertion sort” or “if A is empty”, as long as it’s precise.
14: Prefer mathematical notation to syntax specifific to Python or other languages
15: For comparisons, use == or “equals”. For variable assignments, use = (or \gets to prevent ambiguity)
16: For example, S ← ∅ to create an empty set, and S == ∅ or “S is empty” to check if it’s empty
17: Some operations take more than O(1) time! You can write max(A) instead of a loop, but it’s still O(n)
18: end if
19: return Don’t forget to RETURN your answer!
b. (3 points) Give a proof of correctness for your algorithm.
c. (1 point) Analyze the runtime of your algorithm.
2 Basketball Tournament 算法课业代写
A basketball tournament is held between n teams in round-robin format: every team plays each other team exactly once. The results are recording in a matrix A ∈ Rn×n, where A[i, j] = 1 if team i beat team j or A[i, j] = 0 if team i lost to team j (there are no ties). Since a team cannot play itself, A[i, i] is undefined for all i ∈ [n]. An elite team is defined as a team which loses fewer than 10 games.
a. (4 points) What is the maximum possible number of elite teams? Prove your answer.
Hint: Recall that in order to establish a maximum of k elite teams, you must show that it is possible to have k elite teams and impossible to have k + 1 or more elite teams for some integer k.
b. (6 points) Write pseudocode for an algorithm which takes A as an argument and outputs the set of all elite teams in the tournament. Your algorithm must run in O(n log n) time (it is also possible to improve this bound to O(n) time); no points will be awarded for naive / brute force solutions.
Hint: Consider the bound obtained in part (a) above.
c. (2 points) Give a proof of correctness for your algorithm.
d. (1 point) Analyze the runtime of your algorithm.
更多代写：代写英国ESSAY GRE代考 英国代修商科网课 代写英国ESSAY 北美艺术学summary代写 英文网课代修
