Teaching Scheme (in Hours)
Subject Credit : 5
Examination Scheme (in marks)
ESE Viva (V)
Syllabus Content Download
From problems to programs, set theory, functions and relations Insertion sort, analyzing algorithms, designing algorithms, asymptotic notation.
Divide and conquer, Strassen’s algorithm for matrix multiplication, The substitution method for solving recurrences, The recursion tree method for solving recurrences, master method.
Dynamic programming, Making Change, The principal of optimality, the knapsack problem, Floyd’s algorithm for shortest paths.
Greedy Algorithms, making change, Knapsack problem, Shortest Path – Dijkstra’s algorithm, Huffman codes.
Amortized analysis- aggregate analysis, accounting method, potential method.
Single source shortest paths. Bellman Ford, directed acyclic graphs, Floyd Warshall algorithm.
Number theoretic algorithms, Greatest common dividor, Modular arithmetic.
String matching, the naïve string matching, Rabin Karp algorithm,Boyer Moore pattern matching, Knuth Moriss Pratt algorithm.
Introduction to NP completeness, The class P and NP, polynomial reductions, NP complete problems.
Heuristic algorithm – the travelling salesperson, approximate algorithms-knapsack problem.
After learning the course the students should be able to:
- Perform best case and worst case analysis of algorithm.
- Solve recurrence problem.
- Find optimal solution by applying various methods.
- Apply pattern matching algorithms to find particular pattern.
- Differentiate polynomial and nonpolynomial problems.
- Find shortest path for directed and undirected graph.
Darshan Institute of Engineering & Technology is a leading institute offering undergraduate (B.E.), postgraduate (M.E.) and Diploma programs in engineering.