Showing that HALF-2-SAT is in P I need to show that the following problem is in P:
$$\begin{align*}\text{HALF-2-SAT} = \{ \langle \varphi \rangle \mid \, &\text{$\varphi$ is a 2-CNF formula and there exists an assignment} \\
& \text{that satisfies at least half of the clauses} \}\end{align*}$$

I know that 2-SAT is in P, hence it got a decider and I wanted to use it for HALF-2-SAT but got stuck to find how to extract the right half of the clauses that will be satisfied in a polynomial way.

Is there an official way to choose half of the clauses that satisfy the formula?

Is there an official way to choose half of the clauses that satisfy the formula?

There is no official way. As noted by Juho, "any algorithm that you prove correct is acceptable". Moreover, you do not have to choose that half of the clauses explicitly.

Here is the simplest algorithm to decide $\text{HALF-2-SAT}$ that runs in polynomial time. In fact, it runs in constant time. (If the algorithm should verify the given input is valid, it runs in linear time.)

Input: $\varphi$ and $m$, where $\varphi$ is a 2-CNF formula with $m$ clauses.
Output: True if there is an assignment of the variables such that at least $m/2$ clauses become 1.
Procedure: Return true.

Why does the above algorithm work? Here is the reason.

Lemma. Let $\varphi$ be a 2-CNF formula. Then there exists an assignment that satisfies at least half of the clauses in $\varphi$.

Proof. Let $f_0$ assign 0 to all variables. Let $f_1$ assign 1 to all variables. Let $c$ be any one of the clauses in $\varphi$. Suppose variable $x$ appears in $c$.

the literal $x$ is in $c$. Then $c$ becomes 1 under $f_1$.
the literal $\neg{x}$ is in $c$. Then $c$ becomes 1 under $f_0$.

So every clause becomes 1 under $f_1$ or $f_0$.  So the number of clauses is not greater than the sum of the number of clauses that becomes 1 under $f_1$ and the number of clauses that becomes 1 under $f_0$. Hence, at least half of the clauses in $\varphi$ are satisfied under $f_1$ or $f_0$. QED.

Here are several exercises.

Exercises 1. Show the following language is in P:
$$\begin{align*}\text{3-SAT}_{\ge\frac12} = \{ \langle \varphi \rangle \mid \, &\text{$\varphi$ is a 3-CNF formula and there exists an assignment} \\
& \text{that satisfies at least half of the clauses} \}\end{align*}$$

Exercises 2. Show that the following problem is in P:
$$\begin{align*}\text{2-SAT}_{\le\frac34} = \{ \langle \varphi, f \rangle \mid \, &\text{$\varphi$ is a 2-CNF formula and $f$ is an assignment} \\
& \text{that satisfies at most three fourth of the clauses} \}\end{align*}$$

Exercises 3. Let $\varphi$ be a 2-CNF formula such that none of its clause involves only one variable. Then there exists an assignment that satisfies at least three fourth of the clauses in $\varphi$.


In which reference can I find a definition for the equivalence of DFAs? How is the equivalence of DFA defined?  I found the equivalence of states --- James Hein, section 5.3, page 301.  But he doesn't define equivalence between entire automata.  (Ullman and Hopcropft seem to define neither.)

You can find a definition in Automata Theory, Languages and Computation by Hopcroft, Motwani, Ullman, in the fourth chapter.

Here's a link : HMU, the section begins at page 171 of the pdf

Two DFA are said to be equivalent if they accept the same language, and (an equivalent proposition) if they have the same minimal automaton (which is unique).


Is it possible that the subtraction between two undecidable languages is regular? If $L_1$ and $L_2$ are both non-decidable languages (Not decidable, so can be SD
or $\lnot$SD), is it possible that $L_1-L_2$ is regular and $L_1-L_2\neq\phi$, where $\phi$ is the empty set?

What's a good way of tackling this question? Me and some classmates have been stuck on this question for a while, and this was the best we've got:

It should be possible given the following example:

Let $L_1=H\cup a^*$ and $L_2=H$, where $H=\{<M,w>:$ Turing machine $M$ halts on $w$$\}$, so $L_1-L_2=L_1\cap \lnot L_2=(H\cup a^*)\cap \lnot H=\lnot H\cap a^* = a^*$ which is regular. (we are saying $H$ does not contain $a^*$, so $\lnot H$ must contain $a^*$, hence why the intersection gives $a^*$.)

But we are not confident this is correct due to the last part with the intersection does not feel right. What's the answer to this question?

Your example almost works. You need to make sure that the regular part is disjoint from the non-decidable part.

Suppose our alphabet has at least two symbols, say $a$ and $b$. Consider any undecidable langauge $H$, for example the halting set, and define
$$L_2 = \lbrace b w \mid w \in H\rbrace$$
and
$$L_1 = L_2 \cup \lbrace a \rbrace.$$
Now it is obvious that $a \not\in L_2$ because all words in $L_2$ start with $b$. Also, $L_2$ and $L_1$ are undecidable because there are easy reductions from $H$ to them, and back. And of course we have
$$L_1 \setminus L_2 = \{a\},$$
which is decidable. You can make the example more complicated by taking any decidable langauge $D$ and define $L_2$ as before, but change $L_1$ to
$$L_1 = L_2 \cup \{a w \mid w \in D\}.$$
This way $L_1 \setminus L_2$ is computably isomorphic to $D$.


Why is there no extensive Standards Body overseeing ISAs, Bitcodes, Code Representation, etc... as there is in the case of Unicode There exist a vast array of prominent bitcode formats, each suited for their specific task:

LLVM IR:

This format is build around a XML like binary streams model, designed to be used as a common compiler target across a multitude of Architectures and languages.
JVM bytecode:

Java compile target, mainly; increasingly reused as a larger target in that ecosystem.
Khronos Spir-V:

Shader language target, graphics hardware abstraction.
Web Assembly:

Built as a target to better integrate ecosystems and existing code within the browser context.
Specialized: (Ex. Lua and Python Bytecodes):

Interpreters generally execute bytecode during execution whether, explicitly or not.

The hardware/ISA ecosystem is equally split, particularly amoung ARM, i386/x86, x86_64, Microchip/Atmel and now Risc-V.
Fragmentation also exists in the computer graphics industry, which in many ways has outpaced CPU growth in recent times.
Hardware Acceleration Layer/API design is primary split between Khronos and Microsoft, but now apple and Google are joining in; Even in the case of the two leading providers, backwards compatibility has proven to be a difficult problem, leading to increased segmentation and overhead.

I only see these problems getting worse in the future with the current state of traditional Moore's Law, increasing use of accelerators and FPGAs, IoT proliferation, diverse memory types and caching mechanisms, hyperscaling, etc...

In the past, segmentation has been forsean and in the case of character set localization, avoided. This is why the Unicode Consortium was Established, independent of any single company/organization. The Unicode Consortium has managed to standardize over 100,000 character encodings to date and this is virtually universal.

Theoretically I see no reason why this cannot be accomplished in the bitcode/turing realm.

https://www.quora.com/unanswered/Why-is-there-no-extensive-standards-organization-for-instruction-set-architectures-ISA-and-bitcodes-as-there-is-in-the-case-of-Unicode-1

In Response to Community:

@Gilles Unicode acts as a super-set of its predecessor, ASCII; it conforms to UTF-8, UTF-16 and UTF-32 standards. Modern microprocessors are no strangers to expanding type codes in their instruction decoding pipelines. Any machine can emulate larger types than its baseline and architecture level support for this is not uncommon.

Reference:

VLIW Architecture
Unicode Consortium

Unicode is a suitable encoding for most scripts because it includes characters from all the scripts. The analog would be an instruction set architecture that includes instructions from all processors. This would be huge and impractical to implement whether in hardware or in software. It would even be contradictory: how do you reconcile an architecture with 16-bit words with an architecture with 64-bit words? an architecture that allows unaligned word accesses with one that doesn't? an architecture that guarantees the presence of an MMU with one that guarantees that addresses used by software map directly to addresses in physical memory? an architecture that guarantees that all memory accesses take exactly the same amount of time with one that has memory caches?

A realistic ISA can't combine what all the ISA do. You have to make choices, and these choices depend on your objectives. If you're building a processor for real-time processing, a guarantee that memory accesses take the same amount of time is crucial. If you're building a processor for fast numerical or symbolic computation, caching memory accesses is essential for performance. A good instruction set for general-purpose computing is not the same as for graphical rendering, and machine learning calls for yet another approach. There is no one-size-fits-all.

Why isn't there a standard model of vehicle? Why are there so many different models of cars and airplanes and bicycles and motorcycles and helicopters and submarines and so on?


In cache-oblivious algorithms, how is recursive reduction of data performed? From wikipedia:

"Typically, a cache-oblivious algorithm works by a recursive divide and conquer algorithm, where the problem is divided into smaller and smaller subproblems. Eventually, one reaches a subproblem size that fits into cache, regardless of the cache size."

(Is this recursive subdivision manual, or automated? Assuming automated...)

In what way must one produce code in order for it to be suitable for reduction to a cache-oblivious form? Does this rely on the specific implementation of recursive reduction applicable in one's given case?

Another way of putting the question is, would I need to write my code in a special way in order for some automated parser to run through the code and optimise it for cache-oblivious access?

P.S. I'm trying to get a handle on how to approach writing code for practical optimisation using the methods noted in the literature.

From the paper entitled "Cache-Oblivious Mesh Layouts" (Yoon et al):

The cache miss ratio function (CMRF), pl, is a function that relates
the cache miss ratio to an edge span, l. The CMRF always lies within
the interval [0;1]; it is exactly 0 when there are no cache misses,
and equals 1 when every access results in a cache miss. We alter the
layouts using a local permutation that reorders a small subset of the
vertices. The local permutation changes the edge span of edges that
are incident to the affected vertices (see Fig. 3).

The data granularity is repeatedly reduced in software until the "atoms" are small enough to fit cache. The lower bound on data structure granularity is reached as soon as the cache miss ratio reaches zero: beyond this point, further reduction becomes unnecessary. For any given target environment, at runtime, we proceed to reduce the size of data set atoms until they are small enough that the miss ratio reaches zero.
This (often recursive) reduction / linearisation is explored in the MIT OCW lessons on Cache Oblivious algorithms (this lesson and the following one).
Perhaps other approaches exist(?), but it makes sense to me that an algorithm oblivious to block size B would use this sort of approach, in general.


Find all subsets with a given sum How to choose from a set of positive numbers all the subsets that sum to some number x?
For example if the set $S=[1,1,2,3,4,5,6,7]$ and I'm searching for all the subsets that sum to $7$ I would have $[1,6],[1,6],[2,5],[1,1,5],[3,4],[1,2,4],[1,2,4],[7]$.
What I'm trying to do now is to generate all the possible tuples of $\{0,1\}$, so for the set $S$ which has length $7$ I have: $\{0, 0, 0, 0, 0, 0, 0\}, \{0, 0, 0, 0, 0, 0, 1\}, \{0, 0, 0, 0, 0, 1, 0\},...$, multiply the element of tuples of $0$ and $1$ by the corresponding element of the set $S$ and check if the sum is equal to $7$.

