Blockchain cipher suitable for preschoolers Is there a cipher that well suited for preschool-aged children to work out on pencil and paper, to learn concepts of block chains?

It must have the following requirements:

Able to be easily verified
a. For example, Joe submitted red, but Suzy submitted blue. Everyone knows Suzy is right...somehow. (Color-specific results are not required but used to illustrate that the cipher need not be number-based, although that is fine too)
Able to be easily ciphered with pencil and paper, or drawings, or in a child's head
Able to use a previous result (minus the genesis of course), to create a 'blockchain' of sorts

The cipher may be low-complexity. It does not matter if it is easily broken.

Most ciphers are geared towards being easy to verify, but difficult to decipher. This situation is a bit different in that it does not have to be difficult to decipher. Out of the box ideas are quite welcome.

I'd suggest you don't try to create or use a cipher.  Rather, I think maybe a more interesting way to view blockchain systems is as a log that is created through a distributed lottery.

So, in lesson one, you could describe how to keep track of something (account balances?  something more relevant?) via a sequence of log entries written on the board.  This would be a centralized scheme.

In lesson two, you can make it distributed.  In each stage, have a lottery where you randomly pick one of the students to win the lottery.  The winner of the lottery gets to write down the next log entry on the board.  Everyone else watching can see whether that student did it correctly and fairly.  If not, the next winner ignores the bogus stuff written on the board.

No cryptography is needed.  You just need a way to randomly pick one student in the room, in a fair way.  This could be done with numbered balls in a box, or any number of other ways.


Using Huffman Encoding to improve Lempel-Ziv Encoding Can anyone think of a way to use Huffman Encoding to improve the compression rate of Lempel-Ziv Encoding?

My initial idea was to encode with higher probabilities given to shorter strings (i.e. the string "e" would have a higher probability than the string "ef").

Does anyone know of a good way?

Huffman encoding is already used this way.

Huffman encoding is already used together with LZ77 to improve its compression rate.  The most widely used instance of LZ77-style compression is DEFLATE.  DEFLATE combines LZ77 with Huffman encoding.  See https://en.wikipedia.org/wiki/LZ77_and_LZ78#Implementations and
https://en.wikipedia.org/wiki/DEFLATE.

Huffman encoding is commonly used together with standard LZW (Lempel-Ziv-Welch) encoders to improve their compression rate.  See the Wikipedia article on LZW and other standard resources on LZW coding for details: https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch


Sorting an already k-sorted array Can anybody give me some hint on how to do this? I'm not really sure where to start. The problem says:

  We say that an array $A[1...n]$ is $k$-sorted if it can be divided
  into $k$ blocks, each of size $n/k$, such that the elements in each
  block are larger than the elements in earlier blocks, and smaller than the elements in later
  blocks. The elements within each block need not to be sorted. For
  example, the following array is 4-sorted: $$1,2,4,3 | 7, 6, 5 | 10,11, 9, 12 | 15, 13, 16, 14$$

  a) Describe an algorithm that $k$-sorts an arbitrary array in time
  $O(n\log k)$.

  b) Prove that any comparison-based $k$-sorting algorithm requires
  $\Omega(n \log k)$ comparisons in the worst case.

  c) Describe an algorithm that completely sorts an already $k$-sorted
  array in time $O(n \log(n/k))$.

Googling I found this paper with the solution of of a) and b), but I still don't fully understand how to solve this.

For a) my teacher said that we need to find the median and then do something like what quicksort does on finding a good pivot. I was searching over the net and I had the idea to put the $k$ first elements as leafs of a min-heap and then take the min element and with the next element of the array fill each block with $n/k$ elements, but it fails with the input: $8, 7, 6, 5, 4, 3, 2, 1$

Clearly, b) is something like proving that any algorithm based in comparisons takes $O(n\log n)$. Maybe $\log k$ is because we only need to sort each block with $n/k$ elements, that means for each block we need to do $O(n/k \times\log k)$ $k$ times, so we could actually do it in time
 $O(k\times n/k \times \log k) = O(n\log k)$

For c) I'm not really sure, but I can take all the elements of each block and put them as leafs of a min-heap $-$ which gives $O(\log n/k)$ $-$ and then sort them, which I think would take $O(n \log n/k)$.

Thanks in advance.

You have the right idea but I think you are overthinking it a bit.

For a), your teacher had a good hint.   I think there is a simpler solution than the way you are going. As a further hint, notice that if $k=2$, the problem is solved after 1 round of quicksort (with linear median-finding).  You have two equal-sized subarrays, where the left is smaller than the right.  Can you extend this to $k=4$?  Then, can you extend it to arbitary $k$?

b) I think you have the right intuition, but this argument is not formal yet.  Recall the original proof of the sorting lower bound, where you argue that you need $n\log n$ comparisons to get  $n!$ permutations.  Can you extend that to this case?  How many permutations are required when we don't need to fully sort?


Counting the number of N-dimensional coprime integer vectors I am looking for an efficient way to count the number of coprime vectors in a finite and bounded set of integer vectors.

The vectors in my set are $N$-dimensional integer vectors whose components are bounded on the top and bottom by an arbitrary value $K$. Let $x = [x_1,x_2,\ldots,x_N]$ denote a vector from this set. Then $x$ is coprime if the greatest common denominator of all its elements is 1. That is, $\gcd(x_1,x_2,...,x_N)=1$.

Some 3-dimensional coprime vectors include: $x = [1,2, 3] , [6, 10, 15] ,[0, 1, 1]$
Some 3-dimensional non-coprime vectors include: $x = [2,4,6] ,[0, 10, 15] ,[0, 12, 12]$

For fixed $N$ and $K$, my set contains a total of $(2K+1)^N$ distinct integer vectors as each of the $N$ elements can take on integer values from $-K,\ldots,0,\ldots,K$.
A brute-force approach for counting the number of coprime vectors consists of iterating over each of the $(2K+1)^N$ possible vectors and checking to see whether they are coprime (using, for instance, this function). Unfortunately, this approach quickly runs into time and memory issues for large values of $N$ and $K$.

I am wondering if anyone can think of a way to smart algorithm to do this. Ideally, I am looking to implement this algorithm as a MATLAB function that can number of coprime pairs given $N$ and $K$ as its input.

For $N=2$, the problem is easy: count the number of non-coprime pairs, by expressing it as a union over all possible values for their common divisor.  In particular, a pair $(x_1,x_2)$ is not coprime if there exists a $d>1$ such that $d|x_1$ and $d|x_2$; for fixed $d$, it's easy to count the number of such pairs, so now just sum over all possible values of $d$.

For $N=3$, you could try using the following characterization:

$\gcd(x_1,x_2,x_3)=1$ iff either (a) $\gcd(x_1,x_2)=1$, or (b) $\gcd(x_1,x_2)>1$ (so define $d=\gcd(x_1,x_2)$) and $\gcd(d,x_3)=1$.

These two conditions are mutually exclusive, so you can count the number of type-(a) triples and the number of type-(b) triples and then sum those two numbers, to get the number of co-prime triples.

You can count the number of triples of type-(a) quickly (by reducing to the $N=2$ case).  You can also count the number of triples of type-(b) quickly, by summing over all possible values of $d$ (for fixed $d$, the number of type-(b) tuples with a particular value of $d$ reduces to a smaller version of your problem with $N=2$ and a smaller value of $K$).

I think you can probably see how to generalize this to larger $N$, giving you a recursive algorithm to solve your problem for general $N$.  I'll let you work out the details.


TSP problem with a benchmark data I've got a test Travel Salesman Problem's data with known optimal solutions. It's in a form of set of 2D points. Particularly, this is a tsplib format; sources are here and here.

I'd started a simple test with the "Western Sahara - 29 Cities" (wi29) and found that my algorithm rapidly found a few better particular solutions than the proposed optimum.

I checked one of them manually and didn't find an error. So, I guess, here're the three options.

I did a mistake.
Wrong optimum.
Different problems were solved.

1 and 2. My solution tour is:

  17>18>19>15>22>23>21>29>28>26>20>25>27>
  24>16>14>13>9>7>3>4>8>12>10>11>6>2>1>5

(will list my checking calculations if requested)

Rounded length: 26040.76.
Optimal reference value: 27603.

I can't find a particular task descriptions and especially rounding policy for the TSPLib examples optimums. This is important, because they're looking rounded or discretized in another manner, but simple result rounding isn't looks like it.

In the TSPLIB norm, the travel cost between each pair of cities is the Euclidean distance between the points rounded to the nearest integer (not the distance rounded to two decimal places).


context sensitive language finite or infinite let L be a CSL. (my understanding/ memory/ expectation is) the problem

  is L finite or infinite?

is undecidable.

where was this 1st proved/ published?
are there any cases in the literature of analyzing a CSL L in some "limited context" and determining whether it is finite or infinite? (also wondering about machine learning contexts.)

(brief background: the question can arise in analysis/ application of automated theorem proving. one might reduce a theorem "there exist an infinite x" to a CSL L which enumerates x and the question of whether L is finite or infinite.)

It's a standard theorem that it's undecidable whether a given context-sensitive grammar generates the empty language or not.

From this, we can prove that it's undecidable whether a context-sensitive grammar is finite or infinite.  Let $L$ be a context-sensitive language.  By the standard closure properties for CSL's, if $L$ is context-sensitive, then so is $L^+$.  Now if $L$ is empty, then $L^+$ is empty (and thus finite); but if $L$ is non-empty, then $L^+$ is infinite.  Consequently, if it were decidable to check whether a CSL is finite or infinite, we could apply that decider to $L^+$ and learn whether $L$ was empty or not -- but the theorem mentioned above implies this is impossible.

Therefore, determining whether a given context-sensitive grammar generates a finite or infinite language is undecidable.

Footnote: You can find a proof of the standard theorem above in many places; e.g., these lecture notes from CS 373 at U Illinois.  The result is also mentioned in passing on Wikipedia, which cites Hopcroft and Ullman -- a standard resource on formal languages.  The same Wikipedia article also mentions some smaller classes of languages that are contained in CSL.


Show that the Language is irregular I was solving some problem from past test, there was this question:
Use the closure property of regular language to show the language $L$ is not regular
$$L =\{ a^3 b^n c^{n-3}  \mid  n>3\} $$
I know how to solve it using Pumping Lemma, but how to solve it with closure property?
Also, I know that to prove that a language L is not regular using closure properties, the technique is to combine L with regular languages by operations that preserve regularity in order to obtain a language known to be not regular, but I can't figure out with whom to combine.
I saw some similar questions but didn't get ideas about how to do this one.
Any hints?
Thanks.

Suppose that $L$ is regular. Then so is $L' = L \circ \{ccc\} = \{a^3 b^n c^n \mid n \ge 3\}$. This implies that $L'' = (aaa)^{-1}L' = \{b^n c^n \mid n \ge 3\}$ is also regular and, in turn, that $L''' = L'' \cup \{\varepsilon, bc, bbcc\} = \{b^n c^n \mid n \in \mathbb{N}\}$ is regular. This is a contradiction since $L'''$ is known not to be regular.


