ECE 665, Spring 2005 - Lectures

Tu, Th, 2:30 - 3:45 in Marston 220

Part I. Data Structures

• Lecture 1. Jan. 27 - Course introduction and organization.

• Lecture 2. Feb. 01 - Algorithms and complexity. Complexity analysis.
  

• Lecture 3. Feb. 03 - Complexity analysis, cont'd.
  

• Lecture 4. Feb. 08 - Elementary Data Structures

• Lecture 5. Feb. 10 - Elementary Data Structures, cont'd: Trees.
  Discussion of possible class projects:
  - High level synthesis (scheduling allocation, and resource binding).
  - VLSI layout generation using Euler graph traversal algorithm.

  Please read about the famous Euler's Bridges of Konigsberg problem.

• Lecture 6. Feb. 15 - Trees and Euler paths, cont'd.
  Application: Standard cell layout generation .
  Heaps and Priority Queues,

• Lecture 7. Feb. 17 - Heaps and Priority Queues, cont'd.
  

• Lecture 8. Feb. 22 - Other data structures: Hash Tables.

• Lecture 9. Feb. 24 - Ordered dictionaries and Binary Search Trees.
  AVL Trees

Part II. Algorithms

• Lecture 10. March 01 - Fundamental Methods: Greedy Algorithms,
  

• Lecture 11. March 03 - Fundamental Methods: DivideAndConquer.
  Examples: Merge Sort and Quick Sort.

• Lecture 12. March 08 Divide and Conquer with examples.

• Lecture 13. March 10 - Dynamic Programming.

  Have a nice Spring Break !

• Lecture 14. March 22 - Dynamic Programming: Knapsack revisited
  Applications to VLSI Design. Technology mapping.

• Lecture 15. March 24 - Applications to VLSI Design. Channel routing.
  

• Lecture 16. March 29 - Graphs, data structures, traversal methods.
  Graphs basics , Depth First Search

• Lecture 17. March 31 - Undirected graphs, cont'd.
  Biconnectivity , Breadth First Search.

• Lecture 18. April 05 - Directed graphs, reachability, topological sorting:
  Directed Graphs.

• Lecture 19. April 07 - Weighted Graphs: Shortest Paths .
  

• Lecture 20. April 12 - Weighted Graphs, cont'd:
  Minimum Spanning Trees , Example.

• Lecture 21. April 14 - Network Flows and Matching.
  Max Flow.

• Lecture 22. April 19 - Network Flows, cont'd
  Bipartite matching, min-cost flows. Finish Chapter 8.

  Paper Presentations by students will start the week of April 25. All Ph.D. students must prepare a 20-minute power-point presentation. Please mail the presentation slides in powerpoint format to your instructor by April 22.

• April 21 - No lecture (Monday schedule).

• Lecture 23. April 26 - Students Presentations
  • Terrance O'Regan, Simulated Annealing.

  • Jorge Trabal, Fast Fourier Transform.

  • Jorge Salazar, Cryptography.

• Lecture 24. April 28 - Students Presentations, cont'd.
  • Huaping Wang, Cache Algorithms .

  • Adel Alshayji, Force Directed Placement.

  • Khalid Hadi, Bi-partition Algorithms .

Part III. Mathematical Programming

• Lecture 25. May 03 - Intro to Mathematical Optimization
  Linear Programming (LP).

• Lecture 26. May 05 - Linear and Integer Programming
  Integer Linear Programming (ILP).
  Relationship between LP and ILP.
  Handouts: Total Unimodularity and Duality (PDF notes).

• Lecture 27. May 10 - Linear Programming, Duality: Longest Path example.
  Input Lingo files for the longest path example: primal LP and dual LP.
  

• Lecture 28. May 12 - LP Duality, cont'd
  LP duality (Longest path + Max-Flow Min-cut revisited).

  Course conclusion. LAST CLASS.
  

---

Additional material: Applications of decision trees and graphs to VLSI synthesis and design verification:
BDD Tutorial (slides). Gate matrix layout generation (slides).

---