All Questions

Shorter version of my question: Is there any polygon union algorithm that allows me to change one of the polygons quickly? Longer version: Currently the major performance bottleneck I'm facing in one ...

I'm writing some software that involves processing a large collection of images that are arranged spatially. It basically involves loading pairs of images into caches and computing an operation on the ...

Algorithm rec(n) { if (n ≤ 2) return 1 else { return (2*rec(√n) + n) } } Return value recurrence relation, I want to find the exact value and not ...

There is a lot of Turing machine out there. Most of them are purpose-specific. What make universal Turing machine universal? How do we know or prove if a computer is universal? Edited: Is ...

Specifically, what NP-hard problem can we reduce (the decisions version of) GAP to and how do we prove its correctness? The decision version of the generalized assignment problem is to determine ...

I would like to brainstorm/get some advice/tips regarding the following question. Given an array,you can either insert elements or you can delete elements from it.Note the insertion/deletion must be ...

Consider the following algorithm for bin packing: Initially, sort the items by their size. Put the largest item in a new bin. Fill the bin with small items in ascending order of size, up to the ...

The question is: A given graph is given with only weights 1 or 2 on its arcs. (I.e. each arc has a weight of 1 or a weight of 2) And a origin vertex s. Write an efficient algorithm that finds the ...

Let $A$ be a finite set of variables. Let $B$ be a finite set of equations of the form $(\sum_{x \in C}x - \sum_{x \in D}x = a)$ where $C$ and $D$ are two disjoint subsets of $A$, and $a$ is an ...

Suppose $$L=\{wo^n\mid w\in\{a,b\}^*, n_a(w)=n \text{ or} |w|=n\}$$ Can we conclude that $L$ is DCFl? I think it's DCFL because $$L=\{a^no^n\}\cup \{\{a,b\}^no^n\}$$ Since $$\{a^no^n\}\subseteq \{\{a,...

Integer Multiplication: $x$ and $y$ are two n-bit integers, where $n=3^k$ for some $k>0$. We break $x$ into three parts $a$, $b$, $c$, each with $n/3$ bits; and $y$ into three parts $d$, $e$, $f$, ...

Given are $n$ integer numbers in the range $0$ to $5n$. A SubSort algorithm organizes the numbers into $k=n/100$ sets, $s_{1}$, …, $s_{k}$ , each containing $100$ numbers, such that the following ...

Its little vague question. I am not able to visualize - Tree data structure is used to represent hierarchical entities in real world or is meant to organize data to optimize certain operations like ...

