📘 AM501PC

Design and Analysis of Algorithms

Access study materials and notes for this subject

DAA Unit 1: Introduction and Divide and Conquer

PDF Document

PreviewDownload

DAA Unit 2: Disjoint Sets And Priority Queue

PDF Document

PreviewDownload

DAA Unit 3: Dynamic Programming

PDF Document

PreviewDownload

DAA Unit 4: Greedy Method, Basic Traversal and Search Techniques

PDF Document

PreviewDownload

DAA Unit 5: Branch And Bound, Np-hard And Np-complete Problems

PDF Document

PreviewDownload

DAA Unit 1 (alt): Introduction and Divide and Conquer

PDF Document

PreviewDownload

DAA Unit 1 (alt OBS): Introduction and Divide and Conquer

PDF Document

PreviewDownload

DAA Unit 2 (alt): Disjoint Sets And Priority Queue

PDF Document

PreviewDownload

DAA Unit 3 (alt): Dynamic Programming

PDF Document

PreviewDownload

DAA Unit 1: Assignment

PDF Document

PreviewDownload

Syllabus Overview

UNIT - 1: Introduction and Divide and Conquer

Introduction

  • Algorithm
  • Performance Analysis: Space complexity, Time complexity
  • Asymptotic Notations: Big Oh notation, Omega notation, Theta notation, Little Oh notation

Divide and Conquer

  • General method
  • Applications: Binary search, Quick sort, Merge sort, Strassen’s matrix multiplication

UNIT - 2: Disjoint Sets and Priority Queue

Disjoint Sets

  • Disjoint set operations
  • Union and find algorithms

Priority Queue

  • Heaps
  • Heapsort

Backtracking

  • General method
  • Applications: n-queen’s problem, Sum of subsets problem, Graph coloring, Hamiltonian cycles

UNIT - 3: Dynamic Programming

Dynamic Programming

  • General method
  • Applications: Optimal binary search tree, 0/1 knapsack problem, All pairs shortest path problem, Traveling salesperson problem, Reliability design

UNIT - 4: Greedy Method, Basic Traversal and Search Techniques

Greedy Method

  • General method
  • Applications: Job sequencing with deadlines, Knapsack problem, Minimum cost spanning trees, Single source shortest path problem

Basic Traversal and Search Techniques

  • Techniques for Binary Trees
  • Techniques for Graphs: Connected components, Biconnected components

UNIT - 5: Branch and Bound, NP-Hard and NP-Complete Problems

Branch and Bound

  • General method
  • Applications: Traveling salesperson problem, 0/1 knapsack problem: LC Branch and Bound solution, FIFO Branch and Bound solution

NP-Hard and NP-Complete Problems

  • Basic concepts
  • Non-deterministic algorithms
  • NP-Hard and NP-Complete classes
  • Cook’s theorem
Design and Analysis of Algorithms Notes