Floating-Point Binary to Decimal I'm having difficulty with the following question:

  Given a bit pattern with mantissa $10110000$ and exponent $0111$, what
  does the bit pattern represent in denary (i.e decimal / base 10)?

I got the right answer(!) but the wrong (or alternative) work:

Convert the exponent to denary: $0111$ is $7$
Apply this exponent to the mantissa: $10110000\rightarrow1011000$ after shifting $7$ places
Convert the mantissa to denary: $1011000$ is $88$
Set the sign: $-88$ (which is correct!)

Using a different method, the mantissa $1.0110000$ is somehow deteremined to be $-11/16$ and then $-11/16 \times 2^7 = - 88$ (I understand this shift with the exponent). However, what I don't understand is:

  How do you convert 1.0101 (mantissa) to -11/16? Is this a standard way to do it?

I got the answer with a bit of reverse engineering.

1) 0111 is 7 in denary so the exponent is power(2,7)

2) convert 10101000 to a positive number using twos comp

3) you  you get: 010110000 which is 1/2 + 1/ 8 + 1/16 using the powers of 2 after the radix point

4) this is 11/16 but we no it is negative from step 2 so it is -11/16!


Prove $\{a^ib^i\mid i\ge0\}$ is not regular using the pumping lemma I do not understand the last sentence of the proof provided. It says that the fact that xz does not belong to L contradicts the hypothesis, but isn't it that xyz not belonging to L what we are trying to prove?

By the pumping lemma $a^n b^n$ can be written as $xyz$ with $|xy| \le n$ and $|y| \ge 1$ in a way that ensures that $xy^kz \in L$ for any $k \ge 0$.
Picking $k=0$, this implies that $xz \in L$.
Since this is not the case for your language $L$, you know that $L$ cannot be regular.


Reduce ATM to the language of TM encodings where if the TM accepts w then the TM accepts ww Today I did a test in my class, the trace was:

  Prove that the language $L =\{\langle M\rangle\mid \forall w \in \{0,1\}^\ast: M \text{ accepts
}w\implies M \text { accepts }ww \}$, is undecidable with a reduction
  from $A_{\mathrm{TM}}$.Hint: You can suppose that $w\in \{0,1\}^*$

I answered:

  Suppose that $L$ is decidable. Therefore, there is a TM $R$ such that $L(R)= L$, so we can construct a new TM $S$ that decides
  $A_{\mathrm{TM}}$. First, construct $N$ as follows:$\\$
  "On input $x$:

  if $x$ is of the form $ww$, accept
  otherwise, run $M$ on $w$ and do what $M$ does.

  Now we can construct $S$ as follows:

  Construct $N$ as above.
  Run $R$ on $N$; if $R$ accepts, accept; otherwise, reject.

Now I know this isn't correct, but I don't why. More generally, how to recognize a language of a reduction? For example, in my reduction, $S\text{ accepts } w \iff \text{the language of } N\text{ is ?} \iff \langle M,w\rangle \in A_{\mathrm{TM}} $ I think I'm missing something about reductions but I don't know what.

First of all, assume the TM $S$ receives a (correctly encoded) instance $\langle M, w \rangle$ of $A_{\text{TM}}$. $N = N_{M,w}$ must be constructed in terms of $M$ and $w$, that is, its description depends on the problem instance $\langle M, w \rangle$. (It is sloppy to just describe $N$ without having fixed this instance first.)

Your overall proof structure is correct, only you made a couple of mistakes in the constructions of $N = N_{M,w}$ and $S$. Instead you should have for $N$:

  On input $x$:

  If $x$ is of the form $w'w'$ for some $w' \in \{0,1\}^\ast$, reject;
  Otherwise, simulate $M$ on input $w$ and do what $M$ does.

Why this? Consider the following:
$$\begin{align*}
\langle N \rangle \in L
&\iff \forall w' \in \{0,1\}^\ast: (w' \in L(N) \implies w'w' \in L(N)) \\
&\iff \forall w' \in \{0,1\}^\ast: w' \not\in L(N) \lor w'w' \in L(N) \\
&\iff \forall w' \in \{0,1\}^\ast: w' \not\in L(N) \\
&\iff \not \exists w' \in \{0,1\}^\ast: w' \in L(N) \\
&\iff \lnot (\text{$M$ accepts input $w$})
\end{align*}$$

The third equivalence is the reason behind constructing $N$ so as to reject inputs of the form $w'w'$. The last equivalence holds because not all strings are of the form $w'w'$ for some $w' \in \{0,1\}^\ast$.

To complete the construction of $S$, have it feed $\langle N \rangle$ to $R$ and accept if $R$ rejects and reject otherwise (i.e., $S$ returns the opposite of what $R$ returns). By the equivalences above, $S$ reduces $A_{\text{TM}}$ to $L$, so $L$ must be undecidable.

As to your more general question regarding reductions: Unfortunately, I am afraid these kind of problems are rather tricky in of themselves. (I suppose that, at the core of it, the problem is that we are dealing with paradoxes, which are, of course, very nasty little things.) Nevertheless, Rice's theorem generalizes a great deal of these questions and makes it much simpler to prove something reduces to $A_{\text{TM}}$ or the halting problem.


Asymptotics of a sinusoid Consider the function
$$
f(n) = 2n^2 |\sin(\pi \cdot n/2)|.
$$
Which of the following classes does $f(n)$ belong to?
$$ O(n^2), \Omega(n^2), \Theta(n^2), \omega(n^2), o(n^2). $$

I'm working in this and so far I have been trying to use different methods but always get to a dead end.

Let us notice the following:
$$
|\sin(\pi \cdot n/2)| = \begin{cases} 1 & \text{if $n$ is odd}, \\ 0 & \text{if $n$ is even}. \end{cases}
$$
This implies that your function $f(n)$ alternates between $n^2$ (for odd $n$) and $0$ (for even $n$). This means, for example, that $f(n) = O(n^2)$ (since $f(n) \leq n^2$ for all $n$) but $f(n) \neq \Omega(n^2)$ (considering even $n$).


Swaps Used in Selection Sort I was trying to come up with a formula for the number of swaps used in selection sort. So we know that selection sort gives the minimum number of swaps to sort an array.

The formula I came up with is given an unsorted array and it's descending or ascending order. We find the number of elements dissimilar to the sorted array. When we subtract 1 from this number we can get the number of swaps.

For example,
Let the array be

[3, 4,2 ,9,1]

Using selection sort for descending order:

[9,4,2,3,1] ---[9,4,3,2,1] which gives a total of 2 swaps

My logic:

Descending array is [9,4,3,2,1]. So three elements are in incorrect position which are 9, 3 and 2. So, 3-1 = 2 swaps.

Let us consider ascending order:

Section sort:

[1,4,2,9,3]--[1,2,4,9,3]--[1,2,3,9,4]--[1,2,3,4,9] which gives a total of 4 swaps.

My logic:

Ascending array is [1,2,3,4,9]. So all five elements are in incorrect position from the sorted array which gives a total swap count of 5-1 = 4.

But my logic seems to be incorrect when tested on hacker rank. Could you give me an example where this logic fails. Thanks :)

Considering following array
[5,4,3,2,1]

Now for ascending order, four elements are in incorrect position i.e. 5,4,2 and 1

So according to your logic,
No of swaps = No. of elements at incorrect position - 1 therefore No. of swaps = 4-1 i.e. 3

Now, according to Selection sort,

[5,4,3,2,1] Original Array

1st Pass: [1,4,3,2,5] i.e. 1 swap

2nd Pass: [1,2,3,4,5] i.e. 2 swaps

We are done, with Only 2 swaps not 3 swaps.

Similarly for Descending order,

Now, according to Selection sort,

[1,2,3,4,5] Original Array

1st Pass: [5,2,3,4,1] i.e. 1 swap

2nd Pass: [5,4,3,2,1] i.e. 2 swaps

We are done, with Only 2 swaps not 3 swaps.

Hope this helps !


Can you automatically generate a parser for a type using type theory some how? Was wondering since all the types are spelled out constructively, and the constructions can all be reflected symbolically on a computer, if you can automatically parse expressions in a type?

In programming languages, we usually distinguish concrete syntax, where a program is represented as a linear list of symbols, from abstract syntax, where programs have a tree structure.

The vast majority of PL theory, including most type systems, happens after parsing, working with abstract syntax.

So, it's impossible to generate a parser simply from type rules or definitions, because there are arbitrarily many concrete syntaxes that could correspond to any abstract syntax. The choice is a purely human one.

In some languages, like Haskell, the description of a data type can be used to generate parsers and printers for types, using the deriving mechanism of the typeclass system. But it chooses a syntax that corresponds to the Haskell one by convention, and they could have chosen to define it any other way.


In type systems, is there a name for SQL's way of cutting and combining record types into new types? I'd like to have this feature in my application programming language (which these days, is Scala), but when I went to learn more about it on the internets, I realized I don't know the name of it.  I'm talking about the ability to do this (in Scala-ish pseudocode):

// Define some types that correspond to table rows in relational DB
class User
   val id: Int
   val name: String
   val email: String
   val created: DateTime

class Comment
   val id: Int
   val text: String
   val userId: Int
   val created: DateTime

// Call a select/join query function
val list = select c.id, c.text, u.name
           from comments c join user u on c.userId = u.id ...

And then list gets a type of something like List[R] where R is an unnamed record type with properties id, text, name, or maybe c.id,c.text,u.name.

Some languages, like Scala, support you writing that select function so it returns a tuple type (Int, String, String), but not a type with named fields.

Is there a name for that?

I think what you are looking for is type inference for record types.  Let me give you a bit of an overview on each of those; but those keywords should help you find a lot more on those topics.

Type inference means that you don't need to declare the type of everything.  Instead, the compiler figures out the types where it can, from context.  For instance if you write a function

function f(x,y):
    return (x+y)/2

the compiler can figure out that f is a function that accepts two ints and returns an int.  (How?  It knows that 2 is an int, and that both operands to the / operator must have the same type.  Therefore, the type of (x+y) must be int.  That in turn means that both x and y must have type int.  And so on.)

You want type inference, so you don't need to explicitly declare the type of the result of the select and join operations.

A record type is basically just a fancy name for a struct.

A record is an object that has a list of fields; each field has a name and a type.  For instance, to invent some example syntax: {height: 69, weight: 152, name: "Bob"} might be a record with three fields; if r is a variable holding this record, then you might be able to use syntax like r.height to access the height field.

You might notice that a record is a lot like a tuple, except that the elements of a tuple do not have names (you just access the first element, second element, third element, etc. of a tuple), whereas the elements of a record do have names.  The ability to provide names is convenient.

Others have suggested you want anonymous record types, meaning you don't have to explicitly declare the record type.  That might be relevant, too.

With those concepts, here's what I think you want from a language.  First, I think you want your language to support records.  Second, assuming you want a statically typed language, it sounds like you want your language to support type inference, so that the compiler can infer the types of records where possible.  (In a dynamically typed language, you might not need the type inference part.)  Third, you want your language to provide select and join operations that operate on records and return records, and (assuming you want a statically typed language) you want the type inference operation to be able to infer the types on their result based on the types of what they're operating on.

