Analysis & Design of Algorithms (BCS401)

Analysis & Design of Algorithms

Course Code BCS401 
CIE Marks 50
Teaching Hours/Week (L: T:P: S) 3:0:0:0 
SEE Marks 50
Total Hours of Pedagogy 40 
Total Marks 100
Credits 03 
Exam Hours 03
Examination type (SEE) Theory

Module-1

INTRODUCTION: What is an Algorithm?, Fundamentals of Algorithmic Problem Solving.

FUNDAMENTALS OF THE ANALYSIS OF ALGORITHM EFFICIENCY: Analysis Framework,

Asymptotic Notations and Basic Efficiency Classes, Mathematical Analysis of Non recursive

Algorithms, Mathematical Analysis of Recursive Algorithms.

BRUTE FORCE APPROACHES: Selection Sort and Bubble Sort, Sequential Search and Brute

Force String Matching.

Chapter 1 (Sections 1.1,1.2), Chapter 2(Sections 2.1,2.2,2.3,2.4), Chapter 3(Section

3.1,3.2)

Module-2

BRUTE FORCE APPROACHES (contd..): Exhaustive Search (Travelling Salesman probem and

Knapsack Problem).

DECREASE-AND-CONQUER: Insertion Sort, Topological Sorting.

DIVIDE AND CONQUER: Merge Sort, Quick Sort, Binary Tree Traversals, Multiplication of

Large Integers and Strassen’s Matrix Multiplication.

Chapter 3(Section 3.4), Chapter 4 (Sections 4.1,4.2), Chapter 5 (Section 5.1,5.2,5.3, 5.4)

Module-3

TRANSFORM-AND-CONQUER: Balanced Search Trees, Heaps and Heapsort.

SPACE-TIME TRADEOFFS: Sorting by Counting: Comparison counting sort, Input Enhancement

in String Matching: Horspool’s Algorithm.

Chapter 6 (Sections 6.3,6.4), Chapter 7 (Sections 7.1,7.2)

Module-4

DYNAMIC PROGRAMMING: Three basic examples, The Knapsack Problem and Memory

Functions, Warshall’s and Floyd’s Algorithms.

THE GREEDY METHOD: Prim’s Algorithm, Kruskal’s Algorithm, Dijkstra’s Algorithm, Huffman

Trees and Codes.

Chapter 8 (Sections 8.1,8.2,8.4), Chapter 9 (Sections 9.1,9.2,9.3,9.4)

Module-5

LIMITATIONS OF ALGORITHMIC POWER: Decision Trees, P, NP, and NP-Complete Problems.

COPING WITH LIMITATIONS OF ALGORITHMIC POWER: Backtracking (n-Queens problem,

Subset-sum problem), Branch-and-Bound (Knapsack problem), Approximation algorithms for

NP-Hard problems (Knapsack problem).

Chapter 11 (Section 11.2, 11.3), Chapter 12 (Sections 12.1,12.2,12.3)

Suggested Learning Resources:

Textbooks

1. Introduction to the Design and Analysis of Algorithms, By Anany Levitin, 3rd Edition (Indian),

2017, Pearson.

Reference books

1. Computer Algorithms/C++, Ellis Horowitz, SatrajSahni and Rajasekaran, 2nd Edition, 2014,

Universities Press.

2. Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronal L. Rivest, Clifford

Stein, 3rd Edition, PHI.

3. Design and Analysis of Algorithms, S. Sridhar, Oxford (Higher Education)

Web links and Video Lectures (e-Resources):

● Design and Analysis of Algorithms: https://nptel.ac.in/courses/106/101/106101060/