# All Questions

48,985 questions
Filter by
Sorted by
Tagged with
1 vote
79 views

### What does the perfect chess algorithm look like?

Say we have an infinitely powerful computer playing chess. This computer can tell which moves lead to a win/draw/loss with best play. Obviously we want to pick a winning move if available, or a ...
15 views

### How is this factorial Y combinator evaluating in scheme?

I can't understand how this is evaluating in scheme. ((lambda (n) ((lambda (fact) (fact fact n)) (lambda (ft k) (if (= k 1) 1 (* k (ft ft (- k 1))))))) 5) ...
1 vote
103 views

### Why must 2 distinct strings go to the same state in a DFA?

I'm finding it difficult to understand why due to the pigeonhole principle, 2 distinct words must go to the same state in a DFA. Is it that if there are n words and m states, where there are more ...
35 views

### Lower bounds of sieves for factorization

Among factoring algorithms, both the Quadratic Sieve and the Number Field Sieve use sieves to find smooth (pairs of) values, in order to obtain congruent squares $\bmod n$, the number to be factored. ...
1 vote
31 views

### LTL Model Checking Worst Case size for NBA

I have a slide that gives the worst case time complexity of LTL model checking which uses a product construction of an LTS along with the NBA for the negation of the LTL formula. My question is, when ...
107 views

### Are deterministic Büchi automata omega-closed?

As in, given a regular language $V$, does there exist a deterministic Büchi automaton $\mathcal{A}$, or equivalently a regular language $W$ such that $\mathcal{L}(\mathcal{A})=\vec{W}=V^\omega$? For ...
775 views

### Scheduling / Queuing jobs with multiple different workers

