Savitribai Phule Pune University, Maharashtra (SPPU), Information Technology Semester 3, Data Structure & Algorithms Syllabus

214443:Data Structure & Algorithms

Credit Scheme: 3

Unit- I Introduction
Introduction to Data Structures: Concept of data, Data object, Data structure, Concept of Primitive and non-primitive, linear and Nonlinear, static and dynamic, persistent and ephemeral data structures, Definition of ADT
Analysis of algorithm: Frequency count and its importance in analysis of an algorithm, Time complexity & Space complexity of an algorithm Big 'O', ‘Ω' and 'Θ' notations,

Sequential Organization: Single and multidimensional array and address calculation.
Linked Organization: Concept of linked organization, Singly Linked List, Doubly Linked List, Circular Linked List (Operations: Create, Display, Search, Insert, Delete).
Case Study Set Operation, String Operation

Unit- II Searching and Sorting
Searching and sorting: Need of searching and sorting, Concept of internal and external sorting, sort stability, Searching methods: Linear and binary search algorithms, Fibonacci Series.
Sorting methods: Bubble, insertion, Quick, Merge, shell and comparison of all sorting methods. Analyze Insertion sort, Quick Sort, binary search, hashing for Best, Worst and Average case.

Case Study Study and Analyze Selection sort, bucket sort,radix sort.

Unit- III Stack & Queue
Stack: Concept of stack, Concept of implicit and explicit stack, stack as an ADT using sequential and linked organization, Applications of stack: recursion, converting expressions from infix to postfix or prefix form, evaluating postfix or prefix form.
Queue: Concept of queues as ADT, Implementation of queue using array and linked organization, Concept of circular queue, double ended queue, Applications of queue: priority queue.
Case Study Reversing a string, balanced parentheses in algebraic expressions, Tower of Hanoi problem, double ended queue as Stack and Queue.

Unit- IV Trees
Tree : Trees and binary trees-concept and terminology, Expression tree, Binary tree as an ADT, , Binary search tree, Recursive and Non recursive algorithms for binary tree traversals ,Binary search tree as ADT(Insert Search Delete, level wise Display)
Threaded binary tree: Concept of threaded binary tree (inorder, preorder and postorder). Preorder and In-order traversals of in-order threaded binary tree, Applications of trees.
Case Study Construction of BST from pre and postorder traversal, Expression Tree construction

Unit- V Graph and Symbol Table
Graph -Concept and terminologies, Graph as an ADT, Representation of graphs using adjacency matrix and adjacency list, Breadth First Search traversal, Depth First Search traversal, Prim’s and Kruskal’s algorithms for minimum spanning tree, Shortest path using Dijkstra's algorithm, topological sorting.
Symbol Table -Notion of Symbol Table, OBST, AVL Trees
Heap: Heap data structure, Min and Max Heap, Heap sort, applications of heap
Case Study Consider a network of computers connected to each other. The connection has various parameters associated with it as distance, propagation delay, bandwidth (capacity of carrying data), etc. Based on these parameters, decide which path should be chosen to send data from one computer to every other on the network.
In a system, jobs are submitted for execution at different times. If the system is idle, the job is taken for executed immediately. If there is a job in execution, the newly submitted job is added to a queue. The jobs are assigned a number, which indicates tells the priority of the jobs. The system must execute the high priority jobs first for execution. Implement the above said system using heap data structure.

Unit- VI Hashing and File Organization
Hashing: Hash tables and scattered tables: Basic concepts, hash function, characteristics of good hash function, Different key-to-address transformations techniques, synonyms or collisions, collision resolution techniques- linear probing, quadratic probing, rehashing, chaining with and without replacement.
File:Concept of File, File types and file organization (sequential, index sequential and Direct Access), Comparison of different file organizations.
Case Study What are the advantages of binary tree and binary search in file handling?
Study Hashing techniques for expandable Files(Extendible, Dynamic and Linear Hashing)

Text Books:

1. E. Horowitz, S. Sahni, D. Mehta, "Fundamentals of Data Structures in C++", Galgotia Book Source, New Delhi, 1995, ISBN 16782928
2. Y. Langsam, M. Augenstin, A. Tannenbaum, "Data Structures using C and C++", 2nd Edition, Prentice Hall of India, 2002, ISBN-81-203-1177-9.

Reference Books:

1. G. A.V, PAI , “Data Structures and Algorithms “, McGraw Hill, ISBN -13: 978-0-07-066726-6
2. A. Tharp ,"File Organization and Processing", 2008 ,Willey India edition, 9788126518685
3. M. Folk, B. Zoellick, G. Riccardi, "File Structure An Object Oriented Approach with C++", Pearson Education, 2002, ISBN 81 - 7808 - 131 - 8.

4. M. Welss, “Data Structures and Algorithm Analysis in C++", 2nd edition, Pearson Education, 2002, ISBN- 81-7808-670-0