Syllabus Algorithms - (CS25C12) Foundations of Algorithm Analysis : Performance analysis-space complexity, time complexity, asymptotic notation - big (O) notation, omega notation, theta notation and little (o) notation, recurrences, probabilistic analysis. (Chapter - 1) Activities : • Assignment o Time and Space Complexity calculation for a given Logic o Usage of loops and conditionals and mathematical principles. Divide & Conquer Methods : Merge sort, Long Integer Multiplication, Strassen’s matrix multiplication, Master method, Job Sequencing Problem with Deadlines. (Chapter - 2) Activities : • Flipped Class Room : Solving a puzzle. • Review of GATE Questions. Greedy Methods and Dynamic Programming : Activity Selection Problem, Huffman Codes and Knapsack fractional. Dynamic Programming Method : Knapsack 0 – 1, Matrix Chain Multiplication, Optimal Binary Search Tree and Longest Common Subsequence. (Chapter - 3) Activities : • Project based experiential learning : Creation of treasure hunt. • Quiz : State Transition and Recurrence Relations - Space Optimization Technique String Matching and Convex Hull Algorithms : Multithreaded algorithms, Polynomial Multiplication, Fast Fourier Transform, Extended Euclid Algorithm. Naïve’s algorithm, Rabin Karp algorithm - Graham’s Scan and Jarvi’s March method. (Chapter - 4) Activities : • Assignment : Rabin Karp algorithm • Quiz : Multithreaded and Euclid algorithms. Solvability And Tractability : The classes P and NP, NP Hard and NP Complete Problems. vertex-cover, travelling-salesman, set-covering, subset-sum Problem - N Queen Problem, Graph Coloring, Hamiltonian Cycle Problem - Assignment Problem, Travelling Salesman and Knapsack Problem. (Chapter - 5) Activities : • Assignment : Approximation and randomized Algorithms • Review of GATE Questions. Network Flow Algorithms : Flow Networks, Maximum Flows : Ford-Fulkerson, Edmond-Karp, Push relabel Algorithm, Relabel-to-front algorithm, Minimum Cost flows, Cycle Cancelling Algorithm. (Chapter - 6) Activities : • Flipped Class Room : Relabel Algorithm • Review of GATE Questions.