Comments on: Final Exam http://apollonius.cs.utah.edu/classes/algorithmsf07/2007/12/07/final-exam/ Suresh Venkatasubramanian // MEB 3105 // MW 1045-1205 Tue, 24 Nov 2009 03:00:07 +0000 http://wordpress.org/?v=2.5.1 By: admin http://apollonius.cs.utah.edu/classes/algorithmsf07/2007/12/07/final-exam/#comment-186 admin Tue, 11 Dec 2007 21:09:38 +0000 http://apollonius.cs.utah.edu/classes/algorithmsf07/2007/12/07/final-exam/#comment-186 nope, sorry. nope, sorry.

]]> By: Lost in Vegas http://apollonius.cs.utah.edu/classes/algorithmsf07/2007/12/07/final-exam/#comment-185 Lost in Vegas Tue, 11 Dec 2007 19:38:28 +0000 http://apollonius.cs.utah.edu/classes/algorithmsf07/2007/12/07/final-exam/#comment-185 Hello Prof, I am still lost in Vegas(prob 1)! Could you make at least one question optional? Hello Prof, I am still lost in Vegas(prob 1)! Could you make at least one question optional?

]]> By: admin http://apollonius.cs.utah.edu/classes/algorithmsf07/2007/12/07/final-exam/#comment-184 admin Tue, 11 Dec 2007 16:18:58 +0000 http://apollonius.cs.utah.edu/classes/algorithmsf07/2007/12/07/final-exam/#comment-184 no no. there isn't a compact closed form as far as I know. if you find one, more power to you. I only mentioned the lack of a closed form so people don't go crazy trying to find one. Here's an example of an answer that isn't a closed form, but it sort of what i'm talking about: E[T] = \sum_0^N g(x)^3 It's not a closed form soln because of the summation, but it only involves N and g(x) no no. there isn’t a compact closed form as far as I know. if you find one, more power to you. I only mentioned the lack of a closed form so people don’t go crazy trying to find one.

Here’s an example of an answer that isn’t a closed form, but it sort of what i’m talking about:

E[T] = \sum_0^N g(x)^3

It’s not a closed form soln because of the summation, but it only involves N and g(x)

]]> By: CarrotPhobia! http://apollonius.cs.utah.edu/classes/algorithmsf07/2007/12/07/final-exam/#comment-183 CarrotPhobia! Tue, 11 Dec 2007 10:07:54 +0000 http://apollonius.cs.utah.edu/classes/algorithmsf07/2007/12/07/final-exam/#comment-183 Should we obtain a closed form for Carattopia problem, would we receive no carrots(points)? Does a closed form strictly not exist? Should we obtain a closed form for Carattopia problem, would we receive no carrots(points)? Does a closed form strictly not exist?

]]> By: admin http://apollonius.cs.utah.edu/classes/algorithmsf07/2007/12/07/final-exam/#comment-182 admin Tue, 11 Dec 2007 06:19:57 +0000 http://apollonius.cs.utah.edu/classes/algorithmsf07/2007/12/07/final-exam/#comment-182 You don't really have to. Think about what 6.1 is telling you. You don’t really have to. Think about what 6.1 is telling you.

]]> By: Sarvani http://apollonius.cs.utah.edu/classes/algorithmsf07/2007/12/07/final-exam/#comment-181 Sarvani Tue, 11 Dec 2007 06:18:05 +0000 http://apollonius.cs.utah.edu/classes/algorithmsf07/2007/12/07/final-exam/#comment-181 6.4 : Show that there are at most sqrt(n) augmenting paths remaining ... Can we assume these augmenting paths are vertex disjoint too? 6.4 : Show that there are at most sqrt(n) augmenting paths remaining … Can we assume these augmenting paths are vertex disjoint too?

]]> By: admin http://apollonius.cs.utah.edu/classes/algorithmsf07/2007/12/07/final-exam/#comment-180 admin Tue, 11 Dec 2007 05:51:29 +0000 http://apollonius.cs.utah.edu/classes/algorithmsf07/2007/12/07/final-exam/#comment-180 remember, the first edge is NOT from the matching. that breaks the apparent symmetry between M and M' remember, the first edge is NOT from the matching. that breaks the apparent symmetry between M and M’

]]> By: Sarvani http://apollonius.cs.utah.edu/classes/algorithmsf07/2007/12/07/final-exam/#comment-179 Sarvani Tue, 11 Dec 2007 03:53:11 +0000 http://apollonius.cs.utah.edu/classes/algorithmsf07/2007/12/07/final-exam/#comment-179 Not clear about the matching with respect to M (I did read the previous blog). If an augmenting path alternates between edges in M and M', then we cannot call it an augmenting path wrt to M or M'?. An augmenting path wrt M must hence have edge only from M? Not clear about the matching with respect to M (I did read the previous blog). If an augmenting path alternates between edges in M and M’, then we cannot call it an augmenting path wrt to M or M’?. An augmenting path wrt M must hence have edge only from M?

]]> By: admin http://apollonius.cs.utah.edu/classes/algorithmsf07/2007/12/07/final-exam/#comment-178 admin Tue, 11 Dec 2007 03:44:02 +0000 http://apollonius.cs.utah.edu/classes/algorithmsf07/2007/12/07/final-exam/#comment-178 well an augmenting path is a *path* so by defn there are no repeated vertices. I mean that two augmenting paths do not share common vertices well an augmenting path is a *path* so by defn there are no repeated vertices. I mean that two augmenting paths do not share common vertices

]]> By: Sarvani http://apollonius.cs.utah.edu/classes/algorithmsf07/2007/12/07/final-exam/#comment-177 Sarvani Tue, 11 Dec 2007 03:30:41 +0000 http://apollonius.cs.utah.edu/classes/algorithmsf07/2007/12/07/final-exam/#comment-177 When you say vertex disjoint augmenting paths : do you mean that an augmenting path has no vertex repeated or that two augmenting paths do not have a common vertex? When you say vertex disjoint augmenting paths : do you mean that an augmenting path has no vertex repeated or that two augmenting paths do not have a common vertex?

]]>