All Questions
47,702
questions
0
votes
0
answers
22
views
Manhattan distance always less node expansion than misplaced tiles heuristic?
I created a 8-puzzle search solver using BFS, A* with manhattan distance, and A* with misplaced tiles.
I generated data that said that for a particular random board, misplaced tiles did less node ...
0
votes
0
answers
27
views
Showing for decidable language that is in $P/poly$ but not in $P$ (follow-up)
I've been trying to wrap my head around the proof provided in this answer.
I understand that $P$ is a class where languages can be decided by a Turing Machine and that $P/poly$ is a bigger class that ...
- 11
0
votes
1
answer
52
views
Optimizing Delivery Routes in a Graph-Based Network to Minimize Maximum Delivery Time
In a graph with N nodes, where each node represents a house and is labeled from 0 to N-1, an ...
- 135
0
votes
0
answers
36
views
Recover key from repeating-xor encryption
Let's say that we have a set consisting of many strings encrypted with the same key by a xor cypher, moreover they are the same length as the key, both the key and the original strings might contain ...
- 31
1
vote
1
answer
56
views
Show if $f(n)$ has polynomial growth and $g(n)=\Theta(f(n))$, then $g(n)$ also has polynomial growth
As stated in the question title, if $f(n)$ has polynomial growth and $g(n)=\Theta(f(n))$, then how can we show $g(n)$ also has polynomial growth?
$g(n)=\Theta(f(n))$ gives us $0\leq c_1f(n)\leq g(n)\...
- 151
1
vote
1
answer
18
views
Valid rules in CSG
In the book of Hopcroft-Ullman (the 1979 edition) there is a rule $Da\rightarrow aaD$ in the example of the CSL language $a^{2^i}$.
Valid rules in CSG have the form $\alpha A \beta\rightarrow \alpha\...
1
vote
1
answer
30
views
Showing SAT is auto-reducible
I am trying to wrap my head around the concepts of auto-reducibility and having access to an Oracle.
The way I understand is that a language is auto-reducible iff there is a Turing Machine $M^{L}(x)=1$...
- 11
-1
votes
0
answers
32
views
Is it possible to compute the differentiation of any differentiable function on an interval?
It seems not because of the existence of irrational numbers in any interval, irrational numbers that have an infinite number of decimal digits that a computer is not able to manage?
- 9
1
vote
1
answer
37
views
Subset sum reducible to barter economy problem?
I was given the following problem called the barter economy problem: Given a set of $n$ people $\{p_1, \ldots, p_n\}$ and a set of $m$ distinct objects $\{a_1, \ldots, a_m\}$, where each object $a_j$ ...
0
votes
0
answers
25
views
Concurrent datastructure modification
Given sets A, B, C with a parent-child (one to many) relationship between ...
- 101
0
votes
1
answer
34
views
Absolute difference between largest IEEE754 number and its predecesor
In simple precision format, the largest possible positive number is
$A = 0 ~~~ 11111110 ~~~ 111\ldots 111$
Its predecessor is
$B = 0 ~~~ 11111110 ~~~ 111 \ldots 110$
But what is the absolute ...
- 181
0
votes
0
answers
26
views
Is the optical disk drive an input device?
I have read online and seen websites saying the optical disk drive is a storage device. In my opinion, the optical disk drive only writes data to the optical disk so it's not a storage device, am I ...
0
votes
1
answer
37
views
Solving Recurrence Relations with induction
We got the following tasks in our Higher Algorithm class, to repeat our proof techniques from class:
Find asymptotic upper bounds (as sharp as possible) for $T(n)$ in each of the following cases,
...
0
votes
2
answers
69
views
How to find prefixes and suffixes for infinite languages? (Automata)
L= {abc}
prefix = {epsilon,a,ab,abc}
suffix = {epsilon,c,bc,abc}
It's easy to find suffixes and prefixes for finite Regular languages. But what will be the ...
-4
votes
1
answer
60
views
True or false? Any finite problem is in P
Please explain to me if this is true or false. I had this in an exam, and I really need to know if I got this correct. I believe it is true because finite problems have finite solutions, which can be ...
15
votes
4
answers
2k
views
Is there a known polynomial time complexity problem with bad constants?
As you know, big O notation hides all constants. For instance, both runtimes $T_1=n$ and $T_2=10^{10}n$ are considered to be linear ($\mathcal{O(n)}$).
Is there an iconic problem whose best known ...
1
vote
1
answer
52
views
If the Navier-Stokes equations problem is a computable problem, for example a set/language called "L", what are the elements of L?
First, can the Navier-Stokes problem be a formal computable one? like a P problem? Then, how to define the corresponding language? Would it only be the set of equations, or something else? Then, could ...
- 9
0
votes
0
answers
33
views
What are some visual representations of the lambda calculus?
I'm building some teaching tools for teaching the lambda calculus and would like some kind of visual representation of it. I've looked at Alligator Eggs and while it is something very similar to what ...
0
votes
1
answer
34
views
How are pointers modeled on bit-based computer models?
Why bit-based computer models?
The perhaps most commonly used computer model is a random access machine that can store natural (or even real) numbers in infinitely many cells indexed by natural ...
- 103
0
votes
0
answers
12
views
Collaborative Multi Agent Path planning on directional and non-planar graph
I am trying to implement a multi-agent path planning algorithm that works on non-planar graphs and large agents (that is, collisions may at the intersection of two edges and at points where the edges ...
0
votes
1
answer
58
views
$k$-way number contiguous partitioning
Given a set $S$ of $n$ positive integers $S=\{a_1,\ldots,a_n\}$, can we partition $S$ into $k$ subsets of equal sum such that each subset has contiguous elements from $S$?
Here, a contiguous subset is ...
- 97
2
votes
1
answer
89
views
Optimal torch placement in voxel games
Problem definition
The world consists of an infinite three-dimensional cartesian grid, i.e. every position is in $P = \mathbb{Z}^3$.
Neighbours of a position $p \in P$ are defined by $N(p) = \{p + e_1,...
- 63
0
votes
0
answers
54
views
Similar problem to Knight's tour
You have board size and one Knight but what is different is that when you move it you have to duplicate the knight and the 2 duplicates have to be in valid position from the knight
This gets repeated ...
1
vote
1
answer
39
views
Expected maximum matching size in a random bipartite graphs
What is the expected maximum matching size of a bipartite graph $(A\cup B, V)$ where $\lvert A\rvert = n$ and $\lvert B\rvert = n$ and the probability of a edge existing between $A$ and $B$ is a fixed ...
- 25
0
votes
1
answer
34
views
Find a substring length $k$ with maximum occurrences
Given a string length $S$, find a substring length $k$ that has the most occurrences in the given string.
We want $O(S)$ time complexity in an average case.
I think the solution lies in sophisticated ...
- 21
0
votes
0
answers
20
views
Are ASM and TLA+ somehow related?
I learned about abstract state macines recently, and on first sight they seem somehow reminiscent to TLA formalism. For example both:
Are used to research possible state sequence and prove safety/...
- 101
1
vote
1
answer
35
views
Complexity of simulations in simulations
This video of a group, who simulated (a very simple version of) Minecraft inside Minecraft itself got me thinking about the performance of such setups.
Another example to what I'm referring to, would ...
-4
votes
1
answer
26
views
Which one is an LL(2) but not an LL(1)
I'm pretty sure b and d are ll2 and not one but not 100% sure.
(a) S → aaScc | aaBbc | aaBbb | aBb | ac | Ʌ
B → aBb | Ʌ
(b) S → aaScc | aaBbc | aBb | ac | Ʌ
B → aBb | Ʌ
(c) S → aaScc | aaBbc | B | ac |...
- 1
0
votes
2
answers
49
views
Is there a model for the given logical formula, and if not, why?
I'm trying to determine whether there exists a model for the following logical formula: $(p_1 \to (p_2 \lor p_3)) \land(p_2 \to \neg p_3) \land ((p_1 \lor p_3) \to \neg p_2)$. Here's my understanding ...
- 3
0
votes
0
answers
66
views
Is the following a correct proof for the interval covering problem?
I have written the following greedy stays ahead proof for the problem of covering an interval with subintervals. Is it correct? I think it is, but this is my first time proving a greedy algorithm.
...
- 1
0
votes
0
answers
31
views
recursively enumerable and linear bounded automaton
I have a question about linear bounded automaton. Is it false that every recursively enumerable language is recognized by a LBA ?
Because LBA has limited tape size so not all recursively enumerable ...
2
votes
0
answers
29
views
Easy proof of IP ⊆ PSPACE for private coins
There is an extremely standard proof that IP⊆PSPACE, used for instance here, here, or here, by the argument that the full protocol is max-avg game tree that can be evaluated in polynomial space. It's ...
- 923
0
votes
2
answers
96
views
( Soft question ) P vs NP - is such a situation possible?
Currently P vs NP is the holy grail of theoretical computer science. And the nature of the problem is as such that if actually P = NP is proved then most of the proofs for mathematical statements ...
0
votes
0
answers
19
views
JPS-like path finding algorithm that keeps a distance from the obstacles?
I am using the JPS algorithm to find the shortest path from start $S$ to goal $G$ on a binary grid where each cell can be eithe 0 (free) or 1 (obstacle). Now, I would like my algorithm to take into ...
- 101
0
votes
1
answer
33
views
Counting the expected number of CPU cycles for n-number of assembly instructions
I was trying to count the cpu_cycles from an ARM processor 4 core Cortex A78 to be exact) using the PMU registers. Now, at the beginning, I read the cpu cycles counter register, then for test just run ...
0
votes
1
answer
33
views
Roles of 80386 MMU Paging Unit and similarity with modern CPU MMU
While searching for the structure of the MMU, I found the image below (80386 Internal Architecture).
I have three questions.
Q1. I'd like to know the roles of 'Adder', 'Page Cache', and 'Control and ...
- 3
0
votes
0
answers
22
views
If we have two TMs D1 and D2 and the languages of the TMs L(D1) != L(D2), then is this problem decidable/recognizable? [duplicate]
We know that in the case where, L(D1) = L(D2), the problem is undecidable. But what happens when the languages are not equal?
I would assume it's still undecidable, but is it recognizable? And how ...
2
votes
1
answer
51
views
Comparison of different algorithms for summing floating point numbers
I am exploring several approaches to summing floating point values, such as:
Naive summation, for comparison
Summing sorted values
summing with numpy, again for comparison
Kahan's algorithm
Pairwise ...
- 153
0
votes
0
answers
19
views
Amdahl's law to determine the overall speed increase using the optimizations
There is an old CPU running a program in which memory operations
currently take 30% of its execution time. Scientists find that adding a cache memory
speeds up 80% of memory operations by a factor of ...
- 1
0
votes
1
answer
29
views
Time complexity of search algorithms?
Can we prove that classical search algorithms cannot do better than a binary search algorithm with complexity $O(log(n))$ ?
If so, how do we prove it?
- 101
-1
votes
1
answer
59
views
random problem- the three elevator problem
there are three elevators in a building that has twelve floors. find an algorithm that needs to find the the best possible way for the elevators to stop at any particular floor considering the traffic ...
2
votes
1
answer
55
views
Dinitz’ algorithm in simple unit-capacity networks
I am studying for an algorithm design course, and can't understand this demonstration about how Dinitz’ algorithm computes a maximum flow in $O(m \sqrt{n})$ time.
This is what is written on the slides ...
0
votes
0
answers
24
views
Optimizing an Algorithm for Timestamp-Aware Partitioning of Data
My Problem
I'm currently dealing with an algorithmic problem that involves two input lists:
A list of natural numbers $[A_1, A_2, \dots, A_n]$ with $A_1, \dots, A_n \in \mathbb{N}$.
A list of triples ...
1
vote
0
answers
26
views
Is there any reference materials on complexity analysis for lazy languages?
Is there any books, papers or articles on how to analyze the time complexity of programs written in lazy languages such as Haskell?
I know how laziness is implemented and how it can be expanded and ...
0
votes
1
answer
24
views
Can a trie or DAWG loop?
I am looking at DAWGs, which are compressed tries, like this:
It is an acyclic graph though, and I'm wondering if you are allowed to create loops or cycles in such a data structure.
For example, I am ...
- 2,163
1
vote
1
answer
39
views
Proving lower bound by proving not little o
I have been reading these distributed computing notes. In some of the proofs, for proving lower bound of $\Omega(f(n))$, we prove that no algorithm which solves the problem in $o(f(n))$ exists.
I can'...
- 11
1
vote
0
answers
16
views
Given a group of people with timings for 2 events, find the shortest total time for X and Y given that events are mutually exclusive
Your classmates elected you to be in charge of the creation of the short and long distance running teams for the upcoming Sports Day event in your school. They have kindly given you their timings for ...
- 11
0
votes
1
answer
57
views
solve $T(n)=2T(\dfrac{n}{2})+\dfrac{8}{9}T(\dfrac{3n}{4})+\Theta(\dfrac{n^2}{\log{n}})$ using Akra-Bazzi method
Assume we have this recurrence:
$$T(n)=2T(\dfrac{n}{2})+\dfrac{8}{9}T(\dfrac{3n}{4})+\Theta(\dfrac{n^2}{\log{n}})$$
We want to solve it using Akra-Bazzi method. As we know, $\sum_{i=1}^k\dfrac{a_i}{...
- 151
1
vote
1
answer
37
views
Is the class of star-free languages just the complement to counter languages within the regular language class?
So I'm kind of confused as I'm not that deep into the algebraic theory of languages.
The wikipedia article states:
Another way to state Schützenberger's theorem is that star-free languages and ...
- 67
0
votes
1
answer
37
views
Is the class NP closed under complement? (Follow-up)
As a follow up to this question already been asked here, I was wondering - if we supposed that P != NP, would then the following reasoning be correct:
In NP problems we can only verify in poly-time ...
- 11