128

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 ...


123

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. Computer Graphics/Image Processing, and here you will also need Analytic Geometry and Linear Algebra, heavily! If you go down this path, you may also want to ...


86

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 ...


68

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 ...


59

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 that they do this task methodically: if this number is greater than 9, then add a carry, and so forth. This description they just gave of what to do that is an ...


52

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 ...


44

Yes, I would say knowing something about computational complexity is a must for any serious programmer. So long as you are not dealing with huge data sets you will be fine not knowing complexity, but if you want to write a program that tackles serious problems you need it. In your specific case, your example of finding connected components might have worked ...


34

"So why was assembly language created?" Assembly language was created as an exact shorthand for machine level coding, so that you wouldn't have to count 0s and 1s all day. It works the same as machine level code: with instructions and operands. "Which one came first?" Wikipedia has a good article about the History of Programming Languages "Why am I ...


33

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 ...


31

Why do we need assembly language? Well, there's actually only one language we will ever need, which is called "machine language" or "machine code". It looks like this: 0010000100100011 This is the only language your computer can speak directly. It is the language a CPU speaks (and technically, different types of CPUs speak different versions). It also ...


29

How about an automotive analogy? uses computers and maybe "is good with computers" :: a driver (can drive and refuel safely) and maybe a car enthusiast (can jump start a car; is familiar with many makes and models; knows techniques like using windshield treatment to keep rain from reducing visibility). programmer :: an automotive mechanic or technician. ...


27

In image processing, an image is "processed", that is, transformations are applied to an input image and an output image is returned. The transformations can e.g. be "smoothing", "sharpening", "contrasting" and "stretching". The transformation used depends on the context and issue to be solved. In computer vision, an image or a video is taken as input, and ...


26

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, ...


26

This is a rebuttal of Tom van der Zanden's answer, which states that this is a must. The thing is, most times, 50.000 times slower is not relevant (unless you work at Google of course). If the operation you do takes a microsecond or if your N is never above a certain threshold (A high portion of the coding done nowadays) it will NEVER matter. In those ...


25

Since it is an english major: Computer literacy is like reading, computer programming like composition, and computer science like linguistics. All 3 are about language, but the skills are not exactly interchangable.


25

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 of the whole subject. This is very technical terminology, so let's explain. Algebraic Data Types You may have come across tuples being referred to as product ...


24

Asking how you can study computer science without computers is a bit like asking how you can study cosmology without telescopes. Sure, it's nice to be able to look at the things you're studying and it's often very helpful to be able to play around with things. But there's a whole lot you can do without access to a computer: in extremis, you could probably do ...


21

You can have them draw pictures using context-free grammar. context free art This also works for people who never programmed before and scales to experienced programmers. The basic language is easy enough to explain in maybe half an hour. Learning something about geometry using Turtle graphics should be nice too. Logo was designed for children, so highschool ...


19

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 ...


19

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. For example, if you edit a Word document and press a key, the computer will show the letter you pressed. That's because a programmer wrote a program saying: If ...


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

So why was assembly language created? or was it the one that came first even before high level language? Yes, assembly was one of the first programming languages which used text as input, as opposed to soldering wires, using plug boards, and/or flipping switches. Each assembly language was created for just one processor or family of processors as the ...


14

Let me add one less practical aspect. This is (probably) not a historic reason but a reason for you, today. Assembly (compared to high-level languages) is naked. It does not hide anything (that is done in software), and it is simple in the sense that it has a relatively small, fixed set of operations. This can be helpful for exact algorithm analysis. ...


14

I've been developing software for about thirty years, working both as a contractor and employee, and I've been pretty successful at it. My first language was BASIC, but I quickly taught myself machine language to get decent speed out of my underpowered box. I have spent a lot of time in profilers over the years and have learned a lot about producing fast, ...


13

Check out Computer Science Unplugged. From their site: CS Unplugged is a collection of free learning activities that teach Computer Science through engaging games and puzzles that use cards, string, crayons and lots of running around. The activities introduce students to underlying concepts such as binary numbers, algorithms and data compression, separated ...


13

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 crucial idea for more elaborate models). To prove DFA and NFA accept the same set of languages is also exploring a very important phenomenon in a simple, ...


13

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 to design an algorithm that will compute the solution. Isn't that the only thing that separates programmers from scientists?


13

Automation - Similar to robotics, automation can require quantifying a lot of human behavior. Calculations - Finding solutions to proofs often requires calculus. Visualizations - Utilizing advanced algorithms requires calculus such as cos, sine, pi, and e. Especially when you're calculating vectors, collision fields, and meshing. Logistics and Risk ...


12

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 ...


12

Somebody put it to me this way but I'm afraid I've forgotten who. Disinfecting your kitchen isn't microbiology; operating your computer isn't computer science.


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