When is a problem strongly NP-complete Let the problem of the diophantic equation 0/1 be as follows.

Input : A polynomial equation on n variables whose coefficients are integers (ex : $2x^3_1 x_2 + x_1x^3_3 - 3x_4 = 8$)

Question: Does this equation have a solution in space {0,1}$^n$ ? (can we satisfy the equation by choosing for each variable the value 0 or 1?)

1 - How to prove that this diophantine equation 0/1 is NP-complete?

2 - How to prove that this diophantine equation 0/1 is Strongly NP-complete (ie its restriction to the case where all the coefficients are bounded by a polynomial of the number of variables is already NP-complete)

This problem is strongly NP-complete; it is straightforward to reduce 3SAT to this problem.

The clause $C = (x_1 \lor \neg x_2 \lor x_3)$ can be encoded as the polynomial $p(x_1,x_2,x_3,\dots) = [(1-x_1)x_2(1-x_3)]^2$.  The conjunction of clauses $\varphi = C_1 \land \dots \land C_m$ can be encoded as $q(x_1,\dots,x_n) = p_1(x_1,\dots,x_n) \cdots p_m(x_1,\dots,x_n)$, where $p_i(x_1,\dots,x_n)$ is the encoding of clause $C_i$.  Then, the polynomial $q(x_1,\dots,x_n)$ has a solution in $\{0,1\}^n$ if and only if the original formula $\varphi$ is satisfiable.


Generate collision resistant identifiers with two-way hashing Objective: We want to generate a unique and reproducible identifier for a given slice of bytes and avoid collisions.

High-level idea: Compute $$fK := hash(k_1)\; and\; sK := hash(k_1^{-1})\; where\; k_i^{-1}\; is\; the\; reversed\; bitstring\; k_i$$

We then proceed to set, our identifier to be: $$<value\_of\_fK>\_<value\_of\_sK>$$

Assumption:

For two keys $$k_1\; and\; k_2,\; if\; hash(k_1) = hash(k_2)\; and\; hash(k_1^{-1}) = hashs(k_2^{-1})\; then\; k_1 = k_2$$

where our hash function is FNV1a.

Hypothesis: For any given input bitstring, we will have a unique identifier and no collisions.

I would like to have your input on this

Your assumption is probably false. It can only be true if the size of the hash is at least half the size of the key.

If you want to generate an absolutely unique identifier, why not use the key itself? Another option, if you want an alphanumeric identifier, is to use Base64 (which also uses a few punctuation marks).

If you just want a practically unique identifier, you can just use a hash function – any industry-standard one would do. That's exactly their goal. Since it doesn't seem you care about cryptographic security, you can just use MD5 or SHA1.


What parts of a programming language can't be defined using Regular Expressions? I'm trying to understand how the syntax of some programming language is defined.

I know that there are some parts of the syntax of programming languages that can't be defined using regular expressions (such as an equal number of opening and closing braces) and that this is why context-free languages like BNF are needed.

What I'm struggling to understand is how one can tell which parts of the syntax of a language can only be defined using BNF and which parts could also be defined by a regular expression.

At the moment I think only BNF productions that are recursively defined can't be written as a regular expression. For example I think the following BNF can't be written as a regular expression:

<variable> ::= <letter> | <variable> <letter> | <variable> <digit>

But I think this BNF can be defined using a regular expression:

<digit> ::= 0|1|2|3|4|5|6|7|8|9

My problem with this is that I think I can write a regular expression for a recursive BNF production like this:

<word> ::= <letter> | <word> <letter>

<letter> ::= A|B|...|Z

