Course Announcements

Unofficial final grades are posted.

Marking scheme and comments for Assignment 4 have been posted.

Marks for Assignment 4 have been posted. The assignments are available for pickup from the box outside my office.
Final exam marks and unofficial final course marks will be posted over the weekend.

Marks for Term Test 2 have been posted, for lecture section L5101. Marking comments have been added to the posted test solutions.

An addendum to the sample solutions for assignment 4 has been posted. It contains additional information about questions 2a and 3b, including a simpler way of seeing the answer to question 3b.

Sample solutions for Assignment 4 have been posted.

Solutions and marking scheme for Term Test 2 have been posted. Marks have been posted for section L0101. Unfortunately, the marker has been very busy with some projects and exams of his own and has been unable to finish marking section L5101 so far. The marks and marking scheme for section L5101 will be posted later (as soon as the marker is done).

Important last-minute hints for Assignment 4 have been posted on the assignment FAQ page.

Exceptionally for this week, the summary of lecture notes has been posted already. Tips for studying for and writing the final exam have also been posted on the Tests/Exam page.

Additional office hours: I plan to hold additional office hours on Friday 10 December, 1:30pm-3:30pm and Monday 13 December, 1:30pm-3:30pm.

Tutorial exercises for this week have been posted. We realize you have a lot of work to do, but this exercise will help you understand approximation algorithms and see one more example of computing an approximation ratio.

General extension for Assignment 4: now due by 6pm on Wednesday 8 December 2004. No late submission will be accepted.
(Unfortunately, Faculty regulations do not allow me to give a general extension beyond the last day of classes, so this is the best I can do.)

There will be combined office hours to answer questions on Assignment 4 and on the marking of Assignment 3, on Monday 6 December, 4:30pm-6:30pm, in SF 4303F. These supersede the TA office hours for Assignment 4 announced yesterday.

The cover page for the final exam has been posted (on the "Tests/Exam" page).
The test papers for Term Test 2 have also been posted on that page. Solutions and marking schemes for the test will be posted later.

TA office hours for Assignment 4 will take place from 5:30pm to 6:30pm on Monday 6 December, in room SF 4303F.

The marks, marking scheme, and marking comments for Assignment 3 have all been posted. The assignments will be returned during lecture this week.

All remarking requests received so far have been processed. Updated marks have been posted and you can collect your remarked work from the box outside my office (in SF 4306).

The lecture notes for Week 10 have been updated: the self-reducibility algorithm for CLIQUE was incomplete because it did not specify what to do with edges containing the vertex that is removed at every step.

The handout for Assignment 4 has been updated to make question 1a more specific.

Sample solutions for Assignment 3 have been updated: the verifier for DV3SAT was incomplete because it did not check that every clause in F contains three distinct variables.

Sample solutions for Assignment 3 are posted.

Assignment 4 is posted. Note that you already know everything you need to answer the first two questions on the assignment.

Official course evaluations will take place during next week's lectures. It's important to get as much official feedback as possible, so please try to show up. In particular, since this is the first offering of this new course, there will be additional questions I will want to ask about the course content and organization, in order to help improve the offering for next term.

Sample solutions for Assignment 3 will be posted early next week.

Term Test 2 will be on all of the material covered after Term Test 1 (mapping reducibility) until this week (self-reducibility and complexity classes outside NP).

One-time change of office hours: For this week, my Wednesday office hours will take place 4-6 (instead of the usual 3-5).

Marker office hours for A2: Monday 22 November, 5:30pm-6:30pm, in SF 4303F.

General extension for Assignment 3: the new due date for Assignment 3 is Friday 19 November 2004, no later than 6pm. Absolutely NO late submissions will be accepted!

New dates for Term Test 2: Term Test 2 will now take place on Friday 26 November (for section L0101) and Tuesday 30 November (for section L5101), during regularly scheduled tutorial.

Undergraduate Research Talk:

Prof. Sam Roweis will be giving a research talk on November 17th
at 4pm in BA 1210.  All undergraduates are welcome to attend.
Refreshments will be provided.

The title of his talk is: Visualization and Classification of High
Dimensional Datasets

