129 votes
Accepted

What are the reasons to learn different algorithms / data structures serving the same purpose?

There's a textbook waiting to be written at some point, with the working title Data Structures, Algorithms, and Tradeoffs. Almost every algorithm or data structure which you're likely to learn at the ...
Pseudonym's user avatar
  • 22.1k
124 votes
Accepted

How/when is calculus used in Computer Science?

I can think of a few courses that would need Calculus, directly. I have used bold face for the usually obligatory disciplines for a Computer Science degree, and italics for the usually optional ones. ...
Jay's user avatar
  • 1,349
59 votes
Accepted

How can I explain to my parents that I study programming languages?

If you have a few minutes, most people know how to add and multiply two three-digit numbers on paper. Ask them to do that, (or to admit that they could, if they had to) and ask them to acknowledge ...
Lieuwe Vinkhuijzen's user avatar
52 votes

What are the reasons to learn different algorithms / data structures serving the same purpose?

Aside from the fact that there are myriads of cost measures (running time, memory usage, cache misses, branch mispredictions, implementation complexity, feasibility of verification...) on myriads of ...
Raphael's user avatar
  • 72.4k
30 votes

How/when is calculus used in Computer Science?

This is somewhat obscure, but calculus turns up in algebraic data types. For any given type, the type of its one-hole contexts is the derivative of that type. See this excellent talk for an overview ...
Tuomas Laakkonen's user avatar
19 votes

How can I explain to my parents that I study programming languages?

I would try something like this: Programmers can tell computers what to do. To do that, they need to use a programming language. That is a language that is understood by both computers and humans. ...
Toxaris's user avatar
  • 404
18 votes
Accepted

on "On the cruelty of really teaching computing science"

This is pretty much what TU Eindhoven's Computing Science education, designed and implemented by Dijkstra and colleagues, was like from the time it started, around 1980, until Dijkstra's influence ...
reinierpost's user avatar
  • 5,519
18 votes

False proofs that look correct

One of my favourites is the "brothers paradox": https://en.wikipedia.org/wiki/Boy_or_Girl_paradox I tell it as I learned it*, as follows: in a village, each family has two children, elder ...
Shaull's user avatar
  • 17.2k
17 votes

How to fool the "try some test cases" heuristic: Algorithms that appear correct, but are actually incorrect

2D local maximum input: 2-dimensional $n \times n$ array $A$ output: a local maximum -- a pair $(i,j)$ such that $A[i,j]$ has no neighboring cell in the array that contains a strictly larger value. ...
Neal Young's user avatar
16 votes

False proofs that look correct