(I'm assuming a letter is a character A-Z)

I would be greatly appreciative if someone could clarify how this works for me.

Grammars and regular expressions are both ways to describe a language. Grammars are far more powerful. Context-free grammars are restricted grammars, with less power; regular grammars are further restricted context-free grammars, with less power again.

Regular grammars can describe exactly all regular languages, that is, all languages that can be described by regular expressions.

(Side note: this is only true for the regular expressions taught in computer science, which only use concatenation, union and Kleene star. In programming practice, extended types of regular expressions tend to be used with much more power.)

Regular grammars can be recursive, but only in a very restricted way:

each right hand side of a rule has at most one nonterminal
that nonterminal is either always at the end of a rule (for right-regular grammars) or always at the start (for left-regular grammars)

In your example:

<variable> ::= <letter> | <variable> <letter> | <variable> <digit>
<letter> ::= a | b | c | ...
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

the first rule isn't regular, but it only contains one recursive nonterminal: <letter> and <digit> both generate a finite set of strings. Hence, we can expand them into the rule to yield the equivalent set of rules

<variable> ::= A | B | ... |
               <variable> A | <variable> B | ... |
               <variable> 0 | <variable> 1 | ...

which is (left-)regular.

Hence, a regular expression for <variable> exists:

(a | b | c | ...)(a | b | c | ... | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9)$^*$

There are, in fact, straightforward algorithms for converting regular expressions to regular grammars and vice versa.

So context-free grammars can only generate non-regular languages by containing either right-hand sides with material on both sides of a nonterminal, for instance,

 <block> :== { <statements> }

or rules with multiple "recursive" nonterminals (i.e. of which more than one generates an infinite language).

If they do contain such rules, the language described may still be regular, and it can be really hard to figure out whether it is (it is undecidable).

However, we weren't looking at a grammar and trying to see whether it describes a regular language; we were looking at a language and trying to see whether it is regular.

A general rule I think you may find most useful in practice is to determine whether you can decide whether an utterance (in the case of a programming language: a program) belongs to the language by scanning it from left to right while never remembering more than a constant amount of information.  The syntax is regular if and only if you can do this.

In practice, you usually see two forms of recursion in languages:

a construct may contain another construct repeated an arbitrary number of times: this is regular;
a construct may contain occurrences of itself nested (that is, with some form of brackets to indicate the nesting) arbitrarily deeply: this is not regular, but context-free.

To take C as an example:

a block opens with a { character, followed by arbitrarily many (possibly empty) statements, separated by ;, and ends with }: this is regular, except that
a statement may itself be a block; thus, blocks can be nested inside blocks arbitrarily deeply: this is not regular.

JSON isn't a regular language for the same reason.

It isn't regular because the { and } brackets must match up, and while scanning from left to right, it isn't possible to determine this unless you somehow keep track of how many more { brackets you've seen than } brackets, and this count can be arbitrarily high: no constant amount of information can contain it.

Granted, in practice, you will rarely see C programs or JSON structures with blocks nested more deeply than, say, MAXINT times; but in theory, you may, which makes C syntax and JSON syntax non-regular.

I hope this gives you some intuition on how to distinguish regular from non-regular context-free languages in practice. It must be added that many requirements on the syntax of programming languages aren't even context-free: for instance, requiring variables to be defined before they are used is not.


K String Turing machine Given any $k$-string Turing machine $M$ operating within time $f(n)$, we can construct a single-string Turing machine $M$ operating within time $O(f(n)^2)$ such that for any input $x$, $M(x)=M(x)$

How can we prove that converse is false?

Just take $k=1$ and use the time hierarchy theorem.


Prove that this language is decidable or undecidable Is the following language decidable?

L = {(M) : M performs at least 100 steps on every accepted input.}

I tried to use reduction from the halting problem, but still no dice.

Yes, it is decidable.  There is a limited amount of input that any Turing machine could look at in ≤ 100 steps, so you can test a simulation of any given machine $M$ against all of those possibilities.


Why is a deterministic Turing machine a special case of a probabilistic Turing machine? I have no formal training in computer science as I have not yet taken any such classes, so perhaps this question appears naive.  I was reading about BPP and it was claimed that a deterministic Turing machine is a special case of a probabilistic Turing machine.  I don't understand why this is.

Probabilistic Turing machines are similar to deterministic Turing machines, but have the additional power of tossing coins. If you never make use of this power, you get a deterministic Turing machine.

In a similar fashion, a non-deterministic Turing machine is allowed to make guesses, but if it doesn't it is just a deterministic Turing machine.


Python versus Matlab on the quantity 1/0 Python and Matlab seem to disagree on the division by 0.
Python:
>>> 1 / 0
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ZeroDivisionError: division by zero

Matlab:
>>> 1 / 0
Inf

with the usual properties of $\infty$ for Inf.
Which one is correct when it comes to the IEEE double-precision format?

In the copy that I have of IEEE 754 (2008) it says

7.3 Division by zero 7.3.0
The divideByZero exception shall be signaled if and only if an exact infinite result is defined for an operation on finite operands. The default result of divideByZero shall be an ∞ correctly signed according to the operation:
― For division, when the divisor is zero and the dividend is a finite non-zero number, the sign of the infinity is the exclusive OR of the operands’ signs (see 6.3).
― For logB(0) when logBFormat is a floating-point format, the sign of the infinity is minus (−∞).

Python is choosing that the exception that the standard requires is a Python exception. My own interpretation is that this agrees with section 7.3. We don't get the value float('inf') because the exception interrupts the execution. I personally find it a bit inconvenient. I don't know the reasons they had for this choice.
One can get the behavior of obtaining a value by using numpy. With
x = numpy.float64(1.0)/numpy.float64(0.0)

we get
x = numpy.float64('inf')

and a RuntimeWarning. Alternatively, one can capture the exception ZeroDivisionError and produce the result float('inf') ourselves.
In Matlab we get inf as the result. It agrees with the standard because I think there is a warning (a flag) that can be seen by setting warning on MATLAB:divideByZero.


Permutations in an k-sorted array Definition of $k$-sorted array: An array in which an element is at-most $k$ places away from its sorted order.

I have a question in my Algorithms assignment which asks to prove the lower bound to sort a $k$-sorted array as $\Omega(n\log{k})$. I was trying to approach this question by using the standard comparison sort proof ($\Omega(n!)$), where we have $n!$ total permutations of the sequence [$a_1,a_2,\cdots,a_n$]. My friend told me that there are $k^{(n-k)}k!$ permutations of a $k$-sorted array. I'm finding it difficult to prove the same. How should I go about finding the total permutations of a $k$-sorted array?

Try for $n=5$, $k=2$.

Total permutation is $3\times 3\times 3\times 2\times 1$,
First element has 3 possibilities $\{1,2,3\}$; second has 4 possibilities $\{1,2,3,4\}$, but one position is already taken by the first,so effectively it has $(4-1)$ slots; third has 5 possibilities $\{1,2,3,4,5\}$, but first and second are there in one of these two, hence 3 possibilities; Fouth one has 4 slots $\{2,3,4,5\}$ and 3 of them are taken? (doubt: because 1st position can also be occupied) , hence 2 , and the last has one.

Let $N(n,k)$ be the number of $k$-sorted arrays on $n$ elements. At each position we have at most $(2k+1)$ possible elements, giving an upper bound of $(2k+1)^n$. On the other hand, suppose that we divide $\{1,\ldots,n\}$ into $n/k$ blocks of size $k$ (assuming for simplicity that $k$ divides $n$), and apply an arbitrary permutation on each block. All of these arrays are $k$-sorted, showing that $N(n,k) \geq k!^{n/k}$. In total,
$$
k!^{n/k} \leq N(n,k) \leq (2k+1)^n \\
\frac{n}{k} (k \log k - k + O(\log k)) \leq \log N(n,k) \leq n \log(2k+1)
$$
We conclude that $\log N(n,k) = \Theta(n \log k)$.

For the exact expression, consult a paper of Kløve or the OEIS.


#perfectMatchings is self-reducible How can one show that the counting problem:
Given a  graph, output the number of perfect matchings
Is self reducible?
I found a hint in Moore's Chapter on Counting, Sampling and Statistical Physics:

Let G be a graph and e one of its edges. Show that we can modify G to
produce two graphs, G0 and G1, such that the number of perfect matchings
of G that include and exclude e is the number of perfect matchings of
G1 and G0 respectively.

But I could not come up with a proof. The main question here is: How can we proof self-reducability of #perfectMatchings?
Aside: I don't know of a formal definition of self-reduciability. I just know the intuitive phrasing "partially solving the problem results in a smaller problem of the same kind". But is there a formal definition?

To count all perfect matchings containing an edge $e = (x,y)$, simply remove both endpoints $x,y$. To count all perfect matching not containing the edge $e$, simply remove the edge.


Context free grammar to Chomsky's normal form \begin{align*}
S&\to AACD\\
A&\to aAb\\
C&\to aC\mid a\\
D&\to aDa\mid bdb\mid\varepsilon
\end{align*}

I think that this grammar is infinite so it is not possible to convert it into cnf. Am I correct ?

Every context-free grammar can be converted to Chomsky normal form. Also, note that grammars are by definition finite: a grammar might describe infinitely many strings, but the grammar itself is finite.


Minimum weight triangulation I'm just curious about the pseudocode (or real source code, doesn't matter) of the recursive version of this algorithm. In almost every book chapter/paper when describing this topic, they mention that the recursive version takes exponential time and then they give the code for the dynamic programming approach. I understand how the iterative version (dynamic programming ie. memoization) works. But i just wonder about the recursive version.
For the info, the key part in the iterative code is:

  $\ell$ ... left
  $r$ ... right
  $a$ ... apex
  $T$ ... triangulation

  $T_{\ell,r}= \min\{T_{\ell,a} + \text{perimeter}_{\ell,a,r} + T_{a,r}\}$

So how does the recursive function findOT() seem in
pseudocode or one of these languages (C#, Java, C/C++, PHP, Javascript, SML)?

It's really hard to say, what kind recursion you mean. There are different variants I can think of. For what you have written, I guess it is something like this.

function findOT(int l,r)

if ((r-l)==2) return perimeter(l,l+1,r)

min= infinity
for a=(l+1)..(r-1)
    T=findOT(l,a)+perimeter(l,a,r)+findOT(a,r)
    if T<min then min=T
    endfor
return(min)


Why c_f (u, v) = f (v, u) if f (v, u) not in E? From page8 of the slide, I think $E$ is all the edges in the graph $G$. But why is $c_f (u, v) = f (v, u)$ if $f (v, u)$ is not in $E$? Why do we care about edge that is not in $E$?

There is a significant typo on that slide.

"$c_f (u, v) = f (v, u)$ if $f (v, u)$ not in $E$" should have been "$c_f (u, v) = f (v, u)$ if $(u, v)$ not in $E$" or, what is equivalent, "$c_f (u, v) = f (v, u)$ if $(v, u)$ is in $E$".

  Why do we care about edge that is not in $E$?

In fact, we care only edge $(u,v)$ if either $(u,v)$ is in $E$ or $(v,u)$ is in $E$. If $(v,u)$ is in $E$, it appears that we care about $(u,v)$, an edge that is not in $E$.

The reason can be seen by looking at the specific example in those slides written by Vincent Maccio.

The flow in the above network is not the maximum flow, 6. However, there is no path from $s$ to $t$. How about adding a flow of 2 along the edges along the edges $s\to 2\to1\to3\to t$? This flow is apparently invalid since the only capacity between 1 and 2 are from 1 to 2 instead of from 2 to 1. However, if we consider the net effect of all flows on the edge between 1 and 2, it is effectively 0 as we had a flow of 2 from 1 to 2. So the combinations of all flows, including the apparently illegal flow are in fact valid.

Now the problem is how we can find that apparently invalid but actually valid and helpful additional flow. We did it by a stroke of luck or a flash of intelligence. The systemic way is to adjust the remaining capacities on possible more edges. In the example, we can add an edge from 2 to 1 of capacity 2, which will enable the algorithmic search for additional valid flow.  That is, since directed edge (2,1) is not in $E$ (the directed edge (1,2) is in $E$), we would like to add edge (2,1) with capacity the flow through (1,2). That is " Why $c_f (u, v) = f (v, u)$ if $(u, v)$ not in $E$."

For more information, check the slides and related materials on the web.


how to understand time complexity from a plot? This is my first question here. I'm not a CS at all, so it might be quite trivial.

I have written a program in C where I allocate memory to store a matrix of dimensions n-by-n and then feed a linear algebra subroutine with. I'm having big troubles in understanding how to identify time complexity for these operations from a plot. Particularly, I'm interested in identify how CPU time scales as a function of n, where n is my size.

To do so, I created an array of n = 2, 4, 8, ..., 512 and I computed the CPU time for both the operations. I repeated this process 10000 times for each n and I took the mean eventually. I therefore come up with a second array that I can match with my array of n.

I've been suggested to print in double logarithmic plot, and I read in Wolfram that, using this way, "powers shows up as a straight line". This is the resulting figure (dgesv is the linear algebra subroutine I used).

Now, I'm guessing that my time complexity is $O(a^n)$ since I get straight lines for both my operations (I do not take into consideration the red line). I saw the shapes differences between, say, linear complexity, logarithmic complexity etc. But I still have doubts if I should say something about the time complexity of dgesv, for instance. I'm sure there's a way that I don't know at all, so I'd be glad if someone could help me in understanding how to look at this plot properly.

No, you can't prove asymptotic properties from finite samples. See here and here for more on this.

Plots can give you hints towards the real properties of the running-time function, though, which you can then go ahead and try to prove.


Approximate time for selection operation using index when equality is on nonkey In database query processing, the approximate time for selection operation using primary index when equality is on key is $2(b_s + b_t)$ where $b_s$ is disk seek time and $b_t$ is disk transfer time (assuming one level of indexing), because one seek and transfer time will be needed for finding the index and another one will be for the actual data.

But what will happen if the equality is on a no- key value? Since now we cannot search in the index, don't we have to do a linear search?

In this case full table scan will be executed.

The cost is $N$  I/O operations (where $N$ is a number of pages/blocks in your table)


Calculating worklist with live variable analysis I am struggling with the calculation of the worklist algorithm, I do not want to implement the iterative algorithm as so many redundant steps it takes.
The algorithm I am following to calculate the worklist for live variables is as below

Can anybody explain to me for my example given below, what would be my initial worklist and how the worklist algorithm would be applied to this?
x = 1   /*block 1*/
y = 23  /*block 2*/
x = 100 /*block 3*/
print x+y /*block 4*/

for simple understanding I have taken this code, I have calculated below equations for In[n] block only as I am not able to understand how this algorithm works for out[n].
in[4] = use[4] U (out[4] - def[4])
       = {x, y} U { }
in[3] = use[3] U (out[3] - def[3])
       = { } U { y }
in[2] = use[2] U (out[2] - def[2])
       = { } U { y } - { y }
in[1] = use[1] U (out[1] - def[1])
       = { } U {  }

Now, even though I calculated these equations I am not sure how to use it in worklist? And at end how to does the worklist gets empty?(Algorithms - Nielson book slide 15)

first of all, this will be my first post in here, so if I can't express myself clearly, I am open to all questions and suggestions.
So let's start with your first question, about the initial worklist and how should it look like? In your example, there are four blocks if we show it on control flow graph, we get :

Here we have 4 blocks or as the algorithm calls, "nodes". We create our initial worklist as a FIFO construct. So initially we have something like this :

Now, we will initialize the algorithm. In initialization part, we assign all in and out functions to empty set. So in[1], in[2].... out[3], out[4] will be empty. Also we have created our list in FIFO construct such as W = 4,3,2,1. Now we start the loop.
We start with w.pop = 4. As the algorithm suggests, out[4] = union of successor nodes' in functions. But for node 4, there is no successor so it will be again empty, {} . For in[4] = use [4] U (out[n] - def[n]) = {x,y} U ({} -{}) = {x,y}. Then we check if in[4] has changed or not. The answer is yes, it changed because it was an empty set initially but it updated and become {x,y}. So we should add our work list its predecessors where it is node 3. Now the equations have become in[1], in[2], in[3] = {} , in[4] = {x,y} and out [1], ...out[4] = {}.
Now we continue with our new worklist w = 3,3,2,1. So now we have 3 as the head. out[3] = in[4] = {x,y} and in[3] = use[3] U (out[3] - def[3]) = {}U ({x,y} -{x}) = {y}. Is our new in[3] is different? Again the answer is yes. Then, we add its predecessor 2 to our list. Our list becomes w = 2,3,2,1.
We continue to do it out[2] becomes in[3] = {y} and in[2] = {} U ({y} - {y} ) = {}. In this situation there is no update for in[2]. Because it was {} and still it is. Then we do not add its predecessor to work list, w =3,2,1.
We do the same things for 3 and 2, nothing changes. Then finally we came to the node 1. out[1] = in[2] = {} and in[1] = {}. So it does not change. And finally we finish our list, it became empty. And the algorithm terminates with the equations:
in[1] = {}
in[2] = {}
in[3] = {y}
in[4] = {x,y}
out[1] = {}
out[2] = {y}
out[3] = {x,y}
out[4] = {}
I hope it helps. If you have any questions remaining you can post here or ask me via private message (I don't know if this platform has a functionality for this). If you think that I made some mistakes, that could happen, please let me know.


Algorithm for generating sorting instructions Let's say I am to sort a bookcase given a certain sorting condition, for instance alphabetically. I am looking for a way to generate a step-by-step guide on how to do this sorting based on the original order, as well as the final order.

Original order:

B C A D

Final order:

A B C D

Generated step by step instructions (by index):

0 -> 2
0 -> 2

The problem is, of course, each step will alter the sorting order, requiring the algorithm to take into account the new state of each order.

Is there such an algorithm readily available?

Generally speaking, you sorting algorithm should involve the following two steps:

Sort the books and assign them a numerical order.
Generate optimal sorting instructions given the permutation.

In your example, you start with a list of four books. Sorting them, you assign them a numerical order, B C A D (the numbers here are A,B,C,D). Then you figure out instructions for sorting the permutation B C A D. One approach that will always work is to move A to 0, B to 1, C to 2, and so on. However, this is not optimal. Figuring out the optimal sequence of moves seems like the difficult part of your question.


Equality of NSpace and coNSpace classes I'm trying to decide which of the following statements are true:

$\mathsf{NSpace}(\log \log n) = \mathsf{coNSpace}(\log \log n )$
$\mathsf{NSpace}(\lg^2n) = \mathsf{coNSpace}(\lg^2n)$
$\mathsf{NSpace}(\sqrt n) = \mathsf{coNSpace}(\sqrt n)$

I thought immediately that (1) is correct since $\lg \lg n < \lg n$, and since $\mathsf{NL} = \mathsf{coNL}$, I thought that the statement yields from it. I thought that since we don't know if $\mathsf{P} = \mathsf{PSPACE}$, we can't say anything about a class which is bigger than $\lg n$ and a subset of $P$.

But it is exactly the opposite. (1) is not necessarily true while (2) and (3) are necessarily true. Why is that?

The question is from a past midterm that I'm solving now.

I can't think of any counter-example for (i) right now. But (ii) and (iii) are true due to the Immerman–Szelepcsényi theorem[1], according to which $\text{NSPACE}(s(n)) = \text{co-NSPACE}(s(n))$ for all $s(n) \geq \log(n)$.

[1]: Wikipedia - Immerman–Szelepcsényi theorem


Find maximum in array without comparisons between elements Suppose $A$ is an array of integers, $|A|=n$, $A=\{a_i|1\leq a_i\leq N, i=1\ldots n\}$.

The goal is to find an efficient algorithm $\cal{F}$ to find maximum element in $A$ with these restrictions:

$\cal{F}$ should not compare any $a_i$ with any $a_j$ ever.
$\cal{F}$ also should not add, subtract or exploit some fancy facts about integers
$\cal{F}$ may, however, compare any $a_i$ with some predetermined constant number, and this number may depend on $N$

Why does algorithm exist? Well, counting sort will work, it never compares elements with each other. Its complexity is $O(n+N)$.

I propose this:

compare all $a_i$ with $N/2$, let $L=\{a_i\in A|a_i<\frac{N}{2}\}$, $U=\{a_i\in A|a_i\geq\frac{N}{2}\}$.

If $U$ isn't empty, we may throw $L$ away and compare $U$ with $3N/4$, etc...

If $U$ is empty, we have our initial problem but now the upper bound is $N/2$. Call algorithm recursively.

Basically, it is binary search on $N$, so it will do in $O(n\lceil\log N\rceil)$ in the worst case. If $N$ is big enough it is better than counting sort.

Two questions:

a) am I correct with my algorithm? I can't see any flows in binary search implementation.

b) it is not obvious to me that binary search in this problem is the best solution, is it possible to do better? If not, how to prove it?

I've added some more explanation to clarify the question. According to comments (thanks, EvilJS) I've used term "comparison-based sorting" wrong, so sorry for that.

a) am I correct?

