This work is licensed under a
Creative Commons License.
|
Wednesday, October 22, 2008
Weird Sum/ith largest/Wallet-- revisited
Posted by GASARCH
- In Richard Matthew McCutchen's Guest post he challenged the readers to figure out a certain sum. And I challenged them to help me do a better pi in html.
- KKMD (comment 3) is correct, it is the largest prime that divides n. The formal proof is here.
- pi: I originally used an & followed by pi which yields &pi
- pi: I was supposed to use & followed by pi and then a semicolon which yields π
- pi: Lance says to use < span style=" font-family:times" > & pi;</span> which yields π
- Some of the comments from the posting on ith largest of n inspire some random thoughts from me:
- Why on earth would anyone be doing a computer search for such algorithms? (for algorithms to find ith largest of n with as few comparisons as possible). One hope is that with enough empiricial evidence we may get EXACT values for how many comparisons it takes. Also, for the challenge! But YES, limited practical value. But see next point.
- Why do you think your conjecture is true? The known algorithms for finding ith largest of n take n+(i-1)log n + O(1) and begin by making comparisons pairwise. For i small this is optimal up to the O(1). So in this realm it seems likely. But what is `i small'? When finding the 10th largest out of 40 is that more like i small or like you are finding the n/4th largest element? Don't know- want to find out. Another reason to do this- when is small small?
- A commenter says there is interesting info in a Tech Report that may be hard to find. The notion of a Tech Report that is hard to find may be unfamiliar to young people. With the web it may be easier to find some unpublished papers then some published ones, depending on who the authors are and the journals are. (If someone knows where the Journal version of Barrington's paper on Bounded Width BP containing NC1 is online please let me know. Barrington does not have it on his website or know where it is online.)
- Lance recently recommended a certain wallet in this blog. On his advice I bought it and its great. What I wonder is, how big a mover and shaker is Lance? Should they have given him a free wallet since he influences others? How many others have bought it based on his recommendation? At Maryland Theory Day there was a talk about how sellers should give people of influence discounts since they will influence others to buy their product. This is not a new idea, but with modern technology it can be better targeted.
8:05 AM
# 13 comments
-
Barrington's journal paper can be found in ScienceDirect.
Journal of Computer and System Sciences
Volume 38, Issue 1, February 1989, Pages 150-164
-
At Science Direct all I can get is the abstract- not the paper itself. Anon 1---
if you can actually get the paper itself please email it to me.
bill g.
gasarch@cs.umd.edu
-
I can access the full journal version of Barrington's paper on ScienceDirect through my university's subscription. Ask your university to get better subscription access... Unfortunately, not all scientific articles are freely available (yet).
-
Or you could use the Interlibrary Loan service, Prof. Gasarch.
-
I tried Interlibrary loan-
they send me a scanned in copy that was hard to read and
missing the first two pages.
I will ask our library to get science direct (I think I have in the past- I should
ask again).
However, I am teaching a course NOW for which I want
that paper on line- so if
someone out there has it,
please email it to me.
-
Do you have a fax number? Maybe it's easier for someone to fax you a hard copy than to obtain an e-copy.
-
I want to POST it on my
course website. Hard to do
with a FAX. If someone has an e-copy it should be easy to email me the pdf file
or whatever format it is in.
-
You can't post it on your website. That's illegal: journal copyrights and all.
Tough, but that's how we've all been publishing... And still are.
-
Most computer scientists that I know (1) post their papers to their websites,
and (2) have never gotten a cease and desist order of anything of the sort.
Same with websites dedicated to various topics
(so NOT the website owners
papers)
So while you may be right about the legal status,
you are wrong about
``thats how we've all been publishing'' In fact
I know of very few people who do not post their papers to their website.
Unfortunately, Barrington is one of them.
-
Not to be pedantic, but isn't it true that an author is not typically allowed to post the journal's version (as it appears in the final publication with the journal's name and formatting, etc.) on his/her website but is allowed to post his/her own version (a preprint, for example)? Of course, it would depend on the journal and what its copyright statement says.
-
How many others have bought [the All-Ett billfold] based on [Lance's] recommendation?
Count me in. Chalk it up to the power of personal recommendation.
-
I bought a wallet too.
I was getting annoyed after a few weeks that no package had arrived. Then I finally looked through the envelopes stacked up in my in slot. Of course, it had been there for several weeks.
Doh! If it's the world's thinnest wallet, it don't need no stinkin' package!
I've been carrying for several weeks now. It is a lot easier on my gluts. A little hard getting cash in and out because it is not very stiff. I also wonder if my credit cards will get bent out of shape from sitting on them. But better them than me.
Overall, a thumb's up though.
-
I bought it because of the recommendation, and have influenced at least one other person at MIT to buy one.
Links to this post:
Weblog Home
Archives