I got the idea of the tuples in this question: N subsets with a given sum?
However that problem is slightly different from mine so I was wondering if there's a way to speed things up.

Each subset of $S$ either contains the first element or doesn't. So we can implement a generic enumeration of subsets which match a predicate as (code given in Python but untested):

def subsets_matching_predicate(elements, predicate, included = []):
    if len(elements) == 0:
        if predicate(included):
            yield included
    else:
        for subset in subsets_matching_predicate(elements[:-1], predicate, included):
            yield subset
        for subset in subsets_matching_predicate(elements[:-1], predicate, included + elements[-1:]):
            yield subset

This is essentially what your approach does.

But the sum is monotone, since the numbers are restricted to be positive, so this can be optimised.

def subsets_having_sum(elements, target_sum, included = [], included_sum = 0):
    if included_sum > target_sum:
        return

    if len(elements) == 0:
        if included_sum == target_sum:
            yield included
    else:
        for subset in subsets_having_sum(elements[:-1], target_sum, included, included_sum):
            yield subset
        for subset in subsets_having_sum(elements[:-1], target_sum, included + elements[-1:], included_sum + elements[-1]):
            yield subset

We can also simplify in various ways:

Pass target_sum - included_sum instead of two variables
Accumulate on the way out rather than the way in
Once we hit the target, we don't need to keep going

def subsets_having_sum(elements, target_excess):
    if len(elements) > 0:
        for subset in subsets_having_sum(elements[:-1], target_excess):
            yield subset

        if elements[0] == target_excess:
            yield elements[-1:]
        else:
            for subset in subsets_having_sum(elements[:-1], target_excess - elements[-1]):
                yield elements[-1:] + subset

There's a further optimisation whereby we pre-calculate the numbers which can be reachable with each sublist, and don't bother calling in if they're not reachable. The memory/speed tradeoff depends on the expected length of elements and value of target_sum.

def calculate_masks(elements, target_sum):
    masks_of_interest = (1 << (target_sum + 1)) - 1
    accumulated_mask = 1
    accumulated_mask = []
    for element in elements:
        accumulated_mask = (accumulated_mask | (accumulated_mask << element)) & masks_of_interest
        accumulated_masks.append(accumulated_mask)

def subsets_having_sum_impl(elements, target_excess, masks):
    if len(elements) > 0 and (masks[-1] >> target_excess) & 1:
        for subset in subsets_having_sum(elements[:-1], target_excess, masks[:-1]):
            yield subset

        if elements[0] == target_excess:
            yield elements[-1:]
        else:
            for subset in subsets_having_sum(elements[:-1], target_excess - elements[-1], masks[:-1]):
                yield elements[-1:] + subset

def subsets_having_sum(elements, target_excess):
    masks = calculate_masks(elements, target_excess)
    return subsets_having_sum_impl(elements, target_excess, masks)


How to add decimals to formal grammar? I have a formal language that describes digit production like

<digit> ::= 0|1|2|...|9

and I need to intruduce fraction to write decimals like 3.14 and so on

What did I do:

<frac> ::= <digit><frac> | .<digit><frac> | <digit>

I feel that the .<digit><frac> part is wrong, as every time we go this production we can substitute this part and get more than a single dot for the decimal part, which is wrong? What is the proper way to handle this?

To properly produce a formal grammar, you should designate a non-terminal for each different part of a decimal. Here is a sample grammar in Backus–Naur form that also uses square brackets for optional items.

            <decimal> ::= [<sign>]<nonnegative_decimal>
               <sign> ::= - | +
<nonnegative_decimal> ::= <nonnegative_integer>[<fractional_part>]
<nonnegative_integer> ::= <positive_integer> | 0
   <positive_integer> ::= <nonzero_digit>[<digits>]
    <fractional_part> ::= .<digits>
             <digits> ::= <digit>[<digits>]
              <digit> ::= <nonzero_digit> | 0
      <nonzero_digit> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

It can be made more compact as the following.

            <decimal> ::= [ - | + ]<nonnegative_decimal>
<nonnegative_decimal> ::= <nonnegative_integer>[.<digits>]
<nonnegative_integer> ::= <nonzero_digit>[<digits>] | 0
             <digits> ::= <digit>[<digits>]
              <digit> ::= <nonzero_digit> | 0
      <nonzero_digit> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Please note that the above grammar defines a decimal as a string that starts with a possible sign followed by an integer, possibly followed by a dot and some digits, where only 0,1,2,3,4,5,6,7,8 and 9 are allowed in an integer or digits and where an integer must not start with 0. Many other kinds of decimals are used, too.


Simplifying this Boolean Expression I have to simplify A+C'+B'CD but I don't see how.

I had to deduce the expression starting from a logic diagram in which two AND gates were used for the B'CD part. Seeing the diagram all I can think of is to use one AND gate instead of two, but I don't see how the actual boolean expression can be simplified.

Using the property $X+YZ = (X+Y)(X+Z)$, you can silmplify $C' + B'CD$ as $C' + B'D$.


PDA - Sum of Two Characters = Sum of Two Other Characters For one problem I have to solve, I'm given a Language:

L = {a^r b^s c^t d^u | r+s = t+u}

And from it told to construct a PDA that accepts it. I can construct a PDA for

L1 = {a^r b^s | r,s >= 0}

And for

L2 = {c^t d^u | t,u >= 0}

As they are, essentially, the same language. However, I'm confused as to how I can make sure that the sum of characters in L1 equal those in L2

You can probably build a PDA for the language $\{p^nq^n\mid n \ge 0\}$. If so, you're almost there. Just treat the a's and b's as if they were all p's and the c's and d's as if they were q's, like this (with details elided):

Count the a's and b's by pushing a marker on the stack for each one (making sure that all the a's precede any b).
Match them up with the c's and d's: for each one seen, pop a marker off the stack (again, making sure that the input is correctly formed).
If the stack is empty after having read all the input, accept.


Is time complexity more important than space complexity? I've noticed quite a few cryptographic algorithms speak mainly of the time complexity of an algorithm. For example, with a hashing function h, find x given y = h(x). We normally speak on how long it will take. Or the time to find the discrete log for a public key.

Edit:

While writing this question, I pondered that maybe because for most algorithms in cryptography (that I have seen) , have O(1) space time complexity. i.e. If the solution does not work, we throw it away and encrypt.

Clarification on this will be really helpful.

In fact, when we are talking about algorithms in general, time-complexity is discussed much more frequently than space-complexity. Let me provide a few ideas to support that more general phenomenon which applies to the cryptography as well.

There are much more about time-complexity to talk about in computer science and software industry while space-complexity is more restricted to hardware. It occurs to me that there are over 10 times more tasks/techniques/concepts/results/articles about time-complexity than space-complexity. Overwhelmingly, programming contests are about time-complexity.
Space/memory can be reused easily. Available space can be expanded easily. On the other hand, time needed for computing cannot be shorten that easily. Parallelization helps, but it cannot speed up the serial part of the program. Practically and relatively speaking, we are enjoying the cheap memory now while we are still hungry for computing speed.

Now come to the cryptography side of the question.

As you have observed, most algorithms in cryptography have $O(1)$ space time-complexity. Although space might be critical such as in embedded devices, there is not much value of space-complexity in general.
On the other hand, the time-complexity is the critical factor of a cryptographic algorithm, especially in encryption/decryption. It should produce data fast enough. Authorized users should be able to retrieve the plaintext fast enough while adversaries do not have fast algorithms to decrypt the ciphertext.


n*log n and n/log n against polynomial running time I understand that $\Theta(n)$ is faster than $\Theta(n\log n)$ and slower than $\Theta(n/\log n)$. What is difficult for me to understand is how to actually compare $\Theta(n \log n)$ and $\Theta(n/\log n)$ with $\Theta(n^f)$ where $0 < f < 1$.

For example, how do we decide $\Theta(n/\log n)$ vs. $\Theta(n^{2/3})$ or $\Theta(n^{1/3})$

I would like to have some directions towards proceeding in such cases. Thank you.

$\log n$ is the inverse of $2^n$.  Just as $2^n$ grows faster than any polynomial $n^k$ regardless of how large a finite $k$ is, $\log n$ will grow slower than any polynomial functions $n^k$ regardless of how small a nonzero, positive $k$ is.

$n / \log n$ vs $n^k$, for $k < 1$ is identical to:
$n / \log n$ vs $n / n^{1-k}$

as $n^{1-k} > \log n$ for large $n$, $n / \log n > n^k$ for $k < 1$ and large $n$.


"Mathematical Physics"'s equivalent for Computer Science Mathematical Physics is a well defined scientific fields that deals with the application of mathematics , mathematical tools , and mathematical methods in the theories and the problems of physics.

Is there a well defined scientific field that deals with the application of mathematics , mathematical tools , and mathematical methods in the theories and the problems of computer science ?

When you use mathematics or mathematical models to understand physical nature around us and its dynamics, the mathematics in its association with physical laws become Physics. Similarly, when you leverage mathematics or its models like trees, graph, first-order logic etc to understand computational problems it becomes computer science.


When Huffman coding is inefficient? I have a question regarding the redundancy of Huffman coding. I know that for a general prefix code we have the following inequality:

$$ H(X) \le R \le H(X) + 1 $$

$R$ being the rate (average codeword length) and $H$ is the entropy. Based on this relation, how can we conclude that Huffman coding is very inefficient if entropy of the source is much smaller than 1 bit/symbol?

If $X$ is any non-constant source, then any codeword in any prefix code for $X$ has length at least $1$, and so $R \geq 1$. Therefore if $X$ is a source with very low entropy then there's a large discrepancy between $H(X) \approx 0$ and $R \approx 1$.

As a concrete example, consider a binary source in which the probability of one of the options is $\epsilon$. Then $H(X) = \epsilon \log (1/\epsilon) + O(\epsilon)$ whereas $R = 1$.


On deterministic weighted graph isomorphism from randomized Is there a $O(n^2)$ algorithm to resolve isomorphism between two weighted $n$-vertex graphs? This is a much easier problem than graph isomorphism.

Basically take an real edge weight set $\{w_1,\dots,w_s\}$ where $s=\Omega(n^\alpha)$ where $\alpha\in[0,2]$ and the edge weights are picked uniformly. We can think of the second graph as being generated as follows: Input the weighted first graph to a black box and the black box returns the second graph based on some mechanism.

For every $n$ fix a set of weights.

For every input graphs you assign weights uniformly from a distribution. Then you feed in the input graph, weights and the second graph to the black box and the black box returns you the weighted second graph. Then you have to decide isomorphism on these two weighted graphs. So the probability is over all assignments of weights (the weight set is fixed for every $n$ in some worst case way). If this has an algorithm that is in $\mathsf{BPP}$ then in theory it should be conjecturally derandomizable.

Consider first the case of two colors. We can identify with each vertex $x$ its color distribution $a$, which is the number of edges of color 1. The distribution of $a$ is $\mathrm{Bin}(n,1/2)$, and so if we divide the vertices into bins according to their color distribution, the heaviest bin will contain $O(\sqrt{n})$ vertices with high probability. If we repeat the process, we the heaviest will contain $O(\log n)$ vertices with high probability. Once more, and we expect all bins to have size 1.

What this sketch suggests is that even if you have a constant number of colors (in this case, 8) then with high probability, every vertex will have a unique color distribution (histogram of colors of the edges adjacent to it). This makes graph isomorphism very easy for such graphs.

Of course, this sketch isn't rigorous. To know for sure, you will have to make it rigorous, and find whether it indeed works; perhaps a constant number of rounds isn't enough, but $\alpha\log n$ rounds (as in your case) are.


What is the name of this type of program optimization where two loops operating over common data are combined into a single loop? On an imperative programming language, let us consider the following program:
for i in 0..N { // N is the length of the arrays A, B, C.
  A[i] = A[i] + B[i];
}
for i in 0..N {
  A[i] = A[i] + C[i];
}

This program just sums three arrays $A + B + C$ component-wisely and store it to $A$.
We can easily transform this program into the following equivalent one:
for i in 0..N {
  let tmp = A[i] + B[i];
  A[i] = tmp + C[i];
}

I think the latter code is more efficient than the former because we can decrease the number of memory accesses.
Now I have a question.
What is the name of this type of program transform or program optimization?
Can we also call this deforestation?

It's called "loop fusion".
It's often more efficient, in the sense of doing more work per loop iteration and sometimes (as you say) other advantages. On the other hand, the fused loop in your example may also put more pressure on the CPU's cache prefetch system. So do test it before declaring it more efficient.


Finding a lower bound for the expression $\ln^k(n)$ Problem:
Assume that $k \geq 1$ and $\epsilon \geq 0$, is $\ln^k(n) \in$ $\Omega( n^\epsilon)$?
Answer:
In the special case of $\epsilon = 0$, I claim the answer is no. I suspect the person who wrote this
problem meant to write: assuming $\epsilon > 0$.
I claim that if we differentiate $\log^k(n)$, k times then we get an expression with $n^{-k}$ in it. If
we differentiate $n^{e}$  k times then we get an expression with $n^{\epsilon- 2}$ in it. Let me illustrate
this with an example. Suppose I pick $k = 2$. Then if I differentiate the first expression twice, I get:
$$ \frac{ 2 - 2 \ln(x) }{x^2} $$
When I differentiate the second expression twice, I get:
$$ \epsilon ( \epsilon - 1 ) n ^ { \epsilon - 2 } $$
Hence, I claim the answer is no. Do I have this right?

The notation $\log^k n$ most likely stands for $(\ln n)^k$ (this is a common abuse of notation).
In this case the claim is trivially when $\varepsilon=0$ true since $n^\varepsilon=1$ and $\ln^k n = \Omega(1)$.
For constant $\varepsilon>0$ and $k \ge 1$ you have:
$$
\lim_{n \to +\infty} \frac{\ln^k n}{n^\varepsilon} =
\lim_{n \to +\infty} \left( \frac{\ln n}{n^\frac{\varepsilon}{k}} \right)^k =
\left( \lim_{n \to +\infty}  \frac{\ln n}{n^\frac{\varepsilon}{k}} \right)^k =
\left( \lim_{n \to +\infty} \frac{1}{n \cdot \frac{\varepsilon}{k} \cdot n^{\frac{\varepsilon}{k}-1}}\right)^k
= \left( \lim_{n \to +\infty} \frac{k}{\varepsilon n^\frac{\varepsilon}{k}} \right)^k
 = 0,
$$
showing that $\ln^k n = o(n^\varepsilon)$, and hence that the claim is false.


Curry-howard isomorphism in object oriented programming languages I want to get a better intuition for the curry howard isomorphism, and my intuition is mainly based on object oriented programming languages like JavaScript.

So as an example, I am going to formalize the notion of "topological space" in a hypothetical object oriented programming language with dependent type theory and see if it makes sense:

public class TopologicalSpace
{
    BaseSet:Type
    Topology: (BaseSet -> Boolean) -> Boolean
    public TopologicalSpace(X:Type,T:(X -> 2) -> 2,
         p_axiom1:Axiom,p_axiom2:Axiom2,p_axiom3:Axiom3 )\\constructor
    {
        BaseSet = X;
        Topology = T;
        proof_axiom1 = p_axiom1;
        proof_axiom2 = p_axiom2;
        proof_axiom3 = p_axiom3;
    }

    Axiom1: Topology (function (x:BaseSet) return True) = True
        AND Topology (function (x:BaseSet) return False) = True \\empty set & domain
              \\ are in topology
    public readonly proof_axiom1:Axiom1

    Axiom2: \\\etcetcetc
}

Does this approach make sense? Is there a kind of object oriented type theory + curry howard isomorphism like this?

If you only consider terminating functions, then your axiomatisation works :-) Indeed, terminating functions have a resonable notion of equality:
If their return type has decidable equality then the functions have decidable equality.

