# All Questions

41,026 questions
Filter by
Sorted by
Tagged with
0answers
2 views

### Given an array A and a minimum heap H which of the following are true?

I got this series of questions, each needs to either be proved or disproved (w/ example). If $A$ is sorted in non-descending order, it is a valid minimum heap. If $H$ is represented by $A$, therefore ...
0answers
17 views

### How to make genes look like computer machine language?

How to make genes look like computer machine language? 更多相关中文内容
1answer
21 views

### Understanding a summation notation. Sum(j=2 to n) j - 1

I have been reading analysis of insertion sort in the "Introduction to algorithms" and faced a problem with understanding a specific summation notation when the worst case occurs. I know how ...
2answers
117 views

### If regex describes FSAs, what string formats describe Turing machines?

(Topic summary under the line.) Regex, at least the formal definition featuring only | and *, is used to describe words accepted by a given FSA, but it can be transformed into the corresponding state ...
1answer
7 views

### Finding the distance from a point to a $R^m$ restricted area in $R^n$

The problem is described below: When m=2 and n=3, it is basically finding the distance between a point and a line segment in $R^3$. But when both m and n are larger, do I have to use a generic ...
1answer
13 views

### How would you specify a grammar that can parse letters separated by single underscores?

In JavaScript, let's say, it is easy to build a string intermixed with single underscores by just joining the string parts. ...
1answer
16 views

### Effectively decidable vs. noneffectively (or ineffectively) decidable

The introduction of https://www.sciencedirect.com/science/article/pii/0001870882900482 starts with the following sentence: The word problem for commutative semigroups is effectively decidable. I ...
1answer
32 views

### Reason that integers are used for priorities instead of float

Why are priorities always from a fixed set of integers? In operating systems priorities are integers typically between 1..MAX. But what is the reason that this is the case, when it would obviously be ...
1answer
26 views

### Is $L = \{xw^3x^{rev}\mid x, w\in\{0, 1\}^*\}$ context-free?

The title pretty much explains the question, but still: Is the language $$L = \{xw^3x^{rev}\mid x, w\in\{0, 1\}^*\}$$ context-free? I think it isn't and would motivate that suspicion by the following ...
0answers
11 views

### Z-function and the minimum string period

Let $s$ be a string of length $n$. One of the classical solutions to the problem of finding the smallest period $p$ of $s$ (that is, smallest $p$ such that $s$ can be obtained as a concatenation of ...
1answer
18 views

0answers
22 views

### Is it possible to reverse engineer cellular automata?

Given a sequence of states of a given cellular automata, is it possible to construct the rules of the automata & hence predict the next state? To be clear, initially the rules are NOT known but ...
1answer
29 views

### Is it true that PRIMES are in SPARSE?

I'm wondering if PRIMES, the language of all prime numbers represented in binary, which is $\{10, 11, 101, 111, 1011, 1101, ...\}$, belongs to the SPARSE class, a set of all sparse languages, that is, ...
1answer
15 views

### Is pipeline bubbling only used with RAW data hazards?

I am studying computer science at university and we have an exam, which consists of several problems, one of which has to deal with pipelines. My understanding is that one effective way to solve data ...
0answers
19 views

### equivalence of validity above different alphabet

Given the next alphabets: $\,\,\Sigma_1=\{R^2,P^1,=^2\}\,\,,\Sigma_2=\{c,f^1,=^2\}.$ Prove of Disprove: There's exists an algorithm, that given formula $A$ above $\Sigma_2$, builds formula $A'$ above ...
0answers
14 views

### As a system administrator, which document will I use to understand inter-module interaction,database architecture & application architecture ofSystem?

As a system administrator, which of the following documents will Sachin use as a manual to understand inter-module interaction, database architecture and application architecture of a system? a) High-...
0answers
20 views

### Online cycle detection but not quite: the Featherstitch problem

Featherstitch (Frost et al., 2007) is an approach for representing data consistency requirements for disk storage. This question concerns a graph-theoretic problem (§4.1 in the paper) that its ...
0answers
19 views

### Minimum number of elements in AVL tree to make it worth creating

Given an AVL tree containing nodes ordered by unique integer I.D's and data as pointers to some struct, what would be the expected minimum number of elements that will justify the creation and ...
1answer
17 views

### Parts of a function used in Space Complexity

I'm finding contradictory information online where some places only consider auxiliary space and others define it as Space Complexity of an algorithm is total space taken by the algorithm with ...
1answer
37 views

### Context-free grammar for $a^{2n} b^{2n}$

I have just started learning formal languages and here is a question I am facing a little hurdle: Construct a context-free grammar for $\{ a^{2n}b^{2n} \mid n \ge 0 \}$. This was what I got at first....
2answers
273 views

### Should the certificate for NPSPACE be polynomial in size?

There is a problem that I am working on. I have shown that the problem is NP Hard, but I haven't been able to show that it is in NP. But the problem is also known to be in EXP. My gut feeling is that ...
1answer
43 views

### Minimum number of groups such that every element in graph is included?

Problem Description Note: I originally posted this question on Stack Overflow but was referred to this community instead. I have a graph containing selectors and elements. An element can have multiple ...
0answers
12 views

### How does the railway model of computation get translated to motion on the heptagrid tiling of the hyperbolic plane?

I have been reading these, along with slowly chipping away at the two books Margenstern has produced: A universal cellular automaton in the hyperbolic plane A Universal Cellular Automaton on the ...
2answers
27 views

### How do you express a floor / ceiling in the approximation factor of an approximation algorithm?

Intuitively I feel like this is a bit of a dumb question, and is probably related to my vague understanding of approximation algorithms and whatnot. Suppose I have some minimisation problem $X$ where, ...
1answer
24 views

### How are two registers are enough to simulate a Turing machine?

The paper A universal cellular automaton in the hyperbolic plane says: Our simulation consists in simulating the execution of a register machine. It is known that two registers are enough to simulate ...
0answers
23 views

### Why do exact MaxSAT algorithms scale exponentially as a function of the number of clauses?

As stated in this recent paper from ijcai https://www.ijcai.org/Proceedings/2019/0166.pdf The top -Exact- algorithms worst case complexities are stated as follows where m is the number of clauses in ...
2answers
31 views

### Loop Invariants: Can someone explain this concept?

I am reading Algorithms Unlocked By Tom Cormen and find this concept a little confusing. Why is it that we require loop invariants and how does it help in analyzing algorithms?
0answers
16 views

### CSES Question - Tower [closed]

Ques Link: https://cses.fi/problemset/task/1073/ Code Link: https://pastebin.com/S9nzVJVa In CSES question : Towers, I know it can be solved using sets with greedy approach but I was trying to do ...
1answer
21 views

### Question about reduction Proof

I've recently seen a proof that the set of Turing machines $L = \{encode(M) |L(M) \text{is closed under reversal}\}$ is not decidable. The proof used following idea: Reduce from the $A_{TM}$ problem ...
0answers
9 views

### Asymptotically Optimal Universal Code In Other Bases

