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 ...
user avatar
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 ...
user avatar
  • 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? ...
user avatar
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) \...
user avatar
  • 13
1 vote
1 answer
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 ...
user avatar
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}$?
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 121
0 votes
1 answer
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 ...
user avatar
  • 15
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, <...
user avatar
  • 41
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 ...
user avatar
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, ...
user avatar
  • 101
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.
user avatar
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 ...
user avatar
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,...
user avatar
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 ...
user avatar
  • 129
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 11
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,...
user avatar
0 votes
1 answer
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 ...
user avatar
0 votes
1 answer
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 "...
user avatar
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 ...
user avatar
  • 88
0 votes
0 answers
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 ...
user avatar
  • 101
0 votes
0 answers
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 ...
user avatar
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 ...
user avatar
0 votes
3 answers
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 ...
user avatar
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]$. ...
user avatar
1 vote
1 answer
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)....
user avatar
-2 votes
0 answers
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?...
user avatar
  • 1
0 votes
0 answers
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 (...
user avatar
0 votes
0 answers
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 129
0 votes
0 answers
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 ...
user avatar
  • 131
0 votes
1 answer
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?
user avatar
  • 155
0 votes
1 answer
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 ...
user avatar
  • 103
2 votes
0 answers
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? ...
user avatar
0 votes
1 answer
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 ...
user avatar
  • 5,722
3 votes
1 answer
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|...
user avatar
  • 33
0 votes
4 answers
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 ...
user avatar
  • 101
0 votes
1 answer
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
  • 15
0 votes
1 answer
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 ...
user avatar
0 votes
1 answer
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 ...
user avatar
  • 15
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 ...
user avatar
  • 173
0 votes
1 answer
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 ...
user avatar
0 votes
0 answers
16 views

Conditional probability of making claim by insurance policyholder

In any given year,a male automobile insurance policyholder make a claim with probability $p_m$ and a female automobile insurance policy holder will make a claim with a probability $p_f$ where $p_f \...
user avatar
1 vote
2 answers
50 views

Given a sequence of sets, choose one element from each to get the lowest number of changes

Let $k,n \in \mathbb{N} $ and non empty sets $X_1, X_2, \dots, X_n \subseteq \{1,2,\dots,k\}$. Define the change counting cost function $f: X_1 \times X_2 \times \dots \times X_n \to \mathbb{N}$ by $f(...
user avatar
  • 113
0 votes
1 answer
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: ...
user avatar
  • 1
-1 votes
0 answers
7 views

i couldnt decide between unity gaming and unreal engine [closed]

https://unity.com/ https://www.unrealengine.com/en-US I couldn't choose one platform because I am just starting and I don't know which engine is best according to my need.
user avatar

15 30 50 per page
1
2 3 4 5
898