Subject Details
Dept     : CSE
Sem      : 4
Regul    : 2019
Faculty : Ms.Saranya S
phone  : 8675734838
E-mail  : saranya.s.cst@snsce.ac.in
98
Page views
0
Files
0
Videos
0
R.Links

Icon
Syllabus

UNIT
1
INTRODUCTION

Notion of an Algorithm - Fundamentals of Algorithmic Problem Solving - Important Problem Types — Fundamentals of the Analysis of Algorithm Efficiency - Analysis Framework - Asymptotic Notations and its properties - Mathematical analysis for Recursive and Non-recursive algorithms.

UNIT
2
BRUTE FORCE AND DIVIDE-AND-CON UER

Brute Force - Closest-Pair and Convex-Hull Problems-Exhaustive Search - Traveling Salesman Problem - Knapsack Problem - Assignment problem. Divide and conquer methodology - Merge sort — Quick sort — Binary search — Multiplication of Large Integers- Strassen"s Matrix Multiplication-Closest-Pair and Convex-Hull Problems.

UNIT
3
DYNAMIC PROGRAMMING AND GREEDY TECHNIQUE

Computing a Binomial Coefficient — Warshall"s and Floyd" algorithm - Optimal Binary Search Trees - Knapsack Problem and Memory functions. Greedy Technique— Prim"s al orithm- Kruskal's Al orithm-Di'kstra's Al orithm-Huffman Trees.

UNIT
4
ITERATIVE IMPROVEMENT

The Simplex MeFthod-The Maximum-Flow Problem - Maximm Matching in Bipartite Graphs- The Stable marriage Problem.

UNIT
5
COPING WITH THE LIMITATIONS OF ALGORITHM POWER

Limitations of Algorithm Power-Lower-Bound Arguments-Decision Trees-P, NP and NPComplete Problems--Coping with the Limitations - Backtracking - n-Queens problem — Hamiltonian Circuit Problem - Subset Sum Problem-Branch and Bound - Assignment problem - Knapsack Problem - Traveling Salesman Problem- Approximation Algorithms for NP - Hard Problems - Travelin Salesman roblem - Kna sack roblem

Reference Book:

1 homas H.Cormen, Charles E.Leiserson, Ronald L. Rivest and Clifford Stein, 1. Introduction to Algorithms", Third Edition, PHI Learning Private Limited, 2012. 2. Alfred V. Aho, John E. Hopcroft and Jeffrey D. Ullman, "Data Structures and Igorithms", Pearson Education, Reprint 2006.

Text Book:

1. Anany Levitin, "Introduction to the Design and Analysis of Algorithms", Third Edition, Pearson Education, 2012.

 

Print    Download