# Design and Analysis of Algorithms (DAA) – Micro Syllabus

0
473

## Foundation of Algorithm Analysis

### Algorith and its properties

RAM Model

Time and Space Complexity

Detail Analysis of Algorithm (Like Factorial Algorithm)

Concept of Aggregate Analysis

### Asymptotic Notation

Big Oh, Big Omega and Big Theta Notation, Their Geometrical Interpretation and examples

### Recurrences

Recursive algorithm and recursive relations

Solving Recurrences

• Recursion Tree Method,
• Substitution Method,
• Application of Masters Theorem

Taking too long?

| Open in new tab

## ITERATIVE ALGORITHMS

### Searching Algorithms

Sequential Search and its analysis

### Sorting Algorithms

Bubble, Selection, and Insertion Sort  and its analysis

## DIVIDE AND CONQUER ALGORITHMS

### Searching Algorithms

Binary Search, Min-Max Finding and their Analysis

### Sorting Algorithms

Merge Sort and Analysis, Quick Sort and Analysis (Best Case, Worst Case and Average Case). Heap Sort (Heapify, Build Heap and Heap Sort Algorithms and their Analysis)

### Online Algorithms

Introduction, Ski Problem, Load Falancmg Paging and Caching: Last-in First-out (LIFO). Longest Forward Distance (LFD), Least Recently Used (LRUY)

## GREEDY ALGORITHMS

### Optimization Problems and Optimal Solution:

Introduction of Greedy Algorithms, Elements of Greedy Strategy

### Fractional Knapsack

Job sequencing with Deadlines, Kruskal’s Algorithm, Prims Algorithm, Dijkstra’s Algorithm and their Analysis

### Huffman Coding

Purpose of Huffman Coding. Prefix Codes Huffman Coding Algorithm and its Analysis

## DYNAMIC PROGRAMMING

### Greedy Algorithm vs Dynamic Programming

Recursion vs Dynamic Programming, Elements of DP Strategy

### DP Algorithms

Matrix Chain Multiplication, String Editing, zero one knapsack Problem, Floyd Warshwalll Algorithm, Travelling Salesman Problem and their Analysis

### Memoization  Strategy

Dynamic Programming  Vs Memoization

## BACK TRACKING

### Concept of Backtracking

Recursion vs Backtracking

### Backtracking Algorithms

Subset-sum Problem, Zero-one Knapsack Problem. N-queen Problem and their Analysis

## PARALLEL ALGORITHMS

Semantics of concurrent programming (Axiomatic, Denotational, Operational)

### PRAM models

PRAM Algorithms (Computing prefix sum,Parallel sorting algorithm)

### BSR algorithms

n – criterion algorithm (Sorting, Parenthesis matching, optimall sum sub segment)

### Parallel graph algorithms

Tree graph algorithm, (Computing post order numbering, computing the number of descendants, level computation, Lowest Common Ancestor computation