Confusing equivalence $\Phi(n,n)\downarrow \Leftrightarrow \text{HALT}(n,n)$ Let $B$ be a recursive enumerable set and $B = W_n$, where $W_n = \{x \in \mathbb N \mid \Phi(x,n)\downarrow\}$ and $\Phi^{(n)}(x_1, \ldots, x_n, y)$ is the value of the function at the terminal snaphot.

There is a definition that leaves me really confused:
$$n \in W_n \Leftrightarrow \Phi(n,n)\downarrow \Leftrightarrow \text{HALT}(n,n)$$

the thing is we know that $\text{HALT}$ is not computable, therefore is is undefined so how is it possible that it is equivalent to $\Phi(n,n)\downarrow$ which is actually a defined function? What am I missing here?

The function HALT is perfectly defined, it's just not computable - there is no program that computes it. Similarly, $\Phi(n,n) \downarrow$ is not a condition that can be computed by a program. The situation is asymmetric: if $\Phi(n,n) \downarrow$ then a program can verify that, but in the other case you're at loss. This is because HALT is recursively enumerable (partially computable).


Does Bloom filter with false positive rate greater than 0.5 make sense? If the false positive error rate is greater than 0.5 then a Bloom filter is no different from coin flip, right?

Still, if one does implement this data structure with, say, P=0.55 then it would still work.

Should the constructor method of a Bloom filter implementation forbid values of P greater than 0.5?

A Bloom filter never gives a false negative. This is the property that makes them desirable in many situations. They are appropriate for any situation where the existence of false positives is a potential performance issue, but not a correctness issue.

One obvious example is where the filter is used to avoid a more expensive check. Let's try to quantify this a bit, to see what I mean.

Suppose that you are trying to represent some subset of a universe of $S \subseteq U$. We'll further assume that you are testing elements of $U$ for membership in $S$ with equal probability.

Let $p$ be the proportion of elements that are in the set (i.e. $p =
   \frac{|S|}{|U|}$).
Let $c_p$ be the cost of a precise test (measured in time, cycles,
disk accesses, or whatever seems appropriate).
Let $c_b$ be the cost of a Bloom filter test, and we hope that $c_b <
   c_p$.
Let $q$ be the false positive rate of the Bloom filter.

If we only performed precise tests, the cost of each test is $c_p$.

If we perform a Bloom filter test first, the cost of each test is $c_b$ plus $c_p$ times probability that we need to perform a precise test, whether due to true positives or false positives.

By the inclusion-exclusion principle, the average cost of this test is:

$$c_b + c_p(p + q - pq)$$

As long as $c_p > c_b + c_p(p + q - pq)$, the Bloom filter test gives you a net performance gain.

As you can see, the false positive rate $q$ is not the only important number here; Bloom filters with higher $q$ may, for example, have smaller $c_b$ because physically smaller data structures are more cache-friendly.

For completeness, I will note that having a backup precise test isn't the only use case for Bloom filters. There are other situations where false positives are tolerable.

Consider a network protocol where two systems on different machines need to be kept in sync. You would like to only transmit the changes, to save bandwidth. But occasionally transmitting some data that you don't need to transmit is not as bad as failing to transmit data that needs to be transmitted. It may be wasteful to over-transmit, but it's not incorrect to do so.


How do threads decide when to 'go'? I have written some code that animates two boxes using HTML5 and JavaScript threads. I set them up to move at a fixed rate, which is the same:

executeEvery(box1.animate(), 10);
executeEvery(box2.animate(), 10);

The result is weird for reasons not important here.
This to me seems to be the two executeEvery calls not working in unison - probably some asynchronous issue. Because animate() is a complex function call, the threads behaviour is seemingly erratic.

I am asking here because I think this problem is deeper than a JavaScript issue. Why does this not work as intended?

There are (at least) four reasons.

They do not start at the same time. Before the second executeEvery is even found by the interpreter, the first one may already have executed some steps!
You don't even know if the platform supports parallelism. So you can only expect one move to be computed after the other; you may be able to control the relative speed (see below).
The threads themselves don't have any control over this (on most machines).
Either a virtual or the actual machine runs a scheduler that decides which process or thread runs when. For the programmer, the only robust way to deal with this is by assuming non-determinism (i.e. arbitrary order).
wait(10) won't wait for exactly 10ms. Even active waiting can get you only so close to the exact time frame.

If you want to execute the updates simultaneously -- in the sense that both boxes make their $i$th move before they do their respective $(i+1)$th -- you will have to use means of synchronisation, e.g. a barrier.


Is there a grammar for this language? $w^{m-1}aca^m$? I have to form a free context grammar for this language $w^{m-1}aca^m$ where $w \in \{a,b\}$, so what I have been able to do is this:
$X \rightarrow SacA$
$S \rightarrow aS|bS$
$A \rightarrow aA$
But I don't know how to do it or if possible, condition the exponents as long as $ S $ is repeated $ m-1 $ times, and $ A $, $ m $ times.

You attack it from the exact wrong side.
First, the language is the same as $\{w^m aca a^m|w\in\{a,b\},m\in\mathbb{N}\}$. For this, you apply a rule that adds $w$ on the left and $a$ on the right repeatedly, and then inserts $aca$ in the middle and is done. By using one rule that adds both on the left and the right side, you make the number of w's and a's the same.
$S \rightarrow WSa$
$S \rightarrow aca$
$W \rightarrow a|b$
That’s it.


Counting directed graphs I am trying to find a computable, injective and bijective function $f: \mathbb{N} \to A$ where $A$ is the set of all (finite) directed graphs up to isomorphism (also with no edge repetitions). Which means $A$ is containing equivalence classes defined by isomorphism.

