Master Algorithms and Complexity: Enhance Your Computer Science Skills

Question 1

How does the divide-and-conquer approach improve the efficiency of sorting algorithms? Illustrate your answer with an example of a sorting algorithm that uses this strategy.

Accepted Answer

Merge sort is an example of a divide-and-conquer sorting algorithm. It efficiently sorts an array using the divide-and-conquer approach.

Answer

Divide-and-conquer is not suitable for sorting because it requires dividing the problem into equal-sized subsets.

Answer

The worst-case time complexity of divide-and-conquer algorithms is always O(n^2).

Question 2

Which of the following is NOT considered a fundamental algorithmic technique?

Accepted Answer

Ad hoc approaches

Answer

Dynamic programming

Answer

Greedy algorithms

Answer

Randomized algorithms

Question 3

Determine the time complexity of the following algorithm: for i = 1 to n do for j = 1 to m do print(i, j)

Accepted Answer

O(n^2)

Answer

O(n)

Answer

O(n log n)

Answer

O(m)

Question 4

Provide an example of a randomized algorithm.

Accepted Answer

QuickSort

Answer

MergeSort

Answer

Dijkstra's algorithm

Answer

Fibonacci heap

Question 5

Which of the following is a fundamental characteristic of algorithms?

Accepted Answer

Efficiency

Answer

Precision

Answer

Creativity

Answer

Originality

Question 6

In analyzing the efficiency of an algorithm, which metric is commonly used to measure the amount of time required to complete a task?

Accepted Answer

Time Complexity

Answer

Space Complexity

Answer

Error Rate

Answer

User Interface

Question 7

Which of the following sorting algorithms is considered stable, meaning it maintains the original order of equal elements?

Accepted Answer

Merge Sort

Answer

Bubble Sort

Answer

Quick Sort

Answer

Heap Sort

Question 8

Which of the following is NOT a common algorithmic design technique?

Accepted Answer

Quantum Computing

Answer

Recursion

Answer

Divide-and-Conquer

Answer

Greedy Algorithms

Question 9

In a greedy algorithm, the choice made at each step is based on:

Accepted Answer

Short-term gain

Answer

Long-term optimization

Answer

Random selection

Answer

Historical data

Question 10

Which of the following problems is NP-complete?

Accepted Answer

Travelling Salesman Problem

Answer

Bubble Sort

Answer

Binary Search

Answer

Dijkstra's Algorithm

Question 11

What is the main idea behind dynamic programming?

Accepted Answer

Storing solutions to subproblems to avoid redundant calculations

Answer

Breaking down a problem into smaller subproblems

Answer

Using recursion to explore all possible solutions

Answer

Approximating solutions based on statistical models

Question 12

Which of the following is a benefit of using hashing techniques in algorithms?

Accepted Answer

Efficient search and retrieval based on keys

Answer

Guaranteed optimal solutions

Answer

Reduced memory consumption

Answer

Improved fault tolerance

Question 13

What is the key difference between a depth-first and breadth-first search algorithm?

Accepted Answer

Order of node exploration

Answer

Data structure used for traversal

Answer

Time complexity

Answer

Space complexity

Question 14

Which of the following is not a fundamental algorithmic technique?

Accepted Answer

Linear Regression

Answer

Divide and Conquer

Answer

Dynamic Programming

Answer

Branch and Bound

Question 15

What is the time complexity of a recursive algorithm that makes n recursive calls on a problem of size n/2?

Accepted Answer

O(n log n)

Answer

O(n)

Answer

O(log n)

Answer

O(1)

Question 16

What is the primary purpose of using a hash table in an algorithm?

Accepted Answer

To optimize data storage and enable fast lookups

Answer

To sort data in ascending order

Answer

To reverse a linked list

Answer

To identify the shortest path in a graph

Question 17

Which of the following algorithms incorporates randomization?

Accepted Answer

QuickSort

Answer

MergeSort

Answer

Binary Search

Answer

Bubble Sort

Question 18

Which of the following problems falls under the category of NP-complete problems?

Accepted Answer

Traveling Salesman Problem

Answer

