Algorithm to distribute elements evenly among a population Algorithm to distribute elements evenly among a population

In the software I am doing I have three different categories:

Maize:
    1- Variety A
    2- Variety B
    3- Variety C
    4- Variety D
    5- Variety E
    6- Variety F
    7- Variety G
Fertilizer:
    1- Type A
    2- Type B
    3- Type C
    4- Type D
Management
    1- Form A
    2- Form B
    3- Form C
    4- Form D
    5- Form E

With this categories I need to produce combinations of Maize+Fertilizer+Management. So I get 140 combinations. I need to distribute the 140 combinations into 200 recipients randomly (some will repeat of course) but balanced (to avoid to many of one type of combination)

I saw this post but I might have a different case.

Is there an algorithm to do this?

Traditionally, this kind of problem is described as a fractional factorial design problem. However, your problem also can be elegantly solved via a probabilistic / statistical method that exploits the power of low discrepancy sequences.

For additional context, this method can be applied to very similar questions as yours, such as:

Random but even distribution of AB vs BA
How to shuffle coloured balls

Low Discrepancy Sequences

Low discrepancy sequences, (often described as quasirandom sequences) are numbers that generally appear random, but have an underlying structure to them that makes them more evenly distributed and so have less 'gaps' and 'clumping'.

There are many ways to construct low discrepancy sequences, and they can be generalised to arbitrarily high dimensions, too. For example, below is a picture of the first 100 terms of five different low discrepancy sequences in two dimensional and how they compare to simple random sampling. Note that all of them are substantially more evenly distributed than the conventional uniform random sampling.

Further details can be found at the Wikipedia article: "Halton Sequence".

Equidistributed Allocation

A post I wrote, "The unreasonable effectiveness of quasirandom sequences" , describes how to easily create an efficient extensible $d$-dimensional low discrepancy sequences. (For this particular case, we need a $d=3$ dimensional sequence.)

Define an $n$ x $3$ dimensional array, where each of the $n=200$ rows represents a different trial, and each of the components of each 3-vector defines which type of variety to use for each of the $d=3$ categories.

For $d=3$, there is one magical number involved which is $ \phi_3 = 1.2207440846... $ (see the article if you are interested in what is so special about this number).

Now simply define for all integer $n$, a 3-dimensional vector $\pmb{t}_n$ such that:
$$ \mathbf{t}_n = \pmb{s} + n \pmb{\alpha}  \; (\textrm{mod} \; 1),  \quad n=1,2,3,... $$
$$ \textrm{where} \quad \pmb{\alpha} =(\frac{1}{\phi_3}, \frac{1}{\phi_3^2},\frac{1}{\phi_3^3}).$$

In nearly all instances, the choice of initial seed $\pmb{s} $ does not change the key characteristics, and so for reasons of obvious simplicity, $\pmb{s} =\pmb{0}$ is the usual choice. (I have included it in this definition, because if you wish to create another sampling distribution, all you need to do is re-run the code but with a different starting seed!)

Specifically for $d=3$; with $\phi_3 = 1.2207440846$ and $\pmb{s}= (0.5,0.5,0.5) $,  the first 5 terms of this sequence are:

(0.319173, 0.171044, 0.0497005)
(0.138345, 0.842087, 0.599401)
(0.957518, 0.513131, 0.149101)
(0.77669, 0.184174, 0.698802)
(0.595863, 0.855218, 0.248502)
...

Now consider the first component $x_n$ of each vector $t_n$, to represent the first category ("Maize"). (ie  $x_1 = 0.319173$). If

$ 0 \leq x < 1/7$, then select Maize, option A
$ 1/7 \leq x < 2/7$, then select Maize, option B
$ 2/7 \leq x < 3/7$, then select Maize, option C
...
$  6/7 \leq x < 1$, then select Maize, option G

Similarly, consider the second component $y_n$ of each vector $t_n$, to represent the second category ("Fertilizer"). If

$ 0 \leq x < 1/4$, then select Fertilizer, option A
$ 1/4 \leq x < 2/4$, then select Fertilizer, option B
$ 2/4 \leq x < 3/4$, then select Fertilizer, option C
$  3/4 \leq x < 1$, then select Fertilizer, option G

Summary

The beautiful result of this low discrepancy method is that, for any $n$, the number of varieties allocated in each category will not differ by more than 1.

Said another way, the number of samples for every variety and every category, will never be more than 1 away to the ideal equal allocation method.

Code

Python code to create the low discrepancy sequences is

# Use Newton-Rhapson-Method
def gamma(d):
    x=1.0000
    for i in range(20):
        x = x-(pow(x,d+1)-x-1)/((d+1)*pow(x,d)-1)
    return x

d=3
n=200

g = gamma(d)
alpha = np.zeros(d)
s=0.5  # initial seed.

for j in range(d):
    alpha[j] = pow(1/g,j+1) %1
z = np.zeros((n, d))
for i in range(n):
    z = (s + alpha*(i+1)) %1

print(s)
print(z)

Hope that helps!


How does "δ:Q×Σ→Q" read in the definition of a DFA (deterministic finite acceptor)? How do you say $\delta\colon Q \times \Sigma \to Q$ in English? Describing what $\times$" and $\to$ mean would also help.

$\delta$ is a function which takes a current state and a letter from the alphabet as arguments and produces next state.

It might be easier to understand when you realize that it is just a function that takes a pair, for instance $(q_0, a)$ where $q_0 \in Q$ is a state and $a \in \Sigma$ is a letter in the alphabet, and $\delta(q_0, a) = q_1$ means that if in state $q_0$ you read an 'a', proceed to state $q_1$.

It is the definition of a transition function which is used for example in Turing machines.

$\times$ means Cartesian product and $\to$ means "produces" or "maps to".


