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


Recursive algorithm and recursive relations

Solving Recurrences

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

Download Handwritten Notes of Unit 1

Loader Loading…
EAD Logo Taking too long?

Reload Reload document
| Open Open in new tab

Download [4.65 MB]


Searching Algorithms

Sequential Search and its analysis 

Sorting Algorithms

Bubble, Selection, and Insertion Sort  and its analysis 


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)


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


  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


Concept of Backtracking

Recursion vs Backtracking 

Backtracking Algorithms

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


Parallel processing paradigms:

 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

Facebook Comments