This course addresses both the fundamentals and the research boundaries of algorithm design and analysis. Covered topics include complexity of algorithms, divide and conquer techniques, greedy methods, dynamic programming, recursive backtracking, amortized analysis, graph algorithms, polynomial-time problem reduction, NP-completeness, approximation algorithms and a selected advanced topic.

Students shall be able to demonstrate:

1. The ability to prove mathematically asymptotic analysis of algorithms using big-O, little-o, big-Omega, little-Omega, and  Theta notation; standard complexity classes; empirical measurements of performance; time and space tradeoffs in algorithms.
2. The ability to derive and solve recurrence relations in order to analyze recursive algorithms.
3. The ability to apply fundamental algorithmic strategies such as brute-force; greedy; divide-and-conquer; backtracking; branch-and-bound; heuristics; pattern matching and string/text algorithms; numerical approximation.
4. The ability to apply various graph algorithms such as depth- and breadth-first traversals; shortest-path algorithms (Dijkstra’s and Floyd’s algorithms); transitive closure (Floyd’s algorithm); minimum spanning tree (Prim’s and Kruskal’s algorithms); topological sort.
5. The ability to define the classes P and NP, and to prove that a problem is NP-complete by reducing a classic known NP-complete problem to it.
6. The to solve complex problems using various heuristic problem-solving methods.

Professor Haidar M. Harmanani

haidar@lau.edu.lb • http://vlsi.byblos.lau.edu.lb • http://harmanani.github.io

Office Hours:

Block A • Room 810

Tuesday, Thursday • 3:00pm – 4:30pm • 8:00pm – 9:30pm or by appointment

August 28, 2016: Fall classes begin

October 4, 2016:  Last day for early withdrawal (WI)

October 26, 2016: Deadline for Incomplete grades

November 3, 2016: Midterm Examination

November 9, 2016: Last day for withdrawal from courses (WP/WF)

December 8, 2016: Fall classes end

Lecture 1: Introduction to Algorithms

Lecture 2: Mathematical Background and Order Complexity

Lecture 3: Recurrence Relations

Lecture 4: Recurrence Relations [Continued]

Lecture 5: Divide and Conquer

Lecture 6: Divide and Conquer: Quick Sort

Lecture 7: Medians and Order Statistics

Lecture 8: Heaps, Priority Queues, and HeapSort

Lecture 9: Red-Black Trees, OS Trees, and Interval Trees

Lecture 10: Dynamic Programming

Lecture 11: Greedy Algorithms

Lecture 12: Graph Algorithms

Lecture 13: Graph Algorithms and Minimum Spanning Trees

Lecture 14: Shortest Path and Graph Algorithms

Lecture 16: NP-Completeness and Approximation Algorithms

1. Assignment 1: Complexity Analysis  Solutions
2. Assignment 2: TBA   Solutions
3. Assignment 3: TBA   Solutions
4. Assignment 4: TBA   Solutions
5. Assignment 5: TBA   Solutions
6. Project: TBA

The objectives of the project are to initiate students into research by converting the theoretical description of one or more algorithms into a functioning implementation while making a minor contribution.  The following should be handed over upon the termination of the project:

• A short report (5 to 10 pages) documenting the program. It consists of a description of the main data structures and procedures (using pseudo-code), a motivation of the choices made, an analysis of the time complexity, and a presentation of some results;
• A listing of all the code written with sufficient comment to make the code easily understandable;
• The program itself (delivered e.g. by email) such that it can be tested.

Please check CADathlon Contest for projects selection and references

All students are expected to take exams during the scheduled time slots. With the permission of the instructor, you may be allowed to take an exam at an alternate time. However, you must request this rescheduling at least 2 weeks prior to the exam date. Exceptions will naturally be made for sudden problems such as serious illnesses/injury. Since the exam schedule is being published at the beginning of the semester, scheduling conflicts (e.g., job interviews, GREs, etc.) are not legitimate reasons to miss an exam.

Midterm Exam

The midterm exam is scheduled for November 3, 2016: Midterm Examination. The midterm exam will be a closed book exam. In principle, all topics discussed in class (whether on the lecture notes or not) and in the assigned readings are a legitimate source for exam questions.

Final Exam

The final will be comprehensive, with roughly 1/3 of the material devoted to material covered prior to the midterm.  The exam will be on May 15, 2015 from 8:00 am - 11:00 am.

Midterm Grades

