# All Questions

32,232 questions
Filter by
Sorted by
Tagged with
6k views

### What is the difference between an algorithm, a language and a problem?

It seems that on this site, people will often correct others for confusing "algorithms" and "problems." What are the difference between these? How do I know when I should be considering algorithms and ...
37k views

### Why does Dijkstra's algorithm fail on a negative weighted graphs? [duplicate]

I know this is probably very basic, I just can't wrap my head around it. We recently studied about Dijkstra's algorithm for finding the shortest path between two vertices on a weighted graph. My ...
12k views

### What are common techniques for reducing problems to each other?

In computability and complexity theory (and maybe other fields), reductions are ubiquitous. There are many kinds, but the principle remains the same: show that one problem $L_1$ is at least as hard as ...
20k views

### Contrasting Peterson’s and Dekker’s algorithms

I am trying to understand the algorithms by Peterson and Dekker which are very similar and display a lot of symmetries. I tried to formulate the algorithms in informal language like follows: ...
987 views

### Imagine a red-black tree. Is there always a sequence of insertions and deletions that creates it?

Let's assume the following definition of a red-black tree: It is a binary search tree. Each node is colored either red or black. The root is black. Two nodes connected by an edge cannot be red at the ...
6k views

### What is the name the class of functions described by O(n log n)?

In "Big O", common notations have common names (instead of saying, "Oh of some constant factor"): O(1) is "Constant" O(log n) is "Logarithmic" O(n) is "Linear" O(n^2) is "Quadratic" O(n * log n) ...
2k views

### What should I do with a bunch of 16-17 year olds to get them interested in computer science?

I'm going to be involved with a sort of 'open day' at my university in a few weeks. As part of this time, I (along with a coworker) am being given a whole bunch of high-school level students for two ...
5k views

### How does a computer work?

I have been a computer nerd for many many years. I can program in quite a few languages, and I can even build them. I sat down with a buddy the other day and asked how a computer actually takes ...
20k views

### Why would anyone want CISC?

In our computer systems lecture we were introduced to the MIPS processor. It was (re)developed over the course of the term and has in fact been quite easy to understand. It uses a RISC design, that is ...
7k views

### How does Tarjan's pseudocode work (explained to someone familiar with C or Java)?

The Short Story A famous computer scientist, Tarjan, wrote a book years ago. It contains absolutely bizarre pseudocode. Would someone please explain it? The Long Story Tarjan is known for many ...
3k views

### Explaining the relevance of asymptotic complexity of algorithms to practice of designing algorithms

In algorithms and complexity we focus on the asymptotic complexity of algorithms, i.e. the amount of resources an algorithm uses as the size of the input goes to infinity. In practice, what is ...
26k views

### Is a push-down automaton with two stacks equivalent to a turing machine?

In this answer it is mentioned A regular language can be recognized by a finite automaton. A context-free language requires a stack, and a context sensitive language requires two stacks (which is ...
8k views

### Efficient data structures for building a fast spell checker

I'm trying to write a spell-checker which should work with a pretty large dictionary. I really want an efficient way to index my dictionary data to be used using a Damerau-Levenshtein distance to ...
9k views

### Understanding serialization

I am a software engineer and after a discussion with some colleagues, I realized I do not have a good grasp of the concept serialization. As I understand, serialization is the process of converting ...
4k views

### What is the definition of Computer Science, and what is the Science within Computer Science?

I am pursuing a BS in Computer Science, but I am at an early point of it, and I am pretty sure I will be happy with my choice given that it seems like an academically and career flexible education to ...
9k views

### Is C actually Turing-complete?

I was trying to explain to someone that C is Turing-complete, and realized that I don't actually know if it is, indeed, technically Turing-complete. (C as in the abstract semantics, not as in an ...
1k views

### Is there a regular tree language in which the average height of a tree of size $n$ is neither $\Theta(n)$ nor $\Theta(\sqrt{n})$?

We define a regular tree language as in the book TATA: It is the set of trees accepted by a non-deterministic finite tree automaton (Chapter 1) or, equivalently, the set of trees generated by a ...
5k views

### Is there a known maximum for how much a string of 0's and 1's can be compressed?

A long time ago I read a newspaper article where a professor of some sort said that in the future we will be able to compress data to just two bits (or something like that). This is of course not ...
8k views

### Theoretical machines which are more powerful than Turing machines

Are there any theoretical machines which exceed Turing machines capability in at least some areas?
4k views

### Can PRNGs be used to magically compress stuff?

This idea occurred to me as a kid learning to program and on first encountering PRNG's. I still don't know how realistic it is, but now there's stack exchange. Here's a 14 year-old's scheme for an ...
6k views

### What use are groups, monoids, and rings in database computations?

Why would a company like Twitter be interested in algebraic concepts like groups, monoids and rings? See their repository at github:twitter/algebird. All I could find is: Implementations of ...
38k views

### What exactly (and precisely) is “hash?”

I have heard the word "hash" being used in different contexts (all within the world of computing) with different meanings. For example, in the book Learn Python the Hard Way, in the chapter on ...
14k views

### Deciding on Sub-Problems for Dynamic Programming

I have used the technique of dynamic programming multiple times however today a friend asked me how I go about defining my sub-problems, I realized I had no way of providing an objective formal answer....
1k views

### Are generational garbage collectors inherently cache-friendly?

A typical generational garbage collector keeps recently allocated data in a separate memory region. In typical programs, a lot of data is short-lived, so collecting young garbage (a minor GC cycle) ...
13k views

### Why is the Mersenne Twister regarded as good?

The Mersenne Twister is widely regarded as good. Heck, the CPython source says that it "is one of the most extensively tested generators in existence." But what does this mean? When asked to list ...
8k views

### Clock synchronization in a network with asymmetric delays

Assume a computer has a precise clock which is not initialized. That is, the time on the computer's clock is the real time plus some constant offset. The computer has a network connection and we want ...
9k views