Unit 1 - Previous Questions

Notion of an Algorithm

Define an algorithm and explain its fundamental characteristics (finiteness, definiteness, input, output, effectiveness).
Provide an example of a simple real-world process that can be described as an algorithm.
Differentiate between an algorithm and a program.
What are the properties or characteristics of a "good" algorithm?.
Discuss why the study of algorithms is important in computer science.
Justify the statement: "An algorithm is a notion."

Outline and explain the general steps involved in the algorithm design and analysis process, from understanding the problem to implementing and testing the solution. You may use a flowchart to illustrate this.
What does it mean to prove the correctness of an algorithm? Why is it important?

List and briefly explain common categories of algorithmic problems (e.g., sorting, searching, string processing, graph problems, combinatorial problems, geometric problems, numerical problems).
Explain the concepts of a graph and a weighted graph, using examples.
Describe the two primary methods for representing graphs in computer memory (e.g., adjacency matrix, adjacency lists). Provide an example for each method.

What is meant by the "input size" of an algorithm? How is it typically measured for problems like sorting, matrix multiplication, or graph traversal?
What are the basic operations considered when analyzing the efficiency of an algorithm?
Define the "running time" of an algorithm. What factors can influence it?
Define what is meant by the time complexity and space complexity of an algorithm.
What is the "order of growth" of an algorithm's running time? Why is it a crucial concept for comparing algorithms?
Explain the concepts of worst-case, best-case, and average-case efficiency analysis for algorithms.
Provide an example of an algorithm and discuss its best-case, worst-case, and average-case scenarios.
Justify why worst-case analysis is often considered more important than average-case analysis in the study of algorithms.

Define Big O (O), Big Omega (Ω), and Big Theta (Θ) notations. Explain the significance of each in analyzing algorithm efficiency.
Provide examples for each asymptotic notation (O, Ω, Θ).
Explain why asymptotic notations are beneficial in algorithm analysis.
List and describe the basic asymptotic efficiency classes (e.g., constant, logarithmic, linear, n log n, quadratic, cubic, exponential), providing an example for each.
Compare and contrast O, Ω, and Θ notations.

For each of the following functions, indicate how its value changes if its input n is increased eightfold: a) log₂n b) n c) n² d) n³ e) 2ⁿ
If an algorithm has a time complexity of O(n²), can we also say it is O(n³)? Explain.
If an algorithm has a time complexity of Θ(n), can we also say it is O(n²)? Explain.
Compare the order of growth for the following pairs of functions. State whether the first function has a smaller, larger, or the same order of growth as the second: a) n(n+1) and 200n⁴ b) 2^(n-1) and 2ⁿ
Prove the property: If t₁(n) ∈ O(g₁(n)) and t₂(n) ∈ O(g₂(n)), then t₁(n) + t₂(n) ∈ O(max{g₁(n), g₂(n)}).
For the following functions, express their complexity using Big O, Big Omega, and Big Theta notation: a) f(n) = 10n³ + 8 b) g(n) = 100n + 5
Arrange the following functions in ascending order of their growth rates:
- (n-2)!, 5lg(n+100)¹⁰, 2²ⁿ, 0.001n⁴+3n³+1, ln²n, ³√n, 3ⁿ
Using the definitions of O, Θ, and Ω, determine whether the following assertions are true or false. Justify your answers. a) n(n+1)/2 ∈ O(n³) b) n(n+1)/2 ∈ Θ(n³) c) n(n+1)/2 ∈ Ω(n)

Outline the general plan or steps for analyzing the time efficiency of non-recursive algorithms.
How do you analyze algorithms with nested loops? Provide an example.
Analyze the time complexity of an algorithm that finds the maximum element in an array of n numbers.
Develop an algorithm for the "element uniqueness problem" (checking if all elements in a given array are distinct) and derive its time complexity.
Develop an algorithm for multiplying two n x n matrices and analyze its time complexity.
Write a non-recursive algorithm to compute the factorial of a given non-negative integer n and analyze its time efficiency.
Design a non-recursive algorithm to compute the sum of the squares of the first ‘n’ natural numbers (i.e., 1² + 2² + ... + n²). Analyze its time complexity.
Consider the following algorithm:

	ALGORITHM Sum(n)
	// Input: A non-negative integer n
	Sum ← 0
	For i ← 1 to n do
		Sum ← Sum + i
	Return Sum

What is a recurrence relation? How is it used to describe the efficiency of recursive algorithms?
Describe the general plan or steps for analyzing the time efficiency of recursive algorithms.
Provide a complete analysis of the Towers of Hanoi problem:
- a) Explain the recursive algorithm.
- b) Set up the recurrence relation for the number of moves and solve it to find the algorithm's time efficiency.
Set up and solve the recurrence relation for the time complexity of computing n (factorial) using a recursive algorithm.
State the Master Theorem. Explain its components and when it can be applied to solve recurrence relations.
Solve the following recurrence relations to determine their order of growth, using the Master Theorem if applicable:
- a) T(n)=2T(n/2)+n, for n > 1, T(1)=1. (You may assume n is a power of 2)
- b) T(n)=T(n/2)+1, for n > 1, T(1)=1.
- c) T(n)=3T(n−1), for n > 1, T(1)=4.

Design and explain the Sequential Search algorithm. Analyze its time complexity for best-case, worst-case, and average-case scenarios.
Justify the statement: “More than one algorithmic method can be used for solving the same problem.” Do this by:
- a) Describing two distinct algorithms for computing the Greatest Common Divisor (GCD) of two integers (e.g., Euclid's algorithm and consecutive integer checking).
- b) Analyzing and comparing these two algorithms, discussing their pros, cons, or relative efficiencies.
Illustrate the prime factorization method to find the GCD of two specific numbers, for example, 180 and 30.