[go: up one dir, main page]
Scribd
Upload
74 views4 pages

Exercise 3

These exercises are for students to practice algorithms and problem solving. The problems cover topics like asymptotics, divide-and-conquer algorithms, matrix multiplication, and the maximum subarray problem. Students are encouraged to collaborate and ask for help if needed. The problems range from easier to more challenging and come from previous exams and online sources.

Uploaded by

Khalil El Lejri
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
74 views4 pages

Exercise 3

These exercises are for students to practice algorithms and problem solving. The problems cover topics like asymptotics, divide-and-conquer algorithms, matrix multiplication, and the maximum subarray problem. Students are encouraged to collaborate and ask for help if needed. The problems range from easier to more challenging and come from previous exams and online sources.

Uploaded by

Khalil El Lejri
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

Exercise III, Algorithms 2022-2023

These exercises are for your own benefit. Feel free to collaborate and share your answers
with other students. There are many problems on this set, solve as many as you can and ask
for help if you get stuck for too long. Problems marked * are more difficult but also more
fun :).
These problems are taken from various sources at EPFL and on the Internet, too numer-
ous to cite individually.

1 Asymptotics and recursions


1 (Previous exam question) Give tight asymptotic bounds for the following recurrences (assuming
that T (1) = Θ(1)):

(i) T (n) = 3T (n/3) + Θ(1) (iv) T (n) = T (n/5) + 2T (2n/5) + Θ(n)

(ii) T (n) = 3T (n/3) + Θ(n) (v) T (n) = 25T (n/5) + Θ(n2 )

(iii) T (n) = 3T (n/3) + Θ(n2 )

2 (previous exam question)


Suppose you are choosing between the following five Divide-and-Conquer algorithms:

Algorithm A solves problems of size n by dividing (in constant time) them into two sub-
problems each of size n/2, recursively solving each subproblem, and then combining the
solutions in Θ(n3 ) time.

Algorithm B solves problems of size n by dividing (in constant time) them into nine sub-
problems each of size n/3, recursively solving each subproblem, and then combining the
solutions in Θ(n2 ) time.

Algorithm C solves problems of size n by dividing (in constant time) them into ten subproblems
each of size n/3, recursively solving each subproblem, and then combining the solutions in
Θ(n) time.

Algorithm D solves problems of size n by dividing (in constant time) them into eight sub-
problems each of size n/2, recursively solving each subproblem, and then combining the
solutions in constant time.

Algorithm E solves problems of size n by dividing (in constant time) them into two subprob-
lems each of size n − 1, recursively solving each subproblem, and then combining the
solutions in constant time.

What are the running times of each of these algorithms (in Θ notation), and which would
you choose?

Page 1 (of 4)

CS-250 Algorithms • Autumn 2022


Michael Kapralov
Maximum-Subarray Problem
3 In class we saw a divide-and-conquer algorithm for Maximum Subarray that runs in time
O(n log n). Illustrate how it works by showing/explaining the divide, conquer and merge step of
each subproblem when the algorithm is given the following input

-1 4 -1 -1 2 -5 2 1

Matrix Multiplication
4 (Exercise 4.2-1 in the book)
Use Strassen’s algorithm to compute the matrix product
  
1 3 6 8
7 5 4 2
Show your work.

5 (Exercise 4.2-3 in the book)


How would you modify Strassen’s algorithm to multiply n × n matrices in which n is not an
exact power of 2? Show that the resulting algorithm runs in time Θ(nlg 7 ).

6 (half *, Exercise 4.2-4 in the book)


What is the largest k such that if you can multiply 3 × 3 matrices using k multiplications (not
assuming commutativity of multiplication), then you can multiply n×n matrices in time o(nlg 7 )?
What would the running time of this algorithm be?
Note: lg x corresponds to the base 2 logarithm of x, i.e. lg x = log2 x.

Page 2 (of 4)

CS-250 Algorithms • Autumn 2022


Michael Kapralov
More general questions
7 (previous exam question) Consider the procedure Power that takes as input a number a, a
non-negative integer n and returns an :

Power(a, n)
1. if n = 0
2. return 1
3. if n = 1
4. return a
5. q = b n4 c + 1
6. return Power(a, q)· Power(a, n − q)

7a (10 pts) Let T (n) be the time it takes to invoke Power(a, n). Then the recurrence relation
of T (n) is
(
Θ(1) if n = 0 or n = 1,
T (n) =
T (bn/4c + 1) + T (n − bn/4c − 1) + Θ(1) if n ≥ 2.

Prove that T (n) = O(n) using the substitution method.


In your proof you may ignore the floor function, i.e., you can replace bn/4c by n/4.

Page 3 (of 4)

CS-250 Algorithms • Autumn 2022


Michael Kapralov
7b (15 pts) Design and analyze a modified procedure FastPower(a, n) that returns the
same value an but runs in time Θ(log n).

A solution that only works when n is a power of 2, i.e., n = 2k for some integer k ≥ 0,
gives partial credits.

(Note that an is not a basic instruction and should therefore not be used.)

8 (∗, Exercise 4.1-5 in the book) Use the following ideas to develop a nonrecursive, linear-time
algorithm for the maximum-subarray problem. Start at the left end of the array, and progress
toward the right, keeping track of the maximum subarray seen so far. Knowing a maximum
subarray of A[1 . . j], extend the answer to find a maximum subarray ending at index j + 1
by using the following observation: a maximum subarray of A[1 . . j + 1] is either a maximum
subarray of A[1 . . j] or a subarray of the form A[i . . j + 1], for some 1 ≤ i ≤ j + 1.
Determine a maximum subarray of the form A[i . . j + 1] in constant time based on knowing a
maximum subarray ending at index j.

Page 4 (of 4)

CS-250 Algorithms • Autumn 2022


Michael Kapralov

You might also like