ECE 59500 - Applied AlgorithmsLecture Hours: 3 Credits: 3
This is an experiential learning course.
CMPE Special Content Elective
Experimental Course Offered: Fall 2018, Fall 2019
Requisites by Topic:
Data structures (lists, trees, graphs) and associated algorithms, time and space complexity
Physical design of VLSI (very large scale integration) of circuits and systems deals with the determination of the actual locations of the components, as well as the wirings of the components. To optimize the placement (the actual locations of components) and routing (the wirings of the components), automated physical design tools rely on many clever data structures and algorithms. This course aims to cover many such useful algorithms, including greedy algorithms, dynamic programming and more advanced graph algorithms. It also aims to demonstrate how such algorithms are applied to optimize the placement and routing of circuits and systems and to solve optimization problems encountered in general engineering applications. This is usually accomplished by first transforming or formulating the placement and routing problems or engineering problems into some tree/graph problems. The course will involve a few related programming assignments.
Required Text(s): None.
- Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching, 3rd Edition, Robert Sedgewick, Addison Wesley, 1999, ISBN No. 10:0201314525.
- Algorithms in C, Parts 5: Graph Algorithms, 3rd Edition, Robert Sedgewick, Addison Wesley, 2002, ISBN No. 10:0201316633.
- Introduction to Algorithms, 3rd Edition, Thomas H. Cormen, Chalres E. Leiserson, Ronald L. Rivest, Clifford Stein, MIT Press, ISBN No. 10:0262033844.
- An understanding of greedy algorithms and dynamic programming. 
- An understanding of advanced graph algorithms. 
- an understanding of flow network algorithms. 
- An ability to design and implement appropriate data structures and algorithms for engineering applications. [1,2]
|3.5||Greedy algorithms and dynamic programming|
|1.5||Applications of greedy algorithms and dynamic programming: floor-planning, track assignment, buffer insertion|
|2||Advanced graph algorithms|
|2||applications of advanced graph algorithms: scheduling, clock optimization, re-timing|
|3.5||Flow network algorithms|
|1.5||Applications of flow network algorithms: technology mapping, routing|
|1||Student presentations and 1 mid-term|
Engineering Design Content: