All Questions

Filter by
Sorted by
Tagged with
0 votes
0 answers
6 views

Collapsing loops in a control-flow graph

Let's say we are given some CFG, maybe in SSA-form, and we want to "collapse" each top-level loop into s single node, whose successors would be all exit blocks of the original loop. So we ...
return true's user avatar
0 votes
0 answers
17 views

Data compression - does a complete code is a prefix free code

In the subject of data compression and I have this question: Is every complete code has to be a prefix free code? I don't think so, but I'm having a hard time finding a counterexample for disprove it.
Jack's user avatar
  • 1
1 vote
1 answer
15 views

Constrained Maximum Flow Minimum Cost

Let $G=(V, E)$ be a directed network with a set $V$ of vertices and a set $E$ of edges. Two vertices are distinguished, $s,t$ which are the source and sink respectively. Each edge $(i, j)$ has an ...
Daniel García's user avatar
1 vote
1 answer
11 views

Can you identify this assignment problem and efficient solutions or estimates?

Problem Statement My wife's business runs a summer camp for 68 students. The students are divided into cabins: 27 students in 3 groups of 7 and one group of 6 belong in one set of 4 cabins; 41 ...
D. Ben Knoble's user avatar
4 votes
1 answer
129 views

Size of the certificate as a property of the problem

Suppose I have a decision problem $\mathcal{L}\subseteq\Sigma^*$ and a verifier $V$ that recognizes $\mathcal{L}$, i.e. $L(V)=\mathcal{L}$. Let's arbitrarily choose some certificate $c(w)$ for $w \in \...
Yuumita's user avatar
  • 153
0 votes
1 answer
36 views

Why finding the largest element in a min-heap using a comparison-based algorithm takes Ω(logn) time?

How we can prove that the largest element in a min-heap using a comparison-based algorithm takes Ω(logn) time? Is this useful that worst running time for comparison based sorting is >= longest path ...
Aleksandra Nowińska's user avatar
3 votes
1 answer
62 views

Why $2n−1$ comparisons are sometimes necessary to correctly merge two sorted sequences [duplicate]

How we can prove that $2n−1$ comparisons are sometimes necessary to correctly merge two sorted sequences of $n$ elements each into one sorted sequence? I tried to prove it with binary decision tree, ...
Aleksandra Nowińska's user avatar
0 votes
2 answers
37 views

why didn't ASCII/utf-8 used 00000000 to represent char 0 or rather any other character

I mean why value of 0 value in binary is not used by ascii encoding , it would have been used to represent char 0 or anything else why they used it to represent NULL
Shubham Atkal's user avatar
2 votes
0 answers
18 views

Issue understanding how control signals are pipelined in a RISC architecture

I'm currently implementing a RISC prozessor in a HDL and realized that I seem to have a somewhat incorrect understanding of how pipeling works for control signals. Here's my general understanding: ...
Micronuno's user avatar
0 votes
1 answer
20 views

Find a negative cycle linearly?

In a directed graph, if you find scc (strongly connected components), then for each negative edge, if its 2 vertices are in the same scc and that scc has size > 1, then there is a negative cycle ...
Lorenzo Tinfena's user avatar
0 votes
1 answer
14 views

The Atlas system word addresses

I'm reading about the Atlas operating system and I came across this: The Atlas system used a British computer with 48-bit words. Addresses were 24 bits but were encoded in decimal, which allowed 1 ...
beginwithc's user avatar
-2 votes
0 answers
13 views

Find the asymptotic execution time of the program in explicit form if for known recurrence relation: 𝑇(𝑛) = 𝑂(1), 𝑛=0; 𝑎𝑇(𝑛−1)+𝑂(𝑛),𝑛≥1,𝑎>1

Find the asymptotic execution time of the program in explicit form if for known recurrence relation: 𝑇(𝑛) = 𝑂(1), 𝑛=0; 𝑎𝑇(𝑛−1)+𝑂(𝑛),𝑛≥1,𝑎>1
Богдан Карпа's user avatar
0 votes
0 answers
26 views

Are they talking about virtual memory in this article?

