Back to Subject

Unit 1: Foundations of Algorithm - Practice Quiz

CSE408 — Design And Analysis Of Algorithms 60 Questions
0 Correct 0 Wrong 60 Left
0/60

1 What is an algorithm?

Algorithms Easy
A. A sequence of unambiguous instructions for solving a problem
B. A type of data structure
C. A hardware component of a computer
D. A programming language

2 Which of the following is typically the first step in algorithmic problem solving?

Fundamentals of Algorithmic Problem Solving: Easy
A. Proving the algorithm's correctness
B. Analyzing the algorithm
C. Designing the algorithm
D. Understanding the problem

3 What are the two primary metrics used to analyze an algorithm's efficiency?

Analyzing Algorithm Easy
A. Memory and Bandwidth
B. Lines of code and Variables
C. Time and Space
D. Speed and Cost

4 Which of the following is an example of a linear data structure?

Linear Data Structure Easy
A. Graph
B. Array
C. Heap
D. Tree

5 A tree data structure is fundamentally a type of:

Graphs and Trees Easy
A. Cyclic graph
B. Acyclic connected graph
C. Stack
D. Linear data structure

6 How is the input size typically measured for an algorithm operating on an array?

Measuring of Input Size Easy
A. By the number of elements in the array
B. By the number of lines of code
C. By the physical size of the computer
D. By the time it takes to compile

7 Instead of measuring exact physical time (e.g., seconds), algorithm efficiency is typically measured by counting:

Units for Measuring Running Time Easy
A. The basic operations
B. The number of loops
C. The hardware clock cycles
D. The total bytes of memory

8 Which case analysis provides an upper bound on the running time of an algorithm?

Worst-Case, Best-Case, and Average-Case Efficiencies Easy
A. Average-case
B. Null-case
C. Best-case
D. Worst-case

9 Which case analysis determines the minimum time required to execute the algorithm?

Worst-Case, Best-Case, and Average-Case Efficiencies Easy
A. Best-case
B. Average-case
C. Amortized-case
D. Worst-case

10 Which of the following functions grows the fastest as increases?

Asymptotic Notations and Basic Efficiency Classes: Easy
A.
B.
C.
D.

11 What does Big- notation describe?

O(Big-oh)-notation Easy
A. An exact bound
B. An asymptotic lower bound
C. An asymptotic tight bound
D. An asymptotic upper bound

12 What does Big-Omega () notation describe?

Big-omega notation Easy
A. The exact running time in seconds
B. An asymptotic tight bound
C. An asymptotic upper bound
D. An asymptotic lower bound

13 What does Big-Theta () notation represent?

Big-theta notation Easy
A. The worst-case only
B. Only the lower bound
C. Both upper and lower asymptotic bounds (tight bound)
D. Only the upper bound

14 If and , then is bounded by:

Useful Property Involving the Asymptotic Notations Easy
A.
B.
C.
D.

15 When comparing two functions and , if , what does this imply?

Using Limits for Comparing Orders of Growth Easy
A. No conclusion can be drawn
B. has a smaller order of growth than
C. and have the same order of growth
D. has a larger order of growth than

16 An algorithm whose running time is independent of the input size has an order of growth denoted by:

Order of Growth Easy
A.
B.
C.
D.

17 Which data structure follows the Last-In-First-Out (LIFO) principle?

Linear Data Structure Easy
A. Stack
B. Linked List
C. Array
D. Queue

18 Which data structure follows the First-In-First-Out (FIFO) principle?

Linear Data Structure Easy
A. Tree
B. Graph
C. Stack
D. Queue

19 In a graph, the entities that are connected to each other are called:

Graphs and Trees Easy
A. Edges
B. Vertices (or Nodes)
C. Leaves
D. Roots

20 Which algorithm design technique solves a problem by breaking it down into smaller, overlapping subproblems and storing the results?

Basic Algorithm Design Techniques Easy
A. Greedy Approach
B. Brute Force
C. Dynamic Programming
D. Divide and Conquer

21 Which of the following best describes the characteristics of an algorithm?

Algorithms Medium
A. Finiteness, definiteness, input, output, effectiveness
B. Finiteness, ambiguity, input, effectiveness
C. Infiniteness, precision, input, output, effectiveness
D. Infiniteness, definiteness, input, output, efficiency

