CS3401 Algorithms
Department of Computer Science and Engineering
UNIT I INTRODUCTION 9
Algorithm analysis: Time and space complexity - Asymptotic Notations and its
properties Best case, Worst case and average case analysis – Recurrence relation:
substitution method – Lower bounds – searching: linear search, binary search and
Interpolation Search, Pattern search: The naïve string-matching algorithm - Rabin-
Karp algorithm - Knuth-Morris-Pratt algorithm. Sorting: Insertion sort – heap sort
UNIT II GRAPH ALGORITHMS 9
Graph algorithms: Representations of graphs - Graph traversal: DFS – BFS -
applications -Connectivity, strong connectivity, bi-connectivity - Minimum
spanning tree: Kruskal’s and Prim’salgorithm- Shortest path: Bellman-Ford
algorithm - Dijkstra’s algorithm - Floyd-Warshall algorithm Network flow: Flow
networks - Ford-Fulkerson method – Matching: Maximum bipartite matching
UNIT III ALGORITHM DESIGN TECHNIQUES 9
Divide and Conquer methodology: Finding maximum and minimum - Merge sort -
Quick sort Dynamic programming: Elements of dynamic programming — Matrix-
chain multiplication – Multistage graph — Optimal Binary Search Trees. Greedy
Technique: Elements of the greedy strategy- Activity-selection problem –- Optimal
Merge pattern — Huffman Trees.
UNIT IV STATE SPACE SEARCH ALGORITHMS 9
Backtracking: n-Queens problem - Hamiltonian Circuit Problem - Subset Sum
Problem – Graph colouring problem Branch and Bound: Solving 15-Puzzle
problem - Assignment problem -Knapsack Problem - Travelling Salesman Problem
UNIT V NP-COMPLETE AND APPROXIMATION ALGORITHM 9
Tractable and intractable problems: Polynomial time algorithms – Venn diagram
representation -NP-algorithms - NP-hardness and NP-completeness – Bin Packing
problem - Problem reduction:TSP – 3-CNF problem. Approximation Algorithms:
TSP - Randomized Algorithms: concept and application - primality testing -
randomized quick sort - Finding kth smallest number
Unit 1
Part A
1. Define Time Complexity of an Algorithm?
2. List the type of asymptotic notations in analysing complexity of algorithms.
3. Define recursion relations.
4. Discuss the time and space complexity of insertion sort.
5. State how the running time of an algorithm is measured.
6. Outline the significance of performing worst case analysis of an algorithm.
7. What is average case efficiency?
8. What is space complexity?
9. What is validation of algorithm?
10. How do you measure the efficiency of an algorithm.
Part B and Part C
1. Write an algorithm to perform linear search on an array of ‘N’ numbers.
Illustrate the best case, average case, and worst-case complexity of the
linear search algorithm with an example.
2. What is pattern searching? Outline the steps in the Rabin-Karp algorithm
for pattern searching with an example.
3. Solve the following recurrence relation: (1) T(n)=T(n/2)+1, where n=2k for all
k> 0 (2) T(n)=T(n/3)+T(2n/3)+cn, where ‘c’ is a constant and ‘n’ is the input
size.
4. Explain in detail about naïve string matching alogorithm.
5. Write the asymptotic notations used for best case,average case and worst
case analysi of lgorithms. Writa an algorithm for finding maximum elements
in an array. Give best,worst and average case complexities.
Unit 2
Part A
1. Define a graph.
2. What is complete graph?
3. What is biconnectivity?
4. Write down the optimization technique used for Warshalls algorithm. State
the rules and assumptions which are implied behind that.
5. Define transitive closure of a directed graph.
6. Write short notes on the Maximum-Flow problem.
7. Define maximum cardinality.
8. Define Bipartite Graphs?
9. How is a transportation network represented?
10.Define the constraint in the context of maximum flow problem.
Part B&C
1. Write an algorithm for all pairs shortest path algorithm and what are the
time and space complexity of the algorithm.
2. Discuss about the algorithm and pseudocode to find the Minimum
Spanning Tree using Prim’s Algorithm. Find the Minimum Spanning Tree
for the graph. Discuss about the efficiency of the algorithm.
3.Explain Floyd algorithm with example. Write down and explain the algorithm
to solve all pairs shortest paths problem
4.Explain the Ford-Fulkerson method with a step-by-step example. Illustrate
how the maximum flow is calculated in a sample network.
5. Explain Dijkstra’s algorithm using the following graph. Find the shortest path
between v1, v2, v3, v4, v5, v6 & v7
Unit 3
Part A
1. Explain the Divide and Conquer methodology with an example.
2. Describe the process of finding the maximum and minimum using Divide
and Conquer.
3. State the time complexity of Merge Sort and Quick Sort in the best, worst,
and average cases.
4. What is the basic idea behind the Quick Sort algorithm?
5. What are the key components of dynamic programming?
6. Explain the concept of Matrix-chain multiplication with an example.
7. What is the time complexity of the Matrix-chain multiplication algorithm?
8. Define the multi-stage graph problem and give an example of its application.
9. What is an Optimal Binary Search Tree (OBST)?
10. What is the greedy approach to the Activity-Selection problem?
Part B and C
1. Explain the Merge Sort algorithm with pseudocode. Sort the following array
using Merge Sort:[38,27,43,3,9,82,10] Also, explain the time complexity of
Merge Sort and Quick Sort.
2. (i) Write the Huffman code algorithm and derive its time complexity.(ii)
Generate the Huffman code for the following data comprising of alphabet
and their frequency. a:1,b:1,c:2,d:3,e:5,f:8,g:13,h:21
3. 3.What is a Huffman tree? Outline the steps to build a Huffman tree using
greedy algorithm design paradigm with an example
4. Explain the dynamic programming approach of matrix multiplication with
an example.
5. What is divide and conquer strategy and explain the binary search with
suitable example problem
Unit 4
Part A
1. What is the backtracking technique? Explain with an example.
2. Explain the approach to solving the n-Queens problem using backtracking.
3. Define the Hamiltonian Circuit Problem and explain how it is solved using
backtracking.
4. Describe the Subset Sum Problem and its solution using backtracking.
5. What is the graph coloring problem, and how is it solved using
backtracking?
6. What is the Branch and Bound method?
7. State the steps involved in solving the 15-Puzzle problem using the Branch
and Bound method.
8. What is the Knapsack Problem, and how is it solved using Branch and
Bound?
9. Explain the assignment problem and how it is solved using Branch and
Bound.
10. Describe the Travelling Salesman Problem (TSP) and how Branch and
Bound can be applied to solve it.
Part B and C
1. Explain the backtracking approach to solving the n-Queens problem. Write a
program or pseudocode for placing n queens on an n×n chessboard so that no two
queens threaten each other.
2. Explain the 15-Puzzle problem. Use the Branch and Bound method to solve a
simplified version of the 3×3 puzzle with the following initial and goal states:
Initial State:
123
456
780
Goal State:
123
456
708
3. Illustrate the Hamiltonian circuit problem. Outline the steps to find the
Hamilton circuit using backtracking algorithm design paradigm with an example
4.Build the Knapsack problem. Outline how Knapsack problem can be solved
using branch and bound algorithm design paradigm with an example
5.Identify the steps to solve Travelling Salesperson problem using branch and
bound approach. Explain with an example.
Unit 5
Part A
1. What is the difference between a tractable and an intractable problem?
2. Explain Polynomial Time Algorithms and their significance in problem-
solving.
3. What is NP-completeness? Briefly explain the importance of this concept.
4. Describe the Venn diagram representation of tractable, NP-hard, NP-
complete, and NP algorithms.
5. Define NP-hard problems and provide one example.
6. What is the Bin Packing problem and how does it relate to NP-
completeness?
7. What is problem reduction? How is it used in solving NP-complete
problems?
8. Define the 3-CNF problem and explain how it can be reduced to the
Traveling Salesman Problem (TSP).
9. What is an approximation algorithm? How does it differ from an exact
algorithm?
10. Explain the concept of randomized algorithms with one example.
Part B/C Questions
1. Explain the concept of NP-completeness and prove that the Traveling
Salesman Problem (TSP) is NP-complete. Describe a reduction from the 3-
CNF problem to TSP.
2. Explain the Approximation Algorithm for solving the Traveling Salesman
Problem (TSP). Show how a simple approximation algorithm works, and
calculate the approximation factor for a given set of cities.
3. Explain the Bin Packing problem and describe a polynomial-time
approximation algorithm to solve it. Demonstrate the algorithm on the
following set of items with weights:
[2,3,4,5,6,7,8]
with a bin capacity of 10.
4. Define randomized algorithms and explain how they are applied in primality
testing. Provide an example of a randomized algorithm for testing whether a
given number is prime, and explain its time complexity.
5. Explain Randomized Quick Sort and its advantages over the traditional
Quick Sort. Additionally, describe how to find the kth smallest element in
an array using a randomized approach