Regarding your code, it could be rendered in an OOP-like fashion this way

record TopologicalSpace : Set₁ where

  field
     BaseSet  : Set
     Topology : (BaseSet → Boolean) → Boolean

  Empty    = λ (x : BaseSet) → false
  Universe = λ (x : BaseSet) → true

  field
    axiom1   :       Topology Empty    ≡ true
                AND  Topology Universe ≡ true

This is a real programming language whose functions must always terminate: It is Agda; http://learnyouanagda.liamoc.net/

The source for the code can be found here: https://github.com/alhassy/RandomProgramming/blob/master/Agda/TopologicalSpaces.agda


What is shell expansion in programming language theory? From Bash Reference Manual

  Expansion is performed on the command line after it has been split
  into tokens. There are seven kinds of expansion performed:

  brace expansion
  tilde expansion
  parameter and variable expansion
  command substitution
  arithmetic expansion
  word splitting
  filename expansion

From the programming languages perspective,  are shell expansions of the same kind of pre-defined compiler macros in C?

What is the concept for shell expansions called in programming languages?

Shell languages and scripting languages have specific features adapted to the context of their use. Such features may not exists in that form in more classical programming languages as they would not be inappropriate for their context of use.

A shell language has to assist the user and make him productive in an interactive context, often for commands that are executed only once and then forgotten. Syntactic preprocessing of commands for common needs, use of abbreviation, and such, is part of the interactice help provided.

Programming languages must be often more explicit, more verbose and less context dependent, as they live long and have to be maintained, which requires them to be very readable by a variety of people. Hence, in the context of a programming language, these fonctionalities may be used, but have to be explicitly called as subprograms applied to the concerned data, rather than be implicit in the shell preprocessing of a command to be executed on the spot.


Is the Clique Problem polynomial time reducible to the graph-Homomorphism Problem and if so what does the reduction look like? Is the k-Clique Problem (given a Graph G and a natural number k does G kontain a Clique of size k)
polynomial time reduzible to the graph-Homomorphism Problem (given two graphs, G and H, is there a Homomorphism from G to H)

And if so what would the reduction look like?

Since  i am a little confused by the subject, is the following correct?

A polynomial time reduction from Clique to graph-Homomorphism is a funktion that can be calculated in polynomial time and for which if you input a yes instance of clique it returns a yes instance of graph-Homomorphism, same for no instances.

The $k$-clique problems asks whether there is a homomorphism from the $k$-clique to a given graph. Therefore in principle, given an instance $\langle G,k \rangle$ of $k$-clique, you can just output $\langle K_k, G \rangle$, which is an instance of graph homomorphism.

However, in general $\langle K_k, G \rangle$ could be much larger than $\langle G,k \rangle$, since encoding $k$ takes $\Theta(\log k)$ bits, whereas encoding $K_k$ probably takes $\Theta(k^2)$ bits (depending on your encoding). Assuming that graphs are encoded as adjacency matrices, the solution is to compare $k$ to the number of vertices in $G$. If $k$ is larger than the number of vertices in $G$, then the answer is No, and so you can output a fixed No instance (say $K_2,K_1$). Otherwise the size of the output instance is polynomial in the size of the input instance, and so there is no problem.


Finding combinations of variables that can take value of -1/0/1 that produce sum of 0 with added constraint I have 64 variables that can either take a value of -1, 0, or 1 and I am interested in finding all possible combinations of variables such that I have n variables in each the positive and negative state.

Does anyone know what the best way would be to calculate the full set of combination values that fits this constraint?

Right now I just implemented a simple counting algorithm, but that will take forever since I have to test if there are n positive and negative variables at 3^64 levels, and that is before I even start to evaluate the weighting term I am actually interested in.

There will be ${64 \choose n} \cdot {64-n \choose n}$ such combinations, since there are ${64 \choose n}$ ways to choose a subset of $n$ of the 64 variables to be -1, and then ${64-n \choose n}$ ways to choose a subset of $n$ of the $64-n$ remaining variables to be 1.  Equivalently, this is ${64! \over n!^2 (64-2n)!}$.

You probably won't want to explicitly generate all of those combinations, as it would take exponentially long to do so (as there are exponentially many such combinations).

But if you really wanted to explicitly enumerate all combinations, this formula also highlights the way to do that.  First, enumerate all possible ways to choose $n$ of the 64 variables; there are standard algorithms for how to do that (e.g., https://stackoverflow.com/q/127704/781723, https://en.wikipedia.org/wiki/Combination#Enumerating_k-combinations).  Then, for each such, enumerate all possible ways to choose $n$ of the remaining $64-n$ variables (again, using the same algorithm).  That will give you all ways to choose a combination of the sort you desire.

Still, any time you are enumerating exponentially many possibilities and then doing something to each, you should check whether maybe there's a better way to achieve your ultimate goal without enumerating all of them.  If you want to find the combination that minimizes some cost function, there might be a better way to do that, depending on the cost function.


Deriving the expected number of steps that is taken to perform the k'th operation Consider a datatype whose objects will be sequences of elements that has the following two methods

prepend($x, T$) which will insert an element to x to the beginning of the sequence T

search($T, i$) which returns the ith element in the given sequence

T is a linked list. prepend takes $1$ step. Search takes $i$ steps

Suppose T has exactly one element and a sequence of n operations are performed. You are given that prepend has probability $p$ and search has probability $1-p$ for each operation. The value of $i$ is chosen uniformly from $[1, \dots, T]$

Q) Deriving the expected number of steps that is taken to perform the k'th operation

This would be the average of all possible events so number of search and prepends to the expected length. Expected length is given to be p (k-1). Derived from below

expected length of linked list

search takes i steps (probability 1-p). Prepend takes 1 step (probability is p ).

$E(X) = search(1) + search(2) + \cdots + search((p(k-1)))$

Not sure how to get an exact value for it

Let $N_i$ be the random variable denoting the length of $T$ prior to the $i$th operation. You should be able to calculate $\mathbb{E}[N_i]$.

The expected running time $T_i$ of the $i$th operation is
$$
p \cdot 1 + (1-p) \cdot \frac{1+\cdots+N_i}{N_i} = p + (1-p) \frac{N_i+1}{2}.
$$
Given $\mathbb{E}[N_i]$, you should be able to calculate $\mathbb{E}[T_i]$ using this formula.

I leave you to figure out all remaining details.


