HomeCSE-4TH SEM DAA(MOD1-MOD5) //// CSE-4th SEM- DAA (Design and Analysis of Algorithms)-18CS42

# Design and Analysis of Algorithms NOTES for CS 4 Sem 2018 scheme | VTU CBCS (18CS42 )

ALL MODULE 1-MODULE 5 NOTES DOWN BELOW
(SCROLL DOWN )
ALL NOTES ARE CONTRIBUTED BY SUDARSHAN REDDY
ALL ppts/PDF NOTES CONTRIBUTED BY
SNEHA REDDY
###### Module-1Introduction10 hours

Introduction:

What is an Algorithm?

Asymptotic Notations:

Big-Oh notation (O), Omega notation (â„¦),

Fundamental Data Structures:

Stacks, Queues, Graphs, Trees, Sets and Dictionaries.

###### Module-2Divide and Conquer10 hours

Divide and Conquer:

General method, Binary search, Recurrence equation for divide and conquer, Finding the maximum and ,……

Decrease and Conquer Approach:

Topological Sort. (T1:5.3).

###### Module-3Greedy Method10 hours

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-4Dynamic Programming10 hours

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-5Backtracking10 hours

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).

Programme and Bound:

Assignment Problem, Travelling Sales Person problem (T1:12.2),

0/1 Knapsack problem (T2:8.2, T1:12.2):

LC Programme and Bound solution (T2:8.2), FIFO Programme 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). RBT: L1, L2, L3

RELATED ARTICLES