CA
2022/2023 Academic year
Bachelor of Technology
Option : SWE
Course code/ Title: Credit value …4…..
CSE401/Algorithm and Complexity
Duration: 3hrs Date: 0912/2022 Venue: AA002
Course instructor(s) Mr. FOMAZOU TCHINDA
Instructions:
- OPENBOOK exam
Section A
Question 1: Algorithm analysis 20marks
1. Solve the following recurrences
𝑛
a. 𝑇(𝑛) = 4 × 𝑇 ( 4) + 𝑛2
𝑛
b. 𝑇(𝑛) = 4 × 𝑇 ( 3) + 𝑛3
𝑛
c. 𝑇(𝑛) = 4 × 𝑇 ( 2) + 𝑛𝑙𝑜𝑔𝑛
𝑛
d. T(n) = 4 × T ( 5) + 𝑛2.87
𝑛
e. T(n) = 36 × T (36) + 𝑙𝑜𝑔𝑛
2. Prove that:
a. 𝑛3 − 3𝑛2 − 𝑛 − 1 = 𝜃(𝑛3 )
b. 𝑛2 = 𝑂(2𝑛 )
3. Suppose you have algorithms with the five running times listed below. (Assume these are the exact
running times.) How much slower do each of these algorithms get when you (a) double the input
size, or (b) increase the input size by one?
(a) 𝑛2 (𝑏)𝑛3 (𝑐)100𝑛2 (𝑑) 𝑛𝑙𝑜𝑔𝑛 (𝑒)2𝑛
4. Consider the following code fragment:
Assume n is even. Let T(n) denote the number of times “foobar” is printed as a function of n.
a. Express T(n) as three nested summations.
b. Simplify the summation. Show your work.
5. We have 1,000 data items to store on 1,000 nodes. Each node can store copies of exactly three
different items. Propose a replication scheme to minimize data loss as nodes fail. What is the
expected number of data entries that get lost when three random nodes fail?
Question 2: Divide and conquer 10marks
1. We are given n wooden sticks, each of integer length, where the ith piece has length L[i]. We seek to
cut them so that we end up with k pieces of exactly the same length, in addition to other fragments.
Furthermore, we want these k pieces to be as large as possible.
Page 1|4
a. Given four wood sticks, of lengths L = {10, 6, 5, 3}, what are the largest sized pieces you can
get for k = 4? (Hint: the answer is not 3).
b. Give a correct and efficient algorithm that, for a given L and k, returns the maximum possible
length of the k equal pieces cut from the initial n sticks.
2. Extend the convolution-based string-matching algorithm described in the text to the case of pattern
matching with wildcard characters “*”, which match any character. For example, “sh*t” should
match both “shot” and “shut”.
Question 3: Troublemakers (greedy) 10 marks
Every school class has its troublemakers—those kids who can make the teacher’s life miserable. On his
own, a troublemaker is manageable, but when you put certain pairs of troublemakers together in the same
room, teaching a class becomes very hard. There are n kids in Mrs. Shaida’s math class, and there are m
pairs of troublemakers among them. The situation has gotten so bad that Mrs. Shaida has decided to split the
class into two classes. Help her do it in such a way that the number of troublemaker pairs is reduced by at
least a half.
Input
The first line of input gives the number of cases, N. N test cases Follow. Each one starts with a line containing n
(0≤n≤100) and m (0<m<5000). The next m lines will contain a pair of integers u and v meaning that when kids u and
v are in the same room, they make a troublemaker pair. Kids are numbered From 1 to n.
Output
For each test case, output one line containing “Case #x:” Followed by L—the number of kids who will be moved to a
different class (in a different room). The next line should list those kids. The total number of troublemaker pairs
in the two rooms must be at most m/2. IF that is impossible, print “Impossible.” instead of L and an
empty line afterwards.
Hint
A graph is used to represent the problem, where kids in Mrs. Shaida’s math class are represented as vertices, and there
are edges between each pair of troublemakers. Mrs. Shaida splits the class into two classes, s[0] and s[1], where the
number of kids in s[1] is less than the number of kids in s[0]. The method that Mrs. Shaida uses to split the class into
two classes is as Follows:
For kid i (1≤i≤n), numbers oF kids among kid 1 to kid i-1 who constitute a pair of troublemakers with kid i in s[0]
and s[1] are calculated. IF such a number in s[1] is less than such a number in s[0], the kid i is moved to s[1]; else the
kid i stays in s[0]. The greedy algorithm is as Follows.
Page 2|4
Question 4: Marks Distribution (Dynamic programming) 10mrks
In an examination. one student appeared in N subjects and has got total T marks. He has passed in all the N
subjects where the minimum mark for passing in each subject is P. You have to calculate the number of
ways the student can get the marks. For example, if N=3, T=34 and P=10, then the marks in the three
subjects could be as follows:
So there are 15 solutions. So F (3, 34, 10)=15.
Input
In the first line of the input, there will be a single positive integer K followed by K lines, each containing a single
test case. Each test case contains three positive integers denoting N, T, and P respectively. The values of N,
T. and P will be at most 70. You may assume that the final answer will fit in a standard 32-bit integer.
Output
For each input, print in a line the value of F (N, T, P)
Page 3|4
Hint
GOOD LUCK
Page 4|4
