# Design and Analysis of Algorithm

Teacher

Category

### Course Attendees

Still no participant

Still no reviews

# 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

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 1

Growth of functions

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 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/

### 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.