All Questions
48,503
questions
0
votes
0
answers
2
views
Minimum number of vertices in a tree with pathwidth $h$?
Let $\mathcal{T}_h$ be the set of trees with pathwidth $h$. What is the minimum,$|V(T)|$ over all $T \in \mathcal{T}_h$.
I'm guessing this is a fairly easy question. We know that a complete binary ...
0
votes
0
answers
2
views
Regex for $L = \{ w \mid w \in \Sigma^* \text{ and each substring } u \text{ of } w \text{ where } |u| = 4 \text{ contains the character } 0 \}$
The question asks to write a regex to the following language $L$ above $\Sigma = \left \{0,1 \right \}$.
$L = \{ w \mid w \in \Sigma^* \text{ and each substring } u \text{ of } w \text{ where } |u| = ...
- 33
0
votes
0
answers
3
views
Algorithm to "reverse" search/match pairs from results
Sorry, I don't know how to title it clearly.
There is a game, where players can send their units to attack another player's units (weeell, there is a lot of games like that). Each unit has some value. ...
- 1
0
votes
1
answer
12
views
NFA for a regular expression without $\epsilon$-transitions
I think I know how to convert a regular expression to NFA without requiring epsilon transitions, but I'm not sure if I'm right (I'm just using common sense to be honest, no particular algorithm in my ...
- 101
0
votes
0
answers
18
views
how to 3d render with only drawing pixels
I have been trying to find ways to display a 3d scene on a screen (specifically 480x240px Vex robotics brain). The only ways that I can draw to the screen is with drawing individual pixels or with ...
0
votes
0
answers
11
views
Calculating sequence of $\lambda$ returns
I am having some trouble with answering the following question:
A rat is involved in an experiment. It experiences one episode. At the first step it hears a bell. At the second step it sees a light. ...
- 1
-1
votes
0
answers
14
views
Given my restriction is deciding, if a set $B$ with duplicates exists that sums up to a set $A$ of distinct whole numbers NP-complete? [closed]
Given a set $A$ $=$ {$2,3,...$}, is there an arbitrary set $B$ constructed with an arbitrary number of duplicate elements from $A$, where $\sum_{x \in A} x \neq \sum_{y \in B} y$ ?
In other words ...
- 319
4
votes
2
answers
191
views
How to represent BFS and DFS between adjacency matrix and list?
I'm trying to figure out how to best represent BFS (Breadth First Search) and DFS (Depth First Search) on a graph, specifically between being represented as an adjacency matrix and an adjacency list. ...
- 43
-1
votes
0
answers
11
views
How are max flow problems solved when there is an additional constraint?
This is the question:
Smart Car is expanding, and now has a subsidiary named Smart
Airlines which is experimenting with self-flying plane. Smart Airlines wants
to schedule flights on their ...
0
votes
1
answer
19
views
Is there a delay between two commands to read data from RAM?
Everyone knows that the speed of the CPU is many times faster than the speed of RAM, whereas in this case the processor executes two read or write commands in memory running in a row? As I assume, due ...
- 11
0
votes
0
answers
27
views
Merge two sorted arrays and find median in O(n+m) using divide and conquer
I have two sorted arrays and I have to return the median of both in O(n+m) for an exercice my teacher gave, using divide and conquer.
I did the code below, which works, but is on ...
0
votes
0
answers
9
views
Shortest path in a graph where edge weights can vary dynamically based on the path taken [duplicate]
I have a directed acyclic graph whith negative edges where edge weights can vary dynamically based on the path taken.
...
- 101
1
vote
1
answer
25
views
Size of circuit generating the solutions of a SAT problem
We have a satisfiable CNF formula $F$ which maps $\{0,1\}^n \to \{0,1\}$.
Let us call $S\in \{0,1\}^n$ the set of inputs that satisfy $F$, i.e. $F(s)=1 \, \forall s\in S$.
There is a circuit $C$ with $...
- 145
0
votes
0
answers
32
views
Eliminating left recursive nonterminals without adding $\epsilon$-productions
I have been reading the book "Compiler Construction" written by William M. Waite and Gerhard Goos. I found a statement in the chapter "5.3.2. Top-Down Analysis and LL(k) Grammars" ...
- 111
2
votes
1
answer
43
views
DFS (Depth-first search) vs BFS (Breadth-first search) Space Optimizations
Problem
I am currently digging deep into some optimizations on the classical iterative approaches to both DFS and BFS algorithms. The material I'm currently using at my University presents both ...
- 123
1
vote
1
answer
36
views
Byte addressing and alignment
With byte addressing, the CPU can access a single byte. But how does this access happen during alignment? As I understand it, if a CPU needs to read an unaligned byte, it reads the word starting from ...
- 11
0
votes
1
answer
33
views
Complexity of algorithm waiting $e^{n}$ seconds
A dumb question in complexity theory.
Let's consider an algorithm that solves the following problem:
is $e^{n}$ time passed?
...
- 1
2
votes
0
answers
41
views
Can remainder mod 2 be efficiently computed from addition and equality?
Suppose I have a programming language all of whose variables have natural number type. (So I cannot form higher-type objects, e.g., lists or trees, of natural numbers.) The only atomic commands I am ...
- 121
0
votes
0
answers
8
views
Finding a common variable value among all SAT solutions
Let $F$ be a boolean formula on $n$ variables $x_1, \cdots, x_n$. $\textbf{SAT}(F)$ asks whether there exists an assignment of truth values to variables under which $F$ is true. I'm curious about ...
0
votes
1
answer
27
views
Show that $PLANAR \in co-NP \cap NP$
The fact that the language of planar graphs is in $co-NP$ is easy to show because the complexity of finding a Kuratowski subgraph is $O(|V|)$. But what about $NP$? Any help is appreciated.
0
votes
1
answer
36
views
If $P=NP$, then $LCP \in P$
I want to prove that if we assume $P=NP$, then we can find the longest cycle (maximal number of vertices, no repeated edges, only repeated vertex is the starting one) in an undirected graph in ...
1
vote
0
answers
28
views
Understanding Variable Quantification in Toda's Theorem Part 1
In my attempt to understand the intricacies of Toda's Theorem, I am focusing on the first part of the proof, which establishes a randomized reduction from quantified Boolean formulas (which represent ...
- 11
0
votes
0
answers
29
views
Variant of Generalized-Geography problem
Consider the "Generalized Geography" game: on directed graph G with selected start vertex, players take turns moving along edges, without ever going back to previously visited vertices. ...
- 43
1
vote
1
answer
17
views
Algorithm for creating an esports season schedule
I run an esports league for my Boys & Girls Club and others that want to participate. I'm trying to find a way to take information about when different teams are available to compete and use that ...
- 11
0
votes
1
answer
30
views
If a language L over a finite alphabet A has both a subset and superset that are Turing-recognizable, does this make L Turing-Recognizable too?
"Let A be a finite alphabet, and let L1 and L2 be two Turing-recognisable languages over A such that L1 is a proper subset of L2, i.e. L1 ⊂ L2 but L1 ≠ L2. Let a language L over the alphabet A ...
- 1
0
votes
2
answers
25
views
Greedy solution for minimum weight where all tasks are allocated
I'm trying to solve exercise 13 from Chapter 04 of Algorithms Design (Eva Tardos) books. The problem is the following:
The way I solved: was to have a greedy solution, where I always choose, for an i,...
0
votes
1
answer
18
views
Intuition for Using Greedy Approach in Container with Most Water Problem
Link to leetcode problem: https://leetcode.com/problems/container-with-most-water/?envType=study-plan-v2&envId=top-interview-150
if we consider this solution:
https://leetcode.com/problems/...
3
votes
0
answers
32
views
"Small" formulas for boolean functions
Theorem 10 in the following document:
https://sites.math.rutgers.edu/~sk1233/courses/topics-S13/lec1.pdf
states that every boolean function $f:\{0, 1\}^n\rightarrow \{0, 1\}$ has formula complexity $O(...
- 131
-3
votes
2
answers
37
views
Parse Tree simple example
Consider the grammar G:
S ➝ A | B
A ➝ aB | b | c
B ➝ bA | a | ε
Which of the following strings has two parse trees according to G?
ba
bb
ab
none of the choice
aa
...
- 97
0
votes
0
answers
27
views
Prove P/poly = BPP/poly
To prove the equivalence, we have to show that P/poly $\subseteq$ BPP/poly and BPP/poly $\subseteq$ P/poly thus P/poly = BPP/poly.
Since BPP $\subseteq$ P/poly. My thinking is, we can also add poly to ...
- 11
0
votes
1
answer
26
views
Are there known super-exponential problems?
Can you point a particular problem, all algorithms solving which are of a super-exponential time-complexity?
I know that super-exponential problems exist, but is this a theorem of existence, or can a ...
- 433
0
votes
0
answers
20
views
Is super-exponential complexity useful in practice?
Exponential time-complexity has a useful application in "practical" CS: NP-problems, NP-complete problems. Knowledge about this obviously helps in everyday programming.
Can you give an ...
- 433
0
votes
1
answer
20
views
Conway's Game of Life to expand QR code
If you use a QR code as a seed for Conway's Game of Life, and have information for
A) How many steps you should run it for, and
B) The size of the new square (where to put the border after you are ...
0
votes
1
answer
34
views
Context Free Grammar: How to infer FIRST()
We are given the grammar rules
$A \to F B E$
$B\to A C$
These rules are only some of the rules of a larger grammar $G$, but we are not given the remaining rules of $G$. We are told that $A$ is ...
- 97
0
votes
0
answers
24
views
In what sense do universes solve the problem of not having type $\Pi_{A:\text{Type}}B(A)$?
One motivation for introducing universes, as I see it, is that without universes, we cannot construct types like $\Pi_{A:\text{Type}}B(A)$ because they would require us to have $\Gamma.\text{Type}\...
- 111
1
vote
1
answer
38
views
Why is naive primality test not polynomial, while graph traversal is?
I am reading Sipser's Introduction to the Theory of Computation, and have trouble understanding the difference between polynomial and non-polynomial problems. When describing a PATH problem, where
...
- 11
1
vote
0
answers
40
views
Tree node indexing
I'd appreciate any solutions, ideas, or pointers to relevant literature.
I'm attempting to design a system with nodes (representing the state of some tasks) organised in a tree structure. I'd like to ...
- 11
1
vote
0
answers
31
views
Dependent Types in $\lambda P$ vs MLTT
I am trying to understand the difference between $\lambda P$ and MLT, in particular the dependent type features.
What is the difference between dependent types in $\lambda P$ and dependent types in ...
- 131
0
votes
0
answers
7
views
Why modified PC algorithm (searching for Bayesian structure) "in practice only considers a small subset of separating sets"?
I'll state how the text I'm reading describes PC algorithm.
This algorithm [9] starts with a fully connected graph and, on the
basis of pairwise independence tests, it iteratively removes all the
...
0
votes
0
answers
22
views
Methods to tell the length of data?
What methods are there for telling a computer how long a set of data is? Here are the methods I know of:
Directly telling the computer where the data begins and ends, most often with {} or ().
Having ...
user169480
-1
votes
0
answers
24
views
How to verify the correctness of a voxel based algorithm?
Currently, I have implemented an algorithm for voxelization of triangular meshes. How can I test if this algorithm can correctly convert triangular meshes to voxels? My current idea is to create a ...
0
votes
1
answer
23
views
Set partitions and integer partitions
Consider an algorithm that takes the input a finite set $X$ and an integer partition $\sum_{i=1}^k n_i=|X|$ and gives output all the set partitions $\left(S_1,\ldots, S_k\right)$ of $S$ satisfying $|...
- 101
0
votes
1
answer
44
views
A context-sensite grammar for the language of sequences of two different types of parentheses with possible intersections?
Consider the language $L$ over the alphabet (,[,),]
such that any word $w \in L$ if formed as a shuffle of two (possible empty) well-formed sequence of parenthesis: one over (,) and another over [,].
...
- 103
1
vote
1
answer
38
views
Adding type constructors to universes
Suppse we have a Tarski-style universe $U$, which means, in particular, that the following rules are declared: $$\frac{}{\Gamma \vdash U \text{ type}} \quad \frac{\Gamma \vdash a:U}{\Gamma \vdash \...
- 111
-1
votes
0
answers
19
views
P with oracle to P is equal to P
How we can prove that P = P with P oracle
Can we use this claim: if we have O in P then P with O oracle is in P
and the proof for this claim is the following Allowing an oracle can only help compute ...
0
votes
0
answers
16
views
Kernelization For Odd Cycle Transversal Problem on Perfect Graphs
This problem appears as exercise 2.33 in https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf (page 48). A perfect graph $G$ is bipartite if and only if it contains no triangle graphs. ...
- 101
0
votes
0
answers
11
views
Relation between running time of Insertion sort and number of inversions
What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer.
Consider Insertion sort
...
- 1
-4
votes
0
answers
52
views
Proof that strong AI exists?
If turing machines are capable of simulating physics, then they should be able to simulate a human brain. Isn't that enough to prove the existence of strong AI?
- 153
0
votes
0
answers
13
views
Is this Deterministic Unranked Root-To-Leaf Binary Tree Automata?
I believe I have a definition of deterministic root-to-leaf tree automata in the unranked binary case, and would like to check that I have this definition correct. I would also appreciate any sources ...
- 101
-2
votes
1
answer
32
views
Closed form solution of T(n) = 5T(n−1) + n^2, to T(1) = 7
How to find the closed form solution of this equation?
T(n) = 5T(n−1) + n^2, to T(1) = 7
