CSC238F - Discrete Mathematics for Computer Science  Fall 1999


Instructor: Daniel Panario,   daniel@cdf.toronto.edu
==========

Home page for the course: 
========================

http://www.cs.toronto.edu/~daniel/teaching/238/index.html


Lectures: Mondays and Fridays from 10:10 to 11:00 in MP 103.
========

Tutorials: Wednesdays from 10:10 to 11:00 in 
=========

 ---------------------------- ----------------------
| Tutor Name             |  Place    | Student name |
 ---------------------------------------------------
| Catherine Stinson      | (LM 159)  | A - C        |
| Luis Dissett           | (MP 118)  | D - J        |
| Mohammad Salavatipour  | (LM 157)  | K - L        |
| Theodoulos Garefalakis | (LM 123)  | M - R        |
| Zongpeng Li            | (LM 155)  | S - Z        |
 ---------------------------------------------------

Office hours: 
============  

Fridays from 12:10 to 1:00 PM in SF2302D. Tutors will have office 
hours on Mondays before the assignments are due (Mondays Oct. 4, 
Oct. 18, Nov 8, Nov 22, Dec. 6), from 4:10 to 6:00 PM in SF3207.


Textbook: 
========

There is no textbook for the course. We will use Prof. Vassos 
Hadzilacos' Course Notes.


Other books for reference: 
=========================

R. Grimaldi, "Discrete and Combinatorial Mathematics",
Addison-Wesley, 4th ed., 1999.

K.H. Rosen, "Discrete Mathematics and its Applications",
McGraw Hill, 2nd ed., 1991.


Course Outline:
==============

Induction, program correctness [3 weeks].

    The principle of mathematical induction. Recursive definitions,
    structural induction. Applications of induction to correctness 
    proofs of inductive and recursive algorithms. 

Recurrence relations [3 weeks].

    Solution of recurrence equations. Application to the time 
    complexity of divide and conquer algorithms.

Elementary logic] [4 weeks].

    Introduction to propositional and predicate logic. Truth tables,
    tautologies, logical implication and logical equivalence.

Finite state automata [3 weeks].

    Regular expressions. Finite state automata. Equivalence of 
    finite state automata and regular expressions.


Marking Scheme: 
==============

5 Assignments at 8% each      40%
Term Test                     20%
Final Exam                    40%
                             ----
                             100%

To pass the course, you must receive at least 35% on the final exam.


Schedule: 
========

First lecture - September 13

 ----------------------------------------------------------------
| Assignment | Hand-out Date | Due Date    | Contents    | Worth |
 ----------------------------------------------------------------
|    1       | September 22  | October 6   | Induction   |  8%   |
|    2       | October 6     | October 20  | Recurrences |  8%   |
|    3       | October 27    | November 10 | Logic       |  8%   |
|    4       | November 10   | November 24 | Logic       |  8%   |
|    5       | November 24   | December 8  | Automata    |  8%   |
 ----------------------------------------------------------------


Midterm test - October 27

Last date to drop - November 5 

Last lecture - December 10

Final exam - December 13 - 21, 1999.


Assignments are due at the beginning of tutorial.
Graded assignments and test will be handed back 
in tutorial.

See the webpage of the course for the policies on 
plagiarism and lateness.