CSE 312: Foundations of Computing II, Fall, 2018

| important announcements] | discussion board | office hours | general course information | prior incarnations of course | acknowledgements

Important Announcements

Schedule and Handouts

, ,
Date Topic Reading
Wed, Sept 26 Administrivia and counting Berkeley notes

[Rosen 5.1-5.5], [LLM, chap 15], [BT, 1.6]
Fri, Sept 28 More counting
Mon, Oct 1 Finish counting (see Sept 28 slides)

Intro discrete probability

(See Berkeley intro probability slides)

 Berkeley notes

[Rosen, chap 6][BT, chap 1, especially 1.3-1.4] [LLM, chap 17]
Wed, Oct 3 Events and practice with probability
Fri, Oct 3

Conditional probability

(See Berkeley conditional probability slides)

 Berkeley notes, [BT, chap 1.5, 2.1-2.3] [LLM, chap 17]
Mon, Oct 8 More conditional probability, independence See Friday reading + [BT, 2.4]
Wed, Oct 10 Bayes Theorem
Friday, Oct 12 More on independence Berkeley notes
Monday, Oct 15 More independence, Naive Bayes Intro Random Variables [Rosen 6.2, 6.4][BT, Chap 2], [LLM, chap 18]
Wed, Oct 17 Random vars and expectationBerkeley notes
Fri, Oct 19 Linearity of expectation
Mon, Oct 22 Variance Berkeley notes
Wed, Oct 24 More variance, independence of r.vs + start zoo Berkeley notes
Fri, Oct 26 More r.v.s, conditional expectation [LLM, chap 18]

especially Sections 18.4.5-18.4.6
Mon, Oct 29 More Poisson + LTE
Wed, Oct 31 Randomized quicksort Notes from CMU
Fri, Nov 2 Stream processing and heavy hitters (only slides 1-10) Heavy hitter notes from Stanford

+ Markov's Inequality
Mon, Nov 5 Heavy hitters Princeton notes on universal hashing (sections 2-4)
Wed, Nov 7 Joint distributions plus some slides [BT] 2.5
Fri, Nov 9 midterm
Wed, Nov 14 Continuous random variables (plus slides) Berkeley notes
Fri, Nov 16 Continue continuous [BT, 3.4-3.6]
Mon, Nov 19 Tail bounds and limit theorems

(Some pictures)

Berkeley Notes (Chebychev's Inequality + LLN)

+ Berkeley Notes (CLT)
Wed, Nov 21 Practice with continuous r.v.s
Mon, Nov 26 CLT addendum + more continuous practice + intro MLE [BT, 9.1] (in actual book) and an introduction
Wed, Nov 28 More MLE Some notes from Penn (we didn't cover method of moments)
Fri, Nov 30 Finish MLE + start distinct elements
Mon, Dec 3 Continue distinct elements

Course Information

Lectures time and place: MWF 9:30-10:20am, in MLR 301
Sections time and place: AA: Thursday 12:30 -- 1:20 in MGH 234; AB: Thursday 1:30 -- 2:20 in MGH 287; AC: Thursday 2:30 -- 3:20 in MGH 228; AD: Thursday 11:30-12:20 in JHN 175

Instructor: Anna Karlin, CSE 594, tel. 543 9344
Office hours: Thursdays: 9:00-10am, CSE 594, and by appointment -- just send email to Anna.

Teaching assistants: Send email to instructor + TAs

All Office Hours (in Allen Center)

Monday office hours Tuesday office hours Thursday office hours Friday office hours
3:00-4:00pm: Anna, CSE 594

4:00-5:00pm: Cheng, 3rd floor breakout

1:30-2:30pm: Sierra, CSE 306

5:00-6:00pm: Andrew, 4th floor breakout

6:00-7:00pm: Nathan, CSE 306

9:00-10:00am: Anna, CSE 594 2:00-3:00pm: Kushal, 2nd floor breakout

3:00-4:00pm: Boyan, 5th floor breakout

Course evaluation and grading:

Textbooks:

Learning Objectives:

Course goals include an appreciation and introductory understanding of (1) methods of counting and basic combinatorics, (2) the language of probability for expressing and analyzing randomness and uncertainty (3) properties of randomness and their application in designing and analyzing computational systems, (4) some basic methods of statistics and their use in a computer science & engineering context, and (5) introduction to inference.

Class mailing list:

The mailing list is used to communicate important information that is relevant to all the students. If you are registered for the course, you should automatically be on the mailing list.

Send email to entire class.

Academic Integrity and Collaboration:

Homeworks are all individual, not group, exercises. Discussing them with others is fine, even encouraged, but you must produce your own homework solutions. Also, please include at the top of your homework a list of all students you discussed the homework with. We suggest you follow the "Gilligan's Island Rule": if you discuss the assignment with someone else, don't keep any notes (paper or electronic) from the discussion, then go watch 30+ minutes of TV (Gilligan's Island reruns especially recommended) before you continue work on the homework by yourself. You may not look at other people's written solutions to these problems, not in your friends' notes, not in the dorm files, not on the internet, ever. If in any doubt about whether your activities cross allowable boundaries, tell us before, not after, you turn in your assignment. See also the UW CSE Academic Misconduct Policy, and the links there.

acknowledgements

Thanks to previous instructors of this course (James Lee, Larry Ruzzo, Martin Tompa and Pedro Domingos) for the use of their slides and other materials. (Some of these were in turn drawn from other sources.) We have also drawn extensively on materials from CS 70 at Berkeley, "Mathematics for Computer Science" at MIT, and "Great Theoretical Ideas in Computer Science" at CMU.