All Questions

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

Cross compiler construction

Generate a cross compiler for the first version of EQN compiler, the compiler is written in C and the commands are generated for TROFF. The cross compiler for EQN can be obtained by running it on PDP-...
Sana's user avatar
  • 1
0 votes
1 answer
13 views

Is this graph grouping problem $\mathsf{NP}$-hard?

Let's introduce the notion of layer: given a simple graph $G$ a layer is a subgraph of $G$ satisfying following properties: If any pair of vertices is connected with an edge, these two vertices ...
rus9384's user avatar
  • 1,684
0 votes
0 answers
7 views

Lower Bound States for NFAs: Seeking Examples and Methods

We can establish some lower bounds for DFAs recognizing specific languages. For example, we can show that there exists a language $L_n$ such that every DFA recognizing it has at least $2^n $ states. ...
zap brannigan's user avatar
0 votes
0 answers
10 views

Do I need to display constants in the step count method

I tried looking this up before coming here but I couldn't find any resources. If there is a post that already exists that can explain this please let me know so I can close this one. I am creating ...
Cade Bray's user avatar
1 vote
0 answers
16 views

Relative running times of equivalent Turing machines with arbitrary and binary alphabets

The book "Computational Complexity: A modern approach" by Sanjeev Arora and Boaz Barak contains the following claim: Claim 1.5 For every $f : \{0, 1\}^∗ \to \{0, 1\}$ and time-constructible ...
Gaurav Chandan's user avatar
0 votes
1 answer
14 views

Do edge lists have O(E) storage if default values are used for absent keys?

Ordinarily, edge list representations of graphs take $O(V+E)$ space, where $V$ is the number of vertices and $E$ is the number of edges. For example, consider a graph with 5 nodes and a single edge ...
Ellen Spertus's user avatar
0 votes
1 answer
34 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
2 answers
31 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
20 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
31 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)$ where n is the number of states in the ...
shaggy's user avatar
  • 63
0 votes
0 answers
12 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
14 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
35 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
10 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
17 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
20 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
31 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
1 answer
75 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
54 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
32 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
53 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
  • 538
1 vote
3 answers
37 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
2k 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
24 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
28 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
653 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
27 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
46 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
25 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
26 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
192 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
  • 538
0 votes
1 answer
58 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
100 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
21 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
57 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
40 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

15 30 50 per page
1
2 3 4 5
977