Sorting an array of integers

Answer

Binary search

Answer

Determining whether a graph is connected

Question 19

Which algorithmic paradigm forms the basis of dynamic programming?

Accepted Answer

Memoization

Answer

Divide and Conquer

Answer

Greedy

Answer

Branch and Bound

Question 20

Which of the following is NOT a fundamental algorithmic technique used to design efficient algorithms?

Accepted Answer

Integration

Answer

Recursion

Answer

Dynamic programming

Answer

Brute force

Question 21

Dynamic programming is a technique for solving problems with overlapping subproblems by:

Accepted Answer

Storing the solutions to previously solved subproblems

Answer

Rewriting the problem in a recursive form

Answer

Using a brute-force approach to find the optimal solution

Question 22

Which of the following is an NP-complete problem?

Accepted Answer

Traveling Salesman Problem

Answer

Sorting an array in ascending order

Answer

Finding the shortest path in a graph

Question 23

The greedy algorithm is an effective approach when:

Accepted Answer

The optimal solution can be obtained by making locally optimal choices at each step

Answer

The problem can be solved using recursion

Answer

The problem has multiple constraints that must be satisfied

Question 24

Which of the following is a measure of the space complexity of an algorithm?

Accepted Answer

Number of memory cells required to execute the algorithm

Answer

Running time of the algorithm

Answer

Number of input variables

Question 25

The worst-case time complexity of the merge sort algorithm is:

Accepted Answer

O(n log n)

Answer

O(n)

Answer

O(n^2)

Question 26

Which of the following is an example of a divide-and-conquer algorithm?

Accepted Answer

Merge sort

Answer

Breadth-first search

Answer

Dijkstra's algorithm

Question 27

Which of the following data structures is NOT fundamental to algorithm design?

Accepted Answer

Database

Answer

Array

Answer

Stack

Answer

Queue

Question 28

What is the time complexity of a linear search algorithm?

Accepted Answer

O(n)

Answer

O(log n)

Answer

O(n^2)

Answer

O(1)

Question 29

Which sorting algorithm employs a divide-and-conquer approach?

Accepted Answer

Merge Sort

Answer

Bubble Sort

Answer

Selection Sort

Answer

Insertion Sort

Question 30

Which technique is commonly used in dynamic programming?

Accepted Answer

Memoization

Answer

Branch and bound

Answer

Divide and conquer

Answer

Backtracking

Question 31

How are algorithms and heuristics distinguished from each other?

Accepted Answer

Algorithms guarantee an optimal solution, while heuristics do not.

Answer

Heuristics guarantee an optimal solution, while algorithms do not.

Answer

Algorithms are always more efficient than heuristics.

Answer

Heuristics are always more efficient than algorithms.

Question 32

Which of the following is NOT a type of graph traversal algorithm?

Accepted Answer

Binary search

Answer

Depth-first search

Answer

Breadth-first search

Answer

Topological sort

Question 33

What is the fundamental difference between deterministic and non-deterministic algorithms?

Accepted Answer

Deterministic algorithms always produce the same output for the same input, while non-deterministic algorithms may produce different outputs for the same input.

Answer

Non-deterministic algorithms always produce the same output for the same input, while deterministic algorithms may produce different outputs for the same input.

Answer

Deterministic algorithms are more efficient than non-deterministic algorithms.

Answer

Non-deterministic algorithms are more efficient than deterministic algorithms.

Question 34

When designing and implementing algorithms, which ethical considerations should be prioritized?

Accepted Answer

Design algorithms to minimize bias and promote fairness in decision-making.

Answer

Prioritize efficiency above all else, even if it compromises fairness or privacy.

Answer

Ethical considerations apply only to algorithms used in sensitive areas like healthcare or finance.

Answer

Ethical considerations in algorithm design are solely the responsibility of policymakers and regulators.

Question 35

Which of the following techniques is NOT a widely recognized fundamental algorithmic technique?

Accepted Answer

Random guessing

Answer

Dynamic programming

Answer

Greedy algorithms

Answer

Divide-and-conquer

Question 36

