Berkeley CSUA MOTD:Entry 24619
Berkeley CSUA MOTD
 
WIKI | FAQ | Tech FAQ
http://csua.com/feed/
2024/11/23 [General] UID:1000 Activity:popular
11/23   

2002/4/28 [Computer/Theory] UID:24619 Activity:very high
4/26    Is it possible to find the median value of a group of numbers in O(N)?
        \_ Yes, but in practice people use an O(n log n) solution. -op
        \_ Yes; there is a fairly simple randomized algorithm which does this
           with high probability, and a non-trivial deterministic algorithm
           that people don't usually bother with. If N is really large, it's
           probably worth your time to look into the former (see section
           3.3 of Motwani&Raghavan, where it's called "LazySelect"; the
           original paper is Floyd&Rivest, CACM 18:165-172, 1975, but it may
           well be rather unreadable; M&R also gives refs for the deterministic
           algorithms). -alexf
        \_ you can sort numbers in O(n) with radix sort and counting sort.
           \_ sorting is normally assumed to be O(n lg n)
              \_ and your point is...?
2024/11/23 [General] UID:1000 Activity:popular
11/23   

You may also be interested in these entries...
2012/8/30-11/7 [Computer/SW/Apps, Computer/SW/Unix] UID:54470 Activity:nil
8/30    Is wall just dead? The wallall command dies for me, muttering
        something about /var/wall/ttys not existing.
        \_ its seen a great drop in usage, though it seems mostly functional.
            -ERic
        \_ Couldn't open wall log!: Bad file descriptor
           Could not open wall subscription directory /var/wall/ttys: No such file or directory
	...
2012/1/24-3/3 [Computer/SW/Languages/C_Cplusplus, Computer/SW/Languages/Misc] UID:54296 Activity:nil
1/24    http://james-iry.blogspot.com/2009/05/brief-incomplete-and-mostly-wrong.html
        Amusing "history" of computer science.
        \_ Where's the mentioning of Al Gore the inventor of AlGorithm?
	...
2011/11/20-2012/2/6 [Computer/Companies/Apple, Computer/SW/Unix] UID:54237 Activity:nil
11/20   Are there tools that can justify a chunk of plain ASCII text by
        replacing words with words of similar meaning and inserting/removing
        commas into the text?  I received a 40-line plain text mail where
        all the lines are justified on left and right.  Every word and comma
        is followed by only one space, and every period is followed by two
        spaces.  The guy is my kid's karate instructor which I don't think is
	...
2011/10/26-12/6 [Computer/SW/Unix] UID:54202 Activity:nil
10/24  What's an easy way to see if say column 3 of a file matches a list of
       expressions in a file? Basically I want to combine "grep -f <file>"
       to store the patterns and awk's $3 ~ /(AAA|BBB|CCC)/ ... I realize
       I can do this with "egrep -f " and use regexp instead of strings, but
       was wondering if there was some magic way to do this.
       \_ UNIX has no magic. Make a shell script to produce the ask or egrep
	...
2011/6/29-7/21 [Computer/SW/Database, Computer/SW] UID:54133 Activity:nil
6/29    "An Israeli algorithm sheds light on the Bible"
        http://www.csua.org/u/tq4 (news.yahoo.com)
        "Software developed by an Israeli team is giving intriguing new hints
        about what researchers believe to be the multiple hands that wrote the
        Bible."
        \_ "Hype developed by an American OnLine News Feed is giving
	...