Design and Analysis of Algorithms
🔹 UNIT 1: Foundation of Algorithm Analysis
1. What is an algorithm? Explain the properties of an algorithm. Why do we need algorithms?
Solution
An algorithm is a finite sequence of well-defined steps used to solve a problem.
It takes input values, processes them, and produces output values.
Properties of an Algorithm
The properties of an algorithm define the conditions that make an algorithm valid and effective.
These properties ensure correctness, termination, and efficiency.
Properties
Input
An algorithm can have zero or more inputs.
Output
It must produce at least one output.
Correctness
It gives the correct output for every valid input.
Finiteness
The algorithm terminates after finite steps.
Definiteness
Every step is clear and unambiguous.
Effectiveness
Each operation is simple and executable in finite time.
Generality
The algorithm works for all instances of a problem.
Algorithms are needed to solve problems systematically.
They provide a logical and efficient method for computation.
Reasons
Efficiency
Reduces time and memory usage.
Scalability
Handles large input sizes effectively.
Consistency
Same input always produces the same output.
Automation
Enables automatic execution of tasks.
Example
Binary Search is faster than Linear Search for large datasets.
2. Explain the RAM model with a suitable example. Define time and space complexity.
Soluton
3. Explain best, worst, and average case complexity.
Solution
The RAM (Random Access Machine) model is a theoretical model used to analyze algorithms.
It assumes that each basic operation takes constant time.
It helps in machine-independent analysis of algorithms.
The loop runs n − 1 times.
Each step inside the loop takes constant time.
Time Complexity = O(n)
Space Complexity = O(1)
The RAM model helps analyze algorithms in a simple and uniform manner.
Time Complexity
Time complexity is the measure of time taken by an algorithm.
It depends on the number of steps executed.
It is expressed using Big-O notation.
Example
A loop that runs from 1 to n has time complexity O(n).
Space Complexity
Space complexity is the measure of memory used by an algorithm.
It includes variables and data structures.
It is also represented using Big-O notation.
Example
Using fixed variables gives O(1) space.
Using an array of size n gives O(n) space.
Conclusion
The RAM model provides a standard method for algorithm analysis.
Time and space complexity help compare algorithms based on speed and memory usage.
Explain aggregate analysis with example.
Solution
Aggregate analysis is a method used to analyze the total cost of a sequence of operations.
It determines the overall running time for n operations.
The average cost per operation is then calculated.
Steps in Aggregate Analysis
Find the total cost T(n) of n operations in the worst case.
Divide the total cost by n to get average cost per operation.
Example: Stack Operations
Consider push and pop operations in a stack.
Each push takes constant time O(1).
Each pop also takes constant time O(1).
For n stack operations, total time = O(n).
Average time per operation = O(n) / n = O(1).
Explain Big-O notation with example.
Solution
Big-O notation is used to describe the upper bound of an algorithm’s time or space complexity.
It shows how the running time grows with input size n.
It represents the worst-case performance of an algorithm.
Mathematical Definition
A function f(n) = O(g(n)) if there exist positive constants c and n₀ such that:
0 ≤ f(n) ≤ c · g(n) for all n ≥ n₀.
Here, g(n) is the upper bound of f(n).
Explain Big-Ω notation with example.
Solution
Big-Ω (Big-Omega) notation is used in computer science to describe the lower bound of an algorithm’s running time.
It guarantees that the algorithm will take at least this much time for large inputs.
Given two functions g(n) and f(n), we say that f(n) = Ω(g(n)), if there exists constants c > 0 and n0 >= 0 such that f(n) >= c*g(n) for all n >= n0.
In simpler terms, f(n) is Ω(g(n)) if f(n) will always grow faster than c*g(n) for all n >= n0 where c and n0 are constants.
Explain Big-Θ notation with example.
Solution
Big Theta (Θ) notation is used in algorithm analysis when an asymptotically tight bound is required for a function.
It indicates that a function f(x) is of the same order as another function g(x).
Compare Big-O, Big-Ω, and Big-Θ.
Explain the geometrical interpretation of asymptotic notations.
Solution
Asymptotic notations like Big O, Omega, and Theta are used to describe the growth rate of functions.
Geometrically, these notations define "envelopes" or boundaries on a graph that a function must stay within as the input n grows toward infinity.
What is a recurrence relation?
Solution
A recurrence relation is an equation or inequality that describes a function in terms of its values on
smaller inputs.
To solve a recurrence relation means to obtain a function defined on the natural
numbers that satisfy the recurrence.
To solve recursive algorithms, we need to define their recurrence
relation and by using any one of the recurrence relations solving method we calculate their
complexity.
Solve recurrence using recursion tree method.
( T(n) = 2T(n/2) + 1 )
( T(n) = T(n-1) + 1 )
Solution
Solve recurrence using substitution method.
( T(n) = 2T(n/2) + 1 )
( T(n) = T(n-1) + 1 )
Solution
Solve recurrence using Master’s theorem.
( T(n) = 2T(n/2) + 1 )
( T(n) = T(n-1) + 1 )
Solution
🔹 UNIT 2: Iterative Algorithms
1. Write an iterative algorithm to find the factorial and analyze it.
Solution
The factorial of a number n is the product of all positive integers from 1 to n.
It is denoted by n!.
Factorial can be calculated using an iterative approach.
Algorithm (Iterative Factorial)
Start
Read a number n
Set fact = 1
For i = 1 to n
fact = fact × i
Print fact
Stop
Analysis
Time Complexity: O(n), because the loop runs n times.
Space Complexity: O(1), because only constant variables are used.
2. Write an algorithm to find the nth Fibonacci number and analyze it.
Solution
Fibonacci series is a sequence where each number is the sum of the previous two numbers.
Algorithm (Iterative Fibonacci)
Start
Set first = 0, second = 1
Read the term number n
Set i = 3
While (i ≤ n)
temp = first + second
first = second
second = temp
i = i + 1
Print temp
Stop
Analysis
Time Complexity: O(n), because the loop executes (n − 2) times.
Space Complexity: O(1), since only a fixed number of variables are used.
3. Explain Euclid’s algorithm for GCD.
Solution
GCD (Greatest Common Divisor) is the largest positive integer that divides two numbers exactly.
Euclid’s algorithm is an iterative method to find the GCD using division.
It is based on the principle that GCD(m, n) = GCD(n, m % n).
Algorithm (Euclid’s Method)
Start
Read two numbers m and n
While (n ≠ 0)
r = m % n
m = n
n = r
Print m as the GCD
Stop
Analysis
Time Complexity: O(n), because the loop executes a finite number of times.
Space Complexity: O(1), since only constant variables are used.
4. Define sequential search. Write its algorithm and analyze it.
Solution
Sequential search is a searching technique that checks elements one by one.
It is also known as linear search.
It compares the search key with each element until a match is found or the list ends.
Algorithm (Sequential Search)
Start
Read the search key
Compare the key with the first element of the array
If a match is found, print “Search Successful” and stop
Otherwise, compare the key with the next element
Repeat steps 4 and 5 until the last element is checked
If no match is found, print “Search Unsuccessful.”
Stop
Analysis
Time Complexity: O(n), because each element may be compared once.
Space Complexity: O(n), because the array requires n memory locations.
5. Write an algorithm for selection sort and analyze it.
Solution
Selection sort is a simple sorting technique.
It repeatedly selects the smallest element from the unsorted part.
The selected element is placed in its correct position.
Algorithm (Selection Sort)
Start
For i = 0 to n − 1
Assume A[i] as the minimum element
For j = i + 1 to n − 1
If A[j] < A[i], update minimum
Swap the minimum element with A[i]
Repeat until the array is sorted
Stop
Analysis
Time Complexity: O(n²), due to nested loops.
Space Complexity: O(n), since the array requires n memory locations.
6. Write an algorithm for insertion sort and analyze it.
Solution
Insertion sort is a comparison-based sorting algorithm.
It builds the sorted list one element at a time.
The first element is considered already sorted.
Algorithm (Insertion Sort)
Start
For i = 1 to n − 1
Set temp = A[i]
Set j = i − 1
While (j ≥ 0 and A[j] > temp)
Shift A[j] to A[j+1]
Decrease j by 1
Insert temp at position j + 1
Repeat until all elements are sorted
Stop
Analysis
Time Complexity: O(n²) in average and worst cases.
Space Complexity: O(n), since the array requires n memory locations.
7. Compare bubble sort, selection sort, and insertion sort.
1. Bubble Sort
Advantages
Very simple and easy to understand
Easy to implement
Works well for small datasets
Disadvantages
Very slow for large datasets
High number of comparisons and swaps
Worst and average time complexity is O(n²)
2. Selection Sort
Advantages
Simple algorithm
Fewer swaps compared to bubble sort
Performance does not depend on data order
Disadvantages
Time complexity is always O(n²)
Not efficient for large datasets
Do unnecessary comparisons
3. Insertion Sort
Advantages
Faster than bubble and selection sort for small data
Efficient for nearly sorted lists
Simple and stable sorting method
Disadvantages
Slow for large datasets
Worst-case time complexity is O(n²)
More shifting operations in reverse order of data
Conclusion
Bubble sort is the least efficient.
Selection sort reduces swaps, but still slow.
Insertion sort is the best among the three for small or partially sorted data.
🔹 UNIT 3: Divide and Conquer Algorithms
Explain divide and conquer strategy with example.
Write recursive algorithm for binary search and analyze it.
Write min-max algorithm using divide and conquer and analyze it.
Write merge sort algorithm and analyze its complexity.
Write quick sort algorithm and analyze best, worst, and average case.
What is the worst case of quick sort? How does randomized quick sort handle it?
Trace quick sort for a given array.
Explain heapify operation with example.
Write heap sort algorithm and analyze it.
Trace heap sort for given data.
Define order statistics problem.
Explain selection in expected linear time.
Explain selection in worst-case linear time.
🔹 UNIT 4: Greedy Algorithms
What is an optimization problem?
What is greedy strategy?
When does greedy algorithm give optimal solution?
Explain elements of greedy strategy.
Solve fractional knapsack problem using greedy method.
Write job sequencing with deadlines algorithm and analyze it.
Find minimum spanning tree using Kruskal’s algorithm.
Find minimum spanning tree using Prim’s algorithm.
Explain Dijkstra’s algorithm with complexity.
What is Huffman coding?
Construct Huffman codes for given frequencies.
Find total number of bits using Huffman coding.
🔹 UNIT 5: Dynamic Programming
What is dynamic programming?
Explain elements of dynamic programming.
Compare greedy algorithm and dynamic programming.
Compare recursion and dynamic programming.
Explain memoization strategy.
Compare dynamic programming and memoization.
Solve matrix chain multiplication using DP.
Find optimal parenthesization of matrix chain.
Find edit distance between two strings using DP.
Solve 0/1 knapsack problem using DP.
Explain Floyd-Warshall algorithm.
Find all-pairs shortest path using Floyd-Warshall algorithm.
Explain travelling salesman problem using DP.
🔹 UNIT 6: Backtracking
What is backtracking?
How does backtracking differ from recursion?
Solve subset sum problem using backtracking.
Trace subset sum algorithm for given set and sum.
Solve 0/1 knapsack problem using backtracking.
Explain N-queen problem using backtracking.
Analyze time complexity of backtracking algorithms.
Does backtracking give multiple solutions? Explain.
🔹 UNIT 7: Number Theoretic Algorithms
Explain Euclid’s algorithm and analyze it.
Explain extended Euclid’s algorithm and analyze it.
Why is extended Euclid’s algorithm used?
Solve modular linear equations.
Solve system of congruences using Chinese Remainder Theorem.
Explain Miller-Rabin randomized primality test.
Analyze complexity of Miller-Rabin test.
🔹 UNIT 8: NP-Completeness & Approximation Algorithms
Define tractable and intractable problems.
Explain polynomial time and super-polynomial time.
Define class P.
Define class NP.
Define NP-Hard problems.
Define NP-Complete problems.
State Cook’s theorem.
Explain problem reducibility.
Prove SAT is NP-Complete.
Prove vertex cover is NP-Complete.
Prove subset sum is NP-Complete.
What is approximation algorithm?
Explain approximation algorithm for vertex cover.
Explain approximation algorithm for subset sum.
