Course Title: Data Structure and Algorithms (3 Ct.) Course Code: CACS201 Year/Semester: [VII Class Load: Hts. / Week (Theory: 3 Hrs, Practical: 3 Hrs.) Course Description This course includes fundamental concept of data strctures such as sack, queue is, linked list, trees and graph; application of these chata siuctures along with several algorithms Course Objectives The general objective ofthis course isto provide fundamental concept of data structures, different algorithms and their ‘implementation Course Contents Specific Objectives Content Hour ¢ Define Data Structure and Algoriths Unit 1: Introduction to data Structure 1Hts + Classify and explain the various Data Structures, + Explain Data Structure operations. Explain an Abstract Data Type. + List out the Importance of data structures + Discuss on time and space complexity of algorithm. + Introduce asymptotic notations. + Define Stack Data Structure. Unit 2: The Stack Shs Explain stick an ADT ‘+ Write an algorithms for Stack Operations. «+ List out the applications of Stack «+ Evaluate Inf, Postix and Prefix expressions Definition, Abstiact Data Type, Importance of Data Strcture Introduction, Stack as an ADT, POP and PUSH Operations, Stack Aplications, Evaluation of Init, Postia, and Prefix Expressions, Conversion + Lnplement an algorithms to convert infix expression to postfix offen and prefix expressions + Define Queue. Explain Queue as an Abstract Data Type. Unit 3: Queve Shs. + Describe the primitive operations in Queue.+ Classify the Queue. + Tnplement the Linear Queue + Tnplement the Circular Queue + List ou applications of differen types of Queue ++ Explain the Priority Queue with its operations and Applications. Introduction, Queue as at ADT, Primitive operations in Queue, Linear and Circular Queue andther applications, Enqueye and Dequeue, Priority Queue. «Define List with its applications. Unit 4: List 2H ‘ pia be aa Dyan Lt Sucre Untroducton, Static and Dynamic List Structure, ' tm emer uae 1 ty i Array Implementation of Lists, Queues asa List + Define Linked List Explain Linked Listas an ADT Unit 5: Linked List SHrs + Explain the primitive operations of Linked List. A Ch iene if oe Lia Lntroduction, Linked Listas an ADT, Dynamic «Invert an item in linked ist at star, end and spectic neaton of imposter Devan No ltkedlist. and from a List, Insertion and Deletion after and + Deletean tem from linked list at stat, end and specific bei Nd, Liked Stes Que, ly locaton of linked lst. Linked Lists and Its Advantages + Implement Singly, Circular, Doubly and Circular Doubly, Linked Lis. © Implement Linked Stack. + Inplement Linked Queue + List out the applications and advantages of Linked Lis + Define Recursion, Explain he Principle of Recursion Unit 6: Recursion 4tts. : irae liebe ow Introduction, Principle of Recursion, Recursion vs + Use Recursion to solve the different problems (calculate ane mee en fool, reversingan tee, checking prime number, TOH, | "SPP atm of Reurson, Search Tree Fibonacci Series ete). + Lnplement recursion to find form search tee. + Define tree and tree terminologies, Unit 7: Trees SH, + Explain the basic operations in binary te,«+ Insert and delete node in binary tee «+ Traverse binary tree using pre-rder, post-order, and in-order traversal methods + Explain the applications of Binary Tree. + Construct AVL tree using given set of dita, Tnplement Huffman Algorithm, + Implement Game Tree with its applications. + Constuct B-Te. [ntroduction, Basic Operatiots in Binary Tree, Tree Search and Insertion/Detetion, Binary Tree Traversals (pre-order, post-onder and i-order), Tree Het, Level and Depth, Balanced Tree AVL Balanced Trees, Balancing Algorithm, The Huliman Algorithm, Game Tree, B-Tree + Define Sorting Differentiate beween Internal & External | Unit 8 Sorting ols Surting ve «Wt program to inplenen karan baer — ue lnerton Sr, Sletion Sor, Buble Sar, Quik Sort, Merge 2%¢Seletion So, Exchange Sor, Buble and Sur, Heap So. (Quick Sort, Merge and Radix Son, Shell Sort, + Demons th song using Exchange Sr, Rid Sort, Binary Sor, Heap Sort as Prinity Que, Stell Sr, and Binary Sort, Efficiency of Sorting, Big 0) Notation + Compare Quick sort and Heap Sort © Construct a Heap using given set of data + Explain Heap as a Prionty Queve. + Analyze Efficiency (best, average & worst case) of each Sarting Algorithms. + Inoduce Searching. Explan dictionary as ADT Unit 9: Searching Sits + List cut applications of Searching + Implement Sequential search, Analyze an efliciency of sequential search. + Inplement Binary search. Analyze an efficiency of binary search with compare to sequential search. ‘+ Tnplement binary search tree as searching mechanism, + Introduce Hashing, Explain and implement Hash Functions and Hash Table, + Discuss efliciency of Rehashing mehod. + Identify and implement different types of collision resolution techniques. Lntroduetion to Search Technique, essential of search, Sequential Search, Binary Search, Tree Search, General Search Tree, Hashing: Hash functions and Hash tables, Collision resolution techniques, ficiency comparison of different search technique4 Introduce graph, Explain graph as an ADT Unit 10: Graph Sis + Explain the Applications of graph theory. A El the ae ite vate ve ay ote oh Intec (Graph as an ADT, Transitive — Closure, Warshall’s Algorithm, Types of Graph, + Tnplement the Warshall' algorthan for both directed and 5 “ ' ' unde raph (Graph Traversal and Spanning Forests, Kruskal «+ Explain graph traversal methods with their efficiency sada obi Alpi Shatet Pah + Inplnen tatestp ali soe gun pobens, lit, Greely Alon, Dike’ + Lnplement Dijkstr’s algorithm to solve single source shartest Alwitim path graph problem «+ Explain the minimum spanning tree and forest Use Kruskal’s Algorithm tosolve MST problem, + Use Pim Algorithm to solve MST problems. + Tnplement the Round Robia Algorithm to solve graph problem, «+ Explain the greedy algorithm to traverse graph with its, efficiency ++ Explain the behavior of Determuniste and non-deterministic | Unit 11: Algorithms SH algorithms with their applications, performance and examples + Demonstrate the Divide and Conquer algoritam with ts Defense aa Noi Aleit, pafomane Divide and Conquer Algorithm, Series and Parallel «Diente vee Seis and Pallet Alsons wi ti | Allan, Heursticand ApproxmaAlzorthns applications, ‘+ Demonstrate the Heuristic and Approximate algorithm with their performance, Laboratory Works Laboratory Topics Laboratory Activities There shall be 10 lab exerises based cn Cor ava |. Implementations of different operations related to Stack. 1. Writea program to show the Stack operations 2. Whitea program to implement the linear queue operations.‘Implementation of different operations related to linear and circular queve. Solution of TOH and Fibonace: Series using Recursion. ‘Implementations of different operations related to linked list: Sinly and doubly Linked List Implementation of Trees: AVL tres, Balancing AVL. [Implementation of merge sort ‘Implementation of different searching technique sequential, Tree and Binary. ‘Implementation of Graphs: Grgph taversal ‘Implementation of Hashing 10. Ieplementation of Heap ‘Whitea program to implement circular queue. ‘Whitea program to calcula factorial number using recursion ‘Whitea program to check prime number using recursion. ‘Writea program to reverse integer number using recursion ‘Writea program to print Fibonacci series upto given ‘umber using recursion ‘Whitea program to solve TOH problem using recursion. ‘Whitea program to count the nodes in Linked List, 10, Writea program to insert and delete an item atthe beginning of Singly Linked list 11, Writea program to insert and delete an item atthe end of Singly Linked lst. 12. Writea program to insert and delete anitemat specified location of Singly Linked lst. 13. Writea program to insert and delete an item atthe beginning of Doubly Linked list 4, Writea program to insert and delete an item atthe end of Doubly Linked lst. 15. Writea program to inset and delete an item at specified location of Doubly Linked list. 16 Insert and delete node form circular linked list 17, Writea program to create binary seatch tree using gwen set fds. 18, Writea program to implement binary tee traversal methods (pre-order, in-order and post-order) 19. Writea program to construct AVL tee using given set of dita 20, Whtea program to son an aray using Bubble Sot 21. Writea program to sort an array using Insertion Sort 2. Whitea program to sort an aray using Seletion Sor. 33. Whitea program to sort an aray using Merge Sort,‘44, Writea program to sort an array using Quick Sor. 38, Wnitea program to construct a heap using given set of ita 26, Writea program to sort an array using Heap Sort 27. Writea program to search an item from an array using sequential search. 28, Whitea program to search an item ffoman array using binary search 29. Whtea program to represent the graph. 3, Wntea program to traverse (BFS, DFS) ina graph. 31. Wotea program to implement Dijstra’s Algorithm for finding single source shortest path problem 32. Writea program to implement open addressing hashing approch. ‘Note: Teacher's can add extra practical activities to make clearer the content and to fulfil the requirement of CUS, Teaching Methods The general teaching methods includes cass lectures, group discussions, case stues, guest lectures research work, projet worl, ansignments{ theoretical and practical), and exams, deperding upon te nature ofthe topics. The teaching faculty wil determine the choice of teaching pedagogy as per the need ofthe topics, Evaluation Evaluation Scheme Interal Assessment External Assessment Toul Theory Practical Theory Practical ‘tH el 20G3Hrs) 6)(3 Hrs.)Internal/Practical Assessment Format [FM =40) ‘intemal Assessment Format [FM = 20] — Subject Teacher 7] foe Assignment | Attendance ) Total i 5 5 j pl] Practical Assessment Format [FM = 20] - Extemal Examiner will be assigned by Dean Office, FOHSS. Practical Viva_|__LabReorts Total 10 5 5 2 ‘Note: Assignment may be subject spectic case study, seminar paper preparation, report waiting, project work, research work, presentation, problem solving et, Final Examination Questions Format [FM = 60, PM = 24, Time =3 Hrs.] SN uestion Type Number of Questions Given | Marks per Question | Total Marks ! Objective Type use ‘Choice Questions) 0 ! ixlsi0 : Short Questions (ents st questions) ] 5 fsa) Long: cust ti ‘0 questions) ; W inte © Student must pass ‘nteral Assessment; ‘Practical Assessment and Final Examinaiton' separately. + Student must atend each and every activity ofIoermal Assessment otherwise he/she will be declared as Not Qualified for fina! Examunation. Text Books 1. Y.Langsam, MJ. Augensiein and A.M, Tanenbaum, "Data Structures using Cand C+*", PHI Reference Books1 G.W. Rowe, "introduction to Dita Structures and Algorithms with C and C+", PHL 2 Robert Lafore, ‘Data Structures and Algorithms in Java", Sams Publishing 3. G.S. Baluja, "Data Structures through C”, Dhanpat Rai & Co. Internal Assessment marks Submission format Campus Name: Subject Name: Data Structure and Algorithms Subject Code: CACS201 TU Registration Symbol | Mid-Term | Pre~ Final | Assignment | Attendance | Total SN Wo Name No, i il i i 0) Remarks ‘Name of Subject Teacher: ‘Name of Director/HoD/Coordinator: Signature: Signature: Date: Daie: