All Questions
47,744
questions
2
votes
0
answers
17
views
Windowed LogLog/HyperLogLog algorithm to get a count of the cardinality of the set of the last $k$ elements?
LogLog/HyperLogLog provides a great way for estimating the cardinality of the set of $n$ objects. At its simplest, you hash all $n$ objects into binary strings, find the largest number of leading 0's $...
- 532
-3
votes
2
answers
54
views
Contradiction via pumping lemma
So this is the language that I need to prove is irregular via pumping lemma, however I am completely stuck with this and seeking some advice. The other ones I have done during my tutorial are much ...
user164540
0
votes
2
answers
28
views
Time complexity of algorithm involving function calls
Me again.
This time I have a more general question.
Suppose I have the following code snippet:
...
- 167
0
votes
0
answers
12
views
Better implementations for this dynamic program to solve optimization problem?
In the code below, I describe a problem and provide a backtracking implementation in Python that solves it:
...
- 181
1
vote
1
answer
64
views
If NP $\subset$ BPP, then NP $\subset$ RP. Confusion about the correctness of Probabilistic Turing Machine
I found the proof of this theorem from https://www.csie.ntu.edu.tw/~lyuu/complexity/2011/20120103s.pdf.
Here is the screenshot of the construction of probabilistic Turing machine RP. (https://i.stack....
- 31
1
vote
1
answer
44
views
Time complexity of algorithm with three loops and if statement
Suppose I have this c++ code:
...
- 167
0
votes
0
answers
16
views
Optimize clothing in RPG considering set bonuses
In role playing games, switching equipment for better is a common procedure. My question is to find an algorithm that can optimize linear combination of stats the equipped gear gives - this is exactly ...
- 1
-1
votes
1
answer
93
views
Create DFA such that every substring of w of length 3 contains two or three 0's with w={0,1}
I am attempting to draw the DFA of this problem but I'm kind of stuck. In another post I saw that the DFA should have 10 states. I'm finding it hard to even understand the question, is the input to ...
0
votes
1
answer
19
views
Why is $DSPACE(\log^2n)\subseteq DTIME(n^{\log n})$?
I am having trouble with the statement that $DSPACE(\log^2n)\subseteq DTIME(n^{\log n})$ holds which is given without argument in the paper The structure and complexity of minimal NFA's over a unary ...
- 11
0
votes
1
answer
25
views
Fully Connected Graph to Lattice
I am looking for algorithms (or at least something similar to the problem definition):
Given a fully-connected weighted graph $G$ with $n$ nodes, find a subset $S$ of edges that form a square lattice ...
- 113
1
vote
0
answers
85
views
Can we compute most significant digit of a binary number in O(1) on RAM model?
Consider we use a RAM model with word length w (or if you really want a more exact model, you can use Knuth's MMIX instructions with w-bit numbers).
Given a number n, we want to compute the most ...
- 22.2k
1
vote
2
answers
46
views
In the simulation of a C-program by a Turing machine, how does a TM determine which instruction to execute?
In Arora-Barak, the authors mention a way how TMs can compute everything that can be computed by computers. The idea is that every high-level language program has an equivalent machine language ...
- 11
0
votes
1
answer
20
views
What are the non-overlapping properties of a function?
Specifically, properties that identify preconditions over which a function can be used without resulting in undefined behavior or data races.
For example, I am familiar with 3 important properties:
...
- 101
1
vote
1
answer
29
views
Independent sets generation in a graph
Is there an algorithm that, given an undirected graph and one independent set IS1, finds an other independent set IS2 by adding and deleting vertices from the first IS1?
- 11
-1
votes
1
answer
35
views
Choose elements from sets that form a permutation: NP hard?
Let $n$ be a positive integer and $[n] := \{1,2,3,...,n\}$. You are given $k$ non-empty subsets of $[n]$. Decide whether it is possible to select exactly one element from each subset such that the ...
- 121
0
votes
1
answer
33
views
Pseudopolynomials and $NP$ problems like $CLIQUE$
Having encountered the concept of "pseudopolynomials", my understanding is that we have to be careful when the input to a problem is a number, that the complexity of the solution should be ...
1
vote
0
answers
16
views
Number of DCFG parse tree nodes with respect to input length
I read the question and answer at Number of nodes of a parse tree when the Grammar is in CNF?, and I'm curious about a related matter: obviously with a unrestrained LR grammar (as opposed to CNF) the ...
- 111
0
votes
1
answer
44
views
How to find optimum number of cpu cores for a workload
Following bar graph shows maximum percentage cpu utilization of F16sv2 (16vcpu &32GB) azure virtual machine in last 30 days. Only sometimes CPU usage goes more than 60 percentage.
How to find the ...
- 1
0
votes
0
answers
32
views
1 way 2 stack and 2 way 2 stack Pushdown Accepters that accepts L={a^(n^2)|n≥1}
Using a 1 way 2 stack, and a 2 way 2 stack PDA, I want to check if the length of a an input string is strictly a perfect square number. How can I do this in both approaches?
1
vote
1
answer
30
views
How to find the free memory addresses in RAM?
I am currently trying to build a simple computer in Minecraft (8-bit data, 6-bit addresses, no paging or segmentation), with redstone, where I can make run simple programs written similarly to code in ...
- 13
-2
votes
0
answers
37
views
L = {xy : x, y ∈ {a, b} ∗ , |x| = |y| and x ̸= y^R} where y^R is the reverse of y
How can I convert this context free langauge to conext free grammar? Please help I can not solve this problem for days.
L = {xy : x, y ∈ {a, b} ∗ , |x| = |y| and x ̸= y^R} where y^R is the reverse of ...
-4
votes
0
answers
39
views
How do I convert this context free language to context free grammar L1 = {0^i 1^j : i ̸= j, j ̸= 2i} [duplicate]
How do I convert this cfl to cfg L1 = {0^i 1^j : i ̸= j, j ̸= 2i}
1
vote
1
answer
23
views
Algorithm for constructing a numbering reflecting the order of activities
I'm following a book about graphs and they introduce a concept called 'activity network'. In an activity network, each vertex represents an activity in a project (like building a house for example) ...
- 219
2
votes
2
answers
38
views
Is loading from L2 or L3 of multi level cache direct or require a transfer to L1
(This is mainly about reads, and commercial products not hypothetical machines.) When loading a CPU register with data contained in L2 or L3 of a multi-level cache. Can the data that is in L2 or L3 ...
- 135
0
votes
0
answers
19
views
Knapsack with weight swaps
I have a problem that is 0/1 knapsack, but you are also able to swap the weight of 2 items up to k times. I came up with a O(nkc) solution, but I am looking for a faster o(n*c) solution. I think the ...
0
votes
1
answer
15
views
Algorithm question - check if there exists a path that touches A nodes exactly once and can revisit all other nodes
I am having trouble with a problem where I am given an adjacency list and a list of the nodes that must be visited exactly once to connect two nodes. What is the most efficient way of doing this? This ...
-2
votes
0
answers
32
views
Boolean formula in CNF whose conjugtion is NOT satisfiable
Give an example of a Boolean formula which is in CNF form and satisfiable and whose negation is NOT satisfiable.
0
votes
3
answers
60
views
Transitioning from mathematics to computer science
I'm a mathematics undergraduate interested in theoretical computer science, machine learning, and neuroscience. I wish to pursue graduate studies in computer science but I fear I might not be able to ...
-3
votes
1
answer
54
views
artificial intelligence [closed]
how to solve this puzzle in A* algorithm with the Manhattan distance
heuristic
- 1
0
votes
0
answers
16
views
How to check for correct order in a fill-in-the-blanks exercise
Suppose the following fill-in-the-blanks exercise:
___ ___ and ___ ___ went to the ___.
Suppose the correct solution here is "John Smith and Mike Jones went to the pub". In other words: <...
- 1
0
votes
1
answer
16
views
Graph Algorithms (SSSP vs MST)
I am currently facing a question "Can a graph with a unique MST product a different spanning graph using Dijkstra vs using Prim's algorithm?" The answer is false and I am struggling to ...
1
vote
2
answers
366
views
Does there exist an context free language L such that L∩L^R is not context free?
By the closure property of context-free languages, if $L$ is context-free, then $L^R$ (the reverse of $L$) is also context-free, but $L\cap L^R$ might be non-context-free. I tried to come up with an ...
- 11
0
votes
0
answers
55
views
What is the earliest compiler in chain that was used to create what we nowadays have as a modern C compiler?
My apologies if the title is confusing. First I begin with the statement that may be wrong but what I always thought what happened.
"Dennis Ritchie created C compiler which was used to create ...
-4
votes
0
answers
36
views
Maximum possible coincidences? Python code please [closed]
Given $M = [0,4,8,15]$ as points on a real line place 2 points $C_1$, $C_2$ on the line according to the following conditions
Both $C_1$ and $C_2$ cannot be placed at 0 or 15.
Distance between $C_1$ ...
0
votes
0
answers
14
views
Showing TIME(n) is not closed under poly-time reduction
I am trying to wrap my head around the following proof
Choose some language A $\in$ $TIME(n^3)$ \ $TIME(n)$ (the existence of such a language is guaranteer by the hierarchy theorem)
Let B = {1}
Note ...
- 11
0
votes
0
answers
14
views
Memory ordering and RMW instruction definitions
The typical definition of an RMW instruction with e.g. sequential consistency is an instruction where no memory operation can happen between the load and the store in the global memory order.
Is there ...
- 111
-1
votes
0
answers
58
views
Can we give an example Context-Free Language that a DPDA can not recognize [duplicate]
Can we give an example Context-Free Language that a DPDA can not recognize. If we DPDA can not recognize can you explain why?
- 1
0
votes
0
answers
17
views
Runtime of randomization algorithm to find majority element in an array?
This is for the leetcode problem 169. Majority Element. Given an array of numbers, where there is a guarantee that there is a number that exists in the array greater than floor(n/2), one can find such ...
- 111
0
votes
1
answer
24
views
Can Dijkstra's algorithm be used this way?
Let us say that I wanted to solve a Hamiltonian path problem by treating it as a Hamiltonian cycle(on a weighted graph). I use a TSP solver, and implement a dummy node of edge weight zero, whose ...
2
votes
2
answers
51
views
Derivation trees to show a given grammar is ambiguous
Given the grammar with productions:
\begin{align}
S \rightarrow aSb \mid SS \mid \lambda\\
\end{align}
I would like to show that it is ambiguous. As I understand it, if you can show that some string ...
- 21
0
votes
1
answer
19
views
Process Synchronization and Atomic Instructions
According to the book " Operating Systems Concepts ", ninth edition , page 210, we have the following statement :
Many modern computer systems therefore provide special hardware
...
- 195
1
vote
0
answers
16
views
epsilon-optimality in cycle-cancelling for min cost flow
I'm learning about the (min-mean) cycle-cancelling alg for min-cost flow in Ahuja, Magnanti, and Orlan's Network Flows book (Chapters 9 and 10). When talking about the alg, they prove this fact ...
- 21
0
votes
0
answers
19
views
Would this subtyping relation contradict disjointness?
This is a basic question, but suppose I have two disjoint universes $\mathcal A $ and $\mathcal B$, and some fixed types $A:\mathcal A, B:\mathcal B$. Would it contradict anything if I postulate that $...
- 101
0
votes
0
answers
33
views
An Example of the Conjuction of Two NP-Complete Decision Problems Being Polynomial Time Solvable [duplicate]
Firstly, we define A and B as two decision problems with the same set of inputs.
Define a new decision problem "A AND B" as follows: The input to "A AND B" is any valid input x for ...
- 1
0
votes
0
answers
23
views
Can a problem be NP-complete and also be in complexity class FTP/XP?
P is a NPC problem. Could it be in complexity class XP/FPT or how is the relation to each other?
- 1
-2
votes
0
answers
33
views
Prove vertex limit for cluster editing kernel
A graph G is a cluster graph if every connected component of G is a clique. In the Cluster Editing problem, we are given as input a graph G and an integer k, and the objective is to check whether one ...
0
votes
1
answer
48
views
How to modify Dijkstra's algorithm to model the path of an electric car?
I know that Dijkstra's algorithm is used to find the shortest path between nodes in a weighted graph. And I know that this can be used to model road networks.
Somebody online asked (but nobody ...
0
votes
1
answer
29
views
Proof that $\{0^m 1^n : 0\le m\le n^2\}$ is not a CFL
I am trying to prove by the pumping lemma that $L=\{0^m1^n:0\le m\le n^2\}$ is not a CFL. Here is what I have so far.
Suppose for contradiction that it is a CFL and let $N$ be the pumping length. ...
- 315
0
votes
0
answers
12
views
Algorithm to find the number of N length sticks needed to cut into an array of various sized lengths (all <= N)
Given a length N (e.g. 20) and an array of lengths which are all <= N (e.g. [15, 1, 6]) I'd like an algorithm that finds the minimum number of N lengths necessary to be cut into the array of ...
0
votes
1
answer
21
views
Enumerating proper intersections
Let
$U \subset \mathbb{N}$ be a finite universe set;
$B$ be a set of nonempty subsets of $U$ such that $B$ covers all elements in $U$, i.e. $\bigcup_{b \in B} b = U$, and if $b \in B$ then $b \...
