DATA STRUCTURES AND ALGORITHM DESIGN

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

This course enables the students to

  1. Create different types of data structures and learn their significance and their applications.
  2. Apply basic data structures and algorithms for different applications.
  3. Evaluate the complexity of algorithms when applied to specific problems.
  4. Develop skills to solve the problems using different techniques.

 

Course Outcomes(COs):

 

Learning Outcome (at course level)

 

Learning and teaching strategies

Assessment Strategies

CO59.Demonstrate basic ADTs such as stacks, queues and trees.

CO60.Compare various searching and sorting techniques.

CO61.Applies algorithms and data structures in real-life applications.

        CO62. Design     and     develop      small

applications in C

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 - Algorithm definition and specification – Design of Algorithms, and Analysis of Algorithms,

Asymptotic Notations, Growth of function: Asymptotic notations

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

 

13.00
Unit II: 

Stacks – Array representation & Implementation, Operations on Stacks: Push & Pop, Linked representation of stack, Conversion of infix to prefix and postfix expressions, Evaluation of postfix expression using stack,  Queues - Array and linked representation and implementation, Operations on Queue: Create, Add, Delete,

Full and Empty, Circular queues,  

Searching: Linear and Binary Search Methods

Sorting: Bubble Sort, Selection Sort, Insertion Sort

 

12.00
Unit III: 

Trees: Binary tree, Terminology & Representation, Binary Search Trees (BST)-Insertion and Deletion Graphs: Terminology & Representations, Graphs & Multi-graphs, Directed Graphs, Elementary Graph algorithms, Representation of Graphs, BFS, DFS. Divide and Conquer Method: Merge Sort, Quick Sort

 

 

12.00
Unit IV: 

The  Greedy Method:- Knapsack Problem,Minimum Cost Spanning Tree, Single  Source Shortest Path

Dynamic Programming: Multistage Graphs, All Pair Shortest Path, Optimal Binary Search Trees , 0/1 Knapsack Problem, Traveling Salesman Problem

 

13.00
Unit V: 

Backtracking:- General method – 8-Queens Problem, Sum of Subsets, Hamiltonian Cycles  

Branch and Bound :- The Method– Knapsack Problem

 

ESSENTIAL READINGS: 
  • Anany Levitin, “Introduction to the Design and Analysis of Algorithms”, Third Edition, Pearson Education, 2012.
  • Thomas H.Cormen, Charles E.Leiserson, Ronald L. Rivest and Clifford Stein, “Introduction to Algorithms”, Third Edition, PHI Course Private Limited, 2012.
  • 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
  • A. Tannenbaum, “Data Structure Using C”, Pearson Education, 2019.

 

REFERENCES: 
  • Donald E. Knuth, “The Art of Computer Programming”, Volumes 1& 3 Pearson Education,2009.  
  • Steven S. Skiena, “The Algorithm Design Manual”, Second Edition, Springer, 2008.
  • E. Horowitz &Sahni, “Fundamental Data Structure”, Galgotia Book Source, 1983.   

    

 

Academic Year: 
2021-22
  • Printer-friendly version