210244: DATA STRUCTURES AND ALGORITHMS

Teaching SchemeExamination Scheme Lectures: 4 Hrs./week Theory: 100 Marks

Prerequisite: Computer Fundamentals and Programming (Subject Code: 110013)

Learning objectives

1.

To develop the ability to synthesize and analyze algorithms

2.

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

(Hrs 8)

## 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.

(Hrs 8)

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