DATA STRUCTURES III Semester: AE / ME / CE / CSE / CSE (AI & ML) / CSE (DS) / CSE (CS) / IT / ECE / EEE Course Code Category Hours / Week Credits Maximum Marks L T P C CIA SEE Total ACSD08 Core 3 - - 3 40 60 100 Contact Classes: 48 Tutorial Classes: Nil Practical Classes: Nil Total Classes: 48 Prerequisite: Essentials of Problem Solving I. COURSE OVERVIEW: The course covers some of the general-purpose data structures and algorithms, and software development. Topics covered include managing complexity, analysis, static data structures, dynamic data structures and hashing mechanisms. The main objective of the course is to teach the students how to select and design data structures and algorithms that are appropriate for problems that they might encounter in real life. This course reaches to student by power point presentations, lecture notes, and lab which involve the problem solving in mathematical and engineering areas.
II. COURSES OBJECTIVES:
The students will try to learn I. The skills needed to understand and analyze performance trade-offs of different algorithms / implementations and asymptotic analysis of their running time and memory usage. II. The basic abstract data types (ADT) and associated algorithms: stacks, queues, lists, tree, graphs, hashing and sorting, selection and searching. III. The fundamentals of how to store, retrieve, and process data efficiently. IV. The implementing these data structures and algorithms in Python. V. The essential for future programming and software engineering courses.
III. COURSE OUTCOMES:
At the end of the course students should be able to: CO 1 Interpret the complexity of the algorithm using the asymptotic notations. CO 2 Select the appropriate searching and sorting technique for a given problem CO 3 Construct programs on performing operations on linear and nonlinear data structuresfor organization of a data CO 4 Make use of linear data structures and nonlinear data structures solving real-time applications. CO 5 Describe hashing techniques and collision resolution methods for accessing data with respect to performance CO 6 Compare various types of data structures; in terms of implementation, operations and performance.
IV. COURSE CONTENT:
MODULE – I: INTRODUCTION TO DATA STRUCTURES, SEARCHING AND SORTING (09) Basic concepts: Introduction to data structures, classification of data structures, operations on data structures, Algorithm Specification, Recursive algorithms, Data Abstraction, Performance analysis- time complexity and space complexity, Introduction to Linear and Non Linear data structures, Searching techniques: Linear and Binary search, Uniform Binary Search, Interpolation Search, Fibonacci Search; Sorting techniques: Bubble, Selection, Insertion, and Quick, Merge, Radix and Shell Sort and comparison of sorting algorithms.
MODULE – II: LINEAR DATA STRUCTURES (09)
Stacks: Stack ADT, definition and operations, Implementations of stacks using array, applications of stacks, Arithmetic expression conversion and evaluation; Queues: Primitive operations; Implementation of queues using Arrays, applications of linear queue, circular queue and double ended queue (deque).
MODULE – III: LINKED LISTS (09)
Linked lists: Introduction, singly linked list, representation of a linked list in memory, operations on a single linked list; Applications of linked lists: Polynomial representation and sparse matrix manipulation. Types of linked lists: Circular linked lists, doubly linked lists; Linked list representation and operations of Stack, linked list representation and operations of queue.
MODULE – IV: NON LINEAR DATA STRUCTURES (09)
Trees: Basic concept, binary tree, binary tree representation, array and linked representations, binary tree traversal, binary tree variants, threaded binary trees, application of trees, Graphs: Basic concept, graph terminology, Graph Representations - Adjacency matrix, Adjacency lists, graph implementation, Graph traversals – BFS, DFS, Application of graphs, Minimum spanning trees – Prims and Kruskal algorithms.
MODULE – V: BINARY TREES AND HASHING (09)
Binary search trees: Binary search trees, properties and operations; Balanced search trees: AVL trees; Introduction to M- Way search trees, B trees; Hashing and collision: Introduction, hash tables, hash functions, collisions, applications of hashing.
V. TEXT BOOKS: 1. Rance D. Necaise, “Data Structures and Algorithms using Python”, Wiley Student Edition. 2. Benjamin Baka, David Julian, “Python Data Structures and Algorithms”, Packt Publishers, 2017.
VI. REFERENCE BOOKS:
1. S. Lipschutz, “Data Structures”, Tata McGraw Hill Education, 1st Edition, 2008. 2. D. Samanta, “Classic Data Structures”, PHI Learning, 2nd Edition, 2004.
1. Course template 2. Tutorial question bank 3. Definition and terminology 4. Tech-talk topics 5. Assignments 6. Model question paper - I 7. Model question paper - II 8. Lecture notes 9. Early learning readiness videos (ELRV) 10. Power point presentations
