DylanSp
  • Member for 5 years, 10 months
  • Last seen this week
6 answers
20 votes
3k views
Why must uncommitted transactions be undone in backwards order?
36 votes

Original transactions: Insert record $r$. Update some field $f$ of $r$. Forward undo: Delete record $r$. Reverse the update to $r$ - oh wait, $r$ no longer exists! This causes an error.

View answer
3 answers
12 votes
3k views
Regular languages that can't be expressed with only 2 regex operations
Accepted answer
19 votes

With only union and concatenation, you can't describe any infinite language. The union and concatenation can only produce finitely many strings. With only union and the Kleene star, you can't describe ...

View answer
1 answers
0 votes
59 views
Is it possible to compute -12 (decimal) in 4 bits binary
Accepted answer
7 votes

No, it's not possible, at least using the standard representations. An unsigned $n$-bit number can represent any integer in the interval $[0, 2^{n} - 1]$. A signed $n$-bit number using two's ...

View answer
1 answers
0 votes
532 views
Difference between 2f+1, 2f and 3f+1
Accepted answer
4 votes

$2f$ and $2f + 1$ are just numbers. A set of $2f + 1$ nodes has a majority of non-faulty nodes, as you say; a set of $2f$ nodes can be deadlocked between the non-faulty and faulty nodes. A total of $...

View answer
2 answers
2 votes
3k views
Running time of selection sort
2 votes

The inner loop will iterate $n - r + 1$ times for each iteration of the outer loop. To find the total runtime, we can sum this expression over $r = 1$ to $r = n$: \begin{align*} \sum_{r = 1}^{n} (n - ...

View answer
3 answers
1 votes
3k views
Acceptance of empty string by nondeterministic automaton
2 votes

To expand on Denis's answer, the given automata is non-deterministic because it has $\epsilon$-transitions. Because it's non-deterministic, given an input of the empty string $\epsilon$, we don't have ...

View answer
4 answers
3 votes
898 views
How to determine if a regular language L* exists
2 votes

Simply saying that $L$ has the alphabet $\{x, y\}$ and that no string in $L$ contains the substring $xx$ doesn't define a single language - there are infinite such languages. What you call expressing $...

View answer
2 answers
5 votes
213 views
What data structure might this game use?
0 votes

Sounds like you'd want a 1:1 mapping of elements to numbers, starting at 1 (using an enumerated type or something similar, depending on the implementing language), then use a sparse matrix to store ...

View answer