i.e, given a graph (class) example $[G] \in A$ where $V_G = \{1,2\}$ and $E_G = \{(1,2)\}$ then if $G'$ is defined by $V_{G'} = \{3,4\}$ and $E_{G'}=\{(3,4)\}$ then $G' \in [G]$ and also if $G''$ is defined by $V_{G''} = \{1,2\}$ and $E_{G''}=\{(2,1)\}$ then $G'' \in [G]$.

In general $G' \in [G]$ if and only if $G'$ is isomorphic to $G$.

I need it to fulfill the restrictions:

If $|V_{[G]}| \leq |V_{[G']}|$ then $f^{-1}([G]) \leq f^{-1}([G'])$
If $|E_{[G]}| \leq |E_{[G']}|$ then $f^{-1}([G]) \leq f^{-1}([G'])$

I think the steps should be to give order to $[G], [G']$ such that $|V_{[G]}| = |V_{[G']}|$ and $|E_{[G]}| = |E_{[G']}|$ in some natural way, find how to calculate the number of $[G'] \in A$ such that $|V_{[G]}| = |V_{[G']}|$ and $|E_{[G]}| = |E_{[G']}|$ as function of $n=|V_{[G]}|, m=|E_{[G]}|$ and then somehow find $f$. Not sure how to go about these steps, or how to find $f$ in some other way?

Thanks for any help!

Sure.  Such a function exists.  You have specified it.  Basically, you order the equivalence classes according first to number of vertices, and second by number of edges.  There are countably many graphs, so countably many equivalence classes, so they can be enumerated.  When you can enumerate them, they can be put into bijective correspondence with $\mathbb{N}$.

This function is computable, by enumerating all graphs with a certain number of vertices and edges.  e.g., for each $n:=1,2,3,\dots$, for each $m:=0,1,2,\dots,n^2$, for each graph containing $n$ vertices and $m$ edges, test whether it is isomorphic to any you have computed before, and use that to enumerate the graphs.  Of course, this will be a particularly inefficient algorithm.

In principle there is no known polynomial-time algorithm for computing graph isomorphism, so I would not expect a polynomial-time algorithm for $f$ (but this is not a proof; and it's still possible there might exist algorithms that are relatively efficient in practice).


Find list of tickets with best price sum I have an optimization problem, where i need to find set of tickets for certain period, such that sum of prices for these tickets is minimal.
Algo should accepts list of trips and list of tickets as input. And output list of tickets with min possible sum price with conditions that this list of tickets covers all trips.
Trip has following fields:
OriginZone
DestinationZone
EndOfTripTimestamp

Ticket object consists of these fields:
OriginZone
DestinationZone
MaxNumberOfTransfers  // 0 if limited by duration
MaxDuration           // 0 if limited by transfers
Price

It's considered that ticket covers trip if Ticket.OriginZone =< Trip.OriginZone and Ticket.DestinationZone >= Trip.DestinationZone. Example:
Ticket {OriginZone: 1, DestinationZone: 4, MaxNumberOfTransfers: 1, MaxDuration: 0} covers trip {OriginZone: 2, DestinationZone: 3}
MaxNumberOfTransfers specifies how much times this ticket can be used. If value it's value is 2, this ticket can cover 2 trips that happen between OriginZone and DestinationZone. MaxDuration specifies period in seconds, in which this ticket can be used from time of purchase(for example if ticket is valid for 24 hours, this field will be set to 24 * 3600). It should be considered that ticket was bought right before first trip that it's used for.
This fields are exclusive. So if MaxDuration field is set, than MaxNumberOfTransfers is not used.
Here is example, of how this algo should work:
> trips = [
{OriginZone: 1, DestinationZone: 2, EndOfTripTimestamp: 2020-09-16T15:00:00},
{OriginZone: 3, DestinationZone: 4, EndOfTripTimestamp: 2020-09-16T16:00:00},
{OriginZone: 1, DestinationZone: 2, EndOfTripTimestamp: 2020-09-16T17:00:00},
{OriginZone: 3, DestinationZone: 4, EndOfTripTimestamp: 2020-09-17T18:00:00}
]
> tickets = [
{OriginZone: 3, DestinationZone: 4, MaxNumberOfTransfers 1, MaxDuration: 0, Price: 10},
{OriginZone: 1, DestinationZone: 2, MaxNumberOfTransfers 1, MaxDuration: 0, Price: 10},
{OriginZone: 3, DestinationZone: 4, MaxNumberOfTransfers 2, MaxDuration: 0, Price: 15},
{OriginZone: 1, DestinationZone: 2, MaxNumberOfTransfers 2, MaxDuration: 0, Price: 15},
{OriginZone: 3, DestinationZone: 4, MaxNumberOfTransfers 0, MaxDuration: 24 * 3600, Price: 13},
{OriginZone: 1, DestinationZone: 2, MaxNumberOfTransfers 0, MaxDuration: 24 * 3600, Price: 13}
]
> algo(trips, tickets)
OUTPUT:
  {OriginZone: 1, DestinationZone: 2, MaxNumberOfTransfers 0, MaxDuration: 24 * 3600, Price: 13}
  {OriginZone: 3, DestinationZone: 4, MaxNumberOfTransfers 2, MaxDuration: 0, Price: 15},

To clarify this example, here you see 4 trips that happened in period of 2 days. In first day there's 3 trips overall, 2 from zone 1 to 2, and one from zone 3 to 4. And on second day there's one trip from zone 3 to 4. So algorithm picks 2 tickets to cover these trips -- 24 hour ticket for zones 1 to 2 and ticket with 2 transfers for zones 3 to 4.
Overall this looks like combinatorial optimization problem, but i wasn't able to find any non trivial algorithm for solving it. So, currently i'm using brute force algo that looks like:
recursive_function(trips, tickets):
    trip = trips[0]
    find best price iterating over tickets:
        price, tickets_list = recursive_function(trips[1:], tickets)

   return tickets_list with best price sum

So, my question is, is there any common problem that's similar to my and have non-trivial solution? Or maybe someone can recommend me some topics to look closely into.

If you wanted to solve it in practice, I would recommend that you try using an ILP solver.  You can express this as an instance of integer linear programming, then use an off-the-shelf ILP solver.
Introduce zero-or-one variables $x_i$ (indicates whether the $i$th ticket is bought or not) and $y_{ij}$ (indicates whether the $i$th ticket is used to cover the $j$th trip).  Then you can write linear inequalities to express the requirements; e.g., $\sum_j y_{ij} \le d_i x_i$ where $d_i$ is the max duration of ticket $i$, and so on.  The total price is a linear function of the variables, so you can minimize that objective function, subject to these inequalities.
I don't know whether there is a more efficient algorithm.


Is a graph of zero nodes/vertices connected? Suppose there is a graph G of zero nodes, there is an even number of nodes. By definition of connectivity, the graph G is connected when there is a path between every pair of nodes. But there are no pair of nodes since there are zero nodes.

Does this mean G is connected because there is a path for every pair of nodes (in this case zero) or would this mean G is not connected because there are no paths?

These issues are discussed in the classical paper Is the null graph a pointless concept? by Harary and Read. The conclusion is that usually when we think of graphs, we don't think of them as having zero nodes. Definitions which are equivalent for non-empty graphs can differ on the null graph. Whenever we use null graphs we have to be very careful and choose our definitions according to usage.

Given a definition of connectedness, you can check whether the null graph satisfies it. For example, taking your definition (there is a path connecting any two vertices), the null graph is connected since this condition is satisfied vacuously.


What's the difference between transdichotomous model and RAM? In Wikipedia, it says

  the transdichotomous model is a variation of the random access machine in which the machine word size is assumed to match the problem size.

However, a random access machine is by definition a register machine, whose registers can store any non-negative number.

In addition, the concept of "word" is even not mentioned in the Wikipedia page of random access machine.

So what's the difference between transdichotomous model and RAM?

The transdichotomous model is first proposed by Michael Fredman and Dan Willard [1]. They wrote the motivation as

  ... On the other hand, with the inclusion of division and Boolean operations, they obtain a linear time algorithm. This linear time algorithm, however, suffers from an abuse of the unit cost assumption. In particular, the algorithm generates operands during the course of its computation whose individual lengths are $N^2$ times the length of the largest of the $N$ numbers to be sorted.

  What seems to be needed is a computational model that avoids the potential abuses of the unit cost random access machine, but allows for unit cost operations among operands of “reasonable” size, i.e., operands of size commensurate with the sizes of the numbers to be sorted. Accordingly, we consider a reformulation of the sorting problem wherein our machine has a $b$-bit word size, and each of the $N$ input numbers is assumed to be a non-negative integer less than $2^b$ (and hence each tits into one word). Moreover, it is desirable that a sorting algorithm use only $O(N)$ words of memory.

That is to say, in contrast with RAM model, the transdichotomous model is less powerful because it does not allow unit cost operations on arbitrary large number. For example, in the sorting problem where the largest number is $m$, the transdichotomous model only allows unit cost operations on numbers no more than $m$.

[1] Fredman, M. L., & Willard, D. E. (1993). Surpassing the information theoretic bound with fusion trees. Journal of computer and system sciences, 47(3), 424-436.


Lower bound for $k$-sorting an array This is exercise 2 of the lecture note by Jeff Erickson on decision tree lower bounds.

We say that an array $A[1 \ldots n]$ is $k$-sorted if it can be divided into $k$ blocks, each of size $n/k$ (we assume that $n/k$ is an integer), such that the elements in each block are larger than the elements in earlier blocks and smaller than elements in later blocks. The elements within each block need not be sorted.
(a) Describe an algorithm that $k$-sorts an arbitrary array in $O(n \log k)$ time.
(b) Prove that any comparison-based $k$-sorting algorithm requires $\Omega(n \log k)$ comparisons in the worst case.
(c) Describe an algorithm that completely sorts an already $k$-sorted array in $O(n \log(n/k))$ time.
(d) Prove that any comparison-based algorithm to completely sort a $k$-sorted array requires $\Omega(n \log(n/k))$ comparisons in the worst case.

The first problem can be solved by modifying the quicksort algorithm. However, I am stuck with the second problem which asks for a lower bound. My attempt is to use the decision tree technique. I think the number of leaves of the decision tree is at least $((\frac{n}{k})!)^{k}$. Therefore, the height of the decision tree must be
$$ H \ge \log ((\frac{n}{k})!)^{k} = k \log (\frac{n}{k})! = \Omega(k \frac{n}{k} \log \frac{n}{k}) = \Omega(n \log \frac{n}{k}),$$
which is not the desired result $\Omega(n \log k)$.
What is wrong with my argument? And how to establish the lower bound $\Omega(n \log k)$?

From the result of $k$-sorting an array you can tell which elements of the original array were the $n/k$ smallest, the $n/k$ largest, and which belong to each of the other $k-2$ blocks of $n/k$ elements in between. In particular, there are at least $\binom{n}{n/k,\ldots,n/k}$ different leaves, which works out to $\frac{n!}{(n/k)!^k} = \exp \Theta(n\log k)$. This gives you the correct lower bound.

What you calculated is the number of different ways to completely sorted a $k$-sorted permutation. Therefore your lower bound is for sorting a $k$-sorted permutation, and for this task your lower bound is tight: a $k$-sorted permutation can be sorted in $O(n\log (n/k))$.


Historical examples of bad security policies/mechanisms that we got stuck with through switching costs? The following process seems to be a recurring one:

Initial design. Commercial organisations invent and implement a design that seems at the time to work.
Problem discovered, new design suggested. Due to new developments, or just because the designers missed something, a problem with the design is discovered. Academics find a solution to the problem, and a new design is proposed.
Old, sub-optimal design persists due to existing production. However, the original sub-optimal design is maintained, because a large amount of devices with the old design are already deployed, and for various reasons (network effects, the need for compatibility between devices, etc), this means producers don't want to switch. Or alternatively, new production switches, but we still have to deal with the old design because of the large already produced devices.

I am looking for historical examples of such a process in the context of the IT security of CPU/instruction-set-architecture:

What designs of instruction sets/CPU's are we stuck with that are bad from a security perspective, but that are maintained because the cost of switching is high? (I can imagine that this is also intertwined with OS design and internet protocols).

There were some boo-boos with WiFi, thus the various generations of security protocols. Fortunately, most of the heavy lifting is done in firmware that is uploaded to the card/computer.

Initial (analog) cell phone technologies were trivial to intercept, newer (digital) ones much harder, but there were (are?) still gaps. Needless to say, switching required redoing much infrastructure and everybody getting new phones.

For some entertaining war stories, check out Ross Anderson's "Security engineering" (available as PDFs for each chapter on his homepage). Nicely written, a real classic.


Calculate $(u,v) \in \mathbb{R}$ so that $\sum (a_i + b_i)$ with $ a_i \geq u$ and $b_i \geq v$ maximizes I have two datasets $A$ and $B$:

$A = \{1, 5, -34, 34.34323, -23.5444, 9.43, ....\}$
$B = \{-0.5, 44, -0.243, -3455, 2.22221, -23.23, ....\}$

Those datasets contain a big amount of "random" numbers (They are actually not random, but their source does not matter for this question). Both datasets always have the same size.

Now I need to calculate two numbers $(u,v) \in \mathbb{R}$ so that $\sum (a_i + b_i)$ with $ a_i \geq u$ and  $b_i \geq v$ reaches the biggest possible value.

For clarification: Say $a_3 \geq u$ but $b_3 < v$. Then $(a_3 + b_3)$ is not included in the sum. That is meant by $ a_i \geq u$ and  $b_i \geq v$.

Does an algorithm for the solution to this problem already exist? If not, I am open for ideas.

For each pair of elements, $(a_{i},b_{i})$, you can calculate the sum of all the $(a_j+b_j)$ where $a_{j}$ and $b_{j}$ are both greater than or equal to $a_{i}$ and $b_{i}$. So an algorithm could look like:

largest_pair = 0
largest_value = -∞
for each i:
    for each j:
        total = 0
        if(a[j] >= a[i] & b[j] >= b[i])
            total += a[j] + b[j]
    if(total>largest_value)
        largest_value = total
        largest_pair = i
u = a[largest_pair]
v = b[largest_pair]
output u,v

This algorithm is $O(n^2)$ but is easily adaptable to n-variables, and there should be some shortcuts that could speed it up


How to count the combinations not greater than a given volume in a knapsack problem? You are given a certain set of items with weight wi and the volume of the bag.

Case:

Input:

3 (count of items) 10 (volume of the bag)
1 2 4 (weight for each item)

Output

8 (since you can put any item in or not 2 * 2 *2)

I have a naive solution using DFS as

public class Main {
    public static void main(String... args) throws Exception {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int volume = scanner.nextInt();
        int[] weights = new int[size];
        for (int i = 0; i < size; ++i) weights[i] = scanner.nextInt();
        System.out.println(getCounts(weights, 0, volume));
    }

    private static int getCounts(int[] nums, int pos, int target) {
        if (target < 0) return 0;
        if (pos >= nums.length) return 1;
        return getCounts(nums, pos+1, target) +
            getCounts(nums, pos+1, target-nums[pos]);
    }
}

As expected, it produced TLE and I added cache to avoid re-calculation as

public class Main {
    private static int[][] cache;
    public static void main(String... args) throws Exception {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int volume = scanner.nextInt();
        cache = new int[size+1][volume+1];
        for (int i = 0; i <= size; ++i) {
            for (int j = 0; j <= volume; ++j) {
                cache[i][j] = -1;
            }
        }
        int[] weights = new int[size];
        for (int i = 0; i < size; ++i) weights[i] = scanner.nextInt();
        System.out.println(getCounts(weights, 0, volume));
    }

    private static int getCounts(int[] nums, int pos, int target) {
        if (target < 0) return 0;
        if (pos == nums.length) return 1;
        if (cache[pos][target] != -1) return cache[pos][target];
        int count = getCounts(nums, pos+1, target) +
            getCounts(nums, pos+1, target-nums[pos]);
        cache[pos][target] = count;
        return count;
    }
}

But the OJ prompt me of memory error while the memory is within the limit => 13064K < 32768K, any idea to solve this issue?

Why did it fail?
Could a DP solution without backtracking be found for this?

Any help will be appreciated :)

Here is the original problem in Chinese.

Why did it fail?

Look at the code cache = new int[size+1][volume+1];. Suppose size is 1 and volume is $10^9$. One int uses 4 bytes. So this cache will use $4 \times 2 \times 10^9$ bytes, which is about 8G, which is way much bigger than the limit, 32768K. So the online judge will show you out-of-memory error.

  Could a DP solution without backtracking be found for this?

The right strategy here is called "meet in the middle". Here is the idea of the algorithm, where $w$ is the volume of the bag.

Split the items into $A$ and $B$, two lists of approximately equal size.
Compute all possible sums of items in A, appending them to array arrA. Sort arrA.
Compute all possible sums of items in A, appending them to array arrB. Sort arrB.
For each number in arrA, find the last element in arrB such that the sum of the two is not greater than $w$. Let its index be $upper$. Add $upper + 1$ to the total.
Return total.

The time-complexity of the algorithm is $O(n2^{n/2})$, which comes from sorting two arrays of size about $2^{n/2}$. For $n= 30$, we get $30\times 2^{30/2}=30\times32768$, which is about 1 million.

The space-complexity of the algorithm is $O(2^{n/2})$. For example, if $n= 30$, we allocate two arrays of longs of size $2^{15}$, which spans $2\times2^{15}\times8$ bytes, which is less than 600K. We need some extra work memory for sorting and etc, which will at most triple the memory allocated specifically for our algorithm.

Here is the implementation in Java.

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        final int n = sc.nextInt();
        final int w = sc.nextInt();
        final long[] v = new long[n];
        for (int i = 0; i < n; ++i) v[i] = sc.nextLong();

        int total;
        if (n == 1) {
            if (v[0] <= w) total = 2;
            else total = 1;
        } else {
            final int half_n = n / 2;

            final long[] front = getSortedSums(v, 0, half_n);
            final long[] behind = getSortedSums(v, half_n, n);

            int lastIndexFront = front.length - 1;
            while (front[lastIndexFront] > w) lastIndexFront--;

            int upper = behind.length - 1;
            for (int i = 0; i <= lastIndexFront; i++) {
                while (front[i] + behind[upper] > w) upper--;
                total += upper + 1;
            }
        }

        System.out.println(total);
    }

    // Return all possible sums of elements in the specified segment of v,
    // sorted. Note the first sum is 0, representing the empty sum.
    private static long[] getSortedSums(long[] v, final int low, final int high) {
        int index = 0;
        final long[] sums = new long[1 << (high - low)];
        for (int i = low; i < high; i++) {
            long u = v[i];
            int end = 1 << (i - low);
            for (int j = 0; j < end; j++) {
                sums[++index] = sums[j] + u;
            }
        }
        Arrays.sort(sums);
        return sums;
    }
}


