All Questions

Filter by
Sorted by
Tagged with
0
votes
0answers
4 views

Observations about the structure of an optimal BST

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 keys ...
0
votes
0answers
5 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
15 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
19 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
8 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
11 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 ...
0
votes
1answer
22 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
1answer
38 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
32 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 ...
0
votes
0answers
22 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 ...
2
votes
1answer
25 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
44 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
23 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
19 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
24 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
45 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
29 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
17 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
49 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 ...
2
votes
0answers
70 views

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

I deleted the crosspost in mathematics (see comments for explanation), can someone please reopen this question? I am looking for an algorithm to a problem that I encountered when working with 3D ...
1
vote
1answer
30 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
45 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
27 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
44 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
27 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
6 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 ...
0
votes
0answers
22 views

Deletion in B Trees

Given a B-Tree that contains the keys $k$ and $2k$, we know the height of the tree will be reduced if we delete the key $k$. Prove or disprove: The height of the tree will also reduce if we remove $2k$...
1
vote
0answers
21 views

Given a vertex in a digraph, is there a standard term for (the vertices reachable from it) union (the vertices reaching it)?

Question in title. Looking for whether there is a term that is, if not widely understood, at least citeable to a source. This is equivalent to asking for the set of nodes that are comparable to the ...
0
votes
0answers
13 views

Why can we apply standard matrix operations in data matrix but not in record data?

Tan,Steinbech,Kumar book says-: A data matrix is a variation of record data, but because it consists of numeric attributes,standard matrix operation can be applied to transform and manipulate the ...
0
votes
1answer
30 views

If in a given text the frequency of the letter A is 0.5, then the number of bits encoding in the Hoffman code for the text is 1

Studying for my finals. I saw the following question: Prove or disprove: If in a given text the frequency of the letter A is 0.5, then the number of bits encoding in the Hoffman code for the text is ...
1
vote
1answer
17 views

Runtime of enumerating all integer vectors with a given sum where every element is greater than sqrt(k)

The problem of enumerating all lists of integers such that the list sums to a known value $k$ is well known and takes exponential time to compute. If the problem is restricted so that the integers ...
1
vote
0answers
11 views

What do we mean by permissible transformations in types of attributes-:nominal,ordinal,interval,ratio? [closed]

I am studying data mining and I stumbled upon types of attributes. They are Nominal Ordinal Interval Ratio Data mining book by Tan,Steinbech,Kumar says Permissible transformations for-: nominal-:...
-4
votes
0answers
28 views

Add more button not working for my javascript code [closed]

the add more button is not working on my code attached is the code in JavaScript ...
4
votes
2answers
193 views

Why are Regular sets not closed under infinite unions and intersections? [duplicate]

Why are Regular sets not closed under infinite unions and intersections, with my flawled reasoning I came to a conclusion that since infinite unions can have no relationship between strings of a ...
0
votes
1answer
30 views

Which overhead is smaller - function call or passing variables between processes?

the question is related to networking frameworks; callback-based approach requires you to call a callback function every time you receive a new data packet; this is not a good approach for high-load ...
1
vote
1answer
52 views

What does an NP reduction look like?

From my theory of computation lecture I recall: If $A \le_m B$ and $B$ is decidable then $A$ is decidable (uses a computable function as a reduction). If $A \le_p B$ and $B$ is in P then $A$ is in P ...
1
vote
0answers
15 views

How to cover a surface with a predefined set of objects

I'm making a program that's supposed to be able to find pieces of wood in a dataset to cover a surface. For now I'm focusing on parallelepipedic shapes to simplify the problem (eventually I'd like it ...
2
votes
0answers
18 views

Necessary condition for 3-CNF unique satisfiability

I need to iterate through all formulas of 7 variables in 3-CNF which have unique satisfying assignment (1,1,1,1,1,1,1). I could iterate through all formulas which are true under that assignment -- ...
0
votes
2answers
48 views

A so-called random variable not being well-defined

Consider this algorithm: ...
-4
votes
0answers
54 views

Are approximations to $#P$ gibberish? [closed]

approximations to #P are gibberish the model count in satisfiability (#P) implies straightforward access to a vast empire inside the logic of truth including N Boolean variables in a formula with N ...
0
votes
2answers
42 views

Are this languages can be represented by regular expressions?

The set of all words with the same number of 0’s and 1’s. The set of all words contained in {0,1}* that have an even number of 0’s and an odd number of 1’s. I guess first one is NO. Second one seems ...
-1
votes
1answer
20 views

How do I solve regular expression expansion when I have “+” sign?

For example, I am given this and my output is: 11+11* = 11, 1, 11, 111, 1111, ...... Since + means or sign, my logic is: 11 appears once or more Then I work on solving 11* Is it perfect? Thanks.
0
votes
0answers
26 views

Is there a simple algorithm for generating unit tests given a function's code? [closed]

Given the abstract syntax tree (AST) of each line of a function's code, I am asked to generate code for that function's corresponding unit tests, similar to what Microsoft's IntelliTest tool does here:...
1
vote
0answers
22 views

Minimum unrooted binary spanning tree

Given a graph $G$ with $n$ tip vertices, $n-2$ internal vertices and a cost on each edge $C(v)$, find a minimum spanning tree subject to degree constraints: tips have degree $1$ internal vertices ...
0
votes
1answer
119 views

Four Queens Problem to a Conjunctive Normal Form

Given a chessboard with 4 rows and 4 columns (4x4) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Assign a Boolean variable to each cell of the board as below (1, 2, 3, etc. are variable names) If a ...
-1
votes
0answers
12 views

Finding the disagreement coefficient for certain hypothesis classes and distributions

I need help with the following question: First some definitions, Let $\cal X \subseteq \mathbb R^d$ be some example domain and let $\cal H$ be a hypothesis class on a distribution $\cal D_\cal X$ ...
0
votes
1answer
24 views

The same transition twice in Pushdown automata (PDA)

If we want to design a PDA that accepts all words those the first half equals reverse of the second half and there is a '#' between them, "ab#ba" for example. We start push each letter we ...
0
votes
1answer
27 views

Does finding a reversal of a regular expression by automata need automata to be a DFA?

If I want to find the reversal of a regular expression using an automata, Do I have to transform the automata to DFA if it wasn't ?
3
votes
2answers
44 views

Compact representation for quantified boolean formula

I got black-box (too big to analyze) boolean formula f(...) with 3 sets of input arguments: $x_1... x_i, y_1... y_j, z_1... z_k$. And I want to find such values for x-arguments that for every y-...

15 30 50 per page
1
2 3 4 5
830