Sam Roweis is an Assistant Professor in the Department of Computer Science
at the University of Toronto. His research interests are in machine
learning, data mining, and statistical signal processing. Roweis did his
undergraduate degree at the University of Toronto in the Engineering
Science program and earned his doctoral degree in 1999 from the California
Institute of Technology working with John Hopfield. He did a postdoc with
Geoff Hinton and Zoubin Ghahramani at the Gatsby Unit in London, and has
also worked in several industrial research labs including Bell Labs, and
Whizbang! Labs. He is the holder of a Canada Research Chair in Statistical
Machine Learning and the winner of a Premier's Research Excellence Award.

One-time change of office hours: For this week only, my Wednesday office hours will take place 4-5 (instead of the usual 3-5).

TA office hours for A3: On Monday 15 November, 5:30-6:30, in SF 4303F.

Marker office hours for A1: For unknown reasons, the marker of Assignment 1 was unable to make it to the office hours scheduled for Monday 8 November 5:30-6:30. We apologize for the inconvenience, and have rescheduled the office hours for Thursday 10 November 5:30-6:30 in SF 4303F. Students who are unable to make it to the new time should talk to me during my regular office hours.

Assignment 2 has been marked and will be returned during tutorials this week. The marks, marking scheme, and marking comments for the assignment have all been posted.

Marking comments for Assignment 1 have been posted.

Computer Science Alumni Career Night:
The Department of Computer Science and the UofT Office of Advancement are hosting a Computer Science Alumni Career Night on November 16, 2004 at 6pm in BA 1240.
This is an excellent opportunity to find out more about the exciting careers of three UofT Computer Science graduates:
- Andrew Beck, Chief Technology Officer and Co-founder, INEA Corporation.
- Jae Y. Chong, Chief Technology Officer, Storage ASP Incorporated.
- Mark Verdun, Vice President, Partner Programs, NewStep Networks.
This event will also give you a chance to practice your networking skills!
Space is limited, so register now.
Refreshments will be provided.

The sample solutions for Assignment 2 were updated by adding a paragraph to the answer to question 3. For those of you who may have already printed the sample solutions, here is the additional paragraph.

Intuition: In most of the problems about languages based on TM's with specific properties, it is the possibility of infinite loops that prevent us from deciding the answer with a simple simulation. Here, we want to show that knowing T(n) helps us remove this "infinite loop" difficulty by allowing us to know when a machine has entered an infinite loop. Intuitively, this is because knowing T(n) allows us to put a bound on the resources used by any TM that eventually halts when started in the appropriate configuration, so that any TM that exceeds this bound is known to have entered an infinite loop. In this case, we bound the amount of tape used, which also gives an indirect bound on the number of configurations (hence on the number of steps). Now, let us give a formal answer.

The lecture summary for this week is now posted. The next tutorial exercises were missing but they have been posted now. Please take the time to at least read them, and be prepared to work on them during the tutorial. Our apologies for the delay.

Sample solutions for Assignment 2 are now posted.

A number of hints/clarifications have been posted on the FAQ page for Assignment 3, as well as a few changes to the assignment.

Deadlines for remarking requests: Note that according to the Faculty of Arts & Science rules, requests for remarking of term work must be submitted within one month of the date when the work was returned. This gives the following deadlines to request remarking of Test 1 or Assignment 1:

• Test 1: by 5pm on Wednesday 24 November 2004.
• Assignment 1: by 5pm on Wednesday 1 December 2004.

Proposal to change the date of Term Test 2: I propose to move Term Test 2 one week later, i.e., to change the date of the test
from Friday 19 November to Friday 26 November (for section L0101)
from Tuesday 23 November to Tuesday 30 November (for section L5101).
I will hold a vote on this change during lecture on Monday 15 November (for section L0101) and on Tuesday 16 November (for section L5101).

Assignment 3 is now posted. You know enough material to be able to get started, in particular for 4(a).

Any unclaimed work (Term Test 1, Assignment 1) will be left in a box on the table in my outer office (SF 4306). The work will be sorted by tutorial section (red folders for the day sections, blue folders for the evening). Please be careful to take only your copy and to leave the folders sorted by tutorial section.

Marks for Assignment 1 are posted. Marking comments will be posted this week. The marker will hold an office hour to answer questions about the solutions and marking scheme on Monday 8 November, 5:30pm-6:30pm, in SF 4303F.

