|
General Information |
-
Time & Place: M W F, Period 4 (10:40 - 11:30AM), CSE Building,
Room E222
- Class homepage:
http://www.cise.ufl.edu/class/cot5442sp13/
|
|
Instructor Information |
- Name: Dr. My T. Thai
- Office: CSE 550
- Phone: (352) 450-1837
- Email:
mythai@cise.ufl.edu
- Office Hours: Wednesday, noon - 1:40PM or by
appointments
|
|
Teaching Assistant |
- Name: Yilin Shen, Nam Nguyen
- Email: yshen@cise.ufl.edu,
nanguyen@cise.ufl.edu
|
|
Course Description |
- For many optimization problems, it is almost
unfeasible to find an exact solution. Since approximation algorithms
can provide techniques for near-optimal solutions, the study of this
area is significantly important. This course covers several techniques
to design and analyze many approximation algorithms for
computationally hard problems, divided into three parts: (a)
Combinatorial algorithms, (b) Linear programming based algorithms, and
(c) Semidefinite programming based algorithms. This course also addresses many other
problems existing in the networking research literature.
|
|
Course Objectives |
- Understand the essential techniques to
design and analyze approximation algorithms, including the following:
- Combinatorial methods
- Linear programming
- Primal-dual and relaxation methods
- Semidefinite programming
- Hardness of approximation
- Able to model and solve many practical
problems raising in our real life applications
- Grasp the key ideas of graph theory
|
|
Prerequisites |
- There is no formal prerequisite for this
course. However, students should have a solid background in algorithms
and strong mathematical skills.
|
|
Textbooks |
- Required Textbook:
-
N/A. I will provided the lecture notes
- Recommended Textbooks:
- Vijay Vazirani, Approximation Algorithms, Springer-Verlag, 2001,
ISBN: 3-540-65367-8
- Vasek Chvatal, Linear Programming,
W. H. Freeman Company, 1st ed., 1983, ISBN: 0716711958
- Michael R. Garey and David S. Johnson,
Computers and Intractability: A Guide to the Theory of
NP-Completeness, W. H. Freeman Company, 1990, ISBN: 0716710455
- Ding-Zhu Du, Ker-I Ko, Xiaodong Hu,
Design and Analysis of Approximation Algorithms
(Springer Optimization and Its Applications, Vol. 62) 2011, ISBN:
978-1461417002.
|
|
Grading Policies |
- Homework Assignments:
- 4 homework assignments, together weighs
50%
- Due at the beginning of the lecture on
the due date
- No late assignment will be accepted
- Midterm Exam:
- One midterm exam, weighs 20%
- In class, open books, open notes
- Final Exam:
- One final exam, weighs 30%
- Take home, open books, open notes
- Due by/on Noon of Monday April 22,
2013 at Room E555. No late assignment will be accepted
- Cut-off points:
- A >= 90%, 90% > A- >= 87%, 87% > B+ >= 85%, 85% > B >= 80%, 80% > B- >= 77%, 77% > C+ >= 75%, 75% > C >= 70%
- Undergraduate students, in order to graduate, must have an overall GPA and an upper-division GPA of 2.0 or better (C or better). Note: a C- average is equivalent to a GPA of 1.67, and therefore, it does not satisfy this graduation requirement. Graduate students, in order to graduate, must have an overall GPA of 3.0 or better (B or better). Note: a B- average is equivalent to a GPA of 2.67, and therefore, it does not satisfy this graduation requirement. For more information on grades and grading policies, please visit: https://catalog.ufl.edu/ugrad/current/regulations/info/grades.aspx
|
|
Other Policies |
- Collaboration:
- You may discuss with other students on solutions of homework assignments. However, you must write up
solutions on your own independently
- Cite any sources that you use to help obtain your solutions (but do not copy the sources)
- Honesty Policy: All students admitted to the University of Florida have signed a statement of academic honesty committing themselves to be honest in all academic work and understanding that failure to comply with this commitment will result in disciplinary action. This statement is a reminder to uphold your obligation as a UF student and to be honest in all work submitted and exams taken in this course and all others.
- Accommodation for Students with Disabilities Ð Students Requesting classroom accommodation must first register with the Dean of Students Office. That office will provide the student with documentation that he/she must provide to the course instructor when requesting accommodation.
- UF Counseling Services ÐResources are available on-campus for students having personal problems or lacking clear career and academic goals. The resources include:
- UF Counseling & Wellness Center, 3190 Radio Rd, 392-1575, psychological and psychiatric services.
- Career Resource Center, Reitz Union, 392-1601, career and job search services.
- Software Use: All faculty, staff and student of the University are required and expected to obey the laws and legal agreements governing software use. Failure to do so can lead to monetary damages and/or criminal penalties for the individual violator. Because such violations are also against University policies and rules, disciplinary action will be taken as appropriate. We, the members of the University of Florida community, pledge to uphold ourselves and our peers to the highest standards of honesty and integrity.
|