There are some questions you'll need to decide.  Will select and join be built into the language?  Or do you want to enable them to be implemented as libraries or user-defined functions?

You'll also need to make some decisions about your type system.  Do you want to alow subtyping on records?  Do you want to allow functions in your language to be polymorphic over records?  For instance, consider the following function:

function g(r):
    return (r.weight + 10) / r.height

Do you want your type inference routine to infer that g is polymorphic in the sense that it can accept any record containing width and height fields that are both ints?  Do you want to allow first-class field names?  For instance, consider the following function:

function extract(r,f):
    return r.f

r = {height: 69, weight: 152, name: "Bob"}
extract(r, #weight)

In other words, do you want to be able to pass the name of a field as a first-class value?

There's lots of work on type systems for this sort of stuff, in the programming languages community -- and especially in functional languages.  I believe that F# and ML support sophisticated record types.  Here are two samples:

A proposal for records in Haskell.   Simon Peyton Jones and Greg Morrisett, 2003.
Record Polymorphism in SML#. Atsushi Ohori, Katsuhiro Ueno, 2012.

For experience about how to integrate SQL-like database queries directly into the programming language, take a look at LINQ, which provides support for SQL queries directly in .NET / C#.  There are both academic papers on LINQ and lots of documentation for developers.  It looks very close to what you are looking for.


Return values of Probabilistic Programs Syntax and semantics section of this paper on probabilistic programming mentions that the return expression of the program is a function f satisfying  $
f : \sum \rightarrow \mathbb{R}^{\inf}_{\geqslant0}$ where $\sum$ is the set of states. I do no not see the need of $\geqslant0$. Why can't the return values be negative?

The function $f$ is a probability sub-distribution, which means that it's a like a probability distribution, only its integral can be less than $1$ (due to the observe statements). The return statement normalizes $f$ back to a bona fide probability distribution.

Outside of quantum computing, probabilities are non-negative.


How to decribe an action with STRIPS? The state space is decribed with 3 boolean variables $p,q$ and $r$ (so we have 8 states total). We have an action, let's say $a$. Action $a$ can be executed when $p=\text{False}$ and $q=\text{True}$ and the result is $p=\text{True}$, $q=\text{False}$ and $r=\text{False}$

How can we describe this action with STRIPS? My problem is this: since it isn't allowed on STRIPS to have negative literals, how can I describe it? For example, $\text{precondition}(a) = \{ \neg p,q \}$.

An instance of propositional STRIPS planning is a quadruple $\langle P,O,I,G \rangle$

$P$ is the set of atomic ground formulas;
$O$ is the set of operators (actions); an operator  $a \in O$ has the form $Pre \Rightarrow Post$, where $Pre$ is a satisfiable conjuction of positive ($a^+$) and negative preconditions ($a^-$) of the operator; $Post$ is a satisfiable conjunction of positive ($a_+$) and negative ($a_-$) postconditions of the operator ($a_+$ is called the add list, $a_-$ is called the delete list);
$I \subseteq P$ is the initial state;
$G = \langle G_+, G_- \rangle$, called the goals, is a satisfiable conjunction of positive and negative conjunctions;
the state $S$ is a subset of $P$.

The result of applying operator (action) $a$ on state $S$ is:

$(S \cup a_+) \setminus a_-\quad$ if $a^+ \subseteq S$ and $S \cap a^- = \emptyset$
$S$ otherwise

In your example simply set:
$$a^+ = \{q\}, \quad a^- = \{p\}$$
$$a_+ = \{p\}, \quad a_- = \{q,r\}$$

For a formal definition and a nice computational complexity characterizations of STRIPS with various constraints on the preconditions/postconditions see:
The Computational Complexity of Propositional STRIPS Planning (1994), by Tom Bylander.


Algorithm with $O(n)$ time and $O(n)$ space to compare two arrays $A$ and $B$ are two arrays with $n$ elements each in the range $1$ to $n^2$.

1.How to check if the elements of $A$ are distinct in $O(n)$ time and $O(n)$ space

2.How to check if $A$ and $B$ have a common element in $O(n)$ time and $O(n)$ space.

Both the algorithms shouldn't use Hash sets or any other advanced data structure. A and B are just simple Arrays.

A HashSet can store $n$ elements in $\mathcal{O}(n)$ space and add/query elements in amortized $\mathcal{O}(1)$ time. Therefore we can use the following approaches:

1. Are A's values distinct?

HashSet setA;
for i in {1, ..., n}
    if setA.contains(A[i])
        return "No, A[i] is a duplicate.";
    endif
    setA.add(A[i])
endfor
return "Yes, values are distinct.";

2. Do A and B intersect?

HashSet setA, setB;
for i in {1, ..., n}
    if setB.contains(A[i]) or setA.contains(B[i])
        return "Yes, A and B intersect.";
    endif
    setA.add(A[i]);
    setB.add(B[i]);
endfor
return "No, A and B are disjoint.";

Edit: Thanks to D'Nabre for pointing out a problem. The assumed $\mathcal{O}(1)$ for querying the HashSets may not work out in this case. D'Nabre also pointed at the element distinctness problem, which is worth a look. From Wikipedia:

  it may also be solved in linear expected time by a randomized algorithm that inserts each item into a hash table and compares only those elements that are placed in the same hash table cell.


When LP solution is ILP solution? For many discrete problems, it's natural to consider their continuous relaxations. A common case is when instead of $x_i \in \{0, 1\}$ we allow $x_i \in [0, 1]$. In certain cases, the original problem is an integer linear programming (ILP) problem, and its relaxed version becomes a linear programming (LP) problem, which we can efficiently solve.
Questions: Are there common techniques which show that, for a particular problem:

An LP solution will always be an ILP solution?
There exists an LP solution that is also an ILP solution?
A particular LP algorithm (e.g. simplex method) finds an ILP solution.

By "solution", I, of course, mean a vector on which the objective reaches its optimum.

Consider a linear program of the following form: maximize $c^Tx$ over $Ax \leq b$, where $x \in \mathbb{R}^n$ and $b$ has integer entries.
The simplex algorithm finds a solution of the form $x = A_S^{-1} b_S$, where $A_S$ is a submatrix consisting of $n$ rows, and $b_S$ are the corresponding entries of $b$. Each entry of $A_S^{-1}$ is a ratio of two determinants: the determinant of some $(n-1)\times(n-1)$ submatrix of $A$ (namely, minors of $A_S$), and the determinant of some $n \times n$ submatrix of $A$ (namely, $A_S$). If the entries of $A$ are integers and every $n \times n$ submatrix has determinant $0,\pm 1$, then $A_S^{-1}b$ is integral.
The condition that any square submatrix has determinant $0,\pm 1$ is known as total unimodularity. If the constraint matrix $A$ is totally unimodular, then the simplex algorithm will always find an integral solution.
A more general condition is total dual integrality, which just states that for every integral $c$, the linear program has an integer optimal solution. If the system satisfies TDI then the simplex algorithm is also guaranteed to find an integral solution.


How to wiggle sort an array in linear time complexity? The wiggle sort is nums[0] < nums[1] > nums[2] < nums[3] > nums[4] ...

For an input: nums = [1, 5, 1, 1, 6, 4], the expected output is [1, 4, 1, 5, 1, 6] and there can be many other possible outputs satisfying the aforementioned criteria.

I realised that the problem has a pattern:
nums[1] will be greatest among nums[0:3], nums[3] will be greatest among nums[3:6],...

So, I targeted at getting the next greatest element. This made me implement the heap:

import heapq

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        nums_heap = []
        for num in nums:
            heapq.heappush(nums_heap, -1*num)
        i = 1
        while i < len(nums):
            nums[i] = -1 * heapq.heappop(nums_heap)
            i += 2
        i = 0
        while i<len(nums):
            nums[i] = -1 * heapq.heappop(nums_heap)
            i += 2

However, the time complexity of my solution is O(n) along with O(n) space complexity. I want to solve this in O(1) space complexity and that would require me to not use heap(extra space).

How to do that?

The complete question is also posted here.

Some characterizations of wiggle-sort
Skip this section if you would like to see the algorithms right away.$\def\A{\mathcal A}$ $\def\S{\mathcal S}$
Given an array $\A=(\A_0,\A_1, \cdots, \A_{n-1})$ of numbers, let us call the $\lceil n/2\rceil$-th smallest entry in $\A$ as well as each entry that is equal to that entry a median of $\A$. (This definition of median differs slightly from its usual definition when $n$ is even. For example, the median of $(3,4)$ is $3$ instead of $3.5$)
Call $A$ wiggle-sorted if $\A_0<\A_1>\A_2<\A_3>\A_4<\cdots$. Call $A$ wiggle-sortable if we can rearrange its entries so that it becomes wiggle-sorted. An array is always wiggle-sortable if all numbers in it are distinct. If all numbers are not distinct, the array may or may not be wiggle-sortable. For example, $[1,2,2]$ is not wiggle-sortable while $[1,1,2]$ is wiggle-sortable.
A permutation of $\{0,1,\cdots, n-1\}$, $\sigma$, is called a wiggling permutation if $\sigma(\A)=(\A_{\sigma(0)},\A_{\sigma(1)}, \cdots, \A_{\sigma(n-1)})$ is wiggle-sorted as long as $\A$ is sorted.
For all $n$, define a permutation $$w_n=\pmatrix { 0 &1 &2 &3 &4&5&\cdots\\m &n-1 &m-1 &n-2 &m-2 &n-3 &\cdots},$$
where $m=\lceil n/2\rceil-1$. For example,
$$w_5=\pmatrix { 0 &1 &2 &3 &4 \\2 &4 &1 &3 &0},$$
$$w_8=\pmatrix { 0 &1 &2 &3 &4&5&6&7\\3 &7 &2 &6 &1 &5 &0 &4}.$$
Characterization of wiggle-sortable arrays. The following propositions are equivalent.

$\A$ is wiggle-sortable of size $n$.
(Not too many medians) The number of medians of $A$ is no more than $\lceil n/2\rceil$.
If we have just sorted $A$ (in the usual sense), then $w_n(\A)$ is wiggle-sorted.

Uniqueness of wiggling permutation. For even size $n$, $w_n$ is the unique wiggle permutation. For odd size $n$, $w_n$ and $\overline{w_n}$ are the only two wiggling permutations, where $\overline{w_n}$ is the "reverse" of $w_n$, i.e., $\overline{w_n}(i)=n-1-w_n(i)$ for all $i$.

This uniqueness explains the fact that all solutions to the wiggle-sort problem arrange the given array the same way basically.

Here is the problem again: given an array of numbers, how can we wiggle-sort it?
A simple approach that runs in $O(n\log n)$ time
The easiest approach to implement, as illustrated in the question, is to sort the array, explicitly or implicitly, and rearrange the array.
Input: an array $\A$ of $n$ numbers with indices $0, 1, n-1$.
Output: None if $\A$ is not wiggle-sortable. Otherwise, return $\A$ that has been wiggle-sorted.
Procedure:

Sort $A$ into a temporary array. (Most sorting libraries run in $O(n\log n)$ time on average.)
Copy the largest number, the next largest number, and so on of the temporary array to $A$ at index $1, 3, 5,\cdots$ until the index is out of bound.
Copy the next largest number, the next largest number, and so on of the temporary array to $A$ at index $0, 2, 4,\cdots$ until all numbers are exhausted.
Check if the $\A$ is wiggle-sorted. Return accordingly.

# assume the given array, nums is wiggle-sortable
def wiggle_sort(nums):
    arr = sorted(nums)
    for i in range(1, len(nums), 2): nums[i] = arr.pop()
    for i in range(0, len(nums), 2): nums[i] = arr.pop()

To achieve better performance, we have to avoid sorting the array.

The outline of a faster algorithm
Procedure:

find the median of $\A$ by some $O(n)$ algorithm.
Count the number of all medians. If it is greater than $\lceil n/2\rceil$, return None.
Put all entries larger than the median in positions with odd indices,  $1, 3, 5,\cdots$ in that order.
Put all entries smaller than the median in positions with even indices from the largest-even-indice going downwards.
Fill the remaining entries of $A$ with the median. Return $\A$.

The problem is shifted to how to find the median and arrange the numbers
Find the median in linear time and constant space
To implement the algorithm in linear time and constant space we need to find the median in linear time and constant space.
There are various ways to achieve that deterministically, for example, linear-time in-place selection in less than 3n comparisons, 2005 and linear-time in-place selection with ⋅ element moves, 2006. Unfortunately, all these algorithms are somewhat complicated.
We can find the median in average linear time and constant space using a simple algorithm, quickselect. Here is the python code.
def k_smallest(nums, k, start, end):
    """
    Returns the k-th smallest number in nums[start:end+1].
    """
    if k <= 0 or end - start < k - 1:
        return None

    k = start + k - 1

    while True:
        if start >= end:
            return nums[start]

        # pivot = nums[random.randint(start, end)]
        pivot = nums[end]
        left, right, m = start, end, start
        while m <= right:
            if nums[m] < pivot:
                nums[left], nums[m] = nums[m], nums[left]
                left += 1
                m += 1
            elif nums[m] > pivot:
                nums[right], nums[m] = nums[m], nums[right]
                right -= 1
            else:
                m += 1
        if left <= k <= right:
            return pivot
        elif k < left:
            end = left - 1
        else:  # k > right
            start = right + 1

m = k_smallest(nums, (n + 1) // 2, 0, len(nums) - 1)  # m is the median

If we relax the space requirement slightly, we can find the median in linear-time and logarithmic-space using the median of medians algorithm.
Arrange the numbers in linear time and constant space
Once the median has been found, the problem is shifted to arrange the number as specified. Any reasonable implementation will run linear time. What is not obvious is how to do it in constant space as well.
We can imagine the entries of $\A$ is actually arranged in the memory consecutively as $A_1$, $A_3$, $A_5$, $\cdots$, $A_{n_1}$, $A_0$, $A_2$, $A_4$, $\cdots$, $A_{n_0}$, where $n_1$ and $n_0$ are the largest odd and even number not exceeding $n$.  Here is the explicit access pattern when $n=8$:
$\quad$ Accessing memory at index 0 actually accesses $A_1$.
$\quad$ Accessing memory at index 1 actually accesses $A_3$.
$\quad$ Accessing memory at index 2 actually accesses $A_5$.
$\quad$ Accessing memory at index 3 actually accesses $A_7$.
$\quad$ Accessing memory at index 4 actually accesses $A_0$.
$\quad$ Accessing memory at index 5 actually accesses $A_2$.
$\quad$ Accessing memory at index 6 actually accesses $A_4$.
$\quad$ Accessing memory at index 7 actually accesses $A_6$.
Or, in general, the memory at the index $p$ refers to $\A_{(1+2p)\pmod{n\,|\, 1}}$.
With this mapping between indices, the problem is transformed to the Dutch national flag problem or, what is the same, the tri-color problem on LeetCode. We can apply the tri-color algorithm almost verbatim, which runs in $O(n)$ time and $O(1)$ space (thanks to StefanPochmann for his post).
# Put numbers larger than pivot at smallest odd-indices.
# Put numbers smaller than pivot at largest even-indices.
def tri_color_clustering(nums, pivot):
    n = len(nums)

    def map_index(p):
        return (1 + 2 * p) % (n | 1)

    i, j, k = 0, 0, n - 1
    while j <= k:
        if nums[map_index(j)] > pivot:
            nums[map_index(j)], nums[map_index(i)] = nums[map_index(i)], nums[map_index(j)]
            i += 1
            j += 1
        elif nums[map_index(j)] < pivot:
            nums[map_index(j)], nums[map_index(k)] = nums[map_index(k)], nums[map_index(j)]
            k -= 1
        else:
            j += 1
    # print(nums)

A previous version of this answer shows a simple and fast algorithm to wiggle sort an array in $O(n)$ time and $O(1)$ space, assuming all numbers in the given array are distinct.


How can TSP be an NP-optimization problem, when a feasible solution $s$ must be polynomial bounded in the instance size $|I|$? How can TSP be an NP-optimization problem ?

The definition of an NP-optimization problem $\Pi$ states that for each instance $I \in \Pi$ , the set of feasible solutions $S_\Pi(I)$ is non-empty and that the size of each $s \in S_\Pi(I)$ is polynomial bounded in $|I|$, where $|I|$ denote the size of $I$.

However, in the case of TSP an instance will be encoded using $n^2$ bits, where $n$ is the number of vertices in the instance graph, using the adjacency matrix representation.

But there are $n!$ feasible solutions ? In order to encode these one must use $n! \setminus 2^n$ bits. This number increase as $n$ increase, but $p(|I|)$ is fixed ?

How I overseen something ?

A solution in the TSP problem is a sequence of $n$ vertices.
Consider a labeling $1,\dots, n$ of the $n$ vertices.
We need $O(\log{n})$ bits to encode the label of each vertex.
Then, any sequence of $n$ vertices can be described by $O(n\log{n})$ bits; the concatenation of $n$ vertex labels.
Hence, any solution $s$ of the TSP can be described by a number of bits that is polynomial in $n$.

The size of the instance $I$ is also polynomial in the number of vertices $n$, as noted in the original question.


Definition of the state of an object in OOP I need a concise definition of the "state of an object" in object-oriented programming (for a paper).

For about half of a day I searched for a paper that I can cite on this topic, but I couldn't find one. All the papers I found were mostly general papers on object-oriented programming and they didn't define the state of an object.

I am unsure, but my best guess is something like:
The state of an object is defined by the state of the instance variables of the object.

I am searching for a definition of the state of an object and/or a reference on the topic.

(btw, could I refer to the concept as "object state" or is this uncommon?)

You can take a look to (and cite) the book "Object-Oriented Analysis and Design" by G. Booch:

  ... An object is an entity that has state, behavior, and identity. The structure and
  behavior of similar objects are defined in their common class. The terms instance
  and object are interchangeable.

  We will consider the concepts of state, behavior, and identity in more detail in the
  sections that follow.
  ...

And there is a whole subsection that describes the concept of state:

  ... From this example, we may form the following low-level definition.

  The state of an object encompasses all of the (usually static) properties of the
  object plus the current (usually dynamic) values of each of these properties
  ...


Path finding through bipartite graph Is there a path finding algorithm that exploits a directed bipartite graphs' structure?

I found this: Shortest-Path for Weighted Directed Bipartite Graphs but it didn't seem like the OP needed a bipartite graph and the answer reflected that.

I also found this: https://www.degruyter.com/downloadpdf/j/comp.2013.3.issue-4/s13537-013-0110-4/s13537-013-0110-4.pdf
but it's not clear whether the solution is performant and I also don't have a APSP problem.

Clearly, an algorithm that runs on bipartite graphs only can't be slower than an algorithm that works on any graph. Therefore, the bipartite-shortest-path problem is in P.

In the opposite direction, consider a transformation that splits every edge into a pair of edges. It results in a bipartite graph and it preserves shortest paths. Therefore, any algorithm that can find the shortest path in a bipartite graph with v+e vertices and 2e edges can also find the shortest path in an arbitrary graph with v vertices and e edges.

Time complexity of Dijkstra's algorithm is O(e + v log v),  so any performance improvement gained by a bipartite-shortest-path algorithm over a regular algorithm is limited to the constant factor of 2. Any faster, and it supersedes the regular algorithm entirely.

The Wikipedia page on the shortest path problem lists several special cases but never mentions bipartite graphs even in passing. It does include an algorithm from 2004 which reduces the time complexity to just O(e + v log log v).

Conclusion: There most likely is no known algorithm for bipartite path search that improves upon the best known algorithm for path search on arbitrary graphs. There is also no room for such improvement in terms of algorithmic complexity, and for only a factor of two in terms of runtime (treating log(log v) as a constant).


Reducing 3-coloring problem to trio representatives A group of students is divided into trios - groups of 3 members. Each student can be assigned to more than more trio. We want to assign their representatives, by choosing exactly one member of each trio. Is such assignment possible?

My goal is to use polynomial-time reductions to transform 3-coloring of a graph into this problem. However, I'm stuck on the correct representation.

If each vertex is a different student and edges represent being in the same trio, how do I separate trios?
If each node represents a trio, what could be a sensible meaning of the edges?

I suspect that since a 4-clique has no adequate 3-coloring (which could also mean that 4 trios with the same three members have no possible representative assignment), the latter option could be more sensible, but I'm not sure on how to proceed with this reduction proof.

Let $G = (V,E)$ be an instance of $3$ coloring. Construct an instance $\phi$ of 3-SAT as follows.

For each vertex $v \in V$ create $3$ variables $v_a, v_b, v_c$ representing the $3$ possible ways to color of $v$.
For each vertex $v \in V$ create the clauses $(v_a \vee v_b \vee v_c) \wedge (\overline{v_a} \vee \overline {v_b}) \wedge (\overline{v_b} \vee \overline {v_c}) \wedge (\overline{v_c} \vee \overline {v_a})$. This encodes the fact that $v$ must be colored by exactly one color.
For each edge $(u,v) \in E$ create the clauses $( \overline{v_a} \vee \overline{u_a} ) \wedge ( \overline{v_b} \vee \overline{u_b} ) \wedge ( \overline{v_c} \vee \overline{u_c} )$. This ensures that $u$ and $v$ cannot be given the same color.

Clearly the above reduction can be performed in poylnomial-time and ensures that there is a satisfying assignment to $\phi$ iff there is a 3-Coloring for $G$.

Now transform the instance $\phi$ of 3-SAT into an equivalent of instance $\phi'$ of 1-in-3 SAT  (see here for the definition of 1-in-3 sat and the reduction from 3-SAT).

We have hence shown that 3-Coloring is polynomial-time reducible to 1-in-3 SAT.
It turns out that 1-in-3 SAT is exactly your problem: the set of students is the set of variables and, for each clause $\{x_i, x_j, x_k\}$ you create a group containing students $x_i$, $x_j$, and $x_k$. Setting a variable to true corresponds to selecting the corresponding student as a leader.


Algorithm to Group Vertices of Graph Given is the following graph which is logically divided into layers (with Dijkstra's shortest paths algorithm):

 Vertices   Layer

    Root      0
   /   \
  A     B     1
 / \    |
C   D   E     2
 \  |  /
  \ | /
    F         3

Now I'm looking for an algorithm which groups vertices when they have a (single) common ancestor in the previous layer, e.g. for the graph in the example the groups would be:

0: A, B
1: C, D
2: E
3: F

I know that this is doable by visiting vertices and comparing ancestors but I was wondering whether there is a well known algorithm for it.

Update: My question is really only related to find groups. I'm aware of the fact, that I can traverse vertices and test for incoming edges and group those vertices. Furthermore, the graph is fully constructed.

One (now deleted) answer mentioned DFS, which creates a search forest (as BFS creates a search tree which I basically used for levels, though I mentioned Dijkstra). So, I assume that combining BFS and DFS could give me the desired result.

this seems to be known as the "Lowest Common Ancestor" problem of graphs. see eg

Faster algorithms for ﬁnding lowest common ancestors
in directed acyclic graphs Czumaj et al
LCA Queries in Directed Acyclic Graphs Kowaluk, Lingas
Lowest Common Ancestors in Trees and Directed Acyclic Graphs Bender et al
algorithm to find LCA in DAG, so.se


Partition an infinite regular language into 2 disjoint infinite regular languages Given any infinite regular language $L$, how can I prove that $L$ can be partitioned into 2 disjoint infinite regular languages $L_1, L_2$? That is: $L_1 \cup L_2 = L$, $L_1 \cap L_2 = \varnothing$, and $L_1$ and $L_2$ are both both infinite and regular.

So far, I thought of:

using the pumping lemma such that
$$ \begin{gather}
  L_1 &= \{ xy^nz \mid \text{\(n\) is even} \} \\
  L_2 &= \{ xy^mz \mid \text{\(m\) is odd} \} \\
\end{gather} $$
but couldn't prove that they are dijoint or covering $L$ completely.
Using the regular language partitions $\Sigma^*$ into dijoint equivalence classes, but I haven't figured out how to determine if an equivalence class is regular or infinite.

Every regular language is accepted by some minimal DFA. For an infinite regular language $L$, let's call such a DFA $M_L$. Consider any state $q$ which can be visited more than once while processing some string in $L$. If $q$ can be visited more than once, it follows that it can be visited any number of times. Define $$L_1 = \{w \in L \mid q\text{ is visited an odd number of times}\}$$ and $$L_0 = \{w \in L \mid q\text{ is visited an even number of times}\}$$
This is a DFA, so there's only one path. Any string in $L$ is accepted by the DFA, and must visit the state some number of times (maybe zero). The state can be visited an unlimited number of times; therefore, we know that there are infinitely many strings in $L_1$ (since there are words that cause the state to be visited 1 time, 3 times, etc.) and that there are infinitely many strings in $L_0$ (since there are words that cause the state to be visited 0 times, 2 times, etc.). Any given string is either in $L_1$ or $L_0$, and cannot be in both, so $L_0 \cap L_1 = \emptyset$. However, any word in $L$ is guaranteed to be in one of these two sets, so $L_0 \cup L_1 = L$.


Can a quantum computer (theoretically) do things a classical computer (literally) can't? I've been searching the net for an answer to this question, but it's guetting quite confusing.
I want to know if there are some undecidable problems for a classical computer that a quantum computer could do.
The examples I've seen are things like Shor's algorithm, but that's "just" because the quantum computer is more powerfull than the classical one, and can do stuff like Integer factorization faster. Or at least that's how I understand it so far.
Basically my question is this : is there anything a quantum computer can do that a regular one can't if said regular computer had infinite power (or processing speed or whatever)?
Examples, explanations, sources would be greatly appreciated, but a simple yes/no would please me also.

No. Quantum computers cannot solve undecidable problems.

A quantum computer can be simulated by a classical computer. So, if a quantum algorithm could solve an undecidable problem, then we could also solve it classically via simulation.  However, we already know that if a problem has no classical solution, then it must not have a quantum solution either.

Also, you said:

  that's "just" because the quantum computer is more powerful than the classical one.

This is an open problem.  We do not yet know if $BPP \subset BQP$.


How to translate automatons (Turing machines) into programs of high level programming language? Every program in high level ("industrial") programming language can be expressed as some Turing machine. I guess, that there exists universal algorithm for doing that (e.g. one can take the Cartesian multiplication of the domains of all the variables and the resulting space can be the state space of the Turing machine, though the handling of computer-representable floats can be tricky - is there such general algorithm or system that does that? https://github.com/Meyermagic/Turing-Machine-Compiler is an example for the programming language for Turing machine and for the transpiler that translates C programs into the language of Turing machines or see https://web.stanford.edu/class/archive/cs/cs103/cs103.1132/lectures/19/Small19.pdf for some kind of Turing assembler language). But what about the other direction - can Turing machine be rewritten in concise  program in high level programming language that uses functions, compositionality of functions and higher-order functions?
Of course, there can be infinite results to that conversion - starting from the naming of the variables and functions and ending with the data structures, content of functions, etc. But there are metrics for the quality of the software code and maximizing such metrics can result in more or less unique answer to this stated problem.
Such conversion is very actual in the current context of reward machines for the reinforcement learning (e.g. https://arxiv.org/pdf/1909.05912.pdf) - symbolic representation of the reward function (as opposite to tabular or deep neural representation). Such symbolic representation greatly facilitates skill transfer among different tasks and it introduces the inference during the learning process and in such way reward machines reduce the need for data and need for learning time.
One can say that the extraction of first order and higher-order functions is a quite hard task, but this task is being tackled by the higher order meta-interpretive learning, e.g. https://www.ijcai.org/Proceedings/13/Papers/231.pdf.
So - are there research trends, works, results, frameworks, ideas, algorithms about conversion of the Turing machine into program in high level programming language (and possibly back)? I am interested into any answer - be it about the functional, logic or imperative programming.

https://www.longdom.org/articles/reverse-engineering-turing-machines-and-insights-into-the-collatz-conjecture.pdf is one initial effort to do this for some subclass of Turing machines. Actually there is fantastic culture about it http://bluesky-home.co.uk/. These works almost exclusively cite the author itself, that indicates how undeveloped this field is. Nonetheless, the quality of that research is at the level of peer-reviewed research and the main results are published.


OS: Why is it necessary to have hardware support for implementing Preemptive Scheduling Strategies? I think, Preemption can easily be done in kernel mode, where it just have to call the Context-Switch procedure. Also, based on algorithm we can select the new process from the ready queue as well...
I'm unable to think and find Why and where the role of timers come and what exactly are significance of Hardware in preemptive scheduling.
Can we not do preemptive scheduling without hardware support?
Why I didn't ask on Stack-overflow?
=> I need the theoretical point, although I'll appreciate if someone mentions the actual implementations of Unix.

A preemptive scheduler must stop a program that is looping and not calling any operating system function. The program is not triggering any fault as division by zero.
We are assuming that the interrupt are enabled and assuming single core processor.
Only a timer interrupt can succeed to regain control of the processor.
The rate set by this timer gives you the maximum switching time for the scheduler.
The preferred value is 1000 Hz which gives 1 ms resolution.
For computers not fast enough to allow so many timer interrupt per second, the next popular values were:
60 Hz, from the video card refresh rate
18 Hz, from a 16 bit overflow of IBM PC original timer chips ; color TV cristal of 3.59 MHz / 3 / 65536
Other option: cooperative multitasking. This is how apollo computer managed to run many tasks... As well as Windows 3.1
You call a lightweight scheduler everywhere your code perform long loops.
The lightweight scheduler usually just decrement an integer and immediately return if the value still not zero.
For the rare case where the integer reach zero, immediately set that integer to the default value and perform the next tests to decide if a new task with higher priority needs to be executed.
If a precise timing is needed, then at this point, reading a hardware timer counter and comparing the value with the previous one allow to evaluate precisely the elapsed time.


How to find the best exploration parameter in a Monte Carlo tree search? I've developed a Monte Carlo tree search algorithm in checkers.

Here is my question. What should be the value of $C$, the exploration parameter in the following formula described in Monte Carlo Tree Search (MCTS)?

$$ S_i=x_i+C\sqrt{\frac{\ln (t)}{n_i}}$$

General consensus is that a value of $\sqrt 2$ should be used, but when I use a value of 10 it works, which save me a lot of time.

So, how can I find the best value for $C$, that best suits my problem?

The  value  of $C = \sqrt 2$  was  shown to ensure the asymptotic optimality when rewards are in the $[0,1]$ range (Kocsis, Szepesvári, 2006).

In many games, that reward range is straightforward: maximum and minimum possible scores can be translated to 0 and 1 (0 could mean a loss and 1 a win).

The accuracy of this squashing seems to have a minimal impact (e.g. Using Domain Knowledge to Improve Monte-Carlo Tree Search Performance in Parameterized Poker Squares - Robert Arrington, Clay Langley, and Steven Bogaerts - 2016).

Unfortunately squashing isn't always possible.

With rewards outside the $[0, 1]$ range and/or for fine-tuning the Cross Entropy Method works quite well.


Hashing and number of comparisons Say, I want to put N objects into a hash table. How do I figure out how big the size of the table needs to be to have K comparisons on average when the table is: half full? three quarters full? all but last full?

Basically, this is due to me not really understanding the theory. I tried googling it, but didn't get it either. Can I have an explanation even a monkey would understand?

This explanation is for the Homo sapiens sapiens subspecies of Cercopithecidae (old world monkeys).  For an explanation suitable for other subspecies you'll have to try Knuth.

I'll assume you are talking about collision resolution by open addressing, and double hashing to determine the probe sequence.  Further we'll assume that the hash functions are good (that is: that they are essentially producing uniformly distributed, independent random integers.)

We will use $N$ for the number of objects already in the hash table, $M$ for the total number of buckets in the hash table and $\alpha = N/M$ as the load factor.  The load factor is the fraction of buckets that are already taken, and is really the important thing here.

If I try to insert a new item in a hash table with load factor $\alpha$ what is the probability that I will get a collision on my first probe?  Answer: $\alpha$.  Thus the probability that I find an open bucket on my first probe is $1-\alpha$.

What is the probability that I will find an open bucket on exactly my second probe?  Well the probability that I failed to find an open bucket on my first probe is $\alpha$ and the probability that I succeed on my second probe is $1-\alpha$, which gives a total probability of $\alpha (1-\alpha)$.

What is the probability that I will find an open bucket on exactly my third probe?  Well the probability that I failed to find an open bucket on my first and second probes is $\alpha^2$, and the probability that I succeed on my third probe is $1-\alpha$ so I have a total probability of $\alpha^2 (1-\alpha)$.

I'm an engineer, not a mathematician, so that's good enough for me to assume that the pattern holds for all positive integers.  That is I've just "proved" that the probability I will take $k$ probes to find an open bucket is
$$ p(k) = \alpha^{k-1} (1-\alpha). $$

(Exercise: make sure that this is a good probability by showing that $\sum_{k=1}^\infty \alpha^{k-1}(1-\alpha)=1$.)  Now what's the expected number of probes to find an open bucket?

$$ \begin{eqnarray}
   E[\mathrm{number\ of\ probes}] &=& \sum_{k=1}^\infty k p(k) \\
                                  &=& \sum_{k=1}^\infty k \alpha^{k-1}(1-\alpha) \\
                                  &=& (1-\alpha)\sum_{k=1}^\infty k \alpha^{k-1} \\
                                  &=& \frac{1-\alpha}{\alpha}\sum_{k=1}^\infty k \alpha^k.
\end{eqnarray}$$

I look up this series on Wikipedia and see that $\sum_{k=1}^\infty k \alpha^k = \alpha / (1-\alpha)^2$ so

$$ E[\mathrm{number\ of\ probes}] = \frac{1}{1-\alpha}.  $$


Need help understanding Knuth's proof that: The set of all pure words is well-ordered by the relation > In the paper linked below by Knuth and Bendix, theorem 1:

The set of all pure words is well-ordered by the relation '$>$'

has a proof that I can't seem to follow despite staring at it all day. I can't even decipher what the notation is trying to represent.
So, we have four fixed sequences:

An infinite sequence of variables $v_1, v_2, v_3, ...$ etc. (not relevant for Theorem 1)
A finite sequence of operators $f_1, f_2, f_3, ..., f_n$
A finite sequence of degrees $d_1, d_2, d_3, .., d_n$

(i.e. degree of $f_4 = d_4$)

and a finite sequence of weights $w_1, w_2, w_3, ..., w_n$

(i.e. weight of $f_4 = w_4$)

A word is then defined inductively as either a variable alone or an operator followed by an appropriate number of other words depending on the degree of said operator.
A 'pure word' is a word with no variables and the weight of a pure word, $\alpha$ is defined as follows:

$w(\alpha) = \sum_j w_jn(f_j , \alpha)$ where $n(f_j, \alpha)$ is the number of occurrences of $f_j$ in the word $\alpha$

Finally the relation $>$ that orders all pure words that is proved to be well-ordered is defined as:
$ \alpha > \beta $ if and only if:

$w(\alpha) > w(\beta) $

(I'm assuming the '$>$' here is strict integer inequality and not the same '$>$' that is being defined.)

$w(\alpha) = w(\beta)$ and $\alpha = f_j\alpha_1 ... \alpha_{dj}$, $\beta = f_k\beta_1 ... \beta_{dk}$, and either:

2a) $ j > k$; or
2b) $j = k$ and $\alpha_1 = \beta_1,..., \alpha_{t-1} = \beta_{t-1}, \alpha_t > \beta_t$, for some $t, 1 \leq t \leq d_j$

Finally on page 266, for the proof that $>$ is well-ordered the exposition states:

Now let $\alpha$ be a pure word with $n_j$ symbols of degree $d_j$. It is easy to prove inductively that:
$n_0 + n_1 + n_2 + ... = 1 + 0.n_0 + 1.n_1 + 2.n_2 + ...,$
i.e. $n_0 = 1 + n_2 + 2n_3 + ...$

I don't know whether it really is 'easy' to prove the above because I don't really know what the above is.
I'm fairly sure symbols are just operators in this context of pure words but if $n_0, n_1,$ etc. are symbols then how are they being summed? Does $n_0$ in the above actually represent $w(n_0)$. That doesn't seem to provide any clarity as to what is going on with the proof.
I've reread the first four pages of the paper multiple times and nothing seems to be getting any clearer:
https://www.cs.tufts.edu/~nr/cs257/archive/don-knuth/knuth-bendix.pdf
Any insight would be appreciated.

Now let $\alpha$ be a pure word with $n_j$ symbols of degree $d_j$. It is easy to prove inductively that:
$n_0 + n_1 + n_2 + ... = 1 + 0.n_0 + 1.n_1 + 2.n_2 + ...,$
i.e. $n_0 = 1 + n_2 + 2n_3 + ...$

I think there is a small mistake here, since $n_j$ should be considered as the number of symbols of degree $j$ and not of degree $d_j$ in $\alpha$.

$n_0 + n_1 + n_2 + ... = 1 + 0.n_0 + 1.n_1 + 2.n_2 + ...,$

In this formula, the left side can be interpreted as "the total number of symbols", and the right side can be interpreted as "the first operator symbol plus the total number of arguments". Intuitively, those quantities are indeed equals.
If we correct the mistake, then it is somewhat easy to prove by induction:

if $\alpha$ does not contain any operator of degree $\geq 1$, then we have $\alpha = f()$, where $f$ is an operator of degree $0$ (that could be considered as a constant). We have then $n_0 = 1$, and $n_i = 0$ for any $i \geq 1$. The property $n_0 = 1 + n_2 + 2n_3 + ...$ holds;

if $\alpha = f(\alpha_1, …, \alpha_d)$ where $f$ is an operator of degree $d \geq 1$ and the $\alpha_i$ are pure words that verify the property we want to prove, then we get:

$n_k(\alpha) = \sum\limits_{i=1}^d n_k(\alpha_i)$ if $k \neq d$;
$n_d(\alpha) = 1 + \sum\limits_{i=1}^d n_d(\alpha_i)$.

Therefore we get:
$\begin{array}{rcl}
 n_0(\alpha)& = &\sum\limits_{i=1}^d n_0(\alpha_i) \\ & =& \sum\limits_{i=1}^d\left(1+\sum\limits_{k=2}^{\infty}(k-1)n_k(\alpha_i)\right)\\ & = & d + \sum\limits_{k=2}^{\infty}(k-1)\sum\limits_{i=1}^dn_k(\alpha_i) \\ & =  &d + (d-1)(n_d(\alpha) - 1) + \sum\limits_{k = 2,k\neq d}^{\infty}(k-1)n_k(\alpha)\\ & = & 1 + \sum\limits_{k = 2}^{\infty}(k-1)n_k(\alpha)\end{array}$
And that proves the formula by structural induction on pure words. Please note that the previous sums can be interverted because the infinite sum is, in fact, finite (since $n_k(\alpha_i) = 0$ for $k$ big enough).

The fact that $n_j$ is the number of symbols of degree $j$ and not of degree $d_j$ is somewhat confirmed after the statement: "since each nullary operator has positive    weight, we have $w \geq n_0$". Why? Because $\alpha$ contains $n_0$ occurrences of nullary operators, which are supposed to be of positive weights. The statement would make no sense if $n_0$ was the number of symbols of degree $d_j$ (since $w_j$ could be zero).


Proving that a Language is non-Regular Prove that $L_2 = \{ w \in \{a,b\}^* \mid w = a^ib^j, i \neq j \}$ is not regular.

I was wondering if my intuition holds for proving this language as not regular:

Let $q = \max(i, j) - \min(i, j)$.

Case 1: $i > j$

Let $$L_3 = b^q \Rightarrow L_2 \cdot L_3 = \left \{ a^ib^{j+q} \right \}=\left \{ a^ib^i \mid i \ge 0 \right \}.$$

And then do the same for when $j > i$.

Is this allowed?

No that's not allowed, since $i$ and $j$ are not fixed.

Here is a solution using pumping lemma:

  The better approach is to apply pumping lemma.
Let $x = a^{n!}b^{(n+1)!}$, where $n$ is the pumping constant. Note that $u = a^i$ and $v=a^j$ for some $i\geq 0$ and $j>0$ plus $i+j\leq n$.

Then we let $k = 1+\frac{n\cdot n!}{j}$. After that, $uv^kw = a^mb^{(n+1)!}$ where $m = n!+(k-1)j = n!+n\cdot n! = (n+1)!$. Contradiction.

Here is another solution using closure result (which is less tricky):

  Suppose $L_2$ is regular. Then $(\Sigma^* - L)\cap a^*b^* = \{w\in\{a, b\}^*|w=a^ib^j, i=j\}$ is regular by closure result. Then it's easy to gain a contradiction by applying pumping lemma to $(\Sigma^* - L)\cap a^*b^*$.


Regular expression $(a^{*}b^{*})^{*} = \left( a+b \right)^{*}$ proof Im having a lot of trouble proving that for the Regular expression $R_{1} = \left( a^{*} b^{*} \right)^{*}$ and $R_{2} = \left( a+b \right)^{*}$ that $L \left( R_{1} \right) = L \left( R_{2} \right)$. I was wondering if anyone could help me with this? thanks

First prove that every word in R1 is also in R2; then prove that every word in R2 is also in R1.  Spend some time on each and see what progress you can make.


Variant of bipartite matching, with real capacities from source and to sink, all others unlimited I've got a variant of bipartite graph matching and I can't find any literature about it.

We have bipartite graph with real capacity edges from source to left vertices (the sum of which is 1), real capacity edges from right vertices to sink (also summing to 1), and unlimited capacity edges between left and right.  What is the fastest algorithm for max flow here?

To phrase it more colorfully, you have N types of dog food, totaling 1 kilogram; and N dogs, with each dog being able to eat a maximum quantity of food, but in total they can eat 1 kilogram. Not all dogs will eat all types of dog food, but they will eat up to their "capacity" of any combination of the types that they do like. How do you get the largest quantity of dog food fed to your dogs?

So far it looks like Edmonds-Karp is actually faster than push-relabel. I've been using the networkx python package implementation of both of these algorithms, but now I need to optimize for speed. I will be implementing a solution in C or Cython, but I'm concerned about the algorithm itself. It feels like there should be a specialized solution for this that works faster. Does anyone have any ideas?

Looks like the answer I was looking for was something like Dinitz's algorithm with dynamic trees. There are some implementation optimizations that can be added since we know it's a bipartite graph.


Algorithm for simplifying ANF or polynomials? I have some digital logic circuits in Algebraic Normal Form, and am limited to using XOR and AND logic gates.

For instance:

$B_{out} = B_1 B_2 \oplus B_1 B_3$

I was wondering, are there any algorithms to simplify ANF to use a smaller number of gates?  I'm looking to minimize ANDs specifically.

The above equation would ideally become this:

$B_{out} = B_1 (B_2 \oplus B_3)$

Since AND and XOR act like multiplication and addition respectively, it also seems like the answer could be in algorithms which minimize operations in polynomials.  If that is the case, I'm specifically looking to minimize multiplications (which is the equivelant of ANDs in ANF).

One person suggested i use a Karnaugh map, but am unsure how (or if it's possible) to use a Karnaugh map with XOR/AND instead of OR/AND.  I could convert OR/AND back and forth to XOR/AND terms as needed, but in that case I don't believe the result is garaunteed (or likely) to be minimal anymore.

Are there algorithms for this? I feel like there has to be, but I haven't been able to find any.

The algebraic normal form (ANF) is unique.  You can't "simplify" the ANF; each formula has a single, unique ANF, and there's only one.  Once you've found it, that's it; there's no other, "simpler" ANF for the same formula.

Perhaps what you want is, given a formula, find the smallest circuit that uses only XOR and AND logic gates.  In general, that circuit won't necessarily be in algebraic normal form.  (For instance, $B_1 (B_2 \oplus B_3)$ is not in ANF; the ANF of that formula is $B_1 B_2 \oplus B_1 B_3$.)  That's called "logic minimization" or "logic synthesis" or "circuit minimization".  Most prior work has considered how to use a gate basis of NAND or {AND, OR, NOT}; you are looking for an algorithm that uses the basis {AND, XOR}.

If you want to minimize the total number of gates, I'd suggest you do a literature search on the literature on logic minimization, looking for methods that work with an arbitrary basis, or that work with the basis {AND, XOR}.  (One possibly buzzword or phrase to search for is exclusive-or sum-of-products minimization; this covers the special case of circuits that have multi-input AND gates on the first level and a single multi-input XOR gate at the second level.)

In general, essentially all of these circuit minimization problems are NP-hard, so you shouldn't expect any efficient algorithm that will always work.  Instead, people rely on heuristics that sometimes work or are sometimes efficient.

You can find people who have studied a similar problem in the cryptography world, because Yao-style garbled circuits naturally support AND and XOR gates.  Cryptographers have studied how to implement various functions efficiently using only AND and XOR gates.  However, in that world, for various reasons we can make XOR gates effectively free, so they generally try to minimize the "multiplicative complexity", i.e., the minimum number of AND gates needed in any circuit over the basis {AND,XOR}.  I couldn't tell whether that was what you wanted or not.  If it is, you might enjoy the following page, which lists circuits of minimal multiplicative complexity for a variety of functions of cryptographic interest:

http://cs-www.cs.yale.edu/homes/peralta/CircuitStuff/CMT.html

Perhaps this will help you articulate a more precisely defined question.


AVL Tree - Print ascending using in-order Trying to understand how to write proof of correctness.
Searched over the internet on how to write proof of correctness but can't find a good solution for it.

The following sorting algorithm is proposed using the AVL tree: AVL input of all elements, and printing them in order.

Algorithm  - Sort AVL (A[1..n])

T -> Empty AVL Tree.

for each 1 <= i <= n

insert A[i] to T.

print T elements by using in-order fashion.

Prove the correctness of the algorithm by showing the in-order scan of binary tree is always in ascending order.

AVL trees, like all other binary search trees, have the following guarantee:

  Suppose that $v$ is a node with left child $l$ and right child $r$. If $x$ is a node in the subtree rooted at $l$ and $y$ is a node in the subtree rooted at $r$ then $key(x) \leq key(v) \leq key(y)$.

Using this, you can easily prove by induction that the inorder traversal of a binary search three produces a list of keys in nondecreasing order.


Understanding the definition of reduction From Wikipedia:

  Given two subsets A and B of N and a set of functions F from N to N
  which is closed under composition, A is called reducible to B under F
  if $$
     \exists f \in F \mbox{ . } \forall x \in \mathbb{N} \mbox{ . } x \in A \Leftrightarrow f(x) \in B $$ We write $$
     A \leq_{F} B $$ Let S be a subset of P(N) and ≤ a reduction, then S is called closed under ≤ if $$
     \forall s \in S \mbox{ . } \forall A \in P(\mathbb{N}) \mbox{ . } A \leq s \Rightarrow A \in S $$ A subset A of N is called hard for S
  if $$
     \forall s \in S \mbox{ . } s \leq A $$ A subset A of N is called complete for S if A is hard for S and A is in S.

I am trying to relate the above definitions to those for problems: problem A can be reduced to problem B, a set of problems are NP-hard, a set of problems are NP-complete. But I don't know how to relate. I think one link I am missing is to see how a subset of problem can be seen as a subset of $\mathbb{N}$?

The definition you're quoting is very abstract, but the concepts you're trying to understand are pretty intuitive. A problem $A$ is NP-hard if you can solve any problem in NP using it. This means that any $B \in NP$ can be reduced to $A$, i.e. there is some polytime function $f$ such that $x \in B$ iff $f(x) \in A$; so you can test whether $x \in B$ by computing $f(x)$ and test whether the latter is in $A$.

A problem is NP-complete if it is both in NP-hard and in NP. This means that it is hardest among problems in NP. A problem can be NP-hard without being in NP, for example the halting problem.

You're mentioning sets of problems as belonging to NP, but that's a typing error: members of NP are problems, in the guise of subsets of the set of natural numbers (or of the set of finite binary strings, which is the same). The subset specifies the set of inputs for which the problem has the answer YES.


If an array is full of the same integer, like 0s or 1s, are they all the peak of the array? I am learning the MIT course Introduction to Algorithms.

The professor is saying

  In particular, as an example, position 2 is a peak if, and only if, b
  greater than or equal to a, and b greater than or equal to c. So it's
  really a very local property corresponding to a peak.

My question is, if an array if full of the same integer, like 0s, or 1s, are they all the peak of the array?

This is something you will encounter over and over, not just in science but also in engineering, in law, in programming, and generally in jargon. If there is a definition for a term, then that term means exactly what the definition says it means. No more. No less.

In particular, you may have an intuitive notion of what the term means in English, but this is not English. This is technical jargon. A "peak" doesn't mean what you think it means, it doesn't mean what it means in English, it means exactly what its definition says it means.

So, depending on the definition, all elements could be the peak, or there could be no peak, or any element could be the peak, or maybe it could even be the case that the question doesn't even make sense because there is some precondition to the definition of "peak" that doesn't apply in this case.

Look at the definition. Apply it. Ignore any intuition about what you think the answer should be. Trust the result.


Connection CSP and 3SAT I am interested in showing connection between CSP (Constraint Satisfaction Problems) as it's defined in CSP (definition with Constraint graph, sometimes called binary CSP) and 3SAT problem, when domain of CSP contains of 7 values.

The specific requirement is to show reduction from 3SAT to GAP CSP, when domain of CSP contains of 7 values.

Let try to reduce 3SAT to CSP, every clause of 3SAT can be represent as a vertex of CSP, and edges connect two clauses (vertices) when these clauses have at least one common variable. Set the values (assignments) from the domain of 7 values to every nodes such that to ensure the consistency (each variable get the same value in all clauses).

The problem is I cannot get what is so special about 7 values, apparently, we should have 8 different assignments to the vertices, how can I show that 7 values is enough?

In addition, I still don't have a good intuition about the constraints, for me constraints represented by the edge of the graph, and they ensure the consistency of the assignment (each variable get the same value in all assignments).

Having codded 3SAT as CSP how can we show the reduction to GAP CSP?

Hint: There are seven satisfying assignments to the variables in each clause.


Fixed-length decision-tree-like feature selection to minimize average search performance I have a complex query $Q$ used to search a dataset $S$ to find $H_\text{exact} = \{s \in S \mid \text{where $Q(s)$ is True}\}$. Each query takes on average time $t$ so the overall time in the linear search is $t\cdot |S|$. I can break a query down into simpler sub-queries q_i and find $H_\text{approx} = \{s\in S \mid \forall q_j(s) \text {is True}\}$  and where $H_\text{exact}\subseteq H_\text{approx}$. Each subquery $q_i$ is much faster to compute, so overall it is faster to find $H_\text{approx}$ and then use $Q$ to find $H_\text{exact}$.

Each $Q$ has many $q_i$. The overlap between different $Q$ is high. I'm looking for a way to determine a decision-tree-like set of fixed questions $q_j$ which minimize the average time to find a H_exact, based on a large sample of search queries.

To make this more concrete, suppose the data set contains the 7 billion people in the world, and the complex queries are things like "the woman who lives in the red house on the corner of 5th and Lexington in a city starting with B."

The obvious solution is to check every person in world and see who matches the query. There may be more than one such person. This method takes a long time.

I could pre-compute this query exactly, in which case it would be very fast .. but only for this question. However, I know that other queries are for the woman who lives on the blue house on the same corner, the man who lives on the same corner, the same question but in a city starting with C, or something totally different, like 'the king of Sweden.'

Instead, I can break the complex question down into a set of easier but more general sets. For example, all of the above questions have a gender-role based query, so I can precompute the set of all people in the world who consider themselves a 'woman.' This sub-query takes essentially no time, so the overall search time decreases by roughly 1/2. (Assuming that by other knowledge we know that a Swedish "king" cannot be a "woman." Hatshepsut was an Egyptian woman who was king.)

However, there are sometimes queries which aren't gender-based, like "the person who lives on 8th street in a red house in a city starting with A." I can see that the subquery "lives in a red house" is common, and pre-compute a list of all those people who live in a red house.

This gives me a decision tree. In the usual case, each branch of the decision tree contains different questions, and the methods to select the optimal terms for the decision tree are well known. However, I'm building on an existing system which requires that all branches must ask the same questions.

Here's an example of a possible final decision set: question 1 is 'is the person a woman?', question 2 is 'does the person live in a red house?', question 3 is 'does the person live in a city starting with A or does the person live in a city starting with B?', and question 4 is 'does the person live on a numbered street?'.

When a query $Q$ comes in, I see if its $q_i$ match any of the pre-computed questions $q_j$ I've determined. If so, then I get the intersection of those answers, and ask the question $Q$ on that intersection subset. Eg, if the question is "people who live in a red house on an island" then find that "person lives in a red house" is already precomputed, so it's only matter of finding the subset of those who also live on an island.

I can get a cost model by looking at a set of many $Q$ and check to see the size of the corresponding $H_\text{approx}$. I want to minimize the average size of $H_\text{approx}$.

The question is, how do I optimize the selection of possible $q_j$ to make this fixed decision tree? I tried a GA but it was slow to converge. Probably because my feature space has a few million possible $q_j$. I've come up with a greedy method, but I'm not happy with the result. It too is very slow, and I think I'm optimizing the wrong thing.

What existing research should I be looking at for ideas?

The solution I found (I asked the question) is to use superimposed coding, and more specifically, a variant of Zatocoding which has better support for hierarchical descriptors.

The method I used comes from 'An Efficient Design for Chemical Structure Searching. I. The Screens', Alfred Feldman and Louis Hodes, J. Chem. Inf. Comput. Sci., 1975, 15 (3), pp 147–152.

The non-hierarchical solution is to look at the information density. Each descriptor will be assigned $s_i=-log_2(f_i)$ bits where $f_i$ is the frequency in the data set ($0<$f_i<=1.0). Compute the total number of bits $D$ (the size of the decision tree) using $D=\sum(s_i f_i)/M_c$ where $M_c$ is the Mooers compression factor 0.69 (from $log_e 2$). Once you have determined the total number of bits to use, select $s_i$ bits randomly for each descriptor for bit assignment.

The hierarchical solution from Feldman and Hodes replaces $s_i=-log_2(f_i)$ for descriptors which are a subset of other descriptors. In that case, use $s_i=-log_2(f_i/g_i)$ where $g_i$ is the frequency of the least frequent parent. In addition, when doing the bit assignment do not select bits which are also used by the parent's bit assignment.

There's still a problem of how to come up with the right descriptors, but that will be domain specific.


What is the relation between correlation and causation in machine learning? It is a well-known fact that "Correlation doesn't equal causation", but machine learning seems to be almost entirely based on correlation. I'm working on a system to estimate the performance of students on questions based on their past performances. Unlike other tasks, like Google search, this doesn't seem like the kind of system that can be easily gamed - so causation isn't really relevant in that regard.

Clearly, if we want to do experiments to optimise the system, we will have to care about the correlation/causation distinction. But, from the point of view of just building a system to pick questions that are likely to be of the appropriate difficulty level, does this distinction have any importance?

Not all of AI works on correlation, Bayesian Belief Networks are built around the probability that A causes B.

  I'm working on a system to estimate the performance of students on questions based on their past performances.

I don't think you need causation for this. A past performance does not cause a current performance. Answering on an early question does not cause an answer on a later question.

  But from the point of view of just building a system to pick questions that are likely to be of the appropriate difficulty level - does this distinction have any importance?

No, not for your example. I think correlation (or even simple extrapolation) would solve your problem very well. Assign a difficulty score to each of the questions and then feed questions to the students in increasingly difficult levels (which is how most exams work) and then when the student starts getting them wrong, you can wind back the difficulty. That's a feedback algorithm that is similar to the error minimisation performed on a neuron in a multi-layered perceptron. The non-trivial piece of input spaces like this is deciding what a difficult question is!

A better example of causation in AI would be:

  My car is slowing down. My accelerator is on the floor. There is not much noise. There are lights on the dashboard. What is the probability that I've run out of fuel?

In this case, running out of fuel has caused the car to slow down. This is precisely the sort of problem that Bayesian Belief Networks solve.


Finding minimum spanning tree with O(|V|) Given an undirected weighted graph $G(V,E)$, where the number of edges is $|V|+10$, how can I find the minimum spanning tree of $G$ in $O(|V|)$?

Kruskal's algorithm is out of the question, since sorting alone is $O(|V|\log |V|)$, so I thought maybe using Prim's algorithm with minimum binary heap, but still - every iteration will cost $\log |V|$ for updating vertices keys in the heap, so altogether it's $|V|\log |V|$.
I know that the key here is to use the fact that $|E|=|V|+10$, so I start thinking maybe removing the 11 edges with the biggest weights, as long as the graph stays connected, but that's obviously a bad idea since it'll - again - require sorting.
I just can't figure it out. Any help would be greatly appreciated.

Use DFS to find a cycle in the graph (in linear time). Save the maximum-weight edge while performing DFS, Delete it from the outputted cycle.
Repeat 11 times.
Done.


Boolean expression for sum bit of full adder The Boolean expression I find on the internet for the sum bit of a full adder is A xor B xor Cin. Does't this expression exclude the A=1,B=1,Cin=1 situation? When that happens, the sum bit is also 1, isn't it?

Thank you very much.

1 xor 1 xor 1 = 1, so this is correct in that case as well.


Protecting data unequally using Error Correction Codes Say I'd like to transmit a 100-bit packet which has a field containing a continuous value. I'd like to protect this value with an error correction code but an error in the MSB of this value is much more catastrophic than an error in the LSB, so how do I have to design the code so that it will be optimal by means of protection (more redundant bits for the important parts)?

For example, let's assume my continuous field is Temperature. My problem is that the temperature is represented by X bits but they are not equally important. If the temperature is 23.452298 degrees than I can't risk an error in the integer part (23) but if I'll get an error in the fractional part I'll be able to live with it (though I prefer protecting it too, with less "protection" bits).?

Since error correction here is essentially discrete, it might not be easy to come up with an optimal transient encoding, however you can approximate this by applying different encoding schemes for different parts of your data. In your temperature digits example, you might consider an encoding with $d=5$ Hamming distance for integer part and $d=3$ for fractional part, which will eventually provide a two-bit correction for the integer part and one-bit correction for the fractional part. This partitioning can be varied.


Use 2SAT to show that an implication graphs must have a cycle if it's not satisfiable Using 2SAT and implication graphs, how could I prove the following properties of implication graphs:

Suppose there is a directed path between literals l1 and l2 in G_φ.  Then there is also a directed path between their complements.  Then, there is  τ, a truth assignment satisfying φ where τ(l1) is true, then τ(l2) must also be true.

Using this, show that φ is unsatisfiable <=> there is some directed cycle in G_φ containing a variable x and its complement.

Where G_φ is the directed implication graph of 2SAT containing formula φ with n variables. Hence 2n vertices with one for every possible literal in φ, and edges (not l1, l2) and (not l2, l1) for every clause (l1 ∨ l2) in φ.

My first intuition was a proof by contradiction however I failed to construct a general enough assumption. I then tried to show that if the truth assignment means that l1 and l2 are true, then by building a cycle connecting all variables, the assignment is only valid when those edges exist. However this doesn't seem rigorous enough since I'm not properly understanding why the cycle requires the complement of x to exist.

Currently I build G by adding a vertex for every variable x and it's complement as well. Then for each clause (a v b) I add an edge between not a and b and not b and a.

However I fail to see how this would specifically form a cycle.

Working of the sipser textbook.

Here is a proof sketch. We will show that the given formula is unsatisfiable iff there exists a cycle containing both $x$ and $\lnot x$, for some variable $x$.

Suppose first that there exists a cycle containing both $x$ and $\lnot x$. The existence of a path $x \to^* y$ in the implication graph means that in a satisfying assignment, if $x$ holds then so does $y$ (you can prove it by induction on the length of the path). Since there is a cycle containing both $x$ and $\lnot x$, there are paths $x \to^* \lnot x$ and $\lnot x \to^* x$. In any satisfying assignment, either $x$ or $\lnot x$ holds, and both cases lead to contradiction.

Suppose next that there are no cycles containing both $x$ and $\lnot x$. We will construct a satisfying assignment as follows. Choose some variable $x$. If there is a path $x \to^* \lnot x$, assign $x = F$, and for each literal $\ell$ such that $\lnot x \to^* \ell$, assign the value to the underlying variable which makes $\ell$ true. You cannot be assigning the same variable two different truth values, since if $\lnot x \to^* y$ and $\lnot x \to^* \lnot y$ then also $y \to^* x$ and so also $\lnot x \to^* x$, completing a cycle involving $x$ and $\lnot x$.

If there is a path $\lnot x \to^* x$, assign $x = T$, and continue analogously.

If neither of these paths exist, assign $x$ arbitrarily, and continue as before. This cannot lead to a contradiction, for the following reason. Suppose that we assign $x = F$, and that there are paths $x \to^* y$ and $x \to^* \lnot y$. Then there is also a path $y \to^* \lnot x$ and so a path $x \to^* \lnot x$, contradicting the assumption that none of the two paths exists.

If after this process there is some unassigned variable left, choose one of them, and repeat until the assignment covers all variables.


is it possible to determine using a single depth-first search, in O(V+E) time, whether a directed graph is singly connected? I'm working on exercise 22.3-13 of CLRS (Intro to Algorithms 3rd edition):

  A directed graph $G = (V, E)$ is singly connected if the existence of a path from $u$ to $v$ implies that $G$ contains at most one simple path from $u$ to $v$ for all vertices $u, v\in G$. Give an efficient algorithm to determine whether or not a directed graph is singly connected.

Previous threads on this question are here and here. In that second thread, one of the answers links to a preprint by someone who corresponded with one of the authors of the book, and stated (in the abstract of the preprint) that the solution the authors intended was (if I'm understanding correctly) to call DFS-VISIT(G, u) (from p. 604 of CLRS) on each vertex $u$ of the graph, resetting all vertex colors back to white (to indicate unvisited) in between calls, and return false (for "not singly connected") whenever a forward edge or cross edge is found, and returning true otherwise. This would take O(VE) time.

There seems to be some confusion in the answers and comments section of those threads: the above scheme is referred to as "calling DFS on every vertex". In fact, this is different from the DFS algorithm presented on p. 604 of CLRS, which calls DFS-VISIT on all unvisited nodes in the graph, without resetting the colors in between calls, which takes $O(V + E)$ time.

My question is, instead of doing what is stated in the preprint, which takes O(VE) time, is it sufficient to simply perform the ordinary $O(V + E)$ DFS on the graph, and return false (for "not singly connected") whenever a forward edge or a cross edge that is located entirely within a single DF tree is found? (As correctly pointed out in one of the comments in the second thread linked above, a cross edge within a single DF tree means the graph is certainly not singly connected, but a cross edge between two vertices in different trees does not necessarily mean so).

In other words, is it possible to have a non-singly connected graph, such that for some ordering of the adjacency lists, performing the DFS algorithm from p. 604 of CLRS will not find any forward edges or cross edges within individual trees, but possibly only cross edges between trees, if any?

I just realized, a single call to DFS is not sufficient, since the conjecture I asked about is not true. Here is a counterexample. Suppose DFS first visits all nodes in a tree rooted at $u$, and $v$ is a descendant of $u$. Then suppose an unvisited vertex $w$ has both $u$ and $v$ in its adjacency list. Then, $w$ would not be in the same tree as $u$ and $v$, but there would be cross-tree edges $(w, u)$ and $(w, v)$, and hence there would be more than two paths from $w$ to $v$, making the graph not singly connected.
However, we cannot modify the algorithm to also look for cross edges between trees, since if we removed the $(w,u)$ edge from the example above, then it's still possibly for it to be singly connected even though there's a $(w,v)$ cross edge.


Why are $L$-reductions defined the way they are? I was reading about $L$-reductions and there was one part in the definition that I thought was interesting. I wanted to know what motivated people who came up with it to have it included in the definition.
Recall that a problem $A$ is $L$-reducible to another problem $B$ if there exist polynomial-time computable functions $f$ and $g$, and positive constants $\alpha$ and $\beta$ such that:

If $x$ is an instance of problem $A$, then $f(x)$ is an instance of problem $B$.
If $y'$ is a solution to the instance $f(x)$ of problem $B$, then $g(y')$ is a solution to the instance $x$ of problem $A$.
$OPT_B(f(x)) \leq \alpha OPT_A(x)$.
$|c_A(g(y'))-OPT_A(x)| \leq \beta |c_B(y')-OPT_B(f(x))|$.

where $c_A$ and $c_B$ are the cost functions for the problems $A$ and $B$, and $OPT_A$ and $OPT_B$ have their usual meanings.
Points 1, 2, and 4 seem completely natural to me. We want some way to map instances of $A$ to instances of $B$ in polynomial time. $f$ takes care of that. Additionally, we want some way (again in polynomial time) to map solutions to instances of $B$ to solutions to instances of $A$. $g$ takes care of that. Finally, we want the mapped solutions to preserve some notion of "quality" so that we can make statements like "if $y'$ is a "good" solution, then $g(y')$ is not "too bad" of a solution". Point 4 takes care of that. But what do we need point 3 for? It seems to me that points 1, 2 and 4 suffice for the definition of a "natural" approximation-preserving reduction.
I know that for $L$-reducibility to imply $PTAS$-reducibility, we need point 3. But is that the only reason for adding point 3 to the definition?

L-reductions were defined by Papadimitriou and Yannakakis in their paper Optimization, approximation, and complexity classes. From the abstract:

Furthermore, we show that a number of common optimization problems are complete for MAXSNP under a kind of careful transformation (called L-reduction) that preserves
approximability.

A survey of various related notions of reducibility is Ausiello and Paschos, Approximability preserving reduction. Each of the notions of reductions appearing there was invented to serve some purpose. Definitions are typically not arbitrary. They are supposed to model some intuitive notion. Some definitions are more successful than others. When unsure about a definition, it's always a good idea to check out the original paper(s) introducing the definition.


Proving correctness of an iterative Fibonacci algorithm One of the questions in the problem sets that I'm struggling in is this specific number that asks me to prove an iterative Fibonacci algorithm. The algorithm is written below:

function fib(n)
    if n = 0 then
        return(0)
    else
        a = 0; b = 1; i = 2;
        while i <= n do
            c = a + b
            a = b
            b = c
            i = i + 1
    return(b)

The way too prove correctness, according to my professor was to make sure that there are these three steps:

Initialization - the loop invariant must hold true prior to the first iteration
Maintenance - the loop invariant must hold true after an iteration
Termination - the loop invariant must hold true when the loop terminates

The loop invariant I've chosen is a <= b since I find this to be true for steps 1 through 3. First of all, I'm not sure if this is a valid loop invariant and this is the only observation I saw since i <= n isn't always true for inputs n that are natural numbers.

Assuming that I've chosen the correct loop invariant, I need to answer the proof by doing three steps so for this number I plan to answer it this way

Initialization - before the start of the loop a is assigned a value of 0 while b is assigned a value of 1 which starts the Fibonacci sequence. a <= b holds true prior to the start of the loop
Maintenance - during the loop, another variable c is added such that it is equal to the sum of a and b. After which, b is assigned to variable a while c is assigned to b thus making the invariant a <= b true during the iteration.
Termination - the loop ends when i > n. Before i is incremented, the procedures in the maintenance step is still done, thus the loop invariant still holds true

For my questions, is my loop invariant a <= b correct? And are the three statements I mentioned above sufficient to prove the correctness of an iterative Fibonacci algorithm?

The condition $a \leq b$ is a loop invariant, but it captures very little of the operation of the loop. A better loop invariant is
$$ a = F_{i-2} \text{ and } b = F_{i-1}. $$
This clearly holds just before the loop. The loop sets $a' = b = F_{i-1}$, $b' = a+b = F_{i-2}+F_{i-1}=F_i$, $i' = i+1$, from which it is easy to prove that it maintains the loop invariant. When the loop has finished, we must have $i = n+1$, and so $a = F_{i-2} = F_{n-1}$ and $b = F_{i-1} = F_n$.

There is a weak point in this argument: How do we know that $i = n+1$ at the end of the loop? We can fix this by strengthening the loop invariant to
$$ a = F_{i-2} \text{ and } b = F_{i-1} \text{ and } i \leq n+1. $$
This holds just before the loop since $n \geq 1$ (assuming $n \geq 0$, a precondition that needs to be added to the entire function). It is maintained during the loop since at the beginning of each iteration $i \leq n$. Finally, after the loop we have $i \leq n+1$ and $i > n$, which forces $i = n+1$ since $i$ is an integer.


Showing that T(n) = 2 + 2T($\frac{n}{4}$) = O($\sqrt{n}$) I am doing an exercise which says that this is true:
T(n) = 2 + 2T($\frac{n}{4}$) = O($\sqrt{n}$)
So I tried to solve it by substitution, but I am getting a non-sense result.
So would really appreciate some pointer in the right direction.
So I want to show it for $\frac{n}{4}$ (sub-question, I am picking $\frac{n}{4}$ to show it for because the recurrence has $T(\frac{n}{4})$, but this might not be the correct way to go always?)
I substitute $T(n/4)$ for $c\sqrt{n}$ in the original equation and get
T($\frac{n}{4}$) $\leq$ 2 + 2(c $\sqrt{\frac{n}{4}}$) =
2 + 2c$\frac{\sqrt{n}}{\sqrt{4}}$ =
2+2c$\frac{\sqrt{n}}{2}$ =
2+c$\sqrt{n}$ $\leq$ c$\sqrt{n}$
Which is clearly not true.

Since the OP made a writing mistake in the question, I will keep the first answer and add onto it the correct one.

For $T(n)=2+2T(n/2):$
I believe that the recurrence relation is not $O(\sqrt{n})$, and in fact is $\Theta(n)$.
We can see this easily using the master theorem, where here $a = 2, b = 2, f(n)= 2$, and then $T(n) = aT(n/b) + f(n)$.
Since $f(n)=O(n^{\log_b (a)})=O(n)$ then by the first case in the master theorem we have $T(n) = \Theta(n^{\log_b (a)}) = \Theta(n)$.

For $T(n)=2+2T(n/4)$:
As I have mentioned in the previous proof, the master theorem is useful for solving such recurrence formula. In our case, we have $a=2,b=4,f(n)=2$ and thus $\log_b(a)=\log_4(2) = 0.5$
By the first case of the master theorem, since $f(n)=O(n^{\log_b(a)})=O(n^{0.5})=O(\sqrt n)$ then we will also have $T(n) = \Theta(\sqrt n)$


Kolmogorov complexity of string concatenation If $K(s)$ is the Kolmogorov complexity of the string $s \in \{0,1\}^*$,

Can we prove (or disprove) the following statement:

"Every string $s$ is a prefix of an incompressible string; i.e. for every string $s$ there exists a string $r$ such that $K(sr) \geq |sr|$" ?

In a very informal (and perhaps not too meaningful) way: we know that $K(r) \leq |r| + O(1)$; if we pick a large enough incompressible string $r$, can we "use" the $O(1)$ to "mask" the compressibility of the given string $s$ ?

A similar (but different) result is that for any $c$, we can find $s$ and $r$ such that: $K(sr) > K(s) + K(r) + c$

Your conjecture is wrong. For some constants $C,D$, it holds that $K(sr) \leq 2K(s) + K(r) + C \leq 2K(s) + |r| + D$ (proof: use a universal Turing machine to generate $s$ and then $r$; you need somewhat more than $K(s)+K(r)$ to store both programs, though $2K(s)+K(r)$ is an overkill). Therefore if $2K(s) + D < |s|$, your conjecture doesn't hold. Such easy strings $s$ certainly exist, for example $K(0^n) = O(\log n)$.


What is the avantage of having memory mapped I/O? I can't make out what is the avantage of it comparing with the port designed I/O

Is it faster? Is it more reliable? Is it cheaper?

There are many advantages to memory mapped I/O

Access: Memory mapped devices use the same instructions/addressing modes as regular memory. These map well into high level languages allowing device drivers to manipulate devices without the need to drop down into assembly language to use special I/O instructions.
Security: As memory addressed devices, memory management hardware can be used to control access to those devices. Generally, I/O instructions are "wide open" in privileged modes allowing a driver to access any I/O mapped device, even those that it should not.
Flexibility: Almost without exception, the processor instructions available for memory are more varied and versatile than those for I/O mapped. With memory, load/store instructions are supplemented with various monodic (inc/dec/etc) and dyadic (add/sub/etc) operators. Special I/O mode instructions are generally limited to load/store. This typically gives the compiler a better shot at creating better code (ignoring the whole RISC/CISC debate for now).

Support for special I/O mapping is generally a legacy issue. The x86 for example is (on some level) compatible all the way back to the 8008.

Very old processors often included I/O mapped device support because the memory address space was so small (often 65,536 bytes or less) that I/O addressing provided a way to preserve memory address space for actual memory.

Modern processors have larger (4G or larger) address spaces so that this is no longer an issue.


Survival algorithm for Network deterministic failures Consider an undirected network $G = (V,E)$ in which edge $e$ $\in$ $E$ fails after (deterministic) time $t(e) > 0$. Network failure occurs at the first instant in which $G$ is no longer connected. Let $m = |E|$ and assume the values $\{t(e): e \in E\}$ are distinct.

You wish to determine the instant $\tau$ at which the network fails.

1- Suppose you solve this problem via an intuitive algorithm in which you first sort the edges according to $t(e)$ and then remove the edges, one at a time, to determine if the network has failed. Establish the complexity of this algorithm.

My Answer: We can sort edges in $O(m\log n)$ time + removing edges takes $O(1)$ * the number of edges to be removed $O(m)$. So the complexity is $O(m^2)$.

2- Show that a variation of your intuitive algorithm from part a can determine $\tau$ in a reduced time complexity in which a factor of m is changed to log m.

My expectation: I think we might use a heap for storing edges but I am not sure how to implement it.

3- Using what you know about spanning trees, can you write a new algorithm to improve upon (or equal) the complexity of your algorithm from part b? (Hint: The network will be failed as soon as every spanning tree. contains a failed edge.)

My expectation: I believe we need to find all spanning trees but I am not sure if this will help reduce complexity.

Can anyone help me solving the given problem or direct me towards a reasonable solution?

Part b
Suppose $t(e_1)>t(e_2)>\cdots$, what you want is $e_i$ such that the graph with $e_1,\ldots,e_i$ is connected. Part a checks the graph with $e_1,\ldots,e_m$, then the graph with $e_1,\ldots,e_{m-1}$, and so on. This process can be improved by binary search, i.e. checking the graph with $e_1,\ldots,e_{m/2}$, then graph with $e_1,\ldots,e_{m/4}$ or with $e_1,\ldots,e_{3m/4}$ depending on the result of the first check, and so on.
Part c
You don't need to check all spanning trees. You only need to find the spanning tree of whose edges the earliest failure time is maximized. This is known as a minimum bottleneck spanning tree (cost of an edge is the negative of its failure time).


Complexity of inserting an integer to an empty hashtable What's the complexity of inserting an integer $n$ to an empty hash table? My guess is that it's $O(\log n)$ as we require to scan every bit of $n$ to compute its hash. However, I  often see it as $O(1)$. Am I mixing up things here ?

The answer depends on your model of computation.    In other words, it depends on how you count the number of basic operations, or on what you consider to be a "basic operation".

In the transdichotomous model or Word RAM model, you can do computation on an entire word in $O(1)$ time, and the word size is guaranteed to be large enough to hold the integer (and, in particular, at least $\log n)$.  An operation on a single word counts as a single operation, even though you're operating on a bunch of bits.  Consequently, there exist hash functions that can hash the number $n$ in $O(1)$ time, in these models of computation.

In the bit complexity model, it takes at least $\log n$ time to read an integer with $\log n$ bits, so you're right that hashing $n$ will take $\Omega(\log n)$ time.

You might find it useful to read https://en.wikipedia.org/wiki/Transdichotomous_model and https://cstheory.stackexchange.com/q/2656/5038.

Ultimately, the time to compute a hash will depend on the hash function (some hashes might be even slower than the above), but this might be enough to clear up your particular question.


How is it possible that $L_1$ is $NP$? The question is from my complexity-theory course.

The question

If $L_1,L_2,L_3 \in \lbrace 0,1 \rbrace^*$, and different from $\lbrace 0,1 \rbrace^*$ and from the empty language, prove that if $L_1 \leq_p L_2  \cap L_3$, where $L_2 \in NP$ and $L_3 \in P$ then $L_1 \in NP$

My answer

Due to the fact that $P \subseteq NP$, we know that $L_2 \in NP$ and that $L_1 \in P$. $L_2 \cap L_3$ is at most $L_3$ so $L_2 \cap L_3 \in P$ then I proved that $L_1 \in P$. But the question asks to prove that $L_1 \in NP$. Is it a joke? Am i missing something?

No, your proof is faulty.  You claim "we know that $L_1 \in P$", but that doesn't follow.  You haven't justified that claim, and I don't think it's true. It's not clear why you think that would be true, so it's hard to say why you went astray, but that's the first step that is wrong.  Also "is at most $L_3$ is not well-defined, and the intersection of a language in $P$ and a language in $NP$ is not necessarily in $P$.

I think you need to be more careful with your proofs: you have multiple steps where you make claims that simply don't follow from the previous steps.  I recommend you justify each step much more carefully, in more detail -- and if you can't, you should be suspicious of whether it is actually true.