COURSE SYLLABUS

Course Code / Course Name Approximation Algorithms

Course Instructor Name(s) Muralidhara V N / Pradeesha Ashok
Hours Component
3 L
Credits (L:T:P)
2 T
(Lecture : Tutorial : Practical)
0 P
L:T:P = Total Credits = 4
Grading Scheme 4-point scale (A,A-,B+,B,B-,C+,C,D,F)
(Choose by placing X against
appropriate box) Satisfactory/Unsatisfactory (S / X)
Area of Specialization (if applicable)
(Choose by placing X in box against not more than two areas from the list)
Theory and Systems f or Computing Networking and
X
and Data Communication
Artif icial Intelligence and Machine Digital Society
Learning
VLSI Systems Cyber Security
General Elective

Programme / Branch Course is restricted to the f ollowing programmes / branch(es):

(Place X appropriately. More than one is okay)
Programme: Branch:
X iMTech
X M.Tech
M.Sc.
X CSE
ECE
Digital Society
Course Category Select one f rom the f ollowing:
(Place X appropriately)
Basic Sciences
CSE Core
ECE Core
X CSE Branch Elective
ECE Branch Elective
Engineering Science and Skills
HSS/M
General
Course Pre-Requisites CSE 511 Algorithms or equivalent (Where applicable, state exact course
code/name)

Additional Focus Areas

Select zero or more from the following and write one sentence explaining the focus areas covered as part of the
course.[NAAC criteria 1.1.3, 1.3.2].

Yes /
Focus Area Details
No
Direct focus on employability Yes Problem Solving Skills
Focus on skill development Yes Problem Solving Skills
Focus on entrepreneurship
Provides value added / life skills Yes Problems Solving Skills
(language, writing, communication, etc.)

Course Context and Overview

[Provide introduction to the course ]

The field of approximation algorithms has been developed in response to

the difficulty in solving a good many optimization problems exactly. The goal
here is to design efficient (polynomial-time) algorithms that nearly optimal
(approximate) solutions, and have provable guarantees (both in terms of
performance as well as on the near optimality). The main focus of the course is
problem solving, design and analysis efficient approximation algorithms.

Course Outcomes and Competencies

[Course Outcomes are to be stated using appropriate terminology and taxonomy as required by NAAC
and/or NBA. For every course credit, about 2-3 outcomes are recommended. ]

PO/ Class Lab

Id Course Outcome CL KC
PSO (Hrs) (Hrs)
CO1 Define approximation algorithms. PSO4, U C 3
PO2

CO2 Understand and apply Greedy Algorithms, PO4 An, C, 12

Ap P
Dynamic Programming, Local search, rounding
techniques to design and analyze
approximation algorithms.
CO3 Understand and apply randomized methods, LP PO4/P An, C, 12
SO4 Ap P
techniques, primal-dual method, Lagrangian
methods, metric methods, inapproximability.

CO4 Evaluate the techniques used to design PO4,P E C 18

SO4
efficient approximation algorithms for few real
life problems.
 45

Legend: PO/PSO: Programme Outcomes / Programme Specific Outcomes; CL: Cognitive Level (from Revised
Bloom’s Taxonomy); KC: Knowledge Category (from Revised Bloom’s Taxonomy); Class (Hrs): Number of hours
of instruction; Tut (Hrs): Number of hours of tutorial session (where applicable)

Concept Map of the Course (Optional)

Course Content
[Provide list-wise topics]

There are several problems, that arise in computer science and have applications in
various fields which are NP-hard, which means that optimal solutions
to these problems cannot be computed in polynomial-time unless P equal NP.
There are no practical techniques known to compute the optimum solutions
to for most of these problems. This course is on the design of polynomial-
time approximation (near optimal) algorithms for such problems.
The course will study some of the successful paradigms for designing
approximation algorithms and for proving approximation guarantees.

The techniques that will be covered in the course are: Greedy Algorithms,
Dynamic Programming, Local search, randomized methods, LP techniques,
primal-dual method, Lagrangian methods, metric methods, inapproximability.

The problems that will be covered in the course include Set cover, Vertex
cover,Knapsack, Bin packing, Max Cut, TSP, Scheduling, Facility location,
Steiner tree and other network design problems, Sparsest cut, multi-cut and
other partitioning problems.

Instruction Schedule
[Provide session-wise schedule]

1. Introduction to approximation algorithms

2. Set Cover , TSP, Cut .
 3. Knapsack, Bin Packing and Makespan Scheduling
4. Rounding, LP based methods
5. In approximability.
6. Advanced topics like Scheduling
Learning Resources
[Mention textbooks, reference books and other learning resources required as part of the course]
1. Vijay Vazirani, Approximation Algorithms,Springer-Verlag, Berlin, 2001.
2. David Williamson and David Shmoys, The Design of Approximation Algorithms, 2011.

Assessment Plan
[List grade distribution in terms of % across multiple assessment types (assignments, quizzes, mid-term,
end-term, project, etc.)]

Four class tests. There will be one term paper presentation.

Assignments / Projects
[List exact number of assignments or projects included (provide generic description)]
S. CO
N Focus of Assignment / Project Mappi
o. ng

Evaluation Procedures
Provide details of how evaluations will be done, how students can look at the evaluations. Generic
evaluation procedures included below. Add additional evaluation procedures / criteria as needed
Late Assignment Submission Policy
State any penalty policy for late submission
Not applicable.

Make-up Exam/Submission Policy

State if any specific policy derived from institute policy is applicable. Otherwise leave it as given

As per institute policy.

Citation Policy for Papers (if applicable)
[If the course includes reading papers and citing them as part of activities, state the citation policy. Mention
“Not applicable” if section is not applicable to the course]

Not applicable.
Academic Dishonesty/Plagiarism
As per institute policy.
Accommodation of Divyangs
[State any enabling mechanisms for accommodating learners with special needs]

As per institute policy.