CSCI 433 Midterm Exam 3
Spring 2023
November 5, 2024
Problem 1 (10 pts)
Given an array 𝐴[] of 𝑛 numbers and a number 𝑠, determine in 𝑂(𝑛) time if there are two
elements in 𝐴 whose sum is 𝑠. (Hint: Hashtable)
Bonus points (3 pts): determine in 𝑂(𝑛) time if there is a contiguous subarray 𝐴[𝑖, … , 𝑗]
whose sum is 𝑠.
Solution:
Algorithm 1 Two Sum
1: procedure TwoSum(𝐴, 𝑛, 𝑠)
2: complements ← empty set
3: for 𝑖 ← 0 to 𝑛 − 1 do
4: if 𝐴[𝑖] ∈ complements then
5: return True
6: else
7: complements ← complements ∪ 𝑠 − 𝐴[𝑖]
8: end if
9: end for
10: return False
11: end procedure
1
Algorithm 2 Contiguous Subarray with Given Sum
1: procedure HasContiguousSubarrayWithSum(𝑎𝑟𝑟, 𝑠)
2: if 𝑎𝑟𝑟 = [] or len(𝑎𝑟𝑟) < 1 then
3: return False
4: end if
5: 𝑝𝑟𝑒𝑓 𝑖𝑥_𝑠𝑢𝑚 ← 0
6: 𝑝𝑟𝑒𝑓 𝑖𝑥_𝑠𝑢𝑚_𝑑𝑖𝑐𝑡 ← {0 ∶ −1}
7: for 𝑖, 𝑛𝑢𝑚 in enumerate(𝑎𝑟𝑟) do
8: 𝑝𝑟𝑒𝑓 𝑖𝑥_𝑠𝑢𝑚 ← 𝑝𝑟𝑒𝑓 𝑖𝑥_𝑠𝑢𝑚 + 𝑛𝑢𝑚
9: if 𝑝𝑟𝑒𝑓 𝑖𝑥_𝑠𝑢𝑚 − 𝑠 in 𝑝𝑟𝑒𝑓 𝑖𝑥_𝑠𝑢𝑚_𝑑𝑖𝑐𝑡 then
10: return True
11: end if
12: if 𝑝𝑟𝑒𝑓 𝑖𝑥_𝑠𝑢𝑚 not in 𝑝𝑟𝑒𝑓 𝑖𝑥_𝑠𝑢𝑚_𝑑𝑖𝑐𝑡 then
13: 𝑝𝑟𝑒𝑓 𝑖𝑥_𝑠𝑢𝑚_𝑑𝑖𝑐𝑡[𝑝𝑟𝑒𝑓 𝑖𝑥_𝑠𝑢𝑚] ← 𝑖
14: end if
15: end for
16: return False
17: end procedure
Problem 2 (10 pts)
In the figure, each segment between two adjacent vertices has a length of 1 unit. How many
ways can you go from 𝐴 to 𝐵 along a sequence of 10 edge segments without touching a side or
vertex of the shaded square and without crossing the line that connects 𝐴 and 𝐵? Solve
the problem with a dynamic programming approach.
Answer: 37
2
Problem 3 (10 pts)
Describe a Θ(𝑚 + 𝑛) time algorithm to merge two min heaps (of size 𝑚 and 𝑛, respectively)
into a single min heap.
Answer: Create an empty heap of size and copy elements of both heaps to the new heap. Then
use a bottom-up process to construct the heap.
