MCS-031 Design and Analysis of Algorithms
(4 Credits)
Objectives
Algorithm is the central concept of Computer Science. Whole of Computer Science can be thought of as revolving around the concept of algorithm ? the machines are designed and fabricated to execute algorithms; the programming languages are defined to describe algorithms so that the machines can understand and execute programs written in programming languages; the foundation/theory of Computer Science is the study of the limits of algorithmic methods, i.e., the study tells whether a particular task is accomplishable by a computer or not, etc.
Hence, the study of the Design and Analysis is of Algorithm has to be an essential part of any Computer Science/Engineering curriculum. Even if, software for solving all types of problems may become available in the future and the user/student may not be required to write an algorithm to solve any problem, still training the students in the skills of designing and analyzing the algorithms will remain essential, because these constitute the fundamental skills for solving problems with computers. It is like teaching of geometry to instill in students the skills of logical reasoning.
The objective of the course is to make the students aware of and well-groomed in the use of the tools & Techniques of designing and analyzing algorithms.
Syllabus
BLOCK 1
Introduction to Algorithmics
Unit 1:
Elementary Algorithmics
·
Example of an Algorithm
·
Problems and Instances
·
Characteristics of an Algorithm
·
Problems, Available Tools & Algorithms
·
Building Blocks of Algorithms
·
Outline of Algorithms
Unit 2:
Some pre-rquisites and
Asymptotic Bounds
·
Some Useful
Mathematical Functions & Notations
·
Mathematical Expectation
·
Principle of Mathematical
Induction
·
Concept of Efficiency of an
Algorithm
·
Well
Known Asymptotic Functions & Notations
Unit 3:
Basics of Analysis
·
Analysis of
Algorithm ? Simple Example
·
Well Known Sorting
Algorithms
·
Best-Case and
Worst-Case Analyses
·
Analysis of
Non-Recursive Control
Structures
·
Recursive Constructs
·
Solving Recurrences
·
Average-Case & Amortized Analyses
BLOCK 2 Design Techniques-I
Unit 1:
Divide-and-Conquer
·
General Issues
in Divide-And Conquer
·
Integer Multiplication
·
Binary Search
·
Sorting
·
Finding the
Median
·
Matrix Multiplication
·
Exponentiation
Unit 2:
Graphs Algorithms
·
Examples
·
Traversing Trees
·
Depth-First
Search
·
Breadth-First
Search
·
Best-First Search
& Minimax Principle
·
Topological
Sort
BLOCK 3
Design Techniques - II
Unit 1
Dynamic Programming
·
The Problem
of Making Change
·
The Principle
of Optimality
·
Chained Matrix
Multiplication
·
Matrix Multiplication
Using Dynamic
Programming
Unit 2
Greedy Algorithms
·
Some Examples
·
Formalization
of Greedy Technique
·
Minimum Spanning
Trees
·
Prim’s Algorithm
·
Kruskal’s Algorithm
·
Dijkstra’s Algorithm
Unit 3
Models for Executing Algorithms –I: FA
·
Regular Expressions
·
Regular Languages
·
Finate Automata
Unit 4 Models for Executing Algorithms
–II
PDFA & CFG
·
Formal Language & Grammer
·
Context Free Grammer(CFG)
·
Pushdown Automata (PDA)
BLOCK 4
Complexity & Completeness
Unit 1:
Models for Executing Algorithms – III :TM
·
Prelude to Formal Definition
·
Turing Machine: Formal Definition and Examples
·
Instantaneous Description and Transition Diagram
·
Some Formal Definitions
·
Observations
·
Turing Machine as a Computer of Functions
Unit 2
Algorithmically Unsolvable Problems
·
Decidable And
Undecidable Problems
·
The Halting
Problem
·
Reduction to
Another Undecidable Problem
·
Undecidable
Problems for CFL
·
Other Undecidable
Problems
Unit 3 Complexity of Algorithms
·
Notations for the Growth Rates of
Functions