Universal codes are fairly well studied, and many asymptotically optimal universal codes exist for binary data (see https://en.wikipedia.org/wiki/Universal_code_(data_compression) especially https://...
1answer
9 views

### Under which circumstances a process in ready state can switch to exit without transition into any other intermediate state?

I was studying for an exam when I stumbled across this true or false statement: In a system of 7 states diagram, a process could switch from ready state to exit state directly. The answer to this ...
1answer
28 views

### Generalization of Cellular Automata

So in the little I know about formalization of cellular automata, it appears there are 4 major categories of cellular automata: 1-dimensional (cellular automata on the line) 2-dimensional (cellular ...
1answer
19 views

### Iteration Vs Induction Method

I am working on different methods to solve Recurrence Relations. I am using Iteration method and substitution method, which involves Induction, but I feel that sometimes Induction method creates a bit ...
1answer
41 views

### Is ANN a data structure or an algorithm?

When I read about Artificial Neural Networks (ANN), no one says what ANN is. For instance, Wikipedia says: Artificial neural networks (ANNs), usually simply called neural networks (NNs), are ...
1answer
17 views

For a sentence $\varphi$, we'll define $Spec(\varphi)$ to be the set of all $n\in\mathbb{N}$ for which there is a model $M$ with $|D^M|=n$, such that $M\models\varphi$. Let $\Sigma=\{P(\cdot),R(\cdot)... 1answer 14 views ### Show that the Turing Reduction is transitive: if$A\leq_{T}B$and$B\leq_{T}C$then$A\leq_{T}C$I am struggling with this question, because I came up with an relatively easy proof for mapping reduction: if$A\leq_{M}B$and$B\leq_{M}C$then$A\leq_{M}C$. We know that$w \in A\Leftrightarrow$... 1answer 36 views ### How to prove the same states are repeating in Synchronizable DFA? I'm trying to prove the if$𝑀$is a$𝑘$-state synchronizable DFA, then it has a synchronizing sequence of length at most$𝑘^3$. first I have to prove that if a string syncs two states, then its ... 1answer 25 views ### Avoid Storing Keys in Key-Value Store by Replacing the Key with 128-bit Murmur3 Hash I want to develop LRU key-value data store and in that wanted to get rid of space to store the key itself. Instead wanted to store a 128 bit murmur hash. The structure of data-store that I want to ... 0answers 17 views ### Euclidean space vs metric space in density clustering algorithms I'm trying to find out if these algorithm still work if i replace the Euclidean space with metric space defined on the input point set. But i'm having some trouble figuring it out for some of them. I ... 0answers 26 views ### How far would complexity hierarchies collapse if$L\in CoNP$is$L\in NPH$? Let$L\in CoNP$. Assuming that$L\in NPH$, what would we get? So, as$L\in NPH$then every language$A\in NP$has a reduction$A \leq L$. This would mean that$\overline{L} \leq L$as well. By ... 0answers 34 views ### Find the median in a full min-heap with at most$\left \lfloor \frac{n}{2} \right \rfloor$comparisons I'm thinking to do this recursively using the fact the the left subheap is also a min-heap with its root being the minimum using some variation of Select$\left \lfloor \frac{n}{2} \right \rfloor$. ... 1answer 17 views ### Is there a way to find the correct element in the array for the given index x? In quick sort, in each iteration we are able to find correct index for an element (i.e. pivot element). Is there any algorithm to find correct element for a given index ? Here, correct index of an ... 0answers 22 views ### Given$n$sets of matrices, find$n$matrices that have the least number of LCDs among their entries Let's say I have$n$sets of matrices$$A = \left\{\begin{pmatrix} 2 & 4 & 17\\ 5 & 6 & 9\\ \end{pmatrix} \begin{pmatrix} 2 & 4 & 18\\ 5 & 6 & 9\\ \end{pmatrix} \right\... 0answers 7 views ### Learning algorithms- difference between a learner (the algorithm) having continuous access to the samples (oracle) vs getting all at start Is there any fundamental difference between learning algorithms e.g. variants of PAC which have continuous access to examples on which to train (i.e. these are obtained as the algorithm runs, when ... 1answer 33 views ### Decide if the edges of a mixed graph can be directed in order to be an Eulerian Graph I'm very stuck with this problem. Given$G = (V, E, A)$a mixed graph where every edge in$E$is directed and every edge in$A$is undirected. Thinking as a max-flow problem, decide if it's possible ... 1answer 52 views ### Ray tracing tree Let's suppose that we have a light source. Which of the following are correct for the tree of recursive ray-tracing (ray tree) that create when we make the colors for each pixel in the screen. Which ... 1answer 23 views ### Number of unique values in array in$\theta(n)$average expected time My idea is to initialize a hash table (with chaining) with$n$cells, having load factor$\alpha = 1$hence having$\theta(1)\$ expected number of values in each cell in the hash table, then go cell by ...

15 30 50 per page