# Tag Info

122

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 undergraduate level has some feature which makes it better for some applications than others. Let's take sorting as an example, since everyone is familiar with ...

78

A common error I think is to use greedy algorithms, which is not always the correct approach, but might work in most test cases. Example: Coin denominations, $d_1,\dots,d_k$ and a number $n$, express $n$ as a sum of $d_i$:s with as few coins as possible. A naive approach is to use the largest possible coin first, and greedily produce such a sum. For ...

66

I immediately recalled an example from R. Backhouse (this might have been in one of his books). Apparently, he had assigned a programming assignment where the students had to write a Pascal program to test equality of two strings. One of the programs turned in by a student was the following: issame := (string1.length = string2.length); if issame then for ...

51

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 machine models (TM, RAM, PRAM,...), average-vs-worst-case as well as amortization considerations to weigh against each other, there are often also functional ...

31

The best example I ever came across is primality testing: input: natural number p, p != 2 output: is p a prime or not? algorithm: compute 2**(p-1) mod p. If result = 1 then p is prime else p is not. This works for (almost) every number, except for a very few counter examples, and one actually needs a machine to find a counterexample in a realistic period ...

24

Here's one that was thrown at me by google reps at a convention I went to. It was coded in C, but it works in other languages that use references. Sorry for having to code on [cs.se], but it's the only to illustrate it. swap(int& X, int& Y){ X := X ^ Y Y := X ^ Y X := X ^ Y } This algorithm will work for any values given to x and y, ...

23

Speaking from experience, when trying to figure out the growth rate for some observed function (say, Markov chain mixing time or algorithm running time), it is very difficult to tell factors of $(\log n)^a$ from $n^b$. For example, $O(\sqrt{n} \log n)$ looks a lot like $O(n^{0.6})$: [source] For example, in "Some unexpected expected behavior results for ...

18

There is a whole class of algorithms that is inherently hard to test: pseudo-random number generators. You can not test a single output but have to investigate (many) series of outputs with means of statistics. Depending on what and how you test you may well miss non-random characteristics. One famous case where things went horribly wrong is RANDU. It ...

18

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 started to wane, somewhere half way through the 1990s. I started studying CS at Nijmegen University in 1982; a classmate did the same at TU Eindhoven. Every ...

16

Quicksort's actually pretty easy to understand, if they understand basic counting and division by 2. Make a bunch of X flash cards, number them 1--X, and shuffle it. Then here's the explanation: OK, we've got this deck of (let's say 20) cards here. We want to put them in order, so 1 is first, then 2, then 3, and so on. Here's a very quick way to ...

15

