1 $What is the primary definition of an algorithm in the context of computer science?$

A.

A step-by-step procedure or set of rules to solve a specific problem

B.

A random sequence of operations

C.

A programming language syntax

D.

A hardware component used to process data

2 $Which of the following factors is not typically considered when analyzing the asymptotic running time of an algorithm?$

A.

The number of basic operations performed

B.

The programming language used

C.

The growth rate of the function

D.

The size of the input

3 $If an algorithm processes an input of size using a single loop that runs from $1$ to, what is its time complexity?$

A.

B.

C.

D.

4 $What does Space Complexity refer to?$

A.

The number of lines of code in the program

B.

The amount of memory required by an algorithm to run as a function of input size

C.

The bandwidth consumed during execution

D.

The amount of time the CPU takes to execute instructions

5 $In algorithm analysis, which case provides an upper bound on the execution time?$

A.

Worst-case

B.

Average-case

C.

Best-case

D.

Null-case

6 $Which of the following functions has the highest rate of growth as ?$

A.

B.

C.

D.

7 $Consider the function . What is the Big-O notation for this function?$

A.

B.

C.

D.

8 $What is the Big-O complexity of a nested loop where the outer loop runs times and the inner loop runs times?$

A.

B.

C.

D.

9 $What does the notation formally imply?$

A.

grows strictly slower than

B.

for some constant

C.

for some constant and

D.

for some constant and

10 $Which asymptotic notation represents the lower bound of an algorithm's running time?$

A.

(Big-Theta)

B.

(Big-O)

C.

(Big-Omega)

D.

(Little-o)

11 $If and, then:$

A.

B.

This condition is impossible

C.

D.

12 $Which of the following represents constant time complexity?$

A.

B.

C.

D.

13 $What is the typical time complexity of Binary Search ?$

A.

B.

C.

D.

14 $In the analysis of algorithms, what happens to the constant factors (e.g., the $5$ in) when using Big-O notation?$

A.

They are added to the exponent

B.

They are squared

C.

They are ignored/dropped

D.

They become the base of the logarithm

15 $If Algorithm A is and Algorithm B is, which algorithm is generally preferred for very large inputs?$

A.

Both are equal

B.

Algorithm B

C.

Algorithm A

D.

It depends on the computer hardware

16 $What is the recurrence relation for the Merge Sort algorithm?$

A.

B.

C.

D.

17 $What is the defining characteristic of a Recursive function?$

A.

It always returns 0

B.

It uses a for loop

C.

It calls itself

D.

It uses pointers

18 $In recursion, what is the Base Case ?$

A.

The variable with the largest value

B.

The most complex part of the problem

C.

The first line of the code

D.

The condition that stops the recursion

19 $If a recursive function lacks a base case, what runtime error is likely to occur?$

A.

Stack Overflow Error

B.

Syntax Error

C.

Null Pointer Exception

D.

Index Out of Bounds

20 $Which algorithmic technique systematically searches for a solution by trying options and undoing them if they fail?$

A.

Greedy Method

B.

Divide and Conquer

C.

Dynamic Programming

D.

Backtracking

21 $The N-Queens problem is a classic example solved using which technique?$

A.

Hashing

B.

Backtracking

C.

Sorting

D.

Greedy Algorithm

22 $In the context of Backtracking, what does pruning mean?$

A.

Optimizing the compiler

B.

Cutting off branches of the state-space tree that do not lead to a solution

C.

Removing syntax errors

D.

Reducing the size of the input array

23 $What is Tail Recursion ?$

A.

Recursion with two base cases

B.

When the recursive call is the first statement

C.

Recursion used only for sorting

D.

When the recursive call is the last operation performed

24 $Which of the following problems is typically NOT solved efficiently by recursion due to overlapping subproblems?$

A.

Merge Sort

B.

Tree Traversal

C.

Quick Sort

D.

Calculating the -th Fibonacci number (naive approach)

25 $Dynamic Programming is mainly used for optimization problems that possess which two properties?$

A.

Greedy Choice and Randomization

B.

Recursion and Iteration

C.

Overlapping Subproblems and Optimal Substructure

D.

Encapsulation and Inheritance

26 $In Dynamic Programming, what is Memoization ?$

A.

Using a greedy strategy

B.

Deleting unused memory

C.

A bottom-up approach using iteration

D.

A top-down approach that stores results of expensive function calls

27 $What is the difference between Tabulation and Memoization ?$

A.

Tabulation is Bottom-Up; Memoization is Top-Down

B.

Tabulation is Top-Down; Memoization is Bottom-Up

C.

Tabulation uses more memory

D.

Memoization is not a DP technique

28 $The 0/1 Knapsack Problem is best solved using:$

