Fundamentals of Algorithms and Design

What is the time complexity of a binary search algorithm?

• O(n)

• O(log n)

• O(1)

• O(n log n)

Explain the difference between Big O, Big Θ, and Big Ω notations.

• Big O is for lower bounds, Big Θ is for upper bounds, and Big Ω is for tight bounds.

• Big O is for upper bounds, Big Θ is for tight bounds, and Big Ω is for lower bounds.

• Big O is for average case, Big Θ is for worst case, and Big Ω is for best case.

• Big O is for constant time, Big Θ is for linear time, and Big Ω is for exponential time.

Which data structure would you use to implement a priority queue?

• Linked list

• Binary heap

• Stack

• Array

Aarav is designing a recursive function to help him sort a list of books. He realizes that the function uses O(n) space to store the intermediate results. What is the space complexity of Aarav's recursive function?

• O(n^2)

• O(1)

• O(n)

• O(log n)

Describe the process of depth-first search (DFS) in graph traversal.

• DFS only explores the shortest path in a graph.

• DFS visits all nodes in a random order.

• DFS requires a queue to keep track of nodes.

• Depth-first search (DFS) explores a graph by going as deep as possible along each branch before backtracking.

What is the primary advantage of using a hash table over a binary search tree?

• Faster average-case time complexity for lookups, insertions, and deletions.

• Easier to implement than a binary search tree.

• More efficient memory usage than a binary search tree.

• Better suited for ordered data than a binary search tree.

How does the merge sort algorithm achieve its time complexity of O(n log n)?

• Merge sort has a time complexity of O(n) due to its linear merging process.

• Merge sort achieves O(n log n) by sorting the array in a single pass.

• Merge sort achieves a time complexity of O(n log n) by recursively dividing the array and merging sorted halves.

• Merge sort uses a bubble sort technique to achieve O(n log n).

In what scenario would you choose a linked list over an array?

• When the size of the data is fixed.

• When memory efficiency is a priority.

• When frequent insertions and deletions are needed.

• When random access is required.

Explain the breadth-first search (BFS) algorithm and its applications.

• BFS is used in applications such as finding the shortest path in unweighted graphs, web crawling, and peer-to-peer networks.

• BFS is a depth-first search variant.

• BFS is primarily used for sorting algorithms.

• BFS is only applicable to weighted graphs.

What is the significance of the Master Theorem in analyzing recursive algorithms?

• The Master Theorem simplifies the analysis of recursive algorithms by providing a systematic way to determine their time complexity.

• The Master Theorem is primarily focused on sorting algorithms.

• The Master Theorem is used to optimize iterative algorithms.

• The Master Theorem provides a way to visualize recursive algorithms.