CSC B63: Assignments

Assignment Schedule

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

Assignment 3/4

• Assignment handout (PDF) (PS)
• Due by 1:10 pm on Thursday, July 31. Please submit the written questions directly to your instructor, preferably at the start of lecture.
• Hints and clarifications:
  • Q3: There are many acceptable answers here. Pick one "reasonable" way and explain it sufficiently.
  • Q4a: It's an iff, so be sure to prove both directions. Prove that if there's an odd cycle, that the graph cannot be bipartite, and prove that if there are no odd cycles, you can obtain a bipartition. You may assume wlog that G is connected (why?).
• Sample solutions: PDF or PS

Assignment 2

• Assignment handout (PDF) (PS) and the programming question
• Due by 1:10 pm on Thursday, June 19. Please submit the written questions directly to your instructor, preferably at the start of lecture.
• For the programming question, please submit all required files electronically using the submit command:
  submit -N p2 cscb63s AVLTree.java
  or (if you've previously submitted and want to submit a new version):
  submit -N p2 -f cscb63s AVLTree.java
  The programming portion may be submitted by 6:00pm on Friday, July 4.
• Hints and clarifications:
  • Q1: The clarification seems to have been cut off in the prelude to Q1. It should read: "...split a node only when it's full and you need to add another key to it (split before the new key is added)."
  • Q2: To figure out how to augment this AVL tree, use ideas similar to the examples we saw in class (and are in the textbook). You may need to add more than one piece of information!
  • Q3: If you're having trouble deciding which data structure to use, ask yourself how much time you're allowed to use when processing each GPA. You may assume you know n, and that you're given the n GPAs in one big array (and your data structure need not store them!).
  • Programming: The balance factors should be correct once you return from the balance() method... the balance factors could be updated within this method or by some other method it calls (such as by a rotation method).
  • Programming: Your balance factors must be updated within constant time at each node (i.e., do not compute the height of each subtree!).
• Programming question tester (.tar.gz)
  Instructions: You need the files Node.java, CheckStruct.java, AVLTestTree.java, Tester.java, input and your (the tested file) AVLTree.java.
  Compile the *.java files, and run "java Tester < input" to see how the testing was performed.
  If after running the tester, you believe there was a problem with the autotester, please let us know by Monday.

Assignment 1

• Assignment handout (PDF) (PS) and the programming question
• Due by 1:10 pm on Thursday, May 29. Please submit the written questions directly to your instructor, preferably at the start of lecture.
• For the programming question, please submit all required files electronically using the submit command:
  submit -N p1 cscb63s THeap.java
  or (if you've previously submitted and want to submit a new version):
  submit -N p1 -f cscb63s THeap.java
  The programming portion may be submitted by 6:00pm on Sunday, June 1.
• Hints and clarifications:
  • Q1: The HeapSort algorithm uses a max-heap here (it's not explicitly stated in the question).
    What detail of proof are we looking for? You should be able to convince a skeptical classmate that your argument is correct and complete. It might be just a few lines, or perhaps longer. You may use paragraphs like you see in your textbook. Remember to be consise... overly verbose answers make the TA grumpy.
  • Q2: You may assume the lists are given to you as k arrays or as k linked lists (whichever format you prefer). Try to concentrate on the essence of the algorithm (the main idea) when you describe your solution.
    Observe also that when k=2, this is like the merge operation in MergeSort, and when k=n (n lists of 1 element each), this is like a regular sorting problem.
  • Q3b: Note that this question is asking about the worst case cost of doing k insertions. Attempting to compute the average case cost of an insertion will not help you. (Why not?)
• Sample solutions: PDF or PS

Submission instructions

Assignments will consist of a number of "pen-and-paper" questions (the "written" portion, whose solution involves no computer programming and can be handwritten or typed) and a number of "programming" questions (whose solution is entirely computer programming).

The written portion must be handed in using the cover sheet for assignments (Adobe PDF document) (PS). All written portions must be submitted directly to the instructor by the beginning of class on the specified due date. Late assignments will not be accepted (including assignments submitted after the first 5 minutes of class) except in truly unusual circumstances. (See the policy on special consideration for how to request an individual extension for unusual circumstances).

The programming portion must be handed in electronically using the UTSC submit command. Hardcopies (such as computer printouts) will not be accepted, as your code will be executed to determine your mark. Though your programming portion is due at the same time as the written portion, we will not collect the electronic submissions until Sunday at 6:00pm (so you may think of this as an automatic extension). It is your responsibility to ensure your programming solution is submitted on time, as we cannot automatically disable acceptance through submit at a predetermined time. Ensure your programs work correctly on the UTSC computer system; if they do not, you will not receive any credit.

Frequently solved problems:

• I need a computer account. How do I get one?
  Go to the website: https://www.utsc.utoronto.ca/~accounts/newaccount.cgi
• How do I submit my files?
  Make sure you're in the directory that contains the file(s) you want to submit, and use the command:
  submit -N <assignment> cscb63s <files>
  replacing <assignment> with the assignment name (p1, p2, ...) and replacing <files> with the list of files you are submitting.
• I tried to submit and got the error: "submit: You're not in the cscb63s group." What do I do?
  The computer system doesn't know you're in the class. Make sure that you're officially enrolled in the course. In general, if you enrolled in the class recently, you might have to wait a couple of days before the system administrators give you permission to submit files to our course. If the problem persists, let me know.
• I submitted an old version of my file, and now I want to resubmit my new version. How do I do it?
  First of all, good idea! Submitting early and often makes sure the submit system is working for you, and if anything happens (you sleep in, your computer crashes, etc.), you already have a copy submitted for marking. We only keep the most recent copy that you submitted. To submit a new version, use the "-f" option for submit to overwrite the old version:
  submit -N <assignment> -f cscb63s <files>