Frequently asked questions
Final assignment
Question – how do I get 10 point font and 1 inch margins?
Answer –
\documentclass[10pt]{article}
\usepackage[margin=1in]{geometry}
Question – what form should everything be in?
Answer – the draft should be a single PDF prepared in LaTeX. (It can be a bulleted list/outline or complete paragraphs, whatever works for you to start refining your thinking.) Same for the final writeup. The slides should be separate, and I prefer PDF for those too, but it doesn’t matter how you make them (google slides, keynote, your favorite tablet app, or even dreaded powerpoint if you must).
Midterm 2
Question – what if I have a tie for the most important pages?
Answer – if you can’t break a tie, just say so!
Question – When doing linear algebra operations, I keep getting funky numerical answers with notation like + 0.j. What’s that about?
Answer – Some numerical imprecision might cause your answers to come out with minuscule imaginary parts. If you use np.round(np.real( ),6), say, you’ll get the real part rounded to six digits.
Question – I have a matrix that describes movement around the graph. How do I handle the teleportation probability together with the matrix?
Answer – Modify the matrix to include the teleportation probability. Since you’ll have to vary p as part of the problem, you should do this by working p into the matrix– you’ll have to figure out what the transition probability between vertices should be if they are connected by a link, and if they’re not. Leaving p as a parameter in the construction makes it easy to change later.
Question – help! Linear algebra is not working!
Answer – One very annoying problem is that you have to be sure that the type is a matrix in order to do matrix operations correctly. So be sure that you’ve got np.matrix() and not np.array() to get the matrix-vector products to come out right.
HW6
Question – What’s the dynamical system in the stock market example?
Answer – image here.
Question – On #1, I’m getting strange results when I enter the contracting eigenvector.
Answer – Remember that with computers, there’s a lot of numerical approximation going on! Using your paper and pencil linear algebra skills, try solving for the eigenvectors and confirm what would happen if you applied M^n to the exact eigenvectors. Now consider that when you use decimals, it’s an approximation. Try using more decimal places or fewer decimal places and see how this changes the answer.
Question – For the scrabble experiment, how can I report on the accuracy?
Answer – Up to you! But one approach would be to write some supplementary code that counts the number of times that (running average minus true answer) is less than a threshold. Then you can see how the experiment parameters relate to the accuracy. (How long do you have to run to EVER get within a certain accuracy? How long to you have to run to USUALLY get within a certain accuracy? How much does your answer change when you re-run with the same parameters?)
HW4
Question – I’m getting solver errors in Part 1!
Answer – try setting your solver to ECOS, by replacing prob.solve() with prob.solve(solver='ECOS')
Question – What is a plain English explanation of “complementary slackness”?
Answer – At the simplest level, it says that the primal inequalities are binding exactly where the corresponding dual inequalities are slack.
That is, the primal problem has n decision variables (which typically have to be ≥0) and m additional constraints. The dual problem has m decision variables that match up one-to-one with the constraints, and n constraints that match up one-to-one with the decision variables. The Duality Theorem tells you that there’s a simultaneous optimum z* for both primal and dual. Complementary slackness tells you that out of the m+n pairs of inequalities, each is binding for either the Primal or the Dual but not both.
Example: suppose your initial problem had the inequality 2x_1+x_2+5x_3≥6. You might use y_1 in your dual problem to denote the coefficient you’re multiplying this by. Then the corresponding inequality in the dual program would be y_1≥0. When you solve for the simultaneous optima x* and y*, one of these inequalities should actually obtain equality and the other should not!
Question – In the stack-based solution for branch and bound, what is a “stack”?
Answer – In theoretical CS, a stack is a data type that serves as a memory list (see wikipedia). Think of it as a pile that you can either add things to or pull something off the top of!
Midterm 1
Question – How much explanation is expected? How long should the report be?
Answer – it’s a report, not a problem set, so you need to write persuasively, which takes complete sentences. Include pictures as needed and only include the code that you have something to say about. But code outputs are welcome. To give you a sense of length, the midterm solution set runs to 6 TeXed pages.
Question – Part II – “find a division that would be optimal for the associated linear program, as in Theorem 4” – what does this mean if the hypotheses of Theorem 4 are not satisfied?
Answer – you don’t know that 4abc are equivalent, but you can still solve the linear program described in 4c. It would be great if you’d like to explore whether 4c is equivalent to 4b and whether it satisfies the conditions in 4a, but that’s not required.
Question – Next, consider all binary allocations (where each site is allocated wholly to one side or the other). Which of those are “fair”? Am I just supposed to fine one binary allocation that is fair?
Answer – No, I want to you describe how to check the full set of all possible binary allocations and give back a complete list of those that are “fair.”