Free Bachelor of Science in Computer Science: Algorithms and Data Structures Questions and Answers

Question 1

Which of the provided expressions definitively indicates the validity of the assertion f(n) = Ω(g(n))?

Accepted Answer

f(n) ≥ 4g(n) for all n ≥ 136

Answer

The notation f(n) = Ω(g(n)) (Big-Omega notation) means that f(n) grows at least as fast as g(n). Formally, it implies there exist positive constants c and n₀ such that f(n) ≥ c * g(n) for all n ≥ n₀. Option B directly aligns with this definition, showing that f(n) is bounded below by a constant multiple (c=4) of g(n) for all sufficiently large n (n₀=136).

Question 2

If we let k represent the degree of polynomial p(n) and l represent the degree of polynomial q(n), what must be true when p(n) = o(q(n))?

Accepted Answer

k < l.

Answer

The notation p(n) = o(q(n)) (little-o notation) signifies that p(n) grows strictly slower than q(n) as n approaches infinity. For polynomials, this condition is met when the degree of p(n) is strictly less than the degree of q(n). Therefore, if k is the degree of p(n) and l is the degree of q(n), then k < l must be true.

Question 3

If both f(n) = O(g(n)) and f(n) = Ω(g(n)), what is a consistent and definite conclusion that can be drawn?

Accepted Answer

f(n) = Θ(g(n)).

Answer

Big-O notation (f(n) = O(g(n))) means f(n) grows no faster than g(n), while Big-Omega notation (f(n) = Ω(g(n))) means f(n) grows no slower than g(n). When both conditions are met, it implies that f(n) and g(n) grow at the same asymptotic rate, differing only by a constant factor. This combined condition is precisely what Big-Theta notation (f(n) = Θ(g(n))) represents, indicating an asymptotically tight bound.

Question 4

both a) and b) are always true
When a separate-chaining hash table possesses a load factor λ of 5, what value does the average chain length assume?

Accepted Answer

5

Answer

In a separate-chaining hash table, the load factor (λ) is defined as the ratio of the number of items (n) to the number of slots in the hash table (m), i.e., λ = n/m. The average chain length in a separate-chaining hash table is directly equal to its load factor. Therefore, if the load factor λ is 5, the average chain length is also 5.

Question 5

Flawless hashing technique

Accepted Answer

all of the above

Answer

Flawless hashing, also known as perfect hashing, is a technique where all searches take O(1) time in the worst case because there are no collisions. This makes it highly efficient for data retrieval. It is typically applied to static sets of keys, meaning the set of keys is known in advance and does not change, allowing for the construction of a hash function that guarantees no collisions.

BSCS - Bachelor of Science in Computer Science Practice Test

BSCS - Bachelor of Science in Computer Science Practice Test

Free Bachelor of Science in Computer Science: Algorithms and Data Structures Questions and Answers