Algorithm Design and Analysis - Compiled Questions

Here is the aggregated list of all questions across the provided exam papers, grouped strictly by Topic and
then by Subtopic.

1. Introduction

Analysis of algorithm (including Performance measurements, Time and space

trade-offs, Characteristics)

• Worst case time complexity of merge sort

• Proof: f(n)=O(n^m)
• Lower bound for any comparison sort
• O(g(n)) is
• Big O notation of f(n)=n log n + n² + e^log n
• Complexity of non-deterministic algorithm
• Sorting technique with element placement
• Best/worst case time complexity of Quick sort
• Prove n! = O(n^n)
• Asymptotic notation
• Lower bound of any comparison sort
• o(g(n)) is
• Asymptotically smallest function
• Statements about NP hard and matrix multiplication
• Complexity of merge sort
• Minimum lower bound for sorting
• The time factor when determining the efficiency of an algorithm is measured by
• Which of the following is used to depict the working of algorithm?
• Complexity of Tower of Hanoi problem
• Best and worst case time complexity of quick sort
• Asymptotic Notations
• Complexity of Tower of Hanoi
• Algorithm for x^n with O(log n)
• Complexity analysis of MCM
• Amortized Analysis
• Complexity of algorithm with two independent parts
• Depiction of algorithm working
• Comparisons in merge sort worst case
• Time complexity of Binary Search
• Efficiency of an algorithm time factor
• Best case time complexity of Binary search algorithm is
• Space complexity of Merge sort algorithm is
• Write down the properties of an algorithm.
• Write an algorithm to find the value of x^n, where n is integral power of 2 in O(log n) time.
• Show that the time complexity of your algorithm is O(log n).
• Best and worst case complexity of Quick sort
• What are the features of any Algorithm?

Asymptotic analysis of complexity bounds

• O-notation provides an asymptotic

• Worst case running time of quick sort
• Ω-notation definition
• Big-O notation for f(n)
• Lower bound for comparison sorting
• Correct complexity claims
• Asymptotically smallest function
• Asymptotic notation definitions (O, o, Ω)
• Asymptotic notations
• Θ-Notation
• Asymptotic notations (O, o, Ω, Θ)
• State True/False: O(log n) > O(n)
• Define little omega (ω) notation.
• What is represented by the asymptotic notation O(1)?
• The notation Θ(n) is the formal way to express the ______ bound of an algorithm's running time.
• Discuss the different Asymptotic notations and their importance.
• State True/False: O(2^n) > O(n²) for n>3.
• State True/False: if f(n)=2n³+4n², then f(n)=O(n³).
• Define Little oh (o) notation.
• Prove that: log n! = O(n log n).
• If f■(n)=O(g■(n)) and f■(n)=O(g■(n)), then prove that f■(n)+f■(n)=O(max(g■(n), g■(n))).
• If f■(n)=O(g■(n)) and f■(n)=O(g■(n)) then prove that f■(n) × f■(n)=O(g■(n) × g■(n)).
Analysis of recursive algorithms (through Recurrence Relations, Master's Theorem,
Recursion Tree, Generating Functions)

• Time complexity for recurrence T(n)=2T(n/2)+n

• Recurrence relation using generating function
• Quick sort average case complexity
• Complexity of T(n)=2T(√n)+1
• Recursion tree for T(n)=T(n-a)+T(a)+cn
• Master's theorem and recurrence complexity
• Complexity of recurrence T(n)=8T(n/2)+n²
• Master's theorem and recurrence T(n)=T(2n/3)+1
• Recursion tree for T(n)=T(n-a)+T(a)+cn
• Recurrence relation T(n)=aT(n/b)+f(n) proofs
• Recursion Trees
• Recursion tree for T(n)=T(n-a)+T(a)+cn
• Tail recursion
• Cannot be performed recursively
• Recurrence relation using generating function
• Binary search recurrence and time complexity
• Recursion Tree vs. Substitution method; recurrence T(n)=T(n/4)+T(n/2)+Θ(n²)
• Order of recursive algorithm T(n)=c+T(n-1)
• Recurrence derivation T(n)=2T(n/2)+5n
• Recursion tree
• Master's theorem and recurrence T(n)=2T(n^{1/2})+log n
• Solve recurrence relation using generating function
• Recursion Tree
• Differentiate between recursion and iteration.
• Find the time complexity of the following recurrence relations using Master's Theorem.
• Time complexity for recurrence relation T(n)=2T(n/2)+n is
• Analyze the time complexity of quick sort algorithm for best case and worst case using recurrence
relations.
• Write the recurrence relation for computing the time complexity of "Towers of Hanoi" problem. Also solve
the recurrence relation to get the time complexity.
• Find the time complexity of the following recurrence relation using Recursion Tree Method. Clearly
mention each step: T(n)=3 × T(n/4)+cn²
• Suppose we have a recurrence relation T(n)=aT(n/b)+f(n). Show the following: a) If a f(n/b)=k · f(n) for
some constant k < 1, then T(n)=O(f(n)). b) If a f(n/b)=k · f(n) for some constant k > 1, then T(n)=O(n^{logb
a}). c) If a f(n/b)=k · f(n) for some constant k = 1, then T(n)=O(f(n)logb n).
• How can you convert the following recursion algorithm (Algorithm 1) to tail recursion? Algorithm 1 Fib (n)
i) if n ≤ 1 then ii) Return (n) iii) else iv) Return Fib(n-1) + Fib(n-2) v) end if

