210250: DATA STRUCTURES
Teaching Scheme Examination 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 study implementation of data structures using OOP concepts
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 [TB 1]
Trees
Basic tree concepts, binary trees and their properties, representation using sequential
and linked organization, full and complete binary trees, converting tree to a binary
tree, binary tree traversals, BFS ,DFS (recursive and non recursive), infix, postfix,
prefix, Huffman’s codes. Binary search trees & operations. BST as an ADT, 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 (8 Hrs)
UNIT – II [TB 1]
Graphs
Basic concepts, operations, graphs storage structures, Traversals: Depth First and
Breadth First. Graph algorithm, Graph as an ADT, Minimum spanning trees:
Kruskal’s and Prim’s. Algorithm for shortest path and topological sorting (8 Hrs)
UNIT – III [TB 1]
Symbol Tables: Static & dynamic tree table ,AVL tree ,AVL tree implementation,
AVL tree algorithms.
Hash Tables: Basic concepts, hash function, hashing methods, collision resolution,
bucket hashing. (8 Hrs)
UNIT IV [TB 1]
Heaps and multi way trees
Heap: Basic concepts, heap implementation algorithm & heap sort, heap as an ADT,
heap applications.
Multi way trees: B tree implementation, B-tree variations (8 Hrs)
UNIT V [RB4]:
Files
External storage devices, Files: Definition and concepts, File organization: Sequential
files, random, linked, inverted and cellular partitions. Processing of sequential, Indexsequential
and direct files.
Sequential file organisation, direct file organisation, index sequential file organisation
and their implementation. (8 Hrs)
UNIT VI [TB 2]
Abstract data types: ADT, classes and objects, generic programming: introduction to
STL (Standard Template Library), containers, iterators and algorithms, study of
container template classes for vectors and stacks and related algorithms. (8 Hrs)
Text Books(TB):
1. R. Gilberg, B. Forouzan, “Data Structures: A pseudo code approach with C”,
Cengage Learning, ISBN 9788131503140.
2. A. Michael Berman, “Data structures via C++”, Oxford University Press, 2002,
ISBN-0-19-510843-4.
Reference Books(RB):
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 and A. Tannenbaum, “Data Structures using C and
C++”, 2nd Edition, Prentice Hall of India, 2002, ISBN-81-203-1177-9.
3. R. Gilberg, B. Forouzan, “Data Structures: A pseudo code approach with
C++”, Cengage Learning, ISBN 9788131504925.
4. A. Tharp ,”File organisation and processing”,2008 ,Willey India
edition ,9788126518685
5. A. Drozdek, “Data Structures in C++”, 2nd Edition, Thomson Brookes /COLE
Books, 2002, ISBN 981 – 240 – 079 – 6.
6. J. Tremblay, P. Soresan, “An introduction to data structures with Applications”,
2nd edition, Tata McGraw-Hill International Editions, 1984, ISBN-0-07-462471-7.
7. M. Folk, B. Zoellick, G. Riccardi, “File Structure An Object oriented approach
with C++”, Pearson Education, 2002, ISBN 81 – 7808 – 131 – 8.
8. M. Weiss, “Data Structures and Algorithm Analysis in C++”, 2nd edition,
Pearson Education, 2002, ISBN-81-7808-670-0
Teaching Scheme Examination 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 study implementation of data structures using OOP concepts
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 [TB 1]
Trees
Basic tree concepts, binary trees and their properties, representation using sequential
and linked organization, full and complete binary trees, converting tree to a binary
tree, binary tree traversals, BFS ,DFS (recursive and non recursive), infix, postfix,
prefix, Huffman’s codes. Binary search trees & operations. BST as an ADT, 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 (8 Hrs)
UNIT – II [TB 1]
Graphs
Basic concepts, operations, graphs storage structures, Traversals: Depth First and
Breadth First. Graph algorithm, Graph as an ADT, Minimum spanning trees:
Kruskal’s and Prim’s. Algorithm for shortest path and topological sorting (8 Hrs)
UNIT – III [TB 1]
Symbol Tables: Static & dynamic tree table ,AVL tree ,AVL tree implementation,
AVL tree algorithms.
Hash Tables: Basic concepts, hash function, hashing methods, collision resolution,
bucket hashing. (8 Hrs)
UNIT IV [TB 1]
Heaps and multi way trees
Heap: Basic concepts, heap implementation algorithm & heap sort, heap as an ADT,
heap applications.
Multi way trees: B tree implementation, B-tree variations (8 Hrs)
UNIT V [RB4]:
Files
External storage devices, Files: Definition and concepts, File organization: Sequential
files, random, linked, inverted and cellular partitions. Processing of sequential, Indexsequential
and direct files.
Sequential file organisation, direct file organisation, index sequential file organisation
and their implementation. (8 Hrs)
UNIT VI [TB 2]
Abstract data types: ADT, classes and objects, generic programming: introduction to
STL (Standard Template Library), containers, iterators and algorithms, study of
container template classes for vectors and stacks and related algorithms. (8 Hrs)
Text Books(TB):
1. R. Gilberg, B. Forouzan, “Data Structures: A pseudo code approach with C”,
Cengage Learning, ISBN 9788131503140.
2. A. Michael Berman, “Data structures via C++”, Oxford University Press, 2002,
ISBN-0-19-510843-4.
Reference Books(RB):
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 and A. Tannenbaum, “Data Structures using C and
C++”, 2nd Edition, Prentice Hall of India, 2002, ISBN-81-203-1177-9.
3. R. Gilberg, B. Forouzan, “Data Structures: A pseudo code approach with
C++”, Cengage Learning, ISBN 9788131504925.
4. A. Tharp ,”File organisation and processing”,2008 ,Willey India
edition ,9788126518685
5. A. Drozdek, “Data Structures in C++”, 2nd Edition, Thomson Brookes /COLE
Books, 2002, ISBN 981 – 240 – 079 – 6.
6. J. Tremblay, P. Soresan, “An introduction to data structures with Applications”,
2nd edition, Tata McGraw-Hill International Editions, 1984, ISBN-0-07-462471-7.
7. M. Folk, B. Zoellick, G. Riccardi, “File Structure An Object oriented approach
with C++”, Pearson Education, 2002, ISBN 81 – 7808 – 131 – 8.
8. M. Weiss, “Data Structures and Algorithm Analysis in C++”, 2nd edition,
Pearson Education, 2002, ISBN-81-7808-670-0
No comments:
Post a Comment