Newest Questions

0 votes

0 answers

20 views

Consider a min-heap that is constructed by the keys $\{1,2,3,...,n\}$ where $n=2^{k}-1$ for some $k>1$ not necessarily in the same order. Then I first showed that $j$-th minimum element cannot ...

1 vote

0 answers

17 views

I would like to solve the equation $Ax=b$ where $A$ is an $N\times N$ "cyclic" banded matrix (there might be a better term, but I wasn't able to find it), i.e. a matrix that look like $$\...

2 votes

0 answers

37 views

I have a long array of size $n>10^6,ドル call it $X$. I would like to find all ranges $[a, b)$ satisfying the following conditions $\sum_{i=a}^{b-1}X[i] \leq 0,ドル $b-a \geq K,ドル $\sum_{i=a-1}^{b-1} X[i]...

1 vote

0 answers

34 views

The degree of an $n$-variate polynomial is defined as the maximum degree of the monomials that composes it. Now, given a polynomial $P$ (or rather, a list of monomials, since the coefficients don't ...

2 votes

1 answer

105 views

I'm trying to understand how to interpret the turnstile notation Γ ⊢ A when it appears in natural deduction systems, and I'm confused about the relationship between natural deduction and sequent ...

-1 votes

0 answers

27 views

https://cses.fi/problemset/task/3401 or https://vjudge.net/problem/CSES-3401 please help me to solve it, you can told me the solution or the link to the tutorial. you can also send your opinion to my ...

0 votes

0 answers

14 views

In Arora and Barak's book "Computational Complexity: A Modern Approach" (see draft pdf here https://theory.cs.princeton.edu/complexity/book.pdf), the $\mathtt{PATH}$ problem is given as the ...

-2 votes

0 answers

12 views

I need to create 3 primary partitions, 1 extended which will contain 2 logical partitions. I see that I have to give PartitionNumber as 0 for the extended partition and then PartitionNumber 4 and 5 ...

0 votes

0 answers

34 views

The idea is to combine these two principles together. If we use zero-address instructions in a CPU, this implies having a stack memory. However, the idea of Von Neumann architecture is to store both ...

1 vote

0 answers

17 views

I went through Def 2.1 of this paper, where the approximation version of max-LINSAT is defined as follows. Let $\mathbb{F}_p$ be a finite field. Input: For each $i=1,\cdots,m,ドル let $F_i\subset \...

0 votes

0 answers

20 views

I was working on some conceptual parts about the Turing Machine and streaming algorithm, and got a bit stuck. Below is the statement I am trying to prove. "If L has a streaming algorithm, then L is ...

0 votes

0 answers

23 views

For the language L over the alphabet {0,1} that accepts strings ending in 11, 101, or 110, perform the following steps: State the regular expression defining L. Draw the transition diagram for an NFA ...

1 vote

0 answers

18 views

The COSET WEIGHTS problem is given as follows paper1. Input: A binary matrix $A\in \mathbb{F}_2^{m\times n},ドル a binary vector $y \in \mathbb{F}_2^{m},ドル and a non-negative integer $w\in \mathbb{Z}^{+}$....

0 votes

1 answer

47 views

Recall that a language $A$ is in NP iff it is of the form $$A = \{x \in \Sigma^* : (\exists w\in\Sigma^*)\ (x, w) \in R_A\},$$ for some relation $R_A$ such that membership of $(x, w)\in R_A$ can be ...

0 votes

1 answer

49 views

Let's say we have a term (eg an integer, but interested in symbolic polynomial as well) $t$ that can be factored as $t=p^k \cdot m$. Note: $p$ need not be necessarily prime or otherwise irreducible ...