Design and Analysis of Algorithm

Teacher

Mrs.Monalisa Joshi

Category

Core Courses

Course Attendees

Still no participant

Course Reviews

Still no reviews

Course Name : Design and Analysis of Algorithm

Code(Credit) : BSIT2401 (3-2-1)

Course Objectives

The objective of this course is to study paradigms and approaches used to analyze and design algorithms and to appreciate the impact of algorithm design in practice. It also ensures that students understand how the worst-case time complexity of an algorithm is defined
How asymptotic notation is used to provide a rough classification of algorithms,
how a number of algorithms for fundamental problems in computer science and engineering work and compare with one another, and how there are still some problems for which it is unknown whether there exist
efficient algorithms, and how to design efficient algorithms.

Learning Outcomes

  • An Algorithm is a sequence of steps to solve a problem.
  • Design and Analysis of Algorithm is very important for designing algorithm to solve different types of problems in the branch of computer science and information technology.
  • This introduces the fundamental concepts of Designing Strategies, Complexity analysis of Algorithms, followed by problems on Graph Theory and Sorting methods.
  • This also includes the basic concepts on Complexity theory.

Course Syllabus

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:

 1. Implement Insertion Sort (The program should report the number of comparisons)
2. Implement Merge Sort(The program should report the number of comparisons)
3. Implement Heap Sort(The program should report the number of comparisons)
4. Implement Randomized Quick sort (The program should report the number of comparisons
5. Implement Radix Sort

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.

Assignment 6:  Examples on  Bellman-Ford and Dijkstra's Algorithm

Module VI: Flow Network (4 Hrs)

Ford-Fulkerson method, Fast Fourier Transform, Rabin-Karp string matching algorithm.

Assignment 7: 4 point  DIF and DIT FFT

Assignment 8: 8 point  DIF and DIT FFT

Assignment 9: 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 10:  Example on Travelling Salesman Problem

Session Plan

Session 1

Growth of functions

https://youtu.be/AdmmEEWyZlg

https://www.javatpoint.com/daa-asymptotic-analysis-of-algorithms

http://www.authorstream.com/Presentation/minhas1989-1414747-ppt-on-daa/

Session 2

Asymptotic notations

 

http://www.authorstream.com/Presentation/minhas1989-1414747-ppt-on-daa/

 

https://youtu.be/7dz8Iaf_weM

Session 3

Recurrences https://edurev.in/studytube/Lecture-12-Recurrences-PowerPoint-Presentation--Al/61730de9-7a2e-4262-8d3c-797ae3ecc6b8_p https://youtu.be/Yo_LkK2-WDM

Session 4

Solution of recurrences by substitution, Recurrence tree method https://youtu.be/BgNMiygrUrA https://www.geeksforgeeks.org/analysis-algorithm-set-4-master-method-solving-recurrences/

Session 5

The Master's  method https://www.slideshare.net/ajacin/master-method https://youtu.be/Prks3leZbdQ

Session 6

Quick sort, Merge sort https://youtu.be/7h1s2SojIRw https://youtu.be/mB5HXBb_HY8 Practice:  1. Implement Insertion Sort (The program should report the number of comparisons) https://youtu.be/DfRA0WdNtTI 2. Implement Merge Sort(The program should report the number of comparisons) https://youtu.be/zWMBypwL9vY 3. Implement Heap Sort(The program should report the number of comparisons) https://youtu.be/Y1RDWlz_BJI 4. Implement Randomized Quick sort (The program should report the number of comparisons https://youtu.be/JQalSk4RocI 5. Implement Radix Sort https://youtu.be/vhxpMcDwRPM
 

Session 7

Heap Sort http://heap sort algorithms https://youtu.be/h1rS6cvzIEo

Session 8

Examples solved in min heap and max heap https://youtu.be/3lj-euktmOc https://www.slideshare.net/mohammedarif89/heap-sort-18479976

Session 9

Priority queue, Data structure for disjoint sets (Disjoint set operations https://youtu.be/OxhYCLWMdHs  

Session 10

Data structure for disjoint sets (Disjoint set operations, linked list representation) https://youtu.be/OxhYCLWMdHs https://www.powershow.com/view4/6914eb-NjlmO/Disjoint_Set_Data_Structures_powerpoint_ppt_presentation

Session 11

disjoint set forests https://youtu.be/2KejM1XZQKU https://www.powershow.com/view4/6914eb-NjlmO/Disjoint_Set_Data_Structures_powerpoint_ppt_presentation

Session 12

Matrix chain multiplication https://youtu.be/prx1psByp7U
https://youtu.be/WN8oqF_vbcI

Session 13

Examples on Matrix chain multiplication   https://youtu.be/WN8oqF_vbcI  

Session 14

longest common subsequence https://youtu.be/NnD96abizww https://www.powershow.com/view1/270f73-ZDc1Z/Longest_Common_Subsequence_LCS_powerpoint_ppt_presentation?varnishcache=1

Session 15

Examples on LCS of two strings

https://youtu.be/P-mMvhfJhu8

https://www.tutorialspoint.com/design_and_analysis_of_algorithms/design_and_analysis_of_algorithms_longest_common_subsequence.htm

Practice:

6. Write a program to determine the LCS of two given sequences 

https://youtu.be/FxTjAWaRubU

Session 16

Concept of backtracking, branch & bound design techniques https://youtu.be/DKCbsiDBN6c https://pediaa.com/what-is-the-difference-between-backtracking-and-branch-and-bound/

Session 17

Graph algorithms: Minimal spanning tree (Kruskal's  algorithms) https://youtu.be/5XkK88VEILk https://www.xpowerpoint.com/kruskals-algorithm-for-finding-a-minimum-spanning-tree-115-90-52--PPT.html
Practice: 7. Implement Breadth-First Search in a graph  https://youtu.be/qeE1tkhNLZk 8. Implement Depth-First Search in a graph https://youtu.be/zozEqVy-sKA

Session 18

Graph algorithms: Minimal spanning tree (Prim’s algorithms) https://youtu.be/Uj47dxYPow8 https://www.tutorialspoint.com/data_structures_algorithms/prims_spanning_tree_algorithm.htm Practice: 9. Write a program to determine the minimum spanning tree of a graph  https://youtu.be/qGp37svIN9E

Session 19

Huffman codes https://youtu.be/co4_ahEDCho https://www.gatevidyalay.com/tag/huffman-coding-example-ppt/

Session 20

Fractional knapsac problem https://youtu.be/4i-Q-vMYCu8 https://www.powershow.com/viewht/15fd3e-ZDc1Z/Knapsack_Problem_powerpoint_ppt_presentation

Session 21

Bellman-Ford algorithm https://youtu.be/FtN3BYH2Zes
https://www.slideshare.net/tanu696/shortest-pathsbf

Session 22

Dijkstra’s algorithm https://youtu.be/Lfb8qkXzHY0   https://www.slideshare.net/ami_01/dijkstras-algorithm-7716656

Session 23

Floyd’s algorithm. https://youtu.be/t3mf2Vu9wA4   https://www.slideshare.net/SaidurRahmanKohinoor/floyd-warshall-algorithm-56194284

Session 24

Maximum flow problem (Ford-Fulkerson method) https://youtu.be/Iwc3Uj4aaF4 https://www.cs.rit.edu/~lr/courses/alg/student/1/Ford-Fulkerson%20Method.pdf

Session 25

Example on Ford Fulkerson Algorithm https://youtu.be/hmIrJCGPPG4

Session 26

Fast Fourier Transform https://youtu.be/BXghmsH-mKY https://www.slideshare.net/op205/fast-fourier-transform-presentation

Session 27

Rabin-Karp string matching algorithm ttps://youtu.be/qQ8vS2btsxI https://www.powershow.com/viewfl/407eba-OTQyM/String_Matching_Using_the_Rabin

Session 28

Polynomial time solvability, Verification and Reducibility https://youtu.be/f7U7UK6iiU4 https://www.powershow.com/view1/1e6905-ZDc1Z/NP-Completeness_powerpoint_ppt_presentation?varnishcache=1

Session 29

NP complete problems (without proof) https://youtu.be/ckwHzJcAAmo https://www.powershow.com/view1/1e6905-ZDc1Z/NP-Completeness_powerpoint_ppt_presentation?varnishcache=1
 

Session 30

Approximation algorithm for the traveling salesman problem https://youtu.be/XaXsJJh-Q5Y https://bochang.me/blog/posts/tsp/
 

Our Main Teachers

Mrs.Monalisa Joshi

Asst.prof.Dept.of IT
VIEW PROFILE

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.