CSC238H, Summer 1998

CSC238H: Discrete Mathematics for Computer Science
Summer 1998

Instructor: Eric Ruppert
Office: SF 4008G
Telephone: 978-8725
Email: ruppert@cs.utoronto.ca
Office Hours: Mondays 5:30 p.m. to 7:00 p.m. in SF2304A (or by appointment)

Newsgroup: ut.cdf.csc238h

A course description from the Arts and Science Calendar.

Announcements

Exercises on regular languages

As promised on the exam review sheet, here is a list of some exercises on regular languages that might be helpful in reviewing for the exam:

pp. 224-227: #2-4,6-10,19a
pp. 233-234: #5,8,9,10,13
pp. 241-242: #1,2,5-8,11
pp. 248-249: #1,4,6,7,10-16
pp. 258-261: do a few

We didn't have time to cover pages 262-287 of the text, alas. You can use that part of the text for light summertime reading in a nice hammock or at the beach after the exam.

Course Marks

Here is a list of marks from August 11. It includes the marks for Assignment 3. The last column shows your term mark (i.e. how many of the 60 marks for term work you have earned).

About the Textbook

The text is fairly different from the one that was used in previous terms. (The changes were made in response to students' complaints about the old textbook.) About 45 pages are new, and some material from the old text was removed. The pages were renumbered for the new material, so it might be a little inconvenient for you to use an old version of the text.

Tutorial Sections

The tutorial sections have been rearranged since we now have five TAs instead of four. The division of students (according to colleges) is given below. Each week, you may go either to the standard tutorial for your college or to the remedial tutorial. Go to the remedial tutorial if and only if you are having difficulty with the current material; you will probably be bored in the remedial tutorial if you are not having too many problems with the current material. Quizzes are held in all tutorial sections.

: GB 244 for standard tutorial 1 (Erindale, New, PHE) with Geneviève Arboit (arboit@cs.utoronto.ca),
: GB 119 for standard tutorial 2 (Trinity, Innis, Scarborough) with Alex Budanitsky (abm@cs.utoronto.ca),
: GB 120 for standard tutorial 3 (Victoria, St Michael's, Engineering) with Steve Myers (myers@cs.utoronto.ca),
: SF 3109 for standard tutorial 4 (Woodsworth, University) with Eugenia Ternovskaia (eugenia@cs.utoronto.ca), and
: SF 1101 for the remedial tutorial with Joe Rainsberger (jbrains@cs.utoronto.ca).

Course Handouts

To view a course handout, select one of the following links. Most of the documents are in PostScript format. (You can use the programme called ghostview to view the PostScript files; click here to get a copy of ghostview for your computer.)

General

The course information sheet
Review of prerequisite mathematics
Handout on predicate logic
Some tests from previous terms to practice on before your midterm.
A guide to help you review for the final exam See also the list of problems for regular languages higher up on this page.
Joe's notes on recurrences. These are some solutions that Joe wrote for recurrence exercises in the textbook. He shows how to guess the solution and then he explains how to do the inductive step when proving that the guessed solution is correct. Also included is a description of applying the divide-and-conquer recurrence to find the running time of the fast multiplication algorithm you saw in tutorial a while ago. (These notes will not be handed out in class, but you should take a look at them if you want to see some more examples of how to guess the solution to a recurrence.)

Assignments and Solutions

(I have taken the solutions offline as of June 1999.)

Assignment 1 and its cover page
Solutions to Assignment 1
Comments from the markers (and the instructor) about Assignment 1. These notes include some remarks about common errors and the marking scheme.
Assignment 2 and its cover page
Assignment 2 solutions
Comments about Assignment 2 Abbreviated comments are explained here, and descriptions of common errors are also included.
Assignment 3 and its cover page. Here is the picture missing from question 6 of the assignment's PostScript file.
Solutions to Assignment 3

Quizzes and Tests

Other Web Pages

Select the following links to see web pages for some previous versions of the course. These pages include assignments, tests and solution sets.

Extra Material

A proof system for predicate logic (We won't have time to cover this proof system; I just put it here for people who are interested. These notes are by Faith Fich. For simplicity, it is assumed in these notes that there are no function symbols, but the system can be adapted to handle function symbols too.)
A challenging puzzle that will test your understanding of induction and logic. (New: This puzzle, and some related problems are discussed in Ian Stewart's Mathematical Recreations column in this month's (August 1998) Scientific American.)

Updated August 18, 1998
Send bug reports to Eric Ruppert (ruppert@cs.utoronto.ca)

CSC238H: Discrete Mathematics for Computer Science Summer 1998