IRMA UNIVERSITY Institute: Institute of Technology ‘Name of Pi yrogramme: | MTech CSE (Cyber Security) ‘Course Code: 6CS402 ‘Course Title: Data Structures and Algorithms ‘Course Type: ‘(\ Core/ Value Added Course /L) Department Elective / Institute Elective/ © University Elective/ © Open Elective / Any other) Year of Introduction: [2022-23 L | T | Practical Component Lew | pw [w [s 21-72 7-7-1135 Course Learning Outcomes (CLOs): At the end of the course, the student will be able to — 1, summarize different data structures (BL2) 2. identify appropriate data structures and methodologies for efficient (BL3) algorithm design 3. interpret the applications of various data structures (BLa) 4, design and implement efficient algorithms using various approaches (BL6) Syllabus: Total Teaching hours: 30 Unit Syllabus Teaching hours Unit-l Data Structures: Linked List, Tree, Binary Heap, Binomial Heap, 06 Fibonacci Heap, Disjoint set structures Unit Divide and Conquer: General Template, Various algorithm 06 implementation like Binary search, Merge Sort, Quick Sort etc. UnitIIl Greedy Algorithms: Making change, graphs and minimum spanning 06 tee, shortest path, Knapsack problem, Scheduling, et UnitIV Dynamic Programming: Introduction of Dynamic Programming, 06 Principle of Optimality, Examples like Single source shortest paths, Knapsack problem, Chained matrix multiplication, Longest Common Subsequence, etc. Unit-V_ Graph Algorithms: Elementary algorithms, DFS, BFS, Backtracking, 06 and Branch & Bound techniques with related examples Self-Study: The self-study contents will be declared at the commencement of semester. Around 10% of the questions will be asked from self-study contents Suggested 1. Gilles Brassard and Paul Bratley, Fundamentals of Algorithmics, Readings! PHI Publication, References: 2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest& Clifford Stein, Introduction to Algorithms, PHI Publication. 3. Ellis Horowitz, SartajSahni, Fundamentals of Computer Algorithms, University Press de Sanguthevar — Rajasekaran,4 Jean-Paul Tremblay and Paul G. Sorenson, An Introduction to Data Structures with Applications, Tata McGraw Hill 5. Robert L. Kruse, Data Structures and Program Design in C, PHI Suggested List of Sr. Experiments: No. 1 2 10 Title Hours Demonstrate applications of different data structures. 4 Implement merge sort and external merge sort with 4 ferent input types (random, ascending order, descending order) and large input sizes. Evaluate the time complexity of each algorithm and visualize the same using graphical representation, Implement a quick sort algorithm with the following 4 ways to select pivot element and give your observations for the same with different input types and sizes as given in Practical 2. a. Always pick the first element as pivot b. Always pick the last element as pivot ¢. Pick a random element as pivot Pick median as pivot Solve Make-Change problem using Greedy approach. Implement Kruskal’s algorithm to find MST 4 using greedy approach, Implement fractional knapsack problem using greedy 4 approach, Implement Assembly Line Scheduling problem using dynamic programming concepts. Implement matrix chain multiplication using dynamic programming concepts. Given two sequences X and Y, find the longest 2 common subsequence (LCS) of X and Y using dynamic programming. Implement 0-1 knapsack problem using dynamic 2 programming.