Which of the following is NOT an essential characteristic of an algorithm?

Accepted Answer

It can be expressed solely in natural language.

Answer

It has a precise and unambiguous definition.

Answer

It is guaranteed to terminate after a finite number of steps.

Answer

It produces a correct output for all valid inputs.

Question 37

Which algorithm design technique involves breaking down a problem into smaller, more manageable subproblems?

Accepted Answer

Divide-and-conquer

Answer

Dynamic programming

Answer

Greedy

Answer

Backtracking

Question 38

What is the time complexity of the following algorithm?
    
    for (i = 0; i < n; i++) {
      for (j = 0; j < n; j++) {
        for (k = 0; k < n; k++) {
          // Do some operation
        }
      }
    }
    
    n is the input size.

Accepted Answer

O(n^3)

Answer

O(n log n)

Answer

O(n^2)

Answer

O(n)

Question 39

Which algorithm is specifically designed to find the shortest path between two nodes in a weighted graph?

Accepted Answer

Dijkstra's algorithm

Answer

Bellman-Ford algorithm

Answer

Prim's algorithm

Answer

Kruskal's algorithm

Question 40

What is the primary role of a hash function in a hash table?

Accepted Answer

To map keys to unique indices within the table.

Answer

To store the values associated with keys.

Answer

To locate keys within the table.

Answer

To insert keys into the table.

Question 41

Which sorting algorithm among the following has a worst-case time complexity of O(n^2)?

Accepted Answer

Bubble sort

Answer

Heap sort

Answer

Quick sort

Answer

Merge sort

Question 42

What is the fundamental distinction between a greedy algorithm and a dynamic programming algorithm?

Accepted Answer

Greedy algorithms prioritize locally optimal choices, while dynamic programming algorithms evaluate all potential subproblems.

Answer

Greedy algorithms are inherently faster than dynamic programming algorithms.

Question 43

Which of the following problems is classified as NP-complete?

Accepted Answer

Traveling salesman problem

Answer

Finding the shortest path in a graph

Answer

Sorting an array of integers

Answer

Checking if a graph is connected

Question 44

Greedy algorithms are known for which of the following characteristics?

Accepted Answer

Making locally optimal choices at each step.

Answer

Always finding the global optimum.

Answer

Requiring exponential time complexity.

Answer

Being applicable only to sorting problems.

Question 45

When analyzing the time complexity of algorithms, which complexity class represents the worst-case scenario?

Accepted Answer

O(n^2)

Answer

O(n)

Answer

O(1)

Answer

O(n log n)

Question 46

Dynamic programming techniques aim to improve algorithm efficiency by leveraging which concept?

Accepted Answer

Memoization

Answer

Divide-and-conquer

Answer

Randomization

Answer

Heuristics

Question 47

Hash functions are primarily designed to achieve which of the following goals?

Accepted Answer

Mapping large keys to smaller values.

Answer

Arranging values in sorted order.

Answer

Comparing strings for equality.

Answer

Storing data efficiently in linked lists.

Question 48

In graph theory, which type of graph is characterized by the absence of cycles?

Accepted Answer

Acyclic graph

Answer

Directed graph

Answer

Undirected graph

Answer

Complete graph

Question 49

Dijkstra's algorithm is primarily used to solve which graph-related problem?

Accepted Answer

Finding the shortest path between two nodes.

Answer

Detecting cycles in a graph.

Answer

Finding the minimum spanning tree.

Answer

Determining the number of connected components.

Question 50

Which sorting algorithm employs a divide-and-conquer approach, repeatedly splitting and merging subarrays?

Accepted Answer

Merge sort

Answer

Bubble sort

Answer

Selection sort

Answer

Quick sort

Question 51

Which of the following algorithms divides a problem into smaller subproblems and recursively solves them?

Accepted Answer

Merge sort

Answer

Bubble sort

Answer

Insertion sort

Answer

Selection sort

Question 52

For an algorithm that executes 'n' operations in three nested loops, what is the resulting asymptotic time complexity?

Accepted Answer

O(n^3)

Answer

O(n log n)

Answer

O(log n)

Answer

O(n)