Free Printable CSA06 DESIGN AND ANALYSIS OF ALGORITHMS

Worksheets

CSA06 DESIGN AND ANALYSIS OF ALGORITHMS - Worksheet

Total questions: 51

Worksheet time: 26mins

Name

Class

Date

Consider the recursive function: int mystery(int n) { if (n <= 1) return 1; else return mystery(n - 1) + mystery(n - 1); } What is the time complexity of mystery(n)?

O(n)

O(n²)

O(2ⁿ)

O(log n)

What is the maximum number of comparisons needed to search an element in a sorted array of 1000 elements using binary search?

100

1000

Which of the following problems is most suitable for a greedy approach?

Longest Common Subsequence

Matrix Chain Multiplication

Fractional Knapsack

0/1 Knapsack

Which of the following functions grows faster than f(n) = n log n?

f(n) = n

f(n) = log n

f(n) = n²

f(n) = √n

Given the two recursive algorithms: A1: T(n) = T(n - 1) + n A2: T(n) = 2T(n/2) + n Which algorithm has a better (lower) asymptotic time complexity?

A) A1

B) A2

C) Both same

D) Depends on implementation

For the function f(n) = 3n log n + 2n + 100, what is the dominant term that defines its time complexity?

3n log n

100

None

What is the total number of comparisons done by selection sort in the worst case on an array of size n?

O(n log n)

O(n²)

O(n)

O(log n)

Consider the recurrence T(n) = 3T(n/4) + n. What is the time complexity using the Master Theorem?

O(n)

O(n log n)

$O(n^{1.2})$

Count the number of operations (in Big-O) for the code: for (int i = 0; i < n; i++) for (int j = i; j < n; j++) cout << i << j;

O(n)

$O(n^2)$

O(n log n)

$O(n^3)$

10.

What is the best possible worst-case time complexity for any comparison-based sorting algorithm?

O(n)

O(n log n)

$O(n^2)$

O(log n)

11.

Which of the following strategies does binary search use?

Brute force

Divide and conquer

Greedy

Dynamic programming

12.

Which of the following is an example of an optimization problem?

Finding if an element exists in an array

Finding the shortest path in a graph

13.

Let f(n) = $2n^2 + 3n + 4$ . Which of the following is the tightest upper bound for f(n)?

O(n)

$O(n^2)$

$O(n^3)$

Θ(n log n)

14.

Which of the following statements is TRUE?

f(n) = Θ(g(n)) implies f(n) = O(g(n))

f(n) = O(g(n)) implies f(n) = Θ(g(n))

f(n) = Ω(g(n)) implies f(n) = Θ(g(n))

None of the above

15.

Consider the recurrence relation: T(n) = 2T(n/2) + n. What is the time complexity?

O(n)

O(n log n)

O(log n)

$O(n^2)$

16.

Which of the following is NOT part of the algorithm analysis framework?

Input size

Primitive operations

Execution time

Variable naming conventions

17.

Arrange the following efficiency classes in increasing order of growth:

$O(1)$ , $O(log n)$ , $O(n)$ , $O(n^2)$

$O(n^2)$ , $O(n)$ , $O(log n)$ , $O(1)$

$O(n)$ , $O(1)$ , $O(n^2)$ , $O(log n)$

$O(log n)$ , $O(n^2)$ , $O(1)$ , $O(n)$

18.

Arrange the following in increasing order of their asymptotic complexity:

A) 3 < 1 < 2 < 4

B) 1 < 3 < 2 < 4

C) 3 < 2 < 1 < 4

D) 3 < 1 < 2 < 4

19.

Consider the recurrence: T(n) = T(n - 1) + 1, with T(1) = 1. What is T(n)?

O(n log n)

O(n)

O(1)

$O(n^2)$

20.

Which of the following algorithms has the best worst-case time complexity for sorting?

Merge Sort

Quick Sort

Insertion Sort

Bubble Sort

21.

Which of the following problems can be efficiently solved using the divide and conquer paradigm?

Finding the majority element in an array

Graph coloring

Longest increasing subsequence

All-pairs shortest path

22.

A coin system has denominations {1, 3, 4}. What is the minimum number of coins required to make amount 6?

23.

You are given a function that solves the Tower of Hanoi problem. For n disks, how many recursive calls (excluding the initial call) are made?

$2^n - 1$

$2^n$

$2^{(n-1)}$

24.

Which of the following problems is most suitable for solving using backtracking?

Finding GCD of two numbers

Sudoku solving

Binary Search

Merge Sort

25.

Determining if a Hamiltonian path exists in a graph is an example of which problem type?

NP-complete problem

