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 type of data structure
B. A programming language
C. A hardware component of a computer
D. A sequence of unambiguous instructions for solving a problem

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

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

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

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

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

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

5 A tree data structure is fundamentally a type of:

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

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 lines of code
B. By the number of elements in the array
C. By the time it takes to compile
D. By the physical size of the computer

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 number of loops
B. The total bytes of memory
C. The basic operations
D. The hardware clock cycles

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. Null-case
B. Worst-case
C. Best-case
D. Average-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. Worst-case
C. Average-case
D. Amortized-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 asymptotic tight bound
B. An asymptotic lower bound
C. An exact bound
D. An asymptotic upper bound

12 What does Big-Omega () notation describe?

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

13 What does Big-Theta () notation represent?

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

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 larger order of growth than
C. has a smaller order of growth than
D. and have the same order of growth

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. Array
B. Stack
C. Queue
D. Linked List

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

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

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. Roots
D. Leaves

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. Dynamic Programming
B. Greedy Approach
C. Divide and Conquer
D. Brute Force

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

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

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

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

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. Greedy Approach
B. Divide and Conquer
C. Dynamic Programming
D. Backtracking

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

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

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

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

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 dimension of the matrices
B. The total sum of all elements
C. The number of rows in the first matrix only
D. The value of the largest element in the matrices

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 easier to program
B. It depends on the compiler used
C. It depends on the hardware speed
D. It is independent of hardware and software environments

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. grows strictly slower than .
C.
D. There exist positive constants and such that for all .

33 Which of the following statements is equivalent to ?

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

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

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. Merge Sort
B. Bubble Sort
C. Heap 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 inherently prevents cycle formation
B. It allows traversal in both forward and backward directions
C. It provides access time to the -th element
D. It requires less memory per node

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

Graphs and Trees Medium
A. Level-by-level order
B. Descending order
C. Random order
D. Ascending 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 grows faster than
C. , meaning grows faster than
D. , meaning they have the same order of growth

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 return statement of the algorithm
C. The first operation written in the pseudo-code
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 undefined, so they are asymptotically incomparable
B. The limit is , implying
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 , then
B. If , then
C. If and , 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.
C.
D. They are not asymptotically comparable

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. Forward edges to a descendant
B. Cross edges between different subtrees
C. Back edges to an ancestor
D. Tree edges

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. Dynamic Programming
B. Backtracking
C. Divide and Conquer
D. Greedy Method

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.
C.
D. only

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 naturally account for operating system context switches.
B. Actual time depends on specific hardware, compiler, and environmental factors, whereas operation count is machine-independent.
C. Basic operations always take exactly 1 nanosecond, making the calculation perfectly precise.
D. Execution time in seconds cannot be converted into asymptotic notation.

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. Understanding the problem
B. Proving the algorithm's correctness
C. Analyzing the algorithm's efficiency
D. Testing the algorithm

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.
D. No definitive asymptotic relationship can be deduced

60 Let and . Evaluate the limit comparison between and .

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