TCS-607 DATA STRUCTURES USING C++

UNIT 1.
COMPLEXITY ANALYSIS: Time and Space complexity of algorithms, asymptotic analysis, big O and other notations, importance of efficient algorithms, program performance measurement, data structures and algorithms.
LINEAR LISTS: Abstract data type, sequential and linked representations, comparison of insertion,deletion and search operations for sequential and linked lists, list and chain classes, exception and iterator classes for lists, doubly linked lists, circular lists, linked lists through simulated pointers, lists in STL, skip lists, applications of lists in bin sort, radix sort, sparse tables.

UNIT 2.
STACKS AND QUEUES: Abstract data types, sequential and linked implementations, exception handling in classes, representative applications such as parenthesis matching, towers of Hanoi,wire routing in a circuit, finding path in a maze, simulation of queuing systems, equivalence problem.

UNIT 3.
HASHING: Search efficiency in lists and skip lists, hashing as a search structure, hash table,collision avoidance, linear open addressing, chains, uses of hash tables in text compression, LZW algorithm.

UNIT 4.
TREES: Binary trees and their properties, terminology, sequential and linked implementations,tree traversal methods and algorithms, heaps as priority queues, heap implementation, insertion and deletion operations, heapsort, heaps in Huffman coding, leftist trees, tournament trees, use of winner trees in mergesort as an external sorting algorithm, bin packing.

UNIT 5.
GRAPHS: Definition, terminology, directed and undirected graphs, properties, connectivity in graphs, applications, implementation – adjacency matrix and linked adjacency chains, graph traversal – breadth first and depth first, spanning trees.

SUGGESTED BOOKS:

1. M. T. Goodrich and R. Tamassia, Algorithm Design: Foundations, Analysis and Internet Examples, John Wiley & Sons, 2001.
2. Drozdek, A., “Data Structures and Algorithms in C++”, Vikas Publishing House. 2002
3. Wirth, N., “Algorithms and Data Structures”, Prentice-Hall of India. 1985
4. Lafore, R., “Data Structures and Algorithms in Java”, 2nd Ed., Dorling Kindersley. 2007
5. Datastructure using C, Bandopadhyaya, “Data Structures, Algorithms, and Applications in Java”,WCB/McGraw-Hill. 2001
6. C and datastructure, Padnabham, BSP, Hyderabad