22 When designing an algorithm, what is typically the primary concern immediately after understanding the problem?

Fundamentals of Algorithmic Problem Solving: Medium
A. Proving the algorithm's correctness
B. Choosing between exact and approximate problem solving
C. Ascertaining the capabilities of the computational device
D. Deciding on appropriate data structures

23 Which design technique is characterized by dividing a problem into smaller instances of the same problem, solving them recursively, and then combining their solutions?

Basic Algorithm Design Techniques Medium
A. Dynamic Programming
B. Greedy Approach
C. Backtracking
D. Divide and Conquer

24 Which of the following is NOT typically considered when analyzing an algorithm's efficiency?

Analyzing Algorithm Medium
A. Simplicity of the code syntax
B. Time efficiency
C. Space efficiency
D. Optimality

25 Which linear data structure is most appropriate for evaluating postfix mathematical expressions?

Linear Data Structure Medium
A. Stack
B. Linked List
C. Queue
D. Hash Table

26 In a simple undirected graph with vertices, what is the maximum number of edges?

Graphs and Trees Medium
A.
B.
C.
D.

27 For a matrix multiplication algorithm involving two matrices, what is the most appropriate measure of input size?

Measuring of Input Size Medium
A. The total sum of all elements
B. The value of the largest element in the matrices
C. The dimension of the matrices
D. The number of rows in the first matrix only

28 Why is counting the number of basic operations preferred over measuring actual execution time in seconds?

Units for Measuring Running Time Medium
A. It is independent of hardware and software environments
B. It depends on the hardware speed
C. It is easier to program
D. It depends on the compiler used

29 Which of the following functions has the highest order of growth?

Order of Growth Medium
A.
B.
C.
D.

30 In Sequential Search on an array of size , what is the average-case number of key comparisons for a successful search (assuming all positions are equally likely)?

Worst-Case, Best-Case, and Average-Case Efficiencies Medium
A.
B.
C.
D.

31 If , which of the following is true regarding its Big-O notation?

O(Big-oh)-notation Medium
A.
B.
C.
D.

32 What does formally imply?

Big-omega notation Medium
A. There exist positive constants and such that for all .
B.
C. grows strictly slower than .
D. There exist positive constants and such that for all .

33 Which of the following statements is equivalent to ?

Big-theta notation Medium
A. but
B. and
C. Neither nor applies to
D. but

34 If and , what is the tightest bound for ?

Useful Property Involving the Asymptotic Notations Medium
A.
B.
C.
D.

35 If , where is a constant, what can be concluded?

Using Limits for Comparing Orders of Growth Medium
A. and have the same order of growth
B. No conclusion can be drawn
C. has a smaller order of growth than
D. has a larger order of growth than

36 Which of the following sorting algorithms exhibits a worst-case time complexity of but an average-case of ?

Worst-Case, Best-Case, and Average-Case Efficiencies Medium
A. Bubble Sort
B. Heap Sort
C. Merge Sort
D. Quick Sort

37 What is the primary advantage of a Doubly Linked List over a Singly Linked List?

Fundamental Data Structure: Medium
A. It requires less memory per node
B. It provides access time to the -th element
C. It allows traversal in both forward and backward directions
D. It inherently prevents cycle formation

38 In a binary search tree (BST), an inorder traversal yields the elements in which order?

Graphs and Trees Medium
A. Descending order
B. Ascending order
C. Random order
D. Level-by-level order

39 Evaluate the limit to determine the relative order of growth.

Using Limits for Comparing Orders of Growth Medium
A. , meaning grows faster than
B. , meaning they have the same order of growth
C. , meaning grows faster than
D. , meaning grows faster than

40 What defines the 'basic operation' of an algorithm?

Fundamentals of the Analysis of Algorithm Efficiency: Medium
A. The initialization of loop counters
B. The first operation written in the pseudo-code
C. The return statement of the algorithm
D. The operation that consumes the most time or is executed the most frequently

41 Evaluate the limit where and . What does the result imply about their asymptotic relationship?

Using Limits for Comparing Orders of Growth Hard
A. The limit is , implying
B. The limit is undefined, so they are asymptotically incomparable
C. The limit is a positive constant, implying
D. The limit is , implying

42 Which of the following statements about Big-O notation is FALSE for positive functions and ?

