# All Questions

41,026 questions
Filter by
Sorted by
Tagged with
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 ...
17 views

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

How to make genes look like computer machine language? 更多相关中文内容
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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 ...
18 views

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 ...
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, ...
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 ...
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 ...
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-...
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 ...
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 ...
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 ...
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....
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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
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?
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 ...
21 views

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 ...
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://...
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 ...
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 ...
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 ...