Syllabus
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.
Objectives and Outcomes
Course Objectives:
- To introduce the fundamental concepts of data structures and algorithms as they apply to VLSI design.
- To introduce advanced data structures and algorithms to optimize various design and analysis tasks in VLSI.
- To provide exposure to analysis and optimization VLSI circuit designs using algorithms that manage complexity and improve efficiency in layouts, routing, and placement.
- 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:
CO/PO |
PO 1 |
PO 2 |
PO 3 |
PSO1 |
PSO2 |
PSO3 |
CO 1 |
2 |
|
|
2 |
|
|
CO 2 |
3 |
|
3 |
3 |
|
2 |
CO 3 |
3 |
2 |
3 |
3 |
2 |
3 |
CO 4 |
3 |
2 |
3 |
3 |
2 |
3 |