All Questions

Filter by
Sorted by
Tagged with
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 ...
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) \...
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 ...
-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? ...
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 ...
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 (...
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 ...
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 ...
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 ...
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, <...
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 ...
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}$?
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 ...
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 ...
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 ...
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 ...
2 votes
1 answer
531 views

Task Distribution Algorithm

Different machine has different efficiency on different tasks, like: ...
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 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 ...
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"....
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 (...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
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,...
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 ...
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 ...
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 ...
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 ...
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,...
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!
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 \...
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 ...
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). ...
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 ...
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 ...
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 : ...
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 ...
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 ...
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,...
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 ...
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]$. ...

15 30 50 per page
1
2 3 4 5
898