Graduate Algorithms

The much awaited final is here. There are 6 problems, and all must be solved. Each problem is worth 20 points, and I’ll normalize to 100 later on.

The final is due Tuesday Dec 11 @ 5pm. You may submit the solution electronically or physically (if the latter, slide it under my door). As usual, this post will be the clearing house for question, and you can always email me directly.

The LaTeX for the final is here.

Good luck !

The stats for this homework are somewhat skewed because of the fewer number of submissions.

Average: 32.1
Max: 46
Min: 0
Median: 34

Stats for HW4:  Max = 50, Min = 26.5, Average = 39.29, Median = 39.5 (or some number in the interval between 36 and 43, for those of you who were giving me a hard time last week :))

These are questions really about the next incarnation of the class: you’ll of course be able to put in comments in the teaching evals, but I had my own questions:

• I want to introduce a programming element into the class, and came up with a couple of ideas
  • one programming question in each assignment
  • one full assignment with purely programming questions (probably towards the end of the semester)
  • a project (in lieu or in addition to a final) that would involve programming (some kind of web demo/algorithm comparison etc)

  Which of these do you think would be most useful ? Moreover, what languages are you comfortable programming in. A web demo is probably limited to Java/Flash, but other assignments could be in other forms.

• I know of suggestions you’ve made about topics to be covered. How about topics we *did* cover ? Was the distribution of time/progression of material to your liking, or are there things you’d change (”remove this”, “spend more time on that” etc).

Last lecture ! Here are some of the things we covered today:

• I talked about computational geometry and output sensitivity. In particular, I mentioned convex hull algorithms, and how to make them optimally output sensitive.
• Next, we looked at LP-duality, and how the max-flow min cut theorem can be viewed as a special case of general LP-duality
• Online algorithms are fun to think about, especially the rent-buy ski problem, and the parking lot problem.
• Finally, we looked at amortized analysis, and why it’s good to double every time you reallocate a growing array.

Lecture notes for today’s lecture.

I drew on many sources to cobble together material for this lecture.

• Quantum Computing (lecture notes) by Dave Bacon (the Quantum Pontiff)
• Quantum Computation (lecture notes) by Umesh Vazirani
• Quantum Computing and Quantum Information, by Nielsen and Chuang.