Computer science studies how information can be represented and transformed by algorithms, and what those transformations can achieve. Its central questions connect mathematics to practical design: what answer should a procedure produce, why is it correct, and how much work does it require as its input grows? Computability theory asks which tasks can be solved at all; computational complexity theory asks what resources a solution needs.
The beauty is that choosing a representation can change what is feasible. Finding a name among a million entries sounds like a million checks. Store the entries in a sorted array, and binary search needs at most twenty middle-entry comparisons. The order makes each unsuccessful comparison eliminate a whole region of possibilities. A data structure supplies useful organization; an algorithm exploits it; time complexity explains the resulting savings.
Algorithm correctness covers every permitted input, including absent names and empty collections. Time complexity predicts scaling; statistical program profiling investigates a particular implementation.
- 6.006 Introduction to Algorithms, Fall 2011 by Massachusetts Institute of Technology, 6.006 course staff
- 6.006 Introduction to Algorithms, Fall 2011 by Massachusetts Institute of Technology, 6.006 course staff Lecture 14: Graphs II: Depth-First Search
- Lecture 15: Recursive Algorithms (6.006 Spring 2020) by Massachusetts Institute of Technology, 6.006 course staff
- 3.6. Journal (jbd2) by The kernel development community
- Buffer Heads by The kernel development community
- Explicit volatile write back cache control by The kernel development community
- ext4 General Information by The kernel development community
- Page Cache by The kernel development community
- Page Tables by The kernel development community
Articles were limited to the first 100 out of 972 total.
Articles by others on the same topic
Unfortunately, all software engineers already know the answer to the useful theorems though (except perhaps notably for cryptography), e.g. all programmers obviously know that iehter P != NP or that this is unprovable or some other "for all practical purposes practice P != NP", even though they don't have proof.
And 99% of their time, software engineers are not dealing with mathematically formulatable problems anyways, which is sad.
The only useful "computer science" subset every programmer ever needs to know is:
- for arrays: dynamic array vs linked list
- for associative array: binary search tree vs hash table. See also Heap vs Binary Search Tree (BST). No need to understand the algorithmic details of the hash function, the NSA has already done that for you.
- don't use Bubble sort for sorting
- you can't parse HTML with regular expressions: stackoverflow.com/questions/1732348/regex-match-open-tags-except-xhtml-self-contained-tags/1732454#1732454 because of formal language theory
Funnily, due to the formalization of mathematics, mathematics can be seen as a branch of computer science, just like computer science can be seen as a branch of Mathematics!