Design and Analysis of Algorithms

Master the fundamental concepts of algorithms, understand their characteristics, learn to analyze time and space complexity, and explore basic sorting algorithms with asymptotic notations.

Key Topics:

• Definition and Characteristics of Algorithm
• Properties of a Good Algorithm
• Pseudo Code and Flowcharts
• Time Complexity of Basic Control Structures
• Space Complexity Analysis
• Best Case, Worst Case, and Average Case Analysis
• Insertion Sort – Algorithm and Time Complexity
• Selection Sort – Algorithm and Time Complexity
• Heap Sort – Algorithm and Time Complexity
• Bubble Sort – Algorithm and Time Complexity
• Asymptotic Notations – Big O, Omega, and Theta
• Growth of Functions
• Comparing Algorithm Efficiency

Learn the Divide and Conquer paradigm with algorithms like Binary Search, Merge Sort, and Quick Sort, and explore the Greedy Method approach to solve optimization problems efficiently.

Key Topics:

• Divide and Conquer – General Method and Strategy
• Binary Search Algorithm
• Finding Maximum and Minimum Elements
• Merge Sort – Algorithm and Analysis
• Quick Sort – Algorithm and Analysis
• Strassen's Matrix Multiplication
• Greedy Method – General Approach
• Knapsack Problem (Fractional Knapsack)
• Travelling Salesman Problem
• Job Sequencing with Deadlines
• Optimal Storage on Tapes
• Huffman Codes and Data Compression
• Activity Selection Problem

Understand Dynamic Programming for solving overlapping subproblems and optimal substructure problems, and learn Backtracking technique for constraint satisfaction problems.

Key Topics:

• Dynamic Programming – General Method and Principles
• Assembly Line Scheduling Problem
• Matrix Chain Multiplication
• Longest Common Subsequence (LCS)
• Optimal Substructure Property
• Overlapping Subproblems
• Memoization vs Tabulation
• Backtracking – General Method
• N Queens Problem
• Sum of Subsets Problem
• Hamiltonian Circuit Problem
• State Space Tree
• Bounding Functions in Backtracking

Explore Branch and Bound technique for optimization problems and master fundamental graph algorithms including shortest path, minimum spanning tree, and multistage graphs.

Key Topics:

• Branch and Bound – Introduction and Strategy
• Live Node, Dead Node, and E-Node
• Bounding Functions
• 0/1 Knapsack Problem using Branch & Bound
• Assignment Problem
• Elementary Graph Algorithms
• Graph Representation – Adjacency Matrix and List
• Breadth-First Search (BFS)
• Depth-First Search (DFS)
• Multistage Graphs
• Minimum Spanning Trees – Kruskal's Algorithm
• Minimum Spanning Trees – Prim's Algorithm
• Single Source Shortest Path – Dijkstra's Algorithm
• Single Source Shortest Path – Bellman-Ford Algorithm
• All Pairs Shortest Path – Floyd-Warshall Algorithm