Data Structures using C++

Paper Code: 
MCA 222
Credits: 
04
Periods/week: 
04
Max. Marks: 
100.00
Objective: 

 The course will enable the students to

  1. Understand basic data structures, and algorithms for manipulating them
  2. Learn to design algorithms and apply the algorithm analysis techniques.
  3. Differentiate between different types of data structures, their significance and their applications.
  4. Implementation of basic data structures and algorithms.
  5. Evaluate the complexity of algorithms when applied to specific problems.
  6. Develop skills to solve the problems using different techniques

 Course Learning Outcomes (CLOs):

 

Learning Outcome (at course level)

Students will be able to:

Learning and teaching strategies

Assessment Strategies

  1. Define the basic types for data structures like stacks, queues, linked lists along with their strengths and weaknesses
  2. Examine the use of different data structures and apply methods in algorithm design and analysis.
  3. Apply the appropriate data structure in context of solution of given problem.
  4. Develop programming skills required to solve given problem.
  5. Formulate the problem statement and apply appropriate algorithm to it.
  6. Analyze the complexity of algorithms when applied to specific problems.

Approach in teaching:

Interactive Lectures, Discussion, Tutorials, , Demonstration

 

Learning activities for the students:

Self-learning assignments, Effective questions, Quizzes, Presentations, Discussions

 

  • Assignments
  • Written test in classroom
  • Classroom activity
  • Written test in classroom
  • Semester End Examination

 

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: 
2019-20
  • Printer-friendly version