Advanced algorithms (AA)
syllabus
UNIT - I
Introduction: Role of Algorithms in computing, Order Notation, Recurrences, Probabilistic Analysis and Randomized Algorithms. Sorting and Order Statistics: Heapsort, Quicksort and Sorting in Linear Time. Advanced Design and Analysis Techniques: Dynamic Programming- Matrix chain Multiplication, Longest Common Subsequence, and optimal binary Search trees. (Chapters - 1, 2)
UNIT - II
Greedy Algorithms - Huffman Codes, Activity Selection Problem. Amortized Analysis. Graph Algorithms: Topological Sorting, Minimum Spanning trees, Single Source Shortest Paths, Maximum Flow algorithms. (Chapters - 3, 4)
UNIT - III
Sorting Networks: Comparison Networks, Zero-one principle, bitonic Sorting Networks, Merging Network, Sorting Network. Matrix Operations - Strassen's Matrix Multiplication, inverting matrices, Solving system of Linear Equations. (Chapters - 5, 6)
UNIT - IV
String Matching: Naive String Matching, Rabin-Karp algorithm, matching with finite Automata, Knuth- Morris - Pratt algorithm. (Chapter - 7)
UNIT - V
NP-Completeness and Approximation Algorithms: Polynomial-time, polynomial-time verification, NP-Completeness and reducibility, NP-Complete problems. Approximation Algorithms- Vertex cover Problem, Travelling Salesperson problem. (Chapter - 8)
Click here to download the syllabus copy Download
refer model paper Download
To download the materials of all units click the below links...
Unit 1 material click here
Unit 2 material click here
Unit 3 material click here
Unit 4 material click here
Unit 5 material click here
note: this material is for educational purposes only not for sale
if any issues please feel free to contact me.
Credits - Technical publications
