DAA
Unit 1
Basics of Algorithms and Mathematics
- What is an algorithm?
- Mathematics for Algorithmic Sets
- Functions and Relations
- Vectors and Matrices
- Linear Inequalities and Linear Equations
Analysis of Algorithm
- The efficient algorithm
- Best, Average and Worst case analysis
- Elementary operation
- Asymptotic Notation
- Analyzing control statement
- Amortized analysis
- Sorting Algorithm
- Binary Tree Search
Unit 2
Divide and Conquer Algorithm
- Introduction
- Multiplying large Integers Problem
- Problem Solving using divide and conquer algorithm - Binary Search
- Sorting (Merge Sort, Quick Sort)
- Matrix Multiplication
- Exponential
Greedy Algorithm
- General Characteristics of greedy algorithms
- Problem solving using Greedy Algorithm - Activity selection problem
- Elements of Greedy Strategy
- Minimum Spanning trees (Kruskal’s algorithm, Prim’s algorithm)
- Graphs: Shortest paths
- The Knapsack Problem
- Job Scheduling Problem
Unit 3
Dynamic Programming
- Introduction
- The Principle of Optimality
- Problem Solving using Dynamic Programming – Calculating the Binomial Coefficient
- Making Change Problem
- Assembly Line-Scheduling
- Knapsack problem
- Shortest path
- Matrix chain multiplication
- Longest Common Subsequence
Exploring Graphs
- An introduction using graphs and games
- Undirected Graph
- Directed Graph
- Depth First Search
- Breath First Search
- Backtracking and Branch & Bound– The Knapsack Problem
- The Eight Queens problem
Unit 4
String Matching
- Introduction
- The naive string matching algorithm
- The Rabin-Karp algorithm
- String Matching with finite automata
Introduction to NP-Completeness
- The class P and NP
- Polynomial reduction
- NP- Completeness Problem
- NP-Hard Problems