ECE 59500 - Applied Algorithms

Lecture Hours: 3 Credits: 3

This is an experiential learning course.

Counts as:
CMPE Special Content Elective
EE Elective

Experimental Course Offered: Fall 2018, Fall 2019

Requisites:
ECE 36800

Requisites by Topic:
Data structures (lists, trees, graphs) and associated algorithms, time and space complexity

Catalog Description:
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.

Recommended Text(s):
  1. Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching, 3rd Edition, Robert Sedgewick, Addison Wesley, 1999, ISBN No. 10:0201314525.
  2. Algorithms in C, Parts 5: Graph Algorithms, 3rd Edition, Robert Sedgewick, Addison Wesley, 2002, ISBN No. 10:0201316633.
  3. Introduction to Algorithms, 3rd Edition, Thomas H. Cormen, Chalres E. Leiserson, Ronald L. Rivest, Clifford Stein, MIT Press, ISBN No. 10:0262033844.

Learning Outcomes:

  1. An understanding of greedy algorithms and dynamic programming. [1]
  2. An understanding of advanced graph algorithms. [1]
  3. an understanding of flow network algorithms. [1]
  4. An ability to design and implement appropriate data structures and algorithms for engineering applications. [1,2]

Lecture Outline:

Weeks Lecture Topics
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:

Establishment of Objectives and Criteria
Synthesis
Analysis
Construction
Testing
Evaluation