FUNDAMENTALS OF ALGORITHM DESIGN AND ANALYSIS

Teacher

Mrs.Monalisa Joshi

Category

Core Courses

Course Attendees

Still no participant

Course Reviews

Still no reviews

Course Name : FUNDAMENTALS OF ALGORITHM DESIGN AND ANALYSIS

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

Session 1

Growth of functions

https://youtu.be/AdmmEEWyZlg/

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

https://www.youtube.com/watch?v=8ctZ98WkGuE

 

Session 17

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

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

https://www.youtube.com/watch?v=hAejNMRN78c

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

https://youtu.be/a08SHTk45vc

Session 26

Fast Fourier Transform

https://www.slideshare.net/op205/fast-fourier-transform-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

 

  [    

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.