Design and Analysis of Algorithms 21CS42
Course Code: 21CS42
Credits: 04
CIE Marks: 50
SEE Marks: 50
Total Marks: 100
Exam Hours: 03
Total Hours of Pedagogy: 40P + 20P
Teaching Hours/Weeks: [L:T:P:S] 3:0:2:0
Introduction: What is an Algorithm? It’s Properties. Algorithm Specification-using natural language, using Pseudo code convention, Fundamentals of Algorithmic Problem solving, Analysis Framework Time efficiency and space efficiency, Worst-case, Best-case and Average case efficiency.
Performance Analysis: Estimating Space complexity and Time complexity of algorithms.
Asymptotic Notations: Big-Oh notation (O), Omega notation (Ω), Theta notation ( ) with examples, Basic efficiency classes, Mathematical analysis of Non-Recursive and Recursive Algorithms with Examples.
Brute force design technique: Selection sort, sequential search, string matching algorithm with complexity Analysis.
MODULE-2
Divide and Conquer: General method, Recurrence equation for divide and conquer, solving it using Master’s theorem. , Divide and Conquer algorithms and complexity Analysis of Finding the maximum & minimum, Binary search, Merge sort, Quick sort.
Decrease and Conquer Approach: Introduction, Insertion sort, Graph searching algorithms, Topological Sorting. It’s efficiency analysis.
MODULE-3
Greedy Method: General method, Coin Change Problem, Knapsack Problem, solving Job sequencing with deadlines Problems.
Minimum cost spanning trees: Prim’s Algorithm, Kruskal’s Algorithm with performance analysis.
Single source shortest paths: Dijkstra’s Algorithm.
Optimal Tree problem: Huffman Trees and Codes.
Transform and Conquer Approach: Introduction, Heaps and Heap Sort.
MODULE-4
Dynamic Programming: General method with Examples, Multistage Graphs.
Transitive Closure: Warshall’s Algorithm.
All Pairs Shortest Paths: Floyd’s Algorithm, Knapsack problem, Bellman-Ford Algorithm, Travelling Sales Person problem.
Space-Time Tradeoffs: Introduction, Sorting by Counting, Input Enhancement in String Matching Harspool’s algorithm.
MODULE-5
Backtracking: General method, solution using back tracking to N-Queens problem, Sum of subsets problem, Graph coloring, Hamiltonian cycles Problems.
Branch and Bound: Assignment Problem, Travelling Sales Person problem, 0/1 Knapsack problem.
NP-Complete and NP-Hard problems: Basic concepts, non- deterministic algorithms, P, NP, NP-Complete, and NP-Hard classes.