http://apollonius.cs.utah.edu/classes/algorithmsf07 Suresh Venkatasubramanian // MEB 3105 // MW 1045-1205 Sat, 08 Dec 2007 00:02:26 +0000 http://backend.userland.com/rss092 en 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 ... http://apollonius.cs.utah.edu/classes/algorithmsf07/2007/12/07/final-exam/ The stats for this homework are somewhat skewed because of the fewer number of submissions. Average: 32.1 Max: 46 Min: 0 Median: 34 http://apollonius.cs.utah.edu/classes/algorithmsf07/2007/12/07/homework-5-stats/ 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 :)) http://apollonius.cs.utah.edu/classes/algorithmsf07/2007/12/06/homework-4-stats/ 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 ... http://apollonius.cs.utah.edu/classes/algorithmsf07/2007/12/06/76/ 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 ... http://apollonius.cs.utah.edu/classes/algorithmsf07/2007/12/06/lecture-28-miscellaneous-items/ 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. http://apollonius.cs.utah.edu/classes/algorithmsf07/2007/12/03/lecture-27-quantum-computing/ In the early 80s, there was much excitement in the algorithms community about the idea of parallel machine models. The PRAM (parallel RAM), became the analysis model of choice, and in the lecture today, we'll start to see the basic theory of parallel complexity as seen on the PRAM. The ... http://apollonius.cs.utah.edu/classes/algorithmsf07/2007/11/28/lecture-26-parallel-algorithms/ The average for this assignment was a shade under 34, much lower than normal. Max was 50, min was 2, and median score was 38. http://apollonius.cs.utah.edu/classes/algorithmsf07/2007/11/28/homework-3-statistics/ When you've shown a problem is NP-hard, and designed whatever approximation you can, and still aren't close to solving a problem to the level needed, heuristics are often the next step. From an algorithms perspective, what distinguishes a heuristic from an algorithm is the lack of formal guarantees. This deficiency ... http://apollonius.cs.utah.edu/classes/algorithmsf07/2007/11/24/lecture-25-meta-heuristics/ Due date for this homework is Monday Dec 3, at 5pm. Here's the LaTeX and PDF. http://apollonius.cs.utah.edu/classes/algorithmsf07/2007/11/21/homework-5-randomization/