[go: up one dir, main page]
Scribd
Upload
147 views44 pages

Daa Unit-1

The document outlines the syllabus for the course "Design and Analysis of Algorithms" at Rohini College of Engineering and Technology. It introduces the key topics that will be covered in the 5 units of the course, including introduction to algorithms, brute force and divide-and-conquer techniques, dynamic programming and greedy techniques, iterative improvement methods, and dealing with computationally intractable problems. The syllabus provides an overview of the major algorithmic paradigms and problems that will be studied over the course.

Uploaded by

passion job
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
147 views44 pages

Daa Unit-1

The document outlines the syllabus for the course "Design and Analysis of Algorithms" at Rohini College of Engineering and Technology. It introduces the key topics that will be covered in the 5 units of the course, including introduction to algorithms, brute force and divide-and-conquer techniques, dynamic programming and greedy techniques, iterative improvement methods, and dealing with computationally intractable problems. The syllabus provides an overview of the major algorithmic paradigms and problems that will be studied over the course.

Uploaded by

passion job
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 44

ROHINI

COLLEGE OF ENGINEERING AND TECHNOLOGY


Approved by AICTE and affiliated to Anna University, (An ISO Certified Institution)

DEPARTMENT OF COMPUTER SCIENCE


AND ENGINEERING

NAME OF THE SUBJECT : DESIGN AND ANALYSIS


OF ALGORITHM
SUBJECT CODE : CS8451
REGULATION : 2017

UNIT-1
INTRODUCTION
SYLLABUS

CS8451 DESIGN AND ANALYSIS OF ALGORITHM

UNIT I INTRODUCTION

Notion of an Algorithm – Fundamentals of Algorithmic Problem Solving – Important Problem Types –


Fundamentals of the Analysis of Algorithmic Efficiency –Asymptotic Notations and their properties. Analysis
Framework – Empirical analysis – Mathematical analysis for Recursive and Non-recursive algorithms –
Visualization

UNIT II BRUTE FORCE AND DIVIDE-AND-CONQUER

Brute Force – Computing an – String Matching – Closest-Pair and Convex-Hull Problems – Exhaustive Search –
Travelling Salesman Problem – Knapsack Problem – Assignment problem. Divide and Conquer Methodology –
Binary Search – Merge sort – Quick sort – Heap Sort – Multiplication of Large Integers – Closest-Pair and Convex
– Hull Problems.

UNIT III DYNAMIC PROGRAMMING AND GREEDY TECHNIQUE

Dynamic programming – Principle of optimality – Coin changing problem, Computing a Binomial Coefficient –
Floyd‘s algorithm – Multi stage graph – Optimal Binary Search Trees – Knapsack Problem and Memory functions.
Greedy Technique – Container loading problem – Prim‘s algorithm and Kruskal’s Algorithm – 0/1 Knapsack
problem, Optimal Merge pattern – Huffman Trees.

UNIT IV ITERATIVE IMPROVEMENT

The Simplex Method – The Maximum-Flow Problem – Maximum Matching in Bipartite Graphs, Stable marriage
Problem.

UNIT V COPING WITH THE LIMITATIONS OF ALGORITHM POWER

Lower – Bound Arguments – P, NP NP- Complete and NP Hard Problems. Backtracking – n-Queen problem
Hamiltonian Circuit Problem – Subset Sum Problem. Branch and Bound – LIFO Search and FIFO search –
Assignment problem – Knapsack Problem – Travelling Salesman Problem – Approximation Algorithms for NP-
Hard Problems – Travelling Salesman problem – Knapsack problem.
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner

You might also like