•   Visitors:

### Course Overview

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

#### 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

#### 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
Best-First Search & Minimax Principle
Topological Sort

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 3 : 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 Function

Course Enquiry