SHARDA UNIVERSITY Syllabus: CSE350, Design and Analysis of Algorithm School: SET Batch :2019-2023 Program: B.Tech | Current Academic Year: 2019-20 Branch: CSE ‘Semester: V 1_| Course Code [ CSE 350 | Course Name: Design and Analysis of Algorithms 2_| Course Title | Design and Analysis of Algorithms 3_| Credits 4 4 | Contact 340 Hours (L-T-P) Course UG Status 3 | Course Objective of this course is to Objective 1. Reinforce basic design concepts (e.g., pseudocode, specifications, top-down design) 2. Knowledge of algorithm design strategies 3. Familiarity with an assortment of important algorithms. 4,_ Enable students to analyze time and space complexity © | Course ‘Students will be able to’ Outcomes | CO4: Analyze the asymptotic performance of algorithms C02: Write rigorous correctness proofs for algorithms. CO3: Demonstrate a familiarity with major algorithms and data structures CO4: Apply important algorithmic design paradigms and methods of analysis 7 | Course This course introduces concepts related to the design and analysis of Description | algorithms. Specifically, it discusses recurrence relations, and illustrates their role in asymptotic and probabilistic analysis of algorithms. It covers in detail greedy strategies divide and conquer techniques, dynamic programming and max flow - min cut theory for designing algorithms, and illustrates them using a number of well-known problems and applications. 8__| Outline syllabus ‘CO Mapping Unit 1 Introduction A Introduction : Algorithms, Analyzing algorithms, | CO2, CO3 Complexity of algorithms, Growth of functions, Performance measurements B ‘Asymptotic Notations and their properties — | CO1, CO2, CO3 Mathematical analysis for Recursive and Non- recursive algorithms, Recurrences relations, Master Method c Divide-and-conquer: Analysis and Structure of | COl, CO2, CO4 divide-and-conquer algorithms, _Divide-and- conquer examples-Quick sort, Merge sort, Sorting in Linear Time, Heap Sort Unit 2 ‘Advanced Data StructuresSHA) UNIVE A Red-Black Trees - Definition, Applications, COT, CO2, CO3, Insertion and deletion of elements inRB-Tree | CO4 B B-Trees - Definitions, Applications, Insertion and | CO1, CO2, CO4 Deletion in 8-Trees c Data Structure for Disjoint Sets — Definition, COI, CO2, CO3, Binomial Heaps, Fibonacci Heaps. co4 Unit 3 Dynamic Programming A Overview, Difference between dynamic CO1,CO2,CO3. programming and divide and conquer, Allpair | CO4 shortest path problems: Floyd-Warshall Algorithm B ‘Applications and analysis: Matrix Chain COI, CO2, CO3, Multiplication, 0/1 Knapsack Problem cos c Applications and analysis: Longest Common sub- sequence, Optimal Binary Search tree Unit 4 Greedy Method ‘CO1,CO2,CO3 A (Overview of the Greedy paradigm, Analysis and | CO1,CO2,CO3 example: task scheduling, B Fractional Knapsack problem, Single source ‘CO1,CO2,CO3 shortest paths problem: Dijkastra’s Algorithm, Bellman-ford Algorithm, c ‘Overview and analysis of Backtracking & Branch and Bound: N-Queens problem and Sum of subsets Unit 5 Selected Topics COT,CO2,CO3, A Introduction to NP Complete and NP Hard ‘CO1,CO2,CO3, Problems, Examples, Amortized Analysis B ‘Approximation Algorithms Travelling Sales | CO1,CO2,CO3 Person Problem and Vertex Cover Problem, Randomized Algorithms, Randomized Quick Sort Algorithm c String Matching Algorithms — Naive String Matching Algorithm, Rabin Karp Algorithm, Mode of Theory examination Weightage [CA MTE [ETE Distribution [30% [20% 50% Text bookis* | 3. Cormen et al, “Introduction of Computer Algorithms’, Prentice Hall India Other 3. Sahni et al, “Fundamentals of Computer References Algorithms”, Galgotia Publications. 4. Hopcroft A, The Design And Analysis Computer Algorithms, Addison Wesley DA RSITYSHARDA UNIVERSITY CO and PO Mapping 5, Course Outcome Program Outcomes (PO) No. & Program Specific Outcomes (PSO) T.__ | €Oi:Analyze the asymptotic performance of algorithms PO1,PO2,PO3,PO4,PSO1 (CO2: Write rigorous correctness proofs for algorithms POI, PO3, PO4, PSO2 3, | €03: Demonstrate a familiarity with major algorithms and | PO1,P02,PO3,PO4 data structures 4, | CO4:Apply important algorithmic design paradigms and | POS, POIO,POII, PSOS methods of analysis PO and PSO mapping with level of strength for Course Name Design and Analysis of Algorithm Course Code CSE 350) Tor] POI] PO] POs] PO*] POS | PO] POT] PO] POS [OID] PO] POID| PEON | PSOE | PSO] PSOA | PROS 2 ‘ a a a TPs Ps fe}a >? >? 7272 7 1-Slight (Low) ‘2Moderate (Medium) __3-Substantial (High)