P problem

Tractable problem

Undecidable problem

26.

Which of the following is a problem with a yes/no answer?

Decision problem

Optimization problem

Search problem

Enumeration problem

27.

What will be the output of this recursive function fun(3)?

A) 1 2 3

B) 3 2 1

C) 2 3 1

D) 1 3 2

28.

Which of the following functions belong to the same class of problems in terms of efficiency class (i.e., same growth trend)?

Matrix Multiplication and Tower of Hanoi

Insertion Sort and Selection Sort

Merge Sort and Linear Search

Quick Sort and Bubble Sort

29.

Which of the following is typically solved using brute-force?

Subset sum problem

Primality testing for large numbers

Fibonacci number computation

GCD of two numbers

30.

Which of the following is NOT a valid algorithm design strategy?

A) Divide and Conquer

B) Greedy

31.

The 8-Queens Problem is best solved using which of the following techniques?

Divide and Conquer

Backtracking

Dynamic Programming

Greedy Method

32.

In a sorted array, which method guarantees locating an element if it exists and the array has duplicates?

Jump Search

Linear Search from start

Modified Binary Search to find first/last occurrence

Hashing

33.

Determining whether a graph has a cycle is best described as which type of problem?

Enumeration Problem

Optimization Problem

Decision Problem

Search Problem

34.

What does the following code fragment do? for (int i = 0; i < n; i++) { if (arr[i] == key) return i; }

Binary search

Hashing

Linear search

Jump search

35.

Q34. Which of the following problems can be simulated using a stack, mimicking recursion?

Evaluating expressions using postfix notation

Sorting an array using bubble sort

Finding the shortest path in a graph using Dijkstra's algorithm

Searching an element in a sorted array using binary search

36.

You need to solve a puzzle where the goal state depends on achieving smaller subgoals that resemble the original problem. Which technique are you most likely applying?

Backtracking

Greedy

Divide and Conquer

Brute Force

37.

A recursive algorithm solves a problem by breaking it into two subproblems of size n - 1 each. What is the total number of subproblem calls for input n = 4?

38.

You are solving a maze and need to find any path from the start to the goal. You try all possible directions from each junction until the goal is reached. What is this method?

Depth-First Search

Breadth-First Search

Greedy Selection

Dynamic Expansion

39.

You are solving the Tower of Hanoi problem with 3 disks. What is the minimum number of steps required?

40.

A problem is solved by recursively reducing input size by 1 and combining each result additively. This approach is best described as:

Greedy

Divide and Conquer

Recurrence Accumulation

Dynamic Choice

41.

You're tracing a recursive function where the first thing it does is call itself with n - 1, and then prints n. What will be the order of printed values for input n = 3?

3 2 1

1 2 3

2 3 1

3 1 2

42.

You are designing an algorithm to solve a Sudoku puzzle by filling empty cells with valid digits and backtracking when a dead end is reached. What is the search tree's depth for a grid with 10 empty cells?

100

Depends on puzzle structure

43.

You are given a chessboard and must find all positions where placing a queen will not attack others already placed. Which technique is most suited to solve the n-Queens problem?

Brute Force Enumeration

Backtracking with constraint checks

Heuristic Greedy filling

Divide and Conquer on board halves

44.

If a recursive algorithm branches into 3 subproblems at each level, how many subproblems are generated for depth d = 3?

45.

A recursive algorithm prints a number before and after calling itself on a smaller value. What pattern is expected in its output for input n = 2?

A) 2 1 1 2

B) 1 2 2 1

C) 1 1 2 2

D) 2 2 1 1

46.

A recursive problem is defined such that for input n, it makes one call to n - 1 and then performs a single constant operation. How many operations (excluding base case) are done for input n = 5?

47.

How many different permutations can be generated for a password consisting of 4 distinct characters?

256

120

48.

A recursive algorithm solving a decision problem doubles the number of subproblems at each level. How many subproblem instances are generated (total) for input level 4?

49.

A recursive problem reduces the input by 1 until it reaches 0. At each step, it performs two constant-time operations after the recursive call. How many operations are performed for n = 4?

50.

In a solution space tree, what technique is used to avoid unnecessary exploration of branches that cannot lead to a valid solution?

Preprocessing

Pruning

Memoization

Expansion

51.

You're solving two recursive problems: Problem A: One subproblem per level Problem B: Two subproblems per level Which will likely result in more recursive calls for the same input size?

Both are equal

Cannot be determined without base case

100 %

CSA06 DESIGN AND ANALYSIS OF ALGORITHMS - Worksheet

Total questions: 51

Worksheet time: 26mins

Similar Resources on Wayground