Why does Locality Sensitive Hashing use multiple sets of hash tables? How does it guarantee similarity? With locality sensitive hashing (specifically multi-probe hashing http://www.cs.princeton.edu/cass/papers/mplsh_vldb07.pdf) how are the guarantee of similarity returns made? Why are there multiple tables involved in the hash indexing? Wouldn't that make it LESS probable that an item hashed to a bucket is similar to another rather than the reverse?

LSH indexing first concatenates $k$ simple hash functions $h$ to produce a function $g$. Note that $g$ is a regular LSH function, only with slightly different parameters. In particular, probabilities of collision decrease for both near and far objects. The new probabilities are $p'=p^k$.

Then they take $L$ such functions $g$ and produce $L$ hash tables. Then we search through all the hash tables, one by one. This effectively increases the probability of collision. The new probabilities are $p''=1-(1-p^k)^L$. Note that this function has a sigmoid shape.

It may seem weird to first reduce $p$ and then increase it. However, the parameters $k, L$ are useful knobs for controlling the behavior of the algorithm. You could certainly run with $k=L=1$, but larger values may perform better.


Lexicographically Smallest String Problem Statement: Given a string/pattern only consisting of '<' and '>' symbol, find the lexicographically smallest string that satisfies the pattern(made up of only lowercase english alphabets). Some examples are given below for better understanding.
Examples:

Input(String) - '>>'
Output(String) - 'cba' (because c > b > a)
Input(String) - '>'
Output(String) - 'ba' (because b > a)
Input(String) - '><>'
Output(String) - 'badc' (because b > a < d > c)

Constraints: String/Pattern length is always <= 25 and in the output string, no alphabet should be repeated.
I am unable to come up with any approach which has a lesser complexity than O(N!)(which would surely never pass the time limits), N being the given string/pattern's length. Any help is appreciated.
P.S. - This problem was asked in a HackerEarth hiring contest, and no, the contest is no longer live.

Let us denote the solution for a string $w$ and a set $A$ of remaining letters by $s(w,A)$. Also let $A = a_1 < \cdots < a_n$. If $w$ equals $>^{n-1}$ then clearly the solution is $a_n a_{n-1} \ldots a_1$. If $w$ starts with a run of $\ell$ many $>$'s (possibly $\ell=0$), then the first $\ell+1$ letters of any solution must be $a_{\ell+1} \ldots a_1$ or lexicographically larger. Conversely, there always is such a solution – we can construct one recursively. This shows that
$$
 s(>^\ell<x,\{a_1,\ldots,a_n\})=a_{\ell+1}\ldots a_1 s(x,\{a_{\ell+2},\ldots,a_n\}), \quad s(>^{n-1},\{a_1,\ldots,a_n\}) = a_n \ldots a_1.
$$
Since this greedy construction always "eats away" a prefix of the alphabet, it can easily be implemented in linear time.


Lowest common ancestor similar algorithm for a graph I'm working on a type system and hit upon a problem that seems similar to lowest common ancestor. Given two types, I need to find the smallest sequence of conversions which will result in the same target type. If I had a simple type tree I know how to get the result, but unfortunately I have a slightly more complex graph structure.

That graph has a few key points. It is unidirectional and no loops are ever formed. Due to an unlimited number of types however it cannot be produced statically. The distance of a path is generally quite low. It "feels" more like a tree with a bunch of shortcut edges.

Initially I looked at lowest common ancestor, but it is mainly described as a tree algorithm. I've not yet given up hope that I could adapt it. The other possibility would be a more generic path-finding algorithm.

I'm hoping somebody has seen this problem before, or a similar one, and can give me some references on how to further approach it. It seems familiar enough that I assume something must exist and I'm just searching for the wrong terms/names.

Here's my attempt to describe this more formally.

Let there be a graph $G = \{ V \}$ such that each vertex has a set of outgoing edges $V = \{ E=V_x \}$. Note, as the graph is dynamic, possibly infinite, there is no way to construct the form $G = \{V, E=(V_x,V_y)\}$ for the entire graph.

A path is formed from a vertex by following any of the available edges from that node. $Pnm_x = V_n, ..., V_m$. The length of this path is equal to the number of vertices in the sequence. There is no cycle possible. The set of all paths between two nodes is expressed as $Pnm = \{ V_n, ..., V_m \}$.

Note that $Pnm$ can be determined to be empty in a finite number of steps. Enumerating the entire $Pnm$ set is not practically possible.

The problem is finding the shortest path from two vertices to a third vertex. That is, given $V_a, V_b$, find $V_c$ such that paths $Pac_x$ and $Pbc_y$ exist and $length(Pac_x) + length(Pbc_y)$ is minimal.

If the lowest common ancestor of two types always exists and is unique, then your structure is a join-semilattice. Computing the lowest common ancestor is possible, but the worst case runtime complexity is not as good as I would have expected intuitively. I asked a related question some time ago, but was too lazy to write an answer after I found the relevant solution in the "literature". I just wrote the answer now, and it starts as follows:

This blogpost on lattice theory has a useful reference section, which contains among others "Lattice Theory with Applications" by Vijay K. Garg.
Chapter 2 "Representing Posets" describes some data structures for representing posets, and discusses how to compute join(x,y) using such a data structure.

Here is the relevant part from chapter 2.3.1:

We now give an $O(n + |e_\prec|)$ algorithm to compute the join of two elements $x$ and $y$. The algorithm returns $null$ if the join does not exist. We first assume that we are using the cover relation. To compute $join(x,y)$, we proceed as follows:

Step 0: Color all nodes white.
Step 1: Color all nodes reachable from $x$ as grey. This can be done by a BFS or a DFS starting from node $x$.
Step 2: Do a BFS/DFS from node $y$. Color all grey nodes reached as black.
Step 3: We now determine for each black node $z$, the number of black nodes that point to $z$. Call this number $inBlack[z]$ for any node $z$. This step can be performed in $O(n + |e_\prec|)$ by going through the adjacency lists of all black nodes and maintaining cumulative counts for $inBlack$ array.
Step 4: We count the number of black nodes $z$ with $inBlack[z]$ equal to $0$. If there is exactly one node, we return that node as the answer. Otherwise, we return $null$.


Identifying set of longest time periods excluding overlapping time ranages Suppose I have set of time records as follows

08:00 - 12:00
10:00 - 12:00
08:00 - 13:00
13:00 - 19:00
12:00 - 17:00

Now I want to select set of time records that are not overlapping and has the largest sum.

 08:00 - 13:00 + 13:00 - 19:00 = 12hours

My current approach is

Sort the records by start time
Select the first record and compare with each record and get the sum and store sum and the index of records.
Then select the second item repeat the process.
Loop through sum array and find the largest sum and indexes of records

Is there any better approach I can follow ? Is this a problem related to Dynamic programming ?

Thanks.

Your problem is known as weighted interval scheduling, and can be solved using dynamic programming. It's a nice exercise. You can find the solution in these lecture notes as well as in many other places.


SGD statistical guarantee I have a question regard online learning with SGD. Is there a way to give a statistical guarantee that the value obtained after $n$ samples deviates at most $\epsilon$ from the real value?
Thank you guys.

No, there are no guarantees.  SGD finds a local optimum but not a global optimum, and the solution it finds can be arbitrarily bad, if you have an unfriendly objective function.
The only results I've seen that provide guarantees start from strong assumptions about the objective function (e.g., convexity).


Prove that the Language is Recognizable I got stuck on this question while studying for final exam.

I thought about reducing L' to L to prove that L' is recognizable since L is recognizable. I am not 100% sure if that is correct.

sPaz, your answer in the comment is on the right track.

I'll give you some more hints.

Since $L$ is RE, as you said, we have a TM that accepts it. Let's call it $R$.
Now, we can run $M_i$ on $x$ for any $M_i$ that is being accepted by $R$.
The question is, what happens if $M_i$ is not accepted by $R$ (and in fact, $R$ goes into a loop)? Also, what happens if $M_1$ is accepted by $R$, but $M_1$ goes on an infinite loop on input $x$?

The standard technique of "running in parallel" (dovetailing) should help you to complete your proof. In more details:

   We have a counter $i$. We run $i$ steps of $R$ on any machine $M_j$ such that $\langle M_j \rangle < i$. We keep a list of all the machines that were accepted by $R$. For each such machine, we run $i$ steps of that machine on $x$. If any of them accepts, we accept. Otherwise, we set $i\leftarrow i+1$ and continue.


How to formulate a computational problem rigorously? I often interact with people who want to ask for an algorithm for a computational problem (or its complexity), but they don't express it in a rigorous way for us (computer scientists) to understand.
Referring them to books like CLRS is not helpful because the examples there usually have a quite straightforward way of stating rigorously, e.g. given the adjacency list of a graph and two vertices in it compute the shortest path between those vertices.

Is there any good book (or some other resource) where a person with minimal knowledge of CS can learn how one should formulate and state computational problems in a rigorous way that is understandable to computer scientists?

Preferably the book should have many examples of how to formulate computational problems rigorously from various domain and real world examples.

Clarification
To make the question more specific, let's assume that they know basic math/CS terminology like sets, functions, graphs, lists, etc. at the level of 1st/2nd year undergraduate CS student (which is the case with people who I have in mind). For example, they have read some introductory textbook like Aho and Ullman (although they might not have understood it completely).

Al Aho and Jeff Ullman, Foundations of Computer Science, 1992.

a good resource on/for this, fairly well known by academics but not so widely known outside of specialists, is Mathematical Writing by  Donald E. Knuth, Tracy L. Larrabee, and Paul M. Roberts. there is a published book, lecture videos, and a set of notes. it is more written from the perspective of people attempting to master mathematical writing eg for creating papers, but all the advice is highly applicable to the case of laymen attempting to formulate problems precisely. mathematical writing while formidable to learn is the scientific approach to rigorously define/formulate—and as the book details, solve, eg via algorithms or proofs—computational/algorithmic problems.

Mathematical Writing book info
Mathematical writing lecture videos index
Mathematical writing CS1193 class notes

also, the classic Garey & Johnson text, Computers & Intractability does not exactly describe how to formulate problems precisely, but it does give many examples, and diverse theoretical/conceptual/technical "patterns", organized into sections of similar problems, which can be used as "building blocks" to describe computational/algorithmic problems.


Proof plan for P ≠ NP Let $M$ be a Turing Machine for SAT. We want to encode certain paths of $M$ in a very short way in order to diagonalize against the paths.
For each natural number $k$, we will have a formula $\phi$ of length $n$ that does the following: $\phi$ is satisfiable iff the assignment encodes a run of $M$ on $\phi$ of length $n^k$ that ends in the reject state.
Suppose SAT can be computed in time $n^k$, and let $\phi$ be the formula associated with $k$. If $\phi$ is satisfiable, then the satisfying assignment encodes a run of $M$ on $\phi$ ending in the reject state. If $\phi$ is not satisfiable, then by our assumption there is a run of $M$ on $\phi$ of length $n^k$ ending in the reject state. An encoding of this path satisfies $\phi$. Contradiction. Therefore, SAT cannot be computed in time $n^k$.
Any opinions?  I'm curious if anyone has an immediate reason why this wouldn't work.  (I'm quite aware that it would be difficult.)

Before I explain what went wrong, notice the following red flag:
Let $T(n)$ be some arbitrary function representing some run-time. What would not work from this "proof" if we replace $n^k$ by $T(n)$? From what I see, pretty much nothing. Does that mean that $SAT$ is not solveable in any run-time? of course not!

Now to the actual problem: Each $\Phi_k$ depends on $n$, so let us call it instead $\Phi_k^n$. Notice, that the size of $\Phi_k^n$ would not be $n$, since it takes a lot of "space" to represent this formula. In fact, its size woul most likely be way bigger than $n^k$. When you run $M$ on $\Phi_k^n$, the runtime would take $O(|\Phi_k^n|^k)\approx O((n^k)^k)$ and not $O(n^k)$, since the runtime depends on the size of the input $\Phi_k^n$. This completely nullifies your argument that this is a contradiction.

As a side note, if you do actually manage to encode $\Phi_k^n$ in some magical way with size $O(n)$, then congratulations! Your argument holds and $P\neq NP$. But clearly its not easy to encode it like that... good luck :)


NP-completeness of scheduling to minimise tardy tasks with release times In "Computers and Intractability A Guide to the Theory of NP-Completeness" textbook pp 236, "Sequencing to minimize tardy tasks" is NP-complete.
To be specific the problem is as follows:

For each task $t \in T$, partial order $<$ on $T$, a length $l(t)$, and a deadline $d(t)$ and a positive integer $K \leq |T|$. Is there a one-processor schedule $s$ for $T$ that obeys the precedence constraints, that is $s$ is such that $t < t'$ implies $s(t)+l(t) < s(t')$, and such that there are at most $K$ tasks for which $s(t) + l(t) > d(t)$?

Now we associate each task with a release time $r(t)$ and $s(t)$ should be $\geq r(t)$. Does the revised problem stay NP-completeness ?

Assume the new problem was polynomially solvable. Take any instance of the old problem and add release dates $r(t)=0$ for all $t \in T$. Then the new problem has a "yes" answer for the modified instance if and only if the old problem had a "yes" answer for the original instance. We have reduced the old problem to the new one, so the new one is at least as hard.

This reduction works for any scheduling problem if you (only) add release dates.


Time complexity of travelling salesman problem Time complexity of travelling  salesman problem is $O(n^2*2^n)$ using held-karp algorithm. Now, if don't use dynamic programming and solve it using the recursive procedure, time complexity is still $O(n^2*2^n)$. I know there are overlapping of subproblems and there will be less computations but the time complexity is not getting better with the use of dynamic programming. Moreover, space complexity using held-karp is also $O(n*2^n)$ which is very large. We mostly use dynamic programming when we can improve the time complexity.

So, should we use dynamic programming here?

Here is the recursive approach..

TSP(graph, start, target) {
  if start == target {
    return 0;
  }

  min = infinity;
  for neighbor in neighbors(graph, start, target) {
    tour_length = TSP(remove(graph, start), neighbor, target)
                  + distance(graph, start, neighbor);
    if tour_length < min {
      min = tour_length;
    }
  }
  return min;
}

Time complexity using the recursive method is trying all "reachable" permutations of nodes before getting back to the first node which is in worst case $O(n!)$ (if all permutations are reachable).

However using recursion with memory may reduce it to the complexity of the DP solution. But using memory in itself is the idea behind the DP solution.


Recommended Reading for non-CS undergraduate student doing a research Project on Travelling Salesman Problem I am an undergraduate student in Industrial Engineering. I have taken the topic of Travelling Salesman Problem as a Research Project for my final year. More specifically, I am focusing on Convex Hulls for solving the Euclidean TSP.

I have gone through the published literature and have found that there are no approximation bounds for solving TSP using this method. I have just a little background in TheoCS (Started reading for fun since the last 3 months).

My Question:

Additional Books / Papers needed for achieving a good understanding of the mathematical rigor of the problem.

Here's what I am currently going through:

Approximation Algorithms - Vazirani
Introduction to Algorithms - CLRS
Introduction to Graph Theory - Douglas West
Randomized Algorithms - Motwani and Raghavan

I have also completed an introductory online course on Algorithms by Udacity.

I think I may need some background reading in Computational Geometry (Currently I do not know more than what I read in the chapter from Cormen)

This is my first question here, so sincere apologies in case my question does not conform to the Community Standards.

EDIT:

A resource I stumbled across today: In Pursuit of the Traveling Salesman - Mathematics at the Limits of Computation.
This is a good book for popular reading, providing a survey of the problem and various methods that have been used to solve it.

There are a few good books on the TSP problem where you are likely to find some relevant information:

Lawler et al., eds. The traveling salesman problem: A guided tour of combinatorial optimization. Wiley, 1985.

G. Reinelt. The traveling salesman: computational solutions for TSP applications. Springer, 1994.

G. Gutin and A. P. Punnen, eds. The traveling salesman problem and its variations. Kluwer, 2004.

Good luck with your research!


Minimum # toggle (3 consecutive elements) operations to convert ring A into ring B (rings made of Xs and Os: X->O and O->X) There is a ring A and ring B made of Xs and Os. My aim is to convert A to B by using only the minimum number of # operations. When I do # on an element i of the ring, element i-1, i and i+1 will be toggled. (toggled => X->O and O->X).

