A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

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

114

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

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

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

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

47

This is a broad question that does not have an easy answer; it's a long way from electrons skittering along copper wires to rendering a website in Firefox. I will attempt to give you an overview from bottom to top and point you towards the right things to look up. Encoding Numbers The basic motivation is to compute things, as in doing arithmetics¹. The ...

42

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

32

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

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

29

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

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

The complete picture is fairly complicated. There are many layers built on top of one another that collectively implement high-level abstractions on top of electrical voltages. There is no simple explanation of how everything is put together, especially considering that computer hardware and software has evolved dramatically in the past fifty years. If ...

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.

24

The interesting question is: what is the alternative? The only other method I know is testing/benchmarking. We program the algorithms, let them run on (a representative sample of) the finite input set and compare the results. There are a couple of problems with that. The results are not general in terms of machines. Run your benchmark on another computer ...

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

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

22

Roger Wattenhofer's Principles of Distributed Computing lecture collection is also a good place to start. It is freely available online, it assumes no prior knowledge on the area, and the material is very well up-to-date — it even covers some results that were presented at conferences a couple of months ago.

22

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

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

20

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

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

18

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

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

16

I think that learning about computer science certainly can be an advantage. Here are a number of (related) skills computer science has to offer. Programming – knowing how to program is a useful skill for any discipline. Statisticians and sociologists, geographers and engineers, and so on, often find themselves needing to program. Following a CS degree ...

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

15

I learned about algorithms in a university course years ago. But if you are to do algorithms using a book, then you need a good one. Two books stand out for me as the way to get into algorithms: The Algorithm Design Manual by Steven S. Skiena Introduction to Algorithms by T Cormen, C Leiserson, R Rivest and C Stein The first is perhaps more of a hands-on ...

15

Abstraction is pretty much bread and butter in computer science but unfortunately it is hard to teach explicitly. In my opinion, understanding concepts is more important than being able to mechanically calculate or prove stuff. Sure, you need to know your way around some elementary methods, but the meat lies elsewhere. First of all, you have to grasp the ...

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