BRAC UNIVERSITY
Department of Computer Science and Engineering
Examination: Mid Semester Exam Semester: Spring 2023
Duration: 1 Hour 30 Minutes Full Marks: 40
CSE 221: Algorithms
Answer the following questions.
Figures in the right margin indicate marks.
Name: ID: Section:
1 a. In the primary scholarship exam in Bangladesh, four lakh (n=4,00,000) students take part but only 02
CO3 the top 5 0 students are given an award.
Write the asymptotic time complexity to give the awards. Assume that each award is given in a
constant time.
O(nlogn+50) = O(nlogn)
Ans:
O(1), Θ(1), constant sorting selecting
b. Write the asymptotic time complexity of the following function. 04
CO1
1. def contains_duplicates(elements):
2. for outer in range(len(elements)):
3. for inner in range(len(elements)):
4. if outer == inner:
5. continue
6.
7. if elements[outer] == elements[inner]:
8. return True
9.
10. return False
Ans:
O(n2), Θ(n2)
c. Express the following running time 𝑇(𝑛) with an asymptotic bound. 04
CO3 𝑛
𝑇(𝑛) = 625𝑇( ) + 𝑛
3
5
Any method is acceptable as long as you show calculations.
Ans: Θ(n4)
Master theorem:
a=625, b=5
logba=4
f(n)=n3
n to the power of logba = n4
n to the power of logba is asymptotically larger than f(n)
So the solution is Case 1 of the master theorem
Solution: Θ(n4)
2 a. You are given an array containing 𝑁 distinct integers in a wave-like sequence. Meaning, the
CO4 numbers in the beginning are in ascending order, and after a specific position, they are in
descending order. For example: [1, 3, 4, 5, 9, 6, 2, -1]
You have to find the maximum number of this sequence. Can you devise an efficient algorithm
such that the time complexity will be less than 𝑂(𝑁)?
i) Present your solution idea as a pseudocode/ python code/ flowchart/ step-by-step 04
instructions/ logical explanation in one-two paragraphs.
ii) Write the time complexity of your algorithm. 01
Solution outline
Using binary partition
A[mid-1] < A[mid] < A[mid+1]: ans is in range (mid+1,end)
A[mid-1] > A[mid] > A[mid+1]: ans is in range (start,mid-1)
A[mid-1] < A[mid] > A[mid+1]: ans is A[mid]
Complexity: O(log2N)
Using ternary partition
find_max(start, end)
● Calc mid1, mid2
● A[mid1] < A[mid2]: ans= max( find_max(mid1+1,mid2), find_max(mid2+1,end) )
● A[mid1] > A[mid2]: ans= max( find_max(start, mid1), find_max(mid1+1,mid2-1) )
Complexity: O( )
b. In case of sorting an array in ascending order, Bubble Sort extends a sorted subarray at the 02
CO2 rightmost side and, Insertion Sort extends a sorted subarray at the leftmost side. Your friend, Jimmy
was told to find the first five largest and smallest numbers from a list of 𝑁 distinct integers (
𝑁 > 10). To solve the task, he modified the Bubble sort and Insertion sort algorithm for only 5
iterations and used the rightmost and leftmost 5 numbers as the 5 largest and smallest numbers
respectively. Do you support his strategy? Explain with logical reasons.
b) There are several reasons why this strategy may not always yield correct results:
1. Incomplete Sorting
2. Lack of Comparison
3. Unsorted Middle Elements
4. Inefficient Approach: Jimmy's strategy is not efficient, especially when the list size (N) is large. Both Bubble Sort and Insertion Sort have
average-case time complexities of O(N^2) and are not the best choices for sorting large datasets.
Ans : This scheme might work for finding out the largest 5 elements. But, it won't work for finding
out the smallest 5 elements as the insertion sort only sorts the first k elements at the k-th step. If the
minimum element is after the 5th index, the algorithm will never reach that element.
c. While sorting a list of 10 integers in ascending order using Quick Sort, after the first partition 02
CO2 (using the first element as a pivot), the list looks like this : [13, 11, 19, 7, 23, 37, 29, 53, 59, 41].
Which element was the pivot before partitioning?
Explain your answer in brief.
Ans : 23. As all the elements before it are smaller than 23, and all the elements after it are bigger
than 23. This condition is not satisfied for any other element.
d. Consider the scenario in 2(c). Show how the list will look like after partitioning using 13 as the 01
CO2 pivot.
Ans : [7, 11, 13, 19, 23, 37, 29, 53, 59, 41]. (Showing detailed steps is appreciated. But, as this
question weighs 1 point, explanation is not mandatory.)
d) [11,7,13,19,23,29,37,53,59,41]
3 CO4 You are the coach of the renowned football team “Real Madrid”. Your team is behind one goal and
there is still some time left to back in the game by scoring a goal. Benzema is your main striker and
if you can pass the ball to him he will give the goal for sure. Currently the ball is in your
goalkeeper’s (Courtois) hand. So, your main target should be Passing the ball in minimum steps
from Courtois to Benzema as the time left is very low.
Courtois can pass the ball to Rudiger or Alaba
Rudiger can pass the ball to Modric
Alaba can pass the ball to Modric, Hazard or Nacho
Modric can pass the ball to Benzema
Hazard can pass the ball to Kroos
Nacho can pass the ball to Vini
Kroos can pass the ball to Benzema
Vini can pass the ball to Benzema
Now answer the following questions.
a) Using a suitable algorithm, find the minimum number of passes your team will give to 07
reach the ball from Courtois to Benzema. Mention the name of the algorithm, Show each
step of the simulation properly to find out the minimum number of passes.
b) Find out the players who are required for this minimum number of passes scenario. 03
Ans :
(a)
They Have to first draw a Graph.
Name of the Algorithm : BFS
Steps : Queue_Order : C R A M H N B K V (There can be multiple orders)
Total Number of passes : 3 ( Can be seen from BFS Tree)
(b)
Minimum Path : Courtois → Rudiger → Modric → Benzema
OR
Courtois → Alaba → Modric → Benzema
Answer only one of 4, 4(or)
4 Suppose the company, "Sparkling Ideas," has been new in the market for the past few years and
you work as a financial analyst hired for this company.
You have been provided a list of the company’s monthly incomes over the last year. However, the
incomes are mixed with positive and negative figures, which indicates the company has faced some
difficulties during certain months. The company's CFO has a special skill to identify the trend in
the company's income details, which helps her make informed decisions. She believes that there is
a particular set of consecutive months where the company earns the most, and she wants you to
find out which one(s) it is.
Your task is to find the maximum earnings from the given monthly incomes and determine in
which part of the year the company earned the most.
Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec
7 -15 9 -4 12 -8 3 -11 16 -2 6 -10
The figures are in millions of USD.
a) Try to think of an efficient algorithm to solve this problem and provide the result in terms
of the starting and ending months, along with the corresponding total income. Show a
CO4 07
simulation of your algorithm.
b) Calculate the time complexity of your algorithm. Show proper mathematical logic.
CO4
03
S 4. a) Maximum Sum Subarray
o
l
Mont Mar Apr May Jun Jul Aug Sep Oct Nov Total
h
Earn. 9 -4 12 -8 3 -11 16 -2 6 21
b) If Kadane is applied then O(n)
or,
4 or Inspired by Karatsuba's algorithm for multiplying integers, your friend has come up with the
following divide-and-conquer algorithm for squaring 𝑛-digit numbers. Pseudocode for the
algorithm is given below. Your job is to fill in the details. You may assume that 𝑛 is a power of two.
Now carefully read the algorithm above, and answer the following questions.
0.5
i) Write 𝑥 in terms of 𝑎 and 𝑏. Looking at lines 4 and 5 of the algorithm should help.
2 2 2
ii) Square your answer from (i). The formula (𝑚 + 𝑛) = 𝑚 + 2𝑚𝑛 + 𝑛 should help. 0.5
iii) Fill in the blank in line 8. Your answer should involve a and b in some way. The idea is to
2 2
compute a square that, along with 𝑎 and 𝑏 , helps you compute 2𝑎𝑏. You may want to 02
think about questions (iii) and (iv) at the same time.
CO4 iv) Fill in the blank in line 9. Your answer should involve 𝑆1, 𝑆2, and 𝑆3 in such a way that 𝑃
03
equals 2𝑎𝑏.
v) Fill in the blank in line 10.
vi) Write the running time of your algorithm above. 01
vii) Say you have another algorithm KARAT-SQUARE-2(𝑥) that takes an n-digit number and 01
squares it by recursively squaring six 𝑛/3-digit numbers, and combining them in 𝑂(𝑛)
time. Which algorithm is asymptotically faster: KARAT-SQUARE(𝑥) or 02
KARAT-SQUARE-2(𝑥)?
i) Anything equivalent to “x=10^(n/2)a+b” is worth 0.5 points. Anything else is worth 0 points.
ii) x^2=((10^(n/2)a+b)^2=10^n*a + 10^(n/2)*2ab+b^2. Anything equivalent to this is worth 0.5
points. Anything else is worth 0 points.
iii) and iv) There are multiple possible answer pairs for (iii) and (iv). I’m putting down the ones I
think are the most “natural”.
iii) (a+b), iv) S3-S1-S2
Or
iii) (a-b), iv) S1+S2-S3
In general any linear time computation involving a, b, S1, S2, and S3 that lead to P being equal to
2ab is worth the full (2+3) points. If P does not equal 2ab, then no points should be awarded.
v) S1*10^n+P*10^n/2+S2. Anything else is worth 0 points.
vi) Anything equivalent to O(n^{log_2 (3)} or \Theta(n^{log_2 (3)} is worth the full points.
vii) The second algorithm takes n^{log_3 (6)}, so it’s slower. The student should write down the
correct running time, then compare between their answer for vi) and conclude that the newer
algorithm is slower to get the full 2 points.
BRAC UNIVERSITY
Department of Computer Science and Engineering
Examination: Mid Semester Exam Semester: Spring 2023
Duration: 1 Hour 30 Minutes Full Marks: 40
CSE 221: Algorithms
Answer the following questions.
Figures in the right margin indicate marks.
Name: ID: Section:
1 a. In the primary scholarship exam in Bangladesh, two lakh (n=2,00,000) students take part but only 02
CO3 the top 25 students are given an award.
Write the asymptotic time complexity to give the awards. Assume that each award is given in a
constant time.
O(1), Θ(1), constant
b. Write the asymptotic time complexity of the following function. 04
CO1
1. def cumulative_sum(elem):
2. for outer in range(len(elem)):
3. for inner in range(outer+1,len(elem)):
4. elem[outer]= elem[outer] + elem[inner]
5.
6. return elem
Ans:
O(n2), Θ(n2)
c. Express the following running time 𝑇(𝑛) with an asymptotic bound. 04
CO3 𝑇(𝑛) = 25𝑇( ) + 𝑛
𝑛 3
5
Any method is acceptable as long as you show calculations.
Ans: Θ(n3)
Master theorem:
a=25, b=5
logba=2
f(n)=n3
n to the power of logba = n2
f(n) is asymptotically larger than n to the power of logba
So the solution is Case 3 of the master theorem
Solution: Θ(n3)
2 a. You are given an array containing 𝑁 distinct integers in a wave-like sequence. Meaning, the
CO4 numbers in the beginning are in descending order, and after a specific position, they are in
ascending order. For example: [9, 7, 6, 4, 2, 1, 3, 5, 8]
You have to find the minimum number of this sequence. Can you devise an efficient algorithm such
that the time complexity will be less than 𝑂(𝑁)?
b) Present your solution idea as a pseudocode/ python code/ flowchart/ step-by-step 04
instructions/ logical explanation in one-two paragraphs.
c) Write the time complexity of your algorithm. 01
Solution outline
Using binary partition
A[mid-1] < A[mid] < A[mid+1]: ans is in range (start,mid-1)
A[mid-1] > A[mid] > A[mid+1]: ans is in range (mid+1,end)
A[mid-1] > A[mid] < A[mid+1]: ans is A[mid]
Complexity: O(log2N)
Using ternary partition
find_min(start, end)
● Calc mid1, mid2
● A[mid1] < A[mid2]: ans= min( find_min(start, mid1), find_max(mid1+1,mid2-1) )
● A[mid1] > A[mid2]: ans= min( find_min(mid1+1,mid2), find_max(mid2+1,end) )
Complexity: O( )
b. In case of sorting an array in ascending order, Bubble Sort extends a sorted subarray at the 02
CO2 rightmost side and, Insertion Sort extends a sorted subarray at the leftmost side. Your friend, Jimmy
was told to find the first five largest and smallest numbers from a list of 𝑁 distinct integers (
𝑁 > 10). To solve the task, he modified the Bubble sort and Insertion sort algorithm for only 5
iterations and used the rightmost and leftmost 5 numbers as the 5 largest and smallest numbers
respectively. Do you support his strategy?
Explain with logical reasons.
Ans : This scheme might work for finding out the largest 5 elements. But, it won't work for finding
out the smallest 5 elements as the insertion sort only sorts the first k elements at the k-th step. If the
minimum element is after the 5th index, the algorithm will never reach that element.
c. While sorting a list of 10 integers in ascending order using Quick Sort, after the first partition 02
CO2 (using the first element as a pivot), the list looks like this : [31, 19, 3, 17, 23, 37, 59, 61, 71, 43].
Which element was the pivot before partitioning?
Explain your answer in brief.
Ans : 37. As all the elements before it are smaller than 37, and all the elements after it are bigger
than 37. This condition is not satisfied for any other element.
d. Consider the scenario in 2(c). Show how the list will look like after partitioning using 31 as the 01
CO2 pivot.
Ans : [23, 19, 3, 17, 31, 37, 59, 61, 71, 43]. (Showing detailed steps is appreciated. But, as this
question weighs 1 point, explanation is not mandatory.)
3 CO4 You are the coach of the renowned football team “FC Barcelona”. Your team is behind one goal
and there is still some time left to back in the game by scoring a goal. Lewandowski is your main
striker and if you can pass the ball to him he will give the goal for sure. Currently the ball is in your
goalkeeper’s (Stegen) hand. So, your main target should be Passing the ball in minimum steps from
Stegen to Lewandowski as the time left is very low.
Stegen can pass the ball to Alba or Roberto
Alba can pass the ball to Torres
Roberto can pass the ball to Busquets or Jong
Busquets can pass the ball to Torres or Gavi
Jong can pass the ball to Gavi
Gavi can pass the ball to Lewandowski
Torres can pass the ball to Lewandowski
Now answer the following questions.
07
c) Using a suitable algorithm, find the minimum number of passes your team will give to
reach the ball from Stegen to Lewandowski. Mention the name of the algorithm, Show
each step of the simulation properly to find out the minimum number of passes. 03
d) Find out the players who are required for this minimum number of passes scenario.
Ans : (a)
(a)
They Have to first draw a Graph.
Name of the Algorithm : BFS
Steps : Queue_Order : S A R T B J L G (There can be multiple orders)
Total Number of passes : 3 ( Can be seen from BFS Tree)
(b) Minimum Path :
Stegen → Alba → Torres → Lewandowski (Only one solution)
Answer only one of 4, 4(or)
4 Suppose the company, "Sparkling Ideas," has been new in the market for the past few years and
you work as a financial analyst hired for this company.
You have been provided a list of the company’s monthly incomes over the last year. However, the
incomes are mixed with positive and negative figures, which indicates the company has faced some
difficulties during certain months. The company's CFO has a special skill to identify the trend in
the company's income details, which helps her make informed decisions. She believes that there is
a particular set of consecutive months where the company earns the most, and she wants you to
find out which one(s) it is.
Your task is to find the maximum earnings from the given monthly incomes and determine in
which part of the year the company earned the most.
Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec
17 -15 9 -4 12 -18 3 11 16 -2 -16 10
The figures are in millions of USD.
c) Try to think of an efficient algorithm to solve this problem and provide the result in terms
CO4 07
of the starting and ending months, along with the corresponding total income. Show a
simulation of your algorithm.
CO4
d) Calculate the time complexity of your algorithm. Show proper mathematical logic.
03
4. a) Maximum Sum Subarray
Month Jan Feb Mar Apr May Jun Jul Aug Sep Total
Earn 17 -15 9 -4 12 -18 3 11 16 31
b) If Kadane is applied then O(n)
or,
4 or Inspired by Karatsuba's algorithm for multiplying integers, your friend has come up with the
following divide-and-conquer algorithm for squaring 𝑛-digit numbers. Pseudocode for the
algorithm is given below. Your job is to fill in the details. You may assume that 𝑛 is a power of two.
Now carefully read the algorithm above, and answer the following questions.
0.5
viii) Write 𝑥 in terms of 𝑎 and 𝑏. Looking at lines 4 and 5 of the algorithm should help.
2 2 2
ix) Square your answer from (i). The formula (𝑚 + 𝑛) = 𝑚 + 2𝑚𝑛 + 𝑛 should help. 0.5
x) Fill in the blank in line 8. Your answer should involve a and b in some way. The idea is to
2 2
compute a square that, along with 𝑎 and 𝑏 , helps you compute 2𝑎𝑏. You may want to 02
think about questions (iii) and (iv) at the same time.
CO4 xi) Fill in the blank in line 9. Your answer should involve 𝑆1, 𝑆2, and 𝑆3 in such a way that 𝑃
03
equals 2𝑎𝑏.
xii) Fill in the blank in line 10.
xiii) Write the running time of your algorithm above. 01
xiv) Say you have another algorithm KARAT-SQUARE-2(𝑥) that takes an 𝑛-digit number and 01
squares it by recursively squaring six 𝑛/3-digit numbers, and combining them in 𝑂(𝑛)
time. Which algorithm is asymptotically faster: KARAT-SQUARE(𝑥) or 02
KARAT-SQUARE-2(𝑥)?
