All Questions

Filter by
Sorted by
Tagged with
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 ...
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] ...
-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, ...
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

matplotlib.widget.Slider displays but isn't active when plt.show() is called outside function that created the slider. Am I missing something?

...
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 ...
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 ...
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. ...
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 ...
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 ...
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? ...
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 ...
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 "...
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 ...
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 ...
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 ...
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. ...
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 ...

15 30 50 per page