Data Structures using C++

Paper Code: 
MCA 222
Credits: 
04
Periods/week: 
04
Max. Marks: 
100.00
Objective: 
  • To provide an introduction to basic data structures, and algorithms for manipulating them, by using C++ programming language.
  • The fundamental design, analysis, and implementation of basic data structures and algorithms.
  • The analysis and evaluation of the data structure needs of particular problems.
  • The design, analysis, and implementation of C++ programs by using basic data structures and algorithms.
10.00
Unit I: 
Introduction to Data Structures

The role of Algorithms in Computing, Analyzing Algorithms, Designing Algorithms.

Growth of Functions: Asymptotic notation, Standard notations & Common functions.

14.00
Unit II: 
Elementary Data Structures

Linked lists – Searching, Insertion, Deletion, Sorted Linked List, Circular List, Header list, Two way list.

Stacks – Array representation & implementation of stack, Operations on Stacks : Push & Pop, Linked representation of stack, Applications of stack : Conversion of infix to prefix and postfix expressions, Evaluation of postfix expression using stack, Applications of recursion in problems like “Tower of Hanoi”.

Queues - Array and linked representation and implementation of queues, Operations on Queue: Create, Add, Delete, Full and Empty, Circular queues, D-queues and Priority Queues.

10.00
Unit III: 
Searching

Linear and binary search methods, Comparison and analysis, Hashing: Hash Table, Hash functions.

Sorting: Bubble sort, Selection sort, Insertion sort, Quick sort, Merge sort, Heap sort, Radix sort.

12.00
Unit IV: 
Trees

Binary tree, Terminology & Representation, Binary Search Trees (BST)-

Insertion and Deletion, AVL Trees, B-trees.

14.00
Unit V: 
Graphs

Terminology & Representations, Graphs & Multi-graphs, Directed Graphs, Elementary Graph algorithms, Representation of Graphs, BFS, DFS.

Minimum Spanning Trees, The algorithm of Kruskal &Prim.

Single Source Shortest Path – The Bellman-Ford algorithm, Dijkstra‘s algorithm.

All Pair Shortest Path, The Floyd, Warshall algorithm, Basics of NP – Completeness.

ESSENTIAL READINGS: 
  • Thomas H Coremen, Charles E Leiserson, Ronald L Rivest, Clifford Stein, “Introduction to Algorithms”, Mc-Graw Hill, 2006
  • D.S Malik, “Data Structures using C++”, Cengage Learning, 2nd  edition, 2009
REFERENCES: 
  • Jean – Paul Tremblay, Paul G. Sorenson, “An Introduction to Data Structures with Applications”, Mc-Graw Hill Companies, 2001.
  • Micheal T. Goodrich, Roberto Tamassia, Davis M. Mount, “Data Structures and Algorithms in C++”, John Wiley & Sons Inc., 2nd edition, 2011.
  • R.S. Salaria, “Data structures & Algorithms using C++”, Khanna Book Publishing Co.  (P) Ltd., Delhi, 2009
  • R. Krusetal, “Data Structures and Program Design in C”, Pearson Education Asia, Delhi- 2002.

 

Academic Year: 
2015-16
  • Printer-friendly version