Introduction to Algorithms (BCS755B)

Introduction to Algorithms

Course Code BCS755B 
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,

Important problem Types, Fundamental Data Structures, Analysis Framework, Asymptotic

Notations and Basic Efficiency Classes, ,Analysis Framework, Asymptotic Notations and Basic

Efficiency Classes,

Chapter 1 (Sections 1.1 to 1.4), Chapter 2 (2.1, 2.2)

Module-2

FUNDAMENTALS OF THE ANALYSIS OF ALGORITHM EFFICIENCY: 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 2(Sections 2.3,2.4), Chapter 3(Section 3.1,3.2)

Module-3

Exhaustive Search (Travelling Salesman problem and Knapsack Problem).

Depth First search and Breadth First search.

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

DIVIDE AND CONQUER: Merge Sort, Binary Tree Traversals.

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

Module-4

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

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

in String Matching: Horspool’s Algorithm, Hashing.

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

Module-5

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

Functions.

THE GREEDY METHOD: Kruskal’s Algorithm, Dijkstra’s Algorithm, Huffman Trees and Codes.

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

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)