CS1151 DATA STRUCTURES 3 1 0 100
AIM:
To provide an in-depth knowledge in problem solving techniques and data structures.
OBJECTIVES:
• To learn the systematic way of solving problems
• To understand the different methods of organizing large amounts of data
• To learn to program in C
• To efficiently implement the different data structures
• To efficiently implement solutions for specific problems
UNIT I PROBLEM SOLVING 9
Problem solving – Top-down Design – Implementation – Verification – Efficiency – Analysis – Sample algorithms.
UNIT II LISTS, STACKS AND QUEUES 8
Abstract Data Type (ADT) – The List ADT – The Stack ADT – The Queue ADT
UNIT III TREES 10
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
UNIT IV SORTING 9
Preliminaries – Insertion Sort – Shellsort – Heapsort – Mergesort – Quicksort – External Sorting
UNIT V GRAPHS 9
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
TUTORIAL 15
TOTAL : 60
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)
REFERENCES:
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.
AIM:
To provide an in-depth knowledge in problem solving techniques and data structures.
OBJECTIVES:
• To learn the systematic way of solving problems
• To understand the different methods of organizing large amounts of data
• To learn to program in C
• To efficiently implement the different data structures
• To efficiently implement solutions for specific problems
UNIT I PROBLEM SOLVING 9
Problem solving – Top-down Design – Implementation – Verification – Efficiency – Analysis – Sample algorithms.
UNIT II LISTS, STACKS AND QUEUES 8
Abstract Data Type (ADT) – The List ADT – The Stack ADT – The Queue ADT
UNIT III TREES 10
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
UNIT IV SORTING 9
Preliminaries – Insertion Sort – Shellsort – Heapsort – Mergesort – Quicksort – External Sorting
UNIT V GRAPHS 9
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
TUTORIAL 15
TOTAL : 60
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)
REFERENCES:
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.
EmoticonEmoticon