You can represent a ring as a $n$-bit string, where $n$ is the number of positions in the ring.  Encode an X as 1, and encode a O as 0 (zero).  That gives you a $n$-bit string, say $x$.

The # operation on index $i$ corresponds to xor-ing the string representing the current state of the ring with the string $c_i = 0^{i-1} 111 0^{n-i-3}$.  In other words, if the ring is currently $x$, then the # operation on index $i$ changes the state of the ring to $x \oplus c_i$.

Suppose you're given two rings $x,y$ and you want to find a way to transform $x$ into $y$.  Then all you need to do is find a subset of $c_1,\dots,c_n$ whose xor is equal to $x \oplus y$.  This will be the solution to your problem.  Can you see how to do that?  Solution below (don't mouse over until you've thought about it for a while):

   You can find that solution using linear algebra in modulo 2 arithmetic (i.e., Gaussian elimination modulo 2).


Reduce the following decision problem to CNF-SAT Input:

$X$ = {$x_1$,$x_2$,$x_3$,...,$x_n$}
$Y$ = {$y_1$,$y_2$,$y_3$,...,$y_m$}
$k$, where, $k$ $\leq$ $m$

Output (Yes/No):
Satisfying the following condition, can all the elements in set $X$ be assigned to elements in set $Y$, such that, no elements in $X$ is left unassigned?

Condition: At least $k$ elements in $Y$ is needed to access all the elements in $X$. All the elements assigned to $y_i \in Y$ are said to be accessible using $y_i$.

Reduce this decision problem to CNF-SAT.

Thoughts:

I have considered $n \times m$ no. of variables. Each variables for a pair of element of set $X$ and set $Y$. i.e., $a_{ij}$ : for all $x_i$ and $y_j$.

For ensuring that no elements in $X$ is left unassigned the CNF expression will be.
$(a_{11} \vee a_{12} \vee ... \vee a_{1m}) \wedge (a_{21} \vee a_{22} \vee ... \vee a_{2m})... (a_{n1} \vee a_{n2} \vee ... \vee a_{nm})$

I am not able to form the CNF expression for ensuring that at least $k$ elements from $Y$ are required to access all the elements in $X$. It seems that there will be an exponential number of clauses in the expression.

Thanks for helping.

Yes, you certainly can reduce it to SAT: the problem you state is obviously in NP, and thanks to Cook's theorem, everything in NP can be reduced to SAT.

I suspect that wasn't what you actually meant to ask.  Actually, your problem is in P: Hall's theorem says that such an assignment exists if and only if the corresponding bipartite graph has a perfect matching.  You can test whether a bipartite graph has a perfect matching in polynomial time using standard algorithms.


Can I Use Machine Learning to Predict the Likelihood of an Order Being Shipped? Let's say I have a database of freight orders.  The job is to match freight carriers with customers who need their freight moved.  I have the customer's information, the freight carrier's information, and all details related to the freight orders including date ordered, date shipped, the amount of money it took to hire the freight carrier, and whether a carrier was even found to ship the order.

If I have thousands of these past freight orders, could I use machine learning to look at future freight orders to predict whether or not a freight carrier will be found to move it?

Bonus:
If it is possible, what steps would I need to take to find the best data points to focus on?  From what I understand, I need to convert everything to a number in order to train the classifier, but I am having trouble figuring out what data features are going to help make these types of predictions.

I have been studying how to do machine learning and I am not looking for somebody to tell me everything there is to know on the subject, I just don't know how to determine what data points are going to be useful and am also looking for an answer to whether or not this is something machine learning can do(or if it's something a beginner in machine learning can do).  Sorry if the question seems vague, it's kind of hard to articulate on a subject you are just starting to learn about.  If anybody has materials they can link that would help me to better understand these things, I would appreciate that as well..

Here's the thing to know: machine learning assumes that there is some sort of statistical distribution, and you "learn" that distribution, in order to get the probability of some event.

The common saying in machine learning is "garbage in, garbage out." You have a bunch of random variables, but if those variables are all statistically independent, then you won't get anything useful from machine learning.

Say, for example, that there was a strong correlation between the amount of money paid for the carrier, and whether the item is shipped. Machine learning would likely be able to discover this relationship.

Or, if there were certain periods of the year where an item was more or less likely to be shipped. Machine learning could find this out.

But, if there's no underlying pattern in the data you give to your training algorithm, then you will get no useful information out of it.

For your question of finding the best data points: don't. That's what the machine learning algorithm is for. You give it your data, and it looks at which ones are statistically relevant, given some threshold. The whole point of machine learning is letting the algorithm do that for you, and more importantly, that's all the algorithm can really do for you.

Generally, these algorithms will work better when they have more data, so don't go out of your way to remove what data you're giving it.

And, remember, that ALL these algorithms are doing is statistics. If it says that the item is shipped with probability 0.6, don't be surprised when it isn't shipped. And, it's possible that it will say the item is shipped with probability 0.99, but it won't ship, because there's some variable which is hugely important in real life, which you didn't have recorded for your data set. If that variable isn't correlated with your data, then your model will be no good.


If graph isomorphism is in P, is then P = NP? I think that, since graph isomorphism is not known to be $\textbf{NP}$-complete, we can not reduce all problems in $\textbf{NP}$ to it, and therefore the implication does not hold.

Additionally, in the accepted answer to this question it is stated, that a proof that graph isomorphism is not $\textbf{NP}$-complete would prove $\textbf{P} \neq \textbf{NP}$. Why?

We don't know.

We do know that $\textbf{P} = \textbf{NP}$ implies graph isomorphism is in $\textbf{P}$, but the other implication has not been proven (to the best of my knowledge). It is suspected graph isomorphism is $\textbf{NP}$-intermediate (i.e., it is in $\textbf{NP} \setminus \textbf{P}$ and not $\textbf{NP}$-complete). This question as well as this other one list evidences supporting said suspicions.

Regarding your second question: If $\textbf{P} = \textbf{NP}$, then any (nontrivial) problem in $\textbf{NP}$ is trivially $\textbf{NP}$-complete because any (nontrivial) problem in $\textbf{P}$ is $\textbf{P}$-complete (and we have assumed $\textbf{P} = \textbf{NP}$). Hence, by contraposition, if the conclusion of this implication is false (i.e., there is a problem in $\textbf{NP}$ which is not $\textbf{NP}$-complete), then the premise (i.e., $\textbf{P} = \textbf{NP}$) must also be false.


Solving $T(n) = 3T(\frac{n}{3})+\sqrt{n}$ using master method How can I use the master's method in order to solve the recurrence formula $T(n)=3T(\frac{n}{3})+\sqrt{n}$ ?


Fastest (fast enough to compute) algorithm for finding permutations I have a set of letters, and a list of words, and I'd like to find all the possible "sentences" that can be built using the words from the list, while using up all the letters in the process. (A word can be used more than once.)
The maximum amount of words in a sentence is also given.

For example, my letters are {"a","a","a"}, and for the sake of simplicity, my words are {"a","aa","aaa"}, and I'm looking for sentences of maximum 3 words (cannot be more in this case anyway).

The order of the words in a sentence doesn't matter, so "a aa", and "aa a" would be considered duplicate sentences, so the output would be the following:

{"a a a", "a aa", "aaa"}

