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

Semester III - Paper IV - CS213 - Data Structures and Algorithms

Lecture Lab: 4
Duration: 3 hrs
Maximum Marks: 75
Credits: 3

UNIT - I:

Definition of a Data structure - primitive and composite Data Types, Asymptotic notations, Arrays, Operations on Arrays, Order lists.

UNIT - II:

Stacks - Applications of Stack - Infix to Postfix Conversion, Recursion, Maze Problems - Queues - Operations on Queues, Queue Applications, Circular Queue.

UNIT - III :

Singly Linked List - Operations, Application - Representation of a Polynomial, Polynomial Addition; Doubly Linked List - Operations, Applications - Ordering of Books in Library (Alphabetical Ordering).

UNIT - IV :

Trees and Graphs: Binary Trees - Conversion of Forest to Binary Tree, Operations - Tree Traversals; Graph - Definition, Types of Graphs, Hashing Tables and Hashing Functions, Traversal - Shortest Path; Dijkstra's Algorithm.

UNIT - V:

Algorithm - Definition - Examples - Complexity - Divide and Conquer - Binary Search - Maximum and Minimum - Merge Sort.

References:

1. E.Horowitz and S. Shani Fundamentals of Data Structures in C++, Galgotia Pub. 1999.
2. Horowitz, S. Sahni, and S. Rajasekaran, Computer Algorithms, Galgotia Pub. Pvt. Ltd., 1998.
3. R. Kruse C.L. Tondo and B. Leung, Data Structures and Program design in C, PHI, 1997.