210250: DATA STRUCTURES

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

Prerequisite: Data structures and Algorithms (Subject Code: 210244)

Learning objectives

1.

To study the representation, implementation and applications of data structures

2.

To compare alternative implementations of data structures

3.

To compare the benefits of static and dynamic data structures

4.

To choose the appropriate data structure for modeling a given problem

# UNIT – I

Linked Lists

Concept of linked organization, Singly linked list, Operations such as Insertion, deletion, inversion, concatenation, Computation of length, traversal on linked list, Applications: Representation and manipulations of polynomials using linked lists, Representation of sparse matrix using linked organization, Linked Stacks and Queues, circular linked list, doubly linked list and dynamic storage management, Representation of polynomial/set using generalized linked list, Dynamic memory management: Garbage collection and Compaction. (Hrs 8)

# UNIT – II

# Trees

Review of basic terminology, binary trees and its representation using sequential and linked organization, full and complete binary trees, converting tree to a binary tree, binary tree traversals (recursive and non recursive), operations such as copy, equal etc, Threaded binary trees, Insertion and deletion of nodes in in-order threaded binary tree, preorder, in-order and post order traversals of in-order threaded binary tree, applications of binary trees: Gaming, Expression and decision trees (Hrs 8)

# UNIT – III

Graphs Review of basic terminology, Representation of graphs using adjacency matrix, adjacency list and adjacency Multi-list, Traversals: Depth First and Breadth First, Connected components and spanning trees, Kruskal’s and Prim’s algorithms for minimum spanning tree, Algorithm for shortest path and topological sorting (Hrs 8)

# UNIT – IV

Symbol Tables: Notion of a symbol table, representation, static tree tables and dynamic tree tables

Hash Tables

Hash Tables, Hash Functions: Division and Multiplication methods, Collusion Resolution Strategies: Chaining and Open addressing, Table Overflow: Expansion and extendible hashing.

UNIT V