I need an algorithm that finds and lists these sentences (no matter how many there might be) for larger sets. Right now I have 9000 words, and 24 letters. (I know the amount of words is way too much, but let's just disregard that in this case.)

I'm really new to this kind of problem solving, and algorithms in general, so I tried several approaches on my own (and with the help of the internet) with obviously not much success.

The closest I could come up with was the following:

I assigned a prime to each character, and then each word would be the product of them, then considering the letters is together are also a "word", I could find out whether a word was a part of it with congruency, then after dividing the set of letters by word after word would eventually end up being 1, which means, I found a sentence.

So with this in mind, my approach was the following:

I start a sentence with each word, then then I find the next possible words for each one.
Then I take all the valid (now 2 word) sentences, and find a next word for each of them as well.
And I repeat this until I reached the maximum amount of words I'm looking for.

By "valid" sentences, I mean the ones that can be used in the next iteration, which means that their "letters" are not 1 (in which case no more words can be found, and the sentence is done), and a word was found in the previous iteration, no further validation takes place.

The problem with this is that it takes way too much time to be usable, e.g if I start with 3 words, for finding all the 3 word sentences in the worst case I would have to go through the list of words 3+3^2+3^3 times if I'm not mistaken, but I'm looking for sentences with a maximum of 6 words, and I'm supposed to start with a lot more words. Another problem is that with this approach I end up with duplicatons, and I'd need to filter the result in the end.

Are there any algorithms that are suitable for this kind of problem, or can it even be solved in polynomial time?

Thanks in advance

Suppose you are working with an alphabet of size $d$.  Then each word can be represented as its characteristic vector.  A characteristic vector $v \in \mathbb{N}^d$ is a vector, where the $i$th entry counts the number of times the $i$th letter appears in the word.  For instance, the word $abbad$ would have characteristic vector $(2,2,0,1)$ if the alphabet is $a,b,c,d$.

As Yuval explains, you want to find all strings which satisfy the following two properties: (1) they are a rearrangement of the list of letters, (2) they are a concatenation of up to $n$ words from the list of words (the same word can be used several times).

Looking at characteristic vectors, you can think of the problem as follows: you are given vectors $v_1,\dots,v_k$ (corresponding to the list of words) and a vector $w$ (corresponding to the characteristic vector for the list of letters), and you want to find non-negative integers $a_1,\dots,a_k$ such that

$$a_1 v_1 + \dots + a_k v_k = w.$$

You also want $a_1 + \dots + a_k \le n$ (to satisfy requirement (2) above).  You want to enumerate all solutions $a_1,\dots,a_k$ that satisfy these requirements.

This turns out to be an instance of enumerating lattice points in a convex polytope, for which there are well-studied algorithms.  See the following paper for an overview:

Effective lattice point counting in rational convex polytopes.  Jesús A. De Loerab, Raymond Hemmecke, Jeremiah Tauzera, Ruriko Yoshida.  Journal of Symbolic Computation, vol 38 no 4, Oct 2004, pp.1273-1302.  https://www.sciencedirect.com/science/article/pii/S0747717104000422

You could try applying one of those algorithms to your problem to see how well they work.

Alternatively, it's also possible to solve the problem by repeatedly invoking an ILP solver.  You can use an ILP solver to test whether any solution exists, and the largest value of $a_1$ such that a solution exists.   Then,  if at least one solution exists, you enumerate $a_1=0,1,2,\dots$, and for each value of $a_1$, plug in the value of $a_1$ and recursively invoke the same algorithm to enumerate all solutions for $a_2,\dots,a_k$ (such that $a_2 v_2 + \dots + a_k v_k = w - a_1 v_1$ and $a_2 + \dots a_k \le n - a_1$).  This might be inefficient, though.


Is X+Y sorting problem still an open problem? I have found that X + Y sorting is an open computer science problem but that book was too old and then I have google it but didn't find any strong evidence that it is still open or there is an algorithm that can solve it in O(n2) comparison without using Fast Fourier Transform.

Is there any algorithm proposed that can solve it in O(n2) comparison or is it still unsolved?

Here the problem status is "open". The page was revised in 2006 and it seems updated to September 2017, so we can safely suppose that the problem is still open.
Anyway, an algorithm that solves the problem using $O(n^2)$ comparison (and total complexity $O(n^2\cdot \log(n))$) is known from 1992: J.-L. Lambert, Sorting the sums $x_i+y_j$ in $O(n^2)$ comparisons, Theoretical Computer Science, (1992):103, 137–141 doi 10.1016/0304-3975(92)90089-X.


Implications of Integral linear program Let $(P)$ an Integer Linear Program, where we aim to find $x\in \{0,1\}^n$ maximizing a linear function $f:\mathbb{R}^n\rightarrow\mathbb{R}$ under some linear constraints $Ax\le b$

Let $(P^*)$ be its relaxation, which means that the constraint $x\in \{0,1\}^n$ is replaced by $x\in [0,1]^n$.

Then, suppose that we know that
$$
\max_{x\in \{0,1\}^n} \left\{f(x), Ax\le b\right\} = \max_{x\in [0,1]^n} \left\{f(x), Ax\le b\right\}
$$

Is it possible, given an optimal solution $y^*\in[0,1]^n$ of $(P^*)$ (that we have found with simplex algorithm for instance), to find an optimal solution $y\in\{0,1\}^n$ of $(P)$ (i.e. such that $f(y)=f(y^*)$ and $Ay\le b$),  say in polynomial time ? Or is there any concrete conter-example ?

In general, this is not possible unless P=NP. So, it is unlikely that such a method exists.

Many NP-hard problems can be modeled as an integer program, we take 3SAT for an example. Suppose we are given a 3SAT instance with clauses $C_i$ and variables $v$. For each clause, denote the variables that appear positive by $C_i^+$ and the variables that appear negative by $C_i^-$. Now, consider the following integer program $P$:

$\begin{align}
\max 1 \quad \text{s.t.} \quad & \sum_{v\in C_i^+} x_v + \sum_{v\in C_i^-} (1-x_v) \geq 1 \text{ for all } i\\
& x_v \in \{0,1\} \text{ for all } v
\end{align}$

Note that $P$ has a feasible solution if and only if our 3SAT instance is satisfiable. (a solution to $P$ corresponds to a satisfying assignment of the 3SAT instance) This solution is then 'optimal' as well, as all feasible solutions of $P$ have the same cost. This means that also the relaxation $P^*$ must have the same cost if $P$ is feasible. So, we will assume that the given 3SAT instance is satisfiable, so that the costs of $P$ and $P^*$ are equal.

Now, suppose we have some method to find a solution for $P$ from a solution $y\in [0,1]^d$ for $P^*$. As $P^*$ is a normal linear program, we can find such a solution $y$ in polynomial time, by using e.g. the ellipsoid method. Then, our method gives us a solution for $P$ in polynomial time. But this solution gives a satisfying assignment for our initial 3SAT problem, which means we can find a satisfying assignment to 3SAT problems in polynomial time. As finding a satisfying assignment for 3SAT is NP-hard (even if we know the instance has a satisfying assignment), this means that P=NP

I suppose that intuitively, what is going on here is that knowing the value of a solution to an integer program does not tell you a lot about the specific variable assignment. In a way, this is because the 'complexity' of a linear program lies mostly in its constraints, rather than the goal function.


Understanding the geometrical interpretation of word2vec I'm trying to understand how the $word2vec$ method actually nudges word vectors of similar semantic/syntactic content closer together in the word vector space.

I've read here (Quora answer) that it's because $word2vec$ tries to maximise the probability of target word $w$ given context $c$, and that this probability is roughly inversely proportional to the distance between $w$ and $c$ in the word vector space. I don't really see why the latter is the case though.

If two words tend to appear in the same context, then they will tend to receive a similar word vector.

For instance, a large corpus might contain sentences like "I really love Fuji apples" and "I really love Gala apples".  From this we can see that "Fuji" and "Gala" have appeared with the same context (in this case the context is "love _ apples", if by context we look one word to the left and one word to the right).  This will tend to cause the optimization algorithm to assign Fuji and Gala vectors that are similar.

As you can see, words that tend to be associated with the same surrounding context will often have a similar semantic content.  Not always, but it's a good heuristic.


What are applications of computational models beyond P? If I may summarize how I feel about collapse of the polynomial hierarchy:

Are intractable models of computation, including collapse of $\mathbf{PH}$  or $\mathbf{PSPACE}$ above but not down to $\mathbf P$ useful for any reason besides the off chance they might collapse? Obviously "useful" is broad - I would gladly be interested in answers outside of computer science, but I am wondering if their study helps us understand really anything besides them themselves.

I am taking complexity theory and have essentially been wondering this entire semester, if my increasingly fluency in problems of the form $\exists\forall\exists\forall...$

Not all problems that are encountered in an industrial setting are clearly either NP-Complete or else polynomial-time solvable, even with randomness, heuristics and approximation. So if you encounter (a variant of) a problem such as Exact Independent Set, or Succinct Graph Diameter, for example, then you ought to be looking to the complexity classes $\text{DP}$ and $\Sigma_2^P$. Without the study of these classes, there is no proper placement of these problems, no way to relate them to one another and therefore no way to tackle them coherently, and no way to quantify their hardness. We might look for a way to compactly store and then sell the solutions to NP-Complete problems after we've brute forced them for many inputs. But because of Karp and Lipton, we know that this is impossible, unless the polynomial hierarchy collapses to the second level. In general, these conditional collapses are great for question of the form "Can I...", "No.".

I would love to provide an answer like "We were struggling, but then Immerman and Szelepcsényi proved that $\text{Nondeterministic Logspace}$ was closed under complement, and that really gave a boost to our startup!", being a student myself I don't have any anecdotal evidence, and I would love to hear from someone more seasoned.

So if you are looking for an industrial application of computational complexity theory beyond SAT Solvers, then you may be disappointed. Complexity theory is to computer science a bit like string theory is to physics; it is purely theoretical and its study is not motivated by the urge to solve a particular problem, but rather to understand the nature of computation - how do randomness and nonuniform computation relate to one another? Do all programs with small memory footprints have a fast implementation? - very much like the motivation of theoretical physics is not to design a slightly more efficient engine, but rather to understand the laws of physics. You are taking a theoretical class, and must not be surprised to learn about theoretical results. There are coding classes where you come from; if you prefer those, take those.

If I take the liberty of venturing into speculation, then you may know that right now we do not even know how to rule out ridiculous scenarios in which $\text{BPP}=\text{NEXP}$. Of course everyone believes that the result will be $\text{BPP}\subsetneq\text{NEXP}$, but a proof of this fact cannot come without major advances in our understanding of computation, and, staying with the metaphor of physics, where major advances in our understanding of fundamental physics invariably spurs major progress in unexpected areas, I feel confident in saying that these results, when they come, will spur major progress across all fields of computing.


Doubt with the halting problem undecidable proof The Halting problem proof can be seen as the following programs:

Ends(P, I) is a program that detects (returns true or false) if the program P will halt or
not with the input I
Diag( P ): is a program that

2.1 Halts if P( P ) doesn't halt

2.2 Doesn't halt if P (P) halts

If we use (2) with input Diag it state:

Diag(Diag) halts if Diag(Diag) doesn't halt
Diag(Diag) doesn't halt if Diag(Diag) doesn't halt

Which by contradiction is proven that the program Ends can't exist.

Until here everything is fine. But What if instead of thinking on halt or never halt, we think in steps.

What if I do the following analogy:

Ends( P, I, S ) is a program that detects (returns true or false) if the program P with the input I, it will halt in less or equal S steps.
Diag( P, S) = Diag( P ): is a program that:

2.1 That halts in less or equal than S steps if Ends( P, P, S ) doesn't halts in less or equal than S steps.

2.2 That doesn't halts in less or equals than S steps if Ends( P, P, S ) halts in less or equal than S steps.

if we use (2):

Diag( Diag) halts in less or equal than S steps if Ends( Diag, Diag, S ) doesn't halt in less or equal than S steps.
Diag ( Diag ) doesn't halt in less or equals than S steps if Ends(  Diag, Diag, S ) halt in less or equal than S steps.

Which is the almost the same contradiction, and in this case Ends is possible to build.

What I'm doing wrong?

The main problem with your analogy is the construction of Diag. The usual proof goes as follow:

Assume Ends exists.
Then we can construct Diag with a Turing machine calling Ends. As follows:

Diag(P) = If Ends(P,P) then Loop indefinitely Else Terminates.

This leads to a contradiction thus Ends does not exist.

What you are doing is the following:

1'. Construct Ends(P,I,S).

2'. Construct Diag(P,S).

3'. This leads to a contradiction.

The main problem is that you do not provide the actual construction of Diag in step 2' as we did it in step 2. How can you implement Diag with a TM machine calling Ends? I do not think so as you need more than S steps to run the program Ends.


Two questions on MSO First question :

Is the following formula a valid MSO formula?

$\theta(S, r) = \exists (e_1, t_1), ... ,(e_h, t_h) \bigwedge\limits_{(e_i, e_j) \in \rho(S,r)} \mathcal{R}((e_i, t_i), (e_j, t_j))$

So my main concern here is the fact one states there exists $e_1, t_1$ etc. but then goes on to not use these in the actual formula (only using $e_i$ and $e_j$). Is this correct?

Second question :

While browsing around, I found the following :

(found in this post : MSO (Monadic second-order logic) Logic On Words)

My question here is, in MSO, how come one can still use 2-ary relations, such as $S(x,y)$ (as well as $\mathcal{R}((e_i, t_i), (e_j, t_j))$ from the first question), since I thought MSO is supposed to use only 1-ary relations, i.e. sets?

I think I might have found the answer myself, but I would like to verify : is this allowed because one does not quantify over these 2-ary relations?

You are asking two questions. The first question is about logic more generally. You are wondering whether a statement of the form
$$ \exists x \, \mathrm{True} $$
is valid, although $\mathrm{True}$ doesn't mention $x$. There is absolutely no requirement in the syntax of logical formulas that  you use all the variables you quantify over. This similar to functions which don't depend on all of their arguments. Do you object to the function $f(x) = 1$?

As for your second question, monadic refers to the fact that you are only allowed to quantify over unary predicates. The language itself can freely contain $k$-ary predicates for any $k$. Compare this to first-order logic, in which you are not allowed to quantify over any predicates. Would that mean that first-order logic only allows for 0-ary predicates?


Are HTML and CSS regular languages? I have a question whether or not CSS and HTML are regular languages.

I believe CSS is a regular language, since it should be possible to create a regular expression to match the structure of CSS.

However, I believe that HTML is not a regular language since you have nested attributes that could be defined recursively.

Providing a regular expression or DFA for a language and proceeding to demonstrate that it is correct for the language in question generally constitutes a pretty convincing argument for the regularity of the language. To prove a language is non-regular, you have a few options: the pumping lemma for regular languages is a classic standby, but the Myhill-Nerode theorem is pretty nifty, too (especially since you can use it to prove regularity as well as non-regularity).

Your first job should be to define what constitute valid strings in the languages $HTML$ and $CSS$. Note that most browsers will take anything you call $HTML$ and display something without error; in that sense, anything is valid $HTML$, and the language $\Sigma^*$ is trivially regular. However, I think it's safe to assume that you have something a bit more strict in mind: $HTML$ consists only of those strings that conform to some standard, which probably calls for matched tags. In this case, you should be able to prove that $HTML$ isn't regular, since you can consider the following kinds of strings (whitespace is added only for clarity and could be removed in the real string):

                  ...

This language,  $($

 $)^n($

 $)^n$`</body></html>`, should be enough to get to a proof of non-regularity, provided you accept the above as valid $HTML$, and would say that a missing `</table>` tag would make the resulting string invalid $HTML$, even though browsers would try to render it anyway.

For $CSS$, first figure out what strings you think are valid, then try to come up with a regular expression or DFA for the set of all $CSS$ strings, or figure out how to define a subset of $CSS$ that requires non-local checks and unbounded memory (counting, matching, nesting, etc.) If you can define such a subset (like we did for $HTML$ above), then you're good to go.


Generative power and classification of matrix grammars [Edited] I am reading about matrix grammars from several sources and got confused about its generative power and classification to the Chomsky hierarchy.

In here it is stated that:

A matrix grammar is a quintuple $G = (N, T, M, S, F)$, where $N,T$, and $S$ are specified as for a context-free grammar, $M = \{m_1, m_2, \dots m_n \}$ is a finite set of finite sequences of context free rules (i.e. for $1 \leq m_1 \leq n$, $m_i = (A_{i,1} \rightarrow w_{i,1}, A_{i,2} \rightarrow w_{i,2}, \dots A_{i,r_i} \rightarrow w_{i,r_i})$ for some $r_i \geq 1$, $A_{i,j} \in N$, $w_{i,j} \in (N \cup T)*$, and $1 \leq j \leq r_i$) and $F$ is a subset occurring in the matrices $m_i$
$L(MAT)$ denotes the set of all languages that can be generated by matrix grammars  -
Theorem $L(MAT) = L(RE)$
Theorem For each recursively enumerable language $L$, there is a matrix grammar $G$ in normal form such that $L (G) = L$.

While although this paper is about simple matrix grammars, it also states a definition of matrix grammars (not simple matrix grammars) that is a bit different with the above definition. It is stated that

A matrix grammar (MG for short) is a pair $H = (G, M)$ where $G = (N,T,P,S)$ is a context-free grammar; $M$ is a finite language over the alphabet of rules $(M \subseteq P^*)$.
For $x, y \in (N \cup T)^*, m \in M$,
$x \Rightarrow y[m]$
in $H$, if and only if there are $x_0, x_1,\dots, x_n$ such that
$x_0 = x, x_n = y$, and
$x_0 \Rightarrow x_1[p_1] \Rightarrow x_2[p_2]) \Rightarrow \dots \Rightarrow x_n[p_n]$ in $G$, and
$m = p_1 p_2 \dots p_n$, where $p_i \in P, 1 \leq i \leq n$, for
some $n \geq 1$.
Let $MT$ denotes the family of languages that is generated by matrix grammars
$CF \subset MT \subset CS$

