**CS3401 **

**ALGORITHMS**

**COURSE
OBJECTIVES:**

• To understand and apply the algorithm
analysis techniques on searching and
sorting algorithms

• To critically analyze the efficiency of
graph algorithms

• To understand different algorithm design
techniques

• To solve programming problems using
state space tree

• To understand the concepts behind NP
Completeness, Approximation algorithms and randomized algorithms.

**UNIT
I INTRODUCTION**

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

Graph
algorithms: Representations of graphs - Graph traversal: DFS – BFS -
applications - Connectivity, strong connectivity, bi-connectivity - Minimum
spanning tree: Kruskal’s and Prim’s algorithm- 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**

Divide
and Conquer methodology: Finding maximum and minimum - Merge sort - Quick sort
Dynamic programming: Elements of dynamic programming — Matrix-chain
multiplication - Multi stage 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**

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

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 k^{th} smallest number

** **

**PRACTICAL
EXERCISES:**

**Searching and
Sorting Algorithms**

1. Implement Linear Search. Determine the
time required to search for an element. Repeat the experiment for different
values of n, the number of elements in the list to be searched and plot a graph
of the time taken versus n.

2. Implement recursive Binary Search.
Determine the time required to search an element. Repeat the experiment for
different values of n, the number of elements in the list to be searched and
plot a graph of the time taken versus n.

3. Given a text txt [0...n-1] and a pattern
pat [0...m-1], write a function search (char pat [ ], char txt [ ]) that prints
all occurrences of pat [ ] in txt [ ]. You may assume that n > m.

4. Sort a given set of elements using the
Insertion sort and Heap sort methods and determine the time required to sort
the elements. Repeat the experiment for different values of n, the number of
elements in the list to be sorted and plot a graph of the time taken versus n.

**Graph Algorithms**

1. Develop a program to implement graph
traversal using Breadth First Search

2. Develop a program to implement graph
traversal using Depth First Search

3. From a given vertex in a weighted
connected graph, develop a program to find the shortest paths to other vertices
using Dijkstra’s algorithm.

4. Find the minimum cost spanning tree of a
given undirected graph using Prim’s algorithm.

5. Implement Floyd’s algorithm for the
All-Pairs- Shortest-Paths problem.

6. Compute the transitive closure of a given
directed graph using Warshall's algorithm.

**Algorithm Design
Techniques**

1. Develop a program to find out the maximum
and minimum numbers in a given list of n numbers using the divide and conquer
technique.

2. Implement Merge sort and Quick sort
methods to sort an array of elements and determine the time required to sort.
Repeat the experiment for different values of n, the number of elements in the
list to be sorted and plot a graph of the time taken versus n.

**State Space
Search Algorithms**

1. Implement N Queens problem using
Backtracking.

**Approximation
Algorithms Randomized Algorithms**

1.
Implement any scheme to find the optimal solution for the Traveling Salesperson
problem and then solve the same problem instance using any approximation
algorithm and determine the error in the approximation.

2.
Implement randomized algorithms for finding the kth smallest number. The
programs can be implemented in C/C++/JAVA/ Python.

**COURSE
OUTCOMES:**

At
the end of this course, the students will be able to:

CO1:
Analyze the efficiency of algorithms using various frameworks

CO2:
Apply graph algorithms to solve problems and analyze their efficiency.

CO3:
Make use of algorithm design techniques like divide and conquer, dynamic
programming and greedy techniques to solve problems

CO4:
Use the state space tree method for solving problems.

CO5:
Solve problems using approximation algorithms and randomized algorithms

**TEXT
BOOKS:**

1. Thomas H. Cormen, Charles E. Leiserson,
Ronald L. Rivest and Clifford Stein, "Introduction to Algorithms",
3rd Edition, Prentice Hall of India, 2009.

2. Ellis Horowitz, Sartaj Sahni, Sanguthevar
Rajasekaran “Computer Algorithms/C++” Orient Blackswan, 2nd Edition, 2019.

**REFERENCES:**

1. Anany Levitin, “Introduction to the
Design and Analysis of Algorithms”, 3rd Edition, Pearson Education, 2012.

2. Alfred V. Aho, John E. Hopcroft and
Jeffrey D. Ullman, "Data Structures and Algorithms", Reprint Edition,
Pearson Education, 2006.

3. S. Sridhar, “Design and Analysis of
Algorithms”, Oxford university press, 2014.