All Questions

Filter by
Sorted by
Tagged with
0 votes
0 answers
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 ...
user avatar
  • 101
0 votes
0 answers
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 ...
user avatar
  • 1
4 votes
1 answer
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 ...
user avatar
0 votes
2 answers
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$: ...
user avatar
  • 157
0 votes
0 answers
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: ...
user avatar
1 vote
2 answers
47 views

Can this algorithm for 2-dimensional points be generalized to 3 dimensions?

There is a list of 3-dimensional points $(x_1,y_1,z_1),\ldots,(x_m, y_m,z_m)$, where all coordinates are non-zero integers. I would like to decide whether there exist positive real weights $w_x, w_y, ...
user avatar
0 votes
1 answer
28 views

Time reversible Markov chains question

Let Q be a symmetric transition probability matrix on states 1 , . . . , n; that is $q_{i,j} = q_{j,i}$ for all i , j. Consider a markov chain defined as follows. Whenever the chain is in state i, the ...
user avatar
1 vote
0 answers
18 views

Negotiating a connection between two devices that can't transmit and receive simultaneously

I've got a bit of a puzzle here that sits at the intersection of mathematics and technology. Hopefully this doesn't fall into brainteaser territory - I'm not sure a neat solution is possible! I have ...
user avatar
1 vote
1 answer
20 views

Semi-bounded probabilistic polynomial-time, is it equal to BPP?

The complexity class $\mathsf{BPP}$ is typically defined as the class of all problems for which: Running an algorithm once takes polynomial time at most. The answer is correct with the probability at ...
user avatar
  • 1,393
8 votes
13 answers
6k views

Why do we rely on computers in critical fields?

I assume that computers make many mistakes (like errors, bugs, glitches, etc.), which can be observed from the amount of questions asked everyday on different communities (like Stack Overflow) showing ...
user avatar
  • 215
-4 votes
0 answers
30 views

Whats the big O notation of the following code?

int j , f; System.out.println("enter a number"); ...
user avatar
0 votes
1 answer
47 views

Is the set of Turing machines that halt on infinitely many inputs not recursively enumerable?

Consider this "generalized halting problem": $$ GHP = \{<M>| \mbox{ there are infinitely many inputs that $M$ halts on}\}. $$ I'd like to prove that $GHP\notin RE$, but it doesn't seem ...
user avatar
  • 3
3 votes
1 answer
87 views

"Hack computer" from Nand2Tetris registers, any real world examples of similar design?

The "Hack CPU" (Wikipedia/Hack_computer) is a theoretical computer design created by Noam Nisan and Shimon Schocken and described in their book and also used in their Coursera course ...
user avatar
-1 votes
1 answer
132 views

How to prove that P = NP?

So if someone proves with an algorithm that SAT can be solved in deterministic polynomial time, then P = NP and that's it?
user avatar
1 vote
0 answers
66 views

LWE with a low rank matrix

Consider the decision LWE setting, where we have to distinguish between $(A, As + e)$ and $(A, u)$, for a randomly chosen $m \times n$ matrix $A$, an $n \times 1$ secret vector $s$, an $m \times 1$ ...
user avatar
  • 219
2 votes
0 answers
33 views

What benefit does the brain have on computers in a human brain computer

The concept of brain computer implants assumes that there's some net positive for either a machine or the brain when it comes to calculating or computing things. Usually there is a focus on what the ...
user avatar
  • 121
1 vote
0 answers
30 views

What is the circuit depth of asymptotically fast multiplication algorithms?

