DATA STRUCTURES AND ALGORITHM DESIGN

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

Course Objectives

This course enables 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 Outcomes(COs):

 

Learning Outcome (at course level)

 

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 which require 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 - 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.

12.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”, Fourth Edition, PHI Course Private Limited, 2015.
  • Thomas H Coremen, Charles E Leiserson, Ronald L Rivest, Clifford Stein, “Introduction to Algorithms”, Mc-Graw Hill, 2006
  • A. Tannenbaum, “Data Structure Using C”, Pearson Education, 2019

 

Suggested Readings:

  • 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.
  • Donald E. Knuth, “The Art of Computer Programming”, Volumes 1& 3 Pearson Education, 2009

 

REFERENCES: 

E-Resources

·      NPTEL Lecture Series on Data Structures and Algorithms by Dr. Naveen Garg, Department of Computer Science & Engineering ,IIT Delhi. https://youtu.be/zWg7U0OEAoE

·      Programming and Data structures (PDS), IIT Madras BY Dr. N S. Narayanaswamy https://youtu.be/6PxgaUm46Sohttps://youtu.be/6PxgaUm46So4So

·      Introduction to algorithms and analysis, IIT Kharagpur Prof. Sourav Mukhopadhyayhttps://youtu.be/D-DczeibACE

 

Journals

·      International Journal of Data Structures (IJDS)

·      INTERNATIONAL RESEARCH JOURNAL OF SCIENCE ENGINEERING AND TECHNOLOGY

·      International Journal of Computing Algorithm (IJCOA)
Print ISSN:2278-2397

·      International Journal of Algorithms Design and Analysis

·      International Journal of Computer Science & Programming languages

  

Academic Year: 
2023-24
  • Printer-friendly version