All Questions

Filter by
Sorted by
Tagged with
0
votes
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 ...
-4
votes
0answers
17 views

How to make genes look like computer machine language?

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

Poping a symbol on a PDA when Input and Stack are Irrelevant

Say I had a PDA with alphabet language {0,1}, and a stack language {P,Q,\$}. In the PDA I don't really care what the inputs are at the end and I just want to clear the stack back down to the special ...
-1
votes
0answers
11 views

Connected component- feature regions extraction

I'm trying to extract the connected component from a graph, in the following way: ...
2
votes
1answer
22 views

How does software prefetching work with in order processors?

From prof. Onut Mutlu's slides on prefetching, this example has been shown as software prefetching: ...
0
votes
1answer
35 views

Counting strongly connected components in a directed graph in $NL$

Define $K\_SCC = \{ \langle G, k \rangle \,:\, G \text{ has at least $k$ strongly connected components} \}$ I want to show that $K\_SCC \in NSPACE(\log n)$, using that $st-CONN$ and $\overline{st-CONN}...
2
votes
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 ...
0
votes
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, ...
0
votes
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 ...
1
vote
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 ...
-4
votes
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-...
3
votes
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 ...
0
votes
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 ...
2
votes
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 ...
-1
votes
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....
3
votes
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 ...
3
votes
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 ...
0
votes
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 ...
4
votes
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, ...
2
votes
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 ...
0
votes
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 ...
1
vote
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?
0
votes
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 ...
0
votes
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 ...
2
votes
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://...
0
votes
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 ...
2
votes
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 ...
0
votes
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 ...
2
votes
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 ...
2
votes
1answer
17 views

non-existence of sentence that captured specific property

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)...
0
votes
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$ ...
2
votes
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 ...
1
vote
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 ...
0
votes
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 ...
2
votes
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 ...
1
vote
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$. ...
1
vote
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 ...
0
votes
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\...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
1
vote
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
1
2 3 4 5
821