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

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

f(n) ≤ 4g(n) for all n ≥ 1
f(n) ≥ 4g(n) for all n ≥ 136 (Correct answer)
Both A & B
none of the above

Correct answer: f(n) ≥ 4g(n) for all n ≥ 136

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))?

k = l.
k < l. (Correct answer)
k > l.
none of the above

Correct answer: k < l.

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?

f(n) = o(g(n)).
f(n) = Θ(g(n)). (Correct answer)
f(n) = ω(g(n)).
both a) and b) are always true

Correct answer: f(n) = Θ(g(n)).

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?

5 (Correct answer)
log 5.
5 log 5.
log(log 5).

Correct answer: 5

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

represents one of the most efficient ways of retrieving data.
may be applied to static hash tables.
means there are no collisions when retrieving data from the hash table.
all of the above (Correct answer)

Correct answer: all of the above

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.

Question 6: Among the listed algorithms, which one can be efficiently implemented without the need for a heap data structure?

Kruskal’s algorithm (Correct answer)
Prim’s algorithm
Huffman’s algorithm
Dijkstra’s algorithm

Correct answer: Kruskal’s algorithm

Kruskal's algorithm for finding a Minimum Spanning Tree (MST) primarily uses a Disjoint Set Union (DSU) data structure to efficiently detect cycles when adding edges. While a priority queue (often heap-based) can be used to sort edges, the algorithm can also be implemented by simply sorting all edges initially and then iterating through them, making the DSU the core data structure for its logic. In contrast, Prim's, Huffman's, and Dijkstra's algorithms inherently rely on a priority queue for efficient selection of the next element.

Question 7: Which of the subsequent graph-related issues cannot be resolved within a time frame that scales linearly concerning the total number of vertices and edges within the graph (i.e., O(m + n))?

determining a minimum spanning tree for a connected weighted graph (Correct answer)
determining a topological sort of the vertices for a directed acyclic graph
determining if a simple graph is connected
determining if a simple graph is bipartite

Correct answer: determining a minimum spanning tree for a connected weighted graph

Determining a Minimum Spanning Tree (MST) for a connected weighted graph, using algorithms like Prim's or Kruskal's, typically has a time complexity greater than O(m+n), such as O(m log n) or O(m + n log n). The other problems listed—topological sort, checking connectivity, and checking bipartiteness—can all be solved in linear time, O(m+n), using Breadth-First Search (BFS) or Depth-First Search (DFS).

Question 8: A binary search tree T is considered balanced when, for every node n present in T.

n’s left and right subtrees have heights that differ by at most one. (Correct answer)
n’s left and right subtrees have sizes that differ by at most one.
n’s left and right subtrees have equal height.
n’s left and right subtrees have equal size.

Correct answer: n’s left and right subtrees have heights that differ by at most one.

A binary search tree T is considered balanced when, for every node n in T, the heights of its left and right subtrees differ by at most one. This property is crucial for maintaining efficient search, insertion, and deletion operations, ensuring that the tree's height remains logarithmic with respect to the number of nodes. Examples of such trees include AVL trees and Red-Black trees.

Question 9: As long as the pivot is chosen in a certain way, Quicksort is assured to operate within a time complexity of O(n log n).

set to the median of the first, middle, and last array element.
set to the median of the array. (Correct answer)
randomly selected.
none of the above

Correct answer: set to the median of the array.

Quicksort's worst-case time complexity is O(n²), which occurs when the pivot consistently divides the array into highly unbalanced partitions. To guarantee O(n log n) performance, the pivot must consistently create balanced partitions. Choosing the true median of the array as the pivot ensures that the array is divided into two halves of roughly equal size, leading to the optimal O(n log n) time complexity.

Question 10: In Kruskal's algorithm, the decision that follows a greedy approach is to

add the edge of least cost to the forest so long as its addition does not create a cycle. (Correct answer)
add the vertex having least connection cost to the current tree.
remove the vertex having greatest connection cost from the tree.
remove the edge of greatest cost from the graph so long as its removal does not disconnect the graph.

Correct answer: add the edge of least cost to the forest so long as its addition does not create a cycle.

Kruskal's algorithm is a greedy algorithm that builds a Minimum Spanning Tree (MST) by iteratively adding the cheapest available edge. The core greedy decision is to always select the edge with the smallest weight from the remaining edges, provided that adding this edge does not form a cycle with the edges already selected. This process continues until n-1 edges have been added, forming the MST.

