We're in a shared memory concurrency model where all reads and writes to integer variables are atomic.
do: $S_1$ in parallel with: $S_2$ means to execute $S_1$ and $S_2$ in separate threads, concurrently.
atomically: $S$ means to execute $S$ atomically, i.e. all other threads ...
A drink dispenser requires the user to insert a coin ($\bar c$), then press one of three buttons: $\bar d_{\text{tea}}$ requests a cup of tea $e_{\text{tea}}$, ditto for coffee, and $\bar r$ requests a refund. This dispenser can be modeled by the following CCS process:
$$ M \stackrel{\mathrm{def...
Intro graphics courses usually have a project that asks you to build a ray tracer to render a scene. Many graphics students entering grad school say that they want to work on ray tracing. And yet it seems that ray tracing is a dead field in venues like SIGGRAPH etc.
Is ray tracing really the be...
I'm pretty fluent in C/C++, and can make my way around the various scripting languages (awk/sed/perl). I've started using python a lot more because it combines some of the nifty aspects of C++ with the scripting capabilities of awk/sed/perl.
But why are there so many different programming langua...
If you have to recommend books for someone who wants to learn more about TCS at the introductory level such as automata theory, algorithmics, complexity theory, etc, what book(s) would you recommend for those who are interested and want to learn more about TCS, but not had any exposure to it?
Fully connected (at least layer to layer with more than 2 hidden layers) backprop networks are universal learners. Unfortunately, they are often slow to learn and tend to over-fit or have awkward generalizations.
From fooling around with these networks, I have observed that prunning some of the...
We got our first list question. In the light of this discussion, this is what I want to do:
Ask users to propose only one book per answer.
Create one CW answer per field (algorithms, mathematical foundations, logics, languages & automata).
Incorporate all answers with score at least five an...
Are Questions like "(Where) will I ever need Automaton-Theory / P/NP / ... after I finished my studies?" okay? They are kind of meta-y, but somewhat related to CS and I have no idea where you would ask these questions if not here.
Example Questions would be:
Where will I need P/NP-theory after...
We had at least one interview question on the site already. This is not a proposal to ban them or anything like that, but I think a tag like interview-question would be beneficial for everyone:
The Question might get more attention, since it's always good to see what questions might be asked in...
@Gilles: I tough I had made a suggested edit (to add "process-algebras" tag to your css question), but it does not appear anywhere in my activities lists.
To my knowledge, there are three major process algebras that have inspired a vast range of research into formal models of concurrency. These are:
CCS and $\pi$-calculus both by Robin Milner
CSP by Tony Hoare and
ACP by Jan Bergstra and Jan Willem Klop
All three seem to have to this day a quit...
This answer summarises parts of TAoCP Vol 3, Ch 6.4.
Assume we have a set of values $V$, $n$ of which we want to store in an array $A$ of size $m$. We employ a hash function $h : V \to [0..M)$; typically, $M \ll |V|$. We call $\alpha = \frac{n}{m}$ the load factor of $A$.
Here, we will assume th...
@Gilles is this more like what you were looking for?
Windows NT used a point-to-point protocol where a client can communicate "securely" with a server by using a stream cipher to encrypt an array of messages with some key $k$. The server also encrypts its response with the same key $k$. But how is it aware of this key?
More general: if Alice and B...
(inspired by the second bullet in this question)
I read in many places that some problems are difficult to approximate (it is NP-hard to approximate them). But approximation is not a decision problem: the answer is a real number and not Yes or No. Also for each desired approximation factor, th...
@Gilles I saw their announcement. I think that we were paddling during the 3-4 first days. but then came the "kick" and on the 8-9th day we were clear to go.
I feel it starts to be "boring" due to the small number of current users
In a standard algorithms course we are taught that quicksort is $O(n \log n)$ on average and $O(n^2)$ in the worst case. At the same time, other sorting algorithms are studied which are $O(n \log n)$ in the worst case (like mergesort and heapsort), and even linear time in the best case (like bubb...
I'm learning programming in ML (OCaml), and earlier I asked about ML functions of type 'a -> 'b. Now I've been experimenting a bit with functions of type 'a list -> 'b list. There are some obvious simple examples:
let rec loop l = loop l
let return_empty l = []
let rec loop_if_not_empty = ...
It is often said that hash table lookup operates in constant time: you compute the hash value, which gives you an index for an array lookup. Yet this ignores collisions; in the worst case, every item happens to land in the same bucket and the lookup time becomes linear ($\Theta(n)$).
Under what ...
As you said, there is no decision to make, so new complexity classes and new types of reductions are needed to arrive at a suitable definition of NP-hardness for optimization-problems.
One way of doing is to have two new classes NPO and PO that contain optimizations problems and thei mimic of co...
From the answers to (When) is hash table lookup O(1)?, I gather that hash tables have $O(1)$ worst-case behavior, at least amortized, when the data satisfies certain statistical conditions, and there are techniques to help make these conditions broad.
However, from a programmer's perspective, I ...
From the answers to (When) is hash table lookup O(1)?, I gather that hash tables have $O(1)$ worst-case behavior, at least amortized, when the data satisfies certain statistical conditions, and there are techniques to help make these conditions broad.
However, from a programmer's perspective, I ...
@RanG I've edited your answer to show what protocol design guideline was violated, feel free to rollback or edit if you don't like my formulation (in which case I'll leave a comment)
@Gilles That's cool. I wanted to add something similar as well, to say that there is no use for Bob to just encrypt whatever some (anauthenticated) party asks him to.
Fully connected (at least layer to layer with more than 2 hidden layers) backprop networks are universal learners. Unfortunately, they are often slow to learn and tend to over-fit or have awkward generalizations.
From fooling around with these networks, I have observed that prunning some of the...
Are Questions like "(Where) will I ever need Automaton-Theory / P/NP / ... after I finished my studies?" okay? They are kind of meta-y, but somewhat related to CS and I have no idea where you would ask these questions if not here.
Example Questions would be:
Where will I need P/NP-theory after...
To my knowledge, there are three major process algebras that have inspired a vast range of research into formal models of concurrency. These are:
CCS and $\pi$-calculus both by Robin Milner
CSP by Tony Hoare and
ACP by Jan Bergstra and Jan Willem Klop
All three seem to have to this day a quit...
(inspired by the second bullet in this question)
I read in many places that some problems are difficult to approximate (it is NP-hard to approximate them). But approximation is not a decision problem: the answer is a real number and not Yes or No. Also for each desired approximation factor, th...
