# FUNDAMENTALS OF ALGORITHM DESIGN AND ANALYSIS

Teacher

Category

### Course Attendees

Still no participant

Still no reviews

# Code(Credit) : CUTM1899(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

• Introduction, algorithm, pseudo code for expressing algorithms, performance analysis, space
complexity, time complexity, asymptotic notation, big oh notation, omega notation, theta notation,
and little oh notation, probabilistic analysis, amortized analysis.
• Disjoint sets, disjoint set operations, union and find algorithms, spanning trees, connected components, biconnected components Divide and conquer: general method, applications, binary search, quick sort, merge sort,  matrix multiplication.Greedy method: general method, applications, job sequencing with deadlines, 0/1 knapsack
problem, minimum cost spanning trees, single source shortest path problem.Dynamic programming: general method, applications, matrix chain multiplication, optimal binary
search trees, 0/1 knapsack problem, all pairs shortest path problem, travelling sales person
problem, reliability design.Backtracking: general method, applications, n-queen problem, sum of subsets problem, graph
coloring, Hamiltonian cycles.Branch and Bound: general method, applications, travelling sales person problem, 0/1 knapsack
problem. LC branch and bound solution, FIFO branch and bound solution.NP-hard and NP-complete problems: basic concepts, non deterministic algorithms, NP-hard and
NP-complete classes.

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

## Session 1

Growth of functions

https://slideplayer.com/slide/4862946/

https://www.slideserve.com/bonnie/the-growth-of-functions

## Session 2

Asymptotic notations

https://youtu.be/44Lezs_GNc0

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

## 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/mJDNA6Wo0BE[/

## Session 6

Worst case analysis of merge sort

https://youtu.be/Ecvg5rxVZ7A

https://www.slideshare.net/vidushipathak52/merge-sort-14333866

## Session 7

quick sort algorithm

https://youtu.be/RNpBjijkjYY

https://www.slideshare.net/priyankanaidu6/quick-sort-2017249

## Session 8

Heap Sort

http://heap sort algorithms

https://www.slideshare.net/mohammedarif89/heap-sort-18479976

https://www.slideshare.net/priyankanaidu6/quick-sort-2017249

## Session 9

Priority queue, Data structure for disjoint sets (Disjoint set operations

https://youtu.be/OxhYCLWMdHs

https://www.powershow.com/view1/d4215-ZDc1Z/Priority_Queues_Heaps_powerpoint_ppt_presentation?varnishcache=1

## 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://www.slideshare.net/RespaPeter/matrix-chain-multiplication

## Session 13

longest common subsequence

https://youtu.be/NnD96abizww

https://www.powershow.com/view1/270f73-ZDc1Z/Longest_Common_Subsequence_LCS_powerpoint_ppt_presentation?varnishcache=1

## Session 14

Greedy verses dynamic programming

https://youtu.be/5dRGRueKU3M

https://www.javatpoint.com/dynamic-programming-vs-greedy-method

## Session 15

Concept of backtracking, branch & bound design techniques

https://pediaa.com/what-is-the-difference-between-backtracking-and-branch-and-bound/

https://youtu.be/3RBNPc0_Q6g

## Session 16

Graph algorithms: Minimal spanning tree (Kruskal's  algorithms)

https://www.xpowerpoint.com/kruskals-algorithm-for-finding-a-minimum-spanning-tree-115-90-52--PPT.html

## Session 17

Graph algorithms: Minimal spanning tree (Prim’s algorithms)

https://www.tutorialspoint.com/data_structures_algorithms/prims_spanning_tree_algorithm.htm

## Session 18

Huffman codes

https://www.gatevidyalay.com/tag/huffman-coding-example-ppt/

https://youtu.be/co4_ahEDCho

## Session 20

Fractional knapsac problem

https://www.powershow.com/viewht/15fd3e-ZDc1Z/Knapsack_Problem_powerpoint_ppt_presentation

https://youtu.be/yV1d-b_NeK8

## Session 21

Bellman-Ford algorithm

https://www.slideshare.net/tanu696/shortest-pathsbf

https://youtu.be/FtN3BYH2Zes

## Session 23

Dijkstra’s algorithm

https://www.slideshare.net/ami_01/dijkstras-algorithm-7716656

https://youtu.be/DAj7mtiAiQM

## Session 24

Floyd’s algorithm.

https://www.slideshare.net/SaidurRahmanKohinoor/floyd-warshall-algorithm-56194284

https://youtu.be/oNI0rf2P9gE

## Session 25

Ford-Fulkerson method

https://www.cs.rit.edu/~lr/courses/alg/student/1/Ford-Fulkerson%20Method.pdf

https://youtu.be/a08SHTk45vc

## Session 26

Fast Fourier Transform

https://www.slideshare.net/op205/fast-fourier-transform-presentation

https://youtu.be/BXghmsH-mKY

## Session 27

Rabin-Karp string matching algorithm

https://www.powershow.com/viewfl/407eba-OTQyM/String_Matching_Using_the_Rabin-Karp_Algorithm_powerpoint_ppt_presentation

https://youtu.be/3mWbnyQl1U0

## Session 28

Polynomial time solvability, Verification and Reducibility

https://www.powershow.com/view1/1e6905-ZDc1Z/NP-Completeness_powerpoint_ppt_presentation?varnishcache=1

https://youtu.be/YlEqelSE_ic

## Session 29

NP complete problems (without proof)

https://www.powershow.com/view1/1e6905-ZDc1Z/NP-Completeness_powerpoint_ppt_presentation?varnishcache=1

https://youtu.be/DumOqL85Ryc

## Session 30

Approximation algorithm for the traveling salesman problem.

https://bochang.me/blog/posts/tsp/

https://youtu.be/u5rqrQqGk3E

[

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