Feedback. Answering the questions

1. Feedback

2. Answering the questions

• Take 10 minutes for reading the ALL QUESTIONS
• Start answering the easiest question
• Answer only 3 questions in given 4 questions

3.

4. 1. COMPLEXITY AND HASH TABLES

5.

6.

• Answer:O(log​(n)*log(n)*n)

7.

Outer Loop (j):
•The outer loop starts with j = n.
•In each iteration, j is divided by 2:
n,n/2,n/4,n/8,…,1.
•The number of iterations of the outer
loop is approximately log​(n).
Middle Loop (i):
•In each iteration, i is multiplied by 2:
1,2,4,8,…,2m.
•The loop continues as long as i<n.
•The number of iterations of the middle loop is
approximately log​(n)
Inner Loop (k):
•The inner loop starts with k = j.
•In each iteration, k is incremented by 2: j,j+2,j+4,…,kend​.
•In the worst case, when j is small (close to 1), the number of iterations will be
approximately (n−j)/2, which is close to n/2 or O(n).
Answer:O(log​(n)*log(n)*n)

8.

Solution :It differs as this new definitions gives a lower bound while O notation
gives an upper bound.The key difference between Ω-notation and O-notation
lies in the inequality:
• O-notation provides an upper bound on the growth rate of a function. It says
that f(n) grows no faster than a constant multiple of g(n) for sufficiently large n.
• Ω-notation provides a lower bound on the growth rate of a function. It says
that f(n) grows at least as fast as a constant multiple of g(n) for sufficiently
large n.

9.

10.

Multiply k both sides of the inequality
k⋅f(n)≥k⋅c⋅g(n)
Let’s define c′=k⋅c.
Since both k and c are positive, c′>0.
So we now have:
(k∗f)(n)=k⋅f(n)≥c′⋅g(n)for all n≥n0

11.

12. (b) Explain briefly what the load factor of a hash table is and why it is important. (2)

Solution: The load factor of a hash table is alpha = n/N
where n is the number of entries in a map of size N. (1 point).
It is important because the complexity of hash table operations depends on
the load factor/it illustrates the trade-off between time and space.
ADDITIONAL POINTS:A higher load factor can lead to more collisions,
which may increase the time complexity (especially in open addressing
schemes). Conversely, a very low load factor may waste memory

13. c.Recall that hash tables are an implementation of the Map ADT. Explain how the average case of the search, insert, and delete

operation a separate chaining hash table compares to the one of a
Binary Search
Tree and briefly explain its assumptions.
Solution:
• A separate chaining hash table has (amortized) constant average time in
each case. (1 point)
• Binary Search Trees have an average case time of log n/log n/log n for the
three operations. (1 point )
• This assumes the uniform hashing assumption that a reasonable load
factor is maintained/resizing is put in place. (1 point).
Operation
Hash Table (Separate Chaining)
Binary Search Tree (Average)
Search
O(1)
O(logn)
Insert
O(1)
O(logn)
Delete
O(1)
O(logn)

14.

15. Solution:

16. Explanation

17.

18.

19.

Answer

20. TEXT ALGORITHMS AND COMPRESSION

21.

22.

23.

24.

25.

26.

27.

Solution:

28.

Solution:

29. 3. GRAPHS AND GRAPH ALGORITHMS

30.

31.

32.

33.

Articulation Points:
•C: Removing C disconnects E and F from the rest of the graph.
•E: Removing E disconnects F.

34.

Solution:
•A spanning tree connects all vertices with the minimum number of edges and no
cycles.
•A leaf in a tree is a vertex connected by only one edge—removing it does not
disconnect the rest of the tree (or graph).
•An articulation point, by definition, is a vertex whose removal increases the
number of connected components.
•Therefore, if a vertex is an articulation point, it must connect multiple parts of
the graph—and in a tree, this means it has at least two children, i.e., it is an
internal node.
•So, articulation points can never be leaves in any spanning tree.

35. Solution:

36. 4. BALANCED TREES AND AMORTISATION

37.

38.

Solution:
1. Lower bound — ⌊log2 n⌋ i.e O(log n), when the tree is perfectly
balanced.
2. Upperbound – n i.e O(n), when the tree is a single path.

39.

Visual Example for Lower Bound (Balanced BST - Close to
Complete Binary Tree):
Visual Example for Upper Bound

40.

Solution:
• For any internal node of the tree,
• the keys found in its left sub-tree must be smaller than the key in the
node,
• while the keys found in the right sub-tree must be greater (or equal)
to the key in the node.
• The search algorithm needs only traverse one path of the tree, which
can speed up the search in balanced cases, but does not help in
degenerate cases of linear depth.
Balanced BST
DEGENRATED CASE

41.

Solution :
• The internal nodes of red-black trees store an additional bit of “colour”.
• The invariants state that a red node may only have black children (this
includes leaves), the root of the tree must be black,and
• The number of black nodes is the same on all paths from the root to leaves
(as well as the BST invariant).

42.

Solution

43.

How it works

44.

45.

Solution :
• Amortised complexity is a way to analyze the average cost per
operation over a sequence of operations — even if some individual
operations are expensive.
• Instead of looking at just the worst-case time for one operation, we
spread the cost of expensive operations across many cheaper ones to
get a more realistic long-term average.

46.

Solution:
Example of a data structure:Dynamic Array
Add an element to the end
Type of Bound
Time Complexity
Worst-case
O(n)
Amortised
O(1)
Why?
•Worst-case happens when the array is full and needs to resize
(usually doubles in size):
• It allocates a new array and copies all elements: takes O(n)
time.
•Amortised cost is still O(1) because:
• Most inserts are cheap.
• Cost of copying is spread across all future insertions.