Course Information:

• Text: Introduction to algorithms, by T. Coremen, C. Leiserson and R. Rivest, McGraw-Hill.
• Course Outline: The topics covered and the corresponding chapters and sections in the textbook are as follows:
  • Introduction
    • Divide and conquer: 2.3.
    • [SELF-REVIEW] Review of Complexity and Recurrences 3, 4.1, 4.2, 4.3
    • Heapsort: 6.1 - 6.5.
  • Design and analysis techniques
    • Dynamic programming: Ch. 15.
    • Greedy algorithms: 16.1, 16,2, 16.3.
    • Amortized analysis: 17.1 - 17.3.
  • Data structures
    • Binomial heaps: 19.1 - 19.2.
    • Fibonacci heaps: 20.1 - 20.4.
  • Graph algorithms:
    • Review of elementary graph algorithms: 22.1 - 22.4.
    • Minimum spanning trees: 23.1 - 23.2.
    • Shortest Paths: 24.1 - 24.3, 25.1 - 25.3.
  • NP-Completeness: 34.1 - 34.5.

  Class Structure:

  • Homework: There will be 5-6 assignments.
  • Exams: There will be several short in-class quizzes and a final exam. The quizzes and exams are closed book and closed notes.

    	Tentative date
    Quizzes	most thursdays 920-940 pm
    Final Exam	TBD (Th)

    University rules prohibit any student from taking the exam early. Please make your plans for the winter vacation accordingly.

  • Grading Policy:

    Homeworks	30%
    Quizzes	30%
    Final Exam	40%

  Additional policies:

  • Academic Integrity Policies of the University will be strictly enforced. You are encouraged to review these policies, for example in SCampus pp. 74-75, 82-87.
  • Please visit course homepage and check Announcement regularly.
  • No late homework will be accepted unless approval is granted from the instructor in advance.
  
  

  ---