# All Questions

41,423 questions
Filter by
Sorted by
Tagged with
14 views

### A so-called random variable not being well-defined

Consider this algorithm: ...
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 ...
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 ...
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.
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:...
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 ...
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 ...
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$ ...
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 ...
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 ?
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-...
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....
34 views

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 ...
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 ...
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 ...
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 ...
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, ...
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??
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 ...
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 ...
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 ...
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 ...
21 views

### Prove mutual exclusion - Multiprogramming with arbitrary number of components

Given the following multiprogram with arbitrary number of components: ...
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 ...
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 ...
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 ...
58 views

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

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