Data Structures and Basic Algorithms: Basic terminology, Complexity issues and NP-Hardness. Examples - Exponential, heuristic, approximation and special cases. Basic Algorithms. Graph Algorithms for Search, spanning tree, shortest path, min-cut and max-cut, Steiner tree. Computational Geometry Algorithms: Line sweep and extended line sweep methods.
Basic Data Structures. Atomic operations for layout editors, Linked list of blocks, Bin-based method, Neighbor pointers, corner-stitching, Multi-layer operations, Limitations of existing data structures. Layout specification languages.
Graph algorithms for physical design: Classes of graphs in physical design, Relationship between graph classes, Graph problems in physical design, Algorithms for Interval graphs, permutation graphs and circle graphs.
Partitioning: Problem formulation, Design style specific partitioning problems, Classification of Partitioning Algorithms. Group migration algorithms: Kernighan-Lin algorithm, Fiduccia-Mattheyses Algorithm, Simulated Annealing, Simulated Evolution.
Floor Planning: Problem formulation, Constraint based floor planning, Rectangular dualization, Simulated evolution algorithms.
Pin Assignment: Problem formulation. Classification of pin assignment problems, General pin assignment problem.
Placement: Problem formulation, Classification of placement algorithms. Simulation based placement: Simulated annealing, simulated evolution, force directed placement. Partitioning based algorithms: Breur’s Algorithm, Terminal propagation algorithm, Other algorithms for placement.
Global Routing: Problem formulation, Classification of Global routing algorithms, Maze routing algorithms: Lee’s algorithm, Soukup’s algorithm and Hadlock’s Algorithm, Line probe algorithms.
Detailed Routing: Problem formulation, Routing considerations, models, channel routing and switch box routing problems. General river routing problem, Single row routing problem.
Two-layer channel routing algorithms: Basic Left Edge Algorithm, Dogleg router, Symbolic router-YACR2.