Course

Unit 1:

Introduction to VLSI and Algorithms – Basics of Data Structures – Linked lists, stacks, queues, trees, and graphs – Recursion and its applications in VLSI – Arrays and hash tables in VLSI applications. Graph Algorithms for VLSI – Shortest path algorithms (Dijkstra, Bellman-Ford) – Minimum spanning tree (Kruskal, Prim’s) – Applications in routing and layout.

Unit 2:

Computational Geometry in VLSI – Geometric data structures and algorithms – Convex hulls, Voronoi diagrams, and polygon clipping – Applications in floor planning and placement. Divide and Conquer Algorithms in VLSI – Merging, quicksort, and closest pair problems – Partitioning algorithms for circuit design – Divide and conquer in circuit routing.

Unit 3:

Dynamic Programming and Greedy Algorithms – Overview of dynamic programming – Applications in sequence alignment, partitioning, and optimization – Greedy algorithms for wire-length minimization. VLSI Routing Algorithms – Maze routing and channel routing – Line search. Case studies in VLSI Applications.

Course Objectives:

1. To introduce the fundamental concepts of data structures and algorithms as they apply to VLSI design.
2. To introduce advanced data structures and algorithms to optimize various design and analysis tasks in VLSI.
3. To provide exposure to analysis and optimization VLSI circuit designs using algorithms that manage complexity and improve efficiency in layouts, routing, and placement.
4. To inculcate problem-solving skills using advanced data structures and algorithms to solve real-world VLSI design issues.

Course Outcomes: By the end of the course, students will be able to:

• CO1: Design and implement algorithms for basic data structures such as trees, graphs, and lists tailored to VLSI problems.
• CO2: Analyze and solve VLSI-related problems using algorithms
• CO3: Apply computational geometry techniques in the design of VLSI systems
• CO4: Apply optimization algorithms for performance and resource utilization in VLSI systems.

Skills Acquired: Algorithm Design and Analysis, VLSI Problem-Solving, Computational Geometry, Optimization Techniques.

CO-PO Mapping:

1. Sabih H Gerez, “Algorithms for VLSI Design Automation”, Wiley, 1998
2. Naveed A Shervani, “Algorithms for VLSI Physical Design Automation”, Springer, 2013
3. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, “Introduction to Algorithms”, MIT Press, 2009
4. Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars, “Computational Geometry: Algorithms and Applications”, Springer, 2010.