From ftl@math.mit.edu Fri Jul 7 12:13:58 1995 Return-Path: Date: Thu, 6 Jul 1995 09:49:25 -0400 From: "F. Tom Leighton" To: karger@theory.lcs.mit.edu Subject: 6.042 revised sched Cc: koods@theory.lcs.mit.edu Hi David, here is the revised set of lecture assignments: DK: L1-5 (9/7-21), L13-17 (10/24-11/7, but Ravi gives L13 due to FOCS), L21-23 (11/21-11/30) TL: L6-12 (9/26-10/19), L18-20 (11/9-16), L24-26 (12/5/12) Exams: 10/11, 11/15, 12/6, Final TBA This leaves us each with 13 lectures to prepare, although Ravi will be giving one for you while you are away. It would probably be good to get the first batch of 9 Lectures ready soon since that is where we will be doing the greatest amount of change. They also come first... --Tom From ftl@math.mit.edu Fri Jul 7 12:15:26 1995 Return-Path: Date: Fri, 7 Jul 1995 09:27:26 -0400 From: "F. Tom Leighton" To: koods@theory.lcs.mit.edu Subject: Re: 6.042 revised sched Cc: karger@theory.lcs.mit.edu Earlier is tough. I figured that we would grade it that night and return it in recitation on drop date. --Tom Thanks, Tom From ftl@math.mit.edu Fri Jul 7 12:15:42 1995 Return-Path: Date: Fri, 7 Jul 1995 11:26:20 -0400 From: "F. Tom Leighton" To: karger@theory.lcs.mit.edu, koods@theory.lcs.mit.edu Subject: proposed lecture schedule Hi David, Here is a rough outline. The key thing is to now prepare lectures 1-7. The key issue here is whether you will need an extra lecture on induction and relations or if we'll be able to use Lectures 6-7 for a segment on graph theory. Try plotting out some lectures and I'll go over them with you. I'll have a good idea about how long things will take. I think that we can assume that sections 1.1-1.5 are already known to most of the students. Those that don't will be expected to read it early on so you don't have to waste too much class time with that stuff. I'll be away for most of the next 2 weeks. We can also talk at the ARPA mtg. best, Tom From ftl@math.mit.edu Fri Jul 7 12:15:54 1995 Return-Path: Date: Fri, 7 Jul 1995 11:26:39 -0400 From: "F. Tom Leighton" To: karger@theory.lcs.mit.edu, koods@theory.lcs.mit.edu Subject: lecture outline Here is a list of lecture topics for Fall 1995. The first part needs fleshing out still and we have to prep rec notes as well. Part I: Basic Structures and Proof Techniques Week1 (L1, Rec): Administrivia, Statements, Quantifiers, and Basic proof techniques. (Assume 1.1-1.3 as background, cover 3.1.) Week2 (L2-3, Rec): Induction. Include gcd example (touching on integer arithmetic/number theory as problem domain) but don't get too fancy with sums which will come later. (Give some of ch2 as background reading on number theory.) Cover well-ordering, strong, weak induction (perhaps not showing equivalence in class. Cover 3.2-3.5 of text. Application to program verification would seem to be a nice example--cite examples of plane crashes, network disasters, killer CATscanners as the reason proofs need to be correct. Week3 (L4-5, Rec): Sets and relations. Assume 1.4-1.5 as background reading and cover much of ch6, including representation as graphs, posets, matrices. Cover matrix multiplication application. Week4 (L6-7, Rec): OPTION 1: USE THIS TIME TO ADD A LECTURE TO THE INDUCTION LECTURES AND THE RELATIONS LECTURES OR OPTION 2: cover some topics in graph theory. Week5 (L8-9, Rec): Functions, Pigeonhole Principle, cardinality through bijections, countability, infinite sets. (Fleshed out from Fall 94 notes.) Part II Counting and Combinatorics Week6 (L10, Rec): summation methods, Stirling's formula, asymptotic notation. (Fall 94 notes except asymptotic notation swapped into recitation.) Week7 (L11-12, Rec): recurrences (see fall notes 94) Week8/9 (L13-15, Rec): combinatorics (see fall notes from 94) Week9/10 (L16-17, Rec): generating functions (fall 94 notes) Part III Discrete Probability Week10-15 (L18-26, 3 Rec): probability (fall 94 notes) Exams after each part except for third exam which will miss the last 3 probability lectures. Also a final. New material covered in recitation. Practice for exams and HW covered in Tutorial and special study gatherings before exams.