All Questions
45,969
questions
1
vote
0
answers
32
views
Tabular Meta-Learning in RL
There are various meta-learning algorithms in RL that are proposed for settings when we have a (deep) neural network and the policy (or the value function) are parameterized as such.
Can these methods ...
- 175
0
votes
0
answers
10
views
Build javascript object with default values [closed]
I want to build a function let objectBuild = (arg_1, ..., arg_n) => {// Instructions} with fixed key list [key_1, ..., key_n] ...
- 123
-2
votes
0
answers
27
views
Permutation sort algo
You have to sort a permutation of a sequence into the original sequence using reinsertion.
What type of algorithm could be used to minimize number of moves (reinsertions)?
E.g.
Transform $[4, 3, 1, 5, ...
- 1
0
votes
0
answers
21
views
How to think about blank symbol when Turing Machine used as a function?
Turing Machines can be used to compute functions.
For example f(x)=x-1.
0011 is on the tape. Turing Machine computes for some ...
- 299
0
votes
2
answers
34
views
Every DFA accepting a finite language must contain a dead state?
I came a across a question where there were some statements made on Finite Automata, DFA and their states.
One such statements in the question was that a "Every DFA accepting a finite language ...
- 115
1
vote
0
answers
29
views
Is Miller-Rabin not a suitable algortihm for the RSA key generation or am I missing something?
I'm trying to recreate the RSA key generator, from what I understood you must create two prime numbers of 256 bytes long, p and q...
- 11
-1
votes
1
answer
13
views
0
votes
0
answers
18
views
Succinct array datastracture
Is it true that there is no known succinct data structure that has integer array (vector) functionality? Desirable operations would be:
append O(1)
access(i) - returns i-th item O(1)
iterate(i..j) - ...
- 141
0
votes
0
answers
10
views
is co-NSPACE(n^2) a strict subset of DSPACE(n^5)?
Is $co-NSPACE(n^2) \subsetneq DSPACE(n^5)?$
From Savitch theorem $co-NSPACE(n^2) \subset DSPACE(n^4) \implies co-NSPACE(n^2) \subset DSPACE(n^5) $
and as $ PSPACE = NPSPACE$ we can go further to $ ...
1
vote
0
answers
20
views
Proving a maximal bottleneck for all pairs of vertices in maximal spanning tree
Suppose we have an undirected graph $G=(V,E)$ and and it's Maximal spanning tree $T=(V,F)$ such that the edges in $F$ is the heaviest subset of edges $E$ from which you can create a spanning tree.
We'...
- 293
1
vote
1
answer
43
views
Turing Machine, UNLIMITED number of steps left or right on the tape?
In the Church-Turing thesis Wiki page, there are a set of descriptions of the "behavior of a computor—`a human computing agent who proceeds mechanically'". I am content with all of them, ...
- 604
0
votes
1
answer
41
views
Confused on Bellman Ford
We have a graph where we want to get from node u to v in the shortest path possible.
I understand how Bellman-Ford works when we have exactly i edges to go from u to v or at most i edges to get from u ...
1
vote
1
answer
37
views
How does "+" operator fit into the formal grammar of $\lambda$-calculus?
In Wikipedia I found out that the formal grammar of $\lambda$-calculus is the following:
...
- 111
0
votes
0
answers
48
views
Maximizing total value of coins collected
Suppose we have $m$ bags of coins. There are $n$ possible denominations of coins, i.e a coin can be of value $v_1,...,v_n$. Now each bag contains some coins and also two different bags may contain ...
- 11
0
votes
1
answer
42
views
Algorithm for determining an algebraic positivity property of a multivariate polynomial
I am considering multivariate polynomials with integer coefficients that can be expressed as sums of products of terms of the form $y_i-z_j$ for positive integers $i$ and $j$. I am trying to find an ...
- 103
0
votes
1
answer
15
views
In Kolmogorov's $ K(s) \leq |s| + c $, why is $c$ +ve?
Kolmogorov said "It seems natural to call a chain random if it cannot be written down in a more condensed form, i.e., if the shortest program for generating it is as long as the chain itself. &...
- 1,592
0
votes
0
answers
22
views
What the algorith should return and how to implement
I was studying algorithms, and that problem below came up.
Write an efficient algorith that calculates the biggest single positive forward change in value given the values.
There is a second image ...
- 1
2
votes
1
answer
103
views
Min-cut with maximal number of edges
I’ve searched for a solution for this problem for some time now, it is out of an algorithm question sheet.
We know that in order to find the minimal amount of edges in a flow graph’s min-cut we need ...
- 293
1
vote
0
answers
14
views
Why use Welford's Method over a more naive approach?
I came across this pair of blog posts explaining the problem with calculating variance on floating point data:
https://jvns.ca/blog/2023/01/13/examples-of-floating-point-problems/#example-3-a-variance-...
- 111
1
vote
1
answer
16
views
union of NP and co-NP, closure under polynomial time reduction
Is $Union = NP\cup co-NP$ closed under polynomial-time many-one reductions?
I understand that in order to be so, for $A\in Union, A \leq_P B $ there should exist a polynomial time computable function $...
0
votes
1
answer
64
views
Probability of comparison of two nodes after insertion in AVL tree
Suppose $K=a_1<a_2<\dots<a_n$ be a set $n$ distinct keys that inserted into an AVL tree $T$. The probability of any permutation of the order of insertion of the sequence $K$ is equal. Also we ...
- 1,480
0
votes
0
answers
27
views
The computational complexity of a variant of algorithm for the TSP (Travelling Salesman Problem)
What is the algorithm's computational complexity for a variant of the Travelling Salesman Problem, where every node must be visited at least once, meaning that a node can be visited more than once? (...
3
votes
2
answers
90
views
Data structure to estimate the frequency of low frequency elements
I have a file with trillions of numbers and I want to get all numbers that have a frequency <=100. These numbers are in text format (...
- 131
0
votes
1
answer
24
views
Amount of ways N can be written as sum of two or more non-repeating integers
For example, 5 can be written in 2 ways:
4 + 1
3 + 2
8 can be written in 5 ways:
7+1
6+2
5+3
5+2+1
4+3+1
How could this be determined for any positive integer N?
1
vote
1
answer
43
views
Ordered open-end knapsack problem optimised for minimum weight range
Given a fixed number of infinite-capacity containers and a list of items of varying weights, how can I best place the items into the containers preserving their original order in a way that minimises ...
- 111
1
vote
0
answers
44
views
Bin packing with more than one parameter
Usually, in bin-packing, we have objects of sizes $a_1,...a_n$, and each bin has size 1, We need to minimize the number of bins, and for this, there are best fit/first-fit approximation algorithms.
...
- 11
0
votes
0
answers
67
views
Iterate through all values of a certain subset of all permutations
Let's say we've got $n$ numbers to multiply together. But the multiplication operation, like in computer floating-point arithmetics, is not associative. Thus the order of multiplication matters.
...
- 83
1
vote
1
answer
33
views
Understanding the Strong Exponential Time Hypothesis
Let $n$ be the number of variables in the input formula and $m$ the number of clauses. Define $s_k = \inf\{\delta : k\text{-SAT can be solved in } 2^{\delta n} \text{ time}\}$. The strong exponential ...
- 15
0
votes
1
answer
34
views
What are common heuristic algorithms of self-organizing list?
So in my "Advanced algorithms" course, we were taught about the "self-organizing list" data structure. The professor showed the following three heuristic algorithms: Frequency ...
- 231
0
votes
0
answers
24
views
How does the regular expression '^(a+)+$' lead to this specific NFA?
OWAPS has an article on ReDoS (archived).
In it, they use the regular expression ^(a+)+$ as an example for ReDoS vulnerabilities.
They provide this illustration of ...
- 101
0
votes
2
answers
44
views
How to find tangent line on a curve of unknown function?
I have x and y values to plot the curve and I need to find a tangent line of slope 1 that intersects the curve and the point at which it intersects. I was trying to do polynomial and exponential ...
-2
votes
0
answers
22
views
Prove there is a way to partition vertices of a simple graph into two groups so that degree of each vertex will be even in it's group induced subgraph
One of our groups can be empty Hint : we should use induction Question designer also suggested to choose one vertex first then supplement its neighbourhoods induced subgraph and then delete selected ...
0
votes
0
answers
34
views
What should be the order of eliminating empty rules and unit rules when converting context free grammar to chomsky normal form?
Let's say that we have a context free grammar G, which is not in chomsky normal form, and we need to convert it to chomsky normal form.
The steps involved in the conversion are as follows:
Add a new ...
- 305
0
votes
0
answers
26
views
Equivalence for Turing Machines is not Recognizable - Reduction DOUBT
I have a big doubt on this video about $EQ_{TM}$, especially on minute 5:11.
Why is he saying that to reduce $ A_{TM}\lt_{m}\overline{EQ_{TM}} $ we need to create a machine M that rejects every input?
...
- 3
1
vote
1
answer
50
views
Optimality of A* algorithm
In the book Artificial Intelligence a Modern Approach 4th edition, the author claims that the A* algorithm is cost-optimal if the heuristic function is ...
- 111
0
votes
1
answer
51
views
Why these languages are closed under union or concatenation?
This is a question in my text book that I cannot understand the solution provided for that:
In each case below, give a simple descreption of the smallest set of languages that contains all the "...
- 11
0
votes
1
answer
24
views
When applying pumping lemma for regular languages to prove that a given language is non regular, do we show that pumping fails for all $i$ or one $i$?
Pumping Lemma for Regular Languages
Pumping Lemma for Regular Languages: If $A$ is a regular language, then there is a number $p$ ( the pumping length ) where if $s$ is any string in $A$ of length ...
- 305
0
votes
1
answer
36
views
Is a problem in NP if it runs in P time on a NDTM, verifiable in P on a DTM, but solution doesn’t halt on a DTM?
Say there was a decision problem which was solved optimally in polynomial time on a non-deterministic Turing machine, and verifiable in polynomial time on a deterministic TM, but would not halt when ...
1
vote
3
answers
72
views
Decide whether a flow graph has a single min-cut
The problem is whether a graph (which we represent as a flow network) has a single min-cut, or there could be multiple min cuts with the same maximum flow value, I've yet to encounter a well explained ...
- 293
0
votes
0
answers
33
views
Constraint satisfaction problems in Natural language processing
I have just started learning about CSP and NLP, for which I have to write a review paper of some research articles.
The problem is that when a searched for research articles on some trusted digital ...
- 1
0
votes
2
answers
37
views
Decidability of the minimum number of states a Turing Machine needs to accept a language
I'm reading some old notes from a course on Turing Machines and I've bumped into the following question:
Is the following language decidable? The language formed by the set of all Turing Machines ...
- 163
0
votes
0
answers
15
views
What is the algorithm for finding the shortest cycles made by the robot? [closed]
Consider a weighted directed graph, including $V$ vertices and $E$ edges. A robot will make some shortest cycles (unknown to us), namely $c_j$, in this graph as follows.
The cycle must start and end ...
0
votes
0
answers
17
views
Ambiguous type of "triangle" operator for sum types
In Meijer, Fokkinga and Patersons "Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire" the ∇ operator for sum types is introduced which removes the tags from its ...
- 26
0
votes
1
answer
18
views
Do Left regular grammar describe a language containing the reverse of the strings described by the right regular grammar for another language?
Let's say that we have a regular language $L_1$ that is described by a right regular grammar. Now, assume we have a left regular grammar, can we describe the same language $L_1$ or would the left ...
- 305
1
vote
1
answer
23
views
Reducing BB to SMR and vice versa
It's often said that State Machine Replication and Byzantine broadcast are equivalent (e.g., the abstract of [1]), but it seems only obvious how to reduce SMR to BB. I.e., give BB one can construct an ...
- 181
0
votes
0
answers
26
views
Bit model vs RAM model confusion
I've been struggling with this analysis of algorithms notion for a few hours now in an introductory course. Let us define a function $N(n)$ for positive integer $n$ as the number of times performing $...
0
votes
0
answers
27
views
In DFA, can a state be changed after the accepted state?
If I have the input string as 00 for this diagram, will I ever go to q3 or once I reach to q2, that state would be accepted so no matter the input string, once the state is accepted, will I never be ...
0
votes
1
answer
39
views
Time complexity of $\mathsf{NP}$ problem under assumption of $\mathsf{P} \neq \mathsf{NP}$
A simple question, but I can't find an answer in quite the form I'm looking for:
Assume $\mathsf{P} \neq \mathsf{NP}$, and thus $\mathsf{P} \subsetneq \mathsf{NP}$. If we have $L \in \mathsf{NP}$ and $...
- 3
-3
votes
2
answers
145
views
How can we analyze the procedure Product: multiply two n-bits binary numbers x and y?
I am trying to analyze the algorithm Product: multiply two n-bits binary numbers x and y.
...
- 101
1
vote
1
answer
60
views
Another Game Theory Problem
We have an array of integers of length N(even). A and B play a game where A selects a number followed by B without replacement until the array becomes empty(Both A and B select N/2 elements each). The ...
- 25