Question. How come when matrix grammars can generate recursively enumerable languages but it is still classified as a proper subset of the family of context-sensitive languages? Perhaps because they are different matrix grammars? I also read about it in this book but it is too complicated for me.

Additional Question.  If a grammars $G$ can generate some context-sensitive languages (let's say that the family of languages generated as $XG$ ), is it still possible that the family of languages is going to be classified as a proper subset (strict inclusion) of $CS$, i.e. $XG \subset CS$?

Isn't the difference because matrix grammars exist with and without appearance checking? In the usual notation $\mathrm{MAT} \subset \mathrm{MAT}_\mathrm{ac} = \mathrm{RE}$.

A matrix grammar basically is a grammar with so-called matrices, lists of context-free type of productions $(A_1\to x_1, \dots, A_k\to x_k)$. There are two main variants of how to apply productions in matrix grammars. Either a matrix is applicable if all its productions can be applied in the given order. This is the less powerful variant, although we can generate $\{ a^nb^n c^n \mid n\ge 1\}$ that way.

Alternatively in a more powerful version some of the productions in a matrix may be marked as skipping productions. If the left-hand nonterminal in such production is present in the string it must be applied, when it is not present the production can be skipped. It is called appearance checking, and turns out to be a very powerful feature.

(added) In your new explicit definition of matrix grammars the set $F$ of occurrences of productions in the matrices are in fact the productions that can be skipped whenever the left side is not present (normally they would block the application of the matrix).
So, when $F\neq\varnothing $ your model has appearance checking. Your first reference indeed has this feature, but does not mention it explicitly by name.


How can we solve halting problem efficiently? I was doing exercises regarding the halting problem and there is this question where I am stuck
Ques: it goes like suppose if you can decide the halting problem with a query "Is <tm,s> belongs to HALT?" (tm = turning machine and s = string) so it can solve i number of instances <tm1,s1> <tm2,s2> <tm(i),s3(i)> now it says show how can we solve 3 instances with 2 queries only?
I am not sure how to start thinking about this one.. like should we have to simulate one instance with another one? Can anyone provide a proof?

The idea is to determine how many of the Turing machines halt. We will show more generally that given $N = 2^n-1$ many Turing machines $T_1,\ldots,T_N$, we can determine which of them halt (on the empty input) using only $n$ calls to an oracle that solves the halting problem.
First, let us see how to determine, using a single oracle call, whether at least $\ell$ of the Turing machines halt. The idea is to construct a Turing machine $S_\ell$ which runs all of $T_1,\ldots,T_N$ in parallel, and halts once $\ell$ of the machines have halted.
Given this, we can determine how many of $T_1,\ldots,T_N$ using binary search. In your case, $N = 3$, this proceeds as follows:

Determine whether at least two of $T_1,T_2,T_3$ halt.
If so, determine whether at least three of $T_1,T_2,T_3$ halt.
Otherwise, determine if at least one of $T_1,T_2,T_3$ halts.

Having found out that exactly $\ell$ of the machines halt, we simply simulate all the machines in parallel until $\ell$ of them halt. The remaining machines will not halt.
It would be interesting to figure out whether this is optimal, that is, whether we can determine the halting of more than $2^n-1$ machines using only $n$ oracle calls.


Finding Minimum Weight Subgraph Spanning Tree Suppose we have a graph $G = (V, E, w:e\in E \to x \in \{0,1\})$. That is, a set of vertices, a set of edges and a weight function that assigns edges weights of 0 or 1.

Suppose we also have a subset of vertices $S \subset V$ and that we want to find a minimum-weight tree that spans the vertices in $S$. Since the vertices in $S$ might not be directly connected, we are allowed to use vertices in $V$ that may not be in $S$ to build our minimum-weight tree.

Is there an algorithm similar to Prim's or Kruskal's that we can use to solve this?

No, it's highly unlikely there is a polynomial time algorithm for this problem. The problem you describe is known as Steiner tree, and it is NP-hard. Moreover, it is computationally quite difficult from many other viewpoints as well.

A classical dynamic programming approach is the Dreyfus-Wagner algorithm running in $O^*(3^k)$ time, where $k$ is the number of terminals (i.e., the size of the set of pairs $S$ in your terminology). There is a lot of literature on the problem, so you might want to look at it from a particular viewpoint.


Could my algorithm be considered Divide-and-Conquer? So for my homework, I was supposed to design an algorithm which was divide-and-conquer that fulfilled the task of finding the two smallest numbers in an array of size n.

I recognize that my version is a bit cheap in that regard, in that it uses reference variables and only does work on the size 1 cases of the recursion. Is this still technically considered divide-and-conquer? Or is it practically too close to a linear search. If it is divide-and-conquer, how could you express the recurrence relation when the work is being done only on the "leaves" of the recursion.

   find_mins(int A[], int& min, int& sec_min, int l, int r){
    int pivot = (l+r)/2;

    if(l==r){
      if(A[l] < min){
        sec_min = min;
        min = A[l];
        return;
      }
      else if(A[l] < sec_min && A[l] > min){
        sec_min = A[l];
        return;
      }
      return;
    }

    find_mins(A,min,sec_min,1,pivot);
    find_mins(A,min,sec_min,pivot+1,r);

}

"Pseudocode"

FUNCTION(Array, min1, min2, left, right)
  Find pivot
  if(size of subproblem is 1)
    calculate mins
  function(Array,min1,min2,1, pivot)
  function(array,min1,min2,pivot+1,right)

Keep in mind, the code really isn't all that relevant, I just am curious if the structure fits divide-and-conquer description. My concern is that because work is only being done on the case where the size is 1, that it's more of a "linear search" than anything else.

TL;DR
Divide and concur doesn't have any rigorous definition.  So any argument you make for or against will be just an emotional argument.  The situation is made worse by the fact that the task accomplished by this algorithm doesn't need D&C.  So, the answer is "probably".
Long version
One scenario where it would make sense to use D&C in finding the minimum is a distributed system (eg. Hadoop), where the size of input may require from you that you do computation in chunks.  The algorithm as you designed it is not suitable for this task because it would have to communicate the best result found so far to all parts of the program handling the computation of each chunk.  The version I've written below eliminates this problem by computing local minima for given sublists and then calculating the minima of the previously computed minima and so on.  This feels (remember emotional argument?) more like D&C.  Besides, it makes the algorithm more language-agnostic and eliminates the corner-case errors.

Empty lists have no minimum.
Lists with only one element have only one minimum (not two).
If a list happens to have more than one minimum element, then the second minimum will be equal to first minimum.
Solution doesn't require guessing the minimum before running the algorithm.

The code is set in Prolog.  I believe it is better than conventional pseudo-Pascal in that it allows to avoid "uninteresting" parts of the algorithm.
two_mins([], _, _) :- !, fail.  /* Empty list has no minimum */
two_mins([Min1], Min1, _) :- !. /* There is only one element */
two_mins([Min1, Min2], Min1, Min2) :- Min1 < Min2, !.
two_mins([Min1, Min2], Min2, Min1) :- !.
two_mins(List, Min1, Min2) :-
    length(List, N),
    LenA is N div 2,
    length(A, LenA),
    append(A, B, List),
    two_mins(A, Min1A, Min2A),
    two_mins(B, Min1B, Min2B),
    Min1 is min(Min1A, Min1B),
    /* In case A or B had only one element, we will get
       rid of non-instantiated solutions. */
    include(ground, [Min2A, Min2B], Ground),
    min_list([max(Min1A, Min1B) | Ground], Min2).


Is $\Pi’\propto_{poly}\Pi$ for any two NP-complete problems $\Pi,\Pi'$? I am facing the following question:

Let $\Pi$ and $\Pi$’ be two NP-complete problems, prove or refute $\Pi’\propto_{poly}\Pi$.

I do not understand the meaning of this question and how to answer it.
The definition of $\Pi’\propto_{poly}\Pi$" as follows:

Let $\Pi$ and $\Pi'$ be two decision problems. We say that $\Pi$ reduces to $\Pi'$ in polynomial time, symbolized as $\Pi’\propto_{poly}\Pi$, if there exists a deterministic algorithm $A$ that behaves as follows. When $A$ is presented with an instance $I$ of problem $\Pi$, it transforms it into an instance $I’$ of problem $\Pi'$ such that the answer to $I$ is yes iff the answer to $I’$ is yes. Moreover, this transformation must be achieved in polynomial time.

Try to combine the following two definitions:

A problem $\Pi$ is NP-hard if $\Pi' \propto_{\mathit{poly}} \Pi$ for every $\Pi'$ in NP.
A problem $\Pi$ is NP-complete if $\Pi$ is NP-hard and $\Pi$ is in NP.


It is possible to write any program (i.e. Turing complete) with just one single expression? So I'm currently taking discrete math II at my university and I came across a somewhat philosophical question (so I apologize if this is question is hard to answer precisely) of whether mathematicians and computer scientists view computation in the same way.

We computer scientists define computation with the Turing machine and/or lambda calculus. I was simply wondering if there is some language/notation (lambda calculus??) that allows a mathematician to write a computable (i.e. Turing computable) program using only one mathematical expression.

Again, I apologize if that's a bit of an abstract question (I'm new to these concepts and my terminology isn't great) but let me try to clarify: in math (or at least when I did math in school), there isn't the notion of control flow over time with different statements--there is only a single expression that evaluates to a value. Evaluating the expression may involve partially evaluating nested expressions in a certain order but the end result and the expression itself represented computation in some sort.

So now my question is this:

(Through the use of lambda calculus) is it possible to write any program (i.e. Turing complete) using only one expression with no more than one statement? Is lambda calculus set up in a way that removes or hides the notion of control flow?

I think that your general question is pretty broad, because you'd need to specify what you consider a program (e.g. is the identity function that outputs the input it receives a program?).

It is possible to have some sort of control flow in lambda expressions (there are only expressions in lambda calculus); consider e.g. Church Booleans that enable conditionals.

If you would like to see examples of lambda calculus expressions put to work like regular programs, I can recommend John Tromp's binary lambda calculus. I have been able to evaluate some of his programs using plain β-reductions (examples), so I can say it's definitely possible to write programs even with pure lambda calculus.


Number of Comparisons in an Algorithm The number of comparisons in the following algorithm is supposed to be $3n/2 - 3/2$ if $S$ is odd. I understand that the for loop is $3n/2$ comparisons, but I fail to see where the $-3/2$ comes from.
if (n % 2 == 0):
    if (S[0] > S[1]):
        Largest = S[0]
        Smallest = S[1]
    else:
        Smallest = S[0]
        Largest = S[1]
    I = 3
else:
    Smallest = Largest = S[0]
    I = 2

for (i=I; i<=n-1; i+=2):
   if S[i] < S[i+1]:
     if S[i] < Smallest:
      Smallest = S[i]
     if S[i + 1] > Largest:
      Largest = S[i + 1]
   else:
     if S[i + 1] < Smallest:
      Smallest = S[i + 1]
     if S[i] > Largest:
      Largest = S[i]

If $n$ is odd, no comparison involving elements of $S$ is performed outside of the for loop.
Moreover, each loop iteration performs exactly $3$ comparisons involving some element in $S$. The number of iterations is the minimum integer value of $k$ such that $2+2k > n$, i.e., $k=\left\lceil \frac{n-2}{2} \right\rceil = \frac{n-1}{2}$.
Therefore, the total number of comparisons involving some element in $S$ is $3 \cdot \frac{n-1}{2} = \frac{3n}{2}-\frac{3}{2}$.


Game of Nim (Find winning states in large range) If I want to solve a game of nim with 3 piles containing (x, 2x, 3x) respectively

I know that the solution of (winning) iff x^2x^3x != 0

but if x can be in the range from 1 to 2^61 so How many winning states in this range?

I want to solve this problem ... I tried to find a pattern but I think there is no pattern for that

Let $a=a_{n-1} \cdots a_0$ and $b=b_{n-1} \cdots b_0$ be two positive integers with given binary expansion. Since $z+w = 2(z \land w) + (z \oplus w)$, we have
$$
a + b = a \oplus b + 2(a \land b),
$$
where $a \oplus b$ and $a \land b$ are bitwise XOR and AND. In particular, $a + b = a \oplus b$ iff $a \land b = 0$.

Consider now the equation $x \oplus 2x \oplus 3x = 0$. We can rewrite it as $x \oplus 2x = 3x = x + 2x$. Above we have seen that this is equivalent to $x \land 2x = 0$. If $x = x_{n-1} \ldots x_0$ then
$$ x \land 2x = 0 (x_{n-1} \land x_{n-2}) \ldots (x_1 \land x_0) 0. $$
Thus $x \oplus 2x \oplus 3x = 0$ if the binary expansion of $x$ doesn't contain two adjacent 1s.

It remains to count how many binary strings of length $n$ (in your case, $n = 61$) satisfy this condition. It is a standard exercise to show that the answer is the Fibonacci number $F_{n+2}$.


Accurate definition of BPP I'm a bit confused about the definition of BPP. The way BPP is defined in typical text books (Arora/Barak for example) is that if M(x) is a Probabilistic Turing Machine (PTM) that recognizes a language $L(x)$, then $Pr[M(x)=L(x)]> 2/3$. My question is, what is the probability taken over? Arora/Barak remark (7.2) that the probability is taken over internal coin tosses of $M(x)$, i.e., fix a value of $x$, and run all possible $2^{T(|x|)}$ experiments of internal coin tosses, and compute the majority of accept state. But if this is true, then Amplification theorem cannot hold because by definition if the probability is computed by executing all $2^{T(|x|)}$ possible coin-flips, then no matter how many times I run the algorithm, the probability is not going to change. (For example, if I have a bag with 2 red balls and 1 blue ball, then no matter how many times I pick a ball from the bag (and return it), the probability of picking a red ball is going to remain 2/3.)

Basically, a PTM is a random process in two variables: The input string $x \in \{0,1\}^*$ and random coin tosses $ r \in \{0,1\}^{T(|x|)}$. For the amplification theorem to hold, I think one needs to fix a value of $r$ and run the machine on all values of $x$, and compute $Pr[M(x) = L(x)]$. Then for a fixed $x$, running $M(x)$ multiple times will have amplification effect, but if the probability is computed over internal coin tosses, then the Amplification theorem cannot hold.

What am I misunderstanding here?

Repeating what MCH said, every time you run the algorithm, you use fresh random bits.

As an example, here is a BPP algorithm that computes the number $1$:

Toss a biased coin (heads w.p. 2/3, tails w.p. 1/3). If heads, output 1, else output 0.

The algorithm "succeeds" with probability $2/3$. The amplification procedure amounts to tossing $n$ biased coins, outputting $1$ if the majority of them were heads, and $0$ otherwise. Since we expect roughly $(2/3)n > n/2$ of the coins to be heads, it is very likely that the amplified algorithm is successful (outputs $1$).

In other words, when you run your algorithm $n$ times, each time you run it, you re-toss all the coins. So the amplified algorithm tosses $n$ times as many coins, and the probability is taken over all these coin tosses.


When an ISAM index is built, how is the number of leaf nodes per index node (the "fan-out") calculated? I asked this question on DB.SE but it didn't get any traction, so I'll ask it here...

The following statement is in the Ramakrishnan text (2nd ed. page 252):

(emphasis in bold is mine)

  The non-leaf pages direct a search to the correct leaf page. The number of disk I/Os
  is equal to the number of levels of the tree and is equal to $log_FN$, where $N$ is the
  number of primary leaf pages and the fan-out $F$ is the number of children per index
  page. This number is considerably less than the number of disk I/Os for binary search,
  which is $log_2N$; in fact, it is reduced further by pinning the root page in memory. The
  cost of access via a one-level index is $log_2(N/F)$. If we consider a file with $1,000,000$
  records, $10$ records per leaf page, and $100$ entries per index page, the cost (in page
  I/Os) of a file scan is $100,000$, a binary search of the sorted data file is $17$, a binary
  search of a one-level index is $10$, and the ISAM file (assuming no overflow) is $3$.

Question: How is the value of F calculated when the index is constructed?

From the example given it seems the structure will be:

root node containing 1,000 pointers to index nodes
one level of 1,000 index nodes, each containing a pointer to 100 leaf nodes
100,000 leaf nodes, each containing ten records

Assuming that is the correct understanding of what he describes, what determines the value of $F$ when the index is built? Is it calculated in such a way that the index will have exactly 3 levels and so $F$ is set to ensure we can reach all leaf nodes in 3 steps? This doesn't seem to be the case since he has a diagram elsewhere in the book of an ISAM index with more than 3 levels.

So then what dictates the value of $F$? i.e. what keeps it from being 1K or 100K?

In a page-structured file, each page has a fixed size. This effectively eliminates internal fragmentation.

Each index page needs to store a bunch of keys and corresponding pointers to other disk pages. The number of keys-and-pointers that can be stored in a disk page is what determines F.

So how big is a page?

In a real-world DBMS, the lower limit is the virtual memory page size, which is determined by the hardware and the operating system. The physical block size of a disk is typically smaller than this, so that's not a concern. Setting your file page size to be some multiple of the VM page size lets the operating system buffer cache act as the database buffer cache.

The upper limit is set by efficiency considerations, since pages which are too big require more I/O and also potentially wastes space when pages are under-full.

So in practice, a small power-of-two multiple of the VM page size is appropriate.


CLRS Question 8-6 Lower bound on merging sorted lists I'm doing the CLRS Problems and there's a part I'm having trouble following.
The question is:
Part a) Given 2n numbers, compute the number of possible ways to divide them into two sorted lists, each with n numbers.
Part b) Using a decision tree and your answer to part (a), show that any algorithm that correctly merges two sorted lists must perform 2n−o(n) comparisons.
Part a) makes senses to me.
The first line to the solutions of part b) states any decision tree to merge two sorted lists must have at least $2n$ choose $n$ leaf nodes.
I don't follow why this is. In particular, what is each branch comparing to get to this result? And what does each leaf node represent?

