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

C.

A random sequence of operations

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 number of basic operations performed

B.

The size of the input

C.

The growth rate of the function

D.

The programming language used

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 memory required by an algorithm to run as a function of input size

B.

The number of lines of code in the program

C.

The amount of time the CPU takes to execute instructions

D.

The bandwidth consumed during execution

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

A.

Average-case

B.

Worst-case

C.

Null-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-Theta)

B.

(Big-Omega)

C.

(Little-o)

D.

(Big-O)

11 $If and, then:$

A.

B.

C.

This condition is impossible

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

Algorithm A

B.

It depends on the computer hardware

C.

Both are equal

D.

Algorithm B

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

D.

It calls itself

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

A.

The condition that stops the recursion

B.

The most complex part of the problem

C.

The first line of the code

D.

The variable with the largest value

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

A.

Syntax Error

B.

Null Pointer Exception

C.

Index Out of Bounds

D.

Stack Overflow Error

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

A.

Backtracking

B.

Greedy Method

C.

Dynamic Programming

D.

Divide and Conquer

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

A.

Greedy Algorithm

B.

Backtracking

C.

Sorting

D.

Hashing

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

A.

Reducing the size of the input array

B.

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

C.

Removing syntax errors

D.

Optimizing the compiler

23 $What is Tail Recursion ?$

A.

When the recursive call is the first statement

B.

Recursion used only for sorting

C.

Recursion with two base cases

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.

Calculating the -th Fibonacci number (naive approach)

B.

Merge Sort

C.

Tree Traversal

D.

Quick Sort

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.

A bottom-up approach using iteration

B.

Deleting unused memory

C.

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

D.

Using a greedy strategy

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

A.

Memoization is not a DP technique

B.

Tabulation is Bottom-Up; Memoization is Top-Down

C.

Tabulation is Top-Down; Memoization is Bottom-Up

D.

Tabulation uses more memory

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

A.

Binary Search

B.

Greedy Algorithm

C.

Dynamic Programming

D.

Bubble Sort

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.

Prim's Algorithm

C.

Bellman-Ford Algorithm

D.

Dijkstra's Algorithm

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

A.

Divide and Conquer

B.

Dynamic Programming

C.

Greedy Algorithm

D.

Backtracking

32 $What defines a Greedy Algorithm ?$

A.

It looks ahead to see the final outcome before deciding

B.

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

C.

It tries all possible solutions

D.

It solves subproblems and stores their results

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

A.

0/1 Knapsack Problem

B.

Traveling Salesman Problem

C.

Longest Common Subsequence

D.

Fractional Knapsack Problem

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

A.

A Maximum Spanning Tree

B.

A shortest path graph

C.

A sorted array

D.

An optimal prefix-free binary tree for data compression

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.

Binary Search

B.

Prim's Algorithm

C.

Strassen's Algorithm

D.

Merge Sort

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

A.

Increasing order of weight

B.

Random order

C.

Decreasing order of weight

D.

Based on the node index

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

A.

It runs out of memory

B.

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

C.

It cannot handle cycles

D.

It is too slow

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

A.

We want the maximum number of coins

B.

The coins are all the same value

C.

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

D.

The total value is negative

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.

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

B.

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

C.

Prim's uses recursion; Kruskal's uses iteration

D.

There is no difference

42 $Which concept explains why Merge Sort is ?$

A.

It sorts in place without extra memory

B.

It uses a greedy approach

C.

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

D.

It runs loops inside loops

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

A.

The determinant of the result

B.

The number of matrices

C.

The total number of scalar multiplications

D.

The size of the 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 is only found in sorting algorithms

C.

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

D.

It implies the solution is unique

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.

(Little-o)

B.

(Big-O)

C.

(Theta)

D.

(Omega)

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

A.

A comment in the code

B.

The operation contributing most to the running time

C.

A complex function call

D.

The entire program

49 $Which strategy does Binary Search use?$

A.

Backtracking

B.

Divide and Conquer

C.

Dynamic Programming

D.

Greedy

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

A.

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

B.

It has complexity

C.

It requires negative edge weights

D.

It can be solved easily with Greedy

Unit 6: Algorithms - Practice Quiz

Did this save you a night before the exam?