CS1151--DATA STRUCTURES - Anna University Chennai Syllabus

CS1151--DATA STRUCTURES

PROBLEM SOLVING

Problem solving - Top-down Design - Implementation - Verification - Efficiency - Analysis - Sample algorithms.

LISTS, STACKS AND QUEUES

Abstract Data Type (ADT) - The List ADT - The Stack ADT - The Queue ADT

TREES

Preliminaries - Binary Trees - The Search Tree ADT - Binary Search Trees - AVL Trees - Tree Traversals - Hashing - General Idea - Hash Function - Separate Chaining - Open Addressing - Linear Probing - Priority Queues (Heaps) - Model - Simple implementations - Binary Heap

SORTING

Preliminaries - Insertion Sort - Shellsort - Heapsort - Mergesort - Quicksort - External Sorting

GRAPHS

Definitions - Topological Sort - Shortest-Path Algorithms - Unweighted Shortest Paths - Dijkstra-s Algorithm - Minimum Spanning Tree - Prim-s Algorithm - Applications of Depth-First Search - Undirected Graphs - Biconnectivity - Introduction to NP-Completeness

Reference

Text Books

1. R. G. Dromey, -How to Solve it by Computer- (Chaps 1-2), Prentice-Hall of India, 2002. 2. M. A. Weiss, -Data Structures and Algorithm Analysis in C 2nd ed, Pearson Education Asia, 2002. (chaps 3, 4.1-4.4 (except 4.3.6), 4.6, 5.1-5.4.1, 6.1-6.3.3, 7.1-7.7 (except 7.2.2, 7.4.1, 7.5.1, 7.6.1, 7.7.5, 7.7.6), 7.11, 9.1-9.3.2, 9.5-9.5.1, 9.6-9.6.2, 9.7)

Reference Books

1. Y. Langsam, M. J. Augenstein and A. M. Tenenbaum, -Data Structures using C Pearson Education Asia, 2004 2. Richard F. Gilberg, Behrouz A. Forouzan, -Data Structures - A Pseudocode Approach with C Thomson Brooks / COLE, 1998. 3. Aho, J. E. Hopcroft and J. D. Ullman, -Data Structures and Algorithms Pearson education Asia, 1983.