CS 1211 DATA STRUCTURES AND ALGORITHMS 3 1 0 100
AIM
To present the concept of arrays, recursion, stack, queue, linked list, trees and graph data
structures.
OBJECTIVES
i.* * To introduce the concept of arrays, structures, pointers and recursion.**
ii. To study stack, queue and linked list concepts.
iii. To study trees, representation of trees, tree traversal and basic operations on trees.
iv. To study some of the sorting and searching techniques.
v. To study the concept of graphs, traversal techniques and minimum spanning tree.
*1. INTRODUCTION TO DATA STRUCTURES 9 *
Abstract data types  Sequences as value definitions  Data types in C  Pointers in C Data structures and C  Arrays in C  Array as ADT  One dimensional array Implementing one dimensional array  Array as parameters  Two dimensional array Structures in C  Implementing structures  Unions in C  Implementation of unions Structure parameters  Allocation of storage and scope of variables.
Recursive definition and processes: Factorial function  Fibonacci sequence  Recursion in C  Efficiency of recursion.
* *
*2. STACK, QUEUE AND LINKED LIST 9 *
Stack definition and examples – Primitive operations – Example  Representing stacks in C  Push and pop operation implementation.
Queue as ADT  C Implementation of queues  Insert operation  Priority queue  Array implementation of priority queue.
Inserting and removing nodes from a listlinked implementation of stack, queue and priority queue  Other list structures  Circular lists: Stack and queue as circular list Primitive operations on circular lists. Header nodes  Doubly linked lists  Addition of long positive integers on circular and doubly linked list.
*3. TREES 9 *
Binary trees: Operations on binary trees  Applications of binary trees  Binary tree representation  Node representation of binary trees  Implicit array representation of binary tree – Binary tree traversal in C  Threaded binary tree  Representing list as binary tree  Finding the Kth element  Deleting an element.
Trees and their applications: C representation of trees  Tree traversals  Evaluating an expression tree  Constructing a tree.
*4. SORTING AND SEARCHING 9 *
General background of sorting: Efficiency considerations, Notations, Efficiency of sorting. Exchange sorts: Bubble sort; Quick sort; Selection sort; Binary tree sort; Heap sort. Heap as a priority queue  Sorting using a heapheap sort procedure  Insertion sorts: Simple insertion  Shell sort  Address calculation sort  Merge sort Radix sort.
* * Sequential search: Indexed sequential search  Binary search  Interpolation search.
* *
*5. GRAPHS* *9*
Application of graph  C representation of graphs  Transitive closure  Warshall's algorithm – Shortest path algorithm  Linked representation of graphs  Dijkstra's algorithm  Graph traversal  Traversal methods for graphs  Spanning forests  Undirected graph and their traversals  Depth first traversal  Application of depth first traversal  Efficiency of depth first traversal  Breadth first traversal  Minimum spanning tree  Kruskal's algorithm  Round robin algorithm. L=45 T=15 Total = 60
TEXT BOOK 1. Aaron M. Tenenbaum, Yeedidyah Langsam, Moshe J. Augenstein, 'Data structures using C', Pearson Education, 2004 / PHI.
REFERENCE BOOKS
1. E. Balagurusamy, 'Programming in Ansi C', Second Edition, Tata McGraw Hill
Publication, 2003.
*2. Robert L. Kruse, Bruce P. Leung Clovis L.Tondo, 'Data Structures and Program Design in C', Pearson Education, 2000 / PHI.*
* *
* *
