Foundation of VLSI CAD

Matrices: Linear dependence of vectors, solution of linear equations, bases of vector spaces. orthogonality, complementary orthogonal spaces and solution spaces of linear equations. Graphs: representation of graphs using matrices; paths, connectedness; circuits, cutsets, trees; fundamentals circuit and cutset matrices; voltage and current spaces of a directed graph and their complementary orthogonality. Algorithms and data structures: efficient representation of graphs; elementary graph algorithms involving bfs and dfs trees, such as finding connected and 2-connected components of a graph, the minimum spanning tree, shortest path between a pair of vertices in a graph;