Title Syllabus.pdf ✅

1 School of Computer Engineering Kalinga Institute of Industrial Technology (KIIT) Deemed to be University Bhubaneswar-751024 Autumn 2022 Semester Design & Analysis of Algorithm-CS2012 (L-T-P:2-1-0) Instructor Name: Prof. Anil Kumar Swain, Email:[email protected], Mob: +91-9938853866 (WhatsApp & Call) Instructor Chamber: Faculty Chamber-1, Block-B, Campus-15 Time Table:- DAA Theory CSE-3 Class Timing ALGORITHM Lab. CSE-3 Lab. Timing Tuesday (1PM-2 PM), C-LH-002 - Wednesday (11 AM-12 N), C-LH-002 - Thursday (11 AM-12 N), C-WL-102 Thursday (12 N-2 PM), C-WL-102 DAA Theory CSE-10 Class Timing ALGORITHM Lab. CSE-10 Lab. Timing Monday (12 N-1 PM), C-LH-406 - Tuesday (11 AM-12 N), C-WL-103 - Friday (12 N-1 PM), C-LH-409 - DAA Theory ALGORITHM Lab. (10 AM-11 AM), C-LH-405 - (9 AM-10 AM), C-LH-407 - (8 AM-9 AM), C-WL-302 (9 AM-11 AM), C-WL-302 Course Objectives:- This is a core course, open to 3rd year B.Tech.(CS, IT, CSSE, CSCE, ECS) students. The course (CS-2012) objective is to help students acquire skills for the design and analysis of algorithms and data structures for various fundamental problems. In addition various techniques for analyzing an algorithm will also be covered. The emphasis will laid on designing algorithms with it’s
2 efficiency. The accompanying lab (CS2098) will reinforce the concepts taught in class using programming exercises. Grading Policy:-  Assignments/quizzes/activities: 30% (Inside-class 20%)  Mid-semester exam: 20% (syllabus upto Greedy Method i.e. 23rd class)  End-semester exam: 50%. We will have 6 short assignments/quizzes/activities over the semester, at the end of every topic. All examinations will be closed notes and closed book. There will be no make-up exams, unless in the case of emergencies. Any form of cheating will not be tolerated during the tests. Lecture-wise plan:- Topics to be covered No. of lectures (Lecture Nos) Introduction  Concepts in algorithm analysis & design motivation  Space and Time Complexity of algorithm  Growth of Functions & Asymptotic Notations.  Analysis of time complexity of Insertion Sort by step count method  Solving recurrences using Iterative, Substitution, Recurrence Tree, Master theorem 8 (1-8) Tutorials / Activity Divide and Conquer Method  Structure of Divide-and-Conquer algorithm  Binary Search, Merge Sort, Quick Sort, Randomized Quick Sort 7 (9-15) Tutorials / Activity Heap  Algorithm for heap building, heap insertion, heap deletion, heap sort.  Priority queue 3 (16-18) Tutorials / Activity Greedy Method  Overview of Greedy paradigm  Fractional knapsack problem  Activity selection problem  Huffman’s code 5 (19-23) Tutorials / Activity Dynamic Programming  Overview of Dynamic Programming paradigm  Matrix Chain Multiplication  Longest Common Sub sequence 4 (24-27)
3 Tutorials / Activity Graph Algorithms  Dis-joint Set Data Structure  Graph Traversals: BFS, DFS  Single Source Shortest Path - Dijkstra’s Algorithm  All Pair Shortest Path - Floyd Warshall Algorithm  Minimum Cost Spanning Tree - Kruskal’s Algorithm - Prim’s Algorithm 10 (28-37) Tutorials / Activity Computational Complexity  Complexity Classes:  P, NP, NP-Hard and NP-Complete 3 (38-40) Tutorials / Activity Course Outcome:- At the course end, the students will be able to-  analyse the asymptotic performance of algorithms.  understand different algorithm design techniques.  apply important algorithm design paradigms and methods of analysis.  demonstrate familiarity with complex algorithms and data structures  modify existing algorithms to apply in engineering design situations.  understand different classes of problems Practice Problem Sets:- The practice questions below will reinforce your understanding of the lecture material. These problems sets are for your practice only, need not be submitted.  Problem Set 1 (covers lectures 01--08 above)  Problem Set 2 (covers lectures 09--18 above)  Problem Set 3 (covers lectures 19--27 above)  Problem Set 4 (covers lectures 28--40 above) Text Books:-  T. H. Coreman, C. E. Leiserson, R. L. Rivest, “Introduction to Algorithms”, PHI.  E. Harwitz, S. Sahani, S. Rajsekharan, Galgotia “Fundamentals of Computer Algorithms”, Galgotia Publication. Reference Books:-  J. Kleinberg & E. Tardos, Algorithms Design”, Pearson International 1st Edition.  Michael Goodrich, Roberto Tamassia, “Algorithm Design: Foundations, Analysis & Internet Examples”, John Wiley & Sons.