Course Details
Subject {L-T-P / C} : CS6103 : Data Structure and Algorithm Design { 3-0-0 / 3}
Subject Nature : Theory
Coordinator : Prof. Bibhudatta Sahoo
Syllabus
Introduction: introduction to the ideas of specification, correctness, and analysis of algorithms, proving algorithm correctness, analyzing algorithms asymptotic analysis and amortized analysis, analyzing the worst-case performance of algorithms.
Problem-solving: The art of problem-solving, problem solving, and decision making, Basic algorithmic structures as an approach to "automatic" problem solving, towards good algorithm design, the role of data structure in algorithm design. The general structure of an optimization algorithm, constraints, solution space, and feasible reasons, and representation of solution space.
NP-completeness: The Class P, The Class NP, NP-complete Problems The satisfiability problem, vertex cover, independent set and clique problems, More NP-complete Problems, The Class co-NP, The Class NPI, The Relationships Between the Four Classes.
Lower bound techniques: Introduction, Trivial Lower Bounds, The Decision Tree Mode The search problem, The sorting problem, The Algebraic Decision Tree Model The element uniqueness problem, Linear Time Reductions The convex hull problem, The closest pair problem, The Euclidean minimum spanning tree problem.
Hashing: The symbol table abstract data type Static Hashing, Dynamic Hashing, Hashing algorithms and application of hashing algorithm.
Heap Structures: Min-max heaps, Deaps, Leftist Trees, Binomial Heaps, Fibonacci Heaps.
Randomized Algorithms: Introduction, Las Vegas and Monte Carlo Algorithms, Randomized Quicksort, Randomized Selection, Testing String Equality, Pattern matching, Random Sampling, Primality Testing.
Approximation Algorithms: Introduction, Basic Definitions, Difference Bounds Planar graph coloring, Hardness results in the knapsack problem, Relative Performance Bounds The bin packing problem, The Euclidean traveling salesman problem, the vertex cover problem, Hardness result in the traveling salesman problem, Polynomial Approximation Schemes The knapsack problem, Fully Polynomial Approximation Schemes, the subset-sum problem.
Heuristics Algorithms: Differentiate between Heuristics and metaheuristic algorithms, Optimization algorithms like Genetic optimization, Particle Swarm Optimization, and Ant colony optimization.
String matching problem, solving real-world problems with string matching, String matching algorithm: Naive Algorithm, KMP (Knuth Morris Pratt) Algorithm, Boyer Moore Algorithm, multiple patterns matching algorithm: Rabin–Karp algorithm, application of string matching algorithm.
Course Objectives
- Synthesize efficient algorithms for the real-world problem.
- Methods to be adopted to cope with NP-complete Problem
- Application of data structures in problem representation and algorithm design
- Apply important algorithmic design paradigms and methods of analysis in problem solving
Course Outcomes
Argue the correctness of algorithms using inductive proofs and invariants.
Essential Reading
- S. K. Basu, Design Methods and Analysis of Algorithms, Prentice Hall of India , Second Edition , February 2015
- Jon Kleinberg and Eva Tardos, Algorithm design, Pearson
Supplementary Reading
- Ellis Horowitz, Sartaj Sahni, Dinesh Mehta, Fundamentals of Data Structures in C++, Universities Press
- Steven S. Skiena, Algorithm Design Manual, Springer
Journal and Conferences
- Journal of Algorithms, Elsevier.