Algorithm analysis in the presence of undefined functions I wonder how we can perform algorithm analysis when in an algorithm we have calls of functions whose definition we do not know, e.g. functions delivered by external libraries.

There are two ways to do this.  If you're lucky, the implementer of the external library will have given you a runtime analysis of their code.  If you're not, you can use an oracle model of computation. In a sense, this is treating the library routines as if they run in constant time. Of course, that would be ridiculous but an oracle-based analysis is a little smarter than that because it allows you to quantify how many times the oracle is accessed.  For example, your answer might end up being something like, "The running time is $O(n^2)$ plus the cost of $O(\log n)$ calls to makeSausage() on instances of at most linear size."


Does an algorithm exist for scheduling jobs on two processors? I have two processors, and I want to schedule as many jobs as I can. I have their starting time and finishing time, and each job has to be unique to a processor (no overlap). I looked around and found one processor, or n processors - but none for two. I thought it'd be popular but I can't find if anyone's done this before?

My idea is just like the normal interval scheduling algorithm, to implement a greedy approach. First, sort by earliest starting time. Then, start by scheduling the first job to the first processor. The second job to the second processor. From there, schedule the next job to the processor who is going to finish their job first.

I think it would work, but I think this is in O(n^2) time and I'm trying to get to O(n) or O(n log n)

Any help is appreciated :)

The algorithms for $n$ processors will do the job just fine for the 2-processor case. In this context, $n$ does not refer to the number of tasks to be scheduled, which probably caused the confusion when you looked for algorithms.

Then, there is a great website for searching for scheduling problems, which you can access at http://www-desir.lip6.fr/~durrc/query/ -- You select the properties of your problem and will receive an overview of known results. Your case is called $P2 \mid r_j \mid C_\mathit{max}$ on that page. This is not quite your setting, as this assumes that the finishing times are the same for all tasks. But even in this slightly easier case, the web page gives you a reference for an NP-completeness proof for your problem:

Complexity of machine scheduling problems, Lenstra, J.K. and Rinnooy Kan, A.H.G. and Brucker, P., Ann. of Discrete Math., Vol. 1, p.343-362 1977.

So your algorithm will probably not yield a feasible schedule whenever there exists one.


Automatic translation between formal languages There are parser generators (some of which are limited to certain classes of grammars) which, given a grammar, automatically generate a parser for that grammar.

Would it be possible to make a general-purpose translator generator to automatically translate from a string in the language with production rules described by grammar $G_1$ to a string in the language with production rules described by grammar $G_2$? If so, what rules would have to be imposed? For practical purposes let's say these grammars must both be CFGs. Would a formalization of semantic rules for the grammars also have to specified for the translator generator?

An example of this hypothetical, general-purpose translator generator:
the translator generator is given grammar $G_1$ (which is a CFG representing a context-insenitive adaptation of the C programming language), $G_2$ (which is a CFG representing a context-insenitive adaptation of the JavaScript programming language), and a formalization of the semantic rules of the language with production rules described by grammar $G_2$1. The translator generator is expected to produce a translator which takes as input a string in the language with production rules described by grammar $G_1$ and translates that string to a string in the language with production rules described by grammar $G_2$.

1 I am not entirely sure of what this formalization of the language's semantic rules would look like, so if there exists some formalization which would make the existence of this general-purpose translator generator decidable, then I would also welcome suggestions on what this formalization would look like.

I think you are asking this from a stand point of specific tools so let me answer this in two parts.

Theory Part (ideal view):

There is a notion of languages and a notion of computational systems that except these different classes of languages. Finite Automata can accept regular languages, Pushdown Automata can accept context-free languages. If we go all the way up in the Chomsky hierarchy we get recursively enumerable languages which are accepted by turing machines.

As long as the class of languages define by a certain syntax is less than or equal in power to the target syntax's class of languages then this is possible (at least in principal). Parser generators typically compile context-free grammars to turing machines (or turing complete systems rather) which is just jumping rather far in Chomsky hierarchy. Nicely however this allows us to use context-free grammars in settings where we need recursive enumerability like interpreters. I could in principal compile a context-free grammar to a context-free grammar but defined using a different syntax; this is just an issue of the syntax being used to define context-free grammars. What I could not however do is compile a context-free grammar to a regular expression. No semantic rules need apply in this ideal view.

Practical part:

Real parser generators don't just generate code that accepts a given context free language however. They add in bits of your code to produce abstract syntax trees for your programs to use. I think the details of translating something like Antlr 3 (LL grammars) to Bison (LR grammars which are more general) or some other parser generator would be a bit tricky; I wouldn't want to try it. They probably use slightly different template systems for your code for starters. It could be that they execute your code in different orders so unless your code was pure there would really be no hope of translating the code properly.

So I think the answer to "would semantic rules for the grammars also have to formally specified" would be yes. The code that generates the ASTs would need to be functional and pure or something like that. The substitution principal needs to apply I think which is not something that generally applies except in languages like Haskell where even their effectual code has the substitution property.

My bet is that something like this is possible between the right tools but I think it is a very tricky thing.


Determine whether a sorted array contain at least 4 distinct elements in O(log n) time On one of my previous courseworks, I was faced with the following problem, which I think is unrealistic when using a direct / straightforward approach that usually algorithms have by leveraging certain data structures like dictionaries, etc.

Design an O(log n) algorithm whose input is a sorted list A. The algorithm
should return true if A contains at least 4 distinct elements. Otherwise
the algorithm should return false.

My lecturer came up with the following solution:
def ThreeDiff(A):
  if A[0]==A[len(A)-1]:
    return -1

  minind=0
  maxind=len(A)-1

  while maxind-mind>1:
    midind=int((minind+maxind)/2)
    if A[midind]>A[minind] and A[midind]<A[maxind]:
      return midind
    if A[midind]==A[minind]:
      minind=midind
    else:
     maxind=midind
  return -1

def FourDiff(A):
  midind=ThreeDiff(A)
  if midind==-1:
    return false
  return ThreeDiff(A[0:midind+1])!=- 1 or ThreeDiff(A[midind:len(A)]) != -1

Is there a cleaner or better way to solve this problem?

Here is a cleaner and better way to solve the problem.
# Return the smallest index where the element is bigger than `A[start_index]`.
# If `len(A)` is returned, no element is bigger than `A[start_index]`.
def next_bigger_element(start_index, A):
    lo, hi = start_index, len(A)
    while lo + 1 < hi:
        mid = (lo + hi) // 2
        if A[mid] == A[start_index]:
            lo = mid
        else:
            hi = mid
    return hi

def distinct_elements_at_least(k, A):
    if len(A) == 0:
        return k <= 0
    index = 0
    count = 1
    # keep finding the next bigger element until `k` elements have
    # been found or we have reached the end of the array.
    while count < k and A[index] != A[-1]:
        index = next_bigger_element(index, A)
        count += 1
    return count >= k

To find whether A contains at least 4 distinct elements, just call distinct_elements_at_least(4, A).
This program works correctly for any given number k. For example, it can be used to check whether A has 0 element  or whether A has 7 distinct elements. For any fixed k, it works in $O(\log n)$ time as at most k binary searches on an interval of size at most n are done.

If you do not mind import bisect, you may prefer the following shorter code, since method next_bigger_element is no longer needed.
from bisect import bisect_right

def distinct_elements_at_least(k, A):
    if len(A) == 0:
        return k <= 0
    index = 0
    count = 0
    while index < len(A) and count < k:
        count += 1
        index = bisect_right(A, A[index], index + 1)
    return count >= k


