CPSC 4110/5110 Advanced Algorithms – Approximation Algorithms
Time: Tue and Thr @ 1:40 pm – 2:55 pm in TH.173 (Turcotte Hall)
Text: Design of Approximation Algorithms, Shmoys and Williamson,
Syllabus
Previous assignments
Final take home exam
Duration: 24 hours. Dates: Pickup the questions on Wed. Dec 11, 9am – 10am, in my office at C556. Drop off the answers on Thr. Dec 12, 9am – 10am, in my office at C556. I recommend you stay at … Continue reading →
Assignment 3
Due: Thr, Dec 5, in class Undergraduate students can work in teams of two students and can submit a single paper per team. Any notation that is not explained is standard notation. Search google for the definition. 10 pts are … Continue reading →
Schedule for presentations
Farshad Barahimi: Tue Nov 19, 1:40 PM: Shortest superstring problem. A. Golovnev, A.S. Kulikov, and I. Mihajlin, Approximating Shortest Superstring Problem Using de Bruijn Graphs. In CPM 2013, Lect. Notes Comput. Sci. 7922:120–129, 2013. [paper] [presentation] Regular lecture: Tue Nov … Continue reading →
Solutions to midterm and assignments
Midterm questions: http://www.cs.uleth.ca/~benkoczi/files/approx/midterm.pdf Midterm solutions: http://www.cs.uleth.ca/~benkoczi/files/approx/midterm-sol.pdf Assignment 2 questions: http://www.cs.uleth.ca/~benkoczi/wordpress/?page_id=317 Assignment 2 solutions: http://www.cs.uleth.ca/~benkoczi/files/approx/a2-sol.pdf Assignment 3 questions: http://www.cs.uleth.ca/~benkoczi/wordpress/?p=370 Assignment 3 solutions: http://www.cs.uleth.ca/~benkoczi/files/approx/a3-sol.pdf
Midterm exam – Thr. October 31, 2013
Happy Haloween! Exam duration: 75 minutes, in class, on Thr. Oct 31, 2013. Exam preparation guidelines: Chapters covered: 1, 2 (excluding section 2.6); 3.1 Review linear programming Attempt the following exercises from the text: 1.1 (use the greedy algorithm), 1.2 … Continue reading →
Term project and presentation
Due date for projects: Friday Dec 6, midnight Submission instructions: Please send the following by e-mail to the address: roben777+files@gmail.com: the source code, preferably as a link to some code repository or inside a compressed archive (zip, tar.bz2, or tar.gz) … Continue reading →
Approximation algorithms – Lectures
Sep 5 – 19 Read Chapter 1 – Introduction and Appendix A – Linear programing. Sep 19 – 26 Read Chapter 2 (greedy and local search): The k-center + scheduling with deadlines on a single machine + scheduling on parallel … Continue reading →