Master Algorithms: Introduction to Algorithms for Computer Science MEng

Question 1

Choose the option that best defines an algorithm.

Accepted Answer

A step-by-step guide to solve a problem

Answer

A recipe for cooking a dish

Answer

A set of instructions for assembling a product

Answer

A poem describing a story

Question 2

An algorithm executes a loop that performs constant-time operations on each of the n elements in an array. What is the time complexity of this algorithm?

Accepted Answer

O(n)

Answer

O(log n)

Answer

O(n^2)

Answer

O(1)

Question 3

Which sorting algorithm is most efficient for an almost sorted array?

Accepted Answer

Insertion Sort

Answer

Bubble Sort

Answer

Selection Sort

Answer

Quick Sort

Question 4

Explain the essence of the divide-and-conquer paradigm.

Accepted Answer

Breaking a problem into smaller similar problems, solving them recursively, and combining their solutions

Answer

Iterating through a list and performing operations on each element

Answer

Using a stack to store intermediate results while solving a problem

Answer

Recursively calling a function until a predefined stopping condition is met

Question 5

Which characteristic is NOT associated with greedy algorithms?

Accepted Answer

Feasible for dynamic programming problems

Answer

Optimal solution for each subproblem

Answer

Globally optimal solution may not be found

Answer

Often employed in approximation algorithms

Question 6

What is the main objective of algorithm analysis?

Accepted Answer

To measure the efficiency and effectiveness of algorithms

Answer

To design and implement efficient algorithms

Answer

To verify the accuracy of algorithms

Answer

To visualize the execution of algorithms

Question 7

Which notation is widely used to represent the time complexity of algorithms?

Accepted Answer

Big-O notation

Answer

Little-o notation

Answer

Omega notation

Answer

Theta notation

Question 8

What is the time complexity of the merge sort algorithm?

Accepted Answer

O(n log n)

Answer

O(n)

Answer

O(n^2)

Answer

O(2^n)

Question 9

What is a potential disadvantage of using heuristics in algorithm design?

Accepted Answer

Heuristics may not always yield optimal solutions.

Answer

Heuristics can be challenging to implement efficiently.

Answer

Heuristics require rigorous testing for accuracy.

Answer

Heuristics are unsuitable for large-scale problems.

Question 10

What is the significance of randomized algorithms?

Accepted Answer

Randomized algorithms provide efficient solutions for problems that are difficult to solve deterministically.

Answer

Randomized algorithms always find optimal solutions.

Answer

Randomized algorithms reduce the space complexity of algorithms.

Answer

Randomized algorithms are particularly effective for small-scale problems.

Question 11

Which of the following is a defining characteristic of divide-and-conquer algorithms?

Accepted Answer

They break down a problem into smaller subproblems recursively.

Answer

They use a fixed amount of memory regardless of input size.

Answer

They are always more efficient than greedy algorithms.

Answer

They are best suited for problems with small data sets.

Question 12

Which of the following statements about algorithms is **incorrect**?

Accepted Answer

They are guaranteed to produce correct outputs for all inputs.

Answer

They consist of a finite set of well-defined instructions.

Answer

They can be designed to solve specific problems.

Answer

They have clearly defined inputs and outputs.

Question 13

What does Big-O notation primarily represent?

Accepted Answer

Upper bound of an algorithm's complexity

Answer

Lower bound of an algorithm's complexity

Answer

Average case complexity of an algorithm

Answer

Constant complexity of an algorithm

Question 14

Which sorting algorithm exhibits a worst-case time complexity of O(n^2)?

Accepted Answer

Bubble sort

Answer

Quick sort

Answer

Merge sort

Answer

Heap sort

Question 15

What is the primary function of a hash function?

Accepted Answer

Generating unique identifiers for inputs

Answer

Sorting a set of data

Answer

Compressing data

Answer

Encrypting data

Question 16

Which data structure is best suited for storing a collection of distinct elements?

Accepted Answer

Set

Answer

Array

Answer

Linked list

Answer

Stack

Question 17

Which of the following is **not** a recognized algorithm correctness verification method?

Accepted Answer

Empirical proof

Answer

Inductive proof

Answer

Constructive proof

Answer

Formal proof

Question 18

What is the primary functionality of a hash table?

Accepted Answer

Storing and retrieving data efficiently using a key-value pair mechanism.

Answer

Sorting data in a specific order (ascending or descending).

Answer

Performing complex mathematical operations on large datasets.

Answer

Representing hierarchical relationships between data items.

Question 19

Which scenario is a typical application of binary search trees?

Accepted Answer

Efficiently searching for a specific element within a sorted collection of data.

Answer

Storing and organizing data with hierarchical relationships.

Answer

Performing complex mathematical calculations.

Answer

Managing dynamic memory allocation.

Question 20

Identify the key difference between a directed graph and an undirected graph. Which statement accurately describes it?

Accepted Answer

Directed graphs allow edges to have a direction (source and destination), while undirected graphs do not.

Answer

Undirected graphs allow multiple edges between the same pair of nodes, while directed graphs do not.

Answer

Directed graphs are used to represent hierarchical relationships, while undirected graphs are used for general connectivity.

Answer

There is no meaningful difference between directed and undirected graphs.