tag:blogger.com,1999:blog-3722233.post2880896609363558848..comments2024-03-18T23:13:09.570-05:00Comments on Computational Complexity: America's Most Important AlgorithmLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-3722233.post-45241258172314223772011-01-02T17:03:59.507-06:002011-01-02T17:03:59.507-06:00The Apportionment Act of 1911 set that number in p...The Apportionment Act of 1911 set that number in place (population of around 90 million). The Reapportionment Act of 1929 kept it at that number (population around 120 million). The Apportionment Act of 1941 basically locked it in as that (population around 130 million). The number did increase temporarily when Alaska and Hawaii joined (they each got one representative without any existing state losing one) but the total count went back down to 435 after the 1960 Census (population around 180 million) and is still at that number today (population around 310 million).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42402595704209572882010-12-31T05:16:00.317-06:002010-12-31T05:16:00.317-06:00The number of House seats is fixed at 435 even if ...The number of House seats is fixed at 435 even if the national population doubles? That can't be right.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62891807965098813972010-12-24T05:36:55.714-06:002010-12-24T05:36:55.714-06:00the number of seats can be computed in o(n) space....the number of seats can be computed in o(n) space. It first needs to compute the truncated integer according to proportion (of remainder using plus one seat rule). Then it needs to add all these truncated integers, to compute the still remaining number of seats r. Then it needs to check if the score m/sqrt(n(n+1)) is in the first r scores. This can be done using just O(1) numbers to keep the intermediate scores and counters.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87355961231523596072010-12-23T07:32:56.329-06:002010-12-23T07:32:56.329-06:00Well, i used this method on Indian Census data 200...Well, i used this method on Indian Census data 2001 .. the results : http://goo.gl/Bq6EsVenkathttps://www.blogger.com/profile/09538725607137736665noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32051605676352543842010-12-22T18:48:04.973-06:002010-12-22T18:48:04.973-06:00@Tyson: The Huntington-Hill method avoids the Alab...@Tyson: The Huntington-Hill method avoids the Alabama paradox and the population paradox, while violating the quota rule. Given that one cannot avoid losing one of the above three properties, this is about as good as one can hope for. See<br /><br />http://www.ams.org/samplings/feature-column/fcarc-apportionii3<br /><br />The fact that one has monotonicity (i.e. no Alabama or population paradox) more or less eliminates the opportunity for 'gaming' the system as raised by the first anonymous; assuming that states desire as many seats as possible, the incentive is always to report the population as fully as possible.Terryhttps://www.blogger.com/profile/10186436058521523236noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54881496450860570292010-12-22T18:23:07.152-06:002010-12-22T18:23:07.152-06:00I'm wondering how that video was made....it wo...I'm wondering how that video was made....it would be cool to have something like that for other algorithmsYaroslav Bulatovhttps://www.blogger.com/profile/06139256691290554110noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4677523110815539052010-12-22T17:14:42.622-06:002010-12-22T17:14:42.622-06:00Except that this algorithm is probably not "f...Except that this algorithm is probably not "fair" (in the same sense that Arrow proved that no voting system is fair) because of the <a href="http://en.wikipedia.org/wiki/Apportionment_paradox" rel="nofollow">Apportionment paradox</a>.Tyson Williamshttp://pages.cs.wisc.edu/~tdw/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-6716764111571816092010-12-22T14:59:19.456-06:002010-12-22T14:59:19.456-06:00If you follow this algorithm by hand, (as was prob...If you follow this algorithm by hand, (as was probably done in 1940), then it is clear that only one value of rep[i] changes in each iteration and only one update is required.<br /><br />Probably the first person who implemented this algorithm saw the efficient way to implement it.Davidhttps://www.blogger.com/profile/13818371550669837787noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55410789466410675402010-12-22T12:01:57.963-06:002010-12-22T12:01:57.963-06:00No, "j" does not have to appear in the b...No, "j" does not have to appear in the body of that loop.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68146755152909255942010-12-22T10:41:15.458-06:002010-12-22T10:41:15.458-06:00Should you be using j somewhere in the for loop?Should you be using j somewhere in the for loop?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89408783999874803792010-12-22T09:07:14.616-06:002010-12-22T09:07:14.616-06:00I have a couple of questions.
1) What happens whe...I have a couple of questions.<br /><br />1) What happens when the populations of all states are equal?<br /><br />2) Is it possible for a state to "rig up" its population so that it can have desired number of representatives? What happens if all states try to do this? - Do we have a game theoretic framework?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41895120447227424962010-12-22T05:56:46.936-06:002010-12-22T05:56:46.936-06:00It makes a nice programming exercise for an introd...It makes a nice programming exercise for an introductory algorithms and data structures course. If someone wants to use it, description and data files can be found at tinyurl.com/345l72t .<br /><br />Data files include US census data, but as you point out, they are actually too small. The files called huge-*.in are fictional population data for planets, the largest of these distributes the 1 million seats in the galactic senate among 200,000 planets. (I had fun with this. The names of the planets are created by an algorithm similar to what was used in the 1984 computer game Elite, picking random digrams from “..LEXEGEZACEBISOUSESARMAINDIREA.ERATENBERALAVETIEDORQUANTEISRION”.)Anonymousnoreply@blogger.com