All Questions

Filter by
Sorted by
Tagged with
1
vote
1answer
3 views

Max-Min Weighted Matching

The maximum weighted matching problem (https://en.wikipedia.org/wiki/Maximum_weight_matching) finds a matching in a weighted graph that has maximum sum of weights. I was wondering if there are any ...
0
votes
0answers
3 views

Algorithm using a trie while calculating edit distance for fuzzy-string autocomplete matching?

In the paper Efficient Error-tolerant Query Autocompletion by Xiao et al., they state: The existing state-of-the-art solutions to the query autocompletion with edit distance constraints adopt the ...
0
votes
0answers
6 views

Concerning websites that have a search box. how prevalent is the use of the minus sign to exclude a term from the search?

I know that in prehistoric times, Lexis/nexis used the minus sign to exclude terms from a search. Today, google uses the same convention. Is it nearly universal, or more like 50%?
1
vote
0answers
5 views

Why place of MA in MB then copy from MB to IR rather than going straight from MA to IR

During the fetch stage of the fetch-execute cycle, why are the contents of the cell whose address is in the MA (memory address register) placed in MB (memory buffer) then copied to IR (instruction ...
0
votes
1answer
29 views

Is Python truly OOP?

My understanding is that a programming language is generally paradigm (functional, procedural, OOP) independent: we can code using different paradigms in some language. However, some languages, like ...
1
vote
0answers
9 views

Are there more efficient recognizers for the halting problem?

Define the halting problem as $\{\langle M, w\rangle: \text{$M$ is a TM that halts on $w$}\}$. It is undecidable, but recognizable, with a naive recognizer that simulates $M$ on $w$. In a certain ...
0
votes
1answer
19 views

Minimum number of intervals to cover all possible colors

Given $n$ points in $\mathbb{R}$ each colored with one of following three colors $$C=\{c_1, c_2, c_3\}.$$ In polynomial time, Choose the minimum number of intervals of length $1$ each containing some ...
0
votes
0answers
27 views

Are arrays “more abstract” than stacks or queues?

It seems to me that an array can be used as a stack or a queue and for various other things. In my mind this makes an array a higher order abstraction compared to those other two. Is this an ...
1
vote
1answer
13 views

DFA and a Partition of $\Sigma^*$

So I'm learning about Myhill-Nerode relations and as an introduction, the book describes possible partitions for $\Sigma^*$. As an example, given a language $L$, a partition of $\Sigma^*$ would be $\{...
1
vote
1answer
10 views

update distance matrix between n points

I am looking for an efficient algorithm to update a $N*N$ matrix, in which the coefficients represents the distance between $N$ number of points, every time that the coordinates of a point change in a ...
0
votes
0answers
12 views

How to count the number of nodes for a tree generated by context free grammar derivation?

Given context free grammar I use breadth first search and left most derivation rule to generate all possible words for a given language. For example: ...
1
vote
0answers
10 views

Is there an Upper Bound on Number of Redundant Clauses in a satisfiable $3-SAT$?

For a non-empty $3-SAT$ with $n\geq3$ variables and $T\geq1$ non-identical non-degenerate clauses $C_i$: $$S=C_1 \wedge \ldots \wedge C_T$$ where a non-degenerate clause is one containing $3$ unique ...
-1
votes
0answers
11 views

what's the algorithm for left recursion if Empty productions

what's the algorithm for left recursion if Empty productions. e.g. S::= αSβ | γ, ε ∈ α Since α maybe Empty, after some derivations, S->...-> Sβ is possible, how to eliminate such left ...
0
votes
0answers
18 views

Prove there is an algorithm that needs at most n-1 comparisons to check if n-element array has all equal elements?

Question: Prove that there exists an algorithm that can decide using at most n-1 comparisons whether a n-element array contains only equal numbers. We use an algorithm that loops through all the ...
0
votes
1answer
9 views

Term for the total communicated data over a distributed system

I am looking for a publication-friendly term to describe the total quantity of data communicated between nodes of a distributed system, as invoked by some discrete operation. This term would describe ...
0
votes
0answers
10 views

What exactly is "compositional desugaring"?

I've been reading Pombrio and Krishnamurthi's Hygienic Resugaring of Compositional Desugaring and I don't fully understand what they mean by "compositional desugaring". For example, they ...
0
votes
0answers
11 views

How do relational algebra query analyzers generate query alternatives?

tl;dr: How does a query analyzer know how to modify a query to find a better one? I would like to implement a distributed database. I have figured out ways of storing data in a normalized form, and ...
1
vote
1answer
27 views

Why Prefer Two Stacks to an Array for Undo/Redo?

It seems to be a popular opinion that "the right way" to implement undo/redo is "using a stack." (particularly in the context of an algorithms and data structures interview.) Here'...
4
votes
0answers
34 views

Algorithm to find equivalent classes of homotopic pathes on a grid with obstacles

Given a $n \times n$ grid with some walls and two cells $a$ and $b$, I want to compute the non-homotopics paths from $a$ to $b$ on this grid. A path is a sequence of adjacent cells (diagonal does not ...
0
votes
0answers
6 views

Count all independent sets and cliques of an undirected graph

I need to write a Java program that tells if a graph is a (k, l)-graph or not, that is, if we can partition its set of vertices into k independent sets and l cliques. Then I would need to build a ...
0
votes
0answers
15 views

A regular expression E* defines an infinite language $L_E$ [closed]

So I'm studying for an exam which is about languages and automata. There is a question in the book which asks us to prove that given a regular expression that can be infinite, say $E*$, the language ...
0
votes
1answer
9 views

What is the difference between discriminative information and diverse information in computer vision?

I am studying deep learning and found a lot of papers in which they tried to distinguish between discriminative information and diverse information. What disctiminative and diverse information mean? ...
0
votes
0answers
9 views

Turing machine with polynomial complexity on Jflap

I would like to ask a question: I have this very simple Turing machine. Simply by subtracting the numbers A and B, given the input M (A, B, C, D) =. Using the Step function on Jflap, complete the ...
0
votes
0answers
22 views

Sum of asymptotic notations

Let's consider a function $f \in \Theta(h)$ and a function $g \in \omega(h)$, what could I conclude about the sum $f + g$? Since $f \in \Theta(h)$ I think about $f$ as if it grows just like the ...
1
vote
1answer
30 views

Computable Numbers and Cantor's Diagonal Method

We were given the following problem in our university: We will call $x \in (0; 1)$ computable iff there exists an algorithm (e.g. a programme in Python) which would compute the $n^{th}$ digit of $x$ (...
0
votes
0answers
24 views

Max RAM capacity on modern cpus

I am wondering why modern consumer cpu usually has 128GB memory limit when server cpu supports terabytes. 128GB is really not that much. Do they really can't handle more RAM? How wide is their address ...
1
vote
2answers
30 views

Does multiplying word size numbers take constant time?

Does multiplying word size numbers (using standard grade school algorithm) take constant time? Can you use this to speed up computation and do the fast multiplication algorithms use this? By constant ...
0
votes
0answers
17 views

Understanding Theory of DPLL [closed]

I have several questions regarding DPLL Algorithm : Does by doing BCP could expose a new pure literal? Does by doing PLP could expose a new unit propagation? Can the output of DPLL is correct if we ...
1
vote
2answers
54 views

Iterable hash table

I'm currently working on implementing all the major data structures from C++ to better understand them and I arrived at the unordered_map, which should be a hash table implementation (it's actually ...
0
votes
0answers
15 views

TAPL - Concrete terms for untyped Lambda-Calculus

Working through Types and Programming Languages on my own. Hopefully check my work is allowed on this site. If not I will ask at the proposed Proof Assistants site after it goes live. For grammar in ...
0
votes
0answers
27 views

Why can't we solve the consensus problem by just enforcing a new leader?

I am going through this lecture series by Martin Kleppman. In this video at around 1:25, he says you can manually configure the distributed nodes to chose a leader. If that's the case can't we just ...
0
votes
0answers
13 views

Algorithm for scheduling tasks and resources [closed]

I want to design an algorithm to distribute $n$ tasks into $k$ resources. Tasks have a length and they cant be partitioned. And the aim of the algorithm must be that a task must end at the same time (...
2
votes
1answer
70 views

D* Lite - can edge costs be asymmetric?

I'm trying to modify the original D* Lite algorithm adding a margin constraint wrt to any nearby obstacle to be satisfied for each selected cell in the path. This causes the edge cost function between ...
0
votes
2answers
54 views

Θ, O, Ω, and how they relate to each other as subsets

I'm trying to better understand how Θ(n), O(n), and Ω(n) relate to each other as sets and want to make sure I'm on the right track. I get that Θ(n) ⊆ O(n) since Θ(n) is stronger and all of its ...
1
vote
0answers
18 views

How can a non-deterministic Turing Machine be converted to a deterministic TM with a witness-input?

This 2014 paper by Barak and Goldreich defines the notion of a universal set $S_{\mathcal{U}}$ as the set of all tuples $(M,x,t)$ such that the non-deterministic machine $M$ accepts the input $x$ in $...
0
votes
0answers
19 views

variant of skyline problem

This question is based off of the Skyline problem from GeeksForGeeks, and is also discussed in several other websites. The problem has two variations from the Skyline problem described in the ...
0
votes
1answer
34 views

Can 3-SAT be recognized in less than exponential time?

Obviously it is an open question if $3$-SAT can be decided in a polynomial amount of time. But what results do we know about its recognizabilty? Can $3$-SAT be recognized in a polynomial amount of ...
3
votes
0answers
26 views

fast multiplication of power of a matrix by a vector

I'm interested in computing of the product $M^n v$, where $M$ is an $m\times m$ matrix (over a semiring) and $v$ is column-vector, with the smallest number of multiplications in the underlying ...
0
votes
1answer
29 views

strange and different conclusions about Bellman Ford

Recently I asked a question Here about following topics: after finishing bellman ford algorithm, if BF continue to update distances and distance value related to one vertex v being updated,then v is ...
1
vote
1answer
19 views

Finding a minimum spanning tree that shares the minimum number of edges with the given one

Given some undirected weighted graph $\ G(V,E, w) $ and its minimum spanning tree $\ T$, I need to find another spanning tree $\ T' $ with minimal amount of common edges of both trees. If there are no ...
1
vote
0answers
25 views

How can I prove the correctness of the Hoshen–Kopelman algorithm?

I'd like to formally prove the correctness of Hoshen–Kopelman algorithm (link here https://en.wikipedia.org/wiki/Hoshen%E2%80%93Kopelman_algorithm). Anyway I don't know what is the right approach. At ...
0
votes
0answers
14 views

graph representation of a Boolean function

I'm trying to classify a certain family of Boolean functions, and need to represent the function as a graph. Is there any well-known graph representation for a Boolean function that captures the ...
3
votes
0answers
23 views

Linear time complexity

We know from the linear-speedup-theorem that NTIME($\mathcal{O}(f)$) = NTIME($f$) and DTIME($\mathcal{O}(f)$) = DTIME($f$), given that $f(n) > (1+\varepsilon) n$ for some $\varepsilon\in\mathbb{R}$....
-1
votes
1answer
53 views

if P=NP, and if language A is not NP-hard, A = ∅ or A = Σ*

I don't know how to solve this. Show that if P=NP, and if language A is not NP-hard, A = ∅ or A = Σ*
1
vote
1answer
33 views

Are there any operating systems that utilize only user threads?

We're going over threading models in my freshman CS class. Are there any examples of operating systems that use exclusively user threads (N:1)? It looks like 1:1 is far and away the most common model ...
0
votes
0answers
27 views

Finding the optimal packet size

I have recently started reading the book Computer Networking: A Top-down Approach in hopes to get introduced to computer networks. When attempting one of the questions from the book for practice, I ...
0
votes
0answers
26 views

Upper bound of sum of sub-tree depth difference on a complete binary tree with $n$ leaves

A complete binary tree with $n$ leaves has $n-1$ internal nodes. For every internal node $i$, I care about the difference between the maximum depth of the left sub-tree and the maximum depth of the ...
1
vote
1answer
77 views

bellman ford and one surprizing fact

I ran into a very surprising local contest problem. after finishing bellman ford algorithm, if we continue to updating distance and distance of one vertex v being updated, then v is on negative cycle....
0
votes
0answers
25 views

Modern proof of Goldwasser-Sipser IP[n]=AM[n+2]?

The original paper by Goldwasser and Sipser proved IP[Q(n)]=AM[Q(n)+2]. Is there some modern source that proofs the theorem? (The full theorem and not specific cases such as limiting the number of ...
1
vote
1answer
30 views

Tower of Hanoi variation - Split into two towers of odd and even disks

Suppose we have three rods A, B and C, and rod A ...

15 30 50 per page
1
2 3 4 5
862