2. Fundamental Algorithmic Strategies

Brute-Force (including Sorting and Divide and Conquer Illustrations)

• Linear search vs binary search

• Strassen's matrix multiplication
• Sorting technique with element placement
• Time complexity of insertion sort is
• Approach in Divide & Conquer algorithms
• Binary Search algorithm can't be applied to
• Tight bound for building a max heap
• Strassen's Matrix Multiplication
• Lower bound for comparison sorting
• Worst case time complexity of Merge Sort
• Design technique in quick-sort
• Merge sort comparisons for 2 elements
• Sorting method for almost sorted list
• Space requirement for quick sort
• External Sorting
• Algorithm design technique used in quick sort
• Heap Creation Technique
• State True/False: Brute Force method gives the best quality of solution.
• Define Brute Force Algorithm.
• Write down an algorithm of Quick Sort.
• Time complexity of Heap sort with n items is
• Let A[1..n] be a sorted array of n distinct integers. Give a divide-and-conquer algorithm that can find an
index i such that A[i] = i (if one exists) with running time O(log n).
• The worst case time complexity of Heap sort is
• Write down an algorithm for Quick Sort.

Greedy (including Knapsack, TSP, Job Sequencing, Activity Selection Illustrations)

• Optimal solution for knapsack (100 kg)

• Greedy vs Dynamic programming
• Fractional Knapsack optimal solution
• Characteristics of greedy algorithm
• Activity selection problem
• Kruskal algorithm is a
• Optimal substructure property is exploited by
• Difference between 0-1 and fractional Knapsack
• General Knapsack problem (Greedy)
• Kruskal's Algorithm is an example of
• Optimal solution for fractional knapsack
• Greedy algorithm characteristics, Activity selection, Greedy vs DP
• Knapsack greedy solution
• Dynamic programming vs. Greedy
• Activity selection problem
• Knapsack using greedy method
• Match Fractional/0-1 Knapsack with technique
• Prim's algorithm technique
• Job sequencing with deadlines
• Solve knapsack problem (Greedy)
• Characteristics of Greedy method
• Fractional Knapsack problem
• Job Sequencing with Deadlines
• Greedy strategy for 0-1 knapsack
• General Knapsack problem and greedy algorithm
• What is the time complexity of Knapsack algorithm using Greedy method?
• Write down an algorithm to solve the Job Sequencing with Deadline Problem using Greedy method.
• Fractional knapsack problem is solved most efficiently by which algorithm design technique?
• The 0-1 Knapsack problem can be solved using Greedy algorithm - state True or False.
• Given items as value, weight pairs {(40,20),(30,10),(20,5)}. The capacity of knapsack is 20 kg. Find the
maximum value output assuming items to be divisible
• For the given set of 5 items and the knapsack capacity of 10 kg, find the maximum profit. You are
allowed to take fractional amount of any item.
• Write the greedy algorithm for job sequencing with deadline.
• Using greedy method, find an optimal solution to the problem of job sequencing with deadline where n=4
and (d1,d2,d3,d4)=(2,1,2,1)
• What is the time complexity of Job Sequencing with Deadline algorithm using Greedy method?
• What is the time complexity of Prim's algorithm using Greedy method? Number of vertices = V.
• What is the time complexity of Kruskal's algorithm using Greedy method? Number of edges = E.
• Find the maximum profit and solution vector of the following fractional knapsack problem: Profit
P={16,60,150,25,150}, Weight W={4,10,50,5,75}, Knapsack Size m=44
Dynamic Programming (including Matrix Chain Multiplication, 0/1 Knapsack
Illustrations)

