# All Questions

48,815 questions
Filter by
Sorted by
Tagged with
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-...
• 1
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 ...
• 1,684
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. ...
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 ...
1 vote
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 ...
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 ...
• 1,558
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. ...
• 173
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 ...
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 ...
• 71
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, ...
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 ...
• 63
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 ...
• 1
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 ...
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 ...
• 101
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 ...
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 >= ...
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. ...
• 7
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)$ ...
• 21
1 vote
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 ...
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 ...
• 121
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 ...
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 ...
• 121
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. ...
• 103
1 vote
53 views

• 465
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),...