Govt.

Engineering College, Sreekrishnapuram

Mannampatta P.O, Sreekrishnapuram, Palakkad-678633
Phone: 04662260350, [email protected]

Computer
Department : Science& Batch : 2K21 2021-2023 Semester : IInd Semester
Engineering

Subject Plan of 08CS6122 - Algorithms and Complexity

Topic Name Date Hour Module Slot Teaching Pedagogy

Amortized analysis -
Wed, 6th April 2022 1 1 1 Lecture
introduction

Aggregate method Mon, 11th April 2022 3 1 2 Lecture

Potential method Tue, 12th April 2022 2 1 3 Lecture

Advanced Data Structures:

Wed, 13th April 2022 1 1 4 Lecture
B-Trees

Advanced Data Structures:

Mon, 18th April 2022 3 1 5 Lecture
B-Trees

Fibonacci heaps Tue, 19th April 2022 2 1 6 Lecture

Fibonacci heaps Wed, 20th April 2022 1 1 7 Lecture

Disjoint sets-applications Mon, 25th April 2022 3 1 8 Lecture

GCD algorithm Tue, 26th April 2022 2 2 9 Lecture

GCD algorithm Wed, 27th April 2022 1 2 10 Lecture

Extended Euclid’s
Mon, 2nd May 2022 3 2 11 Lecture
algorithm

Primality testing - Miller-

Tue, 3rd May 2022 2 2 12 Lecture
Rabin test

Primality testing - Miller-

Wed, 4th May 2022 1 2 13 Lecture
Rabin test

Integer factorization -
Mon, 9th May 2022 3 2 14 Lecture
Pollard Rho heuristic

Flow properties Tue, 10th May 2022 2 3 15 Lecture

Ford-Fulkerson method Wed, 11th May 2022 1 3 16 Lecture

Ford-Fulkerson method Mon, 16th May 2022 3 3 17 Lecture

Series Test I Tue, 17th May 2022 2 2 18 Lecture

Maxflow-Mincut theorem Wed, 18th May 2022 1 3 19 Lecture

Maxflow-Mincut theorem Mon, 23rd May 2022 3 3 20 Lecture

Edmonds-Karp heuristics Tue, 24th May 2022 2 3 21 Lecture

Maximum bipartite
Wed, 25th May 2022 1 3 22 Lecture
matching

Rabin-Karp algorithm Mon, 30th May 2022 3 4 23 Lecture

Knuth-Morris-Pratt
Tue, 31st May 2022 2 4 24 Lecture
algorithm

Overview of complexity
Wed, 1st June 2022 1 4 25 Lecture
classes

NP completeness proofs:
Mon, 6th June 2022 3 4 26 Lecture
Clique

NP completeness proofs:
Tue, 7th June 2022 2 4 27 Lecture
vertex-cover problem.

NP completeness proofs:
Wed, 8th June 2022 1 4 28 Lecture
Hamiltonian-cycle

NP completeness proofs:
Travelling-salesman Mon, 13th June 2022 3 4 29 Lecture
problem

Polynomial time
Tue, 14th June 2022 2 5 30 Lecture
approximation scheme

1
 Topic Name Date Hour Module Slot Teaching Pedagogy

Polynomial time
Wed, 15th June 2022 1 5 31 Lecture
approximation scheme

Fully polynomial time

Mon, 20th June 2022 3 5 32 Lecture
approximation scheme

Vertex-cover problem Tue, 21st June 2022 2 5 33 Lecture

Series Test II Wed, 22nd June 2022 1 4 34 Lecture

Traveling-salesman
Mon, 27th June 2022 3 5 35 Lecture
problem

Set covering Problem Tue, 28th June 2022 2 5 36 Lecture

Permuting arrays Wed, 29th June 2022 1 6 37 Lecture

Birthday paradox Mon, 4th July 2022 3 6 38 Lecture

Balls and bins Tue, 5th July 2022 2 6 39 Lecture

Online hiring problem,

Wed, 6th July 2022 1 6 40 Lecture
fingerprinting, counting

Online hiring problem,

Mon, 11th July 2022 3 6 41 Lecture
fingerprinting, counting

Quicksort Tue, 12th July 2022 2 6 42 Lecture