Here is another (admittedly rather constructed) example, but still one I find remarkable. It is intended to show that plots can be very misleading for judging asymptotic growth. The following plots show two functions $f$ and $g$ — disclosed below ;) — in different ranges. Remarkably, both functions are monotonically (strictly) increasing, (...

14

At its core, Quicksort is this: Take the first item. Move everything less than that first item to the left of it, everything greater to the right (assuming ascending order). Recurse on each side. I think every 4-year-old on the planet could do 1 and 2. The recursion might take a little bit more explanation, but shouldn't be that hard for them. Repeat on ...

13

Insert real-world predicates and read aloud, for instance: It can not be both winter and summer (at any point in time). and (At any point in time) It is not winter or it is not summer. Clearly, the two statements are equivalent.

12

A nice example is Brzozowski's deeply magical minimal DFA algorithm. Given a finite automaton $N = (Q, S \subseteq Q, F \subseteq Q, R \subseteq Q \times \Sigma \times Q)$, we can compute a minimal deterministic finite automaton from it: $$\mathrm{Minimize} : \mathrm{NFA \to DFA} = \mathrm{Determinize\circ Reverse \circ Determinize \circ Reverse}$$ ...

11

If you like to visualize it, use the venn diagrams. See this, for instance. I find it more simple just to memorize the basic 2 laws: everytime you "break" a negation line, you replace the AND to OR (or vice versa). Adding two negation lines changes nothing (but gives you more "lines" to break). It just works.

11

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. (The neighboring cells are those among $A[i, j+1], A[i, j-1], A[i-1, j], A[i+1, j]$ that are present in the array.) So, for example, if $A$ is \begin{...

11

The parts that you mentioned are basic concepts of linear algebra. You cannot understand the more advanced concepts (say, eigenvalues and eigenvectors) before first understanding the basic concepts. There are no shortcuts in mathematics. Without an intuitive understanding of the concepts of span and linear independence you won't get far in linear algebra. ...

10

I would say very definitely teach using Karp (many-one) reductions. Regardless of the benefits of using poly-time Turing reductions (Cook), Karp reductions are the standard model. Everybody uses Karp and the main pitfall of teaching Cook is that you'll end up with a whole class of students who become pathologically confused whenever they read a textbook or ...

9

Fisher-Yates-Knuth shuffling algorithm is an (practical) example and one on which one of the the authors of this site has commented about. The algorithm generates a random permutation of a given array as: // To shuffle an array a of n elements (indices 0..n-1): for i from n − 1 downto 1 do j ← random integer with 0 ≤ j ≤ i exchange a[j] ...

8

These are primality examples, because they're common. (1) Primality in SymPy. Issue 1789. There was an incorrect test put on a well-known web site that didn't fail until after 10^14. While the fix was correct, it was just patching holes rather than rethinking the issue. (2) Primality in Perl 6. Perl6 has added is-prime which uses a number of M-R tests ...

8

It is possible to build a Turing machine with "Lego" elements without any electric components, only with pneumatic transmission of energy. The guys who did this used some logic gates with pneumatic but this was the very easy part. The underlying automaton was way harder to build. (webpage in French. The other Turing machines in Legos use electronic devices ...

8

The mathematical technique of curve fitting can be used to provide an infinite number of answers to your question. Given a curve and a range, one can readily find a polynomial that fits the curve to any degree of accuracy. This example from wikipedia shows how a sin wave can be fairly accurately fitted with a forth order polynomial (the blue curve). I could ...

8

FFT is an algorithm for computing the DFT. It is faster than the more obvious way of computing the DFT according to the formula. Trying to explain DFT to the general public is already a stretch. Also, they probably don't know what an algorithm is. Perhaps you could say that there's a fast way of computing the DFT, and that's one more reason why it's so ...

8

Here are some tips and pitfalls I've collected after using live coding for a week, and from talking to a colleague. DOs Prepare a script to follow and try to stick to it. Clear the buffers frequently to focus on relevant part. Start afresh for each new topic. Use a bigger font. Master the tool you are using, to avoid wasting too much time on trivialities....

7

It is better to teach both! A computer science major should know about both of them. I don't know anyone who uses Cook reductions for teaching NP-completeness, complexity theorists obviously don't, non-complexity theorists typically follow what is the standard definition since Karp's paper and is used in all textbooks (that I know of). It will cause a lot ...

7

Believe it or not, here's a guy who built logic gates using streams of water... http://www.blikstein.com/paulo/projects/project_water.html Apparently, he worked up to a 4-bit adder, though I believe this picture shows only a single half-adder... (source: blikstein.com)

7

My favorite way to teach recursion is by reference to the Recursion Fairy. I'm sure we're all familiar with the idea that stories can be a very effective way to teach ideas; people seem built to hear and remember stories. The Recursion Fairy is an explanation suggested by Jeff Erickson, which lends well to this approach. As Jeff E. writes: Recursion is ...

7

Linear algebra is sometimes extremely useful and powerful in graph algorithms. With the matrix-tree theorem you can efficiently count the number of spanning trees a graph has (you need to understand eigenvalues). A more challenging application, where you need an even firmer grasp of linear algebra is the FKT algorithm for computing the number of perfect ...

7

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 to understand the algorithms / data structures that are used, it is very helpful to know a large number of algorithms / data structures, including options that ...

6

One of the most well known uses of linear algebra is in Google's Pagerank algorithm: The PageRank values are the entries of the dominant left eigenvector of the modified adjacency matrix.

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