Design & Analysis of Algorithms (Theory & Lab)

Course Outcomes

The student will be able to:

For a given algorithms analyze worst-case running times of algorithms based on asymptotic analysis and justify the correctness of algorithms
Explain when an algorithmic design situation calls for which design paradigm (greedy/ divide and conquer/backtrack etc.)
Explain model for a given engineering problem, using tree or graph, and write the corresponding algorithm to solve the problems
Demonstrate the ways to analyze approximation/randomized algorithms (expected running time, probability of error)
Examine the necessity for NP class based problems and explain the use of heuristic techniques

Detailed Syllabus

Module 1: Introduction

Characteristics of algorithm. Analysis of algorithm: Asymptotic analysis of complexity bounds – best, average and worst-case behavior; Performance measurements of Algorithm, Time and space trade-offs, Analysis of recursive algorithms through recurrence relations: Substitution method, Recursion tree method and Masters' theorem.

Module 2: Fundamental Algorithmic Strategies

Brute-Force, Greedy, Dynamic Programming, Branch-and-Bound and Backtracking methodologies for the design of algorithms; Illustrations of these techniques for Problem-Solving: Bin Packing, Knap Sack, TSP.

Module 3: Graph and Tree Algorithms

Traversal algorithms: Depth First Search (DFS) and Breadth First Search (BFS); Shortest path algorithms, Transitive closure, Minimum Spanning Tree, Topological sorting, Network Flow Algorithm.

Module 4: Tractable and Intractable Problems

Computability of Algorithms, Computability classes – P, NP, NP-complete and NP-hard. Cook's theorem, Standard NP-complete problems and Reduction techniques.

Module 5: Advanced Topics

Approximation algorithms, Randomized algorithms, Heuristics and their characteristics.

Text Books

Introduction to Algorithms, 4TH Edition, Thomas H Cormen, Charles E Lieserson, Ronald L Rivest and Clifford Stein, MIT Press/McGraw-Hill.
Data Structures and Algorithms in C++, Weiss, 4th edition, Pearson.
Fundamentals of Computer Algorithms – E. Horowitz, Sartaj Saini, Galgota Publications.

Reference Books

Algorithm Design, 1st Edition, Jon Kleinberg and Eva Tardos, Pearson.
Algorithm Design: Foundations, Analysis, and Internet Examples, Second Edition, Michael T Goodrich and Roberto Tamassia, Wiley.
Algorithms -- A Creative Approach, 3RD Edition, Udi Manber, Addison-Wesley, Reading, MA.

Design & Analysis of Algorithms Lab (BTCS 405-18)

List of Experiments

Code and analyze solutions to following problem with given strategies:
- Knap Sack using greedy approach
- Knap Sack using dynamic approach
Code and analyze to find an optimal solution to matrix chain multiplication using dynamic programming.
Code and analyze to find an optimal solution to TSP using dynamic programming.
Implementing an application of DFS such as:
- to find the topological sort of a directed acyclic graph
- to find a path from source to goal in a maze
Implement an application of BFS such as:
- to find connected components of an undirected graph
- to check whether a given graph is bipartite
Code and analyze to find shortest paths in a graph with positive edge weights using Dijkstra's algorithm.
Code and analyze to find shortest paths in a graph with arbitrary edge weights using Bellman-Ford algorithm.
Code and analyze to find shortest paths in a graph with arbitrary edge weights using Flyods' algorithm.
Code and analyze to find the minimum spanning tree in a weighted, undirected graph using Prims' algorithm
Code and analyze to find the minimum spanning tree in a weighted, undirected graph using Kruskals' algorithm.
Coding any real world problem or TSP algorithm using any heuristic technique.

Lab Outcomes