11 ms·

What aspects of a solid CS foundation have been particularly useful to you? And how? I'm currently a student, and most of the courses seem shallow, so I'd appr

by arthev 8y ago

What aspects of a solid CS foundation have been particularly useful to you? And how? I'm currently a student, and most of the courses seem shallow, so I'd appreciate a data point to re-calibrate my plans for learning foundations on my own.

Jtsummers 8y ago
Algorithm analysis. Similar to my other post, I've gotten speed ups on the order of 100x or more by changing the algorithms used to accomplish the same work. One example was a data analysis tool, the original author wrote a correct (produced the right stuff) but naive implementation. It took about 3 minutes to perform its work, I got it below 5 seconds without being clever (read: hard to read/write, but fast). I changed the order of some of the data processing, and switched to a smarter data structure (built-in hashmap versus whatever he'd chosen). The final version was readable and maintainable by non-CS folks (it was used by engineers, mostly). I knew of optimal sorting networks which let me optimize a hotspot in an embedded system and improve throughput in a real-time system. It seems like a miniscule savings (versus whatever sort they'd used before, insertion I think) since it was only a handful of items. But its execution time was one of the dominating factors in the system, and reducing the number of comparisons and branches to a minimum was a significant improvement. Familiarity with declarative languages like Prolog informed the design of data analysis tools (that could've been done better in Prolog but that wasn't an option). So I wrote a specialized program that, internally, was halfway to being a Prolog implementation. Parsing. I've not written any compilers, but I have needed custom parsers over the years. Understanding the difference between different types of languages (regular versus context-free in particular) meant I could choose the right tools for the job. Additionally, understanding what needs to be done in a parser leads to better structuring of the code. Programming language theory. You don't need real, formal theory here, but if you understand how ideas map between languages and what some languages excel at (compared to others), you can write idiomatic code in more languages. Versus my predecessors, who could "write Fortran in any language". You can also understand the tradeoffs between the different kinds of languages (why do people support OO, FP, and others; why do they choose each). Additionally, you can borrow ideas from some languages and import them into others, with some care. Understanding abstraction, which I'll admit was generally not taught well in my program, I got it more from my math background. This can lead to generic code and programs that operate on a wider variety of problems and data types.
slipwalker 8y ago
besides everything already said by Jtsummers: - Data structures were fundamental before ( perl's hashes-of-arrays-of-hashes-of-hashes, anyone ? ) and with the rediscovered FP paradigm, those are fundamental again. Once you figure the proper data model, the algorithm becomes much clearer ( https://www.amazon.com/gp/product/0131997467/ https://www.amazon.com/gp/product/0131997467/ ) - Recursion, which importance is very well discussed on this blog post: https://www.joelonsoftware.com/2005/12/29/the-perils-of-javaschools-2/ https://www.joelonsoftware.com/2005/12/29/the-perils-of-java... - Graph theory also was invaluable over the years ( http://www.maths.lse.ac.uk/Personal/jozef/LTCC/Graph_Theory_Bondy_Murty.pdf http://www.maths.lse.ac.uk/Personal/jozef/LTCC/Graph_Theory_... and https://freevideolectures.com/course/3019/graph-theory https://freevideolectures.com/course/3019/graph-theory ). ( hope that helps... )
deleted 8y ago
[deleted]

by arthev 8y ago

Jtsummers 8y ago

Algorithm analysis. Similar to my other post, I've gotten speed ups on the order of 100x or more by changing the algorithms used to accomplish the same work. One example was a data analysis tool, the original author wrote a correct (produced the right stuff) but naive implementation. It took about 3 minutes to perform its work, I got it below 5 seconds without being clever (read: hard to read/write, but fast). I changed the order of some of the data processing, and switched to a smarter data structure (built-in hashmap versus whatever he'd chosen). The final version was readable and maintainable by non-CS folks (it was used by engineers, mostly). I knew of optimal sorting networks which let me optimize a hotspot in an embedded system and improve throughput in a real-time system. It seems like a miniscule savings (versus whatever sort they'd used before, insertion I think) since it was only a handful of items. But its execution time was one of the dominating factors in the system, and reducing the number of comparisons and branches to a minimum was a significant improvement. Familiarity with declarative languages like Prolog informed the design of data analysis tools (that could've been done better in Prolog but that wasn't an option). So I wrote a specialized program that, internally, was halfway to being a Prolog implementation. Parsing. I've not written any compilers, but I have needed custom parsers over the years. Understanding the difference between different types of languages (regular versus context-free in particular) meant I could choose the right tools for the job. Additionally, understanding what needs to be done in a parser leads to better structuring of the code. Programming language theory. You don't need real, formal theory here, but if you understand how ideas map between languages and what some languages excel at (compared to others), you can write idiomatic code in more languages. Versus my predecessors, who could "write Fortran in any language". You can also understand the tradeoffs between the different kinds of languages (why do people support OO, FP, and others; why do they choose each). Additionally, you can borrow ideas from some languages and import them into others, with some care. Understanding abstraction, which I'll admit was generally not taught well in my program, I got it more from my math background. This can lead to generic code and programs that operate on a wider variety of problems and data types.

slipwalker 8y ago

besides everything already said by Jtsummers: - Data structures were fundamental before ( perl's hashes-of-arrays-of-hashes-of-hashes, anyone ? ) and with the rediscovered FP paradigm, those are fundamental again. Once you figure the proper data model, the algorithm becomes much clearer ( https://www.amazon.com/gp/product/0131997467/ https://www.amazon.com/gp/product/0131997467/ ) - Recursion, which importance is very well discussed on this blog post: https://www.joelonsoftware.com/2005/12/29/the-perils-of-javaschools-2/ https://www.joelonsoftware.com/2005/12/29/the-perils-of-java... - Graph theory also was invaluable over the years ( http://www.maths.lse.ac.uk/Personal/jozef/LTCC/Graph_Theory_Bondy_Murty.pdf http://www.maths.lse.ac.uk/Personal/jozef/LTCC/Graph_Theory_... and https://freevideolectures.com/course/3019/graph-theory https://freevideolectures.com/course/3019/graph-theory ). ( hope that helps... )

deleted 8y ago

[deleted]