Detecting all cycles in un-directed graph I would like to detect all the cycles(non duplicate) in a given graph, I mean if A-B-C-A is a cycle, then A-C-B-A is a duplicate of previous one and need to be considered.I could use DFS and detect a cycle, but what if i want to continue to find other cycles? how would i make any node to be considered for other cycle?

Following is an algorithm better than the brute force search.

Given graph $G$, find the DFS tree $T$ of $G$. We know from the structural property of $T$ that any for edge $(u,v)$ in $G$, we have that either $u$ is an ancestor of $v$ in $T$ or $v$ is an ancestor of $u$ in $T$. Therefore, brute force search for cycles in $G$ only along subsets of the branches in $T$. This is equal to the trivial brute force search if $G$ is a clique but better otherwise.

However, one can hope for better heuristics. For instance, see [1].

[1] Hongbo Liu, Jiaxin Wang: A new way to enumerate cycles in graph. AICT/ICIW 2006: 57.


Generate ordered stream of $n$ random integers in a given range using $O(1)$ space (reference request) I'm looking for a reference to an algorithm that does the following. Given n, and a range [min, max], generate a random ascending stream of n integers i_1, i_2 .. i_n such that min <= i_1 < i_2 < ... < i_n <= max. And this should be done in constant space.

(So I'm looking for a more efficient alternative to the following simple approach: First generate n random numbers in the desired range, then sort them, and then go over the sorted list in order. This needs O(n) space.)

I could swear I saw a paper describing an algorithm that does exactly this. But I can't find that paper again, no matter what I search for. Am I misremembering? Can you help me?

It can be done in $O(1)$ space and $O(n^2)$ time.  Let $X_1,\dots,X_n$ denote the numbers in the stream, in sorted order.  You can calculate

$$\Pr[X_i = x_i | X_1=x_1,\dots,X_{i-1}=x_{i-1}]$$

and then use that to generate the numbers $X_1,\dots,X_n$ one by one.

Here is the derivation.  We have

$$\begin{align*}
\Pr[X_1=x_1,\dots,X_{i-1}=x_{i-1}] &= {{\text{max}-x_{i-1} \choose n-i+1} \over
{\text{max}-\text{min}+1 \choose n}}\\
\Pr[X_1=x_1,\dots,X_{i-1}=x_i] &= {{\text{max}-x_i \choose n-i} \over
{\text{max}-\text{min}+1 \choose n}}
\end{align*}$$

so it follows that

$$\Pr[X_i = x_i | X_1=x_1,\dots,X_{i-1}=x_{i-1}] = {{\text{max}-x_i \choose n-i} \over {\text{max}-x_{i-1} \choose n-i+1}}= \Pr[X_i = x_i | X_{i-1}=x_{i-1}].$$

Here the domain of possible values for $X_i$ is $x_{i-1}+1,\dots,\text{max}$; the probability is zero for other values of $X_i$ outside that domain.

Notice that this probability depends only on $x_{i-1},x_i$, so you only need a constant amount of space: you don't need to remember the entire past history.

Thus, the algorithm becomes:

Pick $x_1$ from the distribution $\Pr[X_1=x_1] = {{\text{max}-x_1 \choose n-1} \over {\text{max}-\text{min}+1 \choose n}}$.
For each $i=2,3,\dots,n$, pick $x_i$ from the distribution for $\Pr[X_i = x_i | X_{i-1}=x_{i-1}]$ given above.

This algorithm requires only $O(1)$ space.  The running time might be $O(n^2)$ (since it might take $O(n)$ time to draw from a  distribution with $n$ possible values).  Perhaps further analysis could reduce the running  time by finding a more efficient way to draw from  these distributions.  For instance, if you could find a way to compute the cdf (cumulative distribution function) for these distributions and evaluate it at an arbitrary $x_i$ in $O(1)$ time, then you could reduce the total running time to $O(n \log n)$ by using binary search at each step to draw from the distribution.  I don't see how to do that myself, but perhaps someone else will.

This might get a lot easier  if you are willing to draw streams of non-decreasing integers rather than a stream of  increasing integers (i.e., allow an integer to be repeated), since the formulas for probability for  drawing with replacement tend to be a lot simpler than those for drawing without replacement.


Proofs using the regular pumping lemma I have two questions:

I consider the following language
$$L_1= \{ w\in \{0,1\}^* \mid \not \exists u\in \{0,1\}^* \colon w= uu^R\}.$$
In other words $w$ is not palindrome with even length. I proved that this language is NOT regular by proving that its complement is not regular. My question is how to prove it using the pumping lemma without using going over the complement.
Let
$$L_2=\{w\in\{0,1\}^* \mid \text{$w$ has same number of 101 substrings and 010 substrings}\}. $$  I proved that this language is not regular by using equivalence classes. How I can prove it using the pumping lemma?

Thanks alot for edit:)

Not all non-regular languages fail the test of the pumping lemma. Wikipedia has an annoyingly complex example of a non-regular language which can be pumped. So even if a language is non-regular, we may not be able to prove this fact using the pumping lemma.

But it turns out we can use the pumping lemma to prove your first language is not regular. I'm not sure about the second.

Claim: $L_1$ is non-regular.

