CT11 DATA
STRUCTURES THROUGH C
Structure
1. Introduction to C Programming
2. Arrays
3. Linked Lists
4. Recursion and Backtracking
5. Stacks and Queues
6. Trees
7. Searching and Sorting
8. Graphs
9. General Search Trees
10. Dynamic Memory Management
Details
1.
Introduction to C Programming
1.1 A Tutorial Introduction
1.2 Types, Operators, and
Expressions
1.3 Control Flow
1.4 Functions and Program Structure
1.5 Pointers and Arrays
1.6 Structures
1.7 Input and Output
2.
Arrays
2.1 Representation of arrays -single and multidimensional arrays
2.2 Address calculation using column and row major ordering
3.
Linked lists
3.1
Singly linked lists -operations on list
3.2
Circular and Doubly linked lists with header node
3.3
Polynomial representation and manipulation using linked lists
3.4
Generalized lists
3.5
Sparse matrix representation using generalized list structure
4.
Recursion and Backtracking
4.1 The
Eight-Queens Problem
4.2 The Stable Marriage Problem
5.
Stacks and Queues
5.1
Representation of stacks and queues using arrays
5.2
Circular Queues
5.3
Conversion from infix to postfix and prefix expressions
5.4
Evaluation of postfix expression using stacks.
5.5
Linked Stacks and Queues
5.6
Multiple Stacks and Queues
5.7
Deque (Double Ended Queue)
5.8
Priority Queues
6.
Trees
6.1
Binary tree traversal methods
6.2
Recursive and non recursive algorithms for tree traversal methods
6.3
Threaded Binary trees
6.4
Binary Search trees
6.5
Height balanced (AVL) trees
6.6
Huffman trees
6.7
General Ordered Trees and
equivalent
6.8 Decision and game trees
7.
Searching and Sorting
7.1
Searching
7.1.1
Sequential and Binary searches
7.1
.2 Indexed search
7.1.3
Hashing schemes
7.2
Sorting
7.2.1 Insertion, Selection and Bubble
sort
7.2.2 Quick sort, Heap sort and Merge
sort
7.2.3 Radix and Shell sort
7.3 Analysis of searching and sorting algorithms
8.
Graphs
8.1 Graph representation schemes:
Adjacency Matrix, Adjacency List and Linked
representation
8.2 Graph Traversal schemes: DFS, BFS
8.3 Minimum spanning trees: Kruskal Algorithm, Prim’s
Algorithm
8.4 Dijkstra’s
Shortest path algorithm
8.5 Network Flow Problem
8.6 Scheduling Problem
8.7 Topological sort
9.
General Search Trees
9.1 Multiway
Search Trees
9.2 B-trees
9.2.1
Definition of B- Tree
9.2.2
Basic operations on B- Tree
9.3 B+ Trees
10.
Dynamic Memory Management
10.1 Firstfit and bestfit
approaches
10.2 Boundary Tag method
10.3 Buddy systems
Text
Books
1. Kernighan and Ritchie, "The C Programming
Language", Prentice Hall of India, 1989.
2.,
Tenenbaum, Augestein
and Langsam "Data Structures using C",
Prentice Hall, 1992
3.
Horowitz and Sahani, "Fundamentals of
Data Structures ", Galgotia Book Source
(GBS) Publication, reprint, 1994.
Reference
Books
1. R.G. Dromey,
"How to Solve it by Computer", Prentice Hall of India, 1992.
2. Kruse, Tondo
and Leung, "Data Structures and Program Design in C", Prentice Hall,
2007
3. Donald E. Knuth, "The Art of
Computer Programming vol.1-
Fundamental Algorithms ", Addison Weslay, 1975.
4. Niklaus
Wirth, “Algorithms + Data Structures = Programs”, Prentice Hall, 2001