Course Objectives
- To analyze performance of algorithms.
- To choose the appropriate data structure and algorithm design method for a specified application.
- To understand how the choice of data structures and algorithm design methods impacts the performance of programs.
- To solve problems using algorithm design methods such as the greedy method, divide and conquer, dynamic programming, backtracking and branch and bound.
- To understand the differences between tractable and intractable problems.
- To introduce P and NP classes.
syllabus
UNIT - I
Introduction-Algorithm definition, Algorithm Specification, Performance Analysis-Space
complexity, Time complexity, Randomized Algorithms.
Divide and conquer- General method, applications - Binary search, Merge sort, Quick sort,
Strassen’s Matrix Multiplication.
UNIT - II
Disjoint set operations, union and find algorithms, AND/OR graphs, Connected Components
and Spanning trees, Bi-connected components Backtracking-General method, applications, The 8-queen problem, sum of subsets problem, graph coloring, Hamiltonian cycles.
UNIT - III
Greedy method- General method, applications- Knapsack problem, Job sequencing with
deadlines, Minimum cost spanning trees, Single source shortest path problem.
UNIT - IV
Dynamic Programming- General Method, applications- Chained matrix multiplication, All
pairs shortest path problem, Optimal binary search trees, 0/1 knapsack problem, Reliability
design, Traveling sales person problem.
UNIT - V
Branch and Bound- General Method, applications-0/1 Knapsack problem, LC Branch and
Bound solution, FIFO Branch and Bound solution, Traveling sales person problem.
NP-Hard and NP-Complete problems- Basic concepts, Non-deterministic algorithms, NP -
Hard and NP- Complete classes, Cook’s theorem.
To download the materials of all units click the below links...
Material Credits - SIA publications
Unit 1 material Download
Unit 2 material Download
Unit 3 material Download
Unit 4 material Download
Unit 5 material Download
note:
if you have any issues or any queries, please feel free to contact us.
