CSE 291 LECTURE NOTES

January 25, 2005
 
 

ANNOUNCEMENTS

I'm handing back the first assignment today.  The range of scores was 20 to 40.  Today's lecture will be devoted to comments about people's answers, common misunderstandings, and opportunities for improvement.


GENERAL COMMENTS

These comments are from the point of view that answering the questions on the 291 assignments should be approached similarly to writing a research paper.  Overall, you need to be compelling, i.e. correct, clear, and convincing.  This means that you must grab the attention of the reader, and then convince him/her that you are correct, with little effort needed on his/her part.  If the reader must do work in order to believe you are correct, at a minimum you must convince the reader immediately that what you have written is interesting. 

So, do not stop with the first version of a writeup or of an experiment.  Simplify and simplify again, until everything is clearly correct.  Double-check everything, and describe the checks briefly so the reader can understand them, to increase the chance that the reader will believe whatever your claim is.

You may collaborate to solve the problems, but your write-ups must be personal.  This means you must write your own equations, as well as your own English text.

Answers should have the right level of detail to be convincing for your intended audience.  This is a relative standard, not an absolute one.  For 291 questions, a rule of thumb is to use at least one and at most three type-set sides per question.  If you include code in a programming language, make it polished and elegant, and short and clear.

Good typesetting is important to hold the interest and the respect of the reader.  Suggestions:  Reuse some existing layout, e.g. the NIPS article style, have wide margins (unlike the assignments themselves ...), and start your answer to each question on a new page.

Mathematical writing:  Do not use formal symbols for the logic of your arguments, since this logic is only informal.  Use LaTeX math notation even for single variables and for equations that are inline in your text (I think some WYSIWYG LaTeX editors get this wrong.)  Do not use multiletter variable names.  Do use the correct standard LaTeX macros for special symbols, like \ln and \cdot for multiplication.

For your own sake, i.e. to maximize correctness and to minimize debugging time, follow good software engineering practices when you write code.  In particular, never duplicate code; instead, encapsulate it in a function, and call the function repeatedly.


NOTES ON MATHEMATICAL REASONING

When you need to prove a result, first make sure that you know exactly what should be proved.  Make the nested quantifier structure ("for all" and "there exists") of the theorem statement clear.  This is often not explicit at all in standard mathematical English.

Second, convince yourself that what you want to prove actually is true.  If you try to prove something false, there are two possibilities.  You may waste a lot of time in frustration, never finding a proof.  Alternatively, and worse, you will publish an incorrect proof!

Decompose the theorem statement into separate parts.  Once you have a clear theorem statement, as small as possible, don't try to prove it in big steps.  Subdivide the proof into small subgoals and small steps.  For example, to prove A = B, often you shouldn't start with A and "steam-roller" through to B with a series of equalities.  Instead, prove that A <= B and B <= A separately.  For more advice on solving problems and proving theorems, see the book How to Solve It by George Polya.

Often, a theorem is only true subject to several restrictions and assumptions.  When you notice one of these limitations, if you cannot revise the proof to eliminate it, you may need to make the statement of the theorem more restrictive.  In the history of mathematics, these limitations may be noticed after the theorem is first published.  For an important mathematical discovery, there can be a dialectic lasting many decades of changes to proofs, changes to the theorem statement, and changes to definitions.  For an example of this process applied to Euler's theorem about polyhedra, see the book Proofs and Refutations by Imre Lakatos.


PROBLEM 1 COMMENTS

Part a asked you to explain the notation used.  Most people did not do this; they just explained the substance of the question.  In general, do exactly what is asked; here, the point was to explain each item of notation, one by one.  Showing that you understand notation precisely is a way of showing that you understand the corresponding concepts clearly.


PROBLEM 2 COMMENTS

Here is an example of the need to justify your work at the right level of detail, where the right level is relative.  The point of the question is that Var[X-Y] = Var[X] + Var[Y], if X and Y are independent.  Since this is the central result needed, you should "unpack" it by one level of reasoning.  Explain especially anything that might be counterintuitive.  Here, explain why variances are added, when the random variables are subtracted. 

Note that for the result above, it is not necessary to assume X and Y are Gaussian.  No specific distribution is needed, just independence.

Hypothesis testing:  I spent a long time explaining the standard approach to hypothesis testing, in particular the concept of null hypothesis.  In general, your simulation should generate data according to the null hypothesis, not according to an alternative hypothesis.  Then, you use the observed data in order to set the threshold that you compare simulated data against.


PROBLEM 3 COMMENTS

Here is another example of justifying your work at the right level of detail, which is relative.  The point of the question is a couple of single lines of code in Matlab.  Since these single lines of code are not obvious, you should "unpack" them, by explaining the formulas behind the code, using equations written in LaTeX.

This is also another example of how you should answer exactly the question that is asked.  The question asked for the product of your runtime and your GHz rating.  Most people stated the runtime and the GHz rating, but not the product.


PROBLEM 4 COMMENTS

Matlab, Maple, and Mathematica will all do indefinite integrals for you, but using these systems is a mixed blessing.  The reason is that (1) you have to provide precisely the right integral as input (garbage in, garbage out) and (2) the automated answer is likely to be so complex it provides no insight.  Only human intelligence can make an answer elegant and concise, by picking useful simplifying assumptions and/or notations.

Many people provided numerical examples whose logic was excessively complicated.  Only straightforward examples are compelling.  Also, whenever possible use realistic (i.e. close to real-world) numerical values for parameter settings.  Here this means for example c = 0.02, d = 0.07, s = 0.20. 

Whenever you provide a figure, explain carefully in prose what the lessons are to be learned from the figure.  Do not show many figures; instead, pick one or two very carefully.