C SC 482B/582 Internet Algorithms

FALL 1999

Classes moved as follows:

  • Monday 11:00-1:00 Cornett A339
  • Thursday 11:30-12:30 Cornett A372

Study Aid: Frank Ruskey's Amazing Guide to Pumping Lemma Proofs, Frank'sGuide.ps, Frank'sGuide.pdf

Books about NP-Completeness on reserve:

  • ``Computers and Intractability: A guide to the theory of NP-completeness," by Garey and Johnson.
  • ``Introduction to Algorithms," by Cormen, Leiserson, and Rivest, chapter 36. (Reserved for csc425.)
  • Lecture Slides

  • Reading Assignments

    • Week 1: Review Sections 1.1-1.6. Read Sections 1.7-1.8 in Text.
    • Week 2--3: Read Sections 2.1-2.5.
    • Week 4--5: Read Sections 3.1-3.4
    • Week 8: Read Sections 4.1-4.3; skip p.186-190.
    • Week 9: 4.5; 5.1-5.3
    • Week 11: 5.4, 6.1, 6.4
    • Week 12: 7.1, 7.3
    • Week 13: pages 38-44 in Garey and Johnson, on Cook's Theorem

    Homework Assignments

    Homework Policy

    • Homeworks will be turned in at the lecture on the due date.
    • After this time, and until 2pm on the Monday following the due date, homework may be submitted directly to the TA, Jesse Bingham, by bringing it directly to his office ELW A232. You may put it under the door if he is not there. Any homework submitted in this way will have 20% of the total marks for the assignment deducted from the grade.
    • No homework will be accepted after 2pm on the Monday following the due date for the assignment.
    • All assignments must be stapled and have the following information on a cover sheet or at the top of the first page of the assignment: the course number (CSC320), the section in which you are enrolled, your student number, without the first two digits, and the number of the assignment. DO NOT put your name or full student number anywhere on the assignment.
    • If you have a question about a grade that you receive on the assignment, submit it in writing, with your homework, to Jesse Bingham, who will then pass it on to the grader.



    Here is the solution to problem 1.7.4

    Homework Solutions

    Note: these pages are password protected. To access them, you must supply your gulf userid and password.