1 Problem 2.23
Solutions to Homework 4
Debasish Das
EECS Department, Northwestern University ddas@northwestern.edu
Definition 1 Majority element of an array A[1 … n]: An array is said to have a majority element if more than half of its entries are the same.
A constraint on this problem is that only equality is defined on the objects of the array. You can check if the array elements are equal but there is no > or < relation defined on the elements
(a)We split the array A into 2 subarrays A1 and A2 of half the size. We choose the majority element of A1 and A2. After that we do a linear time equality operation to decide whether it is possible to find a majority element. The recurrence therefore is given by
T(n) = 2T(n) + O(n) (1) 2
The complexity of algorithm comes to O(n log n)
procedure GetMajorityElement(a[1...n])
Input: Array a of objects
Output: Majority element of a
if n = 1: return a[1] k = n
2
elemlsub = GetMajorityElement(a[1...k]) elemrsub = GetMajorityElement(a[k+1...n] if elemlsub = elemrsub:
return elemlsub
lcount = GetFrequency(a[1...n],elemlsub) rcount = GetFrequency(a[1...n],elemrsub) if lcount > k+1:
return elemlsub
else if rcount > k+1:
return elemrsub
else return NO-MAJORITY-ELEMENT
GetFrequency computes the number of times an element (elemlsub or elemrsub) appears in the given array
a[1…n]. Two calls to GetFrequency is O(n). After that comparisons are done to validate the existence of
majority element. GetFrequency is the linear time equality operation.
(b)Using the proposed divide-and-conquer operation, indeed it is possible to give a linear time algorithm.
Idea is to pair up the elements arbitrarily to get n pairs. In each pair if the two elements are different we 2
discard both of them. If they are same only one of them is kept. Before we give the algorithm, we have to prove the following lemma
Lemma 1 After the proposed procedure, there are atmost n elements left and if A has a majority element, 2
then remaining elements will have the same majority element
1
Proof: Let m be a majority element of A. Frequency of m is greater than n where n is the number of 2
elements of A. Since we are forming pairs of 2, there has to be at least one pair where both the elements of the pair are m since otherwise frequency of m in A cannot be greater than n . At most all pairs can have
2
both the elements of the pair as m. So after the procedure at least one element m will be left or at most n
2
p=q (2)
p ̸= q (3) p=m ∧ q̸=m (4) p̸=m ∧ q=m (5)
All pairs (p,q) satisfy one of the 4 equations. For Equations 3-5 majority of m is maintained because while removing one occurence of majority element m we also remove another element. For pairs satisfying Equation 2 we keep p. p may or may not be equal to m but keeping one occurence of p guarantees majority of m.
Note that the lemma holds only if the array A has a majority element m. Therefore once we apply the algorithm and come up with a majority element, it is mandatory to check if m is indeed a majority element of the array. That can be done by a GetFrequency call followed by a check whether the frequency of m in A[1…n] is greater than n .
2
procedure GetMajorityElementLinear(a[1…n])
Input: Array a of objects
Output: Majority element of a
if n = 2:
if a[1] = a[2] return a[1]
else return NO-MAJORITY-ELEMENT
Create a temporary array temp
for i = 1 to n:
if a[i] = a[i+1]:
Insert a[i] into temp
i = i+1
return GetMajorityElementLinear(temp)
procedure CheckSanity(a[1…n])
Input: Array a of objects
Output: Majority element of a
m = GetMajorityElementLinear(a[1…n]) freq = GetFrequency(a[1…n],m)
if freq > n+1: 2
return m
else return NO-MAJORITY-ELEMENT
Recurrence relation for the algorithm is given as follows
T(n) = T(n) + O(n) (6) 2
as we can see the processing of array in the recursive function is done in O(n) time. Complexity of the function GetMajorityElementLinear is O(n). CheckSanity is also O(n). Therefore the whole algorithm is linear in terms of n.
will be left where each of them is m. Therefore out of at most n elements, one of the element must be m. 2
Consider arbitrary pairs (p,q) formed by the procedure. There are four possible cases
2
2 Problem 2.30
(a) ω = 3 or 5 satisfies the equation. 6i=1 ωi = 6i=1 i (by definition of ω). The summation has a factor of 7 in it which makes the sum modulo 7 0.
(b)
1111110 10 3
1326451 41 6
1 2 4 1 2 41 25 4
M6(ω)·X =1 6 1 6 1 61=30=2(mod7) (7)
1 4 2 1 4 2 5 31 3 1546232 31 3
(c) Inverse of 3 for mod 7 arithmetic is 5. 1 1
1 5
−1 1 4 M (ω)·X=6·
24
62 76 1 4 3 51 5
6 1 6 1 2
Therefore 3 and 5 are the number and its inverse respectively.
1 1 1
4 6 2
2 1 4
1 6 1
4 1 2
13 36
21 0 76 1
1326453 682
(d)Let’s call x2 +x+1 as A and x3 +2x+1 as B. Computing the polynomials A and B on the given points
ωi : i ∈ (1..6), we obtain a and b as follows (note that -1 is 6 in mod 7 arithmetic) a=1 1 1 0 0 0T
b=6 2 0 1 0 0T
To compute the transform we multiply a and b with M6(w) as shown in part (b)
1111111 3 1326451 6
1 2 4 1 2 41 0
Ta=1 6 1 6 1 60=1 1 4 2 1 4 2 0 0
154623 0 3 1111116 2
1326452 4
1 2 4 1 2 40 4 Tb=1 6 1 6 1 61=3
1 4 2 1 4 2 0 1 154623 0 1
The product of Ta and Tb gives the transform for the product of polynomials A and B. Let’s call the product polynomial C and transform of C as Tc.
3 · 2 6
6 · 4 3
0 · 4 0
Tc =1·3=3 (9)
0 · 1 0 3·1 3
3
55 1
=6· = (8)
Coefficients of the polynomial C, Ccoeff will be obtained by performing an inverse transform on Tc as shown in part (c) of this problem
1111116 6
1546233 1
1 4 2 1 4 20 1
Ccoeff =6·1 6 1 6 1 63=3 (10)
1 2 4 1 2 4 0 1 132645 3 1
Transforming 6 to -1 in mod 7 arithmetic we get the product polynomial C as
1·x5 +1·x4 +3·x3 +1·x2 +1·x1 +(−1)·x0 (11)
3 Problem 2.31
This problem presents a fast algorithm for computing the greatest common divisor (gcd) of two positive integers a and b. Before giving the algorithm we need to prove the following properties
2·gcd(a,b) ifa,bareeven 22
gcd(a, b) if a is odd, b is even 2
gcd(a,b) =
(a)If a and b are even numbers, 2 is surely a common divisor of a and b. Therefore the greatest common
divisorwillbe2timesthegcdofnumbers a and b. Ifaisoddandbiseven,weknowforsurethatbis 22
divisible by 2 while a is not. Therefore gcd(a,b) remains same as the gcd of a and b . The third property 2
follows from the fact that if a and b are odd, then (a-b) will be even. Since gcd(a,b) = gcd(a-b,b) and a-b is even now we can apply the second property to get the desired result.
(b) The recursive algorithm for gcd is given as
procedure gcd(a,b)
Input: Two n-bit integers a,b
Output: GCD of a and b
if a = b:
gcd(a−b,b) if a, b are odd 2
return a
else if (a
return 2
else if (a
else if (a is odd ∧ b is odd ∧ a > b): return gcd(a−b,b)
2
else if (a is odd ∧ b is odd ∧ a < b): return gcd(a,b−a)
2
(c)Complexity analysis of the algorithm: Assume that a and b are n-bit numbers. Size of a and b is 2n bits. Out of 4 if conditions, every one except the case when a is odd and b is even, decreases the size of a and b to 2n − 2 bits whereas that case decreases it to 2n − 1 bits. Each of the operations is constant time operation as we are dividing or multiplying the numbers by 2. For two cases subtraction of two n-bit numbers are involved which is c·n where n is the number of bits of the operand. Therefore in the worst case
is even ∧ b is even): · gcd(a, b)
2
is odd ∧ b is even): return gcd(a,b)
22
4
the recurrence is given by
T(2n) = T(2n−1) = T(2n − 2) = T(2n−3) =
which is O(n2). Compared to the O(n3) running time of Euclid’s the divide-and-conquer algorithm is faster. 4 Problem 4.4
Counterexample is shown in Figure 1. Using the proposed approach we obtain the shortest cycle as {3, 4, 5, 6, 3} but the shortest cycle in this case is {2,3,6,2}. The depth first search labels for each vertex i : i ∈ (1..6) is i − 1.
T(1)+c Using substitution, we can obtain T(2n) as
... T(2) =
T(2n−1)+cn
T(2n−2)+cn T(2n−3)+c(n−1)bothoperandsaren-1bits T(2n−4)+c(n−1)
n
T (2n) = 2c · i (12) i=1
Figure 1: Counterexample
5 Problem 4.7
Given a directed graph G = (V,E) with no constraints on edges along with a specific node s ∈ V and a tree T = (V,Eˆ) where Eˆ ⊆ E, we have to give a linear time algorithm to check whether T is a shortest path tree for G with starting point S. In this problem the idea is to effectively make use of shortest path distances given on the associated shortest path tree T. Obtain the shortest path distance from each vertex of the tree and annotate the shortest path distance on each vertex of the graph G. Now run subroutine update (Bellman-Ford algorithm page 117) on every edge of the graph G. By definition of shortest path distances, update should not change any shortest path distance on each node. If update changes the shortest path
5
distance (dist) of any vertex, then the given tree is not a shortest path tree. Complexity of the algorithm is O(E ).
procedure verify-tree(s,T)
Input: s∈V,T=(V,Eˆ)
Output: true if T is a shortest path tree
false otherwise
Q = [s] (queue containing v)
while Q is not empty
u = eject(Q)
for each edge (u,v) ∈ Eˆ:
dist(v) = dist(u) + l(u,v)
inject(Q,v)
E = E-(u,v)
for each edge (u,v) ∈ E temp = dist(v) update(e)
if temp ̸= dist(v):
return false
return true
6 Problem 4.10
Given a directed graph with (possibly negative) weighted edges, in which the shortest path between any two vertices is guaranteed to have at most k edgse. We have to give an algorithm to find the shortest path between two vertices u and v in O(k|E|) time. The algorithm we present here is a variant of Bellman-Ford algorithm.
procedure shortest-paths-k(G,l,s)
Input: Directed graph G=(V,E):
edge lengths {le : e ∈ E} with no negative cycles:
vertex u ∈ V
Output: For all vertices v reachable from u,dist(v) is
set to shortest path distance from u for all vertices v ∈ V
dist(v) = ∞
prev(v) = nil
dist(u) = 0
repeat k times:
for all e ∈ E: update(e)
Complexity Analysis: The algorithm is a modification of Bellman-Ford with shortest path lengths known as k from the problem definition. Complexity of the algorithm is O(k|E|).
6