DATA STRUCTURES AND ALGORITHM DESIGN

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

Max. Marks: 100.00

 

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

 
 

CO84.       Define the basic types for data structures like stacks, queues, linked lists along with their strengths and weaknesses

CO85.       Examine the use of different data structures and apply methods in algorithm design and analysis.

CO86.       Apply the appropriate data structure in context of solution of given problem.

CO87.       Develop programming skills which require to solve given problem

CO88.       Formulate the problem statement and apply appropriate algorithm to it.

CO89.       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

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, Queues, Searching, and Sorting

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, Graphs, Divide and Conquer Method

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 and Dynamic Programming

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, Branch and Bound

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

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.

Academic Year: 
2022-23
  • Printer-friendly version