Algorithms: Design, Analysis, and Complexity for Sixth Form College

Question 1

Which of the following is NOT a fundamental characteristic of an algorithm?

Accepted Answer

Unboundedness

Answer

Definiteness

Answer

Input-output relation

Answer

Effectivity

Question 2

Which of the following algorithm design paradigms involves breaking a problem down into smaller subproblems and recursively solving them?

Accepted Answer

Divide-and-Conquer

Answer

Dynamic Programming

Answer

Greedy

Answer

Branch-and-Bound

Question 3

Which of the following notations describes the upper bound of an algorithm's time complexity?

Accepted Answer

Big O

Answer

Big Omega

Answer

Big Theta

Answer

Big Little-o

Question 4

In Dijkstra's Algorithm, a min-heap data structure is employed to achieve which of the following?

Accepted Answer

Efficiently selecting the vertex with the minimum distance from the starting vertex.

Answer

Storing all distances from the starting vertex to every other vertex.

Answer

Validating whether the graph contains any negative-weight edges.

Answer

Computing the shortest path from the starting vertex to all other vertices.

Question 5

Which technique incorporates domain knowledge to guide the search process in heuristic search?

Accepted Answer

A* Search

Answer

Breadth-First Search

Answer

Depth-First Search

Answer

Uniform Cost Search

Question 6

Which of the following algorithm design techniques involves breaking a problem into overlapping subproblems and storing their solutions?

Accepted Answer

Dynamic Programming

Answer

Divide-and-Conquer

Answer

Greedy

Answer

Branch-and-Bound

Question 7

Binary trees are frequently employed in recursive algorithms to:

Accepted Answer

Execute a divide-and-conquer strategy.

Answer

Enhance the time efficiency of the algorithm.

Answer

Store data in a hierarchical structure.

Answer

Search for a specific element within a sorted list.

Question 8

What primary function does a hash function serve within a hash table?

Accepted Answer

Maps a key to a unique index in the table

Answer

Stores data in sorted order

Answer

Resolves collisions within the table

Answer

Enhances the efficiency of search operations

Question 9

Determine the time complexity of a nested loop with N iterations in both loops.

Accepted Answer

N^2

Answer

N

Answer

N^3

Answer

N^4

Question 10

Which sorting algorithm operates with a time complexity of O(n log n)?

Accepted Answer

Merge Sort

Answer

Bubble Sort

Answer

Insertion Sort

Answer

Selection Sort

Question 11

Describe the distinction between a greedy algorithm and a dynamic programming algorithm.

Accepted Answer

Greedy algorithms find local optimal solutions, while dynamic programming algorithms find global optimal solutions.

Answer

Greedy algorithms are faster than dynamic programming algorithms.

Answer

Dynamic programming algorithms are easier to implement than greedy algorithms.

Answer

There is no difference between greedy algorithms and dynamic programming algorithms.

Question 12

Which of the following is NOT a measure of algorithm efficiency?

Accepted Answer

Reliability

Answer

Time complexity

Answer

Space complexity

Answer

Scalability

Question 13

Identify the main difference between a depth-first search (DFS) and a breadth-first search (BFS).

Accepted Answer

DFS explores nodes in a stack-like manner, while BFS explores nodes in a queue-like manner.

Answer

DFS is more efficient than BFS.

Answer

BFS is more efficient than DFS.

Answer

DFS and BFS are equivalent algorithms.

Question 14

In algorithm analysis, what's the main goal of asymptotic analysis?

Accepted Answer

Comparing algorithm performance based on running times for varying input sizes, ignoring constant factors.

Answer

Optimizing code structure to reduce variables and improve readability.

Answer

Predicting algorithm performance on a given input using its behavior on smaller inputs.

Answer

Minimizing memory usage during algorithm execution, even for complex datasets.

Question 15

Which characteristic is unique to a greedy algorithm?

Accepted Answer

It prioritizes making locally optimal choices during each step of execution.

Answer

It consistently produces the optimal solution.

Answer

It requires a substantial amount of time to execute, often growing exponentially with the input size.

Answer

It may not always be able to find a solution, even if one exists.

Question 16

What is the time complexity of the binary search algorithm?

Accepted Answer

O(log n)

Answer

O(n)

Answer

O(n^2)

Answer

O(n!)

Question 17

Which of the following is not a sorting algorithm?

Accepted Answer

Binary search

Answer

Bubble sort

Answer

Merge sort

Answer

Quick sort

Question 18

What is the fundamental concept behind a divide-and-conquer algorithm?

Accepted Answer

Breaking down a problem into smaller subproblems

Answer

Combining multiple partial solutions into a complete solution

Answer

Iterating over a collection of elements in a sequential order

Answer

Finding the maximum value within a set of numbers

Question 19

Which data structure is commonly used to implement a queue?

