210244: DATA STRUCTURES AND ALGORITHMS
Teaching SchemeExamination Scheme Lectures: 4 Hrs./week Theory: 100 Marks
Prerequisite: Computer Fundamentals and Programming (Subject Code: 110013)
To develop the ability to synthesize and analyze algorithms
To study the representation, implementation and applications of data structures
UNIT I: Fundamental Concepts
Introduction to Data Structures: Data, Data objects, data types, Abstract Data types (ADT) and Data Structure, Concept of Primitive and non primitive, Linear and Non-linear, static and dynamic, persistent and ephemeral data structures,
Introduction to Algorithms: Definition and Characteristics of an algorithm, Algorithm Design Tools: Flowcharts and pseudo code, notations: Algorithm Header, Purpose, conditions and return, statements, statement numbers, variables, comments, statement constructs: sequence, selection, loops and sub-algorithms.
Coding: Procedural, Modular, structured and Object-oriented. Good programming practices.
Algorithm Analysis: Time complexity: Real time and Frequency count, Big 'O', ‘Ώ” and Θ notations, Space complexity: Compile-time and run-time, best, average and worst cases
UNIT II: Linear Data Structures using Sequential Organization
Concept of Sequential Organization, arrays as ADT, Storage representation of array (row major and column major), Representation of Polynomials using arrays, Representation of sparse matrix, addition, transpose and fast transpose of sparse matrix, Time and space complexity analysis for simple and fast transpose for sparse matrix.
UNIT III: Stacks
Fundamentals, stack as ADT, Representation and Implementation of stack using arrays, Applications of stack: Expression evaluation and conversion, reversing a string, Parsing: Well-form parenthesis, Decimal to Binary Conversion, Eight queens Problem, representation of multiple stacks using single array
Recursion: Definition, Writing recursive functions, How Recursion works? Simulating recursion using stack (Hrs 8)
UNIT IV: Queues
Fundamentals, queue as ADT, Representation and Implementation of queue using arrays, Circular queue: representation and implementation, Applications of queue: Josephus Problem, Job Scheduling, Queue Simulation, Categorizing Data, Doubly Ended Queue, representation of multiple queues using single array, Priority queue (Hrs6)
UNIT V: Searching and Sorting:
Searching: Sequential, binary and Index sequential search.
Sorting: General concepts: sort order, sort stability, efficiency and passes, Bubble