ECE 51220 - Applied Algorithms

Course Details

Lecture Hours: 3 Credits: 3

Counts as:

  • EE Elective
  • CMPE Selective

Normally Offered:

Fall - odd years

Campus/Online:

On-campus and online

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

Assessment Method:

Weekly homework, programming assignments, project presentation, 1 mid-term test and a final exam