# All Questions

29,234 questions
7 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 ...
31 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 ...
30 views

33 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 ...
28 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 ...
29 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 ...
17 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 ...
28 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?
44 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 ...
42 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 ...
18 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 ...
28 views

### Recursively edit 2-D array using backtracking

I have a 2-D array which contain 3 types of elements: C (Contaminant) R (Rock) W (Water) The rule is that: contaminant can seep through water but not through rocks. Let's say I have the ...
24 views

### Relative efficiency of n tasks in 1 loop vs. 1 task each in n loops?

Say I have 3 simple tasks, to find the min, the max, and the average of an array of numbers. A modular approach would be to write one function for each, thus iterating over the array thrice. However, ...
40 views

### Minimum spanning tree such that one edge can be minimised

During a computer coding exam, I have encountered such a problem. Given a list of vertexes and edges between the vertexes,and a positive number, D, what is the minimum spanning tree between the ...
I try to make an animation of plot in Matlab using vector $X$, vector $Y$ and given time vector $T$. There are several examples related to animation and plot with random time and with 'pause(t)'. It ...