image University of Washington Computer Science & Engineering
  CSE 312Wi '11:  Foundations of Computing II
  CSE Home   About Us    Search    Contact Info 

 332 Coreq.
 Schedule & Reading
 Midterm Review
 Final Review
Course Email/BBoard
 Class List Archive
 GoPost BBoard
 HW #1
 HW #2
 HW #3
 HW #4
 HW #5
 HW #6
 HW #7
 HW #8
Lecture Notes
 1: Intro
 2: Counting
 3: Discrete Probability
 4: Conditional Probability
 5: Independence
 6: Random Variables; Expectation
  Distribution Summary
 7: Continuous Random Variables
  Table of the Normal CDF
 8: Avg-case & Randomized Algs
 9: Tail Bounds
 10: Limit Theorems
 11: Max Likelihood Estimators
 12: Expectation Maximization
  EM Example (.xls)
 13: Hypothesis Testing
 14: Algorithms and P
 15: More Algorithms: Alignment
 16: NP and NP-completeness

Lecture:  MUE 153 (schematic) MWF 1:30- 2:20 
Section A:  EEB 054 (schematic) Th 1:30- 2:20  Daniel Perelman
Section B:  EEB 054 (schematic) Th 2:30- 3:20  Leilani Battle
Section C:  MGH 238 (schematic) Th 12:30- 1:20  Milda Zizyte
Office Hours Location Phone
Instructor:  Larry Ruzzo, ruzzocs  M 12:00- 1:00  CSE 554  543-6298
TAs:  Daniel Perelman, perelmancs  W 2:30- 3:20  CSE 218 
  Leilani Battle, leibattcs  W 4:30- 5:20  CSE 218 
  Milda Zizyte, mzizytecs  Tu 3:30- 4:20  CSE 220 

Course Email: Announcements and general interest Q&A about homework, lectures, etc. The instructor and TAs are subscribed to this list. Enrolled students are as well, but probably should change their default subscription options. Messages are automatically archived. 

For fastest response, questions not of general interest should be directed to the instructor and TAs collectively via the "course staff" link at left. Individual email addresses (above) may also be used, if needed.

Discussion Board: Also feel free to use Catalyst GoPost to discuss homework, etc.

Catalog Description: Examines fundamentals of enumeration and discrete probability; applications of randomness to computing; polynomial-time versus NP; and NP-completeness.

Prerequisites: CSE 311; CSE 332, which may be taken concurrently.

Credits: 4

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, (5) the distinction between tractable and (apparently) intractable computational problems and (6) methods and appropriate reasoning for showing tractability (e.g. dynamic programming) and intractability (reduction).

Grading: Homework, Midterm, Final. Possibly some quizes. Overall weights 55%, 15%, 30%, roughly.

Late Policy: Assignments are due at the start of your quiz section on the due date, either on paper or electronically. Late papers/e-turnin will be accepted (but penalized 30%) up to the start of the next lecture; not accepted thereafter, barring major emergencies.

Extra Credit: Assignments may include "extra credit" sections. These will enrich your understanding of the material, but at a low points per hour ratio. Do them for the glory, not the points, and don't start extra credit until the basics are complete.

Collaboration: Homeworks are all individual, not group, exercises. Discussing them with others is fine, even encouraged, but you must produce your own homework solutions. 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.



A First Course in Probability (8th edition), Sheldon M. Ross, Prentice Hall, 2009. (Available from U Book Store, Amazon, etc.)

Online. The last few weeks of the quarter will use the following, available free online:

Algorithms, by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani

Reference. (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)):

Discrete Mathematics and Its Applications, (sixth edition) by Kenneth Rosen, McGraw-Hill, 2006. Errata. (Available from U Book Store, Amazon, etc.)

Portions of the CSE 312 Web may be reprinted or adapted for academic nonprofit purposes, providing the source is accurately quoted and duly credited. The CSE 312 Web: © 1993-2011, Department of Computer Science and Engineering, University of Washington.

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