I have a stream of jobs (so I don't know upfront how many jobs). And I have N workers in the system. Now I want to schedule / queue a job to one worker (a worker can have multiple jobs in his queue). ...
16 views

### Is this a valid AVL tree?

node 5 is the root of the tree and its left child has height 2 while right child has height 1. the difference between its children is <= 1. other than the difference between children, does a valid ...
24 views

### Solving a problem with linear programming

Suppose we wish to create a speech. Assume we have $n$ words to choose from numbered from $1$ to $n$. Every word holds a list of words that can come after it $S_i$. For example: if $2 \in S_1$ then ...
82 views

### How this state set of DFA was retrieved from the given NFA

I have this NFA: 1,{2, 3} 2,empty 3,{4} 4,empty All the arrows in this NFA are epsilon-arrows. I understand that all possible states that can be reached from each ...
1 vote
153 views

### Covering maximal number of sets using fixed number of elements

I've encountered some problem which seems general enough to have already been solved. There is a set of objects $O=\{o_1, o_2,\dots,o_k\}$ and a family of sets $A_1,A_2,\dots,A_t \subseteq O$. For ...
82 views

### Efficient Implementation of Boolean Lattice-Esque Operation

Let $X = \{1,2,\dots n\}$, and $Y_i= \{T \in \mathcal{P}(X): |T| \le i\}$. I am interested in "avoidance sets" $A \subset Y_n$. We say a subset $S \subset X$ is valid with respect to an ...
11k views

### LL(1) parsing table construction

i have the following CFG E -> ABC A-> a|Cb|epsilon B-> c|xA|epsilon C-> y|z and the First of the Non-Terminal : ...
3k views

### Could someone break down this grouping problem for me?

I am trying to work through this programming problem but I can't progress because I genuinely don't understand what it is that its asking me. New Students are arriving at college. Initially the ...
22 views

### What would a gluon computer be like?

So I was always wondering what a gluon computer (a computer using gluons instead of electrons or photons for the computing medium) would be like. There is absolutely NO literature anywhere online for ...
1 vote
66 views

### Heterogenous Resource Allocation Using Dynamic Programming

I'm working on a resource allocation problem, where there are $n$ different Items and $m$ different tasks ($n\geq m$). Also, The profit of assigning subset $I=\,(\, |I|\leq n)$ of items to task $j$ is ...
1 vote
99 views

### Difference between Data Type and Data Structure

I don't get what is the difference between a Data Type and Data Structure. As per Wikipedia, "Some types are very useful for storing and retrieving data and are called data structures". But: ...
40 views

### Proof of correctness for optimal solution for sorted two-sum

I have been solving the problem of two sum with a sorted array, which can described as follows: Given a sorted array arr sorted in non-decreasing order and a ...
1k views

### Disadvantages to using simple step functions for activation in neural networks?

From what I have read, the main advantage to using tanh(x) or sigmoid(x) as an activation function for neural networks is that it is very easily differentiable. I am trying to implement a neural ...
18 views

### Algorithm to compute the Kruskal’s Tree function

Im talking about the tree function, the famous function whose value TREE(3) is enormous. I know it is computable. Given that the function definition is rather simple, does there exist an algorithm of ...
1 vote
101 views

### What are the guidelines/tips for calculating the complexity of a chained-recursive function?

Any help will be appreciated, as I wasn't able to find much about it online in the last few days and I can't seem to write a suitable recurrence relation for this kind of functions.. Are there any ...
95 views

### Are there theorem dual to Tarjan's theorem for breath first search?

In "Depth-First Search and Linear Graph Algorithms" Tarjan proposed following theorem as the foundation of depth-first search (rephrase a little bit): Let $G=(V,E)$ be a connected (...
210 views

### Who conceived the concept of Discrete Event Simulation, and when?

I'm trying to trace back the origin of the general concept of Discrete Event Simulation and found a 1968 article by Fishman and Kiviat mentioning the term. It is titled The statistics of discrete-...
43 views

### Is $1 + o(1)$ the same as $\Theta(1)$?

Many theoretical papers used something like $N(1+o(1))$ complexity, but is it the same as saying $\Theta(N)$?
1 vote
43 views

### Version of SSSP

Let $G=(V,E)$ a directed graph s.t $|V|=n$. Let $w:E \to \mathbb{R}$ a weight function. Describe an algorithm which finds the minimal-weighted walk of length $\leq n$ from $s \in V$ to all other nodes....
774 views

### How to efficiently create balanced KD-Trees from a static set of points

From Wikipedia, KD-Trees: Alternative algorithms for building a balanced k-d tree presort the data prior to building the tree. They then maintain the order of the presort during tree construction ...
137 views

### Uncomputing measurement gate?

So one of Aaronson's lecture note (https://www.scottaaronson.com/democritus/lec10.html) pointed out that, if we'd like to simulate a BQP-oracle, technically speaking, the oracle of address-target form....
56 views

### Is "Length of Longest Increasing Subsequence" in L?

I can't find space complexity of this problem with search engines. I think I have NL algorithm for it (just a basic "one by one non-deterministically accept values if possible"), but I ...
1 vote
57 views

### On the equivalence between two definitions of universal hashing

Let $H=\{h|h:X\to Y\}$, $|X|=n$, $|Y|=m$. $H$ is a universal hash family if Def 1. For any $x_1,\ x_2\in X$, $x_1\neq x_2$, $\left|\left\{h\in H\middle| h(x_1)=h(x_2)\right\}\right|\leq |H|/m$. (or ...
1k views

### Why can't we prove SAT is NP complete just using the Tseytin Transformation?

The Cook Levin theorem proves SAT is NP-Complete, but it is fairly complicated, non-constructive and uses a Turing machine. I am confused as to why just the Tseytin Transformation does not imply/prove ...
1 vote
90 views

### Question regarding terminology used to describe Benes networks

I'm studying a routing problem on a cyclic butterfly network. The paper I am reading states that two properties of the cyclic butterfly network make it efficient for the routing algorithm it describes....
25 views

### SOFT QUESTION: MS in statistics (computational statistics specialisation) vs MS in CS(data science specialisation)

Question I aim to pursue a PhD in ML/deep learning from a top university in the US/Europe. Should I choose an M.Stat or an M.Tech in CS from the Indian Statistical Institute to strengthen my PhD ...
43 views

### showing NP completeness for XS

the XS problem: Input: n final sets and a number k (final sets - finite set of numbers, and k's value can be at most n). Question: Are there k sets in the n final ones that are not pairwise disjoint? ...
21 views

### Why are cyclic dependencies/imports a huge topic for type checking?

Both MyPy and ArkType cite cyclic dependencies/imports as either a challenge to handle or pride themselves on handling them. One is a type checker for Python while the other is a type checker for ...
1 vote
89 views

### How to group thousand of data points for each user

I have thousands of data points associated with users. So a single user can have 2000-10000 data points. These data points are identified by contiguous numbers (e.g. all numbers from 0 to 2000). Each ...
1 vote
490 views

### finding all cyclic substrings of a string

I have been stuck on this problem for a while now; any help would be appreciated. Given a string S, find the number of distinct substrings which are composed of 2 or more consecutive strings. For ...
145 views

### Analysis of pancake sorting

i was implementing pancake sorting. We can implement it by taking largest element to start and flipping it recursively (Like selection sort). However it is mentioned that the A[i] has to be a ...
1 vote
64 views

### splitting of people betwen groups with group prioritiy list per person

Looking for an algorithm for splitting a list of people (S) into groups (G), |S| <= |G|, more than one person wants to be in a certain group. Every person has a monotone ranking from highest (most ...
1 vote
81 views

### Proof that $PREFIX_{TM}$ is not recognizable

We define $PREFIX_{TM}$ as the following language: $PREFIX_{TM} = \{ \text{ <M> | M is a TM, L(M)}\neq \varnothing \text{ and whenever M accepts w it accepts every prefix of w} \}$ We only ...
396 views

### A Turing machine with each cell accessed at most $10$ times has an equivalent NFA

I am confused by the following claim: Let $T$ be a (decider, single-tape) Turing machine with the property that for every input, every cell on its tape is accessed at most $10$ times. Then there is a ...
356 views

### How to prove the optimization version problem (whose decision version is NP-complete) can be solved in poly-time iff P=NP?

I have proved the decision version of my problem to be $\mathcal{NP}$-complete. And I know that if I can solve the optimization version in poly-time, then I can just compare the obtained minimum (or ...
1 vote
35 views

### Logarithmic space reduction from PATH to 2COLOR-PATH

2COLOR-PATH = {<G,s,t> | G is a 2-Colorable directed graph that has a directed path from s to t} I need to write a logarithmic space reduction from PATH to 2COLOR-PATH (explained above). I know ...
1 vote
37 views

### Undecidability of a language similar to the Halting Problem

I would like to prove the undecidability of the following language $L$, closely related to the Halting problem: $$L:=\{w \mid M_w \text{ accepts a word of size }|w|\}.$$ It is obvious for unary ...
1 vote
377 views

### Check Proof Using Pumping Lemma to Show Language Not Regular

Please check my proof where I use the pumping lemma to show that the language $B=\{0^n1^n | n≥0\}$ is not regular. I'll state the pumping lemma here for clarity: Pumping lemma If $A$ is a regular ...
20 views

### Is this David Patterson 'Computer Architecture A Quantitative Approach' scheme right?

My guess is that L1 cache tag is also 28 bits as the L1 tag compare adress. Another question is why the offset is going to CPU? And the last one What other improvements and errors does this memory ...
45 views

### Optimally partitioning the reciprocals of the first n integers

Do we know anything about the hardness of the optimization version of the multiway number partitioning problem when the set of numbers to partition consists of the reciprocals of the first $n$ ...
770 views

### ALOHA - Throughput and probabilities

I have a few questions regarding slotted-ALOHA. Assume a network have 25 users and transmission request probability = 0.25. 1) What is the throughput and what is the probability that a user will ...
120 views

### How does a minimal DFA ensure minimal computational cost?

I just went to read wikipedia to check a point on FA minimization, and I read there the following sentence: The minimal DFA ensures minimal computational cost for tasks such as pattern matching. ...
138 views

### Window slider difference between GoBackN vs Selective Repeat

I am trying to learn about GoBackN and Selective Repeat ARQ. And I have the following practice question: Consider sender A and receiver B which communicate using an ARQ protocol. The current window ...
Let $p_1,p_2 \dots p_n$ be $n$ points in 2D such that $p_i= ( x_i,y_i)$ Let $d(p_i,p_j)= \max (|x_i-x_j|,|y_i-y_j|)$, or better known as Chebyshev distance. Find a point $p_i$ such that the distance ...