# All Questions

48,980 questions
Filter by
Sorted by
Tagged with
6 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 ...
• 170
25 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? ...
• 25
1 vote
18 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....
12 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 ...
524 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 ...
29 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
31 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 ...
• 25
1 vote
36 views

### Computation theory: decidability and Turing-recognition

I have this question which I have some difficulties with: "Given: There is a non-deterministic Turing machine that quickly recognizes language C. Question: Is C necessarily a decidable language? ...
• 25
6 views

### How to Ensure Consistency When a Worker Process Reads Configurations During Leader Update in ZooKeeper?

I'm going through ZooKeeper: Wait-free coordination for Internet-scale systems. In section 2.3 ZooKeeper Guarantees, authors have detailed how below scenario is handled. Though I believe Justification ...
24 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 ...
61 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: ...
1 vote
36 views

### is 3-SAT ∈ NTIME(n^3)?

I'm struggling to understand the time complexity of 3-SAT using a non-deterministic Turing machine, as well as the relationship between NTIME and DTIME For example, let's say we have 2 literals. My ...
46 views

### Reorder a Binary Heap to have the smallest elements in one half in linear time

Is there a known algorithm that can reorder a binary heap of size $N$ so that after the reordering we still have a valid binary heap the first half of the input ($\frac{N}{2}$ elements) are all ...
1 vote
27 views

### Fixed-point theorem and ability to access its own source code

I am reading this text about quines and, it mentions a fixed-point theorem in computability (which I believe is Rogers's fixed-point theorem). Just after that, it says: The fixed-point theorem has ...
• 241
19 views

### Starvation Condition versus Deadlock in the critical section problem

I'm reading Ben-Ari's book Principles of Concurrent and Distributed Programming and am getting a little confused by his presentation of the "Starvation" requirement and the "Deadlock&...
68 views

### $L'=\left \{w : w\cdot Drop_a(w)\in L \right \}$ is a regular language

$\Sigma=\left \{ a,b,c \right \}$. For a string $w\in \Sigma^*$, $Drop_a(w)$ is the string $w$ after we remove all occurrences of "a" from it. The question asks to show that if $L$ is a ...
• 147
1 vote
13 views

### How can a ball tree improve the efficiency of finding nearest neighbors when it involves finding least-near neighbors?

The motivation for k-d trees and ball trees is that k-nearest neighbors involves eliciting the distances between a particular data point and every other data point, which becomes inefficient as the ...
• 111
30 views

### confusion between memory address and size

Sorry if the question appears silly, but I just really want to understand what actually are memory addresses. When I asked this question on google, I found that some people compared this with a post ...
64 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 (...
• 141
22 views

### Field from "dummy" node gets updated

I am trying to implement evenOddMerge solution to the problem (grouping together firstly odd indexed nodes, then even indexed nodes, e.g. from ...
• 103
17 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 ...
• 101
1 vote
45 views

### $L=\left \{ \left \langle M,D \right \rangle : M=TM\, ,\, D=DFA\, ,\, L(D)\neq \emptyset\, ,\, L(M)\subseteq L(D)\circ L(D) \right \}\notin RE$

$L=\left \{ \left \langle M,D \right \rangle : M\, is\, a\, TM\, ,\, D\, is\, a\, DFA\, ,\, L(D)\neq \emptyset\, ,\, L(M)\subseteq L(D)\circ L(D) \right \}$ $L\notin R$ which can be shown for example ...
• 147
1 vote
38 views

### Can multi-threading help improve an IO-bound process perforamance?

I am trying to understand the difference between CPU Bound vs IO Bound process. ChatGPT suggested that multi-threading/parallel processing can help CPU bound process; However, I think that having ...
• 149
32 views

90 views

### Is this set cover problem NP-complete? (creating a list of best movies per year)

Let $X$ be a finite set. Let $\mathcal{F}$ be a family of subsets of $X$. Assume each set $F\in\mathcal{F}$ is colored with a single color from a set of colors $C$. Is the following problem NP-...
• 53
1 vote
58 views

### Accessing out of bounds indexes on an array in C

I am trying to figure out how to apply the Sobel edge detection for a BMP image, which is a 2D array of BYTE values. When multiplying a pixel by the GX or GY kernel, if the pixel is on the edge of the ...
• 31
17 views

### What is the role of m and Sn in Go-Back-N here?

In a network using Go-Back-N protocol with m = 3 and the sending window of size 7, the values of variables are Sf= 62, Sn=66, Rn=64. Assume that the network does not duplicate or reorder the packets....
1 vote
24 views

### Is always $KL[f(x|a) || g(x|a) ] \leq KL[f(x) || g(x) ]$ for fixed $a$?

Suppose we have two prior distributions over $X$, namely $f(x)$ and $g(x)$ (assume $X$ is finite if necessary). Define $f(x|a) = Z_f\cdot f(x)\cdot h(a|x)$ and $g(x|a) = Z_g \cdot g(x) \cdot h(a|x)$, ...
• 4,012
25 views

### Why do some authors check for "$x \ne w$" in reductions from $A_{TM}$ to $E_{TM}$?

Def.: $A_{TM} = \{<M, w> \mid M$ is a TM and $M$ accepts $w \}$ $E_{TM} = \{<M> \mid M$ is a TM and $L(M) = \emptyset\}$ I found that some authors (e.g. Sipser 2013, 3rd ed.) use an ...
• 123
27 views

### How to find the minimum set of members of many sets

Given many sets, what algorithm finds the minimum set(s) of members present in all those sets? For example, given these sets: {1,2} {1,2,44} {2,5,6} {5,6} The ...
• 101
61 views

### Is there any consensus as to Gordeev & Haeusler's purported proof of $\mathsf{NP} = \mathrm{co}\mathsf{NP}$?

As title states, I'm interested in knowing whether there is any known consensus as to Gordeev and Haeusler's recent results claiming $\mathsf{NP} = \mathrm{co}\mathsf{NP} = \mathsf{PSPACE}$. Although ...
• 165
29 views

### How to generate a skeleton (medial axis) of a polygon using Fortune's algorithm?

I have been learning recently about Fortune's algorithm to generate the Voronoi diagram given some input but I was interested in the application of this within polygons to generate skeletons (also ...
• 131
10 views

### Can I upgrade my laptop. I have an HP Compaq 6910p [closed]

Can I upgrade my laptop. I have an HP Compaq 6910p. It runs Windows XP Professional. It works fine (word excel etc) except that now it’s so old I can’t load/ see most things on the internet. E.g. I ...
• 1
19 views

### Three way merge AST: how to match nodes that are not uniquely identified

Given a structured document like Markdown or Org mode that is recursively made up of - simplifying - sections (with title and body) and subsections, I'm looking for idea on how to possibly implement a ...
• 121
72 views

### Classifying a language of TM encodings

Let $$L=\{ \langle M\rangle: \text{M is a 1-tape TM, and there is no 2-tape TM M' such that}$$ \text{$q'_0\notin \{ q'_{acc}, q'_{rej}\}$, $L(M') = L(M)$, and $M'$ has less states than $M$ }\}\$...
1 vote