The test papers as well as the solutions and marking schemes for the two versions of Term Test 1 have been posted on the Tests/Exam page. The marks for Term Test 1 have also been posted. The test will be returned during tutorial this week.
Note: We believe that every student is honest; unfortunately, past experience has shown that this is not always the case. In order to prevent people from trying to do something silly, we have made copies of a random sampling of the marked tests before giving them to the TA's to hand back in tutorial.

The marking scheme for Assignment 1 has been posted on the Assignments page. The marks for the assignment will be posted as soon as they are available. Unfortunately, I cannot say when that will be exactly.

Change of Office Hours: For section L0101 (day), the marker of Test 1 will hold office hours 4:30pm-5:30pm on Monday 1 November 2004 in SF 4303F. The office hours for section L5101 (evening) will take place at the original time (5:30pm-6:30pm) on the same day.

Term Test 1 will be returned during tutorials this week. The solutions and marking scheme for the test will be posted later this week, as well as the marks for the test.
The markers for Term Test 1 will hold special office hours to answer questions about the solutions and marking on Monday 1 November, 5:30pm-6:30pm, in SF 4303F.

There will be no question number 4 on Assignment 2.

TA Office Hours: 5:30pm-6:30pm on Monday 25 October 2004 in SF 4303F.

The lecture summary for last week, readings for this week, and tutorial exercises for this week have all been posted. Apologies for the delay.

Here's a great opportunity to find out about some of the exciting research being carried out in the department.

 Thursday, October 21st at 4pm (BA 1210)
 Professor Derek Corneil
 "Graph Theory, algorithms and applications"
 
 All undergraduate students are welcome to attend Prof. Corneil's talk
 about his research.  Refreshments will be provided.
 
 Derek Corneil graduated from DCS with a PhD in 1968.  After a
 post-doctoral fellowship, he returned to UofT in a faculty position and
 was Chair of the department from 1985 to 1990.  He has won two CSSU
 Teaching Awards and has supervised over 50 MSc and PhD theses.
 
 Abstract:  This talk examines some of the recent work my students and I
 have done in the area of applied and algorithmic graph theory.  Very
 little knowledge of graph theory is assumed for this talk.

The solutions for Assignment 1 have been updated to include a formal description of the TM for question 4(a).

Warning! Problems 5.14 and 5.15 from the textbook are on Assignment 2. In order to avoid any chance of accidental plagiarism, please don't use these problems to study with other students for Term Test 1.

Sample solutions have been posted for Assignment 1.

TA Office Hours:
1:30pm-2:30pm on Thursday 14 October 2004 in SF 4303F.
5:30pm-6:30pm on Monday 18 October 2004 in SF 4303F.

Assignment 2 has been posted on the Assignments page. Sample solutions and a rough marking scheme for Assignment 1 will be posted early next week.

Term test 1 will take place during tutorial on Friday 15 October (for students in section L0101) and Tuesday 19 October (for students in section L5101). The test will be on all of the material covered in lectures and tutorials, up to and including the tutorial exercises for week 5, as well as the textbook readings for weeks 1-4 and assignment 1.

About tutorial rooms.
Students in the day section (L0101) whose last name starts with T-Z, please make sure that you go to your correct room (BA 3000) starting this week.
Students in the evening section (L5101), please make sure that you go to your correct tutorial.

Because of very low attendance, I have decided to move my Wednesday office hours one hour earlier. If I find that nobody ever comes to my Wednesday office hours, I will consider moving them to a different day (maybe by having longer office hours on Tuesdays).
From now until further notice (or until the end of term), my office hours will be T 3-5, W 3-5.

Reminder: There will be a TA office hour in SF 4303F, 5:30-6:30 tonight.

Clarifications have been posted on the FAQ page for Assignment 1.

Check out the new Undergraduate announcements webpage.

The CS Deptartment is holding a series of faculty presentations for undergraduate students.
All undergrads are welcome to attend the presentations. This is a great opportunity to find out about the cutting edge research going on at UofT, and to meet some of your professors! Refreshments will be provided.
All of the presentations will take place in BA 1210. The schedule for this term is:

• October 6, 2004, 4-5pm
  Professor Allan Borodin
  "Thoughts on a Theory of Algorithms"
• October 21, 2004, 4-5pm
  Professor Derek Corneil
  "Graph Theory, algorithms and applications"
• November 17, 2004, 4-5pm
  Professor Sam Roweis
  "Visualization and Classification of High Dimensional Datasets"

Change of TA Office Hour: An unfortunate incident made it impossible for the TA to be on time for yesterday's office hours. To make up, there will be a TA office hour on Thursday 30 September, 4:30-5:30, in room SF 4303F.

A course newsgroup has been created for the course. Check the Main Webpage for details.

The tutorial exercises for Week 4 are posted on the Lectures/Tutorials page.

TA Office Hour: There will be a TA office hour on Monday 27 September, 4:30-5:30, in room SF 4303F.

The lecture summary for week 2 and the readings for week 3 have been posted on the Lectures/Tutorials page. The tutorial exercises for week 4 will be posted later.

Due to unpredictable circumstances, Alex Hertel was absent from his 6pm tutorial yesterday, in room BA 3008. However, Philipp Hertel (the TA in room BA 3012) tells me that he dropped by BA 3008 to leave a note on the blackboard informing students to come to his tutorial instead. Even though everyone should have seen the note and gone to the other tutorial, a number of students apparently did not (possibly because they did not think to look at the blackboard, or maybe because someone else had already erased the note).
In any case, Alex Hertel will hold a "make up" tutorial session tomorrow (Thursday 23 September) 4:30-5:30 in room SF 4303F.

The author maintains a list of errata for the textbook.

The tutorial exercises for week 3 have been changed: exercise 3.4 has been removed.

There will be a graduate school information session on Thursday 23 September, 4-6pm, in BA 1190. Details here.

The tutorial exercises for Week 3 (Fri 24 Sep for L0101 and Tue 28 Sep for L5101) have been posted.
Don't forget to read the textbook sections listed on the Lectures/Tutorials page to prepare for next week's lectures!

The Engineering and Information Technology Career Info Day 2004 will take place on Thursday 23 September. You must register in order to attend. Check out the details here.

The Professional Experience Year (PEY) internship program will hold an information session on Tuesday 21 September, 11-12 in BA 1130. Check out the details here.

I have fixed a typo in the due date for Assignment 3 (the correct date is Tuesday 16 November).

A summary of my lecture notes for this week has been posted on the Lectures/Tutorials page. Because not everyone will have the book yet, the summary is more detailed than you can expect for the rest of the term.

My office hours for the term will take place T3-5 and W4-6 (my apologies to students in the evening section, but I am unable to stay later than 6pm).
However, for today only (Wed 15 Sep), I will hold office hours from 3:15 to 5:15 as I had originally planned.

The breakdown of marks for Assignment 1 has been added to the assignment handout.

Because the textbook is not available from the bookstore, I have typed the text of the tutorial exercises for next week and made it available on the Lectures/Tutorials page.

The deadline to request prerequisite waivers is Monday 20 September 2004, and it will be strictly enforced. If you are missing one of the prerequisites for this course, you will be removed from the course unless you obtain a prerequisite waiver from your instructor.
The prerequisites for this course are: CSC 236H/238H/240H.

CSC 365H is an "enriched" version of this course taught by Prof. Stephen Cook -- the researcher who started the field of NP-completeness!
It will cover the same topics as CSC 363H, but at a faster pace, in more depth, and with more challenging assignments. If you took CSC 240H or if you obtained an "A" or better in CSC 236H/238H, then you can take the enriched course instead of this one.
Lectures and tutorials are at the same times as for section L0101 (MW2, F2).

Change of tutorial rooms. For this week only, students in section L0101 whose last names start with D-K and T-Z will have their tutorial in room BA 1170 (on Friday 2-3). The regular tutorial rooms will apply starting next week.

The bookstore apparently did not order enough copies of the textbook. I have contacted the appropriate people and this should be fixed shortly.

A section on "learning objectives" has been added to the Lectures/Tutorials page, as well as a more detailed outline for the first part of the course.

Under construction! Most of the information on this site is tentative. Everything should be settled by the end of the first week of classes.
In particular, important information about tutorial sections was added to the course information sheet after 6pm today.