Proof: By the pumping lemma. Let $p$ be the pumping length. (I'm going to use the alphabet $\{a,b\}$ rather than $\{0,1\}$.) If $p = 1$, then take the string $abbaa$, which is in $L_1$ and pump it to $aabbaa$ which is not in $L_1$, so $L_1$ would not be regular.

If $p > 1$, then take the string $a^pbba^{N}$. (We'll figure out what we want $N$ to be later.) Then consider any division of the string into $xyz$ where $x=a^{p-k}$, $y=a^k$, and $z=bba^{N}$.

Now let's pump this string $i$ times. (We'll figure out what we want $i$ to be later.) We get the string $xy^iz$, which gives $a^{p-k}a^{ik}bba^{N} = a^{p-k+ik}bba^{N}$.

Now let's back up. First, we picked $N$. Then, some choice of $k$ was made. Then, we picked $i$. We want to figure out what $N$ to pick so that, for any choice of $k \in [1,p]$, we can choose an $i$ that makes this string a palindrome by making the number of $a$s on the left equal the number on the right. (It will always have even length.)

So we want to always get that $p-k+ik=N$. If we play around with the math, we find that we should pick $N=p+p!$ and pick $i=p!/k+1$.

So to recap, we picked $N=p+p!$ and chose the string $a^pbba^N$. Then some choice of $k$ was made so that the string was made up of $a^{p-k}ybba^N$ where $y=a^k$. Then we picked $i=p!/k + 1$. We pumped the string to get $a^{p-k}y^{i}bba^N = a^{p-k}a^{ik}bba^N = a^{p-k+ik}bba^N$.

But we know that $p-k+ik = p-k+(\frac{p!}{k}+1)k = p-k+p!+k=p+p!$. And $N=p+p!$. So the number of $a$s on both ends is the same, so the string is an even-length palindrome, so it's not in $L_1$, so $L_1$ is not regular.  $\square$


Confusing notation in concatenation of error correcting codes Define an $(m,q,d,k)$-(block) code $C$ to be a code with block size $m$, alphabet $0\ldots ,q-1$, and (non-relative) rate $k$. Meaning: $k=log_q (|C|)$ (if we think of $C$ as a set of legal codewords) ($d$ is the distance which isn't important for this particular question). Such a code could also be thought of as a function:
$$C:[q]^k\rightarrow[q]^m$$
As it takes a word of length $k$ over $[q]$ and encodes it into a word of length $m$.

To my understanding, given an $(m,q,d,k)$ code $C_{out}$ and an $(m',q',d',k')$ code $C_{in}$ such that $q'^{k'}=q$, we can define the concatenation of $C_{out}$ with $C_{in}$ to be a code which takes an input for $C_{out}$, encodes it using $C_{out}$, and then encodes each letter of the resulting word using $C_{in}$.  If this is how a concatenated code truly works, then if we denote the concatenated code $C'$ it should be thought of as a function:
$$C':[q]^k\rightarrow [q']^{m*m'}$$
However, the common notation for such a codes (as can be seen here, for example) is:
$$C_{out}\circ C_{in}$$
Which is exactly in the opposite order to what we would expect if we think about the concatenated code as a composition of functions.

Is there a problem with my understanding of concatenated codes, or is the notation simply confusing? And if my understanding is good, is there a reason the aforementioned notation is common?

You get it right.

The notation $$(C_{out}\circ C_{in})(m)$$
means: "take m, encode it with $C_{out}$ and then encode each symbol with $C_{in}$."
From the point of view of the channel, $C_{in}$ is "closer", hence the inner one; see the figure in the wiki page you refer to.

This is indeed what the wiki page says.

The confusion is probably because you think of composition of functions, where the common notation $(g\circ f)(x)$ means $g(f(x))$. But here we don't have function composition but instead code concatenation, so the $\circ$ operation has a different meaning - it means
$$ C_{in}(c_1), \ldots, C_{in}(c_n)$$
with $(c_1, \ldots, c_n) =  C_{out}(m)$.

Just to complete the picture, concatenation codes where developed by David Forney in 1965, where he named the inner/outer codes that way (again, having the channel  as the center of this point-of-view). See his PHD work and in particular Figure 2 that illustrates this concept (same as in wikipedia).


reducing Max3SAT to Max2sat I want to reduce $MAX3SAT$ to $MAX2SAT$ ...
MAX-n-SAT : given $\phi $ n-CNF formula and number k does $\phi$ has an assignment that satisfy k clauses?

Garey, Johnson and Stockmeyer ("Some simplified NP-complete graph problems") came up (already in 1974!) with a gadget reduction from MAX3SAT to MAX2SAT. Given a 3SAT clause $C = x \lor y \lor z$, they come up with a gadget $G(C)$ consisting of 2SAT clauses on the variables $x,y,z$ as well as some additional variables $V(C)$, satisfying the following property. Given an assignment to $x,y,z$, the maximal number of clauses in $G(C)$ which can be satisfied by an assignment to $V(C)$ is $M_1$ if $C$ is satisfied and $M_2<M_1$ if $C$ is not satisfied.

Try to understand how the existence of this gadget allows us to reduce MAX3SAT to MAX2SAT. Then either try to construct such a gadget, or look it up.


Definition of SAT Problem What is the goal of the SAT Problem?

Check if it is possible to have output '1'?
Above + find the right combination of inputs for that?

Witch one?

Cheers

In computational complexity, we usually think of SAT as a decision problem: given a CNF, decide whether there is a truth assignment that satisfies it. There is also a search version of SAT: given a CNF, either find a satisfying assignment, or state that the formula is unsatisfiable. SAT solvers consider a third version: given a CNF, either find a satisfying assignment, or a proof that the formula is unsatisfiable.

There are several relations between the various versions. First, if you solve the decision version, you can also solve the search version. The idea is to find the lexicographically smallest satisfying assignment. Assuming that the variables are $x_1,\ldots,x_n$, we first substitute $x_1=0$ and check whether the resulting formula is still satisfiable. If so, we continue on to $x_2$. Otherwise, we substitute $x_1 = 1$ (the formula must remain satisfiable) and continue on to $x_2$. After $n-1$ more such steps we uncover a satisfying assignment.

Another relation is that if you can solve the search version that you can also solve the SAT solver version. The idea is that if the algorithm for the search version states that the CNF is unsatisfiable, then the transcript of the algorithm serves as proof that the CNF is indeed unsatisfiable. So these two versions are essentially equivalent.


What does ∈ mean in the exponent? I'm having troubles understanding the following proof:
$$
\begin{align*}
&\text{Proof: } \forall \epsilon \in \mathbb{R}^+, \forall a \in \mathbb{Z}^+, n^\epsilon \gg \log_a(n) \\
&\Longrightarrow \ln(a(n)) = \log_2(e)\ln^2(n) \ll n^{0.01} = \ln(d(n)) \\
&\Longrightarrow a(n) \ll d(n)
\end{align*}
$$
The topic is Big O comparisons. The proof is about $a(n)= n^{\log_2 n}$ and $d(n) = e^{n^{0.01}}$. The proof is very heavy in mathematical notation. I'm not sure what ∈ means in the example.  I know that it denotes set membership in a more usual case, but have never seen it in the exponential position.

That's not $\in$ but $\epsilon$: that is, a lowercase Greek letter epsilon. It's normally written $\varepsilon$ instead for clarity, but this author chose to use the "lunate" form for unknown reasons.

In this case, epsilon is being used as a shorthand for "an arbitrarily small but positive real number". This should probably be explained in the proof, but it's a fairly common shorthand in mathematics (for example, delta-epsilon proofs, floating-point epsilon…).

In other words, it's saying that the log of $n$ is always asymptotically smaller than $n$ raised to any positive power. In the next line it substitutes in a definite value, 0.01, for epsilon.


Can someone give a simple but non-toy example of a context-sensitive grammar? I'm trying to understand context-sensitive grammars.

I understand why languages like

  $\{ww \mid w \in A^*\}$
  $\{a^n b^n c^n \mid n\in\mathbb{N}\}$

are not context free, but what I'd like to know if a language similar to the untyped lambda calculus is context sensitive.

I'd like to see an example of a simple, but non-toy (I consider the above toy examples), example of a context-sensitive grammar that can, for some production rule, e.g., tell whether or not some string of symbols is in scope currently (e.g. when producing the body of a function).

Are context sensitive grammars powerful enough to make undefined/undeclared/unbound variables a syntactic (rather than semantic) error?

My favourite example of a context-sensitive language (CSL) is SAT.  The Landweber-Kuroda Theorem says that CSL = NSPACE$[n]$.  Any SAT instance has a linear-size certificate, so SAT is a CSL.  See my question Context-sensitive grammar for SAT? for references and discussion.

Many other NP-hard languages are also in CSL by the same reason, such as CLIQUE.

There are also fairly natural languages in CSL that are even harder.

However, I am not aware of any way to express an arbitrary CSL as a context-sensitive grammar (CSG), other than to use Landweber's construction in Theorem 3 of his paper.  In this construction, the CSG describes the reverse of the operation of the linear-bounded automaton that recognizes the CSL.  Productions of the CSG describe how a particular state of the machine results from one possible move.  Such a CSG is straightforward translation of the automaton into a grammar, so it is not necessarily going to correspond to language features such as being able to declare variables, but will instead be bogged down by the details of the automaton.

If you insist on a CSG rather than a CSL, and if your actual question is specifically about wanting to see a CSG for a language that involves restricted variable scoping, then Hendrik Jan's answer seems to be a good start.


Confusion about big-O notation comparison of two functions On page 16 of this algorithms book, it states:

  For example, suppose we are choosing between two algorithms for a particular computational task. One takes $f_1(n) = n^2$ steps, while the other takes $f_2(n) = 2n + 20$ steps (Figure 0.2).

He then goes on to say:

  This superiority ... (of $f_2$ over $f_1$) ... is captured by the big-O notation: $f_2 = O(f_1)$, because ...

Now my problem is that in the original quote, he said that $f_1(n) = n^2$ steps and $f_2(n) = 2n+20$ steps, so thus $f_1 = O(n^2)$ and $f_2 = O(n)$ (big-O is defined in Section 0.3). But the second quote above states $f_2 = O(f_1)$, which means $f_2 = O(n^2)$ and contradicts his definition of big-O notation. What have I missed?

The key thing to keep in mind here is that the equals sign in $f = O(g)$ does not behave as an equals sign usually would. The reason is that $O(g)$ is not actually a function but a set of functions. For example, you can think of $O(n^2)$ as being a set which, among many other functions, contains the functions $n$, $5 \sqrt n$, $\log^5 n$, etc. So as the appropriate way to think of $f = O(g)$ is not as equality but instead as being an element of a set: $f \in O(g)$.

So the set $O(n)$ is a subset of $O(n^2)$ since any function that is asymptotically bounded above by a multiple of $n$ is also bounded asymptotically above by a multiple of $n^2$.


Why system calls via interrupts are slow and thus we have SYSENTER/SYSEXIT instructions? As far as I understand we got SYSENTER/SYSEXIT instructions because system calls via interrupts were slow (right? I might be wrong though). Therefore my question is why system calls via interrupts are slow? And how do we optimize them via SYSENTER/SYSEXIT instructions? Thank you

There is the general rule about interrupts being slow, and the particular case of x86 CPUs.

x86 have had several ways to enter kernel mode : Call gates, interrupts. They are complex, microcoded instructions, requiring many register save operation and protection checks. SYSENTER/SYSEXIT are just optimised methods : For example, since the 80286, 4 protection levels were available, but rarely used (except, IIRC, by OS/2 ?) : SYSENTER/SYSEXIT support only ring 0 (user) to ring 3 (kernel)
On many instruction set architectures, software interrupts are used to enter kernel mode from user code. These instructions can be optimised, but, in the simplest implementation, they are handled like external hardware interrupts or MMU faults. They are slow because the pipeline must be flushed, prefetched instructions must be discarded, before jumping to the interrupt vector.


How to prove that 3-coloring is decidable? In order to prove that 3-coloring is decidable, is it sufficient to say:

Each node in the graph has 3 possible colors
Therefore we can enumerate over all $3^n$ possibilities and then check that no two edges connect nodes with the same color

Does that prove that 3-coloring is decidable?  Or do I need to construct a Turing machine for a proper proof?

By 3-coloring I'm talking about the graph coloring problem; i.e. assign one of 3 colors to each node in an undirected graph such that no two adjacent nodes have the same color.

It depends entirely on what level of formality you're aiming for. The informal description of an algorithm in your question is quite enough to convince me that 3-colourability is decidable. If you wanted to be a bit more formal, you could give pseudocode. If you wanted to be more formal still, you could describe a Turing machine in English. If you wanted to be even more formal, you could write down the full description of the Turing machine and prove that it really does decide 3-colourability.

Having said that, of the options I've listed, it's way more likely that there'd be an error in the description of the Turing machine or in its correctness proof! So it's not clear which proof would be the most believable.


Find hamilton cycle in a directed graph reduced to sat problem I need to find a Hamiltonian cycle in a directed graph using propositional logic, and to solve it by sat solver. So after I couldn't find a working solution, I found a paper that describes how to construct a CNF formula to find an Hamiltonian path:

Xi,j - node j is in position i in the path

List of constraints:

Each node j must appear in the path
x1j ∨ x2j ∨ · · · ∨ xnj - for every node j
No node j appears twice in the path ¬xij ∨ ¬xkj for all i, j, k with i 6= k.
Every position i on the path must be occupied - xi1 ∨ xi2 ∨ · · · ∨ xin for each i
No two nodes j and k occupy the same position in the path - ¬xij ∨ ¬xik for all i, j, k with j != k
Nonadjacent nodes i and j cannot be adjacent in the path - ¬xki ∨ ¬xk+1,j for all (i, j) !∈ E and k = 1, 2, . . . , n − 1.

My question is, how can I find Hamiltonian cycle using these constraints? I understand that I need to check if there's a cycle (v1==vn), that's one thing (But I got constraint 2). Second, it's a directed graph and I don't know how can I assure that the vertices would be in the right order of the edges, I thought about this:

Every two nodes must have edges -  Xki ^ Xk+1j for each (i,j)∈ E and k = 1, 2, . . . , n − 1.

But it doesn't seem to work, any help would be appreciated.

EDIT

What I did was to add another constraint -

No edges from the set: (i,j)!∈ E that are the last and the first

Just add the constraint that $x_{1j}=x_{nj}$ for all $j$, and make a special exception to constraint 2 so that you omit constraint 2 in the case where $i=1$ and $k=n$.

Everything works fine for a directed graph.  You just need to interpret constraint 5 appropriately.


Enumerate all solutions to integer programming problem How can I list all feasible solutions to an integer program?  Is there an algorithm whose running time is reasonably related to the total number of such solutions?

It's possible to enumerate all solutions, using a recursive algorithm that repeatedly invokes an integer programming solver.  Basically, at each step, you pick a variable, find its range of feasible values, partition its range into two subranges, and then recursively enumerate solutions that fall into each subrange.

In pseudocode, the algorithm looks like this ($\mathcal{P}$ is an integer programming instance):

EnumSolns($\mathcal{P}$, $M$):

Find a variable $x$ mentioned in $\mathcal{P}$ but not in $M$.  (If no such variable exists, find any solution to $\mathcal{P}$, output it, and return.)
Let $a$ denote the smallest feasible value for $x$ (found using a call to the IP solver).  Let $b$ denote its largest feasible value (another call to the IP solver).
Recursively call EnumSolns($\mathcal{P} \cup \{x=a\}$, $M \cup \{x\}$).
If $a<b$, recursively call EnumSolns($\mathcal{P} \cup \{a+1 \le x \le b\}$, $M'$) where $M'=M \cup \{x\}$ if $a+1=b$, or $M'=M$ otherwise.

To enumerate all solutions to an integer programming problem $\mathcal{P}$, call EnumSolns($\mathcal{P}$, $\emptyset$).  If $s$ denotes the total number of solutions and $n$ the number of variables, the running time will be at most $O(ns)$ calls to the IP solver.

In practice, various optimizations may be possible.  Some IP solvers support pushing and popping inequalities, and can remember facts that were learned during a search for the previous system of inequalities and make use of them after pushing another inequality; this may speed up this algorithm substantially.

For a 0-1 integer program, there is a simpler recursive algorithm:

Enum01Solns($\mathcal{P}$, $M$):

If $\mathcal{P}$ is not feasible (determined with a call to the IP solver), return.
Find a variable $x$ mentioned in $\mathcal{P}$ but not in $M$.  (If no such variable exists, find any solution to $\mathcal{P}$, output it, and return.)
Recursively call Enum01Solns($\mathcal{P} \cup \{x=0\}$, $M \cup \{x\}$) and Enum01Solns($\mathcal{P} \cup \{x=1\}$, $M \cup \{x\}$).

If you just want to count the number of feasible solutions to the integer program, without listing them, see Finding all solutions to an integer linear programming (ILP) problem.


Given an algorithm, do worst case time complexity "class" vary with array and linked list? My intuition says that I can make a sorting algorithm(may be a strange, not an useful), such that with array it have different worst case time complexity class and linked list(assuming time complexity of operation performed in linked list are same as conventionally used) with different complexity class.
But what about the sorting algorithms which are conventionally used(may be the algorithms in CLRS)?
I am assuming the implementation done on RAM model and by class I mean the set $\theta(f)$ with f as worst case running time of the algorithm

Note that complexity classes are classes of problems, not classes of algorithms. Specifically, complexity classes are classes of problems that can be solved within particular resource bounds by some algorithm.  So, for example, sorting is in polynomial time because there is at least one algorithm that sorts with this resource bound. (In fact, you probably know many algorithms that do this.)

When it comes to comparing different algorithms for solving the same problem, yes, they may have different resource usage. The fact that you have random access to the elements of an array but not to a linked list means that you can probably design more efficient algorithms based on arrays compared to those based on linked lists. And note that, by using different data structures, they are different algorithms: they involve different computational steps.

Note also that all of this is dependent on your model of computation. For example, if you're solving computational problems using Turing machines, then arrays and linked lists are essentially the same thing, because we can only access the array by moving the tape head sequentially through the elements. Typically, though, when analyzing actual algorithms, we use models of computation, such as the random access Turing machine, that correspond more closely to actual computers.


Resolution exponential lower bound... alternative proofs? I am reading the Resolution proof system exponential lower bound via Haken's bottleneck method for the Pigeonhole Principle as presented in Arora and Barak's Computational Complexity: A Modern Approach, Chapter 15. However, I don't like how the proof is presented in the book and I am having some difficulties following it.

Does somebody know of alternative sources where this same proof is presented? I know there are different techniques to show exponential lower bounds for Resolution, but I want something based on the Pigeonhole Principle. It's just that the phrasing in this book is truly confusing.

If you don't like the presentation of Arora and Barak, you can always take a look at Haken's original paper.

The modern approach to Resolution lower bounds is, however, via Resolution width, as worked out in a classical paper of Ben-Sasson and Wigderson. You can also find expositions in various lecture notes, for example by Jakob Nordström.


How can I complete my derivation of an algorithm to solve Sudoku puzzles from my formalisation of the rules? I'm hoping to design and implement an intuitive algorithm that solves 9x9 Sudoku puzzles. I want to do this by first formalising the basic rules of the puzzle, and then deriving principles from these that when followed should be sufficient for solving the problem. I have reproduced my (very rough) work below.

Rule 1: Each box must contain one instance of each of the numbers 1 to 9:
----- At least one instance: If (i, j) is only possible location of v in box b, then val(i, j) = v
----- At most one instance: If val(i, j) = v in box b, then for all (i2, j2) in box b, if (i != i2 || j != j2) then val(i2, j2) != v

Rule 2: Each row must contain one instance of each of the numbers 1 to 9:
----- At least one instance: If (i, j) is only possible location of v in row r, then val(i, j) = v
----- At most one instance: If val(i, j) = v in row r, then for all (i2, j2) in row r, if (i != i2 || j != j2) then val(i2, j2) != v

Rule 3: Each column must contain one instance of each of the numbers 1 to 9:
----- At least one instance: If (i, j) is only possible location of v in column c, then val(i, j) = v
----- At most one instance: If val(i, j) = v in column c, then for all (i2, j2) in column c, if (i != i2 || j != j2) then val(i2, j2) != v

Rule 4: Each cell must contain exactly one number:
----- At least one number: If (i, j) cannot contain any value except v, then val(i, j) = v
----- At most one number: If val(i, j) = v1 && val(i, j) = v2, then v1 = v2

However, I have run into a problem. Having solved Sudoku puzzles of various difficulties myself, I am aware of other principles that may need to be followed to solve a given puzzle. For instance:

----- If v must occur in one of two or three cells in box b, and these cells fall in the same row r, v cannot occur anywhere else in r.
----- If v must occur in one of two or three cells in box b, and these cells fall in the same column c, v cannot occur anywhere else in c.

These examples look like weaker versions of principles I have already written above, but I am having a hard time trying to derive them from the rules, since I want to be rigorous rather than simply adding principles ad hoc.

If anyone could give me a hand by showing me how I can go about deriving these more complex principles rigorously from the rules (ensuring that nothing is missed), I would be grateful.
Thanks.

One method of dealing with these, somewhat, emergent rules is constraint solving. You can iterate through each cell and place constraints on other squares based on that cell.

For example, if a square is 3, you can place a "cannot be 3" constraint on all other squares in its row, column, and 3x3 box. The two examples you provided can be solved once you place all the constraints, and look at what options are available.

This sort of method is very similar to what you would do when solving a sudoku puzzle when you write down the possible numbers in each square, and fill a box in when there is only one possibility.


change the info part of each node in binary tree i have a binary tree.

         2
       /   \
      3     4
     / \     \
    5  1      8
     \       /
     6      9

I want to change the info part of each node such that the

nodeinfo = nodeinfo + nextInorderNodeInfo

so the actual inorder traversal

5, 6, 3, 1, 2, 4, 9, 8

will change to

5+6,6+3,3+1,1+2,2+4,4+9,9+8,8+0

11, 9,  4,  3,  6,  13, 17, 8

i need to write a function that will modify the binary tree info parts of each node.

i have done the following

calling

change(root,NULL);

function definition

void change(node* n, node *k)
{
 if (n)
  {
    if (n->left) change(n->left,n);
    if (n->right) change(n,n->right);
    n->info + = k->info;
  }
}

in this way i am not able to modify the nodes that are right hand leaf nodes.

can someone give the correct solution..???

thanks in advance

In my point of view, since you want to use the next info in the inorder traversal, you have to do a function that traverse you tree backward for this order.

    int change(node* n,int next){
     int k;
     k=next;
     if(n){
      if(n->right) k = change(n->right,next);
      if(n->left) change(n->left,n->info);
      n->info += k;
     }
    }

That way, calling

     change(root,0)

You have next that is the info of the next node in your order.

I hope I didn't made a mistake and that it help.


Feynman finite state machine In his lectures on computer science, Feynman talks about finite state machines:

he present a simple delay finite state machine

  Let me now give a specific example of an FSM that actually does
  something, albeit something pretty trivial - a delay machine. You feed
  it a stimulus and, after a pause, it responds with the same stimulus.
  That's all it does. Figure 3.4 shows the "state diagram" of such a
  delay machine.

I just don't see the utility of using two states here, why not just use a machine with one state?

Your machine outputs the character it just received; Feynman's outputs the previous one.

More specifically, when Feynman's automaton receives the sequence of stimuli $s_1, s_2, \dots$, its output is $x, s_1, s_2, \dots$, where $x=0$ if the automaton starts in state $1$ and $x=1$, otherwise.  Your automaton outputs $s_1, s_2, \dots$ given the same sequence of stimuli.


Combinatorial Problem similar in nature to a special version of max weighted matching problem I have a problem and want to know if there is any combinatorial optimization that is similar in nature to this problem or how to solve this special version of the max weight matching problem.
I have a general graph $G(\mathcal{V},\mathcal{E},\mathcal{W})$. I want to find a maximum weight matching of the graph $G$ that must cover a certain subset of vertices and has a specific size. For example, if I have a graph with eight vertices, I want to find a max weighted matching that must cover the subset of vertices $\mathcal{V}'=\{1,2,3\}$ and the size of the matching is $\lceil{|\mathcal{V}'|/2}\rceil$. So one more vertex needs to be chosen that maximizes the weighted matching. How to find the optimal solution in polynomial time if possible?

Maximum Weight Matching algorithms are incremental, so to achieve a maximum weight matching of a bounded size, just stop after so many iterations. To achieve the other constraint, For each terminal vertex in $\mathcal{V}'$, increase the weight of each incident edge by a huge constant amount $U$. Try to prove that this answers your question (note that edges incident to two terminals have to be increased twice to keep the total increase constant in all valid solutions).
Note. It might help in the proof to distinguish different cases according to the size of $\mathcal{V}'$ compared to $k$ (the size of the matching).


Union of regular languages that is not regular I've come across that question :
"Give examples of two regular languages which their union doesn't output a regular language. "

This is pretty shocking to me because I believe that regular languages are closed under union. Which means to me that if I take two regular languages and union them, I must get a regular language.

And I think I understand the proof of that : In my words, if the languages are regular, then there exist automatas that recognize them. If we take all the states (union), and we add a new state for the entry point, and we modify the transition function for the new state with epsilon, we are ok.  We also show that there exist a path from every state etc.

Can you tell me where I'm wrong, or maybe another way to approach the question.

Source of the question, exercise 4, in french.

Also, the same question is asked with the intersection.

There's a significant difference between the question as you pose it and the question posed in the exercise. The question asks for an example of a set of regular languages $L_{1}, L_{2}, \ldots$ such that their union
$$
L = \bigcup_{i=1}^{\infty}L_{i}
$$
is not regular. Note the range of the union: $1$ to $\infty$. Regular languages are closed under finite union, and the proofs runs along the lines that you sketch in the question, however this falls apart under infinite union. We can show this by taking $L_{i} = \{0^{i}1^{i}\}$ for each $i$ (with $\Sigma = \{0,1\}$). The infinite union of these languages of course gives the canonical non-regular (context-free) language $L = \{0^{i}1^{i}\mid i \in \mathbb{N}\}$.

As an aside, we can see easily where the normal proof fails. Imagine the the same construction where we add a new start state and $\varepsilon$-transitions to the old start states. If we do this with an infinite set of automata we have build an automata with an infinite number of states, obviously contradicting the definition of a finite automata.

Lastly, I'm guessing the confusion may arise from the phrasing of the original question, which starts "Donner deux exemples des suites de langages...", which is (roughly, my French is a bit rusty, but externally verified!) "Give two examples of sequences of languages...", rather than "Give two examples of languages...". An incautious reading may mistake the second for the first though.


Can we write algorithms without conditional statements? Regarding turing completeness, i read that for a language/machine to be turing complete it is required that it has some sort of conditional.

Consider the factorial problem, we would typically define the algorithm as

Solution 1.

int fact(int n)
{
if n == 0 then
 return 1;
else
 return n*fact(n-1);
}

An alternative would be to define the function fact as

Solution 2.

int fact(int n)
{
 if n == 0 then return 1;
 elseif n == 1 then return 1;
 elseif n == 2 then return 2;
 elseif n == 3 then return 6;
 ....
 all cases define as above
}

Also, another solution would be to have functions like:

Solution 3.

int fact0()
{
return 1;
}

int fact1()
{
return 1*fact0;
}

int fact2()
{
return 2*fact1;
}

int fact3()
{
return 3*fact2;
}

Then we would have an array of function pointers p which we would have to index according to the factorial we want to determine, such that p[0] points to fact0, p[1] points to fact1, and so forth.

I know that this might sound dumb, but it actually works! What makes solution 1. a valid argument to show that conditionals are required to compute the factorial?

Some additional thoughts on my part:

Is solution 1 the only true "algorithm"? Because the other 2 solutions to not seem to "compute" anything
Are conditionals required only because we don't know the results (or execution steps) of functions beforehand?

Here is a Turing complete "programming" language. It has just two constants, called $K$ and $S$, and one operation called "application", written $x \cdot y$. The two constants satisfy the rules
$$(K \cdot x) \cdot y = x$$
and
$$((S \cdot x) \cdot y) \cdot z = (x \cdot z) \cdot (y \cdot z).$$
This is known as a combinatory algebra and is well known to be Turing complete. There is an actual programming language based on $S$ and $K$, called unlambda. I think we can agree that there is no builtin conditional. Of course, since this language is Turing complete, it can also simulate conditional statements.


Average-case analysis of linear search given that the desired element appears $k$ times The problem below is adapted from CLRS Problem 5-2 "Searching an unsorted array":

  Consider a deterministic linear search algorithm which searches an array $A$ for $x$ in order, say $A[1], A[2], \ldots, A[n]$, until either it finds $A[i] = x$ or it reaches the end of the array. Assume that all possible permutations of the input array are equally likely.

  Suppose that there are $k \ge 1$ indices $i$ such that $A[i] = x$. What is the average-time running time of this algorithm?

Let $X$ be a random variable denoting the number of comparisons.

$$
\begin{align*}
  E(X) &= \sum_{i=1}^{i=n-k+1} i \cdot \Pr(X = i) \\
       &= \sum_{i=1}^{i=n-k+1} i \cdot \left(\frac{n-k}{n} \cdot \frac{n-k-1}{n-1} \cdot \frac{n-k-2}{n-2} \cdot \cdots \cdot \frac{n-k-i+2}{n-i+2} \cdot \frac{k}{n-i+1}\right)
\end{align*}
$$

How to evaluate this summation? Or is there a simple solution to this problem?

Note that when $k=1$, $E(X)$ is $\frac{n+1}{2}$. When $k=n$, $E(X)$ is $1$.


What is the order of the Pancake graph in Given example & what are the properties of Pancake graph? Pancake graph have least diameter & degree (log n/ log log n)

pancake Graph with order-2 will be one single line with two nodes, labeled with permutation of node {12, 21}.

pancake Graph with order-3 will be one single line with one hexagonal, labeled with permutation of node {123, 132, 213, 231, 312, 321}.

Similarly for order-4 graph will be with 4-hexagonal.

This graph is in three dimension or four dimension?
if this graph is in four dimension, then how graph will look like in three dimension?

Based on the example I infer the following structure.

The pancake graph seems to be defined with flipping pancakes in mind. For order $n$ we take all $n!$ permutations of the numbers $1,\dots,n$ as vertices of the graph. The vertices represent orderings of the pancakes, with the topmost pancake listed first, and the other pancakes are listed from top to bottom. The edges represent flips. Take any first $k>1$ numbers in a vertex, and reverse that prefix. An edges is added between those to vertices.
Thus $i_1, \dots, i_k, i_{k+1}, \dots, i_n$ flips to $\overleftarrow{i_k, \dots, i_1}, i_{k+1}, \dots, i_n$.

With $n=3$ there are obviously $3! =6$ vertices. $123, 132, 213, 231, 312, 321$. Each node has degree 2 (i.e., has two neighbours) as I can flip topmost 2 pancakes or all 3 of them. From $123$ I thus have edges to $213$ and $321$. The other edges follow the same rule.

Your example figure has missing edges. All vertices should have three neighbours for $n=4$. So $1324$ should also be connected to $4231$ flipping all the pancakes.

The above diagram have dimension 4.

PS. The pancake graph is important in the context of "sorting by reversal", for instance giving bounds on the number of steps to sort any permutation into the identity permutation. This bound is of course the diameter of the pancake graph. The field has a famous paper by Papadimitrou and Gates (of Microsoft fame).


Number of probes in a successful search in open address hashing Given an open-address hash table with $\alpha$ < 1, the expected number of probes in a successful search is at most $\frac{1}{\alpha}\ln\frac{1}{1-\alpha}$

I read this in a book and the proof starts by saying

Searching for k follows the same probe sequence as inserting it. If $k$ is the $i+1$th key inserted into the table, then $\frac{1}{1-\frac{i}{m}}$ is the maximum expected number of probes for the search.

However I don't understand how $\frac{1}{1-\frac{i}{m}}$ gives the number of maximum probes needed. Imagine we have $n=5$ and $m=10$ with linear probing. Now if we want to insert the 6th key, based on the fraction above it should take us at most $\frac{1}{1-\frac{5}{10}}=2$ probes. However imagine if slots 0 through 4 were occupied in our table and we start at index 0, then I guess it would take 5 probes to find an empty slot, right?

You are almost right about "5 probes". It will take, in fact, 6 linear probes to find an empty slot if the probe starts at index 0 of a table with slots 0 through 4 occupied (and slot 5 available). They are 5 failing probes and 1 successful probe at last.
However, you are, apparently, skipping the meaning of the word "expected". That word here means "on average" basically.

While the number of probes can be as big as 4 sometimes, it can be as low as 1 many times as well. So it is not surprising the expected number of probes can be as low as 2.
To be exact and rigorous, the phrase "expected number" as in "the expected number of probes" and "the maximum expected number of probes" has a specific meaning defined in mathematical terms.

The expected value of a discrete random variable $X$ is $E[X]=\sum_xx\cdot \text{pr}\{X=x\}$, where $\text{pr}\{X=x\}$ is the probability of $X$ taking value $x$.

"The expected number of probes" is the shorthand for "the expected value of the discrete random variable that stands for the number of probes." You can understand it simply as "the average number of probes".
I would recommend you read sections in the textbook you are reading that introduce or review related concepts. Or section 3, Discrete random variables in Appendix C of the book CLRS.


What happens with trios, full trio, (full) semi-AFL, (full) AFL if we require closure under intersection? Wikipedia says:

  A trio is a family of languages closed under e-free homomorphism,
  inverse homomorphism, and intersection with regular language.

  A full trio, also called a cone, is a trio closed under arbitrary
  homomorphism.

  A (full) semi-AFL is a (full) trio closed under union.

  A (full) AFL is a (full) semi-AFL closed under concatenation and the
  Kleene plus.

I am wondering if the four concepts are required to be closed under intersection with regular language, not  intersection with languages in the same family?
why are intersection with regular languages required, not intersection?
I wonder what the concepts are if changing closure under intersection with regular language, to closure under intersection with languages in the same family?

I asked these because I saw that the recursively enumerable languages, recursive languages, context-sensitive languages, regular languages are closed under intersection with languages in the same families, while context-free languages are not.

Because it is a very natural set of operations: the full trio operations (morphism, inverse morphism, intersection with regular languages) exactly corresponds to closure under finite state transductions.

We can formulate results for such nice families.
Requiring too many properties would exclude some families of languages.
Who wants to miss the context-free languages?

Likewise the Boolean operations (intersection, union, complement) form a nice set, but we do not always require them.

The notion "intersection closed full AFL" is well studied.


How does interpreting a script work? Suppose I have a script (.vbs, for example) that is stored in a file. How does the code in the file get converted into machine instructions?  What is between the vbs file and the processor?

"Scripting" languages are typically interpreted, not compiled.  That means that there will be a program called the "interpreter" for that language, which reads the programs written in the language, and executes them. You can start reading about interpreters from the Wikepedia entry:

http://en.wikipedia.org/wiki/Interpreter_(computing)

A compiler, on the other hand, translates a program in the programming language into machine language, and lets the CPU execute the machine language program.  The only reason for compiling instead of interpreting is for speed.  The CPU can typically execute the translated machine language program about 10-100 times faster than any interpreter.  The reason is that the CPU is implemented in hardware.  Otherwise, there is nothing that a CPU can do that a program can't.

Interpreted programs runs slow as compared to compiled ones due to the difference in execution process.

Scripting languages are usually used for expressing high-level operations.  For such things, the speed advantage of the CPU becomes much less significant.  So, interpreting them can be competitive to compiling them.


Is there a known algorithm for computing the n-th Turing machine directly? Let us define a Turing machine by a machine description that is a string of symbols produced by some numerical encoding. For example, a Turing machine $M_1$ can be represented by 9,900,599 ([0 0 halt], where halt = 5 and the start and end of an instruction is 99). A standard enumeration consists of all possible Turing machines.

If given a number $n$, is there a known algorithm out there for producing the $n$th Turing machine ($M_n$) in the standard enumeration?

Generate all strings in order, and keep track of which of them correspond to valid encodings. One you have seen the $n$th one, output it.

There are probably more efficient algorithms, but it depends on your exact encoding. Standard combinatorial enumeration techniques might suffice.


Find n-th number in a number system with only 3 and 4 Given a number system with only 3 and 4. Find the nth number in the number system.

There is a solution given here but its very vague without explaining the mathematics/ concept behind it. Can someone please help me derive the logic for framing an algorithm for this question?

One approach that crosses my mind is, we can think of this number system as also a binary one ( in 3 and 4, instead of 1 and 0)
Thus, we could possibly convert the nth number to its corresponding binary format and replace 0 with 3 and 1 with 4. One problem here though is that say the nth number is 333. This in the regular (0 and 1) binary system would be 000 = 0, which evidently is wrong since the nth number is not 0.

You're on the right track, it is similar to binary in a way.

The first step to coming up with an efficient solution is to recognize that to convert a number from the $3,4$ system to decimal, you can treat $3$'s like a $1$ in binary, they have a value equivalent to $2^n$ where $n$ is the position of the digit, starting from the right $n$ starting at $0$.  Thus $3 \equiv 1$, $33 \equiv 3$, $333\equiv 7$, etc.

A $4$ has a value equivalent to $2^{n+1}$ starting from the right $n$ starting at $0$, so $4\equiv2$, $44 \equiv 6$, etc.

Because of the similarity to binary, we can convert our input (the decimal number) to binary, and then convert that to $3,4$.  To do so, we can use the following algorithm.

Given a binary number, iterate through the digits from right to left.

If the digit encountered is a $1$, place a $3$ for that digit in the result.
If the digit encountered is a $0$, and there are more digits following, place a $4$ for this digit in the result, and for any consecutive $0$'s, place a $3$ for those digits until a $1$ is encountered.  When a $1$ is encountered following a $0$ or series of $0$'s, if there are more digits following, change this $1$ to a $0$, and repeat step $2$ as if this were the first $0$ you've encountered.  When a $1$ is encountered and no more digits are following it, do nothing and return the result.

This reason this works is the following

Step $1$ uses the fact that $3$ has the same value in $3,4$ as $1$ does in binary.
Step $2$ is necessary because in $3,4$ there is no $0$ value for any digit.  Using the fact that $2^n = 2^{n-1} \times 2 = 2^{n-1} + 2^{n-1}$ we convert a $1$ followed by $n$ $0$'s to its equivalent form in $3,4$ of $n-2$ $3$'s followed by a $4$. The first $3$ has a value of $2^{n-1}$ and the remaining $3$'s and $4$ sum up to $2^{n-1}$.

This algorithm is roughly $O(\log n)$.


Strongly connected orientations of undirected graphs I'm trying to prove the following.

  There exists a strongly connected orientation of a connected, undirected graph $G$ if, and only if, $G$ has no bridge.

(An orientation of an undirected graph is a directed graph made by replacing each edge $uv$ with exactly one of the directed edges $(u,v)$ and $(v,u)$; a directed graph is strongly connected if it contains a directed path from $u$ to $v$ for every pair of distinct vertices $u$ and $v$; a bridge is an edge whose deletion disconnects the graph.)

I can prove just one side.
Assume that there is no bridge in the graph. So, for vertices $u$ and $v$, we can remove the edge which is between them and still there are(is) some paths(path) in the graph which we can reach $v$ from $u$ (so still the graph is connected). Because there is no bridge in the graph and every pair of vertices are reachable from the other without the edge of between them, we can convert the undirected graph to directed graph.

how about the other side? how can I prove that?

Can I say that, because the graph is undirected and it can be converted to a digraph, for each arbitrary pair of vertices $u$ and $v$ there is a path (or maybe some paths) which we can reach $v$ from $u$ and vice versa except the directed path of between them (the edge between them). So we can remove the directed path of between them. So there is no bridge edge in the graph.

If $uv$ is a bridge then any orientation of $G$ either includes the edge $u\to v$ and has no path from $v$ to $u$, or vice-versa.

If $G$ has no bridge, then it is $2$-connected. A graph is $2$-connected if, and only if, it can be decomposed as $C\cup P_1 \cup\dots \cup P_k$ where $C$ is a cycle and each $P_i$ is a path (possibly just a single edge) that intersects $C\cup P_1\cup\dots\cup P_{i-1}$ at both its endpoints and nowhere else. Now construct your strongly connected orientation from this decomposition.


How to extend a hash function to manipulate longer integers? Carter and Wegman introduced in the paper Universal Classes of Hash Functions the $H_{1}$ universal class of hash function. This is essentially the function
$h_{a,b}(x) = ((a\cdot x+b)\mod p)\mod m$. I am using here the more common notation from CLRS book respective description, and not from the paper.

Some notation:

$x$ is the input to hash function (the key) and takes values in $\{0..u-1\}$
$p$ is a prime $\geq u-1$
$a$ is a random number in $\{1..p-1\}$
$b$ is a random number in $\{0..p-1\}$
And obviously the outputs of hash function are in $\{0..m-1\}$

The problem is that if key word $x$ is large enough, the multiply and add operation involved in the hash function maybe lead in an overflow.
For example if $u= 2^{32}$, $x= 2^{32}-1$, then we cannot hold the outcome of $a\cdot x + b$ in a 32-bit word. But even if we can (using 64 bit word) the least prime $p$ we can use is $4294967311$ which can be represented by 34 bits. In that case $a$ and $b$ will possibly have values of 34 bits long, so a 64 bit word can't hold the outcome of $a\cdot x + b$ leading in an overflow.

The authors of the paper describe a way to manipulate longer integers in proposition 8 and the following paragraph, using hash functions working with shorter integers.

Can anyone please demystify the way we can extend this function to manipulate longer integers and why this is working? The paper can be found  here here

I believe Schrage's method is exactly what you are looking for.

But for a general method of computing $ax + b \bmod m$ where $a, b, x, m$ all fit in a single CPU word and all are unsigned values I can quickly explain a method. I assume a CPU word has size $2^w$ and overflow is just modulo $2^w$.

First, computing $x + y \mod m$. Reduce $x, y \mod p$ (not necessary if you already know $x, y < p$). Then, if $y \geq m - x$, overflow would occur. So in that case we compute $x + y - m$, otherwise simply $x+y$. In C++:

// Compute (x + y) % m, assumes x, y < m.
uint64_t addmodu64(uint64_t x, uint64_t y, uint64_t m) {
    return x + y - m * (y >= m - x);
}

Then, computing $xy \bmod m$ can be done by multiplication through repeated addition in $O(\log x)$ additions. We can repeatedly apply the following identity:

$xy \equiv (2\lfloor{x\over2}\rfloor + (x\bmod 2))y \equiv 2y\lfloor{x\over2}\rfloor + y(x\bmod 2) \mod m$

This gives a recursive function:

// Compute (x * y) % m, assumes x, y < m.
uint64_t mulmodu64(uint64_t x, uint64_t y, uint64_t m) {
    if (x == 0) return 0;
    uint64_t y2 = addmodu64(y, y, m);
    uint64_t r = mulmodu64(y2, x/2, m);
    if (x % 2) r = addmodu64(r, y, m);
    return r;
}

This is just for demonstration purposes, for a fast implementation you want to convert this to a loop without any calls.

Finally, computing $(ax + b \bmod p) \mod m$ then is as simple as addmodu64(mulmodu64(a, x, p), b, p) % m.


How do we pick and switch hash functions from a universal family? When we have a universal family of hash functions, it gives us a few useful mathematical guarantees. But, if we pick a specific function from the family and use it all the time it's effectively like the family doesn't exists and we only have this one function.
Therefore, the only logical thing seems to be switching a hash function every once in a while (picking a new function from our family). If indeed this is what we should do, how often should we switch functions? How should this time period be selected and is there an optimal time period for different tasks?
Also, suppose we have two hash functions $h_1, h_2$, and then store values in an array according to $h_1$. After a while, we switch our has function to be $h_2$. Do we have to re-hash all of our values according to $h_2$? This seems rather wasteful

You need to decide what sort of resilience you are expecting from your hash function. While it is true that once picked, your hash function does not change (and in a sense "the rest of the family doesn't exist") but you're ignoring the crucial part of picking the function at random.
Suppose that $\mathcal{H}\subseteq U^{[m]}$ is a universal family, $h$ is chosen uniformly at random from $\mathcal{H}$, and is subsequently used to hash elements from $U$ into $m$ cells via chaining. This guarantees that regardless of what is the current content of the table, if the load factor is $\alpha=n/m$, then for every $x\in U$ (note the worst case analysis, as opposed to the average case analysis in the simple uniform hashing case) the expected search/insertion time for $x$ is $O(\alpha)$, where the expectation is taken over the initial choice of $h$ (this is the only place where randomness occurs). This remains true regardless of how many operations were done since the initialization, the random choice of $h$ guarantees low expected search time for all inputs.
Switching might come to mind if you are looking for robustness against certain types of adversaries. If the entire problem was handling a user giving you inputs and hashing them to a table, then everything's fine. This changes if you are looking at the problem of an adversarial user with more access, say e.g. that he might learn the hash value of some elements (which happens in real world attacks based on response time analysis). In that case, the adversarial user might be able to recover $h$ and then send you tailored inputs that will cause high search time. This relied on the adversary having a richer interface than just being able to send arbitrary values (which alone, as we saw above, can't cause problems). Now you're entering the world of cryptographically secure hash functions, and here some switching mechanism might be of use. This requires an entirely different formalization, and to say something interesting about parameters such as switching intervals we need to be clear about what sort of robustness we want to achieve.


