Tutorial time and location: Fri 11-12, rm AC 334.
Prerequisites: CSCA48 and CSCA65.
Text: Vassos Hadzilacos. Lecture Notes for CSC B36/236, 2006-2007 edition. The notes can be purchased for $15 (exact change please!) in room SW 625 during business hours.
Tentative weekly schedule: To view the tentative weekly schedule click here .
Calendar of important course-related
events:
| Date | Event |
| Mon, Sep 11 | First day of class |
| Wed, Sep 13 | Assignment 1 available |
| Wed, Sep 27 | Assignment 1 due and Assignment 2 available |
| Wed, Oct 11 | Assignment 2 due and Assignment 3 available |
| Fri, Oct 27 | Midterm exam |
| Wed, Nov 1 | Assignment 3 due and Assignment 4 available |
| Wed, Nov 15 | Assignment 4 due and Assignment 5 available |
| Tue, Nov 19 | Last day to drop the course |
| Wed, Nov 29 | Assignment 5 due |
| Mon, Dec 4 | Last day of classes |
| Homework | 40% (8% each) |
| Midterm | 20% |
| Final | 40% |
Homework marking: For each homework assignment, we may mark only a selected subset of the questions (but solutions to all problems will be made available). In that event, the homework will be marked out of the total weight of the selected questions.
Late homework policy: No late homeworks will be accepted. If you miss a homework deadline because of a medical or personal emergency, you must fill out the Special Consideration Form . (In case of a medical emergency, you must also submit the UTSC Student Medical Certificate , completed and signed by your physician.) If we judge your reason for missing the deadline to be valid, we will use the average mark you achieved in other homeworks as your mark for the missed homework.
Homework collaboration policy: In each homework you may collaborate with at most one other student who is currently taking CSC B36. If you collaborate with another student on a homework, you and your partner must submit only one copy of your solution, with both of your names on the cover. The solution will be graded in the usual way and both partners will receive the same mark. Collaboration involving more than two students is not allowed. For help with your homework you may consult only the instructor, TAs, your homework partner (if you have one), your textbook and your class notes. You may not consult any other source.
Remarking policy: If your request concerns a simple addition error, see the instructor. To make any other kind of remarking request, you must fill this form , attach it to your homework assignment or test, and give it to the instructor of the course no later than one week from the date the marked assignment or test was made available to the class. Remarking requests made after this deadline will not be accepted.
Missed midterm test policy: If you miss the midterm test due to a medical or other serious emergency, get in touch with your instructor immediately, and fill out the Special Consideration Form . (In case of a medical emergency, you must also submit the UTSC Student Medical Certificate , completed and signed by your physician.) There will be no make-up test, but if we consider your reason for missing the test to be valid, we will use your final examination mark to compute your mark for the missed midterm test.
Attendance in tutorials: Attendance in tutorials is as mandatory as attendance in lectures. In neither case is formal attendance actually taken. However, there will be material presented only in tutorial and not discussed in the lectures for which you are responsible and in which you may be tested in homeworks or exams.
Jan 2 --- Final exam and course marks: ... are now available here. These marks are final as far as I am concerned, but they are not official until they are approved by the Marks Review Committee. Official marks will be posted on ROSI.
Dec 19 --- Final exam answers: ... are now posted in the Handouts section of this document.
Dec 18 --- Homework #5 marks: ... are now available here. The assignments can be picked up from my office on Mon Dec 18 until 5:30pm, or on Tue Dec 19 11am-12noon or after the final exam.
Dec 11 --- Yet another change in pre-exam office hours: I am sorry, but I won't be able to make it on Thursday, either. So my pre-exam office hours will be: Mon Dec 18 1-2, Tue Dec 19 11-12. You can always contact me by email of phone, if you have questions before then.
Dec 8 --- Change in pre-exam office hours: Because of a conflict, the previously announced office hour on Fri Dec 15 1-2 is replaced by an office hour on Thu Dec 14 1-2. Thus, the new schedule for pre-exam office hours is: Thu Dec 14 1-2, Mon Dec 18 1-2, Tue Dec 19 11-12.
Dec 4 --- Announcements related to the final exam:
Time and place: The exam will take place on Tue Dec 19, 2-5 in room SW 309.
Material covered: You should be prepared to answer questions about any subject covered in this course. Some past final exams can be found in the Old exams section of this document.
Aids allowed: The exam will be closed book. You may bring an 8.5x11 hand-written, non-photocopied ``cheat sheet''; you may use both sides, if you wish. During the exam you may not carry on your person or keep on your desk any computation, communication, or storage electronic devices (such as calculators, mobile phones, laptops, and ipods).
Office hours before the final exam: I will hold office hours on Fri Dec 15 1-2, Mon Dec 18 1-2, and Tue Dec 19, 11-12. In addition, I welcome questions by email or telephone. (For contact information see the Contact information section of this document.)
Dec 3 --- Solutions to Assignment #5: ... are now posted in the Handouts section of this document.
Nov 27 --- Typo on p. 263: The production in the first of the bulleted items near the bottom of page 263 should be Apq → AprArq (not Apq → AprAqr).
Nov 27 --- Tutorial this week: There will be no tutorial this Friday December 1.
Nov 15 --- Assignment #5 and Solutions to Assignment #4: ... are now posted in the Handouts section of this document. As in Assignment #4, there are some extra-credit questions, providing one more chance to make up lost ground, for those who need it and are willing to put the extra effort.
Nov 13 --- Midterm exam marks: ... are now available here. The exams were returned in tutorial last Friday.
Nov 13 --- FSA visualisation tool: You may want to check out the FSA/regular expression animation tool in
http://osteele.com/tools/reanimator/
This tool allows the user to specify a regular expression R (in a syntax a bit different from what we use in this course, and closer to the syntax of the Unix utility "grep"), and generates a NFSA and a DFSA that accept the language denoted by R. It also allows the user to visualise the operation of these automata, by showing the current state(s) of the automata after processing a user-supplied input string.
This tool appears to handle only relatively small examples, but you may find it useful as well as fun to experiment with.
To generate the NFSA and DFSA from the specified regular expression, this tool uses refinements of algorithms we discussed in class: The constructions for proving the closure properties of FSA-accepted languages (see Theorems 7.21 and 7.22) are used to generate a NFSA from the given regular expression; and the subset construction is used to convert a nondeterministic FSA to a deterministic one (see Section 7.4.2). The resulting DFSA is then reduced, if possible, by applying an algorithm which converts a given DFSA to a DFSA that accepts the same language and has the minimum possible number of states. (This algorithm is beyond the scope of this course. Its efficient implementation is a nice application of data structures for the so-called Union/Find problem, a topic you will likely study in CSCB63.)
Nov 2 --- Solutions to Assignment #3: ... are now posted in the Handouts section of this document.
Nov 1 --- Assignment #4: ... is now posted in the Handouts section of this document. Note that Question 6 is extra credit. Here is an opportunity for those of you who did poorly in earlier assignments to put in extra effort and make up some lost ground.
Oct 30 --- Assignment #2 marks: ... are now available here. Assignments will be returned in tutorial.
Oct 30 --- the midterm exam: ... is now posted in the Handouts section of this document.
Oct 23 --- Announcements related to the midterm exam:
Time and place: The exam will take place on Friday Oct 27, 3-5 in room HW 215.
Aids allowed: The exam will be closed book. You may bring an 8.5x11 hand-written, non-photocopied ``cheat sheet''; you may use both sides, if you wish. During the exam you may not carry on your person or keep on your desk any computation, communication, or storage electronic devices (such as calculators, mobile phones, laptops, and ipods). Recall that the wall clock in HW 215 does not work, so if you need to keep track of time, you should bring a watch.
Office hours this week: In addition to the usual office hours (Mondays 3-4:30), this week I will also also hold office hours on Tuesday Oct 24 3-4:30, Wednesday Oct 25 3-4:30, and Friday Oct 27 10:30-12.
Tutorial this week: Because of the midterm exam on Friday afternoon, the tutorial and TA's office hours on Friday Oct 27 are canceled.
Oct 12 --- Assignment #1 marks: ... are now available here. Assignments will be returned in tutorial.
Oct 12 --- Solutions to Assignment #2: ... are now posted in the Handouts section of this document.
Oct 11 --- Assignment #3: ... is now posted in the Handouts section of this document.
Oct 9 --- Additional office hours on Tue Oct 10: I will be available in my office at UTSC between 10am and noon.
Oct 8 --- Homework #2 correction and clarification: In Question 4(d), ``for any n in N'' should be ``for any positive integer n''. (The function C(n) is not defined for n=0.) In the same question, the positive constants a and b being sought (a in particular!) may be fractional. My apologies for any confusion.
Sep 27 --- Midterm exam date: The midterm exam will take place on Friday Oct 27, 3-5pm, in room HW 215.
Sep 27 --- Solutions to Assignment #1: ... are now posted in the Handouts section of this document.
Sep 27 --- Assignment #2: ... is now posted in the Handouts section of this document.
Sep 20 --- Putnam exam training sessions: Training sessions for students wanting to write the Putnam Mathematics Competion take place Thursdays 2-4pm in Room H 310. They start this Thursday, Sept 21. Further information is available from Raymond Grinnell grinnell@utsc.utoronto.ca
Sep 12 --- Assignment #1: ... is now posted in the Handouts section of this document.
Sep 7: Welcome to CSCB36. Tutorial 1 (scheduled for Fri 10-11) has been canceled. Affected students must have received notification from the registrar's office. There is now only one tutorial for this course, on Fri 11-12.
There will be a tutorial on the first week (Fri Sep 15). The first tutorial will cover selected parts of Chapter 0.
The lecture notes are now available for purchase from room SW 625 during business hours ($15, exact change please!).
To view these handouts you will need access to the Acrobat Reader. If your machine does not already have this software, you can dowload it for free by following this link .