SimRank on a weighted directed graph (how to calculate node similarity) I have a weighted directed graph (it's sparse, 35,000 nodes and 19 million edges) and would like to calculate similarity scores for pairs of nodes. SimRank would be ideal for this purpose, except that it applies to unweighted graphs.

It's easy to adapt the matrix representation of SimRank to use weighted edges:

$\mathbf{S} = \max\{C \cdot (\mathbf{A}^T \cdot \mathbf{S} \cdot \mathbf{A}),\mathbf{I}\}$

Just replace the entries in the adjacency matrix $\mathbf{A}$ with the edge weights. But I don't see how to derive the "iteration to a fixed-point" method from this formula.

$s_{k+1}(a, b) = \frac{C}{\left|I(a)\right|\left|I(b)\right|} \cdot \sum_{i \in I(a)} \sum_{j \in I(b)} s_{k}(i, j)$

Is the following method correct?

$s_{k+1}(a, b) = C \cdot \sum_{i \in I(a)} \sum_{j \in I(b)} s_{k}(i, j) \cdot w(i, a) \cdot w(j, b)$

My reasoning is that the original method is equivalent to this:

$s_{k+1}(a, b) = C \cdot \sum_{i \in I(a)} \sum_{j \in I(b)} s_{k}(i, j) \cdot \frac{1}{\left|I(a)\right|} \cdot \frac{1}{\left|I(b)\right|}$

so I replaced the trivially equal weights with the actual ones I have. Confirmation would be nice, though.

If there is a superior method to SimRank, I would like to hear about it. (I'm concerned with improvements to accuracy, not performance; this is a small data set.)

Edit: A different similarity metric that's nearly as accurate but performs a lot better would actually be useful too. My initial tests of SimRank are very slow, and the potential optimizations are not simple to code.

The paper "SimRank++: Query Rewriting through Link Analysis of the Click Graph" describes a weighted SimRank algorithm that is similar to my attempt. It uses this formula to update similarity scores:

$s_{k+1}(a, b) = \text{evidence}(a, b) \cdot C \cdot \sum_{i \in I(a)} \sum_{j \in I(b)} s_{k}(i, j) \cdot w(i, a) \cdot w(j, b) \cdot \text{spread}(i) \cdot \text{spread}(j)$

$\text{evidence}(a, b) = \sum_{i=1}^{\left|I(a) \cap I(b)\right|} \frac{1}{2^i}$

$\text{spread}(i) = e^{-\text{Var}(\{w(i, a) ~|~ a \in O(i)\})}$

Note that the weights should be normalized to sum to 1, which I was already doing. SimRank++ also incorporates evidence scores (which account for the quantity of incoming edges) and spread (which accounts for variance of outgoing edge weights).


Basic approximation algorithms understanding Question:

Suppose we have 2 algorithms $Alg1$ and $Alg2$ for the same minimization problem. We know that $Alg1$ is a $2$-approximation algorithm and $Alg2$ a $4$-approximation algorithm.

Is the following statement true?

There must be an input $I$ such that $Alg2(I) \geq 2 \cdot Alg1(I)$.

My answer:

I think the statement is false:

In order to prove that the statement is false it is sufficient to find one case where $Alg1$ is a $2$-approximation and $Alg2$ is a 4 approximation and that there is no input which satisfies the inequality from the statement.

Does my approach make sense? Is there some other approach or thought process which proves statements of this type true/false that I'm missing?

Note:

$Alg$ is a $\rho$-approximation algorithm for a minimization problem $\iff$ $\forall I.(OPT(I) \leq Alg(I) \leq \rho \cdot OPT(I))$ where $\rho > 1$ and $OPT(I)$ denotes the optimal solution to the minimization problem for the input $I$.

According to your definition (which is the standard definition), an algorithm solving a certain minimization problem is an $\alpha$-approximation algorithm for any $\alpha \geq 1$.

Consider a minimization problem solvable in polynomial time, for example minimum cut. Let Alg1 and Alg2 be algorithms solving this problem exactly. Alg1 is a 2-approximation algorithm and Alg2 is a 4-approximation algorithm, yet there is no input on which Alg2 performs worse than Alg1.


Do NFAs with $\varepsilon$-moves never terminate? Suppose in an NFA we have an $\varepsilon$-move from a state $q_0$ to $q_1$. According to Sipser,

  Without reading any input, the machine splits into multiple copies one following each of the exiting $\varepsilon$-arrows and one staying at the current state. Then the machine proceeds nondeterministically as before.

Here is an application of this logic to our case: upon reaching the state $q_0$ our machine splits into two copies: one in state $q_1$, one in state $q_0$. For the latter copy, execution continues as before, so again another copy of the machine is created in state $q_0$. Thus, a copy of the machine always in state $q_0$ will exist indefinitely.

Is this true? If no, why not? How should I then interpret the description given above?

Sipser proposes an operational intuition for non-determinstic machines. As you have experienced, it's not very useful. In particular, it doesn't relate a lot to the formal definition, and there are more problems down the road¹.

I recommend sticking to the definition: an NFA accepts an input if there is a path from a starting to a final state labelled with the input. That really tells you all you need to know, and all there is to know.

Try to think mathematically instead of computationally.

Parallelism and non-determinism are not the same; you can not build non-deterministic machines in a meaningful sense; cost models (e.g. in complexity theory) for non-deterministic machines don't make sense if you have the split/fork intuition; ...


Are intersection and union redundant? Possibility to get smaller output without negation? I've just started learning relational algebra, so I'm reading a lot of articles for this topic. Not so long ago I've encountered two statements that seem to be quite weird to me.

∩ and ∪ (intersection and union) are in fact redundant in relational algebra and you can rewrite any expression without them.

You can't get a smaller result without using negation. So expressions without it are always monotone

There were no explanation for those, so I'm not sure if those are true. Could you give some examples?

Regarding the first question, as you have said in the comments, you can define a relational algebra intersection with other relational algebra operators. Anyway, relational-algebra union is usually considered a relational algebra basic operator (that cannot be defined with other relational algebra operators).
Regarding monotonicity, we say that a query is monotone if the results of the query increases with the size of the database. More formally, a query $q$ is monotone if and only if, for any given database states $D_1$, $D_2$, where $D_1 \subseteq D_2$, we have $q(D_1) \subseteq q(D_2)$.
For instance, a monotone query might be: "All departments with at least one employee". Indeed, if you have a database state $D_1$ with 1 department with at least one employee (e.g. 'MarketingDepartment'), you know, for sure, that any $D_2 \supseteq D_1$ will still bring you such 'MarketingDepartment', and possibly more (since $D_2$ might have more departments with at least one employee).
A non-monotone query might be: "All departments with NO employee". Indeed, if you have a database state $D_1$ with 1 department with no employee (e.g. 'MarketingDepartment'), you can build a database $D_2 \supset D_1$ where 'MarketingDepartment' $\not\in q(D_2)$. Indeed, in $D_2$ you can add some employee for the 'MarketingDepartment', making 'MarketingDepartment' not satisfy your condition.
In relational-algebra, non-monotonic queries are defined through the set-difference operator (in the previous case: Department $\setminus$ $\pi_{dept}$ Employee). If a relational-algebra query has no set-difference operator involved, it is mononote.


Not satisfiable 3SAT instance implications Suppose we have an instance of 3SAT that is NOT satisfiable and we say $S$.
If in $S$ there are the following $8$ clauses
$\left(a\vee b\vee c\right)\wedge\left(a\vee\bar{b}\vee c\right)\wedge\left(a\vee b\vee\bar{c}\right)\wedge\left(a\vee\bar{b}\vee\bar{c}\right)\wedge\left(\bar{a}\vee b\vee c\right)\wedge\left(\bar{a}\vee\bar{b}\vee c\right)\wedge\left(\bar{a}\vee b\vee\bar{c}\right)\wedge\left(\bar{a}\vee\bar{b}\vee\bar{c}\right)$
we have that anyway we set the Boolean value of the variables $a,b,c$, there is a clause that is false.
If in $S$ instead of $a \vee \bar{b} \vee \bar{c}$ we have
$\left(a\vee e\vee f\right)\wedge\left(a\vee\bar{e}\vee f\right)\wedge\left(a\vee e\vee\bar{f}\right)\wedge\left(a\vee\bar{e}\vee\bar{f}\right)$
this implies that anyway we set the Boolean value of the variables $a,b,c,e,f$, there is a clause that is false.
In the first case, we have
$\left(a\vee b\vee c\right)\wedge\left(a\vee b\vee\bar{c}\right)\Rightarrow \left(a\vee b\right)$
$\left(a\vee \bar{b}\vee c\right)\wedge\left(a\vee \bar{b}\vee\bar{c}\right)\Rightarrow \left(a\vee \bar{b}\right)$
$\left(\bar{a}\vee b\vee c\right)\wedge\left(\bar{a}\vee b\vee\bar{c}\right)\Rightarrow \left(\bar{a}\vee b\right)$
$\left(\bar{a}\vee \bar{b}\vee c\right)\wedge\left(\bar{a}\vee \bar{b}\vee\bar{c}\right)\Rightarrow \left(\bar{a}\vee \bar{b}\right)$
and
$\left(a\vee b\right)\wedge\left(a\vee \bar{b}\right)\wedge\left(\bar{a}\vee b\right)\wedge\left(\bar{a}\vee \bar{b}\right)$
is NOT satisfiable.
In the second case, we have
$\left(a\vee e\vee f\right)\wedge\left(a\vee \bar{e}\vee f\right)\Rightarrow \left(a\vee f\right)$
$\left(a\vee e\vee \bar{f}\right)\wedge\left(a\vee \bar{e}\vee\bar{f}\right)\Rightarrow \left(a\vee \bar{f}\right)$
and
$\left(a\vee f\right)\wedge\left(a\vee \bar{f}\right)\Rightarrow a$
and
$a\Rightarrow\left(b\vee c\right)\wedge\left(\bar{b}\vee c\right)\wedge\left(b\vee\bar{c}\right)\wedge\left(\bar{b}\vee\bar{c}\right)$
and this last conjunction is NOT satisfiable.
The question is: given a NOT satisfiable 3SAT instance, if we apply all possible implications and make the conjunction of the right side of the implications, we get a 2SAT instance (the right side of these impliacations is either the conjunction of two variables or a singol variable); is this 2SAT instance not satisfiable? If it isn't, can you give me an example?

You are describing the Resolution refutation system, which is complete in the sense that if a CNF is unsatisfiable, then it can be proven using Resolution. Resolution is also implicitly used in most SAT solvers.
The width of a Resolution refutation is the maximal number of literals in a clause encountered during the refutation. There are 3CNFs on $n$ variables which require width $\Omega(n)$, for example Tseitin contradictions on 3-regular expanders; see for example Massimo Lauria's lecture notes. This means that every Resolution refutation of these 3CNFs must contain a clause having $\Omega(n)$ literals.


Traversals from the root in AVL trees and Red Black Trees We all know that for insertion() operation in AVL tree following can happen:

We traverse down the tree from root to appropriate node and there insert the key and then for maintaining height balance we have to check heights of the ancestors of the newly inserted node and in doing so, we could end up traversing up to the root.

I completely agree with this.

But according to me the same can happen in Red Black tree because first we would traverse down the tree to appropriate node and then insert the key.Then there is a possibility that a series of rotation and flip color operations could make us traverse the path up to the root.

Now my question is : why following statement is right?

  In AVL tree insert() operation, we first traverse from root to newly inserted node and then from newly inserted node to root. While in Red Black tree insert(), we only traverse once from root to newly inserted node.

It came as a question, which of the following statements is right about AVL and Red Black trees and the option with given statement was marked correct in the answer key. I am trying to figure out mistake in my second observation?

For virtually all kinds of binary search trees, including AVL trees and red-black trees, you can implement insertion in what is called a bottom-up fashion.  This involves two passes through the tree: the first pass starting at the root and moving down the tree to find the right place to do the insertion, and the second pass starting at the insertion point and moving upward toward the root fixing the tree as necessary.  Frequently, these two passes are implemented as one recursive function, where the first pass is going down the recursion, and the second pass is coming back out of the recursion.

For some kinds of binary search trees, including red-black trees but not AVL trees, the "fixes" to the tree can fairly easily be predicted on the way down and performed during a single top-down pass, making the second pass unnecessary.  Such insertion algorithms are typically implemented with a loop rather than recursion, and often run slightly faster in practice than their two-pass counterparts.

Note that, for trees like red-black trees, where you can implement insertion either way, the two different approaches (bottom-up/two-pass vs top-down/one-pass) do not necessarily yield exactly the same tree, but will yield trees that are equivalent.  For example, the exact pattern of red and black nodes may vary slightly, but will still obey all the expected invariants of a red-black tree.


Why is ${n \choose 2}$ a $\Theta(n^2)$ computation? In Cormen's Algorithms textbook, the author casually mentions that ${n \choose 2}$ is $\Theta(n^2)$.

Why is this so? In the calculation

$$
{n \choose 2} = \frac{n!}{(n-2)!2!}
$$

there are $n$ multiplication operations in the numerator and $n$ multiplications in the denominator. That means there are at most $2n+1$ computations to here make (one for the division step), no?

$\Theta$-notation more generally refers to the growth of a function. In terms of computational complexity this function can be done in $O(1)$ as:

$$\frac{n!}{(n-2)!2!} = \frac{n(n-1)}{2!} = \frac{n(n-1)}{2}$$

Since there are a finite number of multiplications and multiplication is sometimes treated as $O(1)$ this has constant computational time. But, the author is not referring to the computational complexity of this function. Instead he is referring to the growth of the function:

$$\frac{n(n-1)}{2} = \frac{n^2}{2} - \frac{n}{2} \in \Theta(n^2)$$


Is it possible to denote "any single alphabet symbol" in an FSA state diagram? This is a possible duplicate of the following (but not sure it answered my question):
Is it possible to support .(any symbol) or \d, \w, \W in DFA

My professor is asking for a finite automata state diagram for some language that accepts even length strings (actually it's more complicated than that, but I'm starting with that as a subset). But he didn't define the alphabet of the language (on purpose). We can assume the alphabet is definite, but I assume I can't just use an arbitrary alphabet instance.

Here is a DFA/NFA state diagram concept that I think accepts even strings (including $\epsilon$):

But what alphabet symbols / terminals should I put on the edges? It shouldn't be $\Sigma^*$. It shouldn't be $\epsilon$. Can I use $.$ ? Can I use a $*$ ? Can I use anything as long as I describe what it means?

EDIT - I just found the use of $*$ in these notes of an Illinois course (p.4):

The formal representation of an automaton is the tuple giving its state set, alphabet, transition function, start state and set of accepting states. The diagram is not a formal representation: it's just an informal way of showing what the automaton does.

As such, you can label the arrows however you want, as long as it's clear what each label means. If you think a label might be unclear, you can always add a caption to your diagram that explains what it would mean.

"." is a poor label, since it's too easy to miss. "*" is a confusing label since, in regular expressions, "*" means "any number of times", not "any symbol". Since it's quite common to see arrows in automata labelled, e.g., "$0,1$", I'd probably label the arrow "$\sigma_1, \dots, \sigma_k$" and note in the caption that $\Sigma = \{\sigma_1, \dots, \sigma_k\}$. Or you could just label the arrow "$\Sigma$".


Run time for a specific loop confusion I have a loop:
for(int i = 1; i < N; i*=5) {...}

where {...} is some statement.

I'm trying to understand its run time. So, far I know that:

We start with $i = 1$
We finish when $i > n$
$i$ is incremented by being multiplied by 5.

So, would the run-time be $\log_5(n-1)$? The reason I'm not sure it's because I thought when analyzing algorithms we had to use base 2 log functions. If the latter is the case how would I got about converting $\log_5$ to $\log_2$?

A basic result in elementary arithmetic states that
$$
\log_a n = \log_a b \cdot \log_b n.
$$
Indeed, on the one hand, $a^{\log_a n}$ by definition. On the other hand,
$$
a^{\log_a b \cdot \log_b n} = (a^{\log_a b})^{\log_b n} = b^{\log_b n} = n.
$$
Similarly,
$$
\log_b n = \log_b a \cdot \log_a n.
$$
This shows that every two logarithms only differ by a constant multiple. Since big O notation discounts constant factors, it doesn't matter which logarithm you use (unless it's in the exponent). For example, a function is $O(\log_a n)$ iff it is $O(\log_b n)$. For this reason we usually don't bother writing the basis of a logarithm in big O notation.


Is a "local" version of 3-SAT NP-hard? Below is my simplification of part of a larger research project on spatial Bayesian networks:

Say a variable is "$k$-local" in a string $C \in 3\text{-CNF}$ if there are fewer than $k$ clauses between the first and last clause in which it appears (where $k$ is a natural number).

Now consider the subset $(3,k)\text{-LSAT} \subseteq 3\text{-SAT}$ defined by the criterion that for any $C \in (3,k)\text{-LSAT}$, every variable in $C$ is $k$-local.  For what $k$ (if any) is $(3,k)\text{-LSAT}$ NP-hard?

Here is what I have considered so far:

(1)  Variations on the method of showing that $2\text{-SAT}$ is in P by rewriting each disjunction as an implication and examining directed paths on the directed graph of these implications (noted here and presented in detail on pp. 184-185 of Papadimitriou's Computational Complexity).  Unlike in $2\text{-SAT}$, there is branching of the directed paths in $(3,k)\text{-LSAT}$, but perhaps the number of directed paths is limited by the spatial constraints on the variables.  No success with this so far though.

(2)  A polynomial-time reduction of $3\text{-SAT}$ (or other known NP-complete problem) to $(3,k)\text{-LSAT}$.  For example, I've tried various schemes of introducing new variables.  However, bringing together the clauses that contain the original variable $x_k$ generally requires that I drag around "chains" of additional clauses containing the new variables and these interfere with the spatial constraints on the other variables.

Surely I'm not in new territory here.  Is there a known NP-hard problem that can be reduced to $(3,k)\text{-LSAT}$ or do the spatial constraints prevent the problem from being that difficult?

$(3,k)\text{-LSAT}$ is in P for all $k$. As you have indicated, locality is a big obstruction to NP-completeness.

Here is a polynomial algorithm.

Input: $\phi\in (3,k)\text{-LSAT}$, $\phi=c_1\wedge c_2\cdots \wedge c_m$, where $c_i$ is the $i$-th clause.
Output: true if $\phi$ becomes 1 under some assignment of all variables.
Procedure:

Construct set $B_i$, the variables that appear in at least one of $c_i, c_{i+1}, \cdots, c_{i+k}$, $1\le i\le m-k$.
Construct set $A_i=\{f: B_i\to\{0,1\} \mid c_i, c_{i+1}, \cdots, c_{i+k} \text{ become 1 under} f\}$.
Construct set $E=\cup_i\{(f, g)\mid f\in A_i, g\in A_{i+1}, f(x)=g(x)\text{ for all }x\in B_i\cap B_{i+1} \}$
Let $V=A_1\cup A_2\cdots\cup A_{m-k}$. Consider directed graph $G(V,E)$. For each vertex in $A_1$, start a depth-first search on $G$ to see if we can reach a vertex in $A_{m-k}$. If found, return true.
If we have reached here, return false.

The correctness of the algorithm above comes from the following claim.

Claim. $\phi$ is satisfiable $\Longleftrightarrow$ there is a path in $G$ from a vertex in $A_1$ to a vertex in $A_{m-k}$.
Proof.
"$\Longrightarrow$": Suppose $\phi$ becomes 1 under assignment $f$. Let $f_i$ be the restriction of $f$ to $B_i$. Then we have a path $f_1, \cdots, f_{m-k}$.
"$\Longleftarrow$": Suppose there is a path $f_1, \cdots, f_{m-k}$, where $f_1\in A_1$ and $f_{m-k}\in A_{m-k}$. Define assignment $f$ such that $f$ agrees with all $f_i$, i.e., $f(x)=f_i(x)$ if $x\in B_i$. We can verify that $f$ is well-defined. Since $c_\ell$ becomes 1 for some $f_j$ for all $\ell$, $\phi$ becomes 1 under $f$.

The number of vertices $|V|\le 2^{3(k+1)}(m-k)$. Hence the algorithm runs in polynomial time in term of $m$, the number of clauses and $n$, the number of total variables.


Relationship between complexity classes XP and W[1]? I am reading the introductory chapter in Parameterized Algorithms by Cygan et al. and I am having some problems with the distinction between complexity classes $\mathsf{W[1]}$ and $\mathsf{XP}$.

They explicitly define complexity class $\mathsf{XP}$ on p. 13 as the those problems that, given an instance $(x, k)$ of a parameterized problem, can be correctly decided by an algorithm in $O(f(k)\cdot|(x,k)|^{g(k)})$ time for functions $g, k$. I believe I understand this.

Complexity class $\mathsf{W[1]}$ is not explicitly defined. However, in the discussion of $k$-cliques on p. 9, they give an $O(n^k)$ algorithm for deciding whether a $k$-clique exists in a graph. As I understand it, therefore, the $k$-clique problem must be in $\mathsf{XP}$. However, the authors discuss it as a $\mathsf{W[1]}$ problem in a way that I find confusing.

My question, then, is twofold: (1) Am I right in thinking that $\mathsf{W[1]} \subseteq \mathsf{XP}$? I haven't been able to settle this by looking ahead in the book or by searching online. (2) Intuitively, what is the difference between the two classes? I have found defitions online, e.g. on Wikipedia, but not in language that I have found accessible. I would appreciate, therefore, if someone could provide more of an overview.

1) Yes, you are right: W[1] is a subset of XP. As you noticed, $k$-clique is in XP. The class W[1] is (usually by definition) the closure of that problem under FPT-reductions. XP is closed under these reductions. Hence the subsetship.

2) Citing another answer of mine, here is a bit of intuition about XP:

  The practical importance of XP is as a door to parameterized
  complexity analysis. Once a problem is recognized as belonging to XP
  it makes sense to investigate its exact parameterized complexity. If
  it does not even belong to XP, parameterized analysis doesn't make
  much sense. It can also be argued that in that case the
  parameterization is not meaningful.