Accepted Answer

Linked list

Answer

Array

Answer

Stack

Answer

Graph

Question 20

How does an algorithm differ from a program?

Accepted Answer

An algorithm is a well-defined set of steps, while a program is its implementation in a specific programming language.

Answer

An algorithm pertains to mathematical operations, whereas a program can be applied to any task.

Answer

Algorithms are written in natural language, while programs are written in programming languages.

Answer

There is no distinction between an algorithm and a program.

Question 21

Define the purpose of the asymptotic notation Big O.

Accepted Answer

Describes the upper bound of an algorithm's time complexity

Answer

Represents the exact time complexity of an algorithm

Answer

Compares the efficiency of different algorithms

Answer

Analyzes the space complexity of an algorithm

Question 22

Which aspect below is not a fundamental consideration in algorithm design?

Accepted Answer

Readability

Answer

Efficiency

Answer

Correctness

Answer

Simplicity

Question 23

What is the worst-case time complexity of the Bubble Sort algorithm?

Accepted Answer

O(n^2)

Answer

O(n)

Answer

O(n log n)

Answer

O(n^3)

Question 24

Which of the following is a characteristic of a poorly designed algorithm?

Accepted Answer

Reliance on overly expensive resources

Answer

Clarity in implementation

Answer

Efficiency in time and space usage

Answer

Correctness in functionality

Question 25

What is the primary goal of using a divide-and-conquer approach in algorithm design?

Accepted Answer

To decompose a complex problem into smaller, more manageable subproblems

Answer

To reduce the algorithm's memory usage

Answer

To increase the algorithm's time complexity

Question 26

Which of the following algorithms employs the principle of recursion?

Accepted Answer

Factorial calculation

Answer

Binary search

Answer

Linear search

Question 27

What is the worst-case space complexity of a depth-first search on a graph with 'n' vertices and 'e' edges?

Accepted Answer

O(n)

Answer

O(log n)

Answer

O(1)

Answer

O(n^2)

Question 28

Which data structure is most appropriate for implementing a priority queue, allowing for efficient insertion, deletion, and retrieval of elements based on their priority?

Accepted Answer

Heap

Answer

Stack

Answer

Array

Answer

Linked list

Question 29

What is a key difference between an algorithm and a heuristic?

Accepted Answer

An algorithm guarantees an optimal solution, while a heuristic may not always find the best answer.

Answer

A heuristic is generally faster than an algorithm

Answer

An algorithm is inherently more complex than a heuristic.

Question 30

Which of the following approaches will NOT improve the efficiency of an algorithm?

Accepted Answer

Employing the slowest data structure available

Answer

Avoiding unnecessary recursion

Answer

Eliminating redundant loops

Answer

Minimizing the number of comparisons

Question 31

What is the primary purpose of using Big O notation in algorithm analysis?

Accepted Answer

To represent an upper bound on the algorithm's time or space complexity, providing an asymptotic estimate of its resource consumption.

Answer

To precisely determine the exact number of steps the algorithm will take for a given input

Answer

To directly compare the efficiency of different algorithms

Question 32

Which of the following is a characteristic of an algorithm?

Accepted Answer

It should be finite.

Answer

It should be incorrect.

Answer

It should be inefficient.

Answer

It should be ambiguous.

Question 33

What is the time complexity of an algorithm that performs n^2 operations in a loop?

Accepted Answer

O(n^2)

Answer

O(1)

Answer

O(log n)

Answer

O(n)

Question 34

Which of the following algorithm design paradigms involves making a series of locally optimal choices?

Accepted Answer

Greedy algorithm

Answer

Dynamic programming algorithm

Answer

Divide-and-conquer algorithm

Question 35

What is the purpose of a recursive algorithm?

Accepted Answer

To solve a problem by repeatedly breaking it down into smaller instances of the same problem.

Answer

To sort a list of numbers in ascending order.

Answer

To find the smallest element in an array.

Question 36

What is the key advantage of using a backtracking algorithm?

Accepted Answer

It can find all possible solutions to a problem.

Answer

It is easy to implement.

Answer

It is always the most efficient algorithm for a given problem.

Question 37

Which of the following problems is NP-complete?

Accepted Answer

The Hamiltonian cycle problem

Answer

Sorting a list of numbers

Answer

Searching for a specific value in a binary tree

Answer

Finding the maximum element in an array

Question 38

Which of the following is an advantage of using graph algorithms?

Accepted Answer

They can model and solve problems involving relationships between objects.

Answer

They are always the most efficient algorithms for solving problems.

Answer

They are easy to understand and implement.

Question 39

What is the role of unit testing in algorithm design?

Accepted Answer

It helps to ensure that the algorithm produces correct results for a variety of inputs.

Answer

It is the final step in the algorithm design process.