# All Questions

44,851 questions
Filter by
Sorted by
Tagged with
8 views

### Are there solutions available anywhere for Matt Bishop's Computer Security: Art and Science?

I have been reading Matt Bishop's great textbook Computer Security: Art and Science, but cannot find solutions to the exercises anywhere. Has anyone come across them before on their journey across the ...
26 views

### Resources to learn about the fundamentals of computers? [duplicate]

I have been wanting to learn more about how computers work. Getting way ahead of myself, but as in would it be possible to build a computer from scratch by myself? I mean build the individual parts ...
268 views

### What are the languages produced by context free-grammars with backspace?

If we add backspace to the output alphabet, are all the languages produced still context-free? (If not, then what are they?) The word (a, b, c, Backspace, Backspace), for example, gets interpreted as ...
37 views

### Loops running time as function of n

Suppose I have the following code and I'd like to compute running time as function of $\ n$: ...
19 views

### Given an instance of a HORN-SAT problem with at most 3 literals per clause, what context-free grammar is equivalent to deciding the problem?

Given an instance of a HORN-SAT problem with at most 3 literals per clause, what context-free grammar is equivalent to deciding the problem? For example, here are some HORN clauses: ...
1 vote
47 views

1 vote
39 views

### Average and max. hitting time to a specific vertex [closed]

Consider simple random walks that stop when reaching a given node $x$ in an undirected, unweighted and connected graph on $n$ nodes. Let $H(i,x)$ denote the (expected) hitting time from $i$ to $x$, ...
119 views

### Identify the missing number in a set given its superset

Given a set B and B’s superset A, if B is missing 1 number (let’s y) but don’t know which number it is, how to find that number? That is, B’ = B \ {y}, for some unknown element y B = A \ {x}, for ...
24 views

### How to approximate percentile value from value-count map?

Background: How Percentile Approximation Works (and Why It’s More Useful Than Averages) In traditional scenario, we store each value in an array/slice, in that case, we can just sort the array, and ...
38 views

### Proving grammar equivalence in simple grammar (generate any sequence of three characters)

Goal is proving grammar equivalence Upper-case symbols are non-terminal. Lower-case symbols are terminal. The start symbol is S. A grammar production rule is non-...
32 views

### How substituituion composition is associative?

I'm not convinced that substitutions are associative, I read the https://en.wikipedia.org/wiki/Substitution_(logic)#First-order_logic and the https://www.youtube.com/watch?v=_cVNeccMF-E My problem is ...
4k views

### Is there a PRNG that visits every number exactly once, in a non-trivial bitspace, without repetition, without large memory usage, before it cycles?

PRNGs (pseudorandom number generators) generally have a bit length for the binary numbers they generate (e.g. 32 bits, 64 bits). This is the universe of their possible numbers. It seems that they ...
39 views

### An inverse problem of lexicographic product of graphs

In graph theory, the lexicographic product or (graph composition) $G ∙ H$ of graphs $G$ and $H$ is a graph such that the vertex set of $G ∙ H$ is the cartesian product $V(G) × V(H)$; and any two ...
45 views

### Periodic solutions to coupled nonlinear differential equations

I have a problem involving a system of coupled nonlinear second order differential equations for a physical problem. They are too complicated to be written here but can be solved in Wolfram ...
35 views

### How does Lucene stores indexes that it caused ElasticSearch to remove document type feature?

This question sounded for me too cs than datascience as I'm not working with codes. So I asked here. ElasticSearch removed "1 index, many document types" feature from some version. I think ...
27 views

### Context-free grammar for {a i b j |i, j ≥ 0 and i ̸= j} [duplicate]

I know the CFG for when a^ib^j, i, j>= 0 but with the additional condition of i!=j, I don't know how to do it.
16 views

### Reduction Proof for ALL2_{PDA} using ALL_{CFG} is undecidable

Would appreciate a step by step solution to doing this - I'm stumped on how to start beyond the creation of a new machine M'.
49 views

### Program counter in ISA with multi-word size for instructions

Some ISA's have instructions that are multiple words, such as the MOV instruction in x86. How does the program counter behave in that case, if the instruction loaded is more than one word? For example,...