Still no participant
Still no reviews
Module I: Introduction to analysis and design of algorithm (4 Hrs)
Introduction to analysis and design of algorithm, Growth of functions, Asymptotic notations,
Recurrences, Solution of recurrences by substitution, Recurrence tree and the master method.
Assignment 1: Examples on Recurrences (Substitution Method, Recursion Tree Method, Master's Method)
Module II: Divide and conquer algorithms (4 Hrs)
Worst case analysis of merge sort, quick sort and heap sort
algorithms, Priority queue, Data structure for disjoint sets (Disjoint set operations, linked list
representation, disjoint set forests)
Assignment 2: Example of Merge sort, Quick sort, Heap sort Techniques
Practice:
Module III: Dynamic programming approach (4 Hrs)
Matrix chain multiplication, longest common subsequence.
Assignment 3: Example on Matrix chain Multiplication. Finding LCS among two strings
Practice :
6. Write a program to determine the LCS of two given sequences
Module IV: Greedy method (5 Hrs)
Fractional knapsack problem Greedy verses dynamic programming, Huffman codes. Concept of backtracking, branch & bound design techniques.
Assignment 4: Example on 0/1 Knapsack problem. Huffman coding.
Module V: Single source shortest paths (5 Hrs)
Graph algorithms: Minimal spanning tree (Kruskal's and
Prim’s algorithms), Single source shortest paths (Bellman-Ford and Dijkstra’s algorithm), Floyd’s algorithm.
Practice:
7. Implement Breadth-First Search in a graph
8. Implement Depth-First Search in a graph.
9. Write a program to determine the minimum spanning tree of a graph
Assignment 5: Examples on Kruskal's and Prim's Algorithm. Bellman-Ford and Dijkstra's Algorithm
Module VI: Flow Network (4 Hrs)
Ford-Fulkerson method, Fast Fourier Transform, Rabin-Karp string matching algorithm.
Assignment 6: 4 point & 8 point DIF and DIT FFT
Assignment 7: Example on Robin-Karp String matching Algorithm.
Module VII: NP-Completeness (4 Hrs)
NP Completeness, Polynomial time solvability, Verification and Reducibility, NP complete problems (without
proof), Approximation algorithm for the traveling salesman problem
Assignment 8: Example on Travelling Salesman Problem
I am text block. Click edit button to change this text. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut elit tellus, luctus nec ullamcorper mattis, pulvinar dapibus leo.
Growth of functions
https://slideplayer.com/slide/4862946/
https://www.slideserve.com/bonnie/the-growth-of-functions
Asymptotic notations
http://www.authorstream.com/Presentation/minhas1989-1414747-ppt-on-daa/
Recurrences
https://youtu.be/dq949luGrU0[/
Solution of recurrences by substitution, Recurrence tree method
https://www.geeksforgeeks.org/analysis-algorithm-set-4-master-method-solving-recurrences/
the Master's method
https://www.slideshare.net/ajacin/master-method
https://youtu.be/mJDNA6Wo0BE[/
Priority queue, Data structure for disjoint sets (Disjoint set operations
https://www.powershow.com/view1/d4215-ZDc1Z/Priority_Queues_Heaps_powerpoint_ppt_presentation?varnishcache=1
Data structure for disjoint sets (Disjoint set operations, linked list representation)
https://www.powershow.com/view4/6914eb-NjlmO/Disjoint_Set_Data_Structures_powerpoint_ppt_presentation
disjoint set forests
https://www.powershow.com/view4/6914eb-NjlmO/Disjoint_Set_Data_Structures_powerpoint_ppt_presentation
Matrix chain multiplication
longest common subsequence
https://www.powershow.com/view1/270f73-ZDc1Z/Longest_Common_Subsequence_LCS_powerpoint_ppt_presentation?varnishcache=1
Greedy verses dynamic programming
https://www.javatpoint.com/dynamic-programming-vs-greedy-method
Concept of backtracking, branch & bound design techniques
https://pediaa.com/what-is-the-difference-between-backtracking-and-branch-and-bound/
Graph algorithms: Minimal spanning tree (Kruskal's algorithms)
Graph algorithms: Minimal spanning tree (Prim’s algorithms)
https://www.tutorialspoint.com/data_structures_algorithms/prims_spanning_tree_algorithm.htm
Fractional knapsac problem
https://www.powershow.com/viewht/15fd3e-ZDc1Z/Knapsack_Problem_powerpoint_ppt_presentation
Floyd’s algorithm.
https://www.slideshare.net/SaidurRahmanKohinoor/floyd-warshall-algorithm-56194284
Ford-Fulkerson method
https://www.cs.rit.edu/~lr/courses/alg/student/1/Ford-Fulkerson%20Method.pdf
Fast Fourier Transform
https://www.slideshare.net/op205/fast-fourier-transform-presentation
Rabin-Karp string matching algorithm
Polynomial time solvability, Verification and Reducibility
NP complete problems (without proof)
Approximation algorithm for the traveling salesman problem.
Assistant Professor, Dept.IT, School of Applied Sciences, Centurion University of Technology and Management, Bolangir, Odisha, India. She has over 5 years of teaching experiences. She has educational qualification of Mtech in CSE from BPUT.