Let us consider any comparison-based algorithm for merging two ordered lists $A,B$ of length $n$, focusing on the case in which all $2n$ numbers are distinct. When the algorithm terminates, the results of the comparisons determine the merged list. Stated differently, if we describe the algorithm as a decision tree, then each leaf is labelled with the merged list, which is some permutation of the elements in $A \cup B$. Since all elements are different, each possible such permutation must be represented as some leaf.
Since the lists $A = (a_1,\ldots,a_n)$ and $B = (b_1,\ldots,b_n)$ are ordered, the permutation $\pi$ labeling each leaf must satisfy the following property: if $i < j$ then $a_i$ appears before $a_j$ and $b_i$ appears before $b_j$. This implies that $\pi$ is determined from the set of indices containing elements of $A$. There are $\binom{2n}{n}$ such possible sets, and all corresponding permutations can actually happen, as can be seen by assigning the element in the $k$th the number $k$. For example, if $n = 2$ then the possible orders are:

$a_1,a_2,b_1,b_2$ – achieved for $A = 1,2$ and $B = 3,4$.
$a_1,b_1,a_2,b_2$ – achieved for $A = 1,3$ and $B = 2,4$.
$a_1,b_1,b_2,a_2$ – achieved for $A = 1,4$ and $B = 2,3$.
$b_1,a_1,a_2,b_2$ – achieved for $A = 2,3$ and $B = 1,4$.
$b_1,a_1,b_2,a_2$ – achieved for $A = 2,4$ and $B = 1,3$.
$b_1,b_2,a_1,a_2$ – achieved for $A = 3,4$ and $B = 1,2$.