No, that's not correct. Suppose this array is an unsorted array, and you want to find a maximum element in this array.

First, sorting this array in the increasing order. You can use mergesort or quicksort to sort the array. Mergesort will guarantee the time complexity in the worst and average cases is O(nlogn). However, quicksort will take O(nlogn) for the average case, and O(n) for the worst case. Regarding the worst case of quicksort, if partitioning the array into two groups which one group is empty and another one is (n-1), this will take O(n) time complexity.

Second, after you have a sorted array in increasing order, you can get the maximum element at the last element in the sorted array.

b) is it possible to do better?

You can use heapsort with max heaps property. In this case, the largest element is at the root for max heaps. Heapsort will take O(nlogn) since building maxheap takes O(n) and max-heapifying takes O(logn). It takes only O(1) to find a maximum element.


Special term for a cycle containing a single vertex and edge Is there a special term for a cycle containing a single vertex and edge?  I feel like I read "self-cycle" somewhere, but can't find where.

It is generally called a Self Loop.

It refers to an edge that connects a vertex to itself.


Explain Hashed page tables in operating system I have a difficult time understanding hashed page tables used in virtual memory management. Here is picture of the slide that I am referring to:

I understand that p is hashed and then the hash is checked in the page table for a match. What is elements referring to here? Is it the page table entry? What does chain mean and where is virtual page number located?

Can someobody help me understand the flow chart? Thanks

