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 random sequence of operations

B.

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

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

B.

The growth rate of the function

C.

The programming language used

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

B.

The amount of time the CPU takes to execute instructions

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.

Average-case

B.

Null-case

C.

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

B.

for some constant and

C.

for some constant and

D.

grows strictly slower than

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

A.

(Little-o)

B.

(Big-O)

C.

(Big-Omega)

D.

(Big-Theta)

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.

Algorithm B

C.

Both are equal

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 calls itself

B.

It uses a for loop

C.

It uses pointers

D.

It always returns 0

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

A.

The first line of the code

B.

The most complex part of the problem

C.

The variable with the largest value

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.

Syntax Error

D.

Index Out of Bounds

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

A.

Divide and Conquer

B.

Backtracking

C.

Dynamic Programming

D.

Greedy Method

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

A.

Sorting

B.

Backtracking

C.

Hashing

D.

Greedy Algorithm

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

A.

Reducing the size of the input array

B.

Optimizing the compiler

C.

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

D.

Removing syntax errors

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.

Quick Sort

B.

Calculating the -th Fibonacci number (naive approach)

C.

Tree Traversal

D.

Merge Sort

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

A.

Recursion and Iteration

B.

Greedy Choice and Randomization

C.

Encapsulation and Inheritance

D.

Overlapping Subproblems and Optimal Substructure

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.

Deleting unused memory

D.

A bottom-up approach using iteration

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

A.

Tabulation is Top-Down; Memoization is Bottom-Up

B.

Tabulation is Bottom-Up; Memoization is Top-Down

C.

Memoization is not a DP technique

D.

Tabulation uses more memory

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

A.

Dynamic Programming

B.

Binary Search

C.

Bubble Sort

D.

Greedy Algorithm

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.

Prim's Algorithm

B.

Dijkstra's Algorithm

C.

Bellman-Ford Algorithm

D.

Kruskal's Algorithm

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

A.

Dynamic Programming

B.

Backtracking

C.

Divide and Conquer

D.

Greedy Algorithm

32 $What defines a Greedy Algorithm ?$

A.

It solves subproblems and stores their results

B.

It tries all possible solutions

C.

It looks ahead to see the final outcome before deciding

D.

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

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

A.

0/1 Knapsack Problem

B.

Traveling Salesman Problem

C.

Fractional Knapsack Problem

D.

Longest Common Subsequence

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

A.

A sorted array

B.

A Maximum Spanning Tree

C.

A shortest path graph

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.

Finish times

B.

Priority

C.

Durations

D.

Start times

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

A.

Merge Sort

B.

Strassen's Algorithm

C.

Prim's Algorithm

D.

Binary Search

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

A.

Increasing order of weight

B.

Based on the node index

C.

Random order

D.

Decreasing order of weight

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

A.

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

B.

It is too slow

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.

The coins are all the same value

B.

The total value is negative

C.

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

D.

We want the maximum number of coins

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

A.

Hash Table

B.

Priority Queue (Min-Heap)

C.

Queue

D.

Stack

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

A.

There is no difference

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.

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 uses a greedy approach

C.

It runs loops inside loops

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 size of the matrices

C.

The determinant of the result

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

(Big-O)

B.

(Omega)

C.

(Theta)

D.

(Little-o)

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

A.

A comment in the code

B.

A complex function call

C.

The operation contributing most to the running time

D.

The entire program

49 $Which strategy does Binary Search use?$

A.

Divide and Conquer

B.

Greedy

C.

Dynamic Programming

D.

Backtracking

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?