Therefore the decision tree must contain at least $\binom{2n}{n}$ leaves. Since it is binary (we assumed that no two elements are equal), its depth must be at least $\log_2 \binom{2n}{n}$. Stirling's approximation shows that $\binom{2n}{n} = 4^n/\Theta(\sqrt{n})$, hence $\log_2 \binom{2n}{n} = 2n - \Theta(\log n)$.


What Do These Symbols Mean in Repetitive Rule Application and How Are They Applied Practically? Frequently in cs blogs and books I see this notation, =>* and =>+ but I am not sure how it is being applied in a production rule and it's significance. What exactly does it represent, and can you show an example of it being applied.

In most CS contexts, including this one, $X^*$ means any number of $X$'s, including zero, and $X^+$ means one or more $X$'s.

So $A\Rightarrow^* B$ just means that $A$ gets to $B$ by some number of steps and, if that number is zero, then $A=B$. More formally, it means that there is some number $\ell\geq 1$ and objects $C_1, \dots, C_\ell$ such that $A=C_1$, $B=C_\ell$ and $C_i\Rightarrow C_{i+1}$ for each $i\in\{1, \dots, \ell-1\}$.  $A\Rightarrow^+ B$ means the same thing except with $\ell\geq 2$.

So, for example, given the grammar
$$S\to aS\mid b\,,$$
we have
$$S\Rightarrow aS\Rightarrow aaS\Rightarrow aab\,,$$
so we can write $S\Rightarrow^*aab$. In this case, $\ell=4$, $C_1=S$, $C_2=aS$, $C_3=aaS$ and $C_4=aab$.  Since $\ell\geq 2$, we can also say $S\Rightarrow^+ aab$. We can also write $S\Rightarrow^*S$, which is $\ell=1$, $C_1=S$; but we can't write $S\Rightarrow^+S$, because any positive number of productions from $S$ will give a string with at least one terminal symbol in it.


Classifier optimization Suppose we have a set E of entities. Each entity is described by a set P of binary properties (i.e. each element e of E has a defined true/false value for each element p of P).

|P| >> |E|

We now want to select a subset of fixed size (e.g., 10) of P that will enable us distinguish the elements in E as accurately as possible.

In extensions of this basic scenario, the properties could assume numeric values.

Has this problem been studied? Under what name?

A practical example: there is a set of 100 bacterial species that are characterized for the presence or absence of 1000 genes. We now want to select a subset of 10 genes that, upon typing of a novel sample, will tell us which bacterial species that sample represents.

If you need the optimal answer, the best solution I know is exhaustive search: try all ${|P| \choose 10}$ different subsets, and see which is best.  The running time of this will be $O(|P|^{10})$, though, which is probably too high to be feasible.

Given this, you will probably need to accept solutions that are heuristics or not guaranteed to give an absolutely optimal answer.

One standard approach is to use a greedy algorithm: you iteratively build up a set of properties, one by one.  At each step, if your set is currently $S$, you choose the property $p$ that makes $S \cup \{p\}$ as accurate as possible, and then add $p$ to $S$.  To turn this into a full algorithm, you need to decide how you want to measure/evaluate each candidate $S \cup \{p\}$.

For comparison, you can look also at the ID3 algorithm.  Rather than trying to pick a set of size 10, it tries to pick a decision tree of depth 10, so it's not solving exactly the same problem: but it is similar.  The metric used at each step to evaluate the candidates is the information gain; you could do the same, but for a set rather than a tree.

In the machine learning literature, there is a lot of work on feature selection: given a large number of possible features, the goal is to pick a subset of the features that makes the classifier as accurate as possible.  You could explore that literature and see if any of those methods are effective in your domain.


How best to allocate stock buys and sells when using specific id to maximize long term capital gains Setting aside the fact that tax lots (using specific id) should usually be assigned at the time of the trade (for stocks in the USA), let's assume instead we want an algorithm to optimally allocate them once we have the whole list of trades in hand for a single security. Each trade comprises: date-time, number-of-shares, total-dollar-amount and can be either buy or sell.
Our goal is to maximize the capital gains allocated to long term rather than short term, defined when a matching buy and sell are more than a year apart. A capital gain is the proceeds from the sale of the shares less the cost of those shares.
Example:
Buys
100 shares on Jan 01 2020 total cost \$100
200 shares on Aug 01 2020 total cost \$125
Sells
150 shares on Sep 01 2020 total proceeds \$110
150 shares on Mar 01 2021 total proceeds \$185
Total capital gain is \$(185+110-125-100) ie. \$70 which will be partly short term and partly long term such that short term capital gains + long term capital gains = \$70.
What's the optimal algorithm to allocate tax lots when doing it in retrospect, ie.
What is a general algorithm identifying which share purchase to match to each share sold in order to maximize the long term capital gain portion?
So output might be something like, for the 150 shares sold on 9/1/2020, 100 should come from the first buy, 50 from the second buy. For the 150 sold on 3/1/2021, all 150 come from the 2nd buy.

There's a natural greedy algorithm.  Scan through the buy/sell orders in chronological order.  At each sell order:

Sell as many shares that would be classified as long-term as possible, until you've sold the number required by the sell order.

If you still need to sell more shares, and there are no more shares that would be classified long-term sales, sell the youngest (newest / most recently bought) shares first.

I suggest trying to verify whether that leads to a correct algorithm or not.  See How to prove greedy algorithm is correct.


Heuristics for an Artificial Intelligence problem Problem : Given a (one dimensional) row containing $2N$ tiles arranged in $2N + 1$ spaces. There are $N$ black tiles (B), $N$ white tiles (W), and a single empty space. The tiles are initially in an arbitrary ordering. Our goal is to arrange the tiles such that all white tiles are positioned to the left of the black ones, and one black tile is in the rightmost position. The goal position of the empty space is not specified.
   Tiles can be moved to the empty space when the empty space is at most $N$ cells away. Hence there are at most $2N$ legal moves from each state. The cost of each move is the distance between the tile and the empty space to which it moves ($1$ to $N$).

So I am doing this problem with A* search algorithm with different heuristics(ofcourse admissible).So can anybody suggest me some heuristics.
Thanks

All white tiles must be moved all the way to the left.  Call the left most position 0.  Then, in the final position, the sum of white distances from the axis is 0+1+...(N - 1).

Calculate this value, the "solution distance" of the tiles up front.  As a heuristic, add the zero-based positions of white tiles up, and subtract from this sum the "solution distance" calculated a priori.

This heuristic gives you a minimal cost of finding a solution (eg. it will cost at least that much to get all white tiles in the correct place).


Algorithm for deciding alpha-equivalence of terms in languages with bindings I am interested in the alpha equivalence relation in languages with variable bindings, such as:

t := x:y    'x belong to y'
  | bot     'False'
  | t -> t  'implication'
  | Ax.t    'forall x, t'

Or the pure lambda calculus:

t := x       'variable'
  | (t t)    'application '
  | Lx.t     'abstraction: \x -> t'

I am looking for an algorithm allowing me to determine whether two terms of the language are alpha-equivalent or not. Any published reference is very welcome too. I am assuming a data representation of the terms as a standard
recursive type, for example in Haskell:

newtype Var = Var Int
data Term = Belong Var Var
          | Bot
          | Imply Term Term
          | Forall Var Term

There are several ways to do what you want. One of them is to use a different syntax representation under which $\alpha$-equivalent terms are actually equal. Such representations go under the name nameless or locally nameless syntax. A popular one uses de Bruijn indices. See my blog posts How to implement dependent type theory I, II and III for a blitz introduction to implementing this sort of thing (part III has de Bruijn indices explained).

If you insist on your representation, then we may still secretly use de Bruijn indices, as follows. As we descend inside a subterm during comparison, we keep a list of pairs of bound variables so far encountered. For example, when comparing Forall x1 e1 and Forall x2 e2, we add the pair (x1, x2) to the list and recursively compare e1 and e2. When asked to compare variables x and y, we search down the list: either they must both appear in the same spot (they were bound by the same quantifier) or neither appears and they are equal (they are both free and they are equal).

I am not well-versed with Haskell, but you'd get something like this:

newtype Var = Var Int deriving Eq

data Term = Belong Var Var
          | Bot
          | Imply Term Term
          | Forall Var Term

equalVar :: [(Var,Var)] -> Var -> Var -> Bool
equalVar [] x y = (x == y)
equalVar ((x,y):bound) z w = (x == z && y == w) || (x /= z && y /= w && equalVar bound z w)

equal' :: [(Var, Var)] -> Term -> Term -> Bool
equal' bound (Belong x1 y1) (Belong x2 y2) = (equalVar bound x1 x2 && equalVar bound y1 y2)
equal' bound Bot Bot = True
equal' bound (Imply u1 v1) (Imply u2 v2) = equal' bound u1 u2 && equal' bound v1 v2
equal' bound (Forall x u) (Forall y v) = equal' ((x,y):bound) u v
equal' _ _ _ = False

equal :: Term -> Term -> Bool
equal e1 e2 = equal' [] e1 e2


How to remove empty strings a.k.a (lambda, epsilon) from a LR(0) grammar Say I have the following grammar:

E  -> TE'
E' -> +TE'| -TE' | λ
T  -> (E) |  id

I need to build the finite state machine with the LR(0) items,

But I know in order to do this I have to remove the λ.

How to I accomplish this ?

Also, after I have the SLR(1) table, how to  I prove is valid ?