Definitions (What's with the symbols?)

In the diagram, we have these guys:

Virtual Page Number (VPN): p, q
Page Frame Number (PFN): r
Offset: d
Hash Function: h(x)
Hashed Page Table with schema (key, VPN, PFN, Pointer to next entry with key) for each entry in the table

It so happens that h(p) = same_key and h(q) = same_key. There is hash collision. Both p and q are hashed to the same_key.

This is resolved by chaining the entry with VPN = q to the entry with VPN = p. Chaining means to use the Pointer field in the entry with VPN = q to point to the entry with VPN = p.

Workflow (How the system works)

Operating system (OS) grabs p from the CPU, and performs h(p) to get same_key.

OS looks up the first entry in the Hashed Page Table with key = same_key and checks p against the first entry's VPN field. It checks p against q. This is incorrect.

OS uses the Pointer in the first entry to find the second entry. It knows that the second entry has the same key = same_key, because the Page Table is constructed this way. OS checks p against the seond entry's VPN field. It checks p against p. This is correct. Bam. Kill confirmed.

OS knows that this is the correct entry it is looking for. It grabs PFN from the second entry. It grabs r. r is the correct physical frame number that corresponds to virtual page number p.

OS uses r to look for the physical frame it wants in physical memory, and looks for the exact word wanted which is offset by d within frame r in physical memory. OS grabs the contents of the word and we're done.

Source: Dave Johnson's COMP 421 (Rice University CS Dept)


Size, depth, and time of circuits Can polynomial depth circuits (with, let's say AND, OR, and NOT gates) be simulated in polynomial time?

No.  Every function can be implemented with a polynomial-depth circuit, but not all function families can be implemented with a polynomial-time algorithm.

In particular, if we're allowed unbounded fan-in/fan-out, you can implement every function in depth 2 using a CNF or DNF formula for the function (but the size of the circuit is exponential).  If we're only allowed constant fan-in/fan-out, you can simulate that with linear depth (use a $n$-layer tree to make exponentially many copies of each input; then 1 layer to evaluate the CNF clauses; then a $n$-layer AND tree).


Dijkstra's algorithm for edge weights in range 0, ..., W Suppose I want to run Dijkstra's algorithm on a graph whose edge weights are integers in the
range 0, ..., W, where W is a relatively small number.
How can I modify that algorithm so that it takes time just O((|V| + |E|) logW) and relatively easy implement that in C/C++?

This is the algorithm I know of that is $\mathcal{O}(|E| + W|V|)$. Some things to note:

$C$ is defined as the maximum cost of any shortest path that leaves $s$ (the source). It is at most $W|V|$.
Each $L[i]$ is a doubly-linked list. The $L[i]$ keep track of all vertices that are currently at distance $i$ from the source.
$d[v]$ is the shortest distance (so far) from the source to vertex $v$

Each edge and vertex of the graph will be visited only once, and the outer loop runs in time $\mathcal{O}(C)$, therefore the complexity of the algorithm is $\mathcal{O}(|E| + |V| + C)$. Since $C \leq W|V|$, this reduces to $\mathcal{O}(|E| + W|V|)$.

L[i] <- {}, 0 <= i <= C
L[inf] <- {}
L[0] <- {s}

for v in V do
    push v into L[inf]
    d[v] <- inf
end

d[s] <- 0
p <- 0
while p < C do
    while L[p] != {} do
        pop v from L[p]
        for (v, u) with d[u] > d[v] + w(v, u) do
            remove u from L[d[u]]
            d[u] <- d[v] + w(v, u)
            push u in L[d[u]]
        end
    end
    p <- p + 1
end


Disruption in the context of Genetic Algorithms I'm trying to do a homework problem which references "disruption" in Genetic Algorithms.

  True or false? For  1-point  and  2-point  crossover,  the  schemata
  which  have  bits  that  are  close  together  on  the string encoding
  are more likely to be disrupted by crossover.

I think that it is referring to is the creation of children distinct from their parents.

For example, combining the following two parents at a single crossover point at the second digit would just create the same parents again. Thus, no disruption would occur.

p1: 00000
p2: 00001

However, combining the following two parents at a single crossover point at the second digit would create some disruption.

p1: 00000
p2: 01001
c1: 01000
c2: 00001

By intuition, I would measure disruption as the number of bits that are different in a child as compared to the two parents. However, I have no formal definitions of this, despite turning to Google. The closest I've come is to Holland's Schema Theorem, which I think is related, but I would still like a definition or an explanatory reference.

According to my professor, my intuitive description of disruption is correct, however one does not measure the "degree of disruption". It is a binary measure. Either you have disruption or you do not.

Still can't find an official source for this, so edits to this answer and other answers are welcome.


What does the processor do while waiting for a main memory fetch Assuming l1 and l2 cache requests result in a miss, does the processor stall until main memory has been accessed?

I heard about the idea of switching to another thread, if so what is used to wake up the stalled thread?

Memory latency is one of the fundamental problems studied in computer architecture research.

Speculative Execution

Speculative execution with out-of-order instruction issue is often able to find useful work to do to fill the latency during an L1 cache hit, but usually runs out of useful work after 10 or 20 cycles or so.  There have been several attempts to increase the amount of work that can be done during a long-latency miss.  One idea was to try to do value prediction (Lipasti, Wilkerson and Shen, (ASPLOS-VII):138-147, 1996).  This idea was very fashionable in academic architecture research circles for a while but seems not to work in practice.  A last-gasp attempt to save value prediction from the dustbin of history was runahead execution (Mutlu, Stark, Wilkerson, and Patt (HPCA-9):129, 2003).  In runahead execution you recognize that your value predictions are going to be wrong, but speculatively execute anyway and then throw out all the work based on the prediction, on the theory that you'll at least start some prefetches for what would otherwise be L2 cache misses.  It turns out that runahead wastes so much energy that it just isn't worth it.

A final approach in this vein which may be getting some traction in industry involves creating enormously long reorder buffers.  Instructions are executed speculatively based on branch prediction, but no value prediction is done.  Instead all the instructions that are dependent on a long-latency load miss sit and wait in the reorder buffer.  But since the reorder buffer is so large you can keep fetching instructions if the branch predictor is doing a decent job you will sometimes be able to find useful work much later in the instruction stream.  An influential research paper in this area was Continual Flow Pipelines (Srinivasan, Rajwar, Akkary, Gandhi, and Upton (ASPLOS-XI):107-119, 2004).  (Despite the fact that the authors are all from Intel, I believe the idea got more traction at AMD.)

Multi-threading

Using multiple threads for latency tolerance has a much longer history, with much greater success in industry.  All the successful versions use hardware support for multithreading.  The simplest (and most successful) version of this is what is often called FGMT (fine grained multi-threading) or interleaved multi-threading.  Each hardware core supports multiple thread contexts (a context is essentially the register state, including registers like the instruction pointer and any implicit flags registers).  In a fine-grained multi-threading processor each thread is processed in-order.  The processor keeps track of which threads are stalled on a long-latency load miss and which are ready for their next instruction and it uses a simple FIFO scheduling strategy on each cycle to choose which ready thread to execute that cycle.  An early example of this on a large scale was Burton Smith's HEP processors (Burton Smith went on to architect the Tera supercomputer, which was also a fine-grained multi-threading processor).  But the idea goes much further back, into the 1960s, I think.

FGMT is particularly effective on streaming workloads.  All modern GPUs (graphics processing units) are multicore where each core is FGMT, and the concept is also widely used in other computing domains.  Sun's T1 was also multicore FMGT, and so is Intel's Xeon Phi (the processor that is often still called "MIC" and used to be called "Larabee").

The idea of Simultaneous Multithreading (Tullsen, Eggers, and Levy, (ISCA-22):392-403, 1995) combines hardware multi-threading with speculative execution.  The processor has multiple thread contexts, but each thread is executed speculatively and out-of-order.  A more sophisticated scheduler can then use various heuristics to fetch from the thread that is most likely to have useful work (Malik, Agarwal, Dhar, and Frank, (HPCA-14:50-61), 2008).  A certain large semiconductor company started using the term hyperthreading for simultaneous multithreading, and that name seems to be the one most widely used these days.

Low-level microarchitectural concerns

I realized after rereading your comments that you are also interested in the signalling that goes on between processor and memory.  Modern caches usually allow multiple misses to be simultaneously outstanding.  This is called a Lockup-free cache (Kroft, (ISCA-8):81-87, 1981).  (But the paper is hard to find online, and somewhat hard to read.  Short answer: there's a lot of book-keeping but you just deal with it.  The hardware book-keeping structure is called a MSHR (miss information/status holding register), which is the name Kroft gave it in his 1981 paper.)


PERT Chart exercise - is there enough information to solve? I'm posting this here as my question is from a computer science textbook. It is not a homework question as I am self-studying and I have the answers available.

In the exercise below, I can't see how I'm supposed to know which activity to place on which arrow. I can't tell if there is insufficient information provided or if it is a lack of understanding on my part which makes it impossible to decide which arrow out of node 2 should have be labelled B and which with C for example.

If it is solvable given the information provided, could someone please exaplain the method?

I don't know if there is a standard method to identify which activity matches which arrow, but I was able to complete your PERT chart by examining a few possible cases, while filling the chart from left to right. Each case was accepted or rejected after a while. I found that the higher arrow matches B and the lower C. Note that if you try to match C with the higher arrow, (2,3), E will match with the (3,5) arrow but then you will face the problem that only one activity depends on E while there are two arrows starting from it that have to be filled. Otherwise, if you match (2,3) with B, (3,5) will match with D and then there are two acivities dependent from D as you wish. More uncertainties will raise but they are solvable by considering the different cases.

So the information provided are enough to solve the excersise. One possible typing error that I identify in the problem statement is that Q doesn't depend on K, L and P only, but it depeds on M too. That's why there are four arrows entering node 15 instead of three. Otherwise there is no lack of information and you can solve the problem as I described above.

A second way to solve the problem is to create the PERT chart based on the data written in the table by yourself. The graph that you will make will be isomorphic with the graph that you will get if you merge the nodes connected by dotted edges on the graph of the problem statement. So after that you will have to create an edge matching between the two graphs in order to find which activity matches which arrow on the given graph.

Both methods will lead to a correct solution, you can try them for practice.


Looking for sources: Graph search in social media I am looking for more information/references on how graph search is utilized in social media. Papers, books , anything really.

Facebook graph search is a relatively new technology pioneered/announced by Facebook that attempts to search for relevant info based on social connections in a social media system (eg Facebook). ie it finds relevant info based on exploring information "nearby" on the "social graph".
in this way, basically every person on Facebook doing the same search with same search terms might come up with different results based on how it interrelates with what their friends are posting about. this also can be seen as part of a trend where the major online services are encroaching on each others prior territory, eg Google's recent introduction of Google+ social network. conversely Facebook is now encroaching on Google's lucrative and highly-developed search engine technology.
there is a huge amount of media coverage [cited in the wikipedia article] but mainly at a superficial level of a product introduction. in contrast to Googles pagerank algorithm, the Facebook algorithm did not appear to originate in open scientific research, but instead is a mostly proprietary technology developed within Facebook. Facebook is not going to want to release many details, but the following is useful for an overview, written by Xiao Li, an engineering manager on the natural language team for Graph Search, and Maxime Boucher a research scientist for Graph Search.

Under the Hood: The natural language interface of Graph Search

also it will be natural for Facebook to insinuate this algorithm as highly developed and competitive with Pagerank but because its in early stages of development, one would not expect highly advanced results competitive with Pagerank at least at first (because Pagerank has been highly developed over a decade etc) with respect to mere semantic capability. on the other hand Facebook has access to a social graph, and it would be expected to prove superior quality in some types of searches that best leverage/focus on ones personal social network.
there does not appear to be much open scientific research outside of Facebook related to this topic. however the following seems to be a publication of some of the principles in a previous prototype/experimental iteration/version called Unicorn which the new feature is probably originating from/growing out of.

Unicorn: a system for searching the social graph

Unicorn is an online, in-memory social graph-aware indexing system designed to search trillions of edges between tens of billions of users and entities on thousands of commodity servers. Unicorn is based on standard concepts in information retrieval, but it includes features to promote results with good social proximity. It also supports queries that require multiple round-trips to leaves in order to retrieve objects that are more than one edge away from source nodes. Unicorn is designed to answer billions of queries per day at latencies in the hundreds of milliseconds, and it serves as an infrastructural building block for Facebook's Graph Search product. In this paper, we describe the data model and query language supported by Unicorn. We also describe its evolution as it became the primary backend for Facebook's search offerings.


Finding largest disjoint subtrees spanning nodes I have a taxonomy (tree) of product categories. To each leaf product category, I have assigned a shop department where the products of a given category can be found.
Now for each department, I would like to find the smallest number of the largest subtrees in the taxonomy.
For instance, in the example below leaf nodes have been assigned one of two departments $A$ and $B$.

The expected solution would be: $A$ has two subtrees, namely $x_2$ and $x_7$, $B$ has one subtree $x_4$.
The solution where $A$ has $x_1$ subtree is wrong because $x_1$ is the ancestor of nodes that belong to another department.
The solution where $A$ has $x_3$ and $x_7$ subtrees is wrong because we want the biggest subtrees possible.
Is it a known problem?
Is there a solution for it?

Here's an algorithm.  Let $D(l)$ denote the department of the product category of a leaf $l$.
To find the subtree for leaf $l$ do the following.  For every leaf $l'$ such taht $D(l') \neq D(l)$, mark the node $\text{lca}(l, l')$.  Now, your largest subtree is the subtree rooted in the highest unmarked node.  Call this node $\text{root}(l)$.
To compute for all leaves, clear the marks and output $\bigcup_{l \in L} \text{root}(l)$, where $L$ is the set of leaves.

A different (faster) algorithm: For each leaf $l$, move upwards and mark each node with $D(l)$.  If you hit a node already marked $D(l)$, you move on to the next leaf.  If you hit a node marked with a different color, delete the node.  Then your connected components should be your largest disjoint subtrees.

You ask if it's a known problem, I think that the closest you get to a known problem is the lowest common ancestor problem.


What algorithms are there for scheduling tasks The scenario is something like this

I have tasks that get requested, with a category and a priority
For simplicity let's assume that rate of incoming tasks and completion is about the same, with some existing backlog of tasks
Each category of tasks can only be completed at some certain rate
Completion of tasks is handled out of the system, so we can assume that deciding to take on a certain task is equivalent to completing it

So I want some way of deciding which tasks to complete at a given time, given the existing tasks and their priorities, and the limits on completion within a certain category

One greedy algorithm would be to just organize each category by priority, and then at each decision point take in as many tasks as is allowed by that category's rate, but the problem with this is that if a lot of high priority tasks come in low priority tasks will just sit in the backlog, potentially forever.

I've looked at some scheduling concepts like round robin scheduling and multilevel priority queues, but they don't seem to fit what I want - tasks can't be paused/rescheduled as in round robin, and multi priority queues seems like it'd still have the problem of getting to low priority tasks (could just make the priorities more stratified, but then it's just back to the original problem with deciding how many tasks to take from each queue)

Any advice on what I should look into? Maybe it's a sort of "repeated knapsack" thing?

What you can do is to add another parameter to your tasks, something that I would call dynamic priority delta. Or what is equivalent, you can implement some mechanism to increase or decrease the priority of each task on top of multilevel priority queues.

The basic idea is simple. "A process that waits too long in a lower-priority queue may be moved to a higher-priority queue. This form of aging prevents starvation.", reads section 5.3.6 of Operating Systems Concepts, seventh edition. For an extreme simple example, you can just increase priority level by one if a task has waited for an hour. Here is more excerpt from that book.

  In general, a multilevel feedback-queue scheduler is defined by the following parameters:

  The number of queues
  The scheduling algorithm for each queue
  The method used to determine when to upgrade a process to a higher- priority queue
  The method used to determine when to demote a process to a lower- priority queue
  The method used to determine which queue a process will enter when that process needs service

  The definition of a multilevel feedback-queue scheduler makes it the most general CPU-scheduling algorithm. It can be configured to match a specific system under design. Unfortunately, it is also the most complex algorithm, since defining the best scheduler requires some means by which to select values for all the parameters.

Your situation might be even more complex since your task are also labelled with category. Without more information, I cannot advise further into your scheduling algorithm.

I encourage to read chapter "CPU Scheduling" of Operating System Concepts by Avi Silberschatz, Peter Baer Galvin and Greg Gagne. For even more content, read chapter "Uniprocessor Scheduling" and "Multiprocessor and Real-Time Scheduling" of Operating System Internals and Design Principles by William Stallings. Although they are talking about CPU or processor scheduling, most of the concepts and algorithms are the same as in or can be applied to job/task scheduling. You will find lots of inspirations and ideas and references.


Solution to recurrence $T(n) = T(n/2) + n^2$ I am getting confused with the solution to this recurrence -
$T(n) = T(n/2) + n^2$

Recursion tree -

T(n)                      Height lg n + 1
 |
T(n/2)
 |
T(n/4)

So it turns out to be -

$T(n) = n^2(1 + 1/4 + (1/4)^2) + \ldots (1/4)^{\log_2 n - 1})$

$T(n) = 4*n^2(1- (1/4)^{\log_2 n})/3 + n^2 $

$T(n) = 4*n^2(1 - 1^{\log_2 n} + 4^{\log_2 n})/3 + n^2 $

$ T(n) = 4*n^2(1 - 1 + n^{\log_2 4})/3 + n^2$

$ T(n) = 4*n^2(n^2)/3 + n^2$

$ T(n) = 4/3 * (n^4) + n^2 $

$ T(n) = \Theta(n^4) $

But according to the Master theorem, $a = 1, b = 2, f(n) = n^2 $, then $n^{\log_2 1} = 1 $ which is polynomial times less than $ n^2 $ so the solution should be $ \Theta (n^2) $?

Try this way:
$$
\begin{align*}
T(n) &= T(n/2) + n^2 \\
T(n) &= T(n/4) + (n/2)^2 + n^2\text{ (expand $T(n/2)$)} \\
T(n) &= T(n/8) + (n/4)^2 + (n/2)^2 + n^2\text{ (expand $T(n/4)$)}
\end{align*}
$$

You will end up with:
$$
\begin{align*}
T(n) &= n^2 + (n/2)^2 + (n/4)^2 + (n/8)^2 + \cdots + (n/2^{\lg n})^2 \\
T(n) &= n^2 + n^2/4 + n^2/16 + n^2/64 + \cdots
\end{align*}
$$

We can bound this from above as $T(n) \le 2 n^2$ and from below with $T(n) \ge n^2$, giving $T(n) = \Theta(n^2)$.

Note: we do not need to use induction to prove this; since we can create an upper bound of $T(n) \le c_1f(n)$ and a lower bound of $T(n) \ge c_2f(n)$, we can use the definition of $\Theta(n)$ to establish the time complexity of the relation.


Looking for an algorithm to generate an identicon/avatar from genome data I am looking to develop an app that generates a single identicon image that summarizes the genome information in visual form.

Identicons are essentially a visual hash of of data. usually string data such as an IP address or name. In this case, rather than generating an identicon from a single piece of string data. I want to use the entirety of the genotype information (the 4th column) to summarize this data into a graphical representation as a way to visually identify someone from their partial genome.

The input file is a tab-separated file consisting of 600,000 rows. Each row contains the chromosome identifier (There are 23 in total: 1-20, X, Y or MT), the position of the single nucleotide polymorphism (SNP) and the genotype (a two character variation of G,A,T or C). Below is a two line excerpt from the file.

#RSID        Chromosome   Position  Genotype
rs7537756       1         854250    AG
rs13302982      1         861808    GG

Using the Chromasome, Position and Genotype columns. I would like to generate an abstract identifying image from this data. Since there is far too much data, this image does not need to capture the data, only summarize it in a visual fashion. The goal is to setup a service that analyzes anyone's genome file and generates an identicon that is unique to them.

For more information on identicons See the wiki page

If all you want is uniqueness, you could use a visual hash.  Hash all of the data (say, with SHA256), then apply a visual hash.

A visual hash is a function $H$.  Given a short binary string $x$ (say, 256 bits long), the visual hash computes $H(x)$, a random picture that is a visualization of $x$.  The output of the hash is a visualization of the string -- a picture or image of some form -- with the property that different binary strings will lead to different images.  Also, $H$ is a deterministic algorithm, so if you hash the same binary string twice, you'll get the same picture both times.

Below I list some visual hash schemes that have been proposed, along with sample images produced by each scheme.

Random Art for PGP keys

https://user.xmission.com/~atoponce/art/

(As you'll notice, this is actually a visualization of multiple different schemes at once.)

See also the following research paper:

Hash Visualization: a New Technique to improve Real-World Security.  Adrian Perrig and Dawn Song.  Proceedings of the International Workshop on Cryptographic Techniques and E-Commerce (CrypTEC), Hong Kong, July 1999.

VizHash GD

http://sebsauvage.net/wiki/doku.php?id=php:vizhash_gd

JrSnowflake

https://wiki.debian.org/JrSnowflake

Older: README, source

OpenSSH's Visual Host Key

+--[ RSA 2048]----+
|   .+            |
|   + o           |
|  o o +          |
|   + o +         |
|  . o E S        |
|   + * .         |
|    X o .        |
|   . * o         |
|   .o .          |
+-----------------+

https://stackoverflow.com/a/3601278/781723


Relationship between an integer N and the number of bits n required to represent the integer I'm trying to understand the time complexity of the following code in terms of n.

Pseudocode for trial division:

I understand that the time complexity of the algorithm is O(sqrt(N)). However, can someone explain how the person in the link below came up with O(e^(n/2)). In other words, what's the mathematical relationship between N and n? Thanks.

Time complexity explanation:

The integer $N$ takes $\log_2 N$ bits to write down.  Set $n = \log_2 N$.  Then $N = 2^n$, so $\sqrt{N} = 2^{n/2}$.

I'd guess they are using the natural logarithm (to base $e$), which is where they get $e$ instead of $2$.  That's a bit odd but I suppose it is valid.

See also Complexity of multiplication and Precise runtime of the algorithm to find number of digits in an integer.


Is there difference between a function in mathematics to a function in computer science? I never learned a lot of mathematics (generally only arithmetic) and never learned computer science in a formal frame.
I emphasize that I don't mean to ask about a "function" in programming ("procedure"/"method"), rather only about the difference between the formal definition of function in mathematics to the formal definition of function in (theoretical) computer science, if at all there is any such difference (unless computer science don't share the exact definition common in mathematics).
Is there difference between a function in mathematics to a function in computer science?

A function in mathematics is just a special case for a binary relation, where for every x there is exactly one y such that xRy is in the binary relation.
Computer science uses that term with the same meaning, as it uses lots of mathematical terms. It also uses the term "function" (or "subroutine", "procedure", "method") with a totally different meaning of one component of a program in the area of computer programming.
Just like the word "function" would be used with a completely different meaning in patent law (functional vs. decorative components) architecture (a functional design), medicine or psychology (like a "functional alcoholic").


What is the use of Horner's Method? Here is Wikipedia's explanation of Horner's Method:

  Given the polynomial

  $$
p(x) = \sum_{i=0}^n a_i x^i = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots + a_n x^n,
$$

  where $a_0, \ldots, a_n$ are real numbers, we wish to evaluate the polynomial at a specific value of $x$, say $x_0$.

  To accomplish this, we define a new sequence of constants as follows:

  $$
\begin{align}
b_n & := a_n \\
b_{n-1} & := a_{n-1} + b_n x_0 \\
& {}\  \  \vdots \\
b_0 & := a_0 + b_1 x_0.
\end{align}
$$

  Then $b_0$ is the value of $p(x_0)$.

  To see why this works, note that the polynomial can be written in the form

  $$
p(x) = a_0 + x(a_1 + x(a_2 + \cdots + x(a_{n-1} + a_n x)\cdots)).
$$

  Thus, by iteratively substituting the b_i into the expression,

  $$
\begin{align}
p(x_0) & = a_0 + x_0(a_1 + x_0(a_2 + \cdots + x_0(a_{n-1} + b_n x_0)\cdots)) \\
& = a_0 + x_0(a_1 + x_0(a_2 + \cdots + x_0(b_{n-1})\cdots)) \\
& {} \ \  \vdots \\
& = a_0 + x_0(b_1) \\
& = b_0.
\end{align}
$$

Question:

Is the point of this algorithm that we can now evaluate $p(x_0)$ without having to ever evaluate any of the values $x_0^2, \ldots, x_0^n$, and instead, we are able to just just iteratively compute $b_n$ through $b_0$, where by the time we eventually get to $b_0$ we are finally able to evaluate $p(x_0)$?

If this is the case, why is this useful? Why not just compute $p(x_0)$ the normal way?

EDIT: Is it true that using Horner's rule to compute a polynomial of degree $n$ takes running time from $\Theta(n^2)$ down to $\Theta(n)$?

Yes, exactly as you said. This is used to decrease the number of multiplications, so it is more efficient than computing it the normal way.

Example:

  You have the polynomial $ax^3 + bx^2 + cx + d$.
  Computing directly you have six multiplications: (a * x * x * x, b * x * x, c * x). With Horner $((ax + b)x + c)x + d$ you have three multiplications: (a * x, first parenthesis * x, second parenthesis * x)

It is important to remember that in floating point calculations results from these two methods (direct and Horner) will differ.


Is checking if the length of a C program that can generate a string is less than a given number decidable? I was given this question:

Komplexity(S) is the length of the smallest C program that generates the string S as an output. Is the question "Komplexity(S) < K" decidable?

With respect to decidability, I only know about the Halting Problem and just learned about Rice's Theorem while searching online (though I don't think it can be applied here?). I couldn't reduce the problem to any undecidable problem I know about. Thanks in advance for any help

The length of the smallest C program that generates a given string is known as the Kolmogorov complexity of the string. One of the basic properties of Kolmogorov complexity is its undecidability.


A Question related to the method of find lower bound : Trivial lower bounds In Trivial lower bounds we just need to count the number of items in the input that needs to be processed and the number of items that need to be generated and the trivial lower bound time is then the sum of these two found numbers. My question is , we know that the time complexity = number of times the basic operation is repeated as a function of the input size * the time it is taken to preform the basic operation once. So as we can see from the formula of the time complexity that it depends on the basic operations  not on the number of inputs and output items. So how does the trivial solution is used to compute the lower bound ( worst time complexity of best algorithm) then ?

The trivial bound assumes that the program has to read the entire input. This is usually, but not always, the case. Similarly, it assumes that the program has to write each output item separately. This is usually, but not always, the case.

Since the program has to read the entire input, it has to do some operation for each input item. Similarly, it has to so some operation for each output item. This gives you the trivial bound, in terms of the number of basic operations.

Since we are usually only interested in complexity up to constant factors (big O complexity), the actual time that a basic operation takes doesn't enter the picture at all.


Why is a threshold determined for Byzantine Fault Tolerance of an "Asynchronous" network? (where it cannot tolerate even one faulty node) In following answer (LINK: https://bitcoin.stackexchange.com/a/58908/41513), it has been shown that for Asynchronous Byzantine Agreement:

  "we cannot tolerate 1/3 or more of the nodes being dishonest or we lose
  either safety or liveness."

For this proof, the following conditions/requirements has been considered:

  Our system is asynchronous.
  Some participants may be malicious.
  We want safety.
  We want liveness.

A fundamental question is that:

With considering the well-known paper titled: "Impossibility of Distributed Consensus with One Faulty Process" (LINK: https://apps.dtic.mil/dtic/tr/fulltext/u2/a132503.pdf)

showing that:

no completely asynchronous consensus protocol can tolerate even a single unannounced process death,

Can we still assume that the network is asynchronous ? As in that case the network cannot tolerate even one faulty node.

The answer has to do with tracking the precise assumptions that are made in these different results. In short, while both results assume asynchrony, the "impossibility of distributed consensus with one faulty process" requires a stronger form of liveness and determinism, and that makes consensus impossible.

1. Impossibility of Distributed Consensus with One Faulty Process

This seminal result (of Michael Fischer, Nancy Lynch, and Michael Paterson) is about distributed consensus where the system is not just asynchronous, but also satisfies:

Determinism.  The consensus algorithm does not use any randomness.
Liveness under message delays. Not only may messages be delayed arbitrarily, but we also must guarantee liveness even in the presence of such continued delays.

Let us see why tehse properties are too strong, and make distributed consensus impossible.

Consider an example: Alice, Bob, and Charlie are friends and want to decide on where to meet for dinner. It is possible that one of them unexpectedly goes AWOL (or decides they are not interested in being friends anymore) and stops responding to messages. In this case, the other two can still decide on a place to meet. Now what should they do?

The obvious approach would be that:

  Alice just decides where to go, and tells Bob and Charlie.

But this does not work because Alice may be the one who goes AWOL.
So to fix this, the next most obvious approach might be:

  Both Alice and Bob tell everyone else where to go. If everyone hears from Alice, then they will go where Alice says; otherwise, they will go where Bob says.

But this has a new problem. Suppose you are Charlie. If you hear from Alice, you know where to go. If you hear from neither of them, you wait to hear. The problem is when you have heard from Bob, but not Alice. Because there are arbitrary message delays, you cannot commit to go where Bob said: Alice might have said where to go, and you just have not received it yet!
So you are completely stuck, and if it happens that Alice has gone AWOL, you will just keep waiting forever.

The problem here is that we have no way to abort the transaction; no way to say, "OK, this isn't working, it's been too long and I haven't received a delay -- let's try again." Real-world consensus algorithms (the best known being Paxos) have the possibility that rounds fail due to network delays, and in this case they just try again, hoping for shorter network delays. Additionally, it is possible to get around the problem by using randomized protocols which usually work, and only go on forever with small (or even zero) probability.

2. Asynchronous Byzantine Agreement where less than $1/3$ of the nodes fail

The bitcoinSE post you link glosses over the issue of liveness, saying only that it is "the ability to continue to make forward progress". In fact, the above result shows that the strongest form of this is impossible, so we have to relax our requirements / assumptions.

Let's consider two examples. In Miguel Castro and Barbara Liskov's "Practical Byzantine Fault Tolerance", they achieve practical liveness with less than a third of nodes being faulty by assuming that message delays do not continue to grow indefinitely. As the authors state:

  We guarantee liveness, i.e., clients
  eventually receive replies to their requests, provided at most
  $\frac{n-1}{3}$ replicas are faulty and $delay(t)$ does not
  grow faster than $t$ indefinitely...This is a rather weak synchrony
  assumption that is likely to be true in any real system
  provided network faults are eventually repaired, yet it
  enables us to circumvent the impossibility result in [9].

Here [9] is the impossibility result discussed above. In plain terms for our example, they avoid the above problem with Charlie by requiring a weak form of synchrony: Charlie does not simply have to keep waiting forever, as we know that message delays can only grow termporarily, and not indefinitely. (Of course the actual algorithm gets a lot more complex, but that is partly the conceptual idea of why liveness is possible.)

In Ran Canetti and Tal Rabin's "Fast Asynchronous Byzantine Agreement with Optimal Resilience", they use randomness to get liveness with less than $n/3$ Byzantine node failures. From their paper:

  In this setting, we describe an $(\lceil\frac{n}{3}\rceil- 1)$-resilient Byzantine Agreement protocol. With
  overwhelming probability all the non-faulty players complete the execution of the protocol. Conditioned on the
  event that all the non-faulty players have completed the
  execution of the protocol, they do so in constant expected
  time.

Here $(\lceil\frac{n}{3}\rceil- 1)$-resilient just means less than a third of nodes are Byzantine.
Note the key words with overwhelming probability. So they have a probabilistic algorithm which has many possible "runs", and overwhelmingly most of them work. Note that the above impossibility result implies that there must always be some runs where liveness does not occur, i.e. there is no consensus:

  Fischer, Lynch and Paterson’s [FLP] seminal impossibility result for deterministic protocols implies that any (randomized) protocol reaching BA must have nonterminating runs.


Polytime algorithm for SUBSET-SUM assuming P=NP In the Wikipedia page on P vs. NP problem there is an algorithm that "solves" SUBSET-SUM in case P=NP in polynomial time. (It's idea is to find a TM that gives a certificate). But it gives "yes" in polynomial time and runs forever if the answer is "no". It can be obviously fixed to give "no" in exponential time (just to run exponential algorithm if the first one is running for too long).

But can we explicitly describe an "honest" algorithm, which solves (and I mean, really solves) SUBSET-SUM (or any other NP-complete problem) in polynomial time assuming P=NP?

By "honest" and "really solves" I mean that the algorithm meets the classical definitions for a polynomial-time algorithm, i.e., here should exist constants $C_1, C_2$ such that at any input $x$ algorithm would terminate in no more than $C_1 \cdot |x|^{C_2}$ steps and output "yes" if $x \in $ SUBSET-SUM and "no" otherwise. The Wikipedia algorithm does not satisfy the first condition, so it doesn't "really solve" the problem.

I can half-answer this, but I believe the deeper question you are getting at is something I am in the process of learning better :)

The algorithm on wikipedia, call it W, is based on the idea: rather than guess at certificates why not just guess at the deterministic P algorithm D itself? This is expensive, but since it is independent of the input it is O(1) (if such an algorithm exists). The algorithm actually always decides even if P != NP, because there is of course a series of "brute force" programs that print out just one possible certificate then halt, so W can fall back to a very slow brute force.

The problem is that you actually have no way to verify the program it returns to you. You may imagine running W and find it seems to prefer a certain program, but you may find that on larger input it eventually finds a flaw in that program and moves on. It may seem to settle on an algorithm that seems to be $n^7$ but later on find a mistake in it and switch to an $n^{2000}$ algorithm. You will never know when it has found the "right" one.

This is actually the same idea used in the proof of the Karp-Lipton theorem: given enough computation power you can use it to just start guessing entire classes of programs and verify that they work (the proof is exactly, "guess a program, and verify that it works, then use it", which takes a bit of computational power - more than NP - to pull off.)

I am not aware of theory regarding how complicated a solution can be, but perhaps someone more knowledgeable can answer.

The more concrete scenario in the P=NP reality is that someone actually constructs an algorithm to any NP-complete problem, such as SAT.

I think you asked a good question and I'm curious how to fill in the gaps in my answer, regarding how W may be analyzed and made more useful in semi-practice.


Is this possible to solve SAT in polynomial time by reducing it to the problem of solving system of nonlinear equations? Every conjunctive normal form (CNF) formula can be converted to nonlinear system of equations, where each clause becomes an equation in the system and:

If A and B are logical/boolean variables and defined as A∈{T,F} ∧ B∈{T,F} or (A,B)∈{T,F}2 where

{T,F}2={T,F}⨯{T,F} = {(T,T),(T,F),(F,T),(FF)}

Then:

A=x, ¬A=1-x, B=y, ¬B=1-y and A∨B=x+y-x•y

That's how the left side of each nonlinear equation in the system is computed.

The right side of each nonlinear equation in the system is obviously the constant natural number 1.

Finding a solution to this nonlinear system of equations is finding satisfying assignment to the given CNF formula.

That way SAT is reduced to the problem of solving nonlinear system of equations in polynomial time, thus the problem of solving nonlinear system of equations is NP-Hard, because of the fact that SAT is NP-Complete.

But I think that there already exist algorithms that solve nonlinear system of equations in polynomial time and space complexity, if so then also SAT can be solved in polynomial time and space complexity too.

Do I wrong in everything I said?

It sounds too good to be true and

If it's too good to be true, something's wrong.

quote from John Allison.

It is not currently known whether or not a polynomial algorithm exists to solve these systems of nonlinear equations because, as the reduction provided shows, if such a thing were to exist, it would show that $NP = P$ which remains yet unknown.


Grokking pseudo-code for solution to gas station problem I'm trying to grok the pseudo-code for the gas station problem (which I think we should start calling the charging station problem but that's a different story) given as Fill-Row in Fig. 1 in To Fill or not to Fill: The Gas Station Problem. The algorithm is reproduced below for ease of reference:

There are some obvious things to fix here in any implementation of the algorithm.

The case $q = 1$ needs special consideration as noted by j_random_hacker in this CS SE answer.
It may happen that no $v$ satisfies $g \leq d_{uv}$ so that there is no vertex to pick in line 10 of the algorithm. In this case, the table entry should be declared infinite, $C[u, q, g] = \infty$.

Even with those two fixes, though, it seems to me that something is still off. As the description supporting the algorithm notes, cases where $c(v) \leq c(u)$ should only be considered when $g \leq d_{uv}$, hence the special treatment in lines 9 and 10, but this additional constraint can be ignored when $c(v) > c(u)$ (according to the formula for $A(u, q, g)$ preceding Theorem 2.2). In practice, this means that the generated program does not match the recurrence relation: Below is a rough Python implementation of lines 7--11 of Fill-Row (after r has been sorted):

i = 0
v = r[i]
for g in GV[u]:
    if i == len(r):
        C[(u, q, g)] = inf
        continue
    while g > d[v] - d[u]:
        i += 1
        if i == len(r):
            break
        v = r[i]
    if i == len(r):
        C[(u, q, g)] = inf
    else:
        C[(u, q, g)] = indep[v] - g * c[u]

If this implementation is assumed to be a correct implementation of the pseudo-code, it is easy to generate examples where $C[(u, q, g)]$ does not match $A(u, q, g)$.

A first attempt at fixing this would be to ignore $g \leq d_{uv}$ for $c(v) > c(u)$:

i = 0
v = r[i]
for g in GV[u]:
    if i == len(r):
        C[(u, q, g)] = inf
        continue
    while True:
        if g <= d[v] - d[u] or c[v] > c[u]:
            break
        i += 1
        if i == len(r):
            break
        v = r[i]
    if i == len(r):
        C[(u, q, g)] = inf
    else:
        C[(u, q, g)] = indep[v] - g * c[u]

This seems to work, in that I haven't been able to construct a counter-example. Yet it seems to me that it shouldn't: If $c(v) > c(u)$ occurs for low values of $\mathrm{indep}[v]$, we risk skipping them for all but the smallest $g \in GV[u]$. As such, I would expect that we should rather reset the loop over r ($R$ in the paper) for each iteration, moving the first two lines inside the loop over GV[u]:

for g in GV[u]:
    i = 0
    v = r[i]
    if i == len(r):
        C[(u, q, g)] = inf
        continue
    while True:
        if g <= d[v] - d[u] or c[v] > c[u]:
            break
        i += 1
        if i == len(r):
            break
        v = r[i]
    if i == len(r):
        C[(u, q, g)] = inf
    else:
        C[(u, q, g)] = indep[v] - g * c[u]

However, doing so takes us from $O(n \log n)$ to $O(n^2)$, which invalidates Theorem 2.2. You can probably do something more clever by keeping track of the cases $c(v) > c(u)$ and $c(v) \leq c(u)$ separately, but that doesn't seem to be in the spirit of the pseudo-code (and in particular, I'm aware that an algorithm with lower complexity exists in A fast algorithm for the gas station problem, so that clearly we can do something to remedy this), so I'm simply wondering: Am I misreading the pseudo-code?

The second implementation is correct (so Theorem 2.2 survives): If the condition $c(v) > c(u)$ causes the inner while to halt, that same value of $v$ will be give the optimal value for every following value of $g$, simply because the condition is independent of $g$.


Solving T(n) = 2T(n/3) + 2 T(2n/3) + n The goal is to get big $\Theta$ for $$T(n) = 2T\left(\frac{n}{3}\right) + 2T\left(\frac{2n}{3}\right)+n$$ I tried two approaches, but both failed:

Recursion tree. We see that
$$\begin{align}
\sum_{i = 0}^{\log_{3}(n)}n2^i & = \Theta(n^{1+\log_3(2)})\\
& \ll T(n) \\[1em]
& \ll \sum_{i = 0}^{\log_{\frac{3}{2}}(n)} n2^i \\[0.5em]
& = \Theta(n^{1+\log_{\frac{3}{2}}(2)})
\end{align}$$
but cannot, as I can see, get $\Theta(T(n))$ exactly.
Akra-Bazzi Theorem. We get through straightforward calculus that $T(n) = \Theta(n^p)$ where $2+2^{p+1} = 3^p$, as far as I can see there is no way to get a closed form for p from this equation (but it gives a numerical approximation consistent with 1, $p$ is about $2.19$ so that is good).

What I want is to find a closed form for $p$, one better than $2+2^{p+1}=3^p$. I believe such a closed form does exist, it might be found with domain transformations or something like that.

This is problem 2(m) from Jeffrey Erickson's notes on recurrences:
http://jeffe.cs.illinois.edu/teaching/algorithms/notes/99-recurrences.pdf

Any help is appreciated.

Completely unscientifically, the 2T (N/3) can be ignored. The 2T (2N/3) doubles whenever N is multiplied by 1.5, which starting with T(1) happens log N / log 1.5 times, so the result is about $2^{\log N / \log 1.5}$ or $N^{\log 2 / \log 1.5}$ which is about $N^{1.709}$. The n that is added is less than this, so $\Theta(N^{1.709})$ is my unscientific answer.

It just so happens that $p = \log 2 / \log 1.5 = 1.709$ also solves your equation $2 + 2^{p+1} = 3^p$. At least up to 9 decimals according to my spreadsheet.


Number of maximal cliques in a ($2C_4$, $C_5$, $P_5$)-free graph So far, I have found out that chordal graphs have linear number of maximal cliques with respect to the number of vertices.
In general case, it is exponential.
I am trying to determine whether the number of maximal cliques in a $(2C_4, C_5,P_5)$-free graph is linear or polynomial with respect to the number of vertices.
In a $(2C_4, C_5,P_5)$-free graph, the largest induced cycle is of length 4, and no two 4-cycles are edge-disjoint.
Is there a paper that mentions such result?

(Answered also on https://cstheory.stackexchange.com/questions/47691/)
A ($2C_4$, $C_5$, $P_5$)-free graph may have exponentially many maximal cliques.
For example, the complement of the disjoint union of $n/3$ triangles with $3^{n/3}$ maximal cliques is $K_1 \cup K_2$-free, and thus has none of $2C_4$, $C_5$, $P_5$ appear as an induced subgraph.
https://doi.org/10.1007/BF02760024
Note: If the complement of a graph has $k$ pairwise independent edges, then they give you $2^k$ maximal cliques. Conversely, it is known that the number of maximal cliques is upper-bounded by a function of the maximum number of independent edges in the complement .
https://onlinelibrary.wiley.com/doi/abs/10.1002/net.3230230308


Asynchronous Encryption with wordlists As I understand it encrypted emails have a high profile (detectable through pgp header / attachment).

Would it be possible to match the encrypted data with a wordlist to hide the fact that the email contains a encrypted message?

I know that the other person would need the same list of words for decrypting and the message would be only a bunch of random words, but the fact that its encrypted world be not as obvious for automated scanning.

EDIT: As pointed out I am referring to steganography to hide from traffic analysis.

Yes, this is possible.  It is called steganography and there are many techniques that can be used -- there is an entire literature on the subject.  You might enjoy reading about it.

It still won't stop traffic analysis.


What units should Shannon entropy be measured in? The only examples I've seen use bits as a measurement of entropy, but all these examples happen to use binary code alphabets. If we wanted to see how well a coding with a code alphabet of length n works, would we measure entropy in units of n?

Or would it make sense to stay using bits if we're comparing codings with binary and n-length code alphabets?

Generally bit was introduced by Shannon in 1948. Using bit instead of any other information measurement unit it's because of convenience any information can be represented by single bit or by set of bits.

I bet you already ran into most popular example which is coin tossing. You can represent head as 1 and tails as 0. You can also use stream of bits as representing more complex information as integer.

  Simple example

  Consider W as information about current week day you might use 7bit length stream as representation of week. Eg Monday would be represented as 1000000 and Wednesday as 0010000. So each bit in stream represents one day.

You should always consider domain for your problem and use bit encoding which fits best. Using code alphabet of length n shows universality of that particular encoding (like ASCII or Unicode).

Another thing is that bit can be efficently represented in low powered (5v) circuits. There exists interference detection and fixing functions for such circuits.

Consider domain different then bit, eg real numbers, and let them represent information using some relation R. Now because real numbers are dense even minimal interference will have impact on end result.


Maximum Spanning Tree vs Maximum Product Spanning Tree So I'm kind of wondering if I'm correct on something relating to an algorithms class. Let's say I want to, for whatever reason, find the maximum spanning tree of a graph such that the edge weight is at maximum instead of minimum.

In addition, let's say I want to find a spanning tree with the maximum product-sum weight (the product of the edges of the spanning tree is at its maximum).

Assuming edge-weights must be greater than 0, would their spanning trees contain the same edges? I'm pretty sure that their spanning trees are equal.

Plus, I also believe that a modified Kruskal's algorithm searching for maximum weighted edges would create these spanning trees since you'd want the largest weights for both types of maximum trees.

Is my thinking correct?

You state several beliefs but no reasoning. In math, if things are true then usually there is a good reason, namely a proof that the thing is true. Don't just make guesses, try to prove that your claims hold.

Regarding your conjecture, consider Kruskal's algorithm, modified so that it arranges the weights in decreasing rather than increasing order. If we apply any monotone increasing function on the weights, the algorithm would make exactly the same choices. Consider what happens when you replace each weight $w$ by its logarithm $\log w$. The weight of a spanning tree containing the edges $e_1,\ldots,e_{n-1}$ is then
$$
\log w(e_1) + \cdots + \log w(e_{n-1}) = \log [w(e_1) \times \cdots \times w(e_{n-1})].
$$
In other words, after replacing all weights with their logarithms, you are actually computing the maximum spanning tree with respect to product. Since both algorithms compute the same spanning tree, your conjecture is correct.


Security Lattice Construction I am having a problem trying to solve a question on a past paper asking to design a security lattice. Here is the question:

  The AB model (Almost Biba) is a model for expressing integrity policies rather
      than confidentiality. It has the same setup as Bell-LaPadula, except that $L$ is now a set of
      integrity levels which express the degree of confidence we have in the integrity of
      subjects and objects. Subjects and data at higher integrity levels are considered
      to be more accurate or safe. The set of subjects and objects may also be different,
      for example, programs are naturally considered as subjects.

  Often, the set $L$ is actually a lattice of levels, with two operations: least
      upper bound $l_1 \vee l_2$ and greatest lower bound $l_1 \wedge l_2$, where $l_1, l_2 \in L$.

  i. Design an example integrity lattice for AB, by combining two degrees of
          data integrity dirty and clean and two means by which a piece of input
          may be received, website (external user input from a web site form) and
          dataentry (internal user input by trusted staff).

I have been looking for an explanation on how to build lattices but can't seem to find one on the internet or in textbooks. Can anyone point me in the right direction?

The way to view the lattice is by taking the two pieces one at a time. Firstly, you have the lattice:
$$
\begin{array}{c}
Clean \\
| \\
Dirty
\end{array}
$$
to capture that Clean data has higher integrity than Dirty data.

Similarly,
$$
\begin{array}{c}
DataEntry \\
| \\
Website
\end{array}
$$
captures that DataEntry data has higher integrity than Website data.

These can be combined (using the product of two lattices) into the following,
which captures all combinations and the relationship between them:
$$
\begin{array}{ccccc}
&& (Clean, DataEntry)  \\
& / && \backslash~~~~~~~~~~~~~~~~~~~~~~~~~ \\
 (Dirty, DataEntry)  &&&  (Clean,Website)  \\
&\backslash &&/~~~~~~~~~~~~~~~~~~~~~~~~~~ \\
&&     (Dirty,Website)
\end{array}
$$
The two middle elements are incomparable.

The paper Lattice-based Access Control Models by Ravi Sandhu gives a good overview of the application of lattices in access control models, including the Biba model.

If you want to learn the general theory about lattices, then Introduction to Lattices and Order by B. A. Davey and H. A. Priestley is a very good starting point.


Multiplication mod 2 without extra registers For an arbitrary bitstring $(x_1, x_2,\ldots, x_n)$ and an $n\times n$ invertible binary matrix $M$ (fixed ahead of time), I would like to construct a circuit $C$ acting on these $n$ bits whose output will be such a bitstring $(y_1, y_2,\ldots, y_n)$ that:
$$
\begin{pmatrix}
y_1 \\ y_2 \\ y_3 \\ \ldots \\ y_n
\end{pmatrix}
= M
\begin{pmatrix}
x_1 \\ x_2 \\ x_3 \\ \ldots \\ x_n
\end{pmatrix} \bmod 2 \ ,
$$
The extra registers are not allowed. The circuit $C$ should only contain $NOT$ and $CNOT$ gates (where $CNOT(x, y) = (x, x+y \bmod 2) $). The matrix $M$ is such that it permits for a reversible calculation.

The lower bound is trivially given by $O(n^2)$ operations. (That's how you would usually multiply matrices, if you had access to the original values of registers all the time. The question, however, is inspired by quantum computation, where one cannot store the initial values, and extra qubits are expensive.)

A known fact from quantum information is that such circuit can be constructed with at most $O(\exp(n))$ gates. The goal is to design it using a sub-exponential number of gates.

Your question is solved by Patel, Markov and Hayes in their paper Optimal synthesis of linear reversible circuits. They mention a simple $\Omega(n^2/\log n)$ lower bound for the worst-case $M$, obtained by counting, and show that it is tight, in the sense that there is an $O(n^2/\log n)$ algorithm for any reversible $M$.