All Questions

Filter by
Sorted by
Tagged with
3
votes
0answers
12 views

Dynamically compute the union of polygons

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 ...
2
votes
0answers
10 views

Task scheduling with the constraint of pairs of objects being present in a cache

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 ...
0
votes
0answers
10 views

What is the return value of the following code R(n) = 2R(√n) + n?

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 ...
0
votes
1answer
56 views

What does it mean for a computer to be general-purpose?

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 ...
0
votes
0answers
19 views

How to prove that the generalized assignment problem (GAP) is NP-hard?

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 ...
0
votes
1answer
14 views

minimum insertions and deletions required to ensure that each value X occurs X times

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 ...
3
votes
0answers
20 views

What is the approximation ratio of this bin-backing algorithm?

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 ...
0
votes
2answers
63 views

An “easy” graph problem I can't solve

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 ...
1
vote
0answers
31 views

Automatically find a set of equations

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 ...
1
vote
0answers
44 views

Is $L$ Deterministic Context-Free Language?

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,...
0
votes
1answer
65 views

Multiplying two integers by dividing each into 3 parts

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$, ...
0
votes
1answer
31 views

Sorting elements into k subarrays

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 ...
-1
votes
0answers
14 views

Tree data structure is for behavior modeling or optimizing operations?

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 ...
2
votes
2answers
198 views

Is the following language a Deterministic Context-Free Language?

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-...
0
votes
0answers
55 views

Worst case sorting a boolean matrix

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 ...
2
votes
1answer
156 views

Seeking an “intuitive” proof

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 \\ ...
0
votes
1answer
36 views

Why is “Proof of Space” insufficient to secure a blockchain?

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 ...
3
votes
0answers
28 views

Shortest path which passes through a subset of vertices in an unweighted directed graph [duplicate]

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$ ...
-1
votes
0answers
36 views

David Korn's IOCCC-winning one-liner [closed]

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: ...
-1
votes
0answers
28 views

Resources for learning concurrency proofs

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.
0
votes
0answers
8 views

Full analyses of the number of nodes/keys and height of B-Trees

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 ...
-1
votes
0answers
20 views

Inquiry about the power usage of my pc [closed]

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 ...
0
votes
0answers
27 views

Question about AVL properties

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 ...
3
votes
1answer
41 views

Observations about the structure of an optimal Binary Search Tree

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 ...
0
votes
0answers
11 views

How to convert SDF to CSDF graph?

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

Largest sum of a contiguous subarray using queries of the same form

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 ...
1
vote
2answers
216 views

Sorting an array with x sorted subarrays

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 ...
0
votes
0answers
9 views

Cyber Security Vulnerability Report Writing [closed]

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 ...
0
votes
0answers
18 views

What is the difference between content type and content description in MIME header?

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 ...
-1
votes
1answer
34 views

Pattern finding in an array of numbers

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" (...
2
votes
2answers
75 views

Whats the signifgance of Conway's Game of Life?

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 ...
2
votes
1answer
34 views

Is there a better way to optimize my algorithm for maximizing order volume?

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 ...
1
vote
0answers
35 views

Is it possible to find length of sum of two binary numbers without calculating sum?

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 ...
3
votes
2answers
45 views

Books about data structures and algorithms but specifically focusing on parallel gpgpu programming

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 ...
-3
votes
0answers
45 views

What is “the modifiers data structure” [closed]

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 ...
-4
votes
0answers
24 views

C++ not running in VS code [closed]

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.
0
votes
0answers
21 views

How to close an open polygonal chain such that the resulting enclosed area includes polygon B and excludes polygon C?

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 ...
0
votes
0answers
27 views

How to close an open polygonal chain in clock- or counterclockwise direction?

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 ...
1
vote
2answers
46 views

Why is the time complexity of the Bit Manipulation solution to Binary Addition O(M + N)?

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 ...
0
votes
0answers
31 views

Fast text comparison algorithm for long texts

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 ...
0
votes
0answers
14 views

Voice activation keywords algorithms on iot devices?

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 ...
2
votes
1answer
19 views

Padding in proof of space hierarchy theorems

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)$...
3
votes
0answers
55 views

Is it possible to recover induction for nat from W-types?

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 ...
3
votes
0answers
107 views

Seemingly simple path finding problem, but graph with travelling salesman or shortest path does not work

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 ...
1
vote
1answer
33 views

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$ is True or False and explain

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 ...
2
votes
1answer
49 views

Is there a difference between extremely slow growing functions and constants with respect to computable functions?

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 ...
1
vote
1answer
30 views

Counting substrings of a string that do not contain a given string

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$ ...
1
vote
1answer
46 views

Lower bound on worst-case time complexity of all sorting algorithms neglecting reading input and accessing elements time

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 ...
1
vote
0answers
29 views

How to sample the most unique vectors from a very large set efficiently?

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 ...
1
vote
1answer
8 views

What if the samples in the dataset are fairly naturally similar to each other, would that be considered as data redundancy?

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 ...

15 30 50 per page