Thanks, I'm studying for an exam, and I'm stuck here :(

Find all nullable variables. In this case only E' is nullable.
Let me illustrate the second step with an example:

Replace a production A -> BCD with a family of productions like this (assuming B, C & D are nullable):

A -> BCD | BC | BD | CD | B | C | D

Delete all the productions with the empty string as the right-hand side.

With all that in mind we get:

E  -> TE' | T
E' -> +TE'| -TE' | +T | -T
T  -> (E) |  id


How do you read this context-free language? say you want to make a Pushdown Automaton to recognize this language.

What exactly does the +1 mean? I see in the example it just pushes an a to the stack before arriving at an acceptance state but I don't quite get why.

The language defined as $\{a^ib^j\mid 2i=3j+1\}$ is just the set of all strings of $i$ copies of $a$ followed by $j$ copies of $b$, where $2i=3j+1$. Trying various values of $i$ and $j$ and realizing that both $i$ and $j$ must be integers, we see that the admissible solutions are
$$
(i,j)=(2, 1), (5, 3), (8, 5), (11, 7), \dotsc
$$
For example, with $i=5, j=3$ we see that $2i=2(5) =10=3(3)+1=3j+1$. The corresponding strings are
$$
aab,\quad a^5b^3,\quad a^8b^5,\quad a^{11}b^7 \dotsc
$$
and so on.

With a bit of thought, we can make a PDA for this language by pushing two $a$ markers on the stack for each $a$ we read and then popping off three $a$s for each $b$ we see. If we wind up with a single $a$ on the stack after having read all the $b$s, we pop that off and go to the accept state.

It's worth noting that the PDA you picture does not accept the language described. That one accepts the language $\{a^nb^{2n-1}\mid n>0\}$.


T(n) = 2T (sqrt(n))+ log n Recurrence I am aware that the question is asked before but i there is still a confusing part for me.

In book the solution is like that:

$T(n) = 2T(\sqrt{n}) + \log(n)$
$m = \log n$ yields
$T(2^m) = 2T(2^{m/2}) + m$
Then $S(m) = T(2^m)$ produces the recurrence:
$S(m) = 2S(m/2) + m$
So $T(n) = T(2^m) = S(m) = O(m\log m) = O(\log n (\log {\log n}))$

But i can't understand in part $5$, how $2T(2^{m/2})$ is converted to $2S(2m/2)$ ? If $S(m)$ is $T(2^m)$, then $S(m/2)$ must be $T(2^{m-1})$? Can you verify me that why the book's solution is correct, and i am wrong?

We define $S(m)$ to be $T(2^m)$, for every possible value of $m$. Changing the name of the variable, $S(M) = T(2^M)$ for every value of $M$. Substituting $M := m/2$, we get $S(m/2) = T(2^{m/2})$.

As an example, suppose that $T$ is the identity function: $T(n) = n$. We define $S(m) = T(2^m) = 2^m$. Then $S(m/2) = 2^{m/2}$.


LL(1) and LR(0) Grammars The value in the parenthesis of language expressions signify how many next symbols are needed to make a decision.

For example, without reading a symbol from the input, we cannot decide in LL(1) grammars which rule must be applied for derivation.

In this point, Some thought like that occurs: we can make a decision without reading a symbol from the input in LR(0) grammars for specific derivation.

However, I do not think like that, because we always need an input character in LR(0) parsers. We decide to apply shift or reduce operation by regarding next input symbol. In this case, why is it regarded as LR(0) ?

The question to be answered in an $LR(k)$ parse is "has the parse reached the end of a production?" (And if so, which production?)

If we are at the end of a production, we choose a reduce action. Otherwise, we shift the next input whatever it is.

So it should be clear that there are grammars which can be parsed without any lookahead; they are grammars in which no right-hand side is a prefix of a different right-hand side.


If I'm just trying to show something is NP-hard (as opposed to NP-complete) does my reduction need to be completed in polynomial time? I have a problem that I believe is NP-hard. If I reduce a NP-complete problem to it in exponential time (and not polynomial time), does that prove the problem is NP-hard?

Hardness/completeness is always defined with respect to a specific kind of reduction.

Using exponential-time reductions doens't work at all, because that means your reduction is even more powerful than the thing you're reducing to.*
Every language except $\emptyset$ and $\Sigma^*$ is NP-hard under exponential-time reductions. To see this, let $L$ be any language except $\emptyset$ and $\Sigma^*$, and let $X$ be in NP.  We can reduce $X$ to $L$ as follows. Fix two strings $w_{\mathrm{yes}}\in L$ and $w_{\mathrm{no}}\notin L$. Now, given a string $x$, we can determine in exponential time if $x\in X$. If it is, the reduction maps $x\mapsto w_{\mathrm{yes}}$; otherwise, it maps $x\mapsto w_{\mathrm{no}}$.

* OK, technically, we don't know that EXP is more powerful than NP, but it's certainly at least as powerful, and probably more powerful.


Converting $\beta$-bit integer to a decimal representation in $\Theta(M(\beta) \log \beta)$ The following problem is from CLRS (31.1-13, Page 933, 3rd edition):

  Give an efficient algorithm to convert a given $\beta$-bit (binary) integer to a decimal representation. Argue that if multiplication or division of integers whose length is at most $\beta$ takes time $M(\beta)$, then we can convert binary to decimal in time $Θ(M(\beta)\log \beta)$. (Hint: Use a divide-and-conquer approach, obtaining the top and bottom halves of the result with separate recursions.)

By a simple divide and conquer (by dividing $\beta$-bit integer into two $\beta/2$-bit integers), I obtain the recurrence $T(\beta) = 2T(\beta/2) + M(\beta)$. However, how to argue that it is $O(M(\beta) \log \beta)$?

My attempt: I think the result relies on $M(\beta)$. If $M(\beta) = \Theta(\beta)$, then $T(\beta) = \Theta(M(\beta)\log \beta)$. But, if, for example, $M(\beta) = o(\beta)$ or $M(\beta) = \omega(\beta^2)$, you may not obtain $T(\beta) = \Theta(M(\beta)\log \beta)$.

According to the hint, it seems that we should use different recursions to obtain $O(M(\beta)\log \beta)$ and $\Omega(M(\beta) \log \beta)$, respectively. But how?

If we take $M(\beta) = \log \beta$ we can disprove the assignment's claim (assuming base 2 $\log$).

\begin{align*}
T(\beta) &= 2T(\beta/2) + M(\beta)&\text{given}\\
T(\beta) &= 2T(\beta/2) + \log \beta&\text{given (1)}\\
T(\beta) &= 2\beta - \log (\beta) - 2&\text{inductive hypothesis (2)}\\
T(\beta) &= 2(2\beta/2 - \log (\beta/2) - 2) + \log \beta&\text{substitute (2) into (1)}\\
T(\beta) &= 2\beta - 2(\log (\beta) - 1) - 4 + \log \beta&\text{algebra}\\
T(\beta) &= 2\beta - \log (\beta) -2&\text{QED}\\
\end{align*}

So we've proven that if $M(\beta) = \log \beta$ then $T(\beta) = O(\beta)$. However the assignment claims $O(T(\beta)) = M(\beta)\log \beta = \log^2 \beta$. This cannot be true.

If we read between the lines it seems implied that $M = Ω(\beta)$.


Running time function for an algorithm with while and for loop I have trouble determining the running time function for algorithm below. I know that there are initially two assignment operations, int i=n and int s=0.

Also, I know that the while loop is represented by $\lfloor \log_2n \rfloor + 1$, but the for loop depends on the value of $i$ which decrements by half.

So, the first time the for loop performs $n$ times, the second time the for loop performs $n/2$ times, and so on. How can I represent this behavior?

I suppose that, at the end, the result is the product of both behaviors.

int i = n; int s = 0;
while(i > 0) {
    for(j = 1; j <= i; ++j) s++;
    i /= 2;
}

For each value of $i$, the inner loop runs $i$ times, and so the running time of the body of the outer loop with a given value i is in $\Theta(i)$. The values of i, as you mention, are $n, \lfloor n/2 \rfloor, \lfloor n/4 \rfloor, \cdots, 1$, and so the overall running time is
$$ \Theta(n + n/2 + n/4 + \cdots + 1) = \Theta(n). $$
Here we use the fact that the infinite series $1 + 1/2 + 1/4 + \cdots$ converges (to $2$).


Write down a DFA for the regular expression (000* + 111*)* and explain why it cannot have lesser number of states So, I came up with a DFA for the regular expression. Now for every string described by the regular expression, the DFA accepts it. But in order to ascertain if it's really a DFA for the regex, you also need to know whether the reverse is true or not. Which is to say that the set of strings accepted by the DFA is described by the regex. I have no idea how to know if this is the case or not.

Could you guys tell me how to be sure if the DFA really recognizes the language described by the regex (000* + 111*)*

You state two questions.

(1) You are convinced that all the strings decribed by the RegEx are accepted by the DFA. In order to conclude equality you want to know the converse. Is every string accepted by the DFA also described by the RegEx? To do this, try to argue that every string accepted by the DFA consists of "blocks" of each time at least two the same letter. This is not very dificult: the states of the DFA here "count" symbols $0$ and $1$.

(2) In the title of the question you ask whether the number of states is minimal. This can be done by arguing the no states can be merged. This can be shown by giving for each pair of states a string that "distinguishes" the states: states $p$ and $q$ are distinguished if there is a string $w$ such that $w$ from one of $p$ and $q$ reaches an accepting state, while it does not reach an accepting state from the other.
Here this can be done by looking at most one letter ahead: can be reach an accepting state by $\lambda$, $0$ or $1$? For each of the six staes the answers are different.


To show that a graph-problem is in $L$ or $NL$ Consider the following problem:

$$A=\left\{ (G(V,E),s,t)\mid\text{conditions 1, 2, 3 and 4 hold} \right\}$$

$G$ is a directed graph.
$s,t\in V$.
There is a simple path from $s$ to $t$ (a simple path is a path that visits every vertex not more than once).
$\forall v\in V: \deg^+(v)\leq 2$ (in words: every vertex in $V$ has outdegree at most 2).

Out of the following classes: $\mathsf{L,NL,P,NP,co-NP,EXP}$, I need to determine what is the smallest class (with respect to inclusion) that has $A$ in it.

My idea is: since every vertex has outdegree at most 2, I can write a function $F$, s.t for every $v\in V$ I'll recursively call $F$ with the two adjacent vertices of $v$.

The termination condition will be either if $\deg^+(v)=0$ (we've reached a leaf node) or $v$ has alredy been visited (this will make sure the path is simple) or $v=t$ (we've found a path to $t$), thus concluding that $A\in P$ (the complexity of the described algorithm is $n\log n$).

I'm just not sure if that is the best that can be done. Can it be shown that $A$ is in $\mathsf{L}$ or $\mathsf{NL}$?

The problem is NL-complete.

The fact that it's in NL, as stated in the comments, follows from the fact that this problem is a restriction of the reachability problem for directed graphs.

To see that it's NL-hard, we can reduce from the reachability problem:

Consider a graph $G=(V,E)$ and vertices $s,t$. We transform $G$ to a graph $G'$ with out degree at most $2$, as follows.

For every vertex $v$ with out-neighbors $u_1,...,u_k$ ($k\ge 3$), construct vertices $v_1,...,v_{k-1}$ where there are edges from $v_i$ to $u_i$ and to $v_{i+1}$. The incoming edges to $v$ are now directed to $v_1$, and $v$ is removed.

It is not hard to see that there is a path from $s$ to $t$ in $G$ iff there is a path from $s_1$ to $t_1$ in $G'$. Also, this reduction can be implemented in log-space. Thus, your problem is NL-complete.