What does the notation $f(n) = O(g(n))$ formally imply?

$f(n) \leq c \cdot g(n)$ for some constant $c$ and $n > n_0$

$f(n) \geq c \cdot g(n)$ for some constant $c$ and $n > n_0$

$f(n) = c \cdot g(n)$ for some constant $c$

$f(n)$ grows strictly slower than $g(n)$

CSE357 Unit 6: Algorithms - MCQ Practice | B. Tech. CSE

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 hardware component used to process data

D.

A programming language syntax

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

A.

The growth rate of the function

B.

The programming language used

C.

The number of basic operations performed

D.

The size of the input

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

A.

B.

C.

D.

4 $What does Space Complexity refer to?$

A.

The amount of time the CPU takes to execute instructions

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 number of lines of code in the program

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

A.

Null-case

B.

Worst-case

C.

Average-case

D.

Best-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.

for some constant and

B.

grows strictly slower than

C.

for some constant and

D.

for some constant

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

A.

(Big-O)

B.

(Little-o)

C.

(Big-Omega)

D.

(Big-Theta)

11 $If and, then:$

A.

This condition is impossible

B.

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 in) when using Big-O notation?$

A.

They are added to the exponent

B.

They become the base of the logarithm

C.

They are squared

D.

They are ignored/dropped

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 uses pointers

B.

It always returns 0

C.

It calls itself

D.

It uses a for loop

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

A.

The first line of the code

B.

The variable with the largest value

C.

The most complex part of the problem

D.

The condition that stops the recursion

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

A.

Null Pointer Exception

B.

Stack Overflow Error

C.

Index Out of Bounds

D.

Syntax Error

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

A.

Divide and Conquer

B.

Dynamic Programming

C.

Greedy Method

D.

Backtracking

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

A.

Greedy Algorithm

B.

Backtracking

C.

Hashing

D.

Sorting

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

A.

Removing syntax errors

B.

Optimizing the compiler

C.

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

D.

Reducing the size of the input array

23 $What is Tail Recursion ?$

A.

When the recursive call is the first statement

B.

Recursion with two base cases

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.

Tree Traversal

B.

Merge Sort

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.

Encapsulation and Inheritance

B.

Overlapping Subproblems and Optimal Substructure

C.

Greedy Choice and Randomization

D.

Recursion and Iteration

26 $In Dynamic Programming, what is Memoization ?$

A.

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

B.

Using a greedy strategy

C.

A bottom-up approach using iteration

D.

Deleting unused memory

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

A.

Tabulation is Top-Down; Memoization is Bottom-Up

B.

Tabulation uses more memory

C.

Tabulation is Bottom-Up; Memoization is Top-Down

D.

Memoization is not a DP technique

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

A.

Bubble Sort

B.

Dynamic Programming

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.

Kruskal's Algorithm

B.

Dijkstra's Algorithm

C.

Bellman-Ford Algorithm

D.

Prim's Algorithm

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

A.

Backtracking

B.

Greedy Algorithm

C.

Divide and Conquer

D.

Dynamic Programming

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 solves subproblems and stores their results

D.

It looks ahead to see the final outcome before deciding

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

A.

Fractional Knapsack Problem

B.

Traveling Salesman Problem

C.

Longest Common Subsequence

D.

0/1 Knapsack Problem

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

A.

An optimal prefix-free binary tree for data compression

B.

A sorted array

C.

A Maximum Spanning Tree

D.

A shortest path graph

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

A.

Finish times

B.

Start times

C.

Priority

D.

Durations

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

A.

Binary Search

B.

Prim's Algorithm

C.

Merge Sort

D.

Strassen's Algorithm

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

A.

Based on the node index

B.

Decreasing order of weight

C.

Increasing order of weight

D.

Random order

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

A.

It is too slow

B.

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

C.

It cannot handle cycles

D.

It runs out of memory

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

A.

We want the maximum number of coins

B.

The total value is negative

C.

The coins are all the same value

D.

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

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

A.

Hash Table

B.

Queue

C.

Priority Queue (Min-Heap)

D.

Stack

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

A.

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

B.

There is no difference

C.

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

D.

Prim's uses recursion; Kruskal's uses iteration

42 $Which concept explains why Merge Sort is ?$

A.

It runs loops inside loops

B.

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

C.

It uses a greedy approach

D.

It sorts in place without extra memory

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

A.

The size of the matrices

B.

The determinant of the result

C.

The number of matrices

D.

The total number of scalar multiplications

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 the problem can be solved using a greedy heuristic only

B.

It implies the solution is unique

C.

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

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.

(Big-O)

C.

(Little-o)

D.

(Theta)

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

A.

A complex function call

B.

The operation contributing most to the running time

C.

A comment in the code

D.

The entire program

49 $Which strategy does Binary Search use?$

A.

Greedy

B.

Divide and Conquer

C.

Backtracking

D.

Dynamic Programming

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

A.

It has complexity

B.

It requires negative edge weights

C.

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

D.

It can be solved easily with Greedy

Unit 6: Algorithms - Practice Quiz

Did this save you a night before the exam?