Which traversal technique does DFS primarily employ when traversing a graph?

  • Breadth-First Search (BFS)
  • Level-Order Traversal
  • Post-order Traversal
  • Pre-order Traversal
DFS primarily employs Pre-order Traversal when traversing a graph. In Pre-order Traversal, the algorithm visits the root node, then recursively performs Pre-order Traversal on the left subtree and the right subtree.

In the LIS problem, "patience" refers to the ability to _______ and _______ sequences of numbers.

  • Merge, combine
  • Merge, divide
  • Split, combine
  • Split, merge
In the Longest Increasing Subsequence (LIS) problem, "patience" refers to the ability to split and combine sequences of numbers. The algorithm involves finding the longest increasing subsequence in a given sequence.

The patience sorting algorithm is a technique inspired by a card game called _______.

  • Go Fish
  • Poker
  • Rummy
  • Solitaire
The patience sorting algorithm is inspired by the card game Solitaire. In this algorithm, the process of sorting is similar to organizing a deck of cards in the game of Solitaire.

What is the time complexity of the naive pattern matching algorithm in the worst-case scenario?

  • O(m * n)
  • O(m + n)
  • O(n log n)
  • O(n)
The worst-case time complexity of the naive pattern matching algorithm is O(m * n), where 'm' is the length of the pattern and 'n' is the length of the text. This is because, in the worst case, the algorithm may need to compare each character of the pattern with each character of the text.

Dijkstra's algorithm relies on the use of a _______ to keep track of the shortest distances to each node.

  • Hash Table
  • Linked List
  • Priority Queue
  • Stack
Dijkstra's algorithm relies on the use of a priority queue to keep track of the shortest distances to each node efficiently. The priority queue ensures that nodes are processed in order of increasing distance, optimizing the exploration of the graph and helping in finding the shortest paths.

The time complexity of the dynamic programming approach for the longest common substring problem is _______.

  • O(n log n)
  • O(n)
  • O(n^2)
  • O(nm)
The time complexity of the dynamic programming approach for the longest common substring problem is O(nm), where 'n' and 'm' are the lengths of the input strings. The algorithm uses a table of size n x m to store intermediate results, leading to a quadratic time complexity.

In which pattern matching algorithm is a prefix table or failure function used to optimize the search process?

  • Boyer-Moore Algorithm
  • Brute Force Algorithm
  • Knuth-Morris-Pratt Algorithm
  • Rabin-Karp Algorithm
The Knuth-Morris-Pratt Algorithm uses a prefix table or failure function to optimize the search process. This allows the algorithm to skip unnecessary comparisons by taking advantage of the information about the pattern's own structure.

Discuss the significance of the optimal substructure property in dynamic programming solutions for the Knapsack Problem.

  • It ensures that the problem can be divided into smaller, overlapping subproblems, making it suitable for dynamic programming.
  • It ensures that the solution to a larger problem can be constructed from optimal solutions of its overlapping subproblems.
  • It implies that the problem does not have overlapping subproblems.
  • It indicates that the Knapsack Problem has an efficient greedy solution.
The optimal substructure property in dynamic programming for the Knapsack Problem ensures that the solution to the overall problem can be constructed from optimal solutions to its overlapping subproblems, making it suitable for dynamic programming approaches.

In certain applications such as plagiarism detection, the longest common substring problem helps identify _______ between documents.

  • Connections
  • Differences
  • Relationships
  • Similarities
In certain applications like plagiarism detection, the longest common substring problem helps identify similarities between documents. By finding the longest common substring, one can detect shared sequences of words or characters, aiding in identifying potential instances of plagiarism.

In binary search, the array must be _______ to ensure correct results.

  • Reversed
  • Shuffled
  • Sorted
  • Unsorted
In binary search, the array must be sorted to ensure correct results. Binary search relies on the property of a sorted array to efficiently eliminate half of the remaining elements in each step.