All Questions

Filter by
Sorted by
Tagged with
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 ...
Dennis Gahm's user avatar
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 ...
Meki21's user avatar
  • 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 ...
maplemaple's user avatar
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 ...
Sheeye's user avatar
  • 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)\...
Mason Rashford's user avatar
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\...
Ricardo Wehbe's user avatar
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$...
Meki21's user avatar
  • 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?
someone's user avatar
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$ ...
redbull_nowings's user avatar
0 votes
0 answers
25 views

Concurrent datastructure modification

Given sets A, B, C with a parent-child (one to many) relationship between ...
Aedoro's user avatar
  • 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 ...
lafinur's user avatar
  • 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 ...
Lucretius's user avatar
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, ...
petrit.vidishiqi's user avatar
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 ...
Vedant Khandelwal's user avatar
-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 ...
Anthony Shuey's user avatar
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 ...
Santiago Armstrong's user avatar
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 ...
someone's user avatar
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 ...
Hunter Livesay's user avatar
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 ...
KGM's user avatar
  • 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 ...
CubeArrow's user avatar
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 ...
zebda's user avatar
  • 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,...
user13062187's user avatar
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 ...
KnightsProblem's user avatar
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 ...
Anonymous's user avatar
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 ...
popcorn's user avatar
  • 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/...
uhbif19's user avatar
  • 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 ...
SmallestUncomputableNumber's user avatar
-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 |...
Jonah's user avatar
  • 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 ...
cozen's user avatar
  • 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. ...
windoid's user avatar
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 ...
MathJunior's user avatar
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 ...
Alex Meiburg's user avatar
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 ...
Aditya Mishra's user avatar
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 ...
firion's user avatar
  • 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 ...
Adeesh Lemonickous's user avatar
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 ...
W298's user avatar
  • 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 ...
Luis Ramirez's user avatar
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 ...
Olumide's user avatar
  • 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 ...
tanisha's user avatar
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?
NotaChoice's user avatar
-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 ...
chris pine's user avatar
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 ...
Placido Pellegriti's user avatar
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 ...
mathbreaker's user avatar
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 ...
Kagura Hitoha's user avatar
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 ...
Lance's user avatar
  • 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'...
ABBA's user avatar
  • 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 ...
Crash Bandit's user avatar
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}{...
Mason Rashford's user avatar
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 ...
Crea Teeth's user avatar
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 ...
Meki21's user avatar
  • 11

15 30 50 per page