VTU Notes

# The Complete 18CS42 | Design and Analysis of Algorithms. Notes

• 4.9
• 2018 Scheme | CSE Department ### Description

Important Topics Covered

What is an Algorithm? Algorithm Specification, Analysis Framework. Performance Analysis such as Space complexity, Time complexity. Asymptotic Notations such as Big-Oh notation (O), Omega notation (?), Theta notation (?), and Little-oh notation (o).

Mathematical analysis of Non-Recursive and recursive Algorithms with Examples. Important Problem Types: Sorting, Searching, String processing, Graph Problems, Combinatorial Problems. Fundamental Data Structures, Stacks, Queues, Graphs, Trees, Sets, and Dictionaries.

Divide and Conquer,  A general method, Binary search, Recurrence equation for divide and conquer, Finding the maximum and minimum. Merge sort, Quicksort, Strassen’s matrix multiplication. Advantages and Disadvantages of divide and conquer.

Greedy Method:General method, Coin Change Problem, Knapsack Problem, Job sequencing with deadlines. Optimal Tree problem and Transform and Conquer Approach.

The general method with Examples, Multistage Graphs of Dynamic Programming. Floyd’s Algorithm, Optimal Binary Search Trees, Knapsack problem. Backtracking, Branch and Bound, and NP-Complete and NP-Hard problems.

### Module 1

Introduction:
What is an Algorithm? (T2:1.1), Algorithm Specification (T2:1.2), Analysis Framework (T1:2.1), Performance Analysis: Space complexity, Time complexity (T2:1.3). Asymptotic Notations: Big-Oh notation (O), Omega notation (?), Theta notation (?), and Little-oh notation (o), Mathematical analysis of Non-Recursive and recursive Algorithms with Examples (T1:2.2, 2.3, 2.4). Important Problem Types: Sorting, Searching, String processing, Graph Problems, Combinatorial Problems. Fundamental Data Structures: Stacks, Queues, Graphs, Trees, Sets and Dictionaries. (T1:1.3,1.4).

### Module 2

Divide and Conquer:
A general method, Binary search, Recurrence equation for divide and conquer, Finding the maximum and minimum (T2:3.1, 3.3, 3.4), Merge sort, Quicksort (T1:4.1, 4.2), Strassen’s matrix multiplication (T2:3.8), Advantages and Disadvantages of divide and conquer.
Decrease and Conquer Approach: Topological Sort. (T1:5.3).

### Module 3

Greedy Method:General method, Coin Change Problem, Knapsack Problem, Job sequencing with deadlines (T2:4.1, 4.3, 4.5).
Minimum cost spanning trees: Prim’s Algorithm, Kruskal’s Algorithm (T1:9.1, 9.2).
Single source shortest paths: Dijkstra's Algorithm (T1:9.3).
Optimal Tree problem: Huffman Trees and Codes (T1:9.4).
Transform and Conquer Approach: Heaps and Heap Sort (T1:6.4).

### Module 4

Dynamic Programming: General method with Examples, Multistage Graphs (T2:5.1, 5.2).
Transitive Closure: Warshall’s Algorithm, All Pairs Shortest Paths: Floyd's Algorithm, Optimal Binary Search Trees, Knapsack problem ((T1:8.2, 8.3, 8.4), Bellman-Ford Algorithm (T2:5.4), Travelling Sales Person problem (T2:5.9), Reliability design (T2:5.8).

### Module 5

Backtracking: General method (T2:7.1), N-Queens problem (T1:12.1), Sum of subsets problem (T1:12.1), Graph coloring (T2:7.4), Hamiltonian cycles (T2:7.5). Branch and Bound: Assignment Problem, Travelling Sales Person problem (T1:12.2), 0/1 Knapsack problem (T2:8.2, T1:12.2): LC Branch and Bound solution (T2:8.2), FIFO Branch and
Bound solution (T2:8.2). NP-Complete and NP-Hard problems: Basic concepts, non-deterministic algorithms, P, NP, NP-Complete, and NP-Hard classes (T2:11.1).

### Announcement 