In that sense, XP is the hardest intractable class of parameterized complexity theory. In an even fuzzier sense, on the very opposite side of the spectrum, W[1] is the easiest parameterized version of NP.

Gaining an intuition for W[1] is not exactly made easy (in the past I tried in this answer). As said, it is usually defined by completeness of a problem (like $k$-clique). Definitions using machine models exist (e.g. Chen, Flum, Grohe: Machine-based methods in parameterized complexity theory. TCS 339(2-3), 2005). But that does not imply they are suitable for entry-level understanding of the class. I suggest you just take W[1] as the sum of the facts you know about it.


Is it NP-complete to decide if chromatic and clique numbers agree? It is known that finding chromatic number $\chi(G)$ and clique number $\omega(G)$  are both NP-complete problems.

Is the problem

  Given graph $G$, is $\omega(G)=\chi(G)$?

NP-complete as well?

Side question: is there a name for such graphs?

Your problem is NP-complete. See for example this question on ResearchGate.

Your problem is in NP because to show that $\omega(G) = \chi(G)$ it is sufficient to exhibit a $k$-clique and a $k$-coloring, for some $k$.

Your problem is NP-hard by reduction from 3COL. Given a graph $G$, first check whether it contains a $K_4$, and if so output some trivial No instance (say a $5$-cycle). Otherwise, add a triangle to your graph. The original graph is 3-colorable iff the new one satisfies your condition.


