5 ms·
How long until we start seeing this algorithm in Google interviews?
by Zach_the_Lizard 11y ago
How long until we start seeing this algorithm in Google interviews?
- Ar-Curunir 11y agoVery long, most CS people don't know any group theory.
- wtallis 11y agoJust a week or two ago I saw someone get downvoted for suggesting that many CS degrees don't include real analysis. I suspect that by now undergrad CS programs are all over the place, and I wouldn't dare make broad generalizations about the math content of a CS degree anymore.
- Ar-Curunir 11y agoI am pretty sure that most CS students don't have the algebra background to understand what's going on in this algorithm. I've taken a year's worth of algebra and the algorithm still relies on stuff that I don't get. Edit: and most CS programs do not emphasize traditional math anyways. No analysis, some linear algebra, very very little abstract algebra, and that's pretty much it.
- Zach_the_Lizard 11y agoMy father got a BA in CS that didn't even require calculus. He graduated in the 90s.
- j2kun 11y agoI would, because I'm on the inside. There are even many CS degrees that don't require a course in algorithms. You have to remember that most CS degrees come from public/state universities, not Stanford and MIT. And CS students at public/state universities are largely mathphobic.
- pm90 11y agoThat's a very broad generalization. There are many public/state universities with amazing CS research and programs (e.g. UC Berkeley) that are very math-heavy.
- Ar-Curunir 11y agoAs a student at UC Berkeley, students need to study at most linear algebra and multivariablr calc to major in CS/EECS.
- jsprogrammer 11y agoNo Boolean algebra, probability, or statistics?
- learc83 11y ago>There are even many CS degrees that don't require a course in algorithms. What CS degree doesn't require a course in algorithms? I assume there are some Software Engineering degrees that don't, but how can you spend 4 years studying computer science without an algorithms course? >And CS students at public/state universities are largely mathphobic. I agree that most CS students try to avoid relatively proof heavy classes like Automata. But almost all CS courses require up to Calc 2 and discrete math, so I'm sure the truly "mathphobic" students would have majored in CIS or something else. I also don't think this has anything to do with Standford MIT vs public universities. Students at those Universities would avoid elective proof heavy classes as well. I did undergrad at a relatively unknown state school, and now I'm in grad school in a top ten program. I know plenty of people from both schools who avoid rigorous proof heavy classes when they can.
- j2kun 11y agoHere is one such program, North Carolina State University, which requires a basic theory course (automata) but no algorithms course. https://www.csc.ncsu.edu/academics/undergrad/semester.php https://www.csc.ncsu.edu/academics/undergrad/semester.php There are many more X state universities that churn out computer science degrees than the top schools.
- brianchu 11y agoMost CS programs that I am aware of don't require real analysis. I know Berkeley EECS doesn't, and it's a very rigorous program. Stanford too. I plan on taking it, but only because it shows up in a few esoteric theoretical machine learning contexts.
- alexfoo 11y agoToo true, it's one of the reasons why I did a Maths degree to complement my Comp Sci degree.
- glxc 11y agois that all it's good for?
- Zach_the_Lizard 11y agoNope, it's got useful applications in the real world in, say, chemical compound databases.
- Ar-Curunir 11y agoThis algorithm in its current state really doesn't; GI for most natural instances was already being solved quickly via some heuristics. This algorithm proves a quasipolynomial upper bound on the complexity of GI.
- gilleain 11y agoEr, perhaps. InChI is already based on nAUTy, which even this work acknowledges as the fastest general approach (except for saucy, bliss, etc). So there are no implications of László Babai that have an impact on chemistry, AFAICT.