19
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 ...
- 18k
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. ...
- 993
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\...
- 18.4k
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.♦
- 169k
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 ...
- 18k
10
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 ...
- 6,297
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. ...
- 6,297
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 ...
- 6,297
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), ...
- 106
6
votes
False proofs that look correct
An simple example that I can think of, which is commonly use as introductory topic in amortized analysis, is the analysis of dynamic table. The usual scenario is to analyze the total time needed to ...
- 2,788
6
votes
False proofs that look correct
Induction often yields great wrong proofs because there are many things which can fail:
The induction base $P(0)$ can be false, or it may be missing at all and hence the rest of the induction is ...
- 227
5
votes
How do I improve my problem-solving and creative thinking skills in Computer Science?
Without knowing You and Your personal situation, this question is almost impossible to answer. So all I can try to give is some general-purpose advice which hopefully gets You on the right track.
Get ...
- 1,021
4
votes
Accepted
Where should I start to understand how computers work?
Three books:
1. Code: The Hidden Language of Computer Hardware and Software by Charles Petzold
Using everyday objects and familiar language systems such as Braille and Morse code, author Charles ...
- 156
4
votes
False proofs that look correct
Spaghetti sort can sort numbers in linear time.
Assume without loss of generality that the numbers to be sorted are all in the interval $(0,1)$. A whole spaghetti has length $1$.
For each number cut ...
- 141
4
votes
Accepted
"Entrance exam" homework assignment for 3rd-year algorithms?
I am a teacher in 2nd year in a generalist scientific formation for engineers, and I would expect my students to be able to do that in less than one hour after one semester, so I think this is ...
- 18.4k
4
votes
"Entrance exam" homework assignment for 3rd-year algorithms?
I see three issues that are going to come up for you:
Undergraduate courses in Canada do not have entrance exams. If you expect and encourage students to drop the course because they did not complete ...
- 141
3
votes
Accepted
What programming languages always learned in computer science B.Sc.?
There is no programming language that is taught in every computer science B.A. program. There is a lot of variation in what languages are used to teach material, in different programs. For instance, ...
D.W.♦
- 169k
3
votes
Where should I start to understand how computers work?
Depending on how narrow we understand the question, the answer might be (parts of) a single university course instead of a whole degree.
A course on the design of digital circuits as taught at ETH ...
- 160
3
votes
How to fool the "try some test cases" heuristic: Algorithms that appear correct, but are actually incorrect
For almost 40 years it was thought that an intuitive two-pointers based algorithm for finding a maximum-area triangle inside a convex polygon was correct. It was proved incorrect in https://arxiv.org/...
- 1,339
3
votes
False proofs that look correct
Maybe not exactly what you're looking for, but the Monty Hall problem is famously counterintuitive.
There are three doors. One conceals a car, and the other two goats. You select one door. The host ...
- 396
3
votes
False proofs that look correct
Along the lines of rexkogitans's remark that proofs by induction are fertile ground for false proofs: one of my favorites is that every natural number can be uniquely described in fifteen English ...
- 221
3
votes
Accepted
Easy proof of IP ⊆ PSPACE for private coins
Following the comments, below is a sketch of the proof that shows explicitly that there is no need for the coins to be public, as we can iterate over all random choices in polynomial space.
Sketch of ...
- 5,514
3
votes
What does it mean to prove the halting problem is undecidable "using arithmetization"?
TLDR: It means that they are using a technique to represent Turing machines as numbers in order for the circularity to be possible, hence "arithmetization".
It is not trivial (especially, it ...
- 31
2
votes
Explaining why FFT is faster than DFT for the general public?
What does a Fourier transformation do? It takes a sequence of values, like the sound volume recorded on a CD with 44,100 values per second, and transforms it into frequencies. That is very useful for ...
- 32.6k
2
votes
A physical algorithm that finds all integer partitions of a number
Let us aim at generating the partitions in the following order (below, for $n=6$):
$$
\begin{align*}
& 6 \\
& 5 \, 1 \\
& 4 \, 2 \\
& 4 \, 1 \, 1 \\
& 3 \, 3 \\
& 3 \, 2 \, 1 \...
- 281k
2
votes
resource on translating imperative programs to functional programs
There probably are automated ways of doing it, but the result will be a unreadable mess. You have to understand what the imperative program is doing and rethink it as a functional program. Not easy.
...
- 14.3k
2
votes
Accepted
MOOC recommendations for learning algorithms based on topics covered in Daspupta, Papadimitriou & Vazirani
While I cannot answer your question (MOOC for Dasgupta et al), I will make a different recommendation.
Since you seem to like the more intuitive and slightly informal approaches to learning, rather ...
- 18k
2
votes
Accepted
How does a computer direct the processing of information
Given that this is an introduction, I wouldn't get too concerned about the wording. It's normal to describe things in general terms, and then go into specifics later.
In a typical computer system, ...
- 24.9k
2
votes
Best operating system for a computing degree?
Some Operating Systems that I feel are important to understand are (in no particular order):
Microsoft Research Singularity for its interesting approach of compile-time memory and process isolation, ...
- 6,683
Only top scored, non community-wiki answers of a minimum length are eligible