With Memoization Are Time Complexity & Space Complexity Always the Same? I am studying Dynamic Programming using both iterative and recursive functions.  With recursion, the trick of using Memoization the cache results will often dramatically improve the time complexity of the problem.

When evaluating the space complexity of the problem, I keep seeing that time O() = space O().  This is because we will have to cache all the results, but once we cache them it is O(1) to retrieve

Examples of this are

Dice Sum Problem - count the number of ways N dice can roll a certain Sum.   Time  O(num dice * target Sum)    Space  O(num dice * target Sum)     https://stackoverflow.com/questions/19719439/calculate-the-number-of-ways-to-roll-a-certain-number
Coin Change Problem  -  count number of ways to make change for a certain money amount given a list of coins.   Time  O(num coin denominations * value to make change from)    Space - same as time    https://stackoverflow.com/questions/28910971/dynamic-programming-coin-change-problems

My question is,  with Memoization, will the space & time complexity always be the same ?   If not, why not ?

Edit - Clarification

This question is regarding the Space complexity of the recursive solution.  I have solved the iterative solution using smaller space complexity before, i.e. keeping only a single row in the matrix.   However for the recursive solution, I have never seen a recursive approach where items are deleted from the memoization table.   I suppose you could combine recursion + iteration to only keep a single row in the memoization, but I have not seen an example where you start at the pure end, and only keep limited space.

There are plenty examples for which you

need $\omega(1)$ time to compute each table entry or
do not need to keep all table entries.

An example for the former would be CYK; for the latter memoized Fibonacci and Bellman-Ford.


Definition of a size of type In B. Pierce's book "Types and Programming Languages", he talks about the size of types (see pictures below).

I searched the book for a definition but could not find one. I only found a definition for the size of terms, but not for the size of types.

Could someone please explain what Pierce means by the expression "$size(T_1)$" (marked by yellow in the image below) ?

A term in logic and rewriting theory is anything defined by a tree structure that's supposed to represent the syntax of something. It can be a term of a programming language, a type, a kind, a module, etc.

The size of a term is the size of the tree: it's 1 for a leaf, and $\mathit{size}(t) = \mathit{size}(t_1) + \dots + \mathit{size}(t_n)$ for a tree $t = C(t_1,\dots,t_n)$. The exact definition is often not terribly important: what matters is that the size of a term is strictly larger than the size of any term that appears as a part of it.

In programming language literature, some authors use term in this sense, and some authors use term for a term of the programming language itself as opposed to types, kinds, modules, etc. The former authors use expression for the narrow sense of a term of the programming language itself. Pierce uses term in the narrow sense.

The definition of the size follows the same principle no matter what syntactic category the term (in the broader sense) represents. Thus the size of a type is defined as $\mathit{size}(\mathsf{Nat}) = \mathit{size}(\mathsf{Bool}) = 1$,  $\mathit{size}(\mathsf{T}_1 \mathord\rightarrow \mathsf{T}_2) = 1 + \mathit{size}(\mathsf{T}_1) + \mathit{size}(\mathsf{T}_2)$, etc.

When there are multiple syntactic categories, whether terms of another category count depends on the definition chosen by the author. For example, the size of $\lambda x:T. M$ could be defined as $1 + \mathit{size}(M)$, or as $1 + \mathit{size}(T) + \mathit{size}(M)$, or even as $1 + \mathit{size}(x) + \mathit{size}(T) + \mathit{size}(M)$ depending on what is convenient for the matters at hand.


information theory, find entropy given Markov chain There is an information source on the information source alphabet $A = \{a, b, c\}$ represented by the state transition diagram below:

a) The random variable representing the $i$-th output from this information source is represented by $X_i$. It is known that the user is now in state $S_1$. In this state, let $H (X_i|s_1)$ denote the entropy when observing the next symbol $X_i$, find the value of $H (X_i|s_1)$, entropy of this information source, Calculate $H (X_i|X_{i-1}) $ and $H (X_i)$ respectively. Assume $i$ is quite large

How can I find $H(X_i|s_1)?$ I know that  $$H(X_i|s_1) = -\sum_{i,s_1} p\left(x_i, s_1\right)\cdot\log_b\!\left(p\left(x_i|s_1\right)\right) = -\sum_{i,j} p\left(x_i, s_1\right)\cdot\log_b\!\left(\frac{p\left(x_i, s_1\right)}{p\left(s_1\right)}\right)$$
but I don't know $p(s_1)$.

$$A=\begin{pmatrix}0.25 & 0.75 & 0\\0.5 & 0 & 0.5 \\0 & 0.7 & 0.3 \end{pmatrix}.$$

From matrix I can know that $p(s_1|s_1)=0.25$, etc.

But what is the probability of $s_1$?
And how can I calculate $H (X_i|X_{i-1})$?

You can make the golloowing set of equations, where s1 - the probability of being in s1 state:

s1 = 0.25s1 + 0.5s2
...
s1+s2+s3=1

I don't know the theory, but think that entropy of each state can be computed as follows:

e1 = - 0.25*log(0.25) - 0.75*log(0.75)

with overall entropy given already computed probability and entropy of each state

e = e1*s1 + e3*s3 + e3*s3

I don't know what H(...) means.