I know the circuit depth (i.e. amount of sequential operations on the longest path) for long multiplication can easily be made $O(\log(n))$ (possibly at the cost of increasing the computational ...
user avatar
  • 111
0 votes
0 answers
26 views

How much faster is Montgomery multiplication?

Montgomery multiplication is used to speed up the computation of modular products for large moduli, with respect to simpler techniques such as Barrett reduction or plain division. In practical ...
user avatar
  • 121
0 votes
0 answers
32 views

Is this version of the halting problem NONELEMENTARY?

Input: A TM $M$ and an integer $k$. Output: Yes if $M$ halts within $2\uparrow\uparrow k$ steps (where $\uparrow\uparrow$ is tetration (iterated exponentiation)). Intuitively, it seems like this has ...
user avatar
  • 1
2 votes
0 answers
51 views

What are strong examples of programming languages whose type systems don't embed into their native type theory?

Given a typical popular programming language, its native type theory is a dependent type theory which describes invariants, preconditions, predicates, and other generalizations of typical type-system ...
user avatar
  • 211
0 votes
0 answers
10 views

Editing facial features

Photoshop offers some great image processing filters under the term "Face-Aware Liquify". I want to integrate such techniques into an automated processing system I am currently implementing (...
user avatar
0 votes
1 answer
60 views

Is Huffman coding dynamic programming

Huffman coding follows a bottom-up approach where as Shannon-Fano coding is top-down. Is that contrast similar to dynamic programming versus greedy algorithm (dynamic programming always give optimal ...
user avatar
  • 153
2 votes
2 answers
121 views

How can we show that P is not closed under taking all long prefixes?

Let P be the complexity class of languages decidable by Turing machines running in polynomial time. Say a prefix $s$ of a string $x$ is a long prefix (or an L prefix) if $|s|\ge |x|/2$. For a language ...
user avatar
-1 votes
0 answers
47 views

Determine response of convolution kernel

I have a bank of convolutional filters, and I want to know if there is a way to determine their responses, ie.: the dominant angle that will be preserved after convolution. Example filters Thanks, ...
user avatar
-1 votes
1 answer
38 views

Weigher problem

I got interested in one problem. I have $N$ rocks, where rock with minimum weight have number equal to $1$, the next heaviest stone has a number equal to 2, etc.. So a rock with maximum weight have a ...
user avatar
  • 1
0 votes
2 answers
57 views

Why scopes in general do not have prologue and epilogue instructions?

Data only accessible in a scope, seems to still be maintained by the stack. What is the reason that entering and exiting scopes (in general) does not do the same "prologue and epilogue" ...
user avatar
1 vote
1 answer
39 views

Relation between algorithms and models

I have found this question some time ago. While reading it, I had a problem with understanding the following idea: Question, part 1: Is one allowed to talk about the time/space bound of any algorithm (...
user avatar
0 votes
0 answers
27 views

Rank of random binary string with Bernoulli distribution

For $1\ge p_1 \ge \dots \ge p_n \ge 0$, and for $i\in[n]$ draw $k$ iid binary strings with $m$ length: $$X_{i,1},\dots,X_{i,k}\stackrel{iid}{\sim} \text{Bernoulli}(p_i)^m.$$ Viewing these binary ...
user avatar
0 votes
1 answer
59 views

How to resolve the clash between definition of Big O notation and Inductive Hypothesis when proving running time by substitution method?

Suppose you have to prove the solution to the following recurrence by Induction, $$ T(n)= \begin{cases} \Theta(1), & n=1 \\ 2 T(\lfloor n/2 \rfloor)+\Theta(n), & n>1 \end{cases} $$ Here, $\...
user avatar
  • 151
1 vote
1 answer
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$, ...
user avatar
-3 votes
1 answer
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 ...
user avatar
0 votes
1 answer
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 ...
user avatar
0 votes
1 answer
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-...
user avatar
0 votes
1 answer
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 ...
user avatar
  • 233
18 votes
4 answers
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 ...
user avatar
2 votes
0 answers
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 ...
user avatar
  • 121
-1 votes
0 answers
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 ...
user avatar
-3 votes
0 answers
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 ...
user avatar
-2 votes
0 answers
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.
user avatar
-3 votes
0 answers
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'.
user avatar
0 votes
1 answer
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,...
user avatar
0 votes
1 answer
26 views

Reductions but no algorithms

in "Introduction to Automata Theory, Languages and Computations" by Motwani, Ullman and Hopcroft, when they need to prove, for instance, Rice's theorem, they reduce the universal language, $...
user avatar
  • 1
1 vote
1 answer
28 views

Max flow bottleneck approach flow after k iterations

This is a question from a previous exam in Graph theory and algorithms, the correct answer is E but I don't understand why. Given a network flow $(G,c)$ over graph $G(V,E) $. Assume we run Edmonds-...
user avatar
0 votes
1 answer
45 views

How this state set of DFA was retrieved from the given NFA

I have this NFA: 1,{2, 3} 2,empty 3,{4} 4,empty All the arrows in this NFA are epsilon-arrows. I understand that all possible states that can be reached from each ...
user avatar
-2 votes
0 answers
31 views

What is the time complexity of this code?

...
user avatar
0 votes
1 answer
58 views

Efficient Method for Distance Comparison in Euclidean Space

I have a vector of 2D Euclidean coordinates, and I need to find out if two or more points are within a distance threshold. The naive approach is to compare each point with every other point, but I am ...
user avatar
0 votes
2 answers
41 views

If $f \in \mathcal{o}(g)$, does $f \circ g \in \mathcal{o}(g \circ f)$?

It's a widely known fact that $\lambda n. \left\lfloor \lg n! \right\rfloor \in \mathcal{O}(\lambda n. \left\lfloor \lg n \right\rfloor!)$. Is it also true (I tried and haven't found a counterexample ...
user avatar
  • 115
1 vote
1 answer
40 views

Is $k$-means clustering strictly NP-hard?

I've had lectures and read other threads claiming that $k$-means clustering is NP-hard. The fact that they never mention NP-completeness makes me suspect that strict NP-hardness is what's meant. This ...
user avatar
  • 121
0 votes
0 answers
35 views

Disjoint $k$ Increasing Subsequences

Given a permutation $P$ and an integer $k$, we need to devise an algorithm which finds the $k$ disjoint increasing subsequences (say $L_1,L_2\ldots, L_k$) such that the sum total of their lengths (say ...
user avatar
  • 122
1 vote
1 answer
38 views

Prove that the "6-rule" CFG for arithmetic expressions below is unambiguous

Question: Prove that the 6-rule CFG for arithmetic expressions below is unambiguous. The CFG is as follows. $G = (V:=\{E,T,F\}, \Sigma:=\{+, \times,(,),x\},R,E\})$ where $R$ consists of 6 rules: $E\...
user avatar

15 30 50 per page
1
3 4
5
6 7
898