A.

Dynamic Programming

B.

Bubble Sort

C.

Greedy Algorithm

D.

Binary Search

29 $What is the time complexity of the Dynamic Programming solution for the Longest Common Subsequence (LCS) of two strings of length and ?$

A.

B.

C.

D.

30 $Which algorithm finds the shortest paths from a single source to all other vertices in a graph with negative edge weights (but no negative cycles)?$

A.

Dijkstra's Algorithm

B.

Kruskal's Algorithm

C.

Prim's Algorithm

D.

Bellman-Ford Algorithm

31 $The Floyd-Warshall algorithm for All-Pairs Shortest Paths is an example of:$

A.

Divide and Conquer

B.

Backtracking

C.

Dynamic Programming

D.

Greedy Algorithm

32 $What defines a Greedy Algorithm ?$

A.

It makes the locally optimal choice at each step hoping to find the global optimum

B.

It tries all possible solutions

C.

It looks ahead to see the final outcome before deciding

D.

It solves subproblems and stores their results

33 $Which problem can be solved optimally using a Greedy Algorithm?$

A.

Fractional Knapsack Problem

B.

Traveling Salesman Problem

C.

0/1 Knapsack Problem

D.

Longest Common Subsequence

34 $Huffman Coding uses a greedy strategy to construct:$

A.

A shortest path graph

B.

An optimal prefix-free binary tree for data compression

C.

A Maximum Spanning Tree

D.

A sorted array

35 $The Activity Selection Problem (selecting max non-overlapping activities) is solved by sorting activities by their:$

A.

Start times

B.

Durations

C.

Priority

D.

Finish times

36 $Which of the following algorithms is used to find the Minimum Spanning Tree (MST) ?$

A.

Prim's Algorithm

B.

Strassen's Algorithm

C.

Merge Sort

D.

Binary Search

37 $In Kruskal’s Algorithm for MST, edges are processed in what order?$

A.

Random order

B.

Increasing order of weight

C.

Based on the node index

D.

Decreasing order of weight

38 $Dijkstra's Algorithm is a greedy algorithm. Why does it fail with negative edge weights?$

A.

It cannot handle cycles

B.

It assumes that adding an edge never decreases the total path distance

C.

It runs out of memory

D.

It is too slow

39 $The Coin Change Problem (finding min coins) can be solved greedily only if:$

A.

The total value is negative

B.

The coin system is 'canonical' (e.g., US currency)

C.

We want the maximum number of coins

D.

The coins are all the same value

40 $Which data structure is often used to efficiently implement Prim's Algorithm or Dijkstra's Algorithm ?$

A.

Priority Queue (Min-Heap)

B.

Stack

C.

Queue

D.

Hash Table

41 $What is the key difference between Prim's and Kruskal's algorithms?$

A.

There is no difference

B.

Prim's uses recursion; Kruskal's uses iteration

C.

Prim's grows a tree from a source node; Kruskal's grows a forest of edges

D.

Prim's is for directed graphs; Kruskal's is for undirected

42 $Which concept explains why Merge Sort is ?$

A.

It sorts in place without extra memory

B.

It runs loops inside loops

C.

It uses a greedy approach

D.

The height of the recursion tree is and work per level is

43 $In the Matrix Chain Multiplication problem (DP), what are we trying to minimize?$

A.

The total number of scalar multiplications

B.

The determinant of the result

C.

The size of the matrices

D.

The number of matrices

44 $What is the time complexity of calculating the -th Fibonacci number using DP with Memoization?$

A.

B.

C.

D.

45 $Which of the following is true regarding Optimal Substructure ?$

A.

It means an optimal solution to the problem contains optimal solutions to its subproblems

B.

It means the problem can be solved using a greedy heuristic only

C.

It implies the solution is unique

D.

It is only found in sorting algorithms

46 $What is the complexity of sorting an array using Quick Sort in the worst case?$

A.

B.

C.

D.

47 $Which notation represents the strict upper bound (rarely used in basic analysis)?$

A.

(Omega)

B.

(Theta)

C.

(Big-O)

D.

(Little-o)

48 $In algorithm analysis, a 'Basic Operation' is:$

A.

The entire program

B.

A comment in the code

C.

A complex function call

D.

The operation contributing most to the running time

49 $Which strategy does Binary Search use?$

A.

Greedy

B.

Backtracking

C.

Dynamic Programming

D.

Divide and Conquer

50 $The Travelling Salesman Problem (TSP) is generally considered hard because:$

A.

It has complexity

B.

It can be solved easily with Greedy

C.

It is NP-Hard and no polynomial time algorithm is known

D.

It requires negative edge weights

Unit 6 - Practice Quiz