Does the order matter in the adjacency matrix? I have nodes a, b , c,d,N, and e in an adjacency matrix. If I follow the order as a,b,c,d,N,and,e , I get 100010(the question does not matter because I'm asking about the order) for b.But if I follow the order a,b,c,N,d,and e, I get 100100 which was done by my TA in the class. Does the order really matter? If so then is there a way to find order from the adjacency graphs?

Let $f$ be an isomorphism from graph $G$ to graph $G'$ which takes vertex $v_i$ to vertex $v_i'$.  Let $A$ and $A'$ be the adjacency matrix of $G$ and $G'$, respectively.  If the rows and columns of $A$ are in the order $v_1,\ldots,v_n$, and the rows and columns of $A'$ follow the same order $v_1', \ldots, v_n'$, then it can be seen that $A=A'$.

If $f$ is an isomorphism from $G$ to itself, then $f$ is called an automorphism of $G$.  Thus, $f$ is a permutation of $V(G)$ which maps edges to edges and nonedges to nonedges.  If we permute the rows of the adjacency matrix $A$ by $f$, and if we apply the same permutation to the columns of $A$, we get back the same matrix $A$. Equivalently, a permutation $f$ of $V(G)$ is an automorphism of $G$ if and only if the permutation matrix $P$ corresponding to $f$ satisfies the equation $P^{-1}AP=A$.  Recall that premultiplying a matrix $A$ effects row operations/permutations and postmultiplication effects column permutations.

So, graphs with the same structure (i.e. isomorphic graphs) have the same adjacency matrix (up to a permutation of the rows and columns - here, the same permutation must be applied to both the rows and the columns).  The graph invariants which we study are the same for isomorphic graphs and so the ordering of vertices you choose for the adjacency matrix shouldn't matter.


If a language is not Turing reducible to two languages, may it still be Turing reducible to their "union"? Consider a language $L$ that is undecidable relative to $L_1$ and is also undecidable relative to $L_2$. Suppose, however, that there is a "multi"-oracle Turing machine $M$ that can query both the $L_1$ oracle as well as the $L_2$ oracle such that $M$ decides $L$. In other words, $L$ requires both the $L_1$ and $L_2$ oracles to be decided, but neither one alone suffices to decide $L$. I would like to come up with such languages $L$, $L_1$, and $L_2$. At first, I was hoping that the oracles for the rejecting and the accepting problems for Turing machines together could be queried to decide the halting problem (but neither oracle alone could be used decide it), but that turns out to be a dead end.

Now I'm wondering if I can approach the problem by trying to come up with two languages such that neither is Turing-reducible to the other, but I'm struggling to find examples.

A classical theorem of Sacks states that if $L$ is not computable, then it is almost surely not computable relative to a random oracle. In other words, if $O$ is a random oracle, then the probability that $L$ is computable given $O$ is zero.

Now take your favorite uncomputable $L$, and choose $L_1,L_2$ at random among all languages such that $L = L_1 \Delta L_2$ (here $\Delta$ is symmetric difference). Individually, $L_1,L_2$ are random oracles, and so almost surely $L$ is not computable given just $L_1$ or just $L_2$. However, it is clearly computable given both.

Another solution is to take any two incomparable Turing degrees $L_1,L_2$ and $L = \{ 0x : x \in L_1 \} \cup \{ 1x : x \in L_2 \}$. The proof then follows practically by definition.


How to XOR two binary numbers having different lengths? If we have:

x = 1101 and y = 101

How to XORing these numbers?

There are multiple ways to interpret this XOR.

The most common one is that you XOR bit-wise, and that these strings represent numbers, so adding 0 to the left doesn't change their value.

Then $5 \equiv 101 \to 0101$  and then you XOR bit-wise.

x 1101
y 0101
------- XOR
  1000

which gives 8, if we are talking about unsigned numbers.
However, the above depends on my understanding of your system. Change the assumptions, change the results.


Bipartite graph question Assume you are given a bipartite graph $G = (U, V, E)$ and you are given an integer $n$. Assume also that for each $v \in V$, you are given two integers $v_{min}$ and $v_{max}$ (where $v_{min} \le v_{max}$).

The problem is to find a subset $U'$ of $U$ of size $n$ such that for each $v \in V$, the number of edges coming into $v$ from $U'$ is between $v_{min}$ and $v_{max}$.

Given a problem like this, can we determine efficiently whether there is a solution? And, if there is a solution, can we find one efficiently?

If we can't do so efficiently, is there an approximation algorithm?

Your problem is NP-hard, by reduction from set cover. Given an instance of set cover with universe $V$, sets $U$ and number $n$, draw an edge between a set and a point if the set contains the point. Let $v_\min = 1$ and $v_\max = |U|$. A subset $U'$ satisfies the $v_\min,v_\max$ constraints iff it is a set cover. So if there is a set cover $W$ of size $m \leq n$, you can complete it to some $U'$ of size $n$ by adding $n-m$ sets and get a solution to your problem. Conversely, any solution to your problem is a set cover of size $n$.

Set cover is also hard to approximate better than $\log n$ (under reasonable assumptions), and this carries over to your problem. Your problem could be much harder.


Detailed step of Dijkstra's algorithm performance analysis Reading the book of Dasgupta-Papadimitriou-Vazirani.pdf  about the performance of Dijkstra's algorithm on Page 118, we are given:

4.4.3 Running time
At the level of abstraction of Figure 4.8, Dijkstra's algorithm is structurally identical to breadth-first search. However, it is slower because the priority queue primitives are computationally more demanding than the constant-time eject's and inject's of BFS. Since makequeuetakes at most as long as $|V|$ insert operations, we get a total of $|V|$ deletemin and $|V| + |E|$ insert/decreasekey operations. The time needed for these varies by implementation; for instance, a binary heap gives an overall running time of $O((|V|+|E|)\log |V|)$.

I understand that it has $|V|$ insert and deletemin operations but can someone please explain why we have $|V|+|E|$ insert/decreasekey operations? First of of all, why does one algorithm have TWO kinds of insert operations? If they are the same kind, then where can we learn more about what decreasekey actually does?  The Wikipedia page doesn't seem to cover it much either (unless I missed or misunderstood it).

Since makequeue takes at most as long as $|V|$ insert operations, we get a total of $|V|$ deletemin and $|V | + |E|$ insert/decreasekey operations.
  First of of all, why one algorithm has TWO kinds of insert operations, if they are the same kind, then where can we learn more about what decreasekey actually does?

No, there is only one kind of insert operation. We got

$|V|$ deletemin operations.
a total of at most $|V|+|E|$ operations, where each operation is either an insert operation or a decreasekey operation. We count these two kinds of operations together because it takes the same asymptotic time to do either one of them, $O(\log |V|)$.  More specifically. we have

|V| insert operations during makequeue.
at most |E| decreasekey operations as each edge may or may not lead to a decreasekey operation.


Where is the reorder buffer (ROB)? I just wonder where the ROB is in.
Is ROB in the memory or cache or where??

Somewhere which is not part of the user accessible memory (i.e. not in the main memory nor in the cache -- that would be too slow, one of the main use of OOO is to hide part of the latency of main memory and low level caches).  Probably in register files inside the processor or possibly in the same kind of memory cells used for L1 caches (but not in the L1 caches).  Modern processors have lot of internal state which is not directly accessible.


Why the need for TSP solvers when there are SAT solvers? Concorde TSP is a solver for TSP. SAT solvers are solvers for boolean satisfiability.  TSP and SAT are NP-complete.

Hence, why spent the time to develop Concorde TSP when there is an abundance of SAT solvers in the market back then?

TL;DR: polynomial reduction increases the size of a problem; using a specific solver allows you to exploit the structure of a problem.

When you reduce one NP-complete problem to another one, the size of the problem usually grows polynomially. For example, when you reduce a HAMPATH on a graph with $n$ nodes to SAT, the resulting formula has size of $\Theta(n^3)$ (I don't remember about the constant that arises in a straight-forward TSP->SAT reduction). If you use the Cook-Levin theorem, then the growth might be even bigger because a Turing machine might have really huge (polynomyal) overhead. NP-completeness is mostly a theoretical idea. So is a polynomial-time reduction. Many theoretical papers only state that there is a reduction, saying nothing about how practical it is.

Let's informally assume that TSP is as hard as SAT. It means that it takes similar computational resources to solve TSP on $n$ nodes and SAT with $n$ clauses if you use state-of-the-art solvers for each problem. Now it is easy to see that writing a separate solver is more practical than reducing the problem to SAT and using some existing SAT solver. It is all about polynomial overhead.

There is one more thing to notice: exact problems are usually simpler than broad ones. When you reduce TSP to SAT, the SAT solver knows nothing about the underlying structure of the formula. And special solvers for TSP, of course, deal with the fact that the input is a graph, the problem is to find a shortest Hamiltonian path, so on.

Although for some problems reduction to SAT can be reasonable, mostly if the problem is not well-studied (and no cool solvers exist) and when reduction doesn't increase the problem size a lot. SAT solvers are still very strong for many practical purposes.


Better word to describe JavaScript "algorithm"? For my undergraduate senior project, a professor asked me and my partner to design an algorithm to determine true resolution in the browser, unaffected by zooming, multiple screens, viewport size, etc. (tl;dr our implementation was okay, it usually did the job correctly.)

It's super pedantic, but I've been thinking about the terminology of calling it an "algorithm". It really doesn't seem like an algorithm, because it's very dependent on JavaScript and the state of the browser at a given time. Particularly, our script has a lot of if-statements to determine what what variables and data to work with depending on the browser and configuration. I certainly don't think I could write it out in a language-agnostic pseudocode.

Is there a better word to describe what we wrote? Does it count as an "algorithm" per say? If I had to think of alternate words, they'd be:

implementation (but of what, just our general idea/design?)
script/program

Are there better words that are more general than simply script or program?

You can certainly describe the inner workings of your project as an algorithm. It takes an input (whatever information it obtains from the browser) and produces an output, as a result of some scheme of calculations. Perhaps it needs to read inputs during the course of its calculations (depending on the first inputs, it might make different queries of the browser), so it might be some sort of interactive or adaptive algorithm.


Aho-Corasick for a set of patterns I have completely understood how Aho Corasick works for finding one pattern in a text, and how to construct the automaton for a certain pattern.  I have studied the CLRS book and watched this video. But the problem is that I cannot find any material on how to build an automaton for more than just one pattern. For example given the following words, how can I build an automaton with the required transition function?

P = {vine, vincent, cent, center}

Are there any topics on StackOverflow or any YouTube videos that teach this step-by-step?

At a high level, the process for building an Aho-Corasick automaton is:

Build a trie for the pattern strings.
Add suffix links (also called failure links) from each node to its longest proper suffix that's still in the trie.
Add output links to any patterns that are reachable from each node via suffix links.

Build the trie

Create a root node, then go through each pattern character by character. Starting from the root, try and follow an edge for the current character. If one does not exist, create an edge to a new node for that character.

Using P = {vine, vincent, cent, center}, say we start with the pattern 'vine'. When we go and add the next pattern 'vincent', we first follow the existing edges for v-i-n, and then add in new edges for c-e-n-t:

(I'm marking the ends of each pattern with a double circle). Continue this process until the whole trie is built:

Add suffix links

Now to add the suffix links, we perform a breadth first search of the tree, adding an edge for each node except the root. If a node is one hop away from the root, its suffix link goes to the root. Adding suffix links in blue, the suffix links for the nodes corresponding to 'v' and 'c' are:

Otherwise, the node corresponds to some string wx, where x is the final character. For example, if we look at the string 'vi', w='v' and x='i'. Now follow w's suffix link and let the node you arrive at be called n.

If this node has an edge for x, then set wx's suffix link to point at nx. Else if n is the root node, set wx's suffix link to point at n. Otherwise, follow n's suffix link, let this node be the new n, and repeat. In this case, the node for n does not have an edge for 'i'. Here's another example adding in the suffix link for 'vinc', where w='vin' and x='c':

Add output links

As you are performing the BFS to fill in the suffix links, you can also fill in the output links (all initially null). Let the current node be n. Follow n's suffix link and let the node you arrive at be called m.

If m corresponds to one of the pattern strings (is marked with a double circle), set n's output link to point at m. Else set n's output link to point at the same node as m's output link, or null if m has no output link. In our example there is only one output link, shown here in green:


Why is there a precision loss for floating-point numbers? It could be a silly question, yet I'm not able to understand.
In modern day, computers, we have integers with million digits length. Even in my ordinary 2GB laptop, I can calculate values of numbers up to thousand digits long, but the value of a floating-point calculation is often limited to 15 digits or worse, like 0.1 + 0.2 is not equal to 0.3 (in Python, its 0.30000000000000004).

Why do we have such loss of precision in floating-point calculation? Is it due to the limit of binary system to express floating-point numbers?

Many people can afford to buy a computer with a powerful processor and say 128GB of RAM. Maybe the same cost as a small car.

That's enough to store one number with 300 billion digits. It's enough to store 300,000 numbers of a million digits. But it is also enough to store 16 billion double precision floating point numbers. There are problems where 300,000 numbers are nothing.

The number of operations is another matter. That computer can probably do 50 billion floating-point operations per second. It cannot do anywhere near that number of operations with one million digit numbers. Going down from 50 billion operations to 10,000 operations with one million digit numbers, that hurts.

Higher precision is almost never needed. And if it is not needed, it is an absolute waste of speed and memory. And remember that with a million digits precision, 0.1 + 0.2 still doesn't equal 0.3, but it equals 0.3 (one million zeroes) 4.


Are all context-sensitive languages decidable? I was going through the Wikipedia definition of context-sensitive language and I found this:

  Each category of languages is a proper subset of the category directly above it. Any automaton and any grammar in each category has an equivalent automaton or grammar in the category directly above it.

I could see that linear-bounded automaton is directly below decider in the article's ordering. If this is the case, then that means every computation on a LBA will halt at some point (since every LBA would be a decider). But I feel that there may be some computation which can run on a LBA at the same time never to halt. For example we can write a computation on LBA which would

read the first symbol on the tape and move right;
read the next symbol and move back left.

This (useless) computation (which is obviously a LB computation) would run indefinitely oscillating left and right and never halt and hence cannot be a decider. Where am I thinking wrong?

First, all context-sensitive languages are decidable, since they can be accepted by a LBA (as you said), and a Turing machine is more powerful than a LBA.

However, you were asking about something else. Can there be LBA that cycles? The answer is yes. You gave an example. However, you can modify every LBA $M$ to a Turing machine $M'$ that accepts the same language but never cycles. To see this, observe, that you can simulate $M$ on $M'$ and keep track of all configurations the LBA has attained so far. If there is one configuration that shows up twice, you detected a cycle. In this case you stop rejecting. The important thing here is that the LBA uses on linear space, and hence the number of its configurations is bounded.


Array-like immutable (persistent) data structure implementation with fast indexing, append, prepend, iteration I'm looking for a persistent data structure similar to array (but immutable), allowing for fast indexing, append, prepend, and iteration (good locality) operations.

Clojure provides persistent Vector, but it's only for fast append. Scala's Vector has effectively constant-time append and prepend, but I can't get how it's implemented, since it's based on same data structure (bit-mapped vector trie) as Clojure vector, and, as I understand, bit-mapped vector trie can't have fast prepend without some tricks.

I'm interested not in ready to use implementation but in a description of how to implement such a data structure myself.

The obvious candidate is a persistent balanced binary tree.  All the operations you listed can be performed in $O(1)$ or $O(\lg n)$ time, using path copying.  For more details on how to achieve this runtime, see Chris Okasaki's book referenced below or my answer here.

Of course, as an variant, each leaf of such a tree could itself contain an immutable array (a sequence of consecutive values).  This makes updating a value less efficient, but it might work well for your situation, if you never intend to modify an existing value, just append and prepend.  In this way, your vector is represented as a sequence of immutable sequences, represented as a balanced binary tree with immutable arrays in the leaves.  This allows for fast indexing (logarithmic in the number of leaves), fast append and prepend, and fast iteration.  The worst-case asymptotic complexity is no better, but the performance in practice might be significantly better.

The standard reference is Chris Okasaki's 1998 book "Purely functional data structures".
See also

What classes of data structures can be made persistent?
What's new in purely functional data structures since Okasaki?
What are the outstanding questions in purely functional data structures?
Ten Years of Purely Functional Data Structures


Are there competitions for integer programming? Are there competitions for integer programming like there are for SAT and MAXSAT?

There are competitions for constraint satisfaction solvers. Some problems there can be readily translated to IP solvers as well. See e.g., MiniZinc challenge which has taken place yearly since 2008 or the XCSP competition.


Construct a CFG for $L = \{ w \in \{0,1\}^*\text{ } |\text{ } w = w^R \text{ and } |w| \text{ is even}\}$ I need to construct a CFG for the following language$$L = \{ w \in \{0,1\}^*\text{ } |\text{ } w = w^R \text{ and } |w| \text{ is even}\}$$
I know that the two middle position should always be the same. E.g. $11,00,0\underline{11}0,0\underline{00}0,\dots$ Each position on the opposite sides of the middle points should also be the same.
So these are the production rules of the CFG I came up with
$$
S\rightarrow00$$
$$S\rightarrow11$$
$$S\rightarrow ASA$$
$$A\rightarrow1$$
$$A\rightarrow0$$
$$A\rightarrow \epsilon$$
Is this solution correct?

As HendrikJan stated, we can for example obtain the following languages with above CFG
$$01, 0001,\dots$$
which do not meet the required conditions.
Instead, we need to make sure that the ends are always the same. We can do that by the following production rules.
$$
S\rightarrow 0S0$$
$$S\rightarrow 1S1$$
$$S\rightarrow \epsilon$$


Algorithm for automatic/optimal database joins? I'm curious if there is existing literature or well known algorithms out there for a problem I am working on.

Given a normalized relational database with valid foreign key constraints and a list of fields across different tables, what is a good or at least consistent algorithm for determining the (inner) joins required to provide that information? Ideally using the minimal number of joins possible.

Given a graph and a set of nodes that I want. How do I find a subgraph which is connected that contains all those nodes.

My initial thoughts:

I see the table as a directed graph with tables as vertices and foreign keys as edges between them. For the purposes of the algorithm treating the graph as undirected seems like it might be useful.

Shortest path between tables seemed obvious but as soon as more than 2 tables are requested then I would be finding the shortest path that visits all nodes (traveling salesman territory ACK!). My second thought is the minimum spanning tree of the subgraph. However, how would I choose the subgraph?

Edit:
After thinking about it more I think this could work. Run Kruskal's minimum spanning tree on the graph beginning from a desired node. Assign weights to the edges like so weight=1 if (a,b) is between two desired nodes. Weight = n^2, where n is the number of nodes, if (a,b) is between a desired node and a undesired. Weight = n^4 if between two undesired nodes. The weights are arbitrary. I just thought it would be better to use values that couldn't overlap.

Once all desired nodes are added to the MST, exit Kruskal's. Then from the root (starting node) walk down to each leaf. If a leaf is not desired node, then delete it. Repeat until no nodes are deleted.

This is the minimum Steiner tree problem for general graphs.  It is known to be NP-hard.  Here you have the special case where every edge has weight 1, but that special case is still NP-hard.

However, there are approximation algorithms, which you could use to get somewhat close to the optimum.  Alternatively, if you want the exact optimal solution and your graph is not too large, you could express your problem as an instance of integer linear programming (ILP) and try using an off-the-shelf ILP solver, though the worst-case running time will still be exponential.


Is this language in P? L={ | M is a DFA, |w| is even for all w in L(M)}

Meaning we are looking for a Turing Machine or any algorithm that receives a description of a DFA and decides if all the words this DFA accepts are even in there length(length of 0, 2, 4, 6 ..). DFA stands for Deterministic Finite Automata. My proposal is this, check if all the accepting states stand in an odd positition, meaning you can get to them after an odd number of steps.If so accept M otherwise reject.For example 0011 has even length, 0 takes you to state2 0 state3 1 state4 1 state5. because when you start you are already at state 1(Qstart).

My question: is my solution solid, is it right? Does it run in Polynomial time?
I think running time is: o(n^2)

Using the product construction, given $M$ you can construct (in linear time) a DFA for the language $L'(M) := L(M) \cap \Sigma(\Sigma\Sigma)^*$. Using DFS/BFS, you can check whether $L'(M)$ is empty or not (you check whether some accepting state is reachable from the initial state) – $L'(M)$ is empty iff $M \in L$. The entire algorithm runs in linear time.


Concave Polygon Intersection - Algorithm I'm trying to develop an Algorithm for Polygon Intersection. Where each polygon is an array of Points, where each Point has X and Y properties.
Algorithm limitations:
- Algorithm input: 2 Polygons.
- Algorithm output: Intersection Polygon.
- Polygons may be convex or concave (angle between 2 neighbor edges my be more than 180).
- Polygons will not have any holes and will not be self intersection polygons.

I managed to develop this algorithm this far (given 2 polygons A and B):

For each vertex in PolygonA:
1.1 If vertex is inside PolygonB then Add this vertex to groupA.
For each vertex in PolygonB:
2.1 If vertex is inside PolygonA then Add this vertex to groupB.
For each edge {edgeA} in PolygonA:
3.1 For each edge {edgeB} in PolygonB:
3.1.1 If edgeA and edgeB are intersect (in the edgeA and edgeB segment area) then add there intersection point to groupI.
marge(groupA, groupB, groupI); // I don't know how to implement this

In debug I see that the Intersection area is built from vertexes combined groupA, groupB and groupI. But I don't know how should I merged them together - how to order/sort them???

I have try to sort the clockwise around the center point of the new intersection polygon - but this will only work for convex polygons not for concave.

In this example:
- The Blue Points are vertexes of PolygonA inside PolygonB (groupA)
- The Red Points are vertexes of PolygonB inside PolygonA (groupB)
- The Yellow Points are intersect vertexes of PolygonA with PolygonB (groupI)

First, order the $Blue \cup Yellow$ points according to a clockwise visit of A, and similarly, order the $Red \cup Yellow$ points according to a clockwise visit of B.

Now start at a blue point (if there is one) and follow A clockwise until you are at a yellow point. Then follow B clockwise until you are at a yellow point again; then follow A clockwise, and so on, switching from following one polygon to the other every time you encounter a yellow point. Continue until you are back at the starting point. See Weiler-Atherton clipping algorithm and the references there.

If there are no blue points, start instead from a red point and follow B initially. If there are only yellow points (with no blue nor red), start from any yellow point and follow the polygon that makes you stay inside the other polygon.

Note that in general the intersection of non-convex polygons may consist of multiple disconnected regions. The procedure above will only give you one of these regions.


How to prove the following: Every set is Turing reducible to itself Question:
Prove the following:  Every set is Turing reducible to itself.

If anyone can provide a solution that would be great, I've just been introduced to computation theory so be as descriptive as you like for my sake if not strictly for the answer. Thanks!

Informally, $A$ is Turing reducible to $B$ if you can figure out what $A$ is by asking questions to $B$.

A bit more formally, $A$ is Turing reducible to $B$ if there's some algorithm you can use to figure out whether a number is in $A$ by asking questions about whether or not various numbers are in $B$. For example, an instance of a Turing reduction between $A$ and $B$ might look like the following:

I want to figure out whether $3$ is in $A$.
I ask $B$, "Is $17$ in you?"
$B$ says yes.
I now say, "Okay, based on that answer I now want to ask: is $42$ in you?"
$B$ says no.
I say, "Great! Now I know that $3$ is in $A$.

So, you're trying to do the following: given some arbitrary set $A$ and an arbitrary number $n$, find a way to figure out whether $n$ is in $A$ by "querying" $A$. (HINT: don't overthink this ...)

Incidentally, Turing reductions don't have to be efficient, or non-stupid, or anything else nice; they just have to work. For example, in the problem you're trying to solve, there is a "best" Turing reduction; but we could also modify that reduction to pointlessly ask "Is $17$ in $A$?" at the end for absolutely no reason, and simply ignore that extra information.


Is it possible to prove that this algorithm is big Omega $n^2logn$ time complexity? Considering the following recursive algorithm:
$ T(n)= T(\frac{n}{2})+c_1(\frac {n}{2})^2+c_2n$.
I was able to prove that this algorithm is $O(n^2 logn)$
I was trying to understand whether it is a tight bound or not, yet I was unable to prove that $ T(n)\in \Omega(n^2logn)$
Is it possible or maybe the algorithm's lower bound is $n^2$ ?
Any assistance would help a lot as I am trying to crack this for a while now.

Your recurrence can be written as:
$
T(n) = T(n/2) + f(n)
$, where $f(n) \in \Theta(n^2)$.
Then, by case 3 of the Master theorem, you have $T(n)=\Theta(n^2)$. This means that you won't be able to prove a lower bound of $\Omega(n^2 \log n)$.


Flawed argument in the proof of function extensionality in cubical type theory? I am reading the lectures about cubical type theory in this github repo. In lecture 1 the author defines function extensionality the following way:

funExt (A B : U) (f g : A -> B)
       (p : (x : A) -> Path B (f x) (g x)) :
       Path (A -> B) f g = <i> \(a : A) -> (p a) @ i

and writes

To see that this makes sense compute the end-points of the path:

  (<i> \(a : A) -> (p a) @ i) @ 0 = \(a : A) -> (p a) @ 0
                                  = \(a : A) -> f a
                                  = f

I don't follow. Specifically, when we replace (p a) @ 0 with f a in my mind we use the following fact: \(a : A) -> (p a) @ 0 = f a to rewrite (let's give names to the left and right side) fpa = \(a : A) -> (p a) @ 0 into fa = \(a : A) -> f a. But isn't this by itself using function extensionality with f = fpa, g = fa?

If I am not mistaken, this argument is circular. Can anyone clarify?

The expression:

\(a : A) -> (p a) @ 0

parses as:

\(a : A) -> ((p a) @ 0)

So this is applying p a : Path B (f a) (g a) to the 0 point. This reduces to f a, because it is the beginning point of the path. It's essentially doing the same thing as the earlier step, which beta reduced the (<i> ...) @ 0 to (...)[i := 0], except p a looks abstract to us, but that doesn't matter, because we know what it reduces to when applied to 0 (or 1) based only on its type.

So, it's not using function extensionality to prove extensionality. What it's doing is taking advantage of the fact that Path types are similar to function types, and that the two Path types in funExt are 'just' functions with different argument order (so it flips them).


Iterate over each cell of a grid through whose interior a given line segment passes Let $a,b>0$ and suppose we have divided the domain $\Lambda:=[0,a]\times[0,b]$ into a grid of width $n_x$ and height $h_y$.

We enumerate the grid from bottom to top and left to right. Given $(x_0,y_0),(x,y)\in\Lambda$, I want to iterate over each grid cell through whose interior the line segment connecting $(x_0,y_0)$ and $(x,y)$ passes.

Suppose we number the first cell by $(0, 0)$ and the last cell by $(n_x-1,n_y-1)$. How can we find an efficient algorithm, which iterates over the desired cells?

Use a line drawing algorithm, such as Bresenham's.