Need help understanding what co-recursively enumerable means Lets say I have a set: $ L = \{\langle G \rangle | L(G) = \Sigma^{\star}\}$ and the question asks if it is co-RE. I know that if something is co-RE, it halts on every input not in L but may or may not halt on inputs in L.

So in this case would something "not in L" be nothing?

If you by co-CE mean co-Computably Enumerable, then they are the same.

The field called Recursion Theory is also known as Computation Theory.

You find the same analogy in the classes.  Recursive is a different way of calling Computable.  A recursively enumerable set is a different way of calling computably enumerable set.


Evaluating Statements Using a Parse Tree I'm building a compiler. I already have a parse tree which I built using Bison for a grammar similar to the ANSI C grammar in this link. I see that for multiplicative expression in my parse tree, there can be 3 children e.g.

child 1: multiplicative_expression
child 2: '*'
child 3: cast_expression

I expect to implement a new class for interpreting the parse tree. However, I have no idea how to even traverse the parse tree in order to evaluate the statements. How do I traverse the tree properly in order to interpret all the types of statements? I want to interpret not only multiplicative statements but also if-else statements etc.

An expression is composed usually of an operator (or function) applied
to some arguments, or in the simplest case, just a constant (aka
literal) or a variable.

For evaluation:
The value of a constant is that constant, The value for
a variable is the current value stored in that variable, as each
variable corresponds to a memory location where values can be stored.
The value of an operator or function applied to arguments is obtained
by evaluating arguments (recursively) and then applying the operator or
function to the values thus obtained.

