All Questions

Filter by
Sorted by
Tagged with
0
votes
2answers
14 views

A so-called random variable not being well-defined

Consider this algorithm: ...
-1
votes
0answers
14 views

Are approximations to $#P$ gibberish?

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

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

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

Conjunctive Normal Form n queen

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 ...
0
votes
0answers
8 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
21 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
21 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
1answer
22 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-...
0
votes
0answers
51 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....
0
votes
1answer
34 views

How to determine whether this language is regular?

I've encountered this question recently: Given $\Sigma=\{\sigma_1, \sigma_2, ..., \sigma_n\}$ and $n\ge 2$, determine whether the following language is regular or not: $$ L_1=\{w\in\Sigma^*|for \ 1 \...
0
votes
1answer
23 views

Is it possible to use a quantum computer simulation to perform a cyber attack?

Is it possible to use a quantum computer and or a simulation to perform a cyber attack on classic computers? This is part of a research objective I'm trying to figure out.
1
vote
0answers
16 views

How does AH header in IPSec prevents replay attacks?

According to Tanenbaum's Modern operating systems, The purpose of this field is to detect replay attacks. These sequence numbers may not wrap around. If all $2^{32}$ are exhausted, a new security ...
0
votes
0answers
16 views

what is the formula used in the scale_quantile function in R?

I want to know what formula is being is in the package scale_quantile by the dynutils package. I want to check if I can achieve the same results as with manual calculations like this ...
1
vote
3answers
38 views

A beginner book on algorithms

I am a tenth grader. I currently learnt about sorting algorithms in java in school. I started with the book "Algorithmic Mathematics" so as learn about algorithms mathematically. I know very ...
3
votes
1answer
634 views

What this algorithm is computing and how to prove it?

On Hackerrank I have found a test that is asking to check what the following algorithm computes: If $x > y$ then $x = x - y$ If $y > x$ then $y = y - x$ If $x \neq y$ then goto 1 Print $x$ ...
0
votes
1answer
56 views

Can't understand the $O$ notation for runtime of algorithms

In my book,the $O$-notation is given as: $$O(g)=\{f:\mathbb N\rightarrow \mathbb R_{\geq 0}:\exists \alpha\in \mathbb R_{>0},\exists n_0 \in \mathbb N : \forall n\geq n_0 f(n)\leq \alpha g(n)\}$$ ...
3
votes
0answers
27 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 ...
0
votes
0answers
16 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 ...
1
vote
0answers
21 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 ...
0
votes
0answers
18 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 ...
1
vote
3answers
55 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, ...
-2
votes
0answers
23 views

PYTHON RUNNING ERRORS [closed]

I AM NEW TO PYTHON BUT I HAVE STARTED TO GRASP SOME THINGS SO I DECIDED TO MAKE A PYTHON GAME. BUT AFTER RUNNING MY CODE IT TELLS ME render mode:default no settings.py file. WAT CUD BE THE PROBLEM??
2
votes
2answers
58 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 ...
-4
votes
0answers
17 views

Decision Making Algorithm [closed]

can someone help design a simple algorithm for a task's success, it outputs green if the failure percentage is less than 5%, orange if Its greater than 5% and less than 30 and red if its greater than ...
2
votes
0answers
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 ...
0
votes
1answer
58 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 ...
-1
votes
0answers
21 views

Prove mutual exclusion - Multiprogramming with arbitrary number of components

Given the following multiprogram with arbitrary number of components: ...
0
votes
0answers
40 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 ...
0
votes
1answer
24 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 ...
1
vote
1answer
18 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 ...
0
votes
1answer
58 views

Reduction from problem A to another problem B

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

Number of pixels on an object and minimum size to identify an object [closed]

I want to find out how many pixels will cover a specific object in an image at a set distance. My plan is to use the known objects height and distance to calculate the angle it subtends from the ...
1
vote
1answer
26 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 ...
0
votes
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 ...
1
vote
2answers
44 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 ...
0
votes
0answers
31 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(...
-1
votes
0answers
22 views

What is the right conclusion?

This sentence is (1) correctly expresses the English sentence; (2) is syntactically invalid and therefore meaningless; or (3) is syntactically valid but does not express the meaning of the English ...
1
vote
2answers
112 views

Need the type of time complexity and its formula

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

A confidence interval algorithm for Disagreement coefficient

My question has to do with the disagreement coefficient in active learning. I've been trying to solve the following question, where I need an algorithm to derive a confidence interval for $\theta$, ...
-4
votes
3answers
71 views

What is wrong with this argument that if A is NP Complete, but B is in P, then A\B is NP Complete and B\A is NP Complete as well?

The following seems to me to be relevant to this question, but to me is an interesting exercise, especially since I have not formally worked with complexity before, but I want to learn more: Suppose ...
0
votes
0answers
28 views

Reduction from IS problem to other problem [closed]

Given graph 𝐺 = (𝑉, 𝐸) it is said that it is a star if there is a vertex $𝑣_0 ∈ 𝑉$ so that all the other vertices are connected exclusively to it (and not to ...
-1
votes
0answers
13 views

trying to solve linear equetion system above %Z11

give this system linear above Z11 10=(3a^2-b)x-2y by=2 find all the solutions to the linear system I am tried to figure out how to solve something like that. I know how to solve a linear equation and ...
-2
votes
2answers
42 views

How to solve modulo math equation in RSA algorithm?

$(3 \cdot d) \mod 8=1$. I know the answer is $d=3$ by common sense. But what is the mathematical approach to solve this problem? How do I solve this mathematically? How do we get this value of 125^107 ...
0
votes
1answer
35 views

Proving upper/lower bound

$f (n) = Θ(f (n/2))$ The counter example in the solutions was $f(n)=\sqrt{n}$. But then we get for every $n\ge n_{0}$ $\sqrt{n}\le c_{0}\sqrt{\frac{n}{2}}\ \ ->\ \ n\le c_{0}^{2}\cdot\frac{n}{2}\ \...
-4
votes
0answers
22 views

Articulation vertices main method modification [closed]

I have written the code to get the number of articulation vertices and it works perfectly fine in cases where input is of the form num of vertices is the First line num of edges is the Second line ...
0
votes
1answer
45 views

What will you do if multiple users access your application at the same time?

I'm an experienced Software Engineer but very weak in concurrency because of no prior experience in that. I've been interviewing with several companies in which I was asked similar kinds of questions ...
1
vote
0answers
34 views

Finding the optimal combination of matrices to multiply that maximise the result when multiplied

I have a 100000×60000 matrix where each element is either a 1 or 0. A 1 represents a signal to do something whereas 0 means to do nothing. Each column represents a different strategy (where strategies ...

15 30 50 per page
1
2 3 4 5
829