CS60086: Selected Topics In Algorithms
CS60086 | |||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Course name | Selected Topics In Algorithms | ||||||||||||||||||||||||
Offered by | Computer Science & Engineering | ||||||||||||||||||||||||
Credits | 3 | ||||||||||||||||||||||||
L-T-P | 3-0-0 | ||||||||||||||||||||||||
Previous Year Grade Distribution | |||||||||||||||||||||||||
| |||||||||||||||||||||||||
Semester | Spring |
Syllabus
Syllabus mentioned in ERP
The objective of this course is to familiarize students with some contemporary research in the area of algorithm design and analysis. The treatment will be theoretical with emphasis on problem solving and will be primality assignments based. •Models of computation and efficiency: Searching faster than O(log n), sorting faster than O(n log n). •Randomized algorithms in graphs and geometry: The impact of using randomization for designing algorithms that are simpler and often more efficient than the deterministic counterparts for several fundamental problems like MST, mincuts, spanners, convex hulls, triangulations, etc. Typically analysis is often harder than design. •Approximation algorithms: A set of rapidly evolving techniques that lead to provable approximation guarantees for hard optimization problems within polynomial running times. Unlike other communities dealing with the same problems the emphasis here is on provability of general instances and goes hand-in-hand with the "hardness of approximation" theory. Each of the topics on their own could be easily a full semester course, so depending on the class response, we may pick and choose from the above list of topics.