View DSA SE III Syllabus 26 27 flipbook.
Vivekanand Education Society’s Institute of Technology (Autonomous Institute Affiliated to University of Mumbai, Approved by AICTE & Recognised by Govt. of Maharashtra) NAAC accredited with ‘A’ grade COURSE NAME: Data Structures: Algorithms and Applications Teaching Scheme Course Code Course Name Teaching Hours Credits Assigned Theory Practical Tutorial Theory TW/PR Tut Total 26ITPC32 Data Structures: Algorithms and Applications (Theory) 03 --- 03 --- 03 Data Structures: Algorithms and Applications (Lab) --- 02 --- --- 01 --- 01 Examination Scheme Course Code Course Name Theory Term Work Practical and Oral TotalInternal Assessment End Sem Exam Mid-Term Test Continuous Assessment 26ITPC32 Data Structures: Algorithms and Applications (Theory) 20 20 60 --- --- 100 Data Structures: Algorithms and Applications (Lab) — — — 25 25 50 Course Prerequisite: Introduction of Java programming language. Course Objectives:
Vivekanand Education Society’s Institute of Technology (Autonomous Institute Affiliated to University of Mumbai, Approved by AICTE & Recognised by Govt. of Maharashtra) NAAC accredited with ‘A’ grade 1 The fundamental knowledge of data structures. 2 The programming knowledge which can be applied to sophisticated data structures 3 The fundamental knowledge of stacks, queues, linked lists etc. 4 The fundamental knowledge of Trees, Graphs etc. 5 The fundamental knowledge of different sorting, searching, hashing and recursion techniques 6 The real time applications for stacks, queue, linked list, trees, graphs etc. Course Outcomes: After successful completion of the course students will be able to: 1 Classify and Apply the concepts of stacks, queues and linked lists in real life problem solving. 2 Classify, apply and analyze the concepts trees in real life problem solving. 3 Illustrate and justify the concepts of graphs in real life problem solving. 4 List and examine the concepts of searching techniques in real life problem solving. 5 List and examine the concepts of sorting techniques in real life problem solving. 6 Examine and justify different operations of stacks, queues, linked list, trees and graphs to various applications Syllabus Module No. Content Hours 1. Introduction to Data Structures 12 1.1 Introduction to Data Structures: Linear and Non Linear Data Structures, Static and Dynamic Data Structures.
Vivekanand Education Society’s Institute of Technology (Autonomous Institute Affiliated to University of Mumbai, Approved by AICTE & Recognised by Govt. of Maharashtra) NAAC accredited with ‘A’ grade 1.2 Concept of Stack and Queue. Array Implementation of Stack and Queue, Circular Queue, Double Ended Queue, Priority Queue. 1.3 Concept of Linked Lists. Singly linked lists, Doubly Linked Lists and Circular Linked Lists. Insertion, deletion, update and copying operations with Singly linked lists, doubly linked lists and circular linked lists. Reversing a singly linked list. Self-learning Topics: Linked List Implementation of Stack, Linked List implementation of Queue, Circular Queue, Double Ended Queue, Priority Queue. 2. Introduction to Trees 07 2.1 Introduction to Trees: Terminology, Types of Binary Trees. Recursive Preorder, in-order and post-order traversal. Creation of binary trees from the traversal of binary trees. Binary search tree: Traversal, searching, insertion and deletion in binary search tree. 2.2 Threaded Binary Tree: Finding in-order successor and predecessor of a node in threaded tree. Insertion and deletion in threaded binary tree. 2.3 AVL Tree: Searching and traversing in AVL trees. Tree Rotations: Right Rotation, Left Rotation. Insertion and Deletion in an AVL Tree. Self Learning Topics: Implementation of AVL and Threaded Binary Tree. 3. Introduction to Graphs 05 3.1 Introduction to Graphs: Undirected Graph, Directed Graph, graph terminology, Connectivity in Undirected and Directed Graphs. Spanning tree. 3.2 Representation of graph: adjacency matrix, adjacency list, Transitive closure of a directed graph and path matrix. 3.3 Traversals: Breadth First Search, Depth First Search.
Vivekanand Education Society’s Institute of Technology (Autonomous Institute Affiliated to University of Mumbai, Approved by AICTE & Recognised by Govt. of Maharashtra) NAAC accredited with ‘A’ grade Self Learning Topics: Implementation of BFS, DFS 4. Searching 4.1 Searching: Sequential Search, Binary Search. 4.2 Hashing: Hash Functions: Truncation, Mid-square Method, Folding Method, Division Method. Collision Resolution: Open Addressing: Linear Probing, Quadratic Probing, 04 4.3 Analysis of all searching techniques Self Learning Topics: Double Hashing, Separate Chaining Bucket Hashing. 5. Sorting Techniques 045.1 Sorting Techniques: Insertion sort, Selection sort, Merge sort, Quick sort Self Learning Topics: Radix sort, Shell sort 6. Applications of Data Structures 07 6.1 Applications of Linked Lists: Addition of 2 Polynomials and Multiplication of 2 polynomials 6.2 Applications of Stacks: Reversal of a String, Checking validity of an expression containing nested parentheses, Function calls, Polish Notation: Introduction to infix, prefix and postfix expressions and their evaluation and conversions. 6.3 Application of Queues: Scheduling, Round Robin Scheduling Applications of Trees: Huffman Tree and Heap Sort. 6.4 Applications of Trees: Huffman Tree and Heap Sort. 6.5 Applications of Graphs: Dijkstra’s Algorithm, Minimum Spanning
Vivekanand Education Society’s Institute of Technology (Autonomous Institute Affiliated to University of Mumbai, Approved by AICTE & Recognised by Govt. of Maharashtra) NAAC accredited with ‘A’ grade Tree: Prim’s Algorithm, Kruskal’s Algorithm. Self Learning Topics: Practical Applications and Case Studies: Real-world applications of data structures and algorithms Case studies highlighting the importance of efficient algorithms in software development and systems engineering TOTAL 39 Textbooks: 1 Goodrich, M. T., Tamassia, R., & Goldwasser, M. H. (2014). Data Structures and Algorithms in Java (6th ed.). Wiley. 2 Malik, D. S. (2018). Data structures using Java (2nd ed.). Oxford University Press. 3 Weiss, M. A. (2013). Data structures and algorithm analysis in Java (3rd ed.). Pearson. Reference Books: 1 Miller, B. N., & Ranum, D. L. (2014). Problem solving with algorithms and data structures using Java. Franklin, Beedle & Associates. Retrieved from Runestone Academy 2 Lafore, R. (2002). Data structures and algorithms in Java (2nd ed.). Sams Publishing Access to software and virtual labs: 1 https://visualgo.net/en/ 2 https://ds1-iiith.vlabs.ac.in/List%20of%20experiments.html 3 https://www.onlinegdb.com/ 4 https://dev.to/prnvbirajdar/list-of-visual-tools-to-help-with-data-structures-and-algorithms-4nb 2?comments_sort=latest Industry articles and case studies : 1 "Data Structures for Efficient Memory Management in Operating Systems" by ACM Digital Library URL: https://dl.acm.org/doi/10.1145/3373376 2 Case Study: "Sorting Algorithms for Big Data Applications" by IEEE Xplore URL: https://ieeexplore.ieee.org/document/8259339
Vivekanand Education Society’s Institute of Technology (Autonomous Institute Affiliated to University of Mumbai, Approved by AICTE & Recognised by Govt. of Maharashtra) NAAC accredited with ‘A’ grade 3 Case Study: "Search Algorithms in E-commerce Platforms" by SpringerLink URL: https://link.springer.com/chapter/10.1007/978-3-030-32475-9_7 Any other (Access to AI tools / Data driven insights (if applicable) or any other): 1 AI-powered Coding Assistants: Tabnine: https://www.tabnine.com/ 2 GitHub Copilot (Limited Access): https://github.com/features/copilot 3 https://www.hackerrank.com/domains/data-structures 4 https://leetcode.com/explore/interview/card/leetcodes-interview-crash-course-data-structures- and-algorithms/703/arraystrings/ 5 https://cs50.harvard.edu/x/2023/weeks/5/ Internal Assessment: 1) Assessment consists of one Mid Term Test of 20 marks and Continuous Assessment of 20 marks. 2) Mid Term test is to be conducted when approx. 50% syllabus is completed. 3) Duration of the midterm test shall be one hour. Continuous Assessment: Continuous Assessment is of 20 marks. The rubrics for assessment will be considered on approval by the subject teachers. The rubrics can be any 2 or max 4 of the following: Sr. No Rubrics Marks 1 Certificate course for 4 weeks or more: NPTEL/ Coursera/ Udemy/any MOOC 10 marks 2 Wins in the event/competition/hackathon 10 marks 3 Content beyond syllabus presentation 10 marks 4 Creating Proof of concept 10 marks 5 Mini Project / Extra Experiments/ Virtual Lab 10 marks 6 GATE Based Assignment test/Tutorials etc 10 marks 7 Participation in event/workshop/talk / competition followed by small report and certificate of participation relevant to the subject (in other institutes) 05 marks 8. Multiple Choice Questions (Quiz) 05 marks
Vivekanand Education Society’s Institute of Technology (Autonomous Institute Affiliated to University of Mumbai, Approved by AICTE & Recognised by Govt. of Maharashtra) NAAC accredited with ‘A’ grade 9. Peer Review and participation the marks can be left blank (with discretion of faculty) 05 Marks 10 CA is expected to cover Self learning modules under CA End Semester Theory Examination: (Question shall not included questions from Self learning topics) 1 Question paper will be of 60 marks 2 Question paper will have a total of five questions 3 All questions have equal weightage and carry 20 marks each 4 Any three questions out of five need to be solved. Data Structures: Algorithms and Applications LAB Suggested Experiments: Students are required to complete at least 10 experiments. Tools/Libraries: Sr. No. Name of the Experiment CO 1 Implementation of Stack Data Structure using Array: A web browser maintains a history of recently visited pages. Every time a user visits a new page, the URL is stored. When the user clicks the Back button, the most recently visited page is removed and the browser navigates to the previous page. Develop a program using an array-based stack to simulate browser history with Push, Pop, Peek, and Display operations. CO1 2 Conversion of Infix Expression to Postfix Expression Using Stack: A scientific calculator accepts mathematical expressions entered in infix notation (e.g., A+B*C). Before evaluation, the expression must be converted into postfix notation to simplify computation. Develop a program to convert an infix expression into its equivalent postfix expression using a stack. CO1 3 Implementation of Linear Queue Data Structure using Array: A railway ticket reservation counter serves customers in the order they arrive. New customers join the end of the line, while the customer at the front is served first. Develop a program using an array-based linear queue to perform Enqueue, Dequeue, Peek, and Display operations. CO1 4 Implementation of Circular Queue Data Structure using Array: A printer receives print requests continuously. After reaching the end of the queue, new print jobs should
Vivekanand Education Society’s Institute of Technology (Autonomous Institute Affiliated to University of Mumbai, Approved by AICTE & Recognised by Govt. of Maharashtra) NAAC accredited with ‘A’ grade utilize the vacant positions created by completed jobs. Implement a circular queue using an array to efficiently manage print requests. CO1 5 Implementation of Singly Linked List: A college maintains a dynamic list of student registrations. Students may enroll, withdraw, or update their records at any time. Since the number of students changes frequently, implement a singly linked list supporting insertion, deletion, searching, updating, and display operations. CO1 6 Linked List Implementation of Stack/Queue in Real-Life Application: A hospital manages emergency procedures and patient records where the number of patients is unpredictable. Implement either a stack or a queue using a linked list to efficiently manage patient records without fixed memory limitations. CO6 7 Implementation of Circular Singly Linked List: Players sit in a circle to play a game where turns continue cyclically until the game ends. After the last player completes a turn, the first player gets the next turn. Implement a circular singly linked list to manage player turns with insertion, deletion, and traversal operations. CO6 8 Implementation of Circular Doubly Linked List: A music player supports continuous playback where users can move to both the next and previous songs. After the last song, playback continues from the first song. Implement a circular doubly linked list to manage the playlist efficiently. CO6 9 Implementation of Binary Search Tree: A university stores student roll numbers in sorted order to enable quick searching, insertion, and deletion. Implement a Binary Search Tree (BST) to maintain student records and perform insertion, search, deletion, and traversal operations. CO2 10 Implementation of AVL Tree: A banking system stores customer account numbers in a searchable structure. Frequent insertions and deletions should not degrade search performance. Implement an AVL tree that automatically balances itself after every insertion and deletion to ensure efficient searching. CO2 11 Implementation of BFS and DFS on a Directed Graph using an Adjacency Matrix: A navigation system represents cities as vertices and one-way roads as directed edges. Implement Breadth First Search (BFS) and Depth First Search (DFS) using an adjacency matrix to explore all cities reachable from a given starting city. CO3 12 Implementation of Binary Search in a Real-Life Application: A digital library stores book IDs in sorted order. When a user searches for a book using its ID, the system should CO4
Vivekanand Education Society’s Institute of Technology (Autonomous Institute Affiliated to University of Mumbai, Approved by AICTE & Recognised by Govt. of Maharashtra) NAAC accredited with ‘A’ grade quickly determine whether the book exists. Implement Binary Search to efficiently locate the required book in the sorted list. 13 Implementation of Menu-Driven Selection Sort and Insertion Sort: A teacher wants to arrange student marks in ascending order for result analysis. Develop a menu-driven program that allows the user to choose either Selection Sort or Insertion Sort to sort the marks and display the sorted list. CO5 14 Implementation of Menu-Driven Merge Sort and Quick Sort: An e-commerce company needs to sort thousands of product prices efficiently for display on its website. Develop a menu-driven program that allows the user to choose either Merge Sort or Quick Sort to sort the product prices in ascending order and compare the sorted output. CO5 Note: Suggested List of Experiments is indicative. However, flexibility lies with individual course instructors to design and introduce new, innovative and challenging experiments, (limited to maximum 30% variation to the suggested list) from within the curriculum, so that the fundamentals and applications can be explored to give greater clarity to the students and they can be motivated to think differently. Term Work: 1 Term work should consist of 10 experiments and 2 assignments 2 The final certification and acceptance of term work ensures satisfactory performance of laboratory work and minimum passing marks in term work. 3 Total 25 Marks (Experiments: 15 - Experiment marks (10 Experiments + 5 Mini Project), Assignments: (based on Self Learning Module) 5-marks, Attendance- 5 Marks) Practical/Oral Exam: Evaluation Exam: Practical & Oral Exam will be conducted on the entire Syllabus.