• Dynamic programming/Greedy difference

• 0/1 knapsack problem
• Matrix chain multiplication dynamic programming
• Characteristics of dynamic programming / Matrix-chain
• Matrix chain multiplication
• Optimal parenthesization (Matrix Chain Multiplication)
• Algorithm for matrix chain multiplication
• Dynamic programming definition and chain matrix multiplication
• Divide and conquer vs. dynamic programming
• Matrix chain multiplication via dynamic programming
• Dynamic programming for Matrix Chain Multiplication
• Find the minimum number of scalar operations needed to multiply the matrices (Matrix Chain
Multiplication).
• Discuss the advantages and drawbacks of Dynamic Programming.
• Find the minimum number of multiplications required for the following matrix chain multiplication using
Dynamic programming
• What do you mean by dynamic programming? Write the algorithm of matrix-chain multiplication.

Backtracking (including N-Queens, Graph Coloring, Hamiltonian Cycle Illustrations)

• Hamiltonian cycle/permutation tree

• Eight queens algorithm
• 3-colouring problem
• Eight queen problem algorithm
• Backtracking for Hamiltonian cycles
• Algorithm for n-queen's problem
• Backtracking for graph-coloring problem
• 8-Queens Problem
• Algorithm for n-queen's problem
• Apply backtracking for 3-colouring problem
• Backtracking follows ______ traversal technique.
• Write an algorithm to find all solutions of N-Queens problem using backtracking.
• How many solutions are there for 8 queens problem on 8 × 8 board?
• Write an algorithm to find all Hamiltonian cycles from a graph using backtracking.
• Write an algorithm to find all the solutions of graph coloring problem.
• Find all the solutions for the given graph using your algorithm. Number of available colors is 3.
Branch-and-Bound (including 15-Puzzle, TSP Illustrations)

• Branch and Bound method problem

• 15-puzzle problem (Branch and Bound)
• 15-Puzzle Problem
• Problem solved by Branch and Bound
• Differentiate between Backtracking and Branch and Bound.
• Solve the Travelling Salesman Problem using Branch and Bound technique with the given graph image.

Heuristics
• Name one heuristic method of searching.

Illustrations of these techniques for Problem-Solving (including General, TSP, Bin-Packing)

• Travelling salesman problem belongs to
• Quick sort algorithm and complexities
• Traveling Salesman Problem is
• Graph coloring problem algorithm
• Minimum color for graph with n>3 and 2 edges
• Graph Coloring problem
• Min colours for graph with n>3 vertices and 2 edges
• Graph colouring problem
• Give two examples of Optimization Problems.
• What is Bin-Packing problem?
• Define graph coloring problem.

3. Graph and Tree Algorithms

Traversal algorithms (DFS and BFS)

• Compare and contrast BFS vis-a-vis DFS

• BFS running time
• Graph representation
• Node removal making graph disconnected
• Adjacency matrix with self-loop
• Level order traversal technique
• Time to generate connected components
• Adjacency matrix representation limitation
• Data structure for Breadth First Traversal
• BFS complexity with adjacency list
• BFS and DFS
• State True/False: Adjacency matrix and Path Matrix are same.
• Define graph terms (Directed, Undirected, In-Degree, Out-Degree, Complete, Articulation Point, Bridge).
• What is the appropriate data structure for Depth First Search algorithm?
• DFS uses ______ data structure.

Minimum Spanning Tree (Prim's and Kruskal's)

• Minimum cost spanning tree for the graph (with diagram)

• Prim's algorithm vs Kruskal's algorithm
• Minimum cost spanning tree (with diagram)
• Minimal spanning tree algorithm and complexity
• Minimum weight edge in MST
• Minimum spanning tree algorithm
• MST algorithm and time complexity
• Kruskal's algorithm
• Minimum spanning tree
• Algorithm for Minimum Spanning Tree
• What is spanning tree?
• Find the minimum spanning tree using Prim's method.
• Write down an algorithm using Greedy method to find minimum spanning tree by Kruskal's algorithm.
• What is the appropriate data structure for Prim's Minimum Spanning Tree algorithm?
• Define spanning tree.
• Using Prim's algorithm generate the MST from the following graph

Shortest path algorithms (Dijkstra, Bellman-Ford, Floyd-Warshall)

• Dijkstra algorithm and shortest path

