Berkeley CSUA MOTD:Entry 23318
Berkeley CSUA MOTD
 
WIKI | FAQ | Tech FAQ
http://csua.com/feed/
2025/05/24 [General] UID:1000 Activity:popular
5/24    

2001/12/20 [Computer/Theory, Computer/SW/Unix] UID:23318 Activity:very high
12/19   Why is EULER-PATH not as important as HAMPATH? (seriously, what is the
        main diff between "edges only once" and "nodes only once")
        \_ Euler path is a linear problem- O(V+E).  Hamiltonian circuit is
           NP-Complete, which means that it's at least as hard as
           thousands of other problems.  Produce a polynomial time
           algorithm for Hamilton and you can crack nearly any public-key
           cryptography system.
           \_ isn't prime factorization NP-intermediate?
              \_ So? All that means that you don't _have_ to solve Hampath
                 in polytime in order to solve factoring. If you _do_ solve
                 Hampath in polytime, this still gives you polytime factoring.
           \_ what's the O(n) alg for EULER-PATH then?
              \_ Find all nodes with odd degrees. If there's more than 2, halt
                 and return "impossible". Else, start at a node of odd degree
                 if there is one, and just keep going around while there're
                 edges from where you are which you haven't used yet. It's
                 fairly easy to prove that this will always find an Euler
                 path if one exists. -alexf
                 \_ Not true. Consider this graph:   |_ _
                                                      /|_|
                                                     |
                    If you start at the top node, go down,
                    go right, then go diagonally  down and
                    left you've cut yourself off from the
                    square at the right. But you can start
                    a new cycle that picks up that square,
                    then splice it into the other path. -ok
                    \_ I stand duely corrected. Apply the algorithm listed
                       above repeatedly to the graph, restarting at any point
                       which has unused edges coming out. You'll get a
                       collection of paths, of which all but at most 1 will
                       be cycles; you can then "merge" the cycles into the
                       path by just taking a "detour" around the cycle from
                       the point where the path touches said cycle. This should
                       still be linear. -alexf
                        \_ Duly.
2025/05/24 [General] UID:1000 Activity:popular
5/24    

You may also be interested in these entries...
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/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
	...
2010/8/9-19 [Computer/SW/Security] UID:53917 Activity:nil
8/9     I got two files, one is size 522190848 and the other is size
        521648128.  Both sha256 to the same number.  (and sha1 too).
        I don't think this is supposed to happen, right? (least not with
        sha256).
        \_ how are you checking?
           \_ I burned one file to cd, so i mounted /cdrom and
	...
2010/1/20-29 [Computer/SW/Languages/Misc, Computer/SW/Security] UID:53649 Activity:nil
1/20    Did Chinese come up with new way of quicksort?
        http://www.nytimes.com/2010/01/20/technology/20cyber.html
        Joe Stewart, a malware specialist with SecureWorks, a computer
        security company based in Atlanta, said he determined the main
        program used in the attack contained a module based on an unusu
        al algorithm from a Chinese technical paper that has been
	...
2009/10/24-11/3 [Computer/HW/Laptop] UID:53466 Activity:kinda low
10/24   How well do you see color? I got 8, how about you?
        http://www.xrite.com/custom_page.aspx?PageID=77
        \_ 7
           \_ what monitor did you use?
              \_ LCD on thinkpad x32, under not so great lighting conditions.
        \_ I scored 101, which seems impossible. Then again, I didn't
	...
2009/7/14-27 [Academia, Academia/GradSchool, Computer/Theory] UID:53139 Activity:nil
7/22    (redux)
        To those in academia, how do you organize the journal articles
        you keep (hard copies, that is)? By date? Author? Subject?
        Something else? Thanks.
        \_ I am not in academia, but author makes most sense. If you want, you
           can group by subject (Sun Spots, Solar Wind, Solar Flares) and then
	...
2009/1/13-22 [Computer/Theory] UID:52367 Activity:kinda low
1/13    I am writing a commandline parser for a class and I could use some
        tips for algorithms to use. (The project is over and done so I am
        not cheating, but I am dissatisfied with my end result.) I STFW and
        didn't come up with too much I liked. I read the source for some
        shells like tcsh and that is *WAY* too complicated and relies on
        a lot of other code. I know that browsers and other apps have
	...
2008/12/2-6 [Computer/SW/Apps, Academia/Berkeley/CSUA/Motd] UID:52140 Activity:kinda low
12/1    Just curious -- what do you guys generally use soda for? Why do you
        log on? Personally, I use it to keep a presence on IRC and AIM/gTalk
        at all times, and mess around with some Python programming (been
        setting up Twisted and such so I can play with making an irc bot).
        --toulouse
        \_ I use it to post SHIT, er, I mean, spill my guts about the company
	...
2008/11/25-28 [Computer/Theory] UID:52108 Activity:nil
11/25   Holy crap! I was the one asking how to open a locked up masterlock a
        few days ago. I tried the algorithm on this webpage:
        http://www.wikihow.com/Crack-a-%22Master-Lock%22-Combination-Lock
        and it worked! Thanks to whoever suggested it.
        \_ Good to know, thanks for the reply.
	...
2010/6/8-30 [Computer/Companies/Yahoo] UID:53853 Activity:nil
6/8     Newly wed husband and wife found from old picture that they have
        actually crossed path 30yrs ago: http://www.csua.org/u/qwv
        My question is how do stories like this find its way to news media?  Do
        people just go "hey something very interesting happens in our lives.
        Let's call up a news agency or two to tell the world about it."?
        \_ "Your video will begin after a word from our sponsors."
	...
2010/3/8-30 [Computer/SW/Unix] UID:53745 Activity:nil
3/8     I have a mod_rewrite question that I think should be straight-
        forward but I think I'm not getting something.
        I have a virtual server with some root, say /home/user/public_html/
        and in there I have two subdirs, say /app1/ and /app2/
        and i want the following:
        http://mysite/app1   -->   /home/user/public_html/app1
	...
2010/1/22-24 [Computer/SW/Unix] UID:53654 Activity:high
1/22    What's the difference between a job and a career?
        \_ women have jobs, men have careers.
           \_ true statement but one that is sexist and should be
              kept in a private conversation
        \_ A job could be anything that pays mortgage or feed the mouth.
           A career is something that is longer term, most of the time,
	...
2009/8/18-9/1 [Computer/SW/Unix] UID:53284 Activity:nil
8/18    Is it possible to truncate your path name in your prompt in tcsh?
        Tsch veterans REPRESENT!  I know this is how to do it in bash:
        # truncate path: returns $1 truncated to $2 chars, prefixed with ...
        truncate_path () {
                if [ -z "$1" -o -z "$2" ]
                then
	...
2009/8/19-9/1 [Computer/SW/Unix] UID:53285 Activity:nil
8/18    Hi again, new freebsd guy here again, in bash I was able to go
        LD_LIBRARY_PATH=/opt/foo/lib ./runmyapp
        I managed to do this in tcsh by using setenv in a shell script
        that setenv's the lib path and then executes $1, just wondering
        if there was a way to do it in 1 line from the cmd line as in bash?
        Thanks, btw %2c or %3c worked.  Freebsd, tcsh and vi forever!
	...