All Questions

41,511 questions
Filter by
Sorted by
Tagged with
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$...
28 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 ...
16 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 ...
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 ...
19 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 ...
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-:...
31 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 ...
201 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 ...
34 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 ...
53 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 ...
20 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 ...
19 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 -- ...
49 views

A so-called random variable not being well-defined

Consider this algorithm: ...
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 ...
44 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 ...
21 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.
27 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:...
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 ...
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 ...
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$ ...
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 ...
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 ?
49 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-...
65 views

Solving an IMO problem Using Graph Theory

Here is a question from IMO 2021: Let $n>100$ be an integer. Ivan writes the numbers $n,n+ 1,\dots,2n$ each on different cards. He then shuffles these $n+ 1$ cards, and divides them into two piles....
45 views

30 views

Reduction from Edge-Coloring and Vertex-Coloring to a new problem

I have a question from a test I did and failed, a question I failed to do. In short: the question is about reduction from Vertex-coloring and Edge-coloring, to a new problem they have defined. The new ...
18 views

Data space progress - Compilers

Consider a programming language that supports (a) nested subroutine statements with static binding and (b) value-by-reference parameterization and by name, with corresponding keywords val, var and ...
58 views

Is the RecMII really important?

Recently I've asked a question on SO about dependence graph and modulo scheduling, because I'm not able to get the distance of some loop carried dependency and I needed some help. I'm building a ...
20 views

What happens at the receiver side in Pretty Good Privacy [closed]

Say Alice and Bob want to communicate. Alice-: PGP hashes the message using MD5. Encrypts hash using private RSA key of Alice(D_A) Encrypted hash and original message are concatenated. Compressed ...
60 views

A non-CFL over {a,b,c} with a non-CFL complement?

I understand uncountably many such languages exist, and the rational for it is clear to me. I just can't think of one trivial, easy to prove example. For instance, the complement of a^nb^nc^n is CF, ...
78 views

What makes a computer program modular?

Consider: Constants and variables If-then-else-elseif statements Procedures and loops The very fact that a program is comprised of two or more files (instead just from one large file) Each one of ...
24 views

Is computing subgradients an open research area in Authomatic Differentiation

Large portions of the possible research areas in Automatic Differentiation have broadly defined known solutions; most of which were derived in the 80s and 90s. Compute vector jacobian products: use ...
65 views

Which of the following languages can be represented by regular expressions?

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 came to discover that it is possible but not sure how. Can anyone express it in a regular ...
22 views

Prove mutual exclusion - Multiprogramming with arbitrary number of components

Given the following multiprogram with arbitrary number of components: ...
41 views

How to carry out expansion in regular expression problems like ((0*10)*)?

I have been given some problems like: Determine if each of the following strings belongs to the corresponding regular language. i. ‘10100010’ and L((0*10)*). iv. ‘011100101’ and L(01*10*(11*0)*) I ...
26 views

Sharing a requested secret number not knowing which

Alice has a list of secret numbers. Alice wants to give Bob the opportunity to choose one of her secret numbers, and then Alice has to share that specific secret number, but in such a way that Alice ...
20 views

In every DFS run on $G$, in every step of DFS, the $G_{\pi}$ is a forest

Studying for my finals. So I'm reading the "Introduction to Algorithms (Third Edition)" book. In the DFS section there is the following section: Depth-first search yields valuable ...
59 views

I have a question from a test that I failed to pass, I failed to do the question. The question: Let A and B have two languages so that there is a reduction function f: $A\leq _pB$. Suppose that $A \in ... 1answer 28 views Is doing BFS over transitive reduction of a directed acyclic graph equivalent to topological ordering of that graph? I have a directed acyclic graph. Where each node is a task and each edge denotes a dependency. I want a method to effectively parallelize these tasks. One way would be to topological sort them based ... 0answers 12 views Ratio of intra-class scatter by inter-class scatter is getting minimised by linear discrimination process I am optimising projection matrix P using Fisher linear discrimination formula maximise following with P J=N*tr(trnspse(P).SB.trnspse(SB).P) / c * tr(trnspose(P).SW.transpose(SW).P) As per theory, P ... 2answers 46 views Reduction between CLIQUE to SUBSET SUM I have a question from a test that I failed to pass, I failed to do the question. The question is about the reduction between Clique and Subset Sum. I tried to find an explanation for this on the ... 0answers 32 views Sum optimization and greedy approach I've came across the optimization bellow$\phi=argmin_{\theta} \displaystyle\sum_{i=1}^{N}f(x_i,\theta)$Can i say that minimizing this summation by minimizing each term$\left(\displaystyle\frac{df(...
If the complexity of my problem is $O(f_n(n))$ begins at $n =4$ and increases in this sequence: At $n = 4$ the number of operations = $(n - 2)$, $n = 5$ the number of operations = \$((n - 2) (n-2)(n-...