CSC 363: Assignments

Assignment Schedule

Announcements, clarifications, corrections and revisions to assigment specifications are posted to the Announcements page. Please read this page regularly.

Assignment 4

• Assignment handout (PDF) (PS)
• Due by 7:00pm inside drop box in BA 2220 on Thursday, August 10.
  
• Some people asked about the game of Amazons. Here are some pictures I stole from the Internet showing the initial state of the 10x10 game, a middle game state (illustrating a move), and an end game position (all the amazons are separated, assuming good play, so we can determine who will win).
  
• Q1: Do not try to solve TSP in polynomial time (you proved that TSP is NP-complete on Test 2, so it's unlikely you'll be able to do it). Just show that TSP is polytime self-reducible.
• Sample solutions: PDF or PS

Assignment 3

• Assignment handout (PDF) (PS)
• Due by 7:00pm inside drop box in BA 2220 on Thursday, July 20.
  Extended: now due 7:00pm inside drop box in BA 2220 on Monday, July 24.
• Sample solutions: PDF or PS [updated 27 Jul to correct an error on Q4]

Assignment 2

• Assignment handout (PDF) (PS)
• Due in lecture at the start of class (6:10pm) on Tuesday, July 4.
  Do not put your assignments in the drop box for this assignment.
• Sample solutions: PDF or PS
• Marker's notes

Assignment 1

• Assignment handout (PDF) (PS)
• Due by 7:00pm inside drop box in BA 2220 on Thursday, June 8.
• For question 2, a picture of the initial configuration of a multitrack Turing machine (on input abc) might look something like the following:

  +-----+
  |     |
  | q_0 |------+
  |     |      |
  +-----+      |
               V
             +---+---+---+---+---+---+---+--
             | a | b | c |   |   |   |   | ...
             +---+---+---+---+---+---+---+--
             |   |   |   |   |   |   |   | ...
             +---+---+---+---+---+---+---+--
             |   |   |   |   |   |   |   | ...
             +---+---+---+---+---+---+---+--
  
  

  I have drawn seven "cells" from left to right, and there are three tracks in this example. Remember that the single read/write head reads and writes all tracks (all three tracks in this example) at once for a particular cell.

• Marking notes from the TA - the TA makes several important points about common errors students were making. Please read his notes, even if you aced the assignment, to see where students typically go wrong and why it's wrong.
• Sample solutions: PDF or PS

Submission instructions

Every assignment will consist of a number of "pencil-and-paper" questions (whose solution involves no computer programming and can be handwritten or typed). Please recall that the 20% rule does not apply to assignments, where you have the time (and the responsibility) to ask questions and learn how to solve each problem.

All assignments must be submitted directly to the CSC 363 drop box in BA 2220 or given directly to the instructor before the specified time on the due date. Late assignments will not be accepted except in truly unusual circumstances.