I am reading this Wikipedia article: https://en.wikipedia.org/wiki/Memory_segmentation And I am in this paragraph: Segmentation with paging Instead of a memory location, the segment information ...
user394334's user avatar
0 votes
1 answer
36 views

Is my understanding of Eta reduction correct?

In my script I have the following term: x => y => both (x) (y) This is reduced to both My interpretation is that this function (the whole term) takes two arguments and returns a function and ...
Rubus's user avatar
  • 123
0 votes
1 answer
19 views

Is $O(n^{f(n)})$ superexponential if $f(n)$ is a polynomial function such that $f(n) > n$ as $n$ approaches $\infty$?

I know that exponential time complexity is $ O(k^n) $, where $k$ is some constant and $n$ is the input size, and that subexponential time is anything slower than that, $o(k^n)$ . If we define ...
Karlo Vizec's user avatar
0 votes
2 answers
62 views

regular expression for $\{w\in \{a,b\}^*\mid |w|_a \mod 2 = 0\}\setminus \Sigma^*aab\Sigma^*$

The question asks to write down a regular expression $r$ indicating the language of all the words above $\Sigma = \{a, b\}$ , in which the number of $a$ is even and there is no sub-word $aab$ in them. ...
Daniel's user avatar
  • 23
0 votes
0 answers
40 views

PDA equivalent to an $\varepsilon$-free PDA

Say that a PDA is $\varepsilon$-free if it contains no $\varepsilon$ transitions (that is to say, $\varepsilon$ is not in the recognized string symbols even if it still is a stack symbol), but it may ...
Addem's user avatar
  • 335
0 votes
1 answer
20 views

Model checking algorithms

Given a knowledge base and a proposition alpha we can check if our knowledge base entails alpha using a model checking algorithm that functions as such : we generate a set of all the possible models ,...
red wood's user avatar
0 votes
1 answer
17 views

Table driven parser vs Recursive Descent parser