Actually, things can be more complex for a function (and some
operator), depending on parameter passing mechanisms or evaluation
modes (lazy or not), but that is to complex to explain at this level
of discourse.

In your example the operator is child 2, and the two other children
are arguments.

In general the algorithm does pretty much what you would do if you had
to interpret the program by hand. That should be a good guide.


Fenwick Tree/ Binary Index Tree Interval location I have an array of positive numbers, and when calculating the cumulative sum of this array, want to know which interval a given point will lie in.

I have done this by searching linearly through an array, but want to use Fenwick trees in the hopes the speed up will be noticeable. I've followed tutorials online, and have now implemented construct, update and getsum functions. I'm not sure how to go about determining which interval a point will lie in though (while taking advantage of the data structure).

So for example, if I had the array [1,2,2,1,4,6,7,3], then I could calculate the cumulative sum as [1,3,5,6,10,16,23,26]. If I the  had the number 17, I'd want to know what interval this lies in. So starting indexing at 0, this would be in the interval between the 5th and 6th elements of the array.

You can perform binary search on a Fenwick Tree.
The idea is Binary Lifting.

I'm assuming that we use a one-based indexing in the Fenwick tree, and that we have exactly $2^k$ elements in the array $A$. And to formalize the problem: we want to find the biggest $i$, such that $A[1] + A[2] + ... + A[i] < x$ for a given $x$. This means that the prefix sum of the first $i$ element is still too small, but the prefix sum of the first $i + 1$ elements is exactly $x$ or already too big.

