Foundations of Computing, II

CSE 312: Foundations of Computing II, Fall, 2016

Important Announcements

Our midterm will be on November 9.
Submit homework solutions on canvas
Videos of lectures: from the spring 2015 incarnation in the course (in reverse order; this is from a different instructor, so will be different in places) and from MIT (lectures 16 - 25)
Quick guide for getting started with latex, a typesetting system that is very useful for typesetting mathematics.

Schedule and Handouts

Date	Topic	Reading	Homework	Section materials
Wednesday, September 28	Administrivia and counting (updated 9/30)	[Rosen 5.1-5.5], [LLM, chap 15], [BT, 1.6]	Homework 1 and solutions
Friday, September 30	More counting (also see 9/28 slides)			Section 1 worksheet and solutions
Monday, October 3	More counting
Wednesday, October 5	Intro discrete probability	[Rosen, chap 6][BT, chap 1, especially 1.3-1.4] [LLM, chap 17]	Homework 2 and solutions	Martin's notes
Thursday, October 6	Practice on discrete probability			Section 2 worksheet and solutions
Friday, October 7	More equally likely outcomes, intro cond. prob	[BT, 1.5]		Martin's notes
Monday, October 10	Conditional Probability, Bayes Theorem	[BT, chap 1.5, 2.1-2.3] [LLM, chap 17]
Wednesday, October 12	Independence	[BT, 2.4]	Homework 3 and solutions	Section 3 worksheet and solutions
Friday, October 14	Problems (also see Wednesday's slides)
Monday, October 17	Intro Random Variables	[Rosen 6.2, 6.4][BT, Chap 2], [LLM, chap 18]
Wednesday, October 19	Random vars and expectation	Random variables (by Alex Tsun)	Homework 4	Section 4 worksheet and solutions
Friday, October 21	Exp of fn of r.v. and linearity of expectation
Monday, October 24	Linearity of expectation (see 10/21 slides) + variance
Wednesday, October 26	Intro to zoo of r.v.s		Homework 5
Thursday, October 27		Notes on Naive Bayes classification	Programming Project 1 and naivebayes.zip	Section 5 worksheet and solutions
Friday, April 29	Naive Bayes Classifiers			Section 5 worksheet part 2 and solutions part 2

Course Information

Lectures time and place: MWF 9:30-10:20am, in JHN 075
Sections time and place: AA: Thursday 12:30 -- 1:20 in MGH 238; AB: Thursday 1:30 -- 2:20 in GLD 322; AC: Thursday 2:30 -- 3:20 in MEB 246

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

Teaching assistants: Send email to instructor + TAs

All Office Hours

Monday office hours Tuesday office hours Wednesday office hours Friday office hours

3:30-4:30pm: Alex, CSE 220
5:30-6:30pm: Justin, CSE 218
9-10am: Anna, CSE 594
5-6pm Saidutt, CSE 220
2:30-3:30pm: Varun, CSE 220
5-6pm Jonathan, CSE 218
2-3pm Jonathan, CSE 306

Monday office hours	Tuesday office hours	Wednesday office hours	Friday office hours
3:30-4:30pm: Alex, CSE 220 5:30-6:30pm: Justin, CSE 218	9-10am: Anna, CSE 594 5-6pm Saidutt, CSE 220	2:30-3:30pm: Varun, CSE 220 5-6pm Jonathan, CSE 218	2-3pm Jonathan, CSE 306

Course evaluation and grading:

Approximate breakdown: Weekly problem sets (altogether 35%), midterm (25%) and final (40%).
Late homework will not be accepted, barring major emergencies.

Textbooks:

[BT] (optional) Introduction to Probability (2nd edition), Dimitri P. Bertsekas and John N. Tsitsiklis, Athena Scientific, 2008 (Available from U Book Store, Amazon, etc.) 1st edition, free online
[LLM] (free online) Mathematics for Computer Science, Lehman, Leighton and Meyer. (Chapters 15, 17-20).
[DBC] (free online) OpenIntro Statistics, Dietz, Barr and Cetinkaya-Rundel.
[R] (optional) Kenneth H. Rosen, Discrete Mathematics and Its Applications, Sixth Edition, McGraw-Hill, 2007. No direct use of this, but if you already own a copy, keep it for reference. Some students have said they like its coverage of counting (Chapter 5 and 7.5, 7.6) and discrete probability (Chapter 6)).
[Ross] (optional) Sheldon Ross, Introduction to Probability Models, Academic Press. (earlier editions are fine).

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 on materials from "Mathematics for Computer Science" at MIT, and "Great Theoretical Ideas in Computer Science" at CMU, from Edward Ionides at the University of Michigan, from an offering of CS 70 at Berkeley by Tse and Wagner, and from an offering of 6.S080 at MIT by Daskalakis and Golland.