Design and Analysis of Algorithms - CS8451, CS6402

INTRODUCTION

BRUTE FORCE AND DIVIDE

DYNAMIC PROGRAMMING AND GREEDY TECHNIQUE

ITERATIVE IMPROVEMENT

COPING WITH THE LIMITATIONS OF ALGORITHM POWER

Introduction to The Design and Analysis of Algorithms by Anany Levitin

Chapter 1 : Introduction

=> Introduction to the Design and Analysis of Algorithms
=> What Is an Algorithm?
=> Fundamentals of Algorithmic Problem Solving
=> Ascertaining the Capabilities of the Computational Device
=> Algorithm Design Techniques
=> Designing an Algorithm and Data Structures
=> Methods of Specifying an Algorithm
=> Proving an Algorithm’s Correctness
=> Analyzing an Algorithm
=> Coding an Algorithm
=> Important Problem Types in Algorithms Analysis
=> Fundamental Data Structures

Chapter 2 : Fundamentals of the Analysis of Algorithm Eficiency

=> The Analysis Framework
=> Asymptotic Notations and Basic Efficiency Classes
=> Mathematical Analysis of Non recursive Algorithms
=> Mathematical Analysis of Recursive Algorithms
=> Example: Computing the nth Fibonacci Number
=> Empirical Analysis of Algorithms
=> Algorithm Visualization

Chapter 3 : Brute Force and Exhaustive Search

=> Brute Force and Exhaustive Search
=> Selection Sort and Bubble Sort
=> Sequential Search and Brute-Force String Matching
=> Closest-Pair and Convex-Hull Problems by Brute Force
=> Exhaustive Search
=> Depth-First Search and Breadth-First Search

Chapter 4 : Decrease and Conquer

=> Decrease and Conquer
=> Insertion Sort
=> Topological Sorting
=> Algorithms for Generating Combinatorial Objects
=> Decrease by a Constant Factor Algorithms
=> Variable Size Decrease Algorithms

Chapter 5 : Divide and Conquer

=> Divide and Conquer
=> Mergesort
=> Quicksort
=> Binary Tree Traversals and Related Properties
=> Multiplication of Large Integers
=> Strassen’s Matrix Multiplication
=> The Closest Pair Problem by Divide and Conquer
=> Convex Hull Problems by Divide and Conquer

Chapter 6 : Transform and Conquer

=> Transform and Conquer
=> Presorting
=> Gaussian Elimination
=> Balanced Search Trees: AVL Trees and 2-3 Trees
=> Heaps and Heapsort
=> Horner’s Rule and Binary Exponentiation
=> Problem Reduction

Chapter 7 : Space and Time Trade Offs

=> Space and Time Trade-Offs
=> Sorting by Counting
=> Input Enhancement in String Matching: Horspool’s and Boyer-Moore Algorithm
=> Open and Closed Hashing
=> B-Trees Algorithms

Chapter 8 : Dynamic Programming

=> Dynamic Programming
=> Dynamic Programming: Three Basic Examples
=> The Knapsack Problem and Memory Functions
=> Optimal Binary Search Trees
=> Warshall’s and Floyd’s Algorithms

Chapter 9 : Greedy Technique

=> Greedy Technique
=> Prim’s Algorithm
=> Kruskal’s Algorithm
=> Dijkstra’s Algorithm
=> Huffman Trees and Codes

Chapter 10 : Iterative Improvement

=> Iterative Improvement
=> The Simplex Method
=> The Iterative Maximum-Flow Problem
=> Maximum Matching in Bipartite Graphs
=> The Stable Marriage Problem

Chapter 11 : Limitations of Algorithm Power

=> Limitations of Algorithm Power
=> Lower-Bound Arguments
=> Decision Trees algorithms
=> P , NP , and NP-Complete Problems
=> Challenges of Numerical Algorithms

Chapter 12 : Coping with the Limitations of Algorithm Power

=> Coping with the Limitations of Algorithm Power
=> Backtracking
=> Branch-and-Bound
=> Approximation Algorithms for NP -Hard Problems
=> Approximation Algorithms for the Traveling Salesman Problem
=> Approximation Algorithms for the Knapsack Problem
=> Algorithms for Solving Nonlinear Equations