Question 11: Within dynamic programming, the term "memoization" pertains to

storing solutions to smaller subproblems for future look up when solving larger subproblems. (Correct answer)
the ability of a dynamic-programming algorithm to remember the current location in the
the ability to remember dynamic-programming recurrences for a comprehensive exam.
storing the dynamic-programming recurrence in a static array so that it may be applied at each level of recursion.

Correct answer: storing solutions to smaller subproblems for future look up when solving larger subproblems.

Memoization is a key technique in dynamic programming where the results of expensive function calls are stored (cached) and returned when the same inputs occur again. This prevents redundant computations of overlapping subproblems, significantly improving efficiency. By storing the solutions to smaller subproblems, the algorithm can simply look them up when needed for larger problems, rather than recomputing them.

Question 12: Except for one, all the following problems can be efficiently addressed using a dynamic-programming algorithm with a polynomial time complexity in the worst-case scenario.

Edit Distance Between Words
0-1 Knapsack (Correct answer)
Matrix Chain Multiplication.
Optimal Binary Search Tree

Correct answer: 0-1 Knapsack

The 0-1 Knapsack problem can be solved using dynamic programming in O(nW) time, where n is the number of items and W is the knapsack capacity. This is considered a pseudo-polynomial time complexity because it depends on the numerical value of W, not just the number of bits required to represent W (log W). Thus, if W is very large, this solution is not truly polynomial in the input size, unlike the other listed problems which have polynomial time complexities.

Question 13: The task of establishing whether a bipartite graph possesses a perfect matching is best transformed into which other problem?

finding a vertex cover in a simple graph.
finding a Hamilton cycle in a simple graph.
finding the longest path in a directed network.
finding the maximum flow in a directed network. (Correct answer)

Correct answer: finding the maximum flow in a directed network.

The problem of finding a perfect matching in a bipartite graph can be efficiently transformed into a maximum flow problem. By constructing a flow network with a source, a sink, and unit capacity edges, a perfect matching exists if and only if the maximum flow from the source to the sink equals the number of vertices in one partition of the bipartite graph. This reduction allows standard maximum flow algorithms to solve the matching problem.

Question 14: The problem of ascertaining whether a bipartite graph possesses a perfect matching finds its most natural reduction in the context of which other problem?

determining if there is a path from one vertex to another in a graph. (Correct answer)
finding the longest path in an acyclic directed network.
determining if a 0-1 Knapsack has a profit that exceeds some threshold.
finding the longest path in a directed network.

Correct answer: determining if there is a path from one vertex to another in a graph.

While the most common and efficient reduction for bipartite perfect matching is to a maximum flow problem, the core of many maximum flow algorithms involves repeatedly finding augmenting paths in a residual graph. The existence of such paths determines if the current matching can be improved. Therefore, at a foundational level, the ability to solve the perfect matching problem relies on the ability to determine if specific paths exist within a constructed network.

Question 15: Due to Professor Jones' proof establishing the absence of a polynomial-time algorithm for the 0-1 Knapsack optimization problem, it follows that the same conclusion holds for several other problems, except for which one?

determining if a graph has a Hamilton cycle.
determining if a set of integers has a subset that sums to some value t.
determining the longest path in a directed acyclic graph. (Correct answer)
determining if a Boolean formula has a satisfying assignment.

Correct answer: determining the longest path in a directed acyclic graph.

The 0-1 Knapsack optimization problem is NP-hard. If there's no polynomial-time algorithm for it, then any problem that can be reduced from it is also NP-hard. Hamilton Cycle, Subset Sum, and Boolean Satisfiability (3SAT) are all known NP-complete problems. However, finding the longest path in a *directed acyclic graph (DAG)* can be solved in polynomial time (O(V+E)) using dynamic programming, making it the exception among the listed problems.

Question 16: Which topic is the Subset Sum decision problem most closely linked to?

the Vertex Cover decision problem.
the 3SAT decision problem.
the Hamilton Cycle decision problem.
The Set Partition decision problem. (Correct answer)

Correct answer: The Set Partition decision problem.

The Subset Sum problem asks if a subset of a given set of integers sums to a specific target value. The Set Partition problem asks if a given set of integers can be partitioned into two subsets such that the sum of the numbers in each subset is equal. These two problems are very closely related and are often reduced to one another, making them strongly linked in complexity theory as classic NP-complete problems.

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

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