O(Big-oh)-notation Hard
A. If and , then
B. If , then
C. If , then
D. If , then

43 Consider an algorithm that searches a sorted array of distinct elements by probing the element at index , then performs a linear search. What is the average-case efficiency if the search key is known to be in the array and uniformly distributed?

Worst-Case, Best-Case, and Average-Case Efficiencies Hard
A.
B.
C.
D.

44 Let and . What is the relationship between and ?

Big-theta notation Hard
A.
B. They are not asymptotically comparable
C.
D.

45 Consider the recurrence relation . What is the asymptotic time complexity of ?

Analyzing Algorithm Hard
A.
B.
C.
D.

46 Rank the following functions by order of growth from slowest to fastest: , , , .

Order of Growth Hard
A.
B.
C.
D.

47 In a connected undirected graph with vertices and edges, a DFS tree is constructed. Which of the following edges CANNOT exist in relative to the DFS tree?

Graphs and Trees Hard
A. Cross edges between different subtrees
B. Tree edges
C. Forward edges to a descendant
D. Back edges to an ancestor

48 When analyzing the time complexity of an algorithm that tests whether an integer is prime by trial division up to , what is the appropriate measure of the input size and the resulting complexity?

Measuring of Input Size Hard
A. , Time
B. , Time
C. , Time
D. , Time

49 Which of the following limits proves that ?

Useful Property Involving the Asymptotic Notations Hard
A.
B.
C.
D.

50 Which design technique is MOST intrinsically linked to solving overlapping subproblems by storing their results?

Basic Algorithm Design Techniques Hard
A. Backtracking
B. Greedy Method
C. Divide and Conquer
D. Dynamic Programming

51 Let be a polynomial of degree with a positive leading coefficient, and be a polynomial of degree with a positive leading coefficient. Under what condition is ?

Big-omega notation Hard
A.
B. only
C.
D.

52 Why is counting the number of basic operations preferred over measuring the actual execution time in seconds when analyzing algorithmic efficiency?

Units for Measuring Running Time Hard
A. Basic operations always take exactly 1 nanosecond, making the calculation perfectly precise.
B. Actual time depends on specific hardware, compiler, and environmental factors, whereas operation count is machine-independent.
C. Execution time in seconds cannot be converted into asymptotic notation.
D. Basic operations naturally account for operating system context switches.

53 You are implementing a Queue using exactly two Stacks. What is the amortized time complexity of the enqueue and dequeue operations, respectively?

Linear Data Structure Hard
A. and
B. and
C. and
D. and

54 Which phase of algorithmic problem solving immediately follows the design of the algorithm and precedes coding?

Fundamentals of Algorithmic Problem Solving: Hard
A. Proving the algorithm's correctness
B. Understanding the problem
C. Testing the algorithm
D. Analyzing the algorithm's efficiency

55 Given the nested loops:

for i = 1 to n
for j = 1 to i^2
for k = 1 to n/2
count++

What is the exact asymptotic order of the count variable?

Analyzing Algorithm Hard
A.
B.
C.
D.

56 An algorithm requires operations. What class of problems typically exhibits this extremely slow-growing complexity?

Algorithms Hard
A. Interpolation search on uniformly distributed sorted data
B. Binary search on an unbalanced tree
C. Finding the maximum in an unsorted array
D. Computing the Fibonacci sequence recursively

57 For the QuickSelect algorithm used to find the -th smallest element in an unsorted array of size , what are the expected average-case and strict worst-case time complexities, respectively?

Worst-Case, Best-Case, and Average-Case Efficiencies Hard
A. and
B. and
C. and
D. and

58 A hash table uses open addressing with linear probing. The load factor is close to 1. What happens to the expected number of probes for an unsuccessful search?

Fundamental Data Structure: Hard
A. It approaches
B. It remains regardless of
C. It approaches
D. It approaches

59 If and , what can be definitively deduced about the relationship between and ?

Useful Property Involving the Asymptotic Notations Hard
A.
B.
C. No definitive asymptotic relationship can be deduced
D.

60 Let and . Evaluate the limit comparison between and .

Using Limits for Comparing Orders of Growth Hard
A. , so
B. , so
C. The limit is a constant, so
D. The limit does not exist, and the functions are not asymptotically comparable using Big-O, Big-Omega, or Big-Theta
Next MCQ
Unit 2