Introduction
ECE588 is CAD Techniques VLSI Design. It is one class I am taking this semester. I am writing this blog to review my homeworks and projects I have finished in this class. Before the exam I am going to create another blog for reviewing everything I learned in this lecture.
Homework 1
The first homework is about graph theory algorithms. Algorithmic graph is used to understand and formulate algorithm. There are 7 algorithms I worked with C language to run and see how these graph theory algorithms work.
1. Breath First Search
Breath First Search is used to search the target vertex from the start vertex. This algorithm check vertices through edges from the vertices around the start vertex. Then it move to the two steps away vertices. It needs to pay attention every vertex should only be count for one time.
2. Depth First Search
Depth First Search is similar with Breath First Search. Only difference is from the start vertex it move through edges to the end, then move into the next beside vertex. It works like maze. Trying another path until goes into the end.
3. Dijkstra’s Algorithm
Dijkstra’s Algorithm is used to find out the shortest path to the task vertex. It works for the graphs have weight on their edges. From the start vertex, it find out the smallest weight to the start vertex in one step. Next step find the second smallest weight to the start vertex. Until all vertices are all went through.
4. Prim’s Algorithm
Prim’s Algorithm also is used to find out the shortest path. It is growing a tree to cover all the vertices. Need to pay attention that Prim’s Algorithm should not have loops on the growing tree. Every step the tree will grow to another vertex which has the smallest weight on the tree.
5. Kruskal’s Algorithm
Kruskal’s Algorithm is growing a forest instead of tree. The difference is it focus on edge instead of vertices. Prim’s Algorithm is a connecting tree. Kruskal’s Algorithm does not necessary to be connect. It always chose the smallest weight edge until the forest connect all the vertices.
6. Bellman Ford’s Algorithm
Bellman Ford’s Algorithm is one way to find out the shortest paths to the start vertex from all vertices. If there are n vertices in the graph, it has n-1 steps. At the beginning, every vertex has infinite weight to the start vertex, except itself. Each step update the smallest weight to the start vertex. At the end of this algorithm, all the weight to the start vertex is the shortest length.
7. Floyd Warshall Algorithm
Floyd Warshall Algorithm is used to find out the shortest paths to any two vertices. One problem for it is Floyd Warshall Algorithm cost a long time to run.
Homework 2
If you have any questions, please contact with tianluwu@gmail.com