I tried to show the following language is DCFL (Deterministic Context-Free Language): $$L=\{wo^n\mid w\in\{a,b\}^*, n_a(w)=n_b(w)=n, |w|=2n\}$$ I tried to show that $L$ has a DPDA (Deterministic Push-...

Suppose we have an 2D array $A[1..64][1..64]$. $$\forall_{i,j\in\{1,2,\dots,64\}}A[i][j]\in\{0,1\}.$$ Our task is, sort the odd rows of $A$ in ascending order, even row of $A$ in descending order. Our ...

Consider the following claim. Let $a_i$'s and $y_i$'s be positive real numbers such that: \begin{gather*} y_1 \leq y_2 \leq y_3 \ldots \leq y_n \\ a_1 y_1 + a_2 y_2 + a_3 y_3 + \dots + a_n y_n = v \\ ...

I just came across a blockchain concept called "Proof of Space-Time" in which participants compete to verify blocks by generating and storing essentially random data to answer essentially ...

Given an unweighted directed graph $G=(V, E)$, two vertices $s,t \in V$ and a subset of vertices $U \subseteq V$, suggest an algorithm which concludes if there exists a shortest path from $s$ to $t$ ...

I happened to have a look at the C one-liner by David Korn, which won him the IOCCC in 1987. The one-liner is as follows: ...

Can you recommend a good resource to learning proofs of concurrency algorithms? A book would be ideal. I have searched the internet but could not find good resources.

If I'm given a tree with "$k$" keys, or "$n$" nodes and I need to find the minimal / maximal height of the tree, I know that I have to split it into two cases: $i$. The tree is ...

I use a pc having an asus monitor and a very old cpu. I just wanted to know how much electricity will my pc consume if I am just reading a pdf on it or browsing something. I have an asus monitor(17 ...

Assume that the oil company saves for each person that works in the company a record with its name, its salary, its age and its date of birth. You can assume that no two fields are identical for any ...

My question is about part 15.5 in CLRS (third edition)*, on optimal binary search trees. I am confused about the following sentences: Consider any subtree of a binary search tree. It must contain ...

A sample example of Synchronous Data Flow (SDF) graph (from here): How to convert it to Cyclo-Static Synchronous Data Flow (CSDF) graph?

We are given an array $A[1..n]$. We don't have direct access to $A$, but we can query what is the sum of $A[i..j]$ for every interval $i..j$. We would like to find the maximum of $A[i..j]$ over all ...

I have been given two True/False questions regarding sorting an array. The questions are as following - Question A Given an array A with 3n keys that contains three equal parts A[1,n], A[n+1,2n] and ...

I am writing a vulnerability report for an online application storing personnel data in a 3rd party server and have some questions about how to do it. If you can answer any please do, any answer and ...

I am following article which says-: Content type-: defines the data present in body of message. eg-: text,image,video,application etc. Content description-: It is used when body of message can't be ...

I have an array of numbers, and I need to check if there is a repeating pattern in the array. Like, for example, if I have an array A=[1,1,6,1,1,6,1,1,6,1,1,6...] this should return "Yes" (...

I've seen Conway's game of life mentioned in different circles and it seems many people (myself included) have made an implementation of it at one point or another. Other than the fact that it is ...

I'm trying to find an efficient algorithm to solve the following ... During the day, a supermarket will receive calls from customers who want to place orders. The supermarket manager knows in advance ...

I'm doing an assignment where I need to multiply two 16 bit numbers and store result as an 16 bit integer array. a is binary with length of ...

I'm looking for a book on the subject of algorithms and data structures, but I want to specifically learn about the parallel implementations. Books that teach CUDA and OpenCL usually have small ...

One of my Client asking me, They need "the modifiers data structure". I need to provide this information to them. I am not sure what they are asking. Could anyone please help me out ...

Can you please help how to resolve this error ?? Also running .\hello in terminal is giving no output and doing nothing. Not even showing up an error.

I have an algorithmic question for you: Given: 3D triangle surface mesh, open polygonal chain A, closed polygon B, closed polygon C, all on the mesh. Wanted: A line that closes A such that B lies ...

I have an algorithmic problem that I am hoping someone can help me out with: Given: 3D triangle surface mesh, an open polygonal chain (blue). Wanted: A line that closes the blue line in clockwise ...

I am trying to understand why the time complexity of the Bit Manipulation solution (https://leetcode.com/problems/add-binary/solution/) to the Binary Addition problem is O(M + N), where M and N are ...

I want to calculate a similarity ratio between two long texts (by "long", I imply something around 1000 characters or higher). For example, two texts with only one word changing should have ...

I've been scouting the internet for days and after a lot of digging, I decided to resort to my last hope and ask: I'm talking about the "hey Google", "Alexa" and so on voice ...

Referring to the Wikipedia proof : Wikipedia proves the space hierarchy theorem using the following language: $$ L = \{ (\langle M \rangle, 10^k) : \text{$M$ does not accept $(\langle M \rangle, 10^k)$...

W-types generalize the type of well-founded trees, i.e., possibly infinetely branching trees. I understand that inductive types may be encoded as such in dependent type theory (CIC, MLTT, etc), this ...

I am looking for an algorithm to a problem that I encountered when working with 3D modeling: On a 3D triangle surface mesh, I have multiple lines, some of them are open, some are closed. The are on ...

Determine if for given some $L$, $S_L=\{\ L(M) | <M>\in L \}$ then for any $L$, if $S_L=RE$ then $L\in R$. Correct or Incorrect and explain why. I think the claim is incorrect, and I'm trying ...

So let's say we have the function $f(n)$ that gives $k$ such that $k$ is the smallest number that gives a busy beaver function $B$ value from input $k$ that is greater than $n$. Or more succinctly the ...

Let's say we have a string $s[0..n-1]$ and a pattern $p[0..m-1]$ with $m < n$. I am looking for an $O(nm)$ solution to the following problem: find the number of substrings of $s$ not containing $p$ ...

We know that the worst-case time complexity of any comparison sorting algorithm is $\Omega(n\log n)$. Is there a lower bound on the worst-case running time of sorting algorithms of any type? Not just ...

While this question already exists and does talk about a heuristic with the Farthest Point First technique, I would like to approach the problem in a more efficient way. I do agree that this is an NP ...

I am working on building ML/DL solution for a problem where that data is considered, naturally similar and I am worried if that would be considered as data redundancy. My question is, is that so? and ...