I am currently writing an LL(1) parser. At several places (Engineering a Compiler book, Dragon book, or this discussion), I have seen two ways to go about this, either with a table driven parser (...
Ali Ahmed's user avatar
2 votes
3 answers
1k views

Find 1s in almost all 0 array using comparisons only

So, we are given a 100 long array, with 97 0s and 3 1s of which we do not know the locations. We must find them using only a compare function, which I managed to write (in Python): ...
user555076's user avatar
1 vote
2 answers
23 views

Is $L = \{ \langle G,k\rangle \mid G $ has a simple cycle at length $k \}$ in P or in NP

$ L = \{ <G,k> |\ G \ has \ a \ simple \ cycle \ at \ length \ k \} $ I think this language is in NP but my friend thinks this language is in P. NP proof: if a graph has a simple cycle of a ...
maya cohen's user avatar
0 votes
1 answer
19 views

Convert ternary constraint into set of binary

I have the following ternary constraint that needs to be converted into a set of binary constraints in order to be used for a constraints solving problem: ...
Stackbot124's user avatar
0 votes
0 answers
18 views

The language made from the context free Language (CFL) is also a CFL? [duplicate]

Let $\Sigma$ be the set {a,b} of letters. For a language $L\subset\Sigma^{*}$ over $\Sigma$, we define $\Gamma(L)$ as follows; $\Gamma(L)=\{v\in\Sigma^{*}|\exists w\in \Sigma^{*}.(|v|=|w|\wedge vw\in ...
Tigerion's user avatar
0 votes
0 answers
25 views

Is this version of SAT NP-Complete?

Given a SAT instance such that: Each clause is of length at most 4. Negative literal occurs only in clauses of length=2. Each length 2 clause has at most 1 negative literal. Is this version of SAT ...
TheoryQuest1's user avatar
0 votes
0 answers
19 views

Want to plot rectangles given their width,height and the cartesian origin (0,0)

The info I am given : block_ID, block_width, block_height as well as how the cuts between the rectangles are(horizontal or vertical); for example two rectangles can be joined by a horizontal cut or a ...
fat_gladiator17's user avatar
0 votes
0 answers
14 views

Textbooks to study machine learning as a TCS/FM/symbolic AI researcher

I work in the fields of theoretical CS, formal verification, and symbolic AI. Here's my DBLP link to have a picture of my background: DBLP Can you suggest me resources (good graduate-level textbooks) ...
Nicola Gigante's user avatar
3 votes
0 answers
20 views

Finding a set of edges $E$ such that every $s$-$t$-path contains at least 2 edges from $E$

Given an undirected graph $G$ and two vertices $s$ and $t$, i want to find a set of edges $E$ in $G$ such that every (simple) $s$-$t$-path contains at least 2 edges from $E$. Is this problem solvable ...
tgnome's user avatar
  • 81
2 votes
1 answer
18 views

Is limiting the input type in subclasses legitimate (does it give a stronger or the same specification)?

Note: I have read a similar post, but my problem seems different from that. Read my attempts to understand the problem for why I believe they are different. My problem: I know that (see this and this) ...
Guanyuming He's user avatar
1 vote
0 answers
28 views

Choosing one element from each partition that minimize the difference between max and min

Given an unsorted array $A$ that contains $n$ elements of numbers. Also $A$ partitioned to $k$ lists $A_1,A_2,A_3,\dots,A_k$, each contains at most nearly $\frac{n}{k}$ elements. We choose exactly one ...
ErroR's user avatar
  • 1,894
2 votes
1 answer
45 views

How to solve the recurrence $ T(n) = 4T\left(\frac{n}{2}\right) + \frac{n}{\lg n} $ in terms of $\Theta$?

I'm attempting to solve the recurrence relation: $$ T(n) = 4T\left(\frac{n}{2}\right) + \frac{n}{\lg n} $$ in terms of its asymptotic behavior ($\Theta$), specifically using the first case of the ...
Ferran Gonzalez's user avatar
1 vote
2 answers
36 views

How to Solve the Recurrence Relation $T(n) = 8T\left(\frac{n - \sqrt{n}}{4}\right) + n^2$ in terms of $\Theta$?

The provided recurrence relation is as follows: $$ T(n) = 8T\left(\frac{n - \sqrt{n}}{4}\right) + n^2 $$ The goal is to express the solution in terms of the asymptotic notation $\Theta$. Unfortunately,...
Ferran Gonzalez's user avatar
0 votes
3 answers
49 views

How Many Times Would The Assembler Load and Store i

So, this is a snippet of a C code: for (i = 0; i < 20; i++) { a[i] = rand() & 0xFF; printf("a[%d]: %d\n", i, a[i]); } Now, imagine "i&...
River Uzoma's user avatar
2 votes
0 answers
45 views

Approximate the parity function in L1-norm

Consider the parity function $MOD_2(x) = x_1 \oplus \cdots \oplus x_n$ for $x \in \mathbb{F}_2^n$. I am concerned about the degree bounds for a real polynomial $f$ which approximates $MOD_2$ well in ...
TheGuy's user avatar
  • 21
1 vote
1 answer
48 views

Proof that nondeterministic TM runs in exponential time

Consider a nondeterministic TM $M$ that takes as input another TM $M'$, a string $x$ and integer $k$. $M$ decides if there exists a string y s.t. $|y| \leq |x|^2$ and $M'(x, y)$ accepts in $k$ steps. ...
wytubev's user avatar
  • 13
1 vote
2 answers
68 views

Resources on Moore and Mealy Machines

I was studying about Moore and Mealy machines but having hard time connecting with them because 1) they are different from typical normal machines.what is the need of "output" and 2) My text ...
hxdshell's user avatar
0 votes
0 answers
33 views

Show 3-colorable graph with hamiltonian cycle is NP-Complete

The language is : $3COLORHC = \{<G> | \text{ G is an undirected 3-colorable graph that contains Hamiltonian cycle} \}$ I was asked to show that this language is NP-Complete. Showing that the ...
Yarin's user avatar
  • 275
-4 votes
0 answers
67 views

Deciability of equivalence of two countably infinite sets where elements are pairs

Consider a set $A = \{\langle X, Y\rangle$ where $X, Y \in S\}$ and $S$ and $A$ are countably infinite sets. Consider another set $B = \{\langle P, Q\rangle, \text{where } P, Q \in R \} \text{ and } ...
kauray's user avatar
  • 511
0 votes
0 answers
18 views

Find maximum sum subgrid under constraint

Give a positive $m$ by $n$ matrix as input, choose a set of elements such that for any 2 by 2 submatrices, at most 2 elements are chosen. Return the maximum sum of chosen elements among all possible ...
vyjtkbyykyhuk's user avatar
2 votes
1 answer
31 views

Maximum of a tritonic array

I have found out how to find the maximum of a "bitonic" array. The problem is as follows. An array is bitonic if it is comprised of an increasing or decreasing sequence of integers followed ...
user716881's user avatar
0 votes
0 answers
11 views

How can I reduce the complexity of an inverse DFT where I have a uniform frequency series being evaluated at non-uniform target points?

I have implemented an N-dimensional Non-Uniform Discrete Fourier Transform (in this case it's specifically an inverse NUDFT) using PyTorch. My goal with this implementation is to have a function which ...
kairocks2002's user avatar
1 vote
1 answer
67 views

What is the role of diagonalization in the proof of undecidability of the halting problem?

I'm trying to understand the proof of undecidability of the halting problem. Some resources give a short proof based on a proof by contradiction. There is no mention of diagonalization. But some ...
Sanyo Mn's user avatar
  • 195
1 vote
1 answer
16 views

Best internal representation of a random variable to enable iterative sampling and interpolation/regression

Let $[0,100]$ denote the interval of real numbers between $0$ and $100$. Given a function $f:[0,100]^n \rightarrow \mathbb{R}^+$, I want to implement the following simple algorithm to search for the ...
EXPTIME-complete's user avatar
-3 votes
0 answers
36 views

Huffman and its enhancement technique called blocking

One enhancement for the Huffman coding algorithm is a technique known as blocking, in which blocks of size k input symbols are encoded simultaneously.Sketch a proof: For any set of input symbols and ...
user168526's user avatar
0 votes
1 answer
46 views

Can the MST's "cut property" be derived from the "cycle property" and vice versa?

The cut and cycle properties of the minimum spanning tree are well-known. It is easy to use similar arguments to prove them. But I wonder if one property be derived from the other. Cut property: ...
Tom Bennett's user avatar
4 votes
1 answer
151 views

Tseitin formula on 2-connected graph

How can we prove that for $\\\\$ every $\\\\$ 2-connected graph G with an odd number of vertices, the unsatisfiable Tseitin formula for it is minimally unsatisfiable, that is, if we remove even a ...
Brett's user avatar
  • 1
6 votes
0 answers
79 views

Problem of constructing binary sequence with least possible 1s under given constraint

You are given a binary pattern p. Problem is to construct a binary sequence of length n such that by sliding p over our sequence there is always at least one position where two 1s align (one in the ...
Relja Šegvić's user avatar
1 vote
1 answer
31 views

Knapsack Problem: Find Top-K Lower Profit Solutions

In the classic 0-1 knapsack problem, I am using the following (dynamic programming) algorithm to construct a "dp table": ...
slaw's user avatar
  • 111
0 votes
1 answer
70 views

Deciding if a language is CFL or in $P$

I'm trying to decide whether $L_c=${$w=uxu, | \ u,x\in \Sigma ^* \ and \ |u|=c $} for some constant $c\in \mathbb{N}$ is context free or not. initialliy, I've thought about choosing $x=\epsilon$ ...
Aishgadol's user avatar
  • 345
0 votes
1 answer
39 views

Correctness proof of bubble sort(bogus proof)

I am aware of bubble sort correctness proof. But what is wrong with following argument while using induction. Proof: Assume correctness of array size $1$ and $n$ (base and hypothesis). Then for ...
user146551's user avatar
0 votes
0 answers
36 views

Find every Hamiltonian path through a 4x4 matrix starting from a given X,Y?

As part of programming a game, I'm trying to generate all the paths through an NxN matrix that touch every cell once without revisiting any, starting from (0,0). Considering the matrix as a graph, ...
temporary_user_name's user avatar

15 30 50 per page
1
2 3 4 5
966