• Bellman-Ford's algorithm and complexity
• Complexity of Floyd's algorithm
• APSP problem using Floyd-Warshall's algorithm
• Dijkstra's Algorithm
• Negative weight-cycle and Bellman-Ford
• Which algorithm solves All-Pair Shortest Path?
• The time complexity of Floyd's algorithm is
• Write an algorithm to find all pairs shortest path using Floyd's method.
• Which algorithm is used to solve the single source shortest path problem in a graph with negative edge
weights?
• What are the differences between Dijkstra's algorithm and Bellman-Ford algorithm? Compare their time
complexities.
• Write the Floyd-Warshall Algorithm for all-pairs shortest path problem. What will be the time complexity?
• Write the algorithm for single source shortest path (-ve edge weights allowed)

Network Flow Algorithm (Max-Flow Min-Cut, Ford-Fulkerson)

• Max-flow min-cut theorem

• Max-Flow-Min-Cut Theorem
• Max-flow min-cut theorem and Ford-Fulkerson algorithm
• Find the maximum flow of the following network.
• Which algorithm is used to solve a maximum flow problem?
• What is a Flow Network? What are the constraints of flow in a network?
• What is an augmenting path in a flow network? Explain residual capacity - how it is calculated.
• Write the Ford-Fulkerson Algorithm for finding maximum flow.

Topological sorting
• Topological sorting is performed on ______ graph.

Transitive closure
• Find the transitive closure of vertex A from the following graph.

4. Tractable and Intractable Problems

Computability of Algorithms / Computability classes (P, NP, NP-complete, NP-hard)

• True statement about NP-hard/complete

• Complexity of non-deterministic algorithm
• Define P, NP, NP-complete
• Correct statement regarding reduction (A ≤_P B)
• Statements about NP hard and matrix multiplication
• P, NP, Reductions, and Clique Decision Problem (CDP)
• Non-deterministic graph colouring
• Traveling Salesman Problem class
• NP-Hard and NP-complete relation
• Relation between NP-hard and NP-complete
• P, NP, NP-hard, NP-complete definitions, relations, and nondeterministic algorithms
• Traveling salesman problem complexity class
• P, NP, NP-complete, NP-hard classes
• Deterministic vs. non-deterministic algorithms
• Travelling Salesman problem is
• Non-deterministic algorithms
• Define P and NP classes
• Relations among P, NP, NP-hard, NP-complete
• State True/False: Ordered searching algorithm is a Polynomial Algorithm.
• State True/False: Travelling Salesman Problem is a Non-Polynomial problem.
• Write and explain the classes P, NP, NP-hard and NP-complete.
• "If any NP-complete problem can be solved in polynomial time then P=NP" explain.
• Define Optimization Problem and Decision Problem.
• Give two examples of Non-Polynomial algorithms.
• Is your algorithm solvable in polynomial time? Justify.

Standard NP-complete problems

• Circuit-SAT and NP
• Clique Decision Problem (CDP)
• Traveling Salesman Problem class
• Vertex cover problem
• Clique Decision problem
• Vertex Cover Problem
• Define Clique with example.
• What is Vertex Cover Problem? Explain with example.

Reduction techniques
• Polynomial reductions

Cook's theorem
• Satisfiability problem and Cook's theorem
• State Cook's Theorem.

5. Advanced Topics

Approximation algorithms

• Approximation algorithms
• Approximation algorithm and uses
• Approximation schemes
• State True/False: Approximation algorithm guarantees the best quality of solution.
• Define Approximation Algorithm.
• Write short note on Randomized algorithms.
• State True/False: Approximation ratio is always less than or equal to 1.
• Define Absolute Approximation and Relative Approximation.
• Write an Approximation algorithm for Vertex Cover problem.
• Illustrate your approximation algorithm with the given graph image.

Out of syllabus / Advanced Topics outside layout

• Tail Recursion (2007 Paper)
• Union-find algorithm (2007 Paper)
• DFT algorithm (2008-9 Paper)
• Turing machines (2009-10 Paper, 11c-iii)
• Write the FFT algorithm and find the computational complexity of this algorithm. (2010-11 Paper)
• Knuth-Morris-Pratt Algorithm (2012 Paper)
• Union-find algorithm (2012 Paper)
• Knuth-Morris-Pratt (KMP) algorithm (2013-14 Paper)
• Apply KMP algorithm (2013-14 Paper)
• LUP decomposition (2013-14 Paper)
• Knuth-Morris-Pratt string matching algorithm (2014-15 Paper)
• Knuth-Morris-Pratt string matching (2015-16 Paper)