CSOR W4231.001 – Spring, 2022
BRIEF solutions to homework 1
1. Solution to problem 1
A straightforward modification of binary search will solve this problem. Time: O(log n).
Copyright By PowCoder代写 加微信 powcoder
2. Solution to problem 2
(a) Scan the array and maintain the minimum and maximum values, m and M, respectively.
Return m,M (max difference is M − m). Time: O(n).
(b) Return A[1], A[n]. Time: O(1).
(c) Sort A, then do as in part (d). Time: O(n log n).
(d) Scan the sorted array. Maintain and return the contiguous pair of elements with min
difference. Time: O(n).
3. Solution to problem 3
We will use a divide & conquer approach. Split the input into two arrays of size n/2. The key observation is that if A has a majority item, then that item must also be a majority item of at least one of the two subarrays. Hence compute recursively the majority items of each of the two subarrays (if such exist), then check if one of them is a majority item of A. The recurrence is T (n) = 2T (n/2) + cn = Θ(n log n).
4. Solution to problem 4
Consider the following algorithm. Start at the root r of the tree. If its value is smaller than both of its children, then r is a local minimum so terminate and return r. Otherwise, move to a child that has a smaller value and iterate.
The algorithm terminates either
(a) if we reach an internal node v that has a smaller value than both of its children; or
(b) if we reach a leaf l.
The correctness of the algorithm follows by observing that the algorithm always terminates atalocalminimum: Incase(a),vhasasmallervaluethanbothofitschildren,andasmaller value than its parent node (otherwise we would not have moved to v from its parent node); in case (b), l has a smaller value than its parent (same reasoning as for case (a)).
Running time: O(log n).
5. Solution to problem 5
Scan the sorted triples in order, and construct the following directed graph G = (V, E).
Vertex set V : If computer Ci appears in a triple at time tk, introduce a node vik corresponding to computer Ci at time tk. (If computer Ci appears in multiple triples at time tk, we only introduce vik once.)
Edge set E: For every triple (Ci,Cj,tk), introduce a pair of anti-parallel edges between vik and vjk. Also, when we introduce a node vik, we find the latest time tf in which Ci previously appeared in a triple, and add the directed edge (vif,vik).
Note that we introduce a constant number of nodes and edges per input triple, hence the graph has O(m) nodes and edges. Further the graph can be constructed in O(m) time.
The original problem is now equivalent to the following graph problem: If we start at node vix, can we reach node vjy? We can solve this problem by running BFS(G,vix) in O(m) time.
6. Solution to problem 6
Note that, if such a vertex exists, then the meta-graph of SCCs of G must contain only one
source SCC (why?). Then any vertex in that source SCC fits desription.
To check this, run DFS in the graph and find the node u with the largest finish time. From the lecture slides, we know that u belongs to a source SCC. Now run the DFS Search subroutine from u. If all nodes are marked as explored, then return u. Running time: O(n + m).
RECOMMENDED EXERCISES (do NOT return, they will not be graded) 1. Solution to recommended exercise 1
• Accordingtomastertheorem,a=4,b=2,k=3. Thusa
•Accordingtomastertheorem,a=6,b=3,k=1. Thusa>bk andT(n)=nlogba, hence T (n) = O(nlog3 6).
• This recurrence is not in the form required by the master theorem. Therefore, we would have to explicitly construct and analyze the recursion tree for this recurrence. Alternatively, we may use the following substitutions.
Let n = 2m (hence n = logn). Then
T(2m) = T(2m/2) + 1.
This recurrence is still not in the desired form but it’s quite close. Let F(m) = T(2m),
This is the recurrence we encountered for the running time of binary search. Or, we can
F(m) = F(m/2) + 1.
use the Master Theorem to obtain F (m) = O(log m). It follows that
T(n) = T(2m) = F(m) = O(logm) = O(loglogn).
2. Solution to recommended exercise 2
First note that f(n) = ni=0 λi. Then for n ≥ 1:
Thenf(n)≥1andf(n)<∞ λi = 1 . Hence f(n) = Ω(1) and f(n) = O(1), thus f(n) = Θ(1). Then f(n) = ni=0 λi = n + 1. Hence f(n) = Θ(n). Thenf(n)=λn+1−1.Hencef(n)≥λn,andf(n)≤λn+1 = λ ·λn. λ−1 λ−1 λ−1 Hence f(n) = Θ(λn). 3. Solution to recommended exercise 3 (log log n)3 2n/2+log n (log n)log n 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com