Exam questions

Question 1

Analysis of binary search algorithm

function binarySearch(𝑇[1. . 𝑛], 𝑥)
    𝑖 ←1
    j ←𝑛
    while 𝑖 < 𝑗 do
        𝑘 ← ⌊(𝑖+𝑗)/2⌋
        case 𝑥 < 𝑇[𝑘]: 𝑗 ← 𝑘 − 1
                 𝑥 = 𝑇 [𝑘]: 𝑖 ← 𝑘; 𝑗 ← 𝑘
                 𝑥 > 𝑇[𝑘]: 𝑖 ← 𝑘 + 1
    return 𝑖

Answer 1

find a function of the variable whose value decreases each time through the loop.

what decreases is the number of elements to be considered:
initially 𝑑 = 𝑛, with 𝑗 = 𝑛 and 𝑖 = 1
let 𝑑 = 𝑗 − 𝑖 + 1

when does the loop terminate?
when 𝑑 ≤ 1

Three possibilities in the loop (cases):
- Let 𝑑 and 𝑑‘ be the values of 𝑗 − 𝑖 + 1 before and after the iteration under consideration
- Let 𝑖,𝑗 and 𝑖′,𝑗′ be the values before and after the iteration

….

see pg 169 of VLs

Question 2

BONUS QUESTION

ECCENTRICITY

The eccentricity of a node is the length of the shortest path to the most distant node in the graph.

The diameter of a graph is the largest eccentricity of all nodes.

The radius of a graph is the smallest eccentricity of all nodes.

Describe an algorithm (pseudo code) to find the diameter and the radius of a graph. What is the complexity of the solution?

(Zoran 2020, question 6)

Question 3

Proof by induction:

Prove that for any positive integer n, n ≥ 0, it holds that:

0 ⋅ 0! + 1 ⋅ 1! + … + n ⋅ n! = (n + 1)! − 1

(Zoran 2020)

Question 4

QUESTION 2 or 3

Assume that we can find the product of two n-digit-numbers using some number of multiplications of n∕3-digit numbers (plus some additions, subtractions and shifts).

What is the largest number of n∕3-digit number multiplications that leads to an asymptotically faster algorithm than the n∕2 divide-and-conquer algorithm discussed in the lecture?

Provide and solve the recurrence equations.

(Zoran 2020)

Question 5

QUESTION 1

What is the running time of the following pseudo code expressed in the big O-notation?

1 for i ← 1 to n − 1 do O(n-1) → O(n)
2 j ← i + 1 O(1)
3 while j ≤ n do O(n+1) → O(n)
4 for k ← 2j to 2n do
5 print i
6 j ← j + 1

Put the running time in order together with: O(nlogn), O(n^3), O(e^n), O(n^n), O(n^logn).

(Zoran 2020)

Question 6

QUESTION 2 or 3

Describe the differences in solution strategies between the Knapsack variant in which a fraction of an object is allowed to be packed in comparison to the variant in which only entire objects of integer weight are allowed to be packed. Be prepared to derive the computational complexity of the two algorithms.

(Zoran 2020)

Question 7

QUESTION 4
GRAPHS

Provide an algorithm to find the longest path in a directed acyclic graph.

What is the computational complexity of the algorithm?

Explain the relation of this problem to the alignment of sequences (global and local).

(Zoran 2020)

Question 8

Which grows faster:

O(n) or O(nlog(n))?

Answer 8

O(nlog(n))

Question 9

List in order of best time complexity:

O(__)

• n
• nlogn
• 2ⁿ
• 1
• n!
• n²
• logn

Answer 9

• 1
• logn
• n
• nlogn
• n²
• 2ⁿ
• n!

Question 10

QUESTION 1

Which is bound above by which? Prove.

• n^logn
• nⁿ

(2022)

Question 11

QUESTION 1

Which is bound above by which? Prove.

• nlogn
• n³

(2022)

Question 12

QUESTION 1

Summation problem and analysis of time complexity.

For i from 1 to n^3:
for j from i+1 to n^3
k <- n-3
while k>n+4
print(i)

What is the complexity? What is the output for k?

Question 13

QUESTION 1

For i <- i to n^2 do
For j <- i + 1 to n do
Print j
For k <- n to n+1 do
Print i

• What is the output?
• Write the summations and solve one/expand it.

Question 14

QUESTION 2/3

Describe the differences in solution strategies between the Knapsack variant in which a fraction of an object is allowed to be packed in comparison to the variant in which only entire objects of integer weight are allowed to be packed.

Be prepared to derive the computational complexity of the two algorithms.

(2020 Zoran)

Question 15

QUESTION 1