Final Grades

Course Grades

Code

 Codes of Partitioning Algorithms

1. High-Level Synthesis: Tutorial 1, Tutorial 2, Tutorial 3, Force-Directed Scheduling, and Facet
2.  R. Rajaraman and D. F. Wong, "Optimal Clustering for Delay Minimization", IEEE Trans. on Computer-Aided Design, 14(1), pp 1074-1085, 1992.
3.  J. Cong and Y. Ding, "FlowMap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-Table Based FPGA Designs", IEEE Trans. on Computer-Aided Design, 13(1), pp 1-12, 1994.
4.  G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar, "Multilevel Hypergraph Partitioning: Application in VLSI Domain", IEEE Trans. on VLSI, 7(1), pp 69-79, 1999.
5.  B. Kernighan and S. Lin, "An Efficient Heuristic Procedure for Partitioning of Electrical Circuits", Bell System Technical Journal", pp 291-307, 1970.
6.  C. M. Fiduccia and R. M. Mattheyses. "A linear-time heuristic for improving network partitions", Proceedings of the Design Automation Conference, pp 174-181, 1982.
7.  L. Hagen and A. B. Kahng, "New Spectral Methods for Ratio Cut Partitioning and Clustering", IEEE Trans. on Computer-Aided Design, 11(9), pp 1074-1085, 1992.
8.  H. Yang and D. F. Wong, "Efficient Network Flow Based Min-cut Balanced Partitioning", IEEE Trans. on Computer-Aided Design, 15(12), pp 1533-1540, 1996.
9.  L. Stockmeyer, "Optimal Orientation of Cells in Slicing Floorplan Designs", 57(2-3), Information and Control, pp 91-101, 1984.
10.  D. F. Wong and C. L. Liu, "Floorplan design of VLSI circuits", Algorithmica, 4(1), pp 263-291, 1989.
11.  S. Sutanthavibul, E. Shragowitz, and J. Rosen, "An analytical approach to floorplan design and optimization", IEEE Trans. on Computer-Aided Design, 10(6), pp 761-769, 1991.
12.  H. Murata, K. Fujiyoshi, S. Nakatake and Y. Kajitani, "VLSI module placement based on rectangle-packing by the sequence-pair", IEEE Trans. on Computer-Aided Design, 15(12), pp 1518-1524, 1996.
13.  M. Breuer, "A Class of Min-cut Placement Algorithms", Proceedings of the Design Automation Conference, pp 284-290, 1977.
14.  A. Dunlop and B. Kernighan, "A Procedure For Placement Of Standard-cell VLSI Circuits", IEEE Trans. on Computer-Aided Design, 4(1), pp 92-98, 1985.
15.  J. Kleinhaus, G. Sigl, F. Johannes, K. Antreich, "GORDIAN: VLSI Placement by Quadratic Programming and Slicing Optimization", IEEE Trans. on Computer-Aided Design, 10(3), pp 356-365, 1991.
16.  W. J. Sun and C. Sechen, "Efficient and Effective Placement for Very Large Circuits", IEEE Trans. on Computer-Aided Design, 14(3), pp 349-359, 1995.
17.  J. M. Ho, G. Vijayan, and C. K. Wong, "New algorithms for the rectilinear Steiner tree problem", 9(2), IEEE Trans. on Computer-Aided Design, pp 185-193, 1990.
18.  A.B. Kahng and G. Robins, "A new class of iterative Steiner tree heuristics with good performance", IEEE Trans. on Computer-Aided Design, 11(7), pp 893-902, 1992.
19.  M. Borah, R. Owens, and M. Irwin, "An Edge-based Heuristic for Steiner Routing", IEEE Trans. on Computer-Aided Design, 13(12), pp 1563-1568, 1994.
20.  J. Cong, A.B. Kahng, G. Robins, M. Sarrafzadeh, and C.K. Wong, "Provably good performance-driven global routing", IEEE Trans. on Computer-Aided Design, 11(6), pp 739-752, 1992.
21.  J. Cong, K.-S. Leung, and D. Zhou, "Performance-Driven Interconnect Design Based on Distributed RC Delay Model", UCLA CSD Tech Report #9200043, 1992.
22.  K. Boese, A. B. Kahng, B. McCoy, and G. Robins, "Near-optimal critical sink routing tree constructions", IEEE Trans. on Computer-Aided Design, 14(12), pp 1417-1436, 1995.