# All Questions

29,196 questions
6 views

### Renaming registers

I have this code ...
5 views

### What is the difference between equals () and == in Java?

Islamic pic of khana kaba (https://i.stack.imgur.com/PiiMS.jpg)
3 views

### Computing Nash equilibria in discrete auctions

I am trying to compute the (pure strategy) Nash equilibria of some discrete auctions. More precisely, let us define the strategy of each player as a function mapping from every valuation that they ...
4 views

### Difference between present - absent bit and valid - invalid bit in a page table?

while reading I found this: Present/Absent bit – Present or absent bit says whether a particular page you are looking for is present or absent. In case if it is not present, that is called Page ...
9 views

### Length of shortest codeword in Huffman encoding

Under Huffman Encoding, if one character occurs more than 1/3rd of the time, is it guaranteed that there will be at least one character whose codeword is of length 1? I thought of 2 cases where this ...
19 views

32 views

### What is the time complexity of the below algorithm?

Below I have two algorithms for finding the maximum 2 numbers from an array of numbers of size>=2. n=Size of the array Algorithm 1:- 1. Loop through the array, find the index of max number. (n ...
27 views

### What are expanding opcodes? What are they good for? What would be a simple example?

I really am in need of some thorough explanation here. A little bit simpler and more understandable than in the textbooks or youtube slides lectures. Turned out to be slightly more complicated to ...
27 views

### Does a Turing complete set of invertible combinators exist?

We'll say that a combinator A is invertible if there exists A' s.t. A'(Ax) = A(A'x) = x For example, Sxyz = xz(yz) is clearly invertible in this sense because we ...
16 views

### Computing a shortest $M$-alternating walk (for the Blossom algorithm)

When explaining the Blossom algorithm for maximum (nonbipartite) matchings, Shrijver describes, given a simple graph $G = (V,E)$, a matching $M \subseteq E$, and the set $X \subseteq V$ of nodes ...
27 views

### Is this problem hard? Finding all the subsets of size k from a sequence of n numbers

I want to know the hardness of finding all subsets of size k from a sequence of n numbers. There is an algorithm based on recursion: Print all possible combinations of r elements in a given array of ...
13 views

### What year exactly did Dijkstra distribute EWD682?

The Dijkstra's archive says EWD682 was written or distributed between 1976--1979. I wonder if you can tell the exact year. It might not be easy since the archive itself didn't make it.
11 views

### How could the Cuckoo Search be implemented into Python? (Presumably a solver) [on hold]

I was looking to do this for just a fun project, and maybe mine some GRIN coin.The proof-of-work for GRIN is the cuck(ar)oo29 algorithm, with 29 nodes in each graph. There is also an ASIC chain, for ...
51 views

### What are the axioms of automata theory?

Every theory has axioms and theorems derived from axioms. How many axioms are there for automata theory? What are the axioms of automata theory?
41 views

### Small space hash functions that are weakly but not strongly universal

This is a follow up to this this question about weakly universal hash functions A family of hash functions $H_w$ is said to be weakly universal if for all $x \ne y$ : P_{h \in H_w}(h(x) = h(y)) \...
27 views

### Minimum Spanning Tree with one particular edge minimised(continued)

I have recently encountered a coding problem, specifically, the CCC problem S4. In the problem, it states that you are given a spanning tree, or otherwise a "valid plan of pipes", that connect each ...
36 views

### Mildly context-sensitive grammar

Consider a context-sensitive grammar $G$, such that all the productions of $G$ have the form $A\to \alpha$ or $Ab \to \alpha b$ (in other words, the left context is always empty and the right context ...
16 views

### Converting CFG from GNF to CNF

I am working with grammars that need to be in Greibach Normal Form. I want to check whether a grammar recognises a string. In order to perform CYK the grammar would have to be converted into CNF. Is ...