Algorithms

CS25C12:

Algorithms

Course Objectives: This course aims at providing the fundamentals of algorithm design and analysis and explains the concepts greedy method and dynamic programming. Also, this course illustrates the methods of backtracking and branch bound techniques to solve the problems.

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.

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

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.

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. Naive’s algorithm, Rabin Karp algorithm - Graham’s Scan and Jarvi’s March method.

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.

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.

Activities:

• Flipped Class Room: Relabel Algorithm

• Review of GATE Questions.

Assessment Weightage:

Weightage:

Continuous Assessment: 40%

(i) .Activities: 30%

(ii) .Internal Examinations – 70%

End Semester Theory Examination: 60%

Mandated Activities with marks:

Assignments (30), Quiz (10), Project based learning (25), Flipped Classroom (10), Review of GATE questions (25).

Internal Examinations: TWO tests

References

1. Anany Levitin, “Introduction to the Design and Analysis of Algorithms”, Third Edition, Pearson Education, 2014.

2. Ellis Horowitz, Sartaj Sahni and Sanguthevar Rajasekaran, “Computer Algorithms/ C++”, Second Edition, Universities Press, 2007.

3. Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and CliffordStein. “Introduction to algorithms”. MIT press, 2022.