All Questions

43,090 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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%?
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 ...
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 ...
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 ...
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 ...
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 ...
13 views

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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}$....
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 = Σ*
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 ...
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 ...
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 ...
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....