Teaching Scheme (in Hours)
Subject Credit : 6
Examination Scheme (in marks)
ESE Viva (V)
Syllabus Content Download
Unit-1: Basics of Algorithms and Mathematics
What is an algorithm?, Mathematics for Algorithmic Sets, Functions and Relations, Vectors and Matrices, Linear Inequalities and Linear Equations.
Unit-2: Analysis of Algorithm
The efficient algorithm, Average, Best and worst case analysis, Amortized analysis , Asymptotic Notations, Analyzing control statement, Loop invariant and the correctness of the algorithm, Sorting Algorithms and analysis: Bubble sort, Selection sort, Insertion sort, Shell sort Heap sort, Sorting in linear time : Bucket sort, Radix sort and Counting sort
Unit-3: Divide and Conquer Algorithm
Introduction, Recurrence and different methods to solve recurrence, Multiplying large Integers Problem, Problem Solving using divide and conquer algorithm - Binary Search, Max-Min problem, Sorting (Merge Sort, Quick Sort), Matrix Multiplication, Exponential.
Unit-4: Dynamic Programming
Introduction, The Principle of Optimality, Problem Solving using Dynamic Programming – Calculating the Binomial Coefficient, Making Change Problem, Assembly Line-Scheduling, Knapsack problem, All Points Shortest path, Matrix chain multiplication, Longest Common Subsequence.
Unit-5: Greedy Algorithm
General Characteristics of greedy algorithms, Problem solving using Greedy Algorithm - Activity selection problem, Elements of Greedy Strategy, Minimum Spanning trees (Kruskal’s algorithm, Prim’s algorithm), Graphs: Shortest paths, The Knapsack Problem, Job Scheduling Problem, Huffman code.
Unit-6: Exploring Graphs
An introduction using graphs and games, Undirected Graph, Directed Graph, Traversing Graphs, Depth First Search, Breath First Search, Topological sort, Connected components.
Unit-7: Backtracking and Branch and Bound
Introduction, The Eight queens problem , Knapsack problem, Travelling Salesman problem, Minimax principle
Unit-8: String Matching
Introduction, The naive string matching algorithm, The Rabin-Karp algorithm, String Matching with finite automata, The Knuth-Morris-Pratt algorithm.
Unit-9: Introduction to NP-Completeness
The class P and NP, Polynomial reduction, NP- Completeness Problem, NP-Hard Problems. Travelling Salesman problem, Hamiltonian problem, Approximation algorithms
|1||Introduction to Algorithms||Thomas H. Cormen, Charles E. Leiserson, Ronald L.||PHI|
|2||Fundamental of Algorithms||Gills Brassard, Paul Bratley||PHI|
|3||Introduction to Design and Analysis of Algorithms||Anany Levitin||Pearson|
|4||Foundations of Algorithms||Shailesh R Sathe||Penram|
|5||Design and Analysis of Algorithms||Dave and Dave||Pearson|
Darshan Institute of Engineering & Technology is a leading institute offering undergraduate (B.E.), postgraduate (M.E.) and Diploma programs in engineering.