Merge-sort can be done in linear time! Indeed, the time complexity to sort a list or array of length $n$ verifies$^{(1)}$: $$T(n) = T\left(\left\lfloor\frac{n}2\right\rfloor\right) + T\left(\left\...
Nathaniel's user avatar
  • 15.5k
14 votes

What does it mean to prove the halting problem is undecidable "using arithmetization"?

I would guess/assume that by "arithmetization", they mean the concept that every Turing machine can be associated with a bit-string or natural number (the fact that we can encode a ...
D.W.'s user avatar
  • 159k
13 votes
Accepted

Why should we study all the three forms of representation of finite automata?

Add regular grammars for a fourth. There are others... Part of the interest in DFA + NFA is that they are simple computation models, with NFA (and $\epsilon$-NFA) examples of nondeterminism (a ...
vonbrand's user avatar
  • 14k
13 votes

How/when is calculus used in Computer Science?

Numerical Methods. There exist cumbersome calculus problems that are unique to specific applications, and they need solutions faster than a human can practically solve without a program. Someone has ...
Jonah Havel's user avatar
13 votes

How/when is calculus used in Computer Science?

Automation - Similar to robotics, automation can require quantifying a lot of human behavior. Calculations - Finding solutions to proofs often requires calculus. Visualizations - Utilizing ...
LJones's user avatar
  • 139
12 votes

How can I explain to my parents that I study programming languages?

Most people understand recipes. If you follow the instructions, you'll get a decent meal. Sometimes, though, the instructions can be difficult to follow. For example, when you're making perogies, you'...
corsiKa's user avatar
  • 423
12 votes

How can I explain lossless compression to a misguided audio engineer?

Tell him to write out the integers between 1 and 100, inclusive. Ask him how it can be that your instruction was so much shorter than the list of numbers he wrote out. Did that brevity cause him to ...
David Richerby's user avatar
10 votes

As a Teacher: Choosing a suitable programming language

My answer? Python. Let me explain by tackling all your points. Simplicity. Python code reads like English. Seriously, how simple is print("Hello World!") ...
Lawrence Vo's user avatar
10 votes

As a Teacher: Choosing a suitable programming language

Background This question raises its ugly head every 5 or so years at our department. We had Miranda and Pascal ages ago, then we had Haskell, now we have C because thee EE dept decided to send us ...
Kai's user avatar
  • 865
10 votes

Where should I start to understand how computers work?

You're asking a very broad question that isn't particularly easy to answer "correctly". What you are describing is what you learn if you follow through with a degree in computer science or maybe more ...
Pål GD's user avatar
  • 16.1k
9 votes

How to memorize Master Theorem?

The key to memorizing the master theorem is to simplify it. There's an approximation to reality that is correct in 99% of the cases. A good (but not technically correct) summary of the Master Theorem ...
Tom van der Zanden's user avatar
9 votes

False proofs that look correct

I have often seen among undergraduates that they believe that the heaps are constructed in $\Theta(n \log n)$ time. The standard algorithm for that is to insert an element to a heap one after another. ...
Inuyasha Yagami's user avatar
9 votes

False proofs that look correct

This one is regarding $\mathsf{FPT}$ time algorithm. Suppose an algorithm has time complexity of: $O((\log n)^k \cdot n^{O(1)})$. Is it an $\mathsf{FPT}$ time algorithm in parameter $k$? Well ...
Inuyasha Yagami's user avatar
8 votes

How can I explain to my parents that I study programming languages?

Your best bet may be to form analogies with human languages. Programming languages are used to provide instructions to computers. Human languages are used to communicate ideas to other people and to ...
200_success's user avatar
  • 1,012
8 votes
Accepted

What mathematical background is enough to go through the entire Knuth's TAOCP?

If your only exposure to math is undergrad level calculus, numerical analysis, and probability, you probably don't want to start out with computer science by reading The Art of Computer Programming. ...
tsleyson's user avatar
  • 3,128
8 votes

False proofs that look correct

This one is classic. $0$-$1$ Knapsack problem is polynomial time problem since there is dynamic programming solution with running time $O(n W)$ time. However, it is incorrect. Note that the input size ...
Inuyasha Yagami's user avatar
7 votes

What are the reasons to learn different algorithms / data structures serving the same purpose?

In the real world, at some point you are likely to be working on software that has been written by a team of other people. Some of this software will have been written before you were born! So as ...
Ian Ringrose's user avatar
7 votes

How/when is calculus used in Computer Science?

The fact is that there's very little chance you'll ever use calculus. However, virtually every other scientific discipline DOES use calculus and you are working on a science degree. There are certain ...
Scott B's user avatar
  • 97
7 votes

How can I explain to my parents that I study programming languages?

Here is how I would (try) to explain this to my mom: Programming languages are used by people to provide instructions to a computer. Everything that a computer does is done through some computer ...
Matt Hall's user avatar
7 votes

As a Teacher: Choosing a suitable programming language

This question is highly opinionated, in my opinion. There's nothing which can trigger an holy war like "which language is the best for X". Still, I'll bite. is there any other factors that i'm ...
chi's user avatar
  • 14.6k
7 votes
Accepted

How can I improve my algorithmic ingenuity?

It seems that competitive programming might help you. Or just the "programming" part of it. If you want to hone your problem solving skills (and therefore your ability to come up with original ideas), ...
IS3NY's user avatar
  • 106

Only top scored, non community-wiki answers of a minimum length are eligible