# All Questions

44,851 questions
Filter by
Sorted by
Tagged with
1 vote
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 ...
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 ...
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? ...
1 vote
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) \...
1 vote
23 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 ...
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}$?
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 ...
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 ...
23 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 ...
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, <...
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 ...
22 views

1 vote
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 ...
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,...
26 views

### Decimal To Binary Conversion: Predicting Numbers With No Zeros

Just a fun puzzle that occurred to me. Given the function below which converts decimal integers to binary strings, is it possible to predict which decimal numbers will lead to binary strings with no ...
38 views

### What defines a byte?

I am asking this question because for some reason ascii codes from range 128 - 255 have a size of 2 bytes but their composition is 8 bits which makes them a "...
1 vote
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 ...
11 views

### Co-refinement or PER-refinement types

I just learned about LiquidHaskell, which is Haskell with refinement types. As pointed out by drcicero, the type former that sets apart a refinement type system from a simple type system is the type ...
26 views

### Power of regex extensions [duplicate]

It is well known that classical regexes recognize exactly regular languages. But in practice, many programming languages have extensions to the regex syntax which potentially broaden the field of ...
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 ...
45 views

### Execution Time in Stage Pipeline

Exam Question: A five-stage pipeline has stage delays of 150,120,150,160 and 140 nanoseconds. The registers that are used between the pipeline stages have a delay of 5 nanoseconds each. The total time ...
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]$. ...
1 vote
985 views

### Why can't 3-SAT be solved efficiently if you convert all clauses (x ∨ y ∨ z) into (u ∨ z) by introducing a variable?

Let $a_i$, $b_i$, etc., be a literal, i.e., a variable or the negation of a variable. 3-SAT concerns formulas in CNF form: $(a_1 \vee a_2 \vee a_3) \wedge \dots \wedge (b_1 \vee b_2 \vee b_3)$ (3-CNF)....
14 views

### ER diagram structure creation

How will be the ER diagram for “Each customer may generate many invoices, or none at all” This a a simple question given by my professor to me. However, I am doubtful to my answer. Can anybody help me?...
26 views

### Complexity of fractional knapsack problem

I am bit confused while reading a standard textbook of my curriculum, where it is mention time complexity for knapsack problem is O(nlogn), and rationale they provided is we need O(n) to calculate (...
39 views

### Tail call optimization via translating to CPS

I am struggling to wrap my head around this compiler technique, so lets say here's my factorial function ...
21 views

### Relation between machine learning and computer vision?

What is correct concept in regards to relation between machine learning and computer vision? As shown red encircled in attached snap, computer vision is a subset of machine learning or Is it an ...
27 views

### Is logic in computation of computation constructivist? [closed]

Is logic in computation of computation constructivist? I think so, because dynamic languages ​​are comparable to constructivist set theory (try a demonstration of the axiom of choice in computing: it ...
52 views

### Are there any formal systems or programming languages in which its only possible to define functions that have inverses?

Consider an algorithm $f(x)$. Are there formal systems or programming languages that only allow $f(x)$ to be defined if $f^-1(x)$ exists?
22 views

### Why does a CRC detect burst errors of longer than r+1 bits independently of burst length?

In this question it is stated that a CRC detects burst errors of length greater than the CRC length with probability $1-2^{-r}$, where $r$ is the length of the CRC. Why is there no dependence on the ...
46 views

### Is odd cycles cover NP-complete?

Schaefer proved that deciding even cycles cover ( 2-factor with even cycles) in cubic graphs is NP-complete. I am interested in the complexity of odd cycles cover in cubic graphs. Is it NP-complete? ...
39 views

### Looking for name of a priority queue data structure based on bit-boundary buckets

(Note: cross-listed on stack overflow: https://stackoverflow.com/questions/73362856/looking-for-name-of-a-priority-queue-data-structure-based-on-bit-boundary-bucket) I'm looking for the name of a data ...
18 views

### Hopcroft's minimization algorithm produces an incorrect result for a particular regular expression

I'm writing a DFA minimizer using Hopcroft's algorithm. While testing some regular expressions, I came out with an issue in the algorithm's output relative to two particular regular expressions: a(b|...
94 views

### Are integers an abstract data type?

I'm trying to understand whether integers are an abstract data type. The Wikipedia article starts out by saying that integers are not an ADT: In practice, many common data types are not ADTs, as the ...
24 views

### Is this an inversion problem?

I understand that total inversion in a sequence is the number of swaps that need to be done, to sort the sequence. And the best approach to solve this problem is to count swaps in a merge sort of the ...
1 vote
38 views

### proof of non Turing-computable function g

In one of my lessons about turing machines I have been taught that the function g is not computable: \begin{cases}g(n)=f_{n}(n)+1 & \text { if } f_{n}(n) \text { is defined } \\ g(n)=1 & \text ...
57 views

### Recurrence relation of multiply two $n$ bit numbers

Suppose given two $n$ bits numbers $A$ and $B$. Also suppose there is a machine that compute multiply two $\sqrt{n}$ bits numbers in $O(1)$. What is time complexity of multiplying two $n$ bits number ...
32 views

### Pumping lemma for context-free languages: Importance of length restriction

(from 'An Introduction to Formal Languages and Automata' by Peter Linz) What I do not understand, is why we have done our best to make sure that the condition (8.2) holds. Why is this restriction ...
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 ...
21 views

### Complexity of the feasibility and optimization problems

Given an optimization problem $P$, if we know that this optimization problem is NP-hard, is it necessary to check the complexity of the corresponding feasibility problem, i.e. the complexity of ...
16 views

26 views

### what is the time complexity of this while loop nested in a for loop?

I'm really having rough time understanding the time complexities of nested loops. So, please help me out in this code. The code is on sliding window with changing length: ...