Analysis and Design of Algorithm

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

           The course will enable the students to

·         To provide an introduction to basic data structures, and algorithms for manipulating them, by using  programming language.

·         To learning he fundamental design, analysis, and implementation of  Greedy algorithms , Dynamic and backtracking algorithms.

·         To understand the analysis and evaluation of the data structure needs of particular problems.

·         To demonstrate design, analysis, and implementation of programs by using basic data structures and algorithms.

.          Formulate  design process, analysis, and implementation of programs by using  Greedy , dynamic and backtracking  algorithms 

 

Course Learning Outcomes (CLOs):

 

Learning Outcome (at course level)

Students will be able to:

Learning and teaching strategies

Assessment Strategies

  1. Learning of complexity of different algorithm
  2. Be capable to identity the appropriate data structure for given problem
  3. Demonstrate the data structure needs for particular problems.
  4. Illustrate applications of greedy method, dynamic programming, Backtracking and Branch and Bound
  5. Develop new applications using greedy method, dynamic programming, Backtracking and Branch and Bound

Approach in teaching:

Interactive Lectures, Discussion, Presentations, Video Tutorials, Demonstration.

 

Learning activities for the students:

Self-learning Assignments, Effective questions, Simulation

  • Assignments
  • Written test in classroom
  • Classroom Activity
  • Continuous Assessment
  • Semester End Examination

 

10.00
Unit I: 
Introduction

Algorithm definition and specification – Design of Algorithms, and Complexity of Algorithms, Asymptotic Notations, Growth of function

12.00
Unit II: 
Elementary Data structures

Stacks and queues – Link Lists- Trees – priority queues –sets  and disjoint set union – graphs – basic traversal and search techniques.

12.00
Unit III: 
Divide – and – conquer

General method – binary search – merge sort – Quick sort – The  Greedy method:-General method – knapsack problem – minimum cost spanning tree – single  source shortest path

13.00
Unit IV: 

Dynamic Programming – general method – multistage graphs – all pair shortest path – optimal binary search trees – 0/1 Knapsack – traveling salesman problem

13.00
Unit V: 

Backtracking:- general method – 8-Queens problem – sum of subsets

Hamiltonian cycles – knapsack problem – Branch and bound:- The Method – 0/1 Knapsack problem – traveling salesperson.

ESSENTIAL READINGS: 
  • AnanyLevitin, “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 Learning Private Limited, 2012.
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: 
2019-20
  • Printer-friendly version