Final Exam: What to Know

The final exam will take place Monday, December 13th, in class, from 2:30-4:20pm. Just like lecture, it’s in room EEB 037.

As I said in class, the final exam will be open notes. Please limit yourself to one notebook worth of notes, along with things like the homework solutions and/or class readings, if you wish.

Here is a list of what you should know/be able to do for the final exam.

• Counting: Permutations and Combinations
• The axioms of discrete probability and how they can be used
  to derive various elementary properties (e.g. inclusion-exclusion)

• Conditional probabilities, the chain rule
• Bayes Theorem, basic Bayesian inference (e.g. the robot problem)
• The definition of independence, and the properties of independent events
• The definition of a random variable and the probability mass function
• Expectation of a random variable
• Variance of a random variable
• Various types of discrete random variables:
  Uniform, Binomial, Poisson

• What tail bounds are useful for. Markov’s inequality and Chebyshev’s inequality
• The basics of continuous random variables; the probability density function and the cumulative distribution function
• The exponential and normal distributions
• The statement of the Central Limit Theorem; how it can be used
• Confidence intervals, parameter estimation
• The method of moments estimator
• Maximum-Likelihood estimation
• The definition of polynomial-time
• The basics of divide-and-conquer algorithms (be familiar with the lecture material, plus the homework problems)
• The basics of dynamic programming (same thing)

Lecture 27: Polynomial-time reductions

Slides.

Lecture 25: Dynamic Programming

Slides.

Homework #8: Algorithms

Due, in class: December 8th.

In solving the problem sets, you are allowed to collaborate with fellow students taking the class, but remember that you are required to write up the solutions by yourself or with a single partner. If you do collaborate in any way, you must acknowledge, for each problem, the people you worked with on that problem.

The problems have been carefully chosen for their pedagogical value, and hence might be similar to those given in past offerings of this course at UW, or similar to other courses at other schools. Using any pre-existing solutions from these sources, for from the web, constitutes a violation of the academic integrity you are expected to exemplify, and is strictly prohibited.

Most of the problems only require one or two key ideas for their solution. It will help you a lot to spell out these main ideas so that you can get most of the credit for a problem even if you err on the finer details.

A final piece of advice: Start working on the problem sets early! Don’t wait until the day (or few days) before they’re due.

1. Problem 1.

   [Hint: Try to setup a stable matching instance that will solve the problem.]

   

   

2. Problem 2: More inversions

   Recall the problem of finding the number of inversions. As in the lecture, we are given a sequence of n numbers , which we assume are all distinct, and we define an inversion to be a pair such that .

   We motivated the problem of counting inversions as a good measure of how different two orderings are. However, one might feel that this measure is too sensitive. Let’s call a pair of significant inversion if and . Given an -time algorithm to count the number of significant inversions between two orderings.

3. Problem 3: Dynamic Programming

   

   

   

Lecture 24: Divide & Conquer

Slides.

Homework #7: Algorithms intro

Due, in class: December 1st.

In solving the problem sets, you are allowed to collaborate with fellow students taking the class, but remember that you are required to write up the solutions by yourself or with a single partner. If you do collaborate in any way, you must acknowledge, for each problem, the people you worked with on that problem.

The problems have been carefully chosen for their pedagogical value, and hence might be similar to those given in past offerings of this course at UW, or similar to other courses at other schools. Using any pre-existing solutions from these sources, for from the web, constitutes a violation of the academic integrity you are expected to exemplify, and is strictly prohibited.

Most of the problems only require one or two key ideas for their solution. It will help you a lot to spell out these main ideas so that you can get most of the credit for a problem even if you err on the finer details.

A final piece of advice: Start working on the problem sets early! Don’t wait until the day (or few days) before they’re due.

Problems

These three problems are taken from the Dasgupta-Papadimitriou-Vazirani Algorithms book. You can find it here.

1. DPV book, Problem 2.4
2. DPV book, Problem 2.12
3. DPV book, Problem 2.16

Lecture 23: A theory of efficiency

Slides.

Lecture 22: Intro to Algorithms

Slides.

Reading for the rest of the quarter

In the rest of the quarter, we’ll see some basic algorithmic ideas, and also the basic theory of intractability and NP-completeness.

11/22 and 11/24 – Divide & conquer algorithms

Reading: Sections 2.1-2.5 of DPV.

11/29 and 12/1 – Dynamic Programming

Reading: Sections 6.1-6.4 of DPV.

12/3, 12/6, 12/8 – NP-completeness and reductions

Reading: Chapter 8 of DPV.

Looking to the future…

If you like algorithms, then you’ll want to take CSE 421 in the Winter quarter (taught by Anup Rao). If you like complexity theory (the study of problems that are hard for computers to solve), then you’ll want to take CSE 431 in the Spring quarter (taught by me). There is also the Machine Learning course CSE 446 taught next quarter by Oren Etzioni.

Lecture 21: Randomized minimum cuts

Today we talked about the following problem: Given an undirected input graph , find a smallest subset of edges such that is disconnected. We called this the Minimum Cut Problem.

We discussed a randomized algorithm.

Algorithm RMinCut

While there are more than 2 nodes remaining

1. Choose an edge e at random.

2. Contract e.

When there are exactly 2 nodes left, output all the edges between the two nodes.

Recall that we maintain a multigraph during the execution, i.e. our graph will eventually have multiple edges between pairs of nodes.

Analysis:

Let be some fixed minimum cut in . Our algorithm will output as long as no edge of is ever contracted. Let’s calculate the probability of this happening.

First, during the execution of the algorithm, every node must have degree at least (the size of the minimum cut), else cutting out that node will result in a cut of size less than .

Therefore the probability that the i-th edge contracted (i=0,1,2,…) is in can be computed:

where we recall that at the i-th stage.

So the probability that no edge of is contracted is at least

This is a telescoping product which equals .

Thus . Now running the algorithm times ensures that with probability at least 90%, we find the actual min-cut.