All Questions
44,851
questions
1
vote
1
answer
18
views
Disjoint Set Constant Time Union Operation
I am following a LeetCode tutorial for Disjoint sets I have trouble understanding why the so called "Quick Find" method needs to take O(n) time.
I have implemented an data structure that has ...
- 34.9k
1
vote
1
answer
12
views
Is ANF-SAT P or NP?
Given a finite set of equations in ANF, for example:
$$
\begin{cases}
(x_1 \land x_2) \oplus (x_1 \land x_3 \land x_4) \oplus 1 = 0 \\
x_3 \oplus (x_2 \land x_3 \land x_4) = 0 \\
(x_1 \land x_4) \...
D.W.♦
- 143k
0
votes
0
answers
5
views
Best style to lay out proofs that use denotational semantics to prove properties about a program?
Given some denotational semantics and a definition of correctness for a program, what is the best way to lay out proof on a program that aims to satisfy correctness?
Should I use some kind of ...
- 155
-2
votes
0
answers
5
views
What is the hamming distance of a 2D parity check?
A 2d parity check can detect all 3 error bits right. So its minimum hamming distance should be 4 right? But if one bit changes in the message, then only its column and row parity changes isnt it? ...
- 263
0
votes
2
answers
1k
views
Time complexity of quicksort for arrays in increasing or descreasing order
Two $n$-size arays are given: $n_1$ is in decreasing order and $n_2$ is in increasing order.
Let $c_1$ be the time complexity for $n_1$ using quicksort, and $c_2$ the time complexity for $n_2$ using ...
CommunityBot
- 1
1
vote
1
answer
39
views
Relation between algorithms and models
I have found this question some time ago. While reading it, I had a problem with understanding the following idea:
Question, part 1: Is one allowed to talk about the time/space bound of any algorithm (...
CommunityBot
- 1
1
vote
1
answer
24
views
What is the optimal algorithm for merging an arbitrary number of convex hulls?
Preparata & Shamos in "Convex Hulls: Basic Algorithms" (1985), give a linear algorithm for merging two convex hulls in $O(n+m)$ time, where $n$ and $m$ are the numbers of vertices in ...
- 4,163
1
vote
2
answers
103
views
Are regular grammar languages defined from "accepting" states?
In a transition diagram, the language L(D) where D is the diagram is defined as all the words that are formed from following an "accepting" walk. Does the same apply for languages of regular ...
CommunityBot
- 1
3
votes
1
answer
61
views
Algorithm for computing $Pr[s \vDash C \bigcup^{\geq n} B]$ for probabilistic verification
I'm having some difficulty trying to come up with an algorithm for computing $Pr[s \vDash C ~\bigcup^{\geq n} B]$ given a finite Markov chain where $S$ is the set of states, $s \in S$, $B,C \subseteq ...
CommunityBot
- 1
0
votes
0
answers
36
views
Simple proof that Lisp expresses all computable list functions
Given computable function $f : LispTerm \rightarrow LispTerm$ is it possible to implement it in Lisp?
The $LispTerm$ is any term that is constructed using cons, <...
- 41
1
vote
2
answers
31
views
How to store set of long char strings to search for long char string key
I have a set of several thousand strings of max length 1024 (containing all visible ASCII chars plus space) I need to store to make it fast to search for an exact match of a key. What is the best ...
CommunityBot
- 1
0
votes
0
answers
10
views
Formulate linear program with proportion constraint in matrix form
I have a lp/least squares problem that is formulated in matrix form:
minimize $c^Tx$
subject to $Ax=b$, $x_i>0$
with $c_i=1$.
How do i formulate a constraint $x_i > x_{i+1}$?
- 1
0
votes
1
answer
24
views
Greibach Normal Form: Proof every sentential form is of the form xy with x terminals and y variables
For any grammar in Greibach normal form, every sentential form obtained from S by a partial left-most derivation is of the form xy with x terminals and y variables.
I think that this can be proven ...
- 27.7k
0
votes
0
answers
17
views
Understanding the step in given algorithm?
I am a newbie to the world of algorithms design and currently working on a algorithm which is related to cell-phone user associating with cell-phone tower. Let $\mathcal{K} = \{1,\dots,K\}$ be set of ...
- 1
0
votes
1
answer
108
views
Difference between forward/backward slicing and reaching definition - def/use - use/def chains
I'm a little bit confused about the difference between forward/backward slicing and the use/def-def/use as part of the reaching definitions technique. Isn't the use-def chain supposed to be equivalent ...
CommunityBot
- 1
0
votes
0
answers
11
views
Link prediction in a network using GNNs versus Matrix Completion and other methods
I am looking at some social network analysis and I need to do link prediction. By link prediction I mean that I only have a subset of the relationships in the network, and I need to make predictions ...
- 121
2
votes
1
answer
531
views
Task Distribution Algorithm
Different machine has different efficiency on different tasks, like:
...
CommunityBot
- 1
3
votes
2
answers
77
views
Rank in a Convex Combination
Given vectors $A, B \in \mathbb{R}^{n}$, $w \in [0,1]$ and $x \in \mathbb{R}$, let
$$
Rank(A,B,w,x)=\sum_{i=1}^{n} \boldsymbol 1 \{w A_{i} +(1-w) B_{i} < x\}
$$
denote the number of elements in the ...
- 1,416
1
vote
3
answers
489
views
Floyd's Cycle Detection Algorithm Proof In Laymen
I came across the algorithm question of detecting a cycle in a linked list, but the solution has to be constant space O(1).
I have looked through various proofs proving that:
If there is a cycle, at ...
- 25.6k
1
vote
1
answer
221
views
Hex Word Search Generator Algorithm
I want to create an algorithm to build a hex matrix with given:
- max n rows
- max m collumns
- min t rown
- min q collumns
containing the specific words from a list: "example", "test", "algorithm"....
CommunityBot
- 1
2
votes
1
answer
2k
views
Using 2-opt Heuristic in a Genetic Algorithm for TSP
I read few papers while trying to find some better approachs to solve the TSP (Traveling salesman problem) as close to the optimal solution as possible. I implemented a Improved Greedy Crossover (...
CommunityBot
- 1
3
votes
2
answers
51
views
Matching superimposed image
We are given two grayscale images, one of which contains a large, mostly contiguous patch from the other one. The patch can be altered with noise, its levels may be stretched, etc.
Here's an example
...
CommunityBot
- 1
0
votes
1
answer
110
views
Minimizing series of XORs
Suppose you receive a list of $n$ instructions on $k$ boolean variables where each instruction has the form
$$x_i \leftarrow x_i \oplus x_j,$$
(where $\oplus$ is the binary XOR) can we efficiently ...
CommunityBot
- 1
2
votes
2
answers
27
views
How can I smooth thousands of faces in a 3D-mesh so as to end up with 6 faces of a die?
I have a 3D scan of an object with multiple faces, for example a standard 6 face die. The scan is a point cloud file of the die.
I am able to convert the point cloud into a mesh and retrieve faces ...
- 4,601
0
votes
2
answers
75
views
is duality principle in boolean algebra is true for every expression
Let say A = 1 and B = 1
and then A+B = 1
now by using duality(replacing or gate by and gate and 1 by 0) we can say that, A.B = 0
but this is not 0, because 1.1 = 1, so please anyone clear my ...
CommunityBot
- 1
2
votes
1
answer
30
views
Are there problems in $P$, long suspected to be $NPC$ (or $NPI$)?
One of the most compelling arguments people cite for believing $P \ne NP$ is that there are many problems of both theoretical and practical significance for which an efficient solution has eluded many ...
D.W.♦
- 143k
1
vote
1
answer
21
views
fastest algorithm for rectangular linear assignment problem
I want to optimally assign $m$ jobs equally to $n$ workers, where $m>n$. Assume $m = an$ for some integer $a$, so that each worker must get exactly $a$ jobs. (The rectangular linear assignment ...
D.W.♦
- 143k
0
votes
1
answer
99
views
Can PDA accept only by final state without finish reading input?
I am defining, a string $w$ is accepted by a PDA whenever the PDA enter into a final state during the computation(at least on one branch of the computation) on the input $w$ (no matter whether the ...
CommunityBot
- 1
0
votes
0
answers
22
views
Non-deterministic Pushdown Automaton to Context-Free Grammar
While doing the exercise about questions about transforming NPDA to CFG, I encountered the following question:
Find a CFG for the following NPDA $M = (\{q_0, q_1\}, \{a, b\}, \{A, z\}, \delta, q_0, z, ...
- 27.7k
0
votes
1
answer
58
views
Efficient Method for Distance Comparison in Euclidean Space
I have a vector of 2D Euclidean coordinates, and I need to find out if two or more points are within a distance threshold.
The naive approach is to compare each point with every other point, but I am ...
CommunityBot
- 1
0
votes
1
answer
23
views
How to handle Insert and Delete requests arriving out of order?
Entries need to be stored in a database. There is Insert(entry) RPC, which adds a new entry in a database, and Delete(entry) RPC,...
- 123
0
votes
1
answer
46
views
Correctness vs Proof of Correctness
Assuming we are observing an algorithm.I am confused as to how one needs to proof correctness.
What exactly the correctness represent for a given algorithm?
And why do we have to proof correctness, in ...
- 4,601
2
votes
4
answers
517
views
What is storing an instruction like?
Texts on microprocessors use lines like the following ones :
"The instructions in an instruction set of a microprocessors have their own address "
"In the first clock cycle the instruction is ...
- 4,601
0
votes
0
answers
5
views
Insert html at caret position inside content editable div
How to insert html at caret position in content editable div?
Actually I am to insert emojis inside content editable div with the help of emoji-mart emoji picker. But I am not able to implement it.
1
vote
0
answers
20
views
Time complexity of LP problems
In almost all websites and papers, the complexity of LP problem is given in the number of iterations (such as https://or.stackexchange.com/a/5924). I was wondering if there are any references where ...
- 125
0
votes
1
answer
600
views
Interest in Artificial Intelligence [closed]
(If I am posting this in the wrong StackExchange site, then please direct me to the correct one)
Okay, so some small background first: I am currently third-years student in Computer Science on the ...
- 171
0
votes
1
answer
49
views
Program counter in ISA with multi-word size for instructions
Some ISA's have instructions that are multiple words, such as the MOV instruction in x86. How does the program counter behave in that case, if the instruction loaded is more than one word? For example,...
CommunityBot
- 1
25
votes
3
answers
15k
views
What is the fastest algorithm for multiplication of two n-digit numbers?
I want to know which algorithm is fastest for multiplication of two n-digit numbers?
Space complexity can be relaxed here!
- 25.6k
1
vote
1
answer
27
views
How to bound the size of Boolean circuits?
Every function $f\colon \{ 0, 1 \}^n \to \{ 0, 1 \}$ can be computed by a circuit over the standard unbounded fan-in basis $\mathcal{B}_1 = \{ \neg, (\vee^n)_{n \in \mathbb{N}}, (\wedge^n)_{n \in \...
CommunityBot
- 1
0
votes
1
answer
45
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 ...
CommunityBot
- 1
2
votes
2
answers
628
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).
...
CommunityBot
- 1
0
votes
0
answers
18
views
What will be the Computational Complexity in terms of order O of the operations shown in the following figure
Suppose I have L bits. First, I want to multiply the L bits with L orthogonal codes of length N, and then I want to add all the vectors.
So, first, I have to do a scalar multiplication with a vector ...
1
vote
1
answer
15
views
Efficiently covering a finite set of points in $\mathbb{Z}^3$ by fixed size, axis-aligned cubes?
In my problem of interest I have an arbitrary, finite set $S \subset \mathbb{Z}^3$. And I would like to cover $S$ with a set $C \subset \{T | T \subset \mathbb{Z}^3 \textrm{ is an axis-aligned cube of ...
D.W.♦
- 143k
0
votes
0
answers
11
views
What exactly is meant by the term"model" in machine learning?
I am very confused. What is the meant by the term"model" in machine learning?Is it any equation/expression or any software/program or a vector?? I have tried to explore google but couldn't ...
- 129
0
votes
1
answer
10k
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 :
...
CommunityBot
- 1
1
vote
0
answers
27
views
Algorithms with different upper and lower bounds
I am preparing a list of algorithms for which big theta expression for (worst case) runtime is not known. This is for a class to demonstrate the point that tight analysis of an algorithm may not be ...
- 11
1
vote
1
answer
79
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 ...
CommunityBot
- 1
0
votes
1
answer
39
views
Enumerate all superincreasing subsequences
A sequence of positive real numbers S1, S2, S3, …, SN is called a superincreasing sequence if every element of the sequence is greater than the sum of all the previous elements in the sequence. E.g: 1,...
- 199
2
votes
1
answer
67
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 ...
CommunityBot
- 1
2
votes
1
answer
70
views
Find the largest segment within a queried range?
We are given $k$ segments $(s_1,e_1),(s_2,e_2),(s_3,e_4),...,(s_k,e_k)$ where $s_i\le e_i$.
Now we are given a query interval $[L,R]$ to find the largest segment $(s_i,e_i)$ contained within $[L,R]$.
...
- 23.9k