The exist multiple different implementations of the Fenwick tree. As I said here I use one-based indexing, since the algorithm is a lot more beautiful this way.
For refreshment, one-based indexing in a Fenwick tree means the following (explained using an example): The sum of the first $13 = 1101_2$ numbers can be computed as $bit[1000_2] + bit[1100_2] + bit[1101_2]$, where $bit$ is the array of the nodes of the Fenwick tree. The first summand $bit[1000_2]$ covers the first $1000_2 = 8$ elements (last set bit), the second summand $bit[1100_2]$ covers the next $100_2 = 4$ elements (last set bit), and $bit[1101_2]$ covers the last $1_2 = 1$ elements (last set bit).

This indexing allows a very cool trick:
We can iterate over the bits, from the highest to the lowest one, and check in $O(1)$ time if we should set it or not.

function find_biggest_smaller_index(x):
    // returns biggest i such that A[1] + A[2] + ... + A[i] < x
    i = 0
    for b = log(n)...0:
        set bit b in i
        if bit[i] < x:
            // yay, gives a better lower bound
            // this handes the last 2^b elements, therefore subtract them
            x -= bit[i]
        else:
            // damn, too big already
            unset bit b in i
    return i

edit: now that I think about it. It should also work if the size of the array $A$ is not a power of 2.