Summer 1998

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.

- 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

- 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).

- 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.)

- 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

- Quiz 1
- Quiz 2 and its solution
- Quiz 3 and its solution
- Quiz 4
- Midterm test and its solution
- Quiz 5
- Quiz 6
- Quiz 7 and its solution
- Quiz 8
- Final Examination

- 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.)

Send bug reports to Eric Ruppert (ruppert@cs.utoronto.ca)