Analysis & Design of Algorithms CS-311

Analysis & Design of Algorithms (CS-311)

Course Type: Discipline Core
Batch: 3rd Year CSE, B.Tech and Dual Degree
Course Credits: 04

To impart knowledge about the asymptotic notations to analyze the performance of algorithms.
To introduce the fundamental concepts various problem-solving techniques such as divide and conquer, greedy algorithm, etc.
To enable the students to understand the concepts of P, NP, NP-hard and NP-complete problems.

Data structure and Linear Algebra

Vivekananda Lecture Hall (F5)

Monday: 10:00 AM - 11:00 AM
Tuesday: 03:00 PM - 04:00 PM
Thursday: 11:00 AM - 12:00 PM
Friday: 03:00 PM - 04:00 PM

Algorithms Introduction: Algorithm Design paradigms- motivation, concept of algorithmic efficiency, run time analysis of algorithms, Asymptotic Notations.
Divide and Conquer Approach: Structure of divide-and-conquer algorithms: sets and disjoint sets: Union and Find algorithms, quick sort, Finding the maximum and minimum, Quick Sort, Merge sort, Heap and heap sort.
Greedy Algorithms: Optimal storage on tapes, Knapsack problem, Job sequence algorithm, Huffman codes.
Graph Algorithms: Representation of graphs, BFS, DFS, Topological sort, strongly connected Component, Single source shortest paths: Bellman-Ford Algorithm.
Dynamic Programming: Overview, difference between dynamic programming and divide and conquer, Matrix chain multiplication, Traveling Salesman Problem, Longest Common sequence, 0/1 knapsack.
Backtracking: 8-Queen Problem, Sum of subsets, graph coloring, Hamiltonian cycles.
Branch and Bound: LC searching Bounding, FIFO branch and bound, LC branch and bound application: 0/1 Knapsack problem, Traveling Salesman Problem.
Computational Complexity: Complexity measures, Polynomial vs nonpolynomial time complexity; NP-hard and NP-complete classes, examples.

Upon successful completion of the course, the students will be able to:

CO1: Understand asymptotic notations to analyze the performance of algorithms.
CO2: Understand and apply various problem-solving techniques such as divide and conquer, greedy algorithm, dynamic programming, etc.
CO3: Solve given problem by selecting the appropriate algorithm design technique and justify the selection.
CO4: Know the concepts of P, NP, NP-hard and NP-complete problems.

Fundamentals of Computer Algorithms by E. Horowitz and S. Sahni, Galgotia.
Introduction to Algorithms by T.H. Cormen, C.E.Leiserson, R.L. Rivest, MIT Press, Cambridge.
The Design and Analysis of Computer Algorithms by A.V. Aho, J.E. Hopcroft and J.D. Ullman, Addison Wesley.
Grokking Algorithms, Aditya Bhargava, 1st edition,Manning.
Data Structures and Algorithms Made Easy, Narasimha Karumanchi, 5th edition, Careermonk Publications.