All Questions

Filter by
Sorted by
Tagged with
0 votes
0 answers
10 views

How do you remember the algorithm for rotating a square matrix?

The algorithm for rotating a square matrix 90 degrees is neat, and it is documented here and here. However, it is difficult to remember, and requires one to look it up first in order to implement it. ...
ktm5124's user avatar
  • 173
0 votes
1 answer
11 views

Quickly converting a regex into a minimized DFA

Is there some sort of algorithmic way to quickly convert a regex into a minimized DFA? I am able to somehow "guess" the DFA by playing around with the regex (as shown in the image, where the ...
Librapulpfiction's user avatar
0 votes
1 answer
13 views

How to create a tree of height $lg(n)$ using Union-Find data structure

I'm wondering given a set $A$ of $n$ numbers, is there any procedure that can create a tree of height $lg(n)$ that contain all the elements of $A$ by applying consecutive Union by rank operation in a ...
Daniel's user avatar
  • 71
-1 votes
0 answers
8 views

Find, in linear time, a line that intersects all the segments and has the largest possible slope, or determine that there is no such line

I'm wondering how to approach this question. Let e1, . . ., en be n horizontal segments in the plane. Find, in linear time, a line that intersects all the segments and has the largest possible slope, ...
K. Stuhl's user avatar
0 votes
0 answers
19 views

Proof that $ALL_{DFA} \in SPACE(log^{2}n)$

we define $ALL_{DFA}$ as: $ALL_{DFA} = \{ <A> | \text{ A is a DFA and L(A) = }\Sigma ^ {*} \}$ I'm looking for a proof that $ALL_{DFA} \in SPACE(log^{2}n)$ I have noticed that $L(A) = \Sigma ^ {*...
shaggy's user avatar
  • 63
1 vote
0 answers
36 views

GOOD BORDERS is NP-complete?

Given a graph $G=(V,E)$ and a set of nodes $S$, the boundary of $S$, denoted as $f(S)$, is the set of arcs having an endpoint at $S$ and one in $V−S$. i.e., $f(S):=\{uv\mid uv\in E,u\in S,v\in V−S\}$....
JOhn stck's user avatar
0 votes
0 answers
11 views

How to maintain chat history context [closed]

I'm using ollama and llama3 to build a chatbot. However, right now it can't remember chat history. For example, if my first query is "tell me about the theory of relativity", and if my next ...
Mr.A's user avatar
  • 1
-1 votes
1 answer
12 views

ER model Many to Many relationship cannot be correct

I am working on this exercise In question c) it says that "a prescription clearly identifies the drug" so I assumed that the relationship "identifies" between drug and prescription ...
Root Groves's user avatar
0 votes
0 answers
25 views

Is there a category theory equivalent of pure type systems?

I have seen the correspondence between the simply-typed lambda calculus and Cartesian closed categories, and am curious about how this generalizes to other lambda calculi. I have seen some related ...
Chris Henson's user avatar
0 votes
0 answers
7 views

n-ary Entity-Relationship for Modified Chen notation

Given is this ER diagram, with the following information: A single actor may receive multiple awards for a specific, single movie. An actor receives such a single award for exactly one movie though. A ...
XaniXxable's user avatar
-1 votes
0 answers
16 views

Prove L = { $c^m$ $a^{2k}$ $b^{n+3}$ | m >= 8, n >= k >= 1} is not regular using pumping lemma

I have to prove that L = { $c^m$ $a^{2k}$ $b^{n+3}$ | m >= 8, n >= k >= 1} is not regular using the pumping lemma. I was thinking that I should take L1 = { $c^m$ $a^{2n}$ $b^{n+3}$ | m >= ...
sharp_pencil's user avatar
-2 votes
1 answer
33 views

$O(|V||E|)$ algorithm for finding all the cut vertices in a connected graph

Given a connected graph $G = (V, E)$, how to find all the cut vertices in $G$ in $O(|V||E|)$ time? I have considered some algorithms for finding all cut vertices in a connected graph as follows. ...
XYJ's user avatar
  • 7
0 votes
0 answers
12 views

How to compute a gradient map from a distance map

I need some help from the community to clarify something, seemingly very basic, to me. I have a 2D uniform grid with distances, for example calculated with Fast Marching Method. Now I would like to ...
Ozaq's user avatar
  • 1
0 votes
0 answers
19 views

If A ∈ coNP, B ∈ NP and $NP \neq coNP$, is it possible to Karp reduce A to B?

If A $\geq_p$B and $B\in NP$, $A\in coNP$, then we can build a Turing machine $M_A$ using $M_B$ machine of B. Input: w We make a new word with a reduction function $f(w)$. Then we run $M_B$ on $f(w)$ ...
Naneless's user avatar
1 vote
1 answer
30 views

Poly Time Algorithm for (0/1) Basic Feasible Solution

I have an LPP where the basic feasible solution is a vector in $\{0,1 \}^n$. I am not very well versed in linear programming and would like to know if poly-time algorithms exist to find such a basic ...
Rishabh Kothary's user avatar
2 votes
0 answers
54 views

Expected Entropy of the Empirical Distribution

Given a distribution on $n$ outcomes where outcome $i$ has probability $p_i$, the Shannon entropy of the distribution is defined as $- \sum_{i = 1}^n p_i \cdot \log_2 p_i$. Let's suppose I sample from ...
Karagounis Z's user avatar
2 votes
1 answer
48 views

Minimum Cell Changes to Ensure Unique Numbers in Each Row and Column of an $ n \times n $ Table

We have an $ n \times n $ table, and in each cell of the table, there is a number from $1$ to $ 2n $. We want to change the numbers in some of the cells and replace them with other numbers from $1$ to ...
Ferran Gonzalez's user avatar
0 votes
0 answers
31 views

Why is the time complexity of bidirectional breadth first search still considered O(V + E)?

I understand that if the branching factor of the graph is b and distance of goal vertex from source is d, then the time complexity is O(b^d). I also understand why that would be O(b^d/2) using ...
Shisui's user avatar
  • 121
0 votes
0 answers
27 views

Proving that if semidecidable, then computable

Definition: The graph of an n-ary function F is the n+1-ary relation $G_F$ defined by $G_F(a_1,...,a_n,b) \Leftrightarrow F(a_1,...,a_n)=b$. Theorem: if $G_F$ is semidecidable, then $F$ is computable. ...
spacemonkey's user avatar
1 vote
2 answers
48 views

Up to a certain number of witnesses, say 4

For a language $L$ to be in $NP$ it suffices for a witness $y$ to exist and a (polynomial) verification algorithm $A$, s.t. $x\in L$ iff there exists a (polynomial size) $y\,$ s.t. invoking $A$ on $x,...
Benicio Agüero's user avatar
0 votes
0 answers
30 views

Can a binary tree be generated from Union-Find using union-by-rank?

I'm trying to determine if the following claims are true or false: Claim 1 When disjoint Union-Find is implemented using up-trees and union-by-rank, and initially  there was a set of 5 single nodes. ...
Daniel's user avatar
  • 71
-1 votes
0 answers
13 views

Checking if two subgroups are equal in sage/python [closed]

I’ve defined two subgroups (E and F) as subgroups of a finite group B. B is a finite group which I defined as a quotient of a free group. My general goal is to determine if E is a subgroup of F. But ...
Ari's user avatar
  • 1
2 votes
2 answers
140 views

Approximation algorithm for binary (linear) programs

I am interested in solving the following problem: $$ \max c^\top x \qquad\text{s.t.}\\ Ax \le b\\ x \in \{0,1\}^n $$ One can assume that $c$, $A$ and $b$ have integer entries if that simplifies things....
Lisa E.'s user avatar
  • 540
1 vote
3 answers
36 views

What happens if CRC fails and errors are not detected?

Suppose you want to send a message M and let R be the CRC obtained using a generating polynomial ...
the_candyman's user avatar
1 vote
2 answers
1k views

Arrays. Find row with most 1's, in O(n)

Suppose that each row of an $n \times n$ array $A$ consists of 1's and 0's such that, in any row of $A$, all the 1's comes before any 0's in that row. Assume $A$ is already in memory, describe a ...
Science Guy's user avatar
-1 votes
1 answer
19 views

What formula was used here to calculate the average search time of the binary tree?

My teacher showed me the following slide on the PowerPoint with two binary search trees and their corresponding "average search times". The PPT did not mention what formula was used to ...
Felix An's user avatar
  • 119
0 votes
0 answers
22 views

In Lafont's interaction net, how to prevent undesirable annihilation?

Here is a simple case, given function f and input x, compute y = f(f(x)): this can be ...
tribbloid's user avatar
  • 103
1 vote
0 answers
27 views

Sparse bit string pattern matching

Suppose there are two strings of bits. Let's call them the needle (n) and the haystack (h). We'll say that the needle matches ...
Yan B.'s user avatar
  • 111
5 votes
2 answers
649 views

Is the complement of this context-free language also context-free?

Question from an old exam: Consider the alphabet $A=\{a, b, c, 1, 2\}$ and two fixed words $u=aaab$ and $v=baac$. Let $\mathcal{G}$ be a context-free grammar with the rules $$ S \rightarrow \epsilon |...
Michał's user avatar
  • 165
1 vote
1 answer
50 views

Can and does any statically typed programming language safely support in-place type-conversion?

Here's some hypothetical rust-inspired language syntax to show what I mean ...
Hjulle's user avatar
  • 113
0 votes
0 answers
26 views

Name for relation between trees being isomorphic after collapsing a single subtree

Suppose I have two rooted trees $T_1$ and $T_2$, such that if I select a subtree in $T_1$ and collapse it into single node (i.e. delete all nodes under the root of this subtree), then I end up with $...
ludog's user avatar
  • 90
0 votes
1 answer
26 views

Question about a grammar who generates $(0+1)^*$

On a test from my Automata theory class of last year, I have seen an excercise that gives the free context grammar $G$ with the following rules: $$S \rightarrow 0S1 | S0 | 1S | \varepsilon$$ and asks ...
Daniel García's user avatar
-1 votes
1 answer
24 views

Create a cfg for the language L = {w ∈ {a,b,c}* : |w| = 3na(w)}

All I know about this language is that it is equivalent to the following: $$L = \{w \in \{a,b,c\}^{∗} : n_b(w) + n_c(w) = 2 * n_a(w)\}$$ but I have absolutely no idea how to create a CFG for it.
AmirMohammad Shakeri's user avatar
1 vote
0 answers
27 views

Bron-Kerbosch algorithm for finding cliques missing a few edges?

The Bron-Kerbosch algorithm takes a graph and finds its maximal cliques in an efficient manner (as far as I'm aware, it is $O(3^{n/3})$, where $n$ is the number of vertices). Let $t$ be a positive ...
Alvaro Martinez's user avatar
1 vote
2 answers
45 views

What does "computer steps" mean in this runtime definition?

My algorithms textbook defines $T(n)$ as "the number of computer steps needed to compute fib1(n)" (where fib1(n) ...
Princess Mia's user avatar
1 vote
1 answer
39 views

Best online algorithm for a monotone priority queue that has equal amount of deletion and insertions

I got an executor thread that is given jobs to execute at certain timestamp. So this means my problem is online. While there are cases when the new job has a timestamp in the past, we can easily test ...
Giancarlo's user avatar
0 votes
0 answers
24 views

Kruskal's algorithm including an edge

I'm trying to solve the following question in which I have to find a list of critical edges and pseudocritical edges. From my understanding of the problem, critical edges are edges that must be ...
S10000's user avatar
  • 101
0 votes
1 answer
25 views

How is the prefix function (for KMP) time complexity O(N)?

I'm looking at the algorithm for the prefix function from here https://cp-algorithms.com/string/prefix-function.html : ...
JobHunter69's user avatar
4 votes
3 answers
187 views

MSOL and Courcelle's theorem for maximum clique

The Clique Problem is known to be NP-complete but is known to be fixed-parameter-tractable (FPT) if the treewidth of the underlying graph is fixed. The traditional proof is by a dynamic programming ...
Lisa E.'s user avatar
  • 540
0 votes
1 answer
57 views

Why get this P=NP? What I am doing wrong?

As we know, all NP problems are decidable because there is a NTM that can solve them in polynomial time. To my knowledge, any NTM is equivalent to a DTM. Thus, if NP problems can be decided by a NTM e....
Ali.A's user avatar
  • 11
5 votes
1 answer
51 views

What is the name of a DFA where all long enough words are synchronizing words?

TLDR: What is the name of a DFA that satisfies the following property: "I can guarantee that after feeding the automaton $n$ random symbols it will end up at some state that does not depend on ...
kovaxis's user avatar
  • 153
7 votes
1 answer
97 views

Determining whether there's a permutation that satisfies a linear equation

Given a positive integer $n$ and integer coefficients $c_1, c_2, c_3, c_4,..., c_n$, the goal would be to find a $\sigma \in S_n$ ($S_n$ is the group of permutations on $\{1,2,...,N\}$) such that: $$\...
Bryle Morga's user avatar
2 votes
2 answers
29 views

Minimal k-way comparison sorting algorithm?

I've watched 600 TV shows, and I want to sort them in order of how much I liked them. I'm bad at assigning absolute scores, but good at comparing relative enjoyment, so it has to be a comparison sort. ...
JentGent's user avatar
2 votes
1 answer
20 views

Limited constant degree HamCycle

Let $G=(V,E)$ be a directed graph. I am interested in a "relaxed" version of the HamCycle problem. In my first case, the degree of each vertex is exactly 6, such that: 3 are outgoing edges ...
Eric_'s user avatar
  • 465
0 votes
1 answer
51 views

Math major looking to learn some CS

I'm currently in school doing a pure math major, and I want to learn some computer science (potentially for jobs in finance requiring it but also just because I think it will be useful for the future),...
Sachin's user avatar
  • 1
0 votes
1 answer
39 views

How to write a Y-combinator implementation in javascript that does not exceed maximum stack size

TL;DR: Why applying a javascript implementation of a factorial function with a lazy Y combinator fails with "Maximum call stack size exceeded"? Here is the code: ...
Bogdan Nikolakov's user avatar
6 votes
2 answers
943 views

What is the difference between NP=EXP and ETH, and what does the community believe about their truth?

We know that $NP\subseteq EXP$ but not whether it is strict. The Exponential Time Hypothesis (ETH) states that SAT cannot be solved in subexponential time. My understanding is that most computer ...
user56834's user avatar
  • 3,982
0 votes
0 answers
14 views

What to learn for Java after AP CSA

I finished my AP CSA class this year where we learned the structural basics of Java. Mainly the different variables, using methods, different loops, arrays, and array lists etc. What should I learn ...
Haridasa's user avatar
  • 101
1 vote
0 answers
31 views

Chromatic Polynomial of Hamming Graphs

I'm trying to calculate the chromatic polynomial of different Hamming Graphs , especially $H(3, 3) = K_3 \times K_3 \times K_3$, so the Graph Cartesian product of the complete graph with three ...
Dan's user avatar
  • 61
0 votes
0 answers
51 views

Is there a "leader election" algorithm for communication via shared disks?

I've been trying to design such an algo with TLA+ formal prover, that is till I realized that it's a case of "simple-looking problem but with soooo many corner-cases", which screams of "...
Hi-Angel's user avatar
  • 121

15 30 50 per page
1
2 3 4 5
977