UNIVERSITY OF MADRAS
B.Sc. DEGREE COURSE IN SOFTWARE ENGINEERING
SEMESTER SYSTEM WITH CREDITS
(Effective from the Academic Year 2003-2004)

SYLLABUS

Semester IV - BSE 204 - Data Structure

Lecture Per Week: 6 hrs
Duration of Examination: 3 hrs
Maximum Marks: 100
Credits: 4

Unit I

Abstract data types - asymptotic notations - complexity analysis - arrays - representation of arrays - operations on arrays - ordered lists - polynomials.

Unit II

Singly linked lists - circular linked lists - doubly linked lists - general lists - stacks - queues - circular queues - evaluation of expressions.

Unit III

Trees - binary trees - binary tree traversals - binary tree representations - binary search trees - threaded binary trees - application of trees - (sets), representation of graphs - graph implementation - graph traversals - applications of graph traversals - minimum cost spanning trees - shortest path problems.

Unit IV

Internal sorting - Optimal sorting time - Sorting Large Objects - Sorting with Tapes - Sorting with Disks.

Unit V

Hashing - AVL trees - red-black trees - splay trees - B - trees.

Books for Study

1. E.Horowitz, S.Sahni - Fundamentals of Data Structures in C++ - Galgotia, 1999.

2. Gregory L.Heileman - Data Structures, Algorithms and Object Oriented Programming, McGraw Hill International Editions - 1996