CS483 Analysis of Algorithms (Summer 2017)


Instructor: Jyh-Ming Lien, jmlien@cs.gmu.edu, Office: 4442, Engineering Building, Office Hours: Thursday 4:15-5:15 pm
TA: TA: Indranil Banerjee, ibanerje@masonlive.gmu.edu, Office: ENGR 5321, Office Hours: 4:30 pm to 5:30 on Tuesdays and 12noon - 1 pm on Thursdays.
Time: 1:30 pm - 4:10 pm Tuesdays and Thursdays
Location: Innovation Hall 208

Prerequisites: CS 310 (minimum grade of C), CS 330 (minimum grade of C), and MATH 125 (minimum grade of C).

Required textbook: Algorithm Design, by Jon Kleinberg and Eva Tardos, Addison Wesley (2006).

Schedule:
June 06 Chapter 1 Intro
June 08 Chapter 2 Basics of Algorithm Analysis
June 13 Chapter 3 Graphs
June 15 Chapter 4 Creedy algorithms
June 20 Review
June 22 Midterm
June 27 Chapter 5 Divide-n-conquer
June 28 Chapter 6 Dynamic progamming
July 06 Chapter 7 Network flow
July 11 Chapter 8 NP and computational intractability
July 13 Chapter 11 Approximation algorithms
July 18 Chapter 12 Local search
July 20 Chapter 13 Randomized algorithms
July 25 Review
July 27 Final (accumulative)

Grades:
- Weekly Homework: 30% (5 total)
- Midterm: 20%
- Final: 50%

Course Outcomes:
- An understanding of classical problems in Computer Science
- An understanding of classical algorithm design and analysis strategies
- An ability to analyze the computability of a problem
- Be able to design and analyze new algorithms to solve a computational problem
- An ability to reason algorithmically

Policy:
- Late coursework will not be accepted
- Make-up tests will not be given for missed examinations
- All coursework is to be done independently

Honor Code:
The class enforces the GMU Honor Code (http://oai.gmu.edu/the-mason-honor-code-2/).


Disability Statement (http://ds.gmu.edu/):
If you have a learning or physical difference that may affect your academic work, you will need to furnish appropriate documentation to the Disability Resource Center. If you qualify for accommodation, the DRC staff will give you a form detailing appropriate accommodations for your instructor.
In addition to providing your professors with the appropriate form, please take the initiative to discuss accommodation with them at the beginning of the semester and as needed during the term. Because of the range of learning differences, faculty members need to learn from you the most effective ways to assist you. If you have contacted the Disability Resource Center and are waiting to hear from a counselor, please tell me.