All Questions

Filter by
Sorted by
Tagged with
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 $...
chausies's user avatar
  • 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 ...
user avatar
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: ...
john doe's user avatar
  • 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: ...
lafinur's user avatar
  • 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....
ltl's user avatar
  • 31
1 vote
1 answer
44 views

Time complexity of algorithm with three loops and if statement

Suppose I have this c++ code: ...
john doe's user avatar
  • 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 ...
Ferazhu's user avatar
-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 ...
Jellyfish's user avatar
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 ...
Yannik Eik's user avatar
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 ...
EnderNicky's user avatar
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 ...
Kaveh's user avatar
  • 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 ...
Burt Macklin's user avatar
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: ...
Jorge Leitao's user avatar
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?
maliya's user avatar
  • 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 ...
Muses_China's user avatar
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 ...
CuriosityScream's user avatar
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 ...
Petr Skocik's user avatar
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 ...
Amal's user avatar
  • 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?
user164486's user avatar
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 ...
hello there's user avatar
-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 ...
user164478's user avatar
-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}
user164478's user avatar
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) ...
Max's user avatar
  • 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 ...
Max Power's user avatar
  • 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 ...
Nathan Dai's user avatar
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 ...
Maceo Cardinale Kwik's user avatar
-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.
Anthony Shuey's user avatar
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 ...
Abdulrahman's user avatar
-3 votes
1 answer
54 views

artificial intelligence [closed]

how to solve this puzzle in A* algorithm with the Manhattan distance heuristic
shar's user avatar
  • 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: <...
Jakub's user avatar
  • 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 ...
pehperclip's user avatar
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 ...
Miki's user avatar
  • 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 ...
Clear Sky's user avatar
-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$ ...
Vamsi Krishna Kunapareddy's user avatar
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 ...
Meki21's user avatar
  • 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 ...
eof's user avatar
  • 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?
slm cmm's user avatar
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 ...
Shisui's user avatar
  • 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 ...
Johnny Upman's user avatar
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 ...
cpf9231's user avatar
  • 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 ...
John adams's user avatar
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 ...
AWhite's user avatar
  • 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 $...
user125234's user avatar
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 ...
Oluchi A's user avatar
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?
Philipp's user avatar
-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 ...
Mos Craciun's user avatar
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 ...
Johnny Upman's user avatar
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. ...
Addem's user avatar
  • 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 ...
ajHurliman's user avatar
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 \...
Matheus Diógenes Andrade's user avatar

15 30 50 per page