CSE 312 - Foundations of Computing II

University of Washington Department of Computer Science & Engineering

CSE 312 - Foundations of Computing II - Spring 2011

CSE Home

About Us

Contact Info

Instructor: Pedro Domingos (pedrod at cs dot washington dot edu)
Office hours: Fridays 2:30-3:20, CSE 648 TA: Aniruddh Nath (nath at cs dot washington dot edu)
Office hours: Wednesdays 3:30-4:20, CSE 218

TA: Boris Kogon (boris at cs dot washington dot edu)
Office hours: Mondays 3:30-4:20, CSE 216

Lectures: Mon, Wed, Fri 1:30-2:20 in MGH 241
Sections: Thu 1:30-2:20 in EEB 045, 2:30-3:20 in EEB 054

Schedule

Week	Dates	Topics & Lecture Notes	Readings
1	March 28-April 1	Introduction, counting	Rosen 5.1-5.5, 7.5
2	April 4-8	Intro to probability, conditional probability and Bayes' theorem, independence	Bertsekas Ch. 1
3	April 11-15	Random variables and expectation, variance and binomial distribution, discrete distributions	Bertsekas Ch. 2
4	April 18-22	Continuous distributions, normal and exponential distributions, joint distributions	Bertsekas Ch. 3
5	April 25-29	Independent random variables, conditional distributions, covariance	Bertsekas Ch. 3 & 4
6	May 2-6	Correlation and conditional expectation, tail bounds, central limit theorem	Bertsekas Ch. 4 & 5
7	May 9-13	Parameter estimation, maximum likelihood, Bayesian estimation	Bertsekas Ch. 8 & 9
8	May 16-20	Machine learning, divide and conquer	Dasgupta Ch. 2
9	May 23-27	Dynamic programming	Dasgupta Ch. 6
10	May 30-June 3	NP-completeness	Dasgupta Ch. 8 & 9

Textbooks

Dimitri Bertsekas and John Tsitsiklis, Introduction to Probability, 2nd Ed., Athena Scientific, 2008 (required).
Sanjoy Dasgupta, Christos Papadimitriou and Umesh Vazirani, Algorithms, McGraw-Hill, 2008 (required; free online).
Kenneth Rosen, Discrete Mathematics and its Applications, 6th. Ed., McGraw-Hill (recommended).

Assignments

There will be four assignments, each worth 16% of the total grade. The final exam will be worth 36%.

Assignment 1, handed out April 1, due April 15.
Assignment 2, handed out April 15, due April 29.
Assignment 3, handed out April 29, due May 13.
Assignment 4, handed out May 13, due May 27.

The final will be on Monday, June 6, from 2:30 pm to 4:20 pm in MGH 241.

Course Administration and Policies

Course mailing list: cse312a_sp11@uw.edu. Archive.
Assignments will be done individually unless otherwise specified. You may discuss the subject matter with other students in the class, but all final answers must be your own work. You are expected to maintain the utmost level of academic integrity in the course.
Assignments are due before class on the due day. Assignments may be handed in up to a week late, at a penalty of 10% of the maximum grade per day.
Comments can be sent to the instructor or TAs using this anonymous feedback form.

Department of Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA 98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX

Instructor: Pedro Domingos (pedrod at cs dot washington dot edu) Office hours: Fridays 2:30-3:20, CSE 648	TA: Aniruddh Nath (nath at cs dot washington dot edu) Office hours: Wednesdays 3:30-4:20, CSE 218
	TA: Boris Kogon (boris at cs dot washington dot edu) Office hours: Mondays 3:30-4:20, CSE 216