tag:blogger.com,1999:blog-1611368930203661681.post875486225722506153..comments2017-03-03T07:18:21.770+01:00Comments on MacGyver Development: Become a better programmer with programming challengesJohan Norénhttp://www.blogger.com/profile/14636265442070759165noreply@blogger.comBlogger14125tag:blogger.com,1999:blog-1611368930203661681.post-58302328622064081832014-05-09T09:02:23.999+02:002014-05-09T09:02:23.999+02:00Thank you It was a very interesting post.Thank you It was a very interesting post.Aurélien Bottazinihttp://www.blogger.com/profile/13692548440465041998noreply@blogger.comtag:blogger.com,1999:blog-1611368930203661681.post-27128731723354326692014-05-03T19:13:01.055+02:002014-05-03T19:13:01.055+02:00Very thorough comment. I appreciate the details. T...Very thorough comment. I appreciate the details. Thank you!Johan Norénhttp://www.blogger.com/profile/14636265442070759165noreply@blogger.comtag:blogger.com,1999:blog-1611368930203661681.post-68488135560958610412014-05-02T18:17:23.467+02:002014-05-02T18:17:23.467+02:00"One of the fastest algorithms [...] is the A..."One of the fastest algorithms [...] is the AKS test [...]"<br /><br />This is one of the *slowest* tests in actual practice. The paper is interesting to read, and it's very important for the theory and for spurring new research areas, but nobody uses it in practice. I would recommend the Miller-Rabin and BPSW tests as better areas of study -- especially noting how they can be deterministic for 64-bit integers, hence are all you need for most programming challenges, and will be thousands or millions of times faster than AKS while offering the same certainty. For proofs I think the BLS (1975) and ECPP methods are more valuable to know; albeit ECPP isn't something easily implemented, but it is, along with BLS75 methods and APR-CL, used in practice for large numbers.<br /><br />For factoring, the entry jumps straight to NFS. Pollard's Rho (and Brent's improvements), SQUFOF, Pollard's p-1, ECM, and Quadratic Sieve are common methods used for numbers less than ~100 digits. For 64-bit, the first one, two, or three methods are all that's needed.<br /><br />Re Fibonacci sequence, if using the closed form, watch out for precision. If n > 71 or so, typically you will have to use a big float package and adjust the used precision. At that point I've found usually using integer formulas (perhaps with the various shortcuts) is faster, but it depends on the problem.Danahttp://www.blogger.com/profile/03846610293039210105noreply@blogger.comtag:blogger.com,1999:blog-1611368930203661681.post-44205071891289025962014-05-02T16:34:10.897+02:002014-05-02T16:34:10.897+02:00Great post! I share it to my student in Multimedia...Great post! I share it to my student in Multimedia Nusantara University, SerpongJohan Setiawan UMNhttp://www.blogger.com/profile/09614330490406265735noreply@blogger.comtag:blogger.com,1999:blog-1611368930203661681.post-76128694579862629792014-05-01T01:09:42.161+02:002014-05-01T01:09:42.161+02:00And of course, O(f(x)) is a set, so a function can...And of course, O(f(x)) is a set, so a function can not be equal to it. You "formal" definition still needs some work.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-1611368930203661681.post-26577703780901751572014-05-01T01:07:24.347+02:002014-05-01T01:07:24.347+02:00Almost. You forgot to say what x0 is.Almost. You forgot to say what x0 is.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-1611368930203661681.post-21764483371388612562014-04-30T23:44:25.357+02:002014-04-30T23:44:25.357+02:00Great post!... Hope the it as addictive as ClashOf...Great post!... Hope the it as addictive as ClashOfClansDanny Trieuhttp://www.blogger.com/profile/08692534145033810513noreply@blogger.comtag:blogger.com,1999:blog-1611368930203661681.post-62214566918578744052014-04-30T22:48:35.588+02:002014-04-30T22:48:35.588+02:00Yes, it was a bit hand waving. Added some more mea...Yes, it was a bit hand waving. Added some more meat to the definition. Hopefully it is quite correct now. Thanks.Johan Norénhttp://www.blogger.com/profile/14636265442070759165noreply@blogger.comtag:blogger.com,1999:blog-1611368930203661681.post-14552357893795856422014-04-30T22:47:21.682+02:002014-04-30T22:47:21.682+02:00Thanks! Concerning the thought process I think it ...Thanks! Concerning the thought process I think it is a question of practice. Once you have solved a few problems using for DP you get an intuition for possible approaches to make the problems simpler. Recursion can be a good way to formalize the solution on paper since it relies on calling the same procedure to solve the same problem but hopefully in a simplified way like in this case. <br />But I agree, there are lots of very hard problems on these sites that make you humbled and feeling not so clever.Johan Norénhttp://www.blogger.com/profile/14636265442070759165noreply@blogger.comtag:blogger.com,1999:blog-1611368930203661681.post-1917572016627855802014-04-30T10:19:55.404+02:002014-04-30T10:19:55.404+02:00My degree was digital hardware and low level softw...My degree was digital hardware and low level software. I took five assembly-language based courses. You study algorithms. I wrote a 64-bit compiler, front, middle and backend. You could not write a backend.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-1611368930203661681.post-44978840375722665672014-04-29T20:43:55.687+02:002014-04-29T20:43:55.687+02:00"The formal definition is that this Big-O fun..."The formal definition is that this Big-O function O() satifies <br /><br />f(x) = O(g(x)) when x ➝ ∞"<br /><br />Yes, let's go with that. Sounds all right, doen't it?<br /><br />Not really. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-1611368930203661681.post-40116006465566884222014-04-29T12:16:55.832+02:002014-04-29T12:16:55.832+02:00There is an open coding challenge running right no...There is an open coding challenge running right now (and until next Monday), with nice prices: https://contest.tuenti.netAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-1611368930203661681.post-51221651422425898772014-04-29T11:40:41.852+02:002014-04-29T11:40:41.852+02:00You failed at pig latin? SERIOUSLY??????????????? ...You failed at pig latin? SERIOUSLY??????????????? who are you ? lolAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-1611368930203661681.post-27704339321499802112014-04-29T10:41:48.524+02:002014-04-29T10:41:48.524+02:00Great post I am a beginner having a bit of trouble...Great post I am a beginner having a bit of trouble with these sorts of problems specifically what upsets me the most is that I always get stuck. For instance in the currency problem how did you magically! come to this assumption?<br /><br />"Let's start thinking from a dynamic programming perspective. Can we make the problem simpler? Let's assume we have solved the same problem (in some at this time unknown way) for 4 currencies. So we know how many combinations you could get x dollars in 1c, 5c, 10c and 25c. Could this help us?"<br /><br />And then after this how did you know you could express this as a recursion?<br /><br />It is not clear what my thought process should be when thinking about these problems maybe I'm just too stupid for these problems...it is seriously frustrating when you can't even solve a single problem. Anonymousnoreply@blogger.com