An algorithm for a minimization problem, How to minimize the wasted length of combination of multiple items with different length and number Suppose there is an unlimited number of pipes, each has length $x$ meters.
There is a list of requirements of pipes with shorter length than $x$. The number of these items are also given.

For example we need to have $n_1$ pipes of length $x_1$,$n_2$ pipes of length $x_2$,..., $n_k$ pipes of length $x_k$ $\forall i, x_i \leq x$.

We need to cut the pipes of length $x$ such that the requirements to be fulfilled and also minimize the number of the used pipes.

For example for $x = 12$ and $$item1: x_1=3,n_1=50$$ $$item2: x_2=5,n_2=30$$ $$item3: x_3=7,n_3=80$$$$item4: x_4=2,n_4=90$$$$item5: x_5=9,n_5=15$$

we can cut the pipes in multiple ways. The worst solution is to allocate one pipe for each requirement, in this way the number of used pipes will be $$\sum_{i=1}^{i=k}{n_i} = 265$$

But by combining item2 and item3 into one pipe, we can reduce $256$ by $30$. In this way item2 is prepared then we can combine item1, item3 and item4 to prepare the items and use the minimum number of the pipes.

As another solution we can also combine item5 and item1, or even allocate one pipe of length $12$ for $4$ pipes of item1

I would like to know is this a famous problem? and is there any efficient algorithm for it?

 My Solutions

Solution 1

Because I really don't know what the class of this problem is, I tried to solve this problem using the approximation algorithm given for the Set Cover problem.

The items form the set of elements, and any combination of items where the summation of their $x_i$ is less than or equal to $x$ is a valid set and its cost equals to $$cost(set_i) = x-\sum_{item_j \in set_i}{x_j} $$

But in set cover problem an element may appear in multiple sets while in this problem such thing is not reasonable. Besides that the $n_i$s are different that is why the Set Cover solution is not working here.

Solution 2

My second solution is a simple greedy algorithm. First I create set of valid sets as explained in the Solution 1, select the one with minimum cost. In this way at least one item with the minimum $n_i$ is produced.

In the second step, first I need to update $n_i$s (because some items are produced in the previous step) and remove the completely covered item from the list. If $set_j$ was the set with minimum cost, Then there will be a few pipes with the length $$wasted= x - \sum_{item_k \in set_j}{x_k}$$.

For the remaining items in the list, if there is anyway to form elements in a set such that sum of their $x_i$ is less than or equal to $wasted$ then we produce those pipes, else we should repeat from the first step with the new list.

Take a look to knapsack problem.

Simple algorithm (not the optimal solution)

order the item descending
cut the n5/(x\x5) ("\" is integer division, i.e. 12\9=1) = 15 pipes to satisfy x5 = 9m and partially x1

Repeat step 2 for x3 = 7m and so on.


Optimization Problem when calculating fitness is expensive I need to solve an optimization problem, maximizing fitness in a set of around 1 million solutions. Calculating the fitness of any solution is very time consuming, taking around 5 minutes. Therefore, I am only able to calculate the fitness of 100 solutions per run. Each solution is represented by vector in ten dimensions with real values [0..1], such that two similar vectors represent similar solutions and should have similar fitness.

Obviously I have no expectation of finding a solution that is anywhere near optimal, but is there a preferred method for AI search when you're only able to test the fitness of very few solutions? I get the feeling that I'm missing one or two keywords that would point my search in the right direction.

I'm considering calculus-based search as one option, as it's better to find a local maxima than just randomly search the space and not find any good solutions whatsoever.

For starters I assume that you can't guess the impact the values of a solution have on its fitness, otherwise you could relax the fitness function to roughly estimate which solutions are promising, and try to find a good solution from there.

However you do know that similar solutions have a similar fitness, so let's work with that. I would suggest something along these lines:

Construct a function to measure the similarity of two solutions.
Using this function, heuristically group your solutions into 100 clusters.
For each cluster, calculate the fitness of the solution closest to its mean.

This will give you the fitness of the 100 most dissimilar solutions, which is a good sample of your search space (it should give you a good idea of the fitness found in most major peaks). As a bonus, you can recursively do this if you want to improve on the best solution found, i.e., divide the best cluster into k clusters and proceed in the same way.


Are turing machine really countable? I feel the notion "there are countably many Turing machines" is wrong.
Suppose there is a Turing machine whose input alphabet is {0}. If we replace the input alphabet {0} with {a} and replace every occurrence of "0" with "a" in the transition table, then we get another Turing machine. Obviously, these two machines are different beacause they recognize different languages, but using any one reasonable encoding sheme, they could be encoded into the same string. So claiming Turing machines are countable only by enumerating their encodings is wrong, because actually there isn't a bijection between Turing machines and their encodings.
Is my opinion right?

You are technically right. The correct phrasing should be that there are countably many TMs up to isomorphism of the tape alphabet and the state-space.

Indeed, if you say that a TM with states $\{q,r\}$ is different than the same TM with states named $\{1,2\}$, then not only are TMs not a countable collection, they are not even a set in the ZFC axiom system.
This follows from the fact that the collection of all sets is not a set itself.


How do I arrive at the multiplication function in lambda calculus? I'm familiar with how Church numerals are defined in the lambda calculus, i.e. as functions that take two arguments and apply the first argument $n$ times to the second.

Then I have the successor and addition functions, both of which I managed to derive and understand:

$$\begin{align}
\mathrm{succ} &:= \lambda nsz.s (n s z) \\
(+) &:= \lambda nm.n\ succ\ m \\
\end{align} $$

But multiplication is where I'm stuck.

I understand that we can define a multiplication function $(*)$ by adding the number $m$ to $0$ exactly $n$ times. After all, $3 \times 2$ is simply $2 + 2 + 2 + 0$.

So that could mean that $(*)$ looks like this:

$$(*) := \lambda nm.n\ ((+)\ m)\ 0$$

This appears to be a somewhat intuitive definition of a lambda calculus multiplication function to me, and if I try it out with $2$ and $3$, after some messy reductions, the result seems correct and $(*)\,2\,3 \rightarrow 6$.

But then elsewhere I found this definition for multiplication:

$$\mathrm{mult} := \lambda xya.x (y a)$$

Now I don't see how you arrive at this function $\mathrm{mult}$. My definition $(*)$, which takes two arguments, seems intuitive enough to me. But his here, which takes two arguments, one for the $x$ and $y$ respectively, which are the numbers to be multiplied, and then a third one $a$, just seems impenetrable to me—and I cannot figure out why it works, or how you would derive it.

Can somebody help me understand the reasoning and derivation of this $\mathrm{mult}$ function?

You know that $(\bar{n}\ s)$ corresponds to $s^{(n)}$, i.e. function $s$ applied $n$ times to its argument. You want to obtain a function that iterates some function $s$ exactly $n \cdot m$ times. From the above observations and some simple rules for the composition of functions we can immediately derive the body of $\textsf{mult}$:

$$s ^ {(n \cdot m)} =
\left( s ^ {(m)} \right) ^ {(n)} =
\bar{n} \left(s ^ {(m)} \right) =
\bar{n}\ (\bar{m}\ s)
$$

Hence

$$ \textsf{mult}\ :=\ \overbrace{\lambda n m.}^\text{  parameters}\underbrace{(\lambda sz.n\ (m\ s) z)}_{\text{Church numeral}}$$

or, if we $\eta$-contract, we get

$$ \textsf{mult}\ :=\ \lambda nms.n\ (m\ s)$$


Lower bound for Merge Sort running time I'm trying to prove that the recurrence $T(n)=2T(\left \lfloor \frac{n}{2} \right \rfloor) + n$ is in $\Omega(n \log_2 n)$.

Here's my attempt: Suppose there is some $c>0$ and a positive integer $n_0$ such that $n_0 \le k < n \implies T(k) \ge ck \log_2 k$.

Then

$$\begin{eqnarray*}
T(n) &=& 2T(\left \lfloor \frac{n}{2} \right \rfloor) + n \\
&\ge& 2c \left \lfloor \frac{n}{2} \right \rfloor \log_2 \left \lfloor \frac{n}{2} \right \rfloor + n \\
&\ge& 2c \left ( \frac{n - 1}{2} \right ) \log_2 \left ( \frac{n - 1}{2} \right ) + n \\
&=& c(n - 1) \log_2(n - 1) - c(n - 1) + n \\
&=& cn \log_2(n-1) - c \log_2(n-1) - c(n - 1) + n \\
&=& cn \log_2 \left [ n \left ( 1 - \frac{1}{n} \right ) \right ] - c \log_2(n-1) - c(n - 1) + n \\
&=& cn \log_2 n + cn \log_2 \left ( 1 - \frac{1}{n} \right ) - c \log_2(n-1) - c(n - 1) + n.
\end{eqnarray*}$$

I can't determine if there is a $c > 0$ such that $cn \log_2 \left ( 1 - \frac{1}{n} \right ) - c \log_2(n-1) - c(n - 1) + n$ is non-negative for $n$ large enough.

Also, I think this approach is too complicated given how easy it is to prove $T(n)=O(n \log_2 n)$. Am I missing some obvious estimate here?

Any help is welcome. Thanks.

$c=\frac{1}{2}$ is enough for large enough $n$.

Indeed, there are positive integers $n_1$ and $n_2$ such that

$$\begin{eqnarray*}
n &\ge& n_1 \implies -\frac{1}{2} < \log_2 \left ( 1 - \frac{1}{n} \right ) \\
n &\ge& n_2 \implies -\frac{1}{2} < -\frac{1}{n} \log_2 (n - 1).
\end{eqnarray*}$$

Rewriting $$cn \log_2 \left ( 1 - \frac{1}{n} \right ) - c \log_2(n-1) - c(n - 1) + n$$

as

$$
cn \left [ \log_2 \left ( 1 - \frac{1}{n} \right ) - \frac{1}{n} \log_2(n-1) + \frac{1}{n} - 1 + \frac{1}{c} \right ],
$$

we have

$$n \ge \max(n_1, n_2) \implies -2 + \frac{1}{c} < \log_2 \left ( 1 - \frac{1}{n} \right ) - \frac{1}{n} \log_2(n-1) + \frac{1}{n} - 1 + \frac{1}{c}.$$

But $-2 + \frac{1}{c} \ge 0 \iff c \le \frac{1}{2}$.


Algorithm to compare two data sets I have two data sets of a particular structure:
User 1:
  Salad1: Tuna, Mayo, Lettuce
  ...
  Breakfast1: Egg, Avocado, Toast

User 2:
  Salad1: Tuna, Mayo
  ...
  Breakfast1: Egg, Toast, Sausage

There are thousands of dishes, and the goal is to ensure that all the ingredients from User 1 dish are present in the corresponding recipe of User 2 data set.
We can't overwrite the recipe in User 2 data set, removing their additions - we only need to ensure that the ingredients from the corresponding User 1 dishes are present, and add them in if they are absent.
My solution:
Create a list of hashes for each recipe from each User:
Salad1|Tuna~Mayo~Lettuce
Breakfast1|Egg~Avocado~Toast

Perform a 'difference' operation on the two string arrays and end up with a list of those recipies that don't match. Break away the dish identifier from each resulting string, find the dish in the second data set and append the missing ingridient.
Benefits of my solution
As you can see, once we add the 'Lettuce' to the Salad1 recipe of User2, the relevant dish will stop coming up in the 'Difference of hashes' output, and the consequent synchronisations will take much less time.
Problems with my solution
Sadly, the Breakfast1 recipe of User2 will keep flagging up the difference even after we add the 'Toast' entry to it, because here the user has added 'Sausage' to the list.
This way, if User2 chooses to add a 'special ingridient' to each recipe we will end up evaluating every single dish in his database for having ingridients of the corresponding dish in User1 data set.
Essentially: my approach reduces the amount of individual dishes that I need to evaluate (iterate over ingridients to see if the ingridients from the User1 dataset are present), but I still need to evaluate those where extra ingridients were added.
The challenge
Is there any established algorithm that would take the two datasets above, and return only 'dishes' from the second data set that need 'ingridients' added to them?

I think you are asking about how to implement a set difference operation. Specifically, if user 1's recipe for salad 1 is viewed as a set of ingredients A, and user 2's recipe for salad 1 is viewed as a set of ingredients B, then the the set difference A \ B is exactly the set of ingredients that are in A but not in B.
One well-known and particularly simple algorithm goes like this:

Sort each list of ingredients (let's say in ascending order).
At the start, the first element of each list is the current element.
Repeatedly compare the current elements of the lists. Calling the current elements of A and B by the names a and b, respectively, there are three cases:

a < b Ingredient a is in A and not in B, so make a note of it. Advance the current element for A, but keep the same current element in B.
a = b Ingredient a is in both, so nothing special need be done. Advance both current elements.
a > b Ingredient b is in B and not in A. We don't need to do anything special to rectify this situation. Advance the current element in B.

When you reach the end of both sorted lists, you will have a record of the ingredients that must be added to B's recipe.
There are more complicated algorithms that exploit the fact that strings support more interesting observations than just comparison, or which can take advantage of situations where there's only a small collection of possible ingredients, but I recommend you start here until you're confident that this algorithm doesn't meet your performance needs.


Are the undecidable languages closed under complement? Are the undecidable languages closed under complement?
How can the answer be proved?

Suppose you could decide the complement. Wouldn't you then be able to decide the language itself?


Is EXPTIME "solvable" or "checkable" in exponential time? According to this video, EXP has problems that are exponentially difficult to check.

But according to this video, EXP are problems that are exponentially difficult to solve.

It would make sense to me, that if EXP contains problems that are exponentially difficult to check, that they would contain problems that are harder than NP-complete ones.

However, if it's true that EXP is problems that are just solvable in exponential time, why wouldn't they be equal? Wouldn't EXP therefore be a subset of NP (and so would R), as problems that are harder (like R) are still solvable in "non-deterministic" time? Because the term "non-deterministic" extends to any finite amount of time, correct?

Thank you in advance for resolving my confusion. If you could explain it as simply as possible, I would appreciate it, as I get easily bogged down by the set theory.

A language $L$ belongs to $\mathsf{EXPTIME}$ if there is an algorithm deciding it which runs in time $O(2^{n^k})$ for some $k$.

A language $L$ belongs to $\mathsf{NEXPTIME}$ if there is an algorithm verifying it which runs in time $O(2^{n^k})$ for some $k$. In other words, a language $L$ belongs to $\mathsf{NEXPTIME}$ if there is a constant $k$ and a machine $M$ running in time $O(2^{n^k})$ such that $x \in L$ iff there exists $y$ of size at most $O(2^{|x|^k})$ such that $M(x,y) = 1$. Alternatively, a language $L$ belongs to $\mathsf{NEXPTIME}$ if it can be decided in nondeterministic time $O(2^{n^k})$ for some $k$.

You observe correctly that every problem in $\mathsf{NP}$ has an $\mathsf{EXPTIME}$ algorithm, that just goes over all possible witnesses. This shows that $\mathsf{NP} \subseteq \mathsf{EXPTIME}$. It is conjectured that the two classes are distinct. In contrast, it is believed that $\mathsf{EXPTIME} \neq \mathsf{NEXPTIME}$, and this is stronger than (i.e., implies) the more famous conjecture $\mathsf{P} \neq \mathsf{NP}$, through a padding argument.

Note that nondeterministic computation can still be time-bounded. For example, $\mathsf{NP}$ is the class of languages computed by nondeterministic polytime algorithms. The nondeterministic time hierarchy theorem shows that $\mathsf{NP} \neq \mathsf{NEXPTIME}$; similarly, the deterministic time hierarchy theorem shows that $\mathsf{P} \neq \mathsf{EXPTIME}$.


Transform a set of points to have a minimum distance between them Assume I have a set of $N$ ordered points, $X$. I would like to find the set of $N$ points, $Y$, where the distance between $X$ and $Y$ $(d = \sum_{i=0}^{N-1} |X_i - Y_i| )$ is minimized but there is a minimum distance between points of $M$ $(Y_{i+1} - Y_i > M)$. Is there an algorithm or approach to deriving $Y$ given $X$ and $M$?

Using log-barrier constraints (suggestion from the comments) along with a Nelder-Mead simplex approach got fantastic results.
As clarification to some of the other comments, the points were in Euclidean space comprised of real numbers.


P and polynomial sized circuits What can we say about decision problems having a polynomial time algorithm, ie, in $P$? Do they always have polynomial sized circuits (but not circuits of polynomial depth)?

Yes. $P \subseteq P/\text{poly}$.  In particular, every polynomial-time algorithm can be simulated by a family of polynomial-sized circuits: the circuit just emulates the behavior of the algorithm.  That this is possible should be pretty clear from the fact that we execute algorithm on CPUs, which are themselves complex circuits built of gates, so it's perhaps not surprising that you can emulate the algorithm in a circuit whose size is not too much larger than the running time of the algorithm.  See, e.g., Why does a polynomial-time language have a polynomial-sized circuit?, https://cstheory.stackexchange.com/q/6721/5038, Why isn't P and P/poly trivially the same?, https://en.wikipedia.org/wiki/P/poly, How to relate circuit size to the running time of Turing machine.


Why line graph is a proper subclass of claw-free graph? A claw is the graph isomorphic to $K_{1,3}$, that is, a star graph with three edges, three leaves, and one central vertex. (see below)

A graph is claw-free if it does not contain a claw as an induced subgraph.

The line graph of G is the intersection graph of the edges of G, that represents the adjacencies between edges of G.

A graph $F$ is a line graph if there exists a graph $H$ such that $L(H) = F$.

My question is why are line graphs a subclass of claw-free graphs??
Thanks a lot!

Your question is answered on Wikipedia:

  "Line graphs may be characterized in terms of nine forbidden subgraphs;[2] the claw is the simplest of these nine graphs."

The reference is to the following paper:

  [2] Beineke, L. W. (1968), "Derived graphs of digraphs", in Sachs, H.; Voss, H.-J.; Walter, H.-J., Beiträge zur Graphentheorie, Leipzig: Teubner, pp. 17–33.

Wikipedia contains a pictorial description of these nine graphs. One of them is $K_5^-$, obtained from $K_5$ by removing a single edge.

If you take any of the other forbidden subgraphs then you get a claw-free graph which isn't a line graph.


Maximum number of nodes with height h How is $\frac{n}{2^{h+1}}$ the maximum possible number of nodes at height $h$ for a binary search tree or heap tree? I saw this as proof to asymptotically bound the build_heap function in the book, but I don't get it.

I actually touched upon this in response to your previous question, but the general idea is that there are $n$ nodes in a binary tree, and starting from the root, at each depth there is: 1, 2, 4, 8, 16 ... maximum nodes. We see that at the greatest depth, there is (at most) half of all nodes ($n/2$). Remember that the height of a node is the distance from the node to a leaf, such that the height of a leaf is 0 (and the height of the root is the height of the tree). So for a leaf, $\frac{n}{2^{0+1}}=n/2$. For the root, $h=\log_2 n$, so $\frac{n}{2^{\log_2 n+1}}=n/n=1$. And the rest of the tree follows from there.


Finding minimum in PRAM model Show that the minimum of $n$ elements stored in an array can be found in a time in $O(\log(n))$ using $O(n/\log(n))$ processors assuming an EREW-PRAM machine is given.

Let us start with a solution using $n$ processors and then we optimize the solution to use $O(n/\log n)$ of them.
Assume first that $n$ is a power of $2$, i.e. $2^k$ for some $k \in \mathbb{Z}$. Imagine a perfect binary tree where the leaves are the elements of the array. In each step we will process one level of the tree in a bottom up manner, where for each node in the tree we will compute the minimum of all elements contained in the leaves of its subtree and write this minimum in the node.

In the first step each node represent one element and hence is the minimum of it self. Now in each further step we go one level up in the tree, half of the processors retire and the other half, each will be responsible for one node. Note that the minimum of leaves in a subtree rooted at some node, is the minimum between the minimum of elements in its right subtree and the minimum of elements in its left subtree. Hence, a processor responsible for a node $M$, it only compares the numbers written on the left child and the right child of this node and write the minimum between them in this node.
When we reach the top of the tree, we will have exactly one processor that will compare the values written in both children of the root and write the minimum of them in the root.

Since the depth of a perfect binary tree of $2^k$ leaves is exactly $k$, the algorithm finishes in $\log n$ steps. Since we started with $n$ processors and the number of used processors kept cutting down, $n$ processors are enough for the whole job.

Now assuming $n$ is not a power of two, then there is a $k$ such that $n < 2^k < 2n$. Try to prove this claim as an exercise. Now using this claim, given an array of $n$ elements, we can use $2n$ processors to build an array of $2^k$ elements in constant time by adding very large numbers to the array (adding numbers equal to the first number of the array suffice since we are looking for the minimum) and run the algorithm as described above.

Now we optimize the number of processors using a preprocessing technique. Assuming we started with $c \cdot n/ \log n$ processors for some constant $c$ (2 is enough here). Let us start by completing the array into a power of two as above and cut the array into chunks, each of size $\log n$. We will have at most $O(n / \log n)$ of them. Each processor can find the minimum in a chunk sequentially in $O(\log n)$ time. Let us build a new array $A'$ of length $O(n / \log n)$, where the processor responsible for the $i$-th chunk writes the minimum in the $i$-th position of the array. We end up with an array of size $O(n / \log n)$ and with $c \cdot n / \log n$ processors we can proceed as above in $O(\log(n/\log n) = O(\log n)$ steps.

In total we get an algorithm with $O(\log n)$ time and $O(n / \log n)$ processors.


What is the initial state of DFA equivalent to an $\epsilon$-NFA? I am unsure I expressed myself correctly.

Anyway, I want to figure out what is the initial state of an automata who had its epsilon transitions removed and who was determinised.

In my text book it is stated, that suppose A is NFA with $\epsilon$-moves, suppose $q_0$ its initial state. Then the initial state of the equivalent DFA is the E-closure of $q_0$.

Yet in one of the softwares recommended by one of my teachers, $\epsilon$-NFA to DFA algorithm  always puts the initial state as $q_0$ and not E-closure($q_0$).

There is no god-given algorithm for converting $\epsilon$-NFAs to DFAs. You can do it in several ways, and the results could well be different. It could be that your textbook's construction and the one in the software are simply different.


Implementing a symbol table with a hash table and a stack I was in class today, in a Language Translations course, thinking about the best way to write a symbol table for a compiler. My professor showed us a hash-table with linked-lists connecting different levels of "blocks", which are usually { } curly brackets in languages such as C.

My thought was, what's wrong with using stacks instead?

For example, here's some code:

int x = 5;
float y = 3;
{
    // stuff
    int x = 100;
}

Would I not be able to start off, hashing x, pushing it onto a stack struct as

struct symbol_def{
    char * type;
    val_type value;
}

I don't know how to do a dynamic type for the value (if the value is even needed in there).

When the second x comes in:

int x = 100;

Then we just again hash x, push onto the stack.

At any given moment, the top of the stacks are the current scope's visibility.

The issue might come with popping however. How do we pop off the right things? That one I'm not entirely sure about, and could be a fatal flaw of this design.

In theory, this would be a lot of O(1) jobs (hash table lookup, pushing, popping, peeking).

Let me know your thoughts. Maybe I'm missing something here, or maybe this is how it's really done already.

A stack of hashtables would be a perfectly fine representation.

A hashtable of stacks wouldn't be a good choice, but a stack of hashtables would work.

When you leave a scope (e.g., the } symbol), you need to pop off all of the symbol names defined in that scope.  That's easy with a stack of hashtables, but a bit more annoying with a hashtable of stacks.

A natural way to represent a stack is as a linked list, so this might turn out to be equivalent to the solution you've already been presented.


Graph find all vertices that are part of a cycle I was wondering how I can find all the vertices in a graph that are part of a cycle. To determine this for one vertex, I could just start a DFS from that vertex, but this seems unefficient to me when I want to know for all vertices.

Thanks for your help!

There is a duplicate question in StackOverflow. I quote the highest voted answer from Craig Gidney here.

  What you want to do is remove all of the Bridges (i.e. edges that disconnect a component when removed). The Wikipedia article gives a linear time algorithm for finding all of the bridges.

  Once all the bridges are gone, each node is either isolated (has degree 0) or is part of a cycle. Throw out the lonely nodes, and what's left is the nodes you want.


Can I have actions that, if taken, cannot be taken again in the following N timesteps? I'm trying to train a load-balancing system with reinforcement-learning (RL) s.t. the incoming jobs are queued evenly at the available servers.
The system will not be able to directly dispatch the jobs, but it will only offer suggestions to use a set of servers over another.
The system will also be capable of reducing the speed at which new jobs arrive and at each time step, to reduce the queue lengths.
The agent must decide whether to change this speed or keep it constant.

Changing the speed at time T, however, disables any other changes until time T+N, with N constant (basically, we need to prevent speed changes at every time-step).

Are these actions an obstacle in training the system?
All RL systems I know only deal with actions that can be taken at every time step and don't put any constraints in future use of the action. Is this a limitation of RL agents?

This is not a limitation.  Which actions are valid can depend on the current state of the system.

To enforce your requirement (changing speed at time T means you can't change again until time T+N), you can add additional information to the state: basically, add how long ago was the last change (where if it's more than N steps ago, you don't keep track of how long, just that it was long enough that a change is now allowed).


Why do black-box deep learning algorithms produce better word similarities than cognitively plausible ones? Why do black-box deep learning algorithms (e.g. Mikolov et al 2013) produce better word similarities than cognitively plausible ones (e.g. Baayen et al 2011)? Could we combine the best of both worlds, biologically motivated learning mechanisms and state-of-the-art performance?

The short answer is that we don't know why current ML algorithms work well on a particular dataset, or why other ML algorithms don't.

Most researchers focus on finding ML algorithms that achieve high accuracy, regardless of how they achieve it.  Cognitive plausibility typically isn't a goal.

Generally, across much of computer science, our best methods often differ from how the brain works.  This is true for machine learning, for computer vision, for playing games like chess, and other tasks.  That could be viewed as an opportunity for improvement and a failure of our methods, or as an indication that the methods that will work best for computers might be different from the ones that our brains have evolved.  We just don't know.


Double hashing - probe count probabilities From TAoCP, Vol. 3 by Knuth we know that expected (mean) probe counts for hash tables with open adressing and double hashing collision-resolution are:

$1 \over 1 - \alpha$ - for unsuccessful search
${1 \over \alpha} ln({1 \over 1 - \alpha})$ - for succesful search

Where $\alpha$ is load factor.

Are there expressions for probabilities of making exactly $i$ = 1,2,3,.. probes?

As Wandering Logic noted, there are approximate expressions for probabilities of probe count in unsuccessful search  case in TAoCP, a few pages later expressions for expected probe count:

$1-\alpha$, $\alpha(1-\alpha)$, $\alpha^2(1-\alpha)$, ... - probabilities of making 1, 2, 3, ... probes respectively.

In successful search case I derived approx. expressions myself, relying on explanation of expected probe count formula in the book:

$1 - {\alpha\over2}$, ${\alpha\over2} - {\alpha^2\over3}$, ${\alpha^2\over3} - {\alpha^3\over4}$, ...


Find the longest path from root to leaf in a tree I have a tree (in the graph theory sense), such as the following example:

This is a directed tree with one starting node (the root) and many ending nodes (the leaves). Each of the edge has a length assigned to it.

My question is, how to find the longest path starting at the root and ending at any of the leaves? The brute-force approach is to check all the root-leaf paths and taking the one with maximal length, but I would prefer a more efficient algorithm if there is one.

Ran G. gave hints towards an efficient algorithm, though perhaps he left out some details. Computing all root-leaf paths is indeed a little inefficient if you are doing work over and over again, for example, if you compute each path and then compute the length.

Perform the following recursive algorithm starting with LongestPath(root) will give
what you want. Essentially, it computes recursively the longest path for each subtree. At each node this requires building the new paths and returning the longest one.

 LongestPath(node)
   If node is a leaf, return (node,0)
   If node is not a leaf:
    For each edge (node,length,next):
       Let (p,l) = LongestPath(next)
       Let (path,len) = (p++[next], l + length)
    Return element (path,len) from previous step with largest value len

This is a combination if pseudo-code with some Haskell notation, so I hope it is comprehensible.


Under which operations is the class of non-recursive languages a closure? I am currently studying turing computability and related problems such as the halting problem with a background in formal languages.

I know that the class of recursive (decidable) languages is a closure under union, intersection and complement, and that recursively enumerable languages (semi-decidable) are a closure under union and intersection, but what about non-recursive (undecidable) languages?

To be more specific, I am trying to prove that a specific language of the form $$L = \{ w \in \Sigma^* : w \in A \lor w \in B \}$$ is non-recursive. I managed to prove that neither $A$ nor $B$ are recursive by reducing them to the universal halting problem, but I am not sure what that implies for $L$.

  The exact language is $$L = \left\{ w\#u \in \left\{ 0, 1, \# \right\}^* | \\ M_w \text{ will halt with input } u \text{ or } M_u \text{ will halt with input } w \right\}$$ where $M_b$ is the turing machine whose transition function $\delta$ is represented using Gödel numbering as a binary string $b$.

Is the class of non-recursive languages a closure under union? If it is, how could I prove it myself or where could I find an existing proof?

Non-recursive languages are closed under complement, but not under union or intersection.

Indeed, a decider for $A$ exists iff there is a decider for $A^c$. Hence the closure under complement.

However, let $B$ be any non-recursive language. $B^c$ is also non-recursive. But $B \cap B^c = \emptyset$ and $B \cup B^c = \Sigma^*$ are both recursive. Hence, non-recursive languages are not closed under union or intersection.

In the example you mention, you can not conclude anything about $L$ from $A,B$ being non recursive.

I will provide a hint for $L$, only. When you have a language of the form $L=\{f(x,y) | x,y\mbox{ s.t. } p(x,y)\}$, it is sometimes convenient to choose a particular value $a$ and study the related language $L_a = \{ y | y\mbox{ s.t. } p(a,y) \}$ first. Maybe one can choose $a$ to make $p(a,y)$ simple enough so that other proof techniques apply.


How to prove that a language is not regular? We learned about the class of regular languages $\mathrm{REG}$. It is characterised by any one concept among regular expressions, finite automata and left-linear grammars, so it is easy to show that a given language is regular.

How do I show the opposite, though? My TA has been adamant that in order to do so, we would have to show for all regular expressions (or for all finite automata, or for all left-linear grammars) that they can not describe the language at hand. This seems like a big task!

I have read about some pumping lemma but it looks really complicated.

This is intended to be a reference question collecting usual proof methods and application examples. See here for the same question on context-free languages.

Proof by contradiction is often used to show that a language is not regular: let $P$ a property true for all regular languages, if your specific language does not verify $P$, then it's not regular.
The following properties can be used:

The pumping lemma, as exemplified in Dave's answer;
Closure properties of regular languages (set operations, concatenation, Kleene star, mirror, homomorphisms);
A regular language has a finite number of prefix equivalence class, Myhill–Nerode theorem.

To prove that a language $L$ is not regular using closure properties, the technique is to combine $L$ with regular languages by operations that preserve regularity in order to obtain a language known to be not regular, e.g., the archetypical language $I= \{ a^n b^n \mid n \in \mathbb{N} \}$.
For instance, let $L= \{a^p b^q \mid p \neq q  \}$. Assume $L$ is regular, as regular languages are closed under complementation so is $L$'s complement $L^c$. Now take the intersection of $L^c$ and $a^\star b^\star$ which is regular, we obtain $I$ which is not regular.

The Myhill–Nerode theorem can be used to prove that $I$ is not regular.
For $p \geq 0 $, $I/a^p= \{ a^{r}b^rb^p\mid r \in \mathbb{N} \}=I.\{b^p\}$. All classes are different and there is a countable infinity of such classes. As a regular language must have a finite number of classes $I$ is not regular.


Joining two red-black trees I have

two red-black trees $T_1$ of black height $H_1$ and $T_2$ of black height $H_2$
such that all the nodes $N$ belonging to $T_1$ are less than (in value) all the nodes $N$ of $T_2$
and a key $K$ such that $K$ is greater than all the nodes of $T_1$ and less than all the nodes of $T_2$.

I wanted to devise an algorithm to combine $T_1$, $K$ and $T_2$ into a single red-black tree $T$.

I could delete each element from either $T_1$ or $T_2$ and put it in other tree. But that will give me an algorithm of time-complexity $2^{H_1}$ or $2^{H_2}$ (depending on the tree from which I have deleted the elements from). I would like to have an algorithm which is $O(\max(H_1,H_2))$.

  Definitions :  Black-height is the number of black-colored nodes in
  its path to the root.

  Red-Black tree : A binary search tree, where each node is coloured
  either red or black and

  The root is black All NULL nodes are black
  If a node is red, then both its children are black
  For each node, all paths from that node to descendant NULL nodes have the same number of black nodes.

Your question surprisingly has an answer on stackoverflow, no doubt dating before this site. The question gives an algorithm of time complexity $O(\max(H_1,H_2))$, and claims that it can be improved to $O(\min(H_1,H_2))$.

By the way, oftentimes $O(H_1 + H_2)$ is used for $O(\max(H_1,H_2))$.


Probability of terminating in a state in a probabilistic algorithm Suppose i have a circular array of $n$ elements.
At time $t=0$ i am in position 0 of the array. The algorithm moves left or right with probability $p=1/2$ (since the array is circular when it moves left from 0 it goes to position $n$).
When i visited all the positions at least once the algorithm returns the position it terminated into.
Launching the algorithms many times shows that it stops with the same probability in any of the n positions (except for zero obviously).
How do i demonstrate that the probability of ending up in each state is uniform?
My understanding is that this process is explained by a doubly stochastic Markov chain, but is there a theorem i can quote about this specific case?

We can imagine simulating the random walk on an infinite line, keeping track of the "extension", which is the distance between the rightmost point visited and the leftmost point visited. Let $\ell(a,b)$ denote the probability that the extension became $b-a$ due to a move to $a$, and let $r(a,b)$ denote the probability that the extension became $b-a$ due to a move to $b$. When $a=b=0$, we arbitrarily define $\ell(0,0) = 1$ and $r(0,0) = 0$.

If we are at the situation counted by $\ell(a,b)$, then known formulas show that we move to the situation counted by $\ell(a-1,b)$ with probability $1-1/(b-a+2)$, and to the situation counted by $r(a,b+1)$ with probability $1/(b-a+2)$. Together with an analogous argument for $r(a,b)$, this gives the recurrences
$$
\ell(a,b) = \left(1 - \frac{1}{b-a+1}\right) \ell(a+1,b) + \frac{1}{b-a+1} r(a+1,b), \\
r(a,b) = \frac{1}{b-a+1} \ell(a,b-1) + \left(1 - \frac{1}{b-a+1}\right) r(a,b-1).
$$
We want to show that for $i=1,\ldots,n-1$,
$$
r(i-n+1,i) + \ell(i-n,i-1) = \frac{1}{n-1}.
$$
We will prove the stronger result
$$
r(i-n+1,i) = \frac{i}{n(n-1)}, \\
\ell(i-n,i-1) = \frac{n-i}{n(n-1)}.
$$
When $n=2$, we need to show
$$
r(0,1) = \ell(-1,0) = \frac{1}{2},
$$
which can be checked directly. For $n > 2$, we have
$$
r(i-n+1,i) = \frac{1}{n} \ell(i-n+1,i-1) + \frac{n-1}{n} r(i-n+1,i-1) = \\
\frac{1}{n} \frac{n-i-1}{(n-1)(n-2)} + \frac{n-1}{n} \frac{i-1}{(n-1)(n-2)} = \frac{i}{n(n-1)},
$$
and similarly
$$
\ell(i-n,i-1) = \frac{n-1}{n} \ell(i-n+1,i-1) + \frac{1}{n} r(i-n+1,i-1) = \\
\frac{n-1}{n} \frac{n-i-1}{(n-1)(n-2)} + \frac{1}{n} \frac{i-1}{(n-1)(n-2)} =
\frac{n-i}{n(n-1)}.
$$
(We don't really need to calculate the two cases separately, since symmetry arguments show that $r(i-n+1,i) = \ell(-i,n-i-1)$.)


Finite number of Turing machines running concurrently on multi-tapes Turing-machine-equivalent? So basically, there are several (finite number of) Turing machines being able to read off and write to the same set of tapes (the number of tapes is finite, but each tape may have infinite tape spaces). And then we consider a group/machine of these machines to solve a problem. Would this machine be Turing machine-equivalent?

A roung, informal sketch of how I would prove this:

We can simulate multiple threads running concurrently in a programming language like C. (Note that this is without hardware support! There are some cool ways to do this, my favorite is using continuations in Scheme, inserting a call to a thread scheduler whenever a function returns).
We can simulate a multi-tape TM with a single-tape TM.
We can simulate a single-tape TM in a programming language like C.

From this, we get that we can simulate a multi-tape TM in our programming language. Since we can simulate threads, we can now simulate multiple multi-tape TM's running concurrently.
And, since we can simulate C with a single-tape TM, we can simulate the whole thing with a single-tape TM.

The transitivity of turing-completeness is a useful tool. That is, if A simulates B, and B simulates C, then A simulates C.


Optimal solution for Weighted points problem Problem:

  Fix a constant $k$. Given a set of $2d$-dimensional points $N = \{N_1, N_2, N_3, \dots, N_n\}$, each associated with an arbitrary weight, find a set of points $X = \{X_1, X_2, X_3, \dots, X_k\} \subseteq N$ such that the pairwise distance between any two points in $X$ is at least $D$, and $\sum_{i=1}^k \mathit{Weight}(X_i)$ is maximized.

It would be nice if I could get the exponential solution and then an efficient heuristic so that I can relate to why and how the problem reduces.
The greedy way to do it would be to sort the points by weight and exclude points which are at distance $D$ from the current point that is being processed. Is there a better way to do it?

This problem is a variation of the Maximal Independent Set (MIS) problem in graph theory. To understand that you need to convert your point set $N$ into a graph $G=(N,E)$, where any two vertices $N_1,N_2 \in N$ are connected by an edge if and only if the distance between $N_1$ and $N_2$ is less than the threshold $D$. So the set $X$ you are looking for will be one of independent sets in the graph $G$. However your case is different, because here:

Each vertex in $G$ has a numerical weight, and you are trying to maximize the total weight of the independent set instead of its size - this problem is called Maximal Weighted Independent Set (MWIS) problem.
You are looking for an optimal independent set with exactly $k$ vertices.

There is a number of approaches to this class of problems, for example - this one. You can try to adapt their approach to your case with fixed size of the optimal independent set (which might not exist).

Another approach to this problem uses the fact, that the graph $G$ belongs to a class of Unit Disk Graphs. There is a number of approximation algorithms, developed for the MWIS, which use geometric specifics of such graphs - for example, this one. Again, they don't limit a number of vertices in the solution set. General discussion of heuristics for problems on unit disk graphs can be found here.

As for the straightforward heuristic algorithm for MWIS with predefined size of the solution - your approach is correct. I'll describe it in more details here. At first a definition:

An anti-neighborhood $A(N_i)$ of any point $N_i \in N$ is a subset of $N$, such that for any point $N_j \in A(N_i)$ the distance between $N_i$ and $N_j$ is greater or equal than $D$.

We'll assume that each anti-neighborhood is represented by a tree-like data structure, which can perform three operations:

Build a set from a list of points in $O(n\log n)$ time.
Find a point (in the set) with maximal weight in $O(1)$ time.
Compute intersection of two sets in $O(n\log n)$ time.

So, the algorithm:

Step 1. Find point $X_1$ with maximal weight and build its anti-neighborhood $A(X_1)$.

Step 2. Find point $X_2 \in A(X_1)$ with maximal weight and build the intersection $A(X_1) \cap A(X_2)$.

...

Step $m$. Find point $X_m \in \bigcap_{i=1}^{m-1}A(X_i)$ with maximal weight and build the intersection $\bigcap_{i=1}^{m}A(X_i)$.

...

The intersection of anti-neighborhoods may become empty at some step - in this case the problem doesn't have a solution.

The total time of this algorithm will be $O(kn\log n)$. It's unclear how close this heuristic solution will be to the optimal one.


Recognizer for decidable language and words it doesn't halt on Suppose we have a decidable language B (there exists some TM that decides it). Suppose we have another TM M which only recognizes B but does not decide it - there are words not in B that M doesn't halt on (for words not in B M might either reject or not halt).

Let A = {w | M does not halt on the word w}.

Which of the following has to be true:

1) A must be decidable

2) A might not be decidable but it has to be recognizable

3)  A might not be recognizable but its complement has to be recognizable.

4) It might be that A and its complement are both not recognizable.

I was asked this question and i think that the answer is 3.

What i don't understand is why give the extra information about some decidable language B that M recognizes if the complement of A will always be recognizable regardless of whether it recognizes some decidable language B -> for any TM, the set of all the words it does halt on will always be recognizable. The recognizer for A complement will be - run M on w and accept if it halts).

What am i missing ? Is the info about B redundant ?

The question is designed to test your understanding, so it's legitimate regardless of whether the details of $B$ are actually relevant. Maybe you're supposed to understand why they're relevant; maybe you're supposed to understand why they're not.

You've said that "recognize" is defined to mean that the Turing machine accepts all words in the language, and either rejects or loops on words not in the language.  This means that $A$ is some subset of $\overline{B}$ (the complement of $B$). Since $B$ is decidable, we know that $\overline{B}$ is also decidable.  So, $A$ is a subset of some decidable language.  Well, $\Sigma^*$ is a decidable language, so $A$ could be any subset of $\Sigma^*$. So it looks like $A$ could be any language at all! However, we have a little more information: $\overline{A} = \{w\mid M(w)\text{ halts}\}$, so $\overline{A}$ is recognizable.


What is the name for a function's "return arity"? The number of parameters a function has (and thus the number of arguments it can take) is known as arity. What is the name for the number of values a function returns? I'm not asking for the "size" of a function's return values. A function returning a tuple returns a single, composite, value.

The term "arity" would have been introduced to programming via formal logic and related fields (e.g. universal algebra). In the context of formal logic, there is little reason to allow function symbols to return multiple values even in the form of a tuple, and good reasons to disallow it.  Mathematically, a function $X\to Y\times Z$ is equivalent to a pair of functions $X\to Y$ and $X\to Z$. So we don't lose anything by disallowing functions into cartesian products. What we gain, though, is a uniform syntax, especially in the context of single-sorted logic which is the typical one in formal logic.

In a single-sorted logic, there is only one sort (base type), call it $S$, so all functions are of the form $S\times\cdots\times S\to S$, or more compactly $S^n\to S$. By disallowing functions into products, if we have a term $f(x,y)$ and a function symobl $g$ of arity 2, say, then $g(f(x, y), z)$ is always a valid term. If we allowed functions into products, we'd need to at least introduce the projections $\pi_i : X_1\times X_2 \to X_i$. This would require us to assume the products were associated in some particular way or we would need to allow a whole family of projections or we would need some syntax to "spread" the results into multiple parameters. Basically, the syntax of terms would become significantly more complicated for no real gain. These syntactic complexities are reflected in programming languages that have real multi-valued returns (as opposed to just a single-valued return of a tuple).

Single-sortedness is what allows us to reduce the arity to a number. Combined with the restriction that function symbols can only return into the single sort, everything you need to know about a function symbol for the purposes of syntax can be reduced to a single number. In multi-sorted logics, it makes more sense to view the arity as a list of sorts, but since the return type is no longer fixed something more like a type annotation, e.g. $(X, Y)\to Z$, makes more sense. These type annotations are more relevant than arity. They are what you need to tell if a term is well-formed.

Most programming languages don't support a true notion of multi-valued return, and many don't even have a good notion of tuple. Occasionally in more theoretical work, the term "coarity" is used for a return sort. In a single-sorted context, the coarity could be represented by a number, but in a multi-sorted, i.e. statically typed, context it would be more natural for it to be a list of sorts. Really, computational models where operations can produce multiple outputs are usually thought of with a circuit metaphor. In such cases, we'd talk about things like fan-in and fan-out, or in-degree and out-degree.


Verifiers equivalent classes This is a HW question, so Im not expecting full solutions or anything, but would love some direction. Also English is not my first language, so I apologize in advance.

We define a new class of languages - VNL:

  all languages L s.t there exists M - a DTM with:

  an input-read-only tape.
  a "witness" tape which is a "one-time" read-only and can be read only as stay/right (the tape head cant move left).
  a work tape which is read/write.
  Also there exists p a polynomial s.t. for every w $\in \{0,1\}^*$:
  $w\in L\ \iff\ \exists u\in\left\{ 0,1\right\} ^{p\left(\left|w\right|\right)}:\ M\left(w,u\right)=acc$
  M is of O(log(|w|)) space complexity (where w is the input).

Now we need to prove VNL=NL. I think I managed the VNL$\subseteq$NL direction:

  Let L$\in$VNL. then there exists M a DTM as we described before.
  I then define a NDTM - $M_L$ on input w: that runs M on w,u where u is randomly generated, bit by bit, everytime M wants to move right.
  It only needs to store an index to make sure u is of the right size, and that takes log(p(|w|) space, which is still logarithmic space complexity, and also running M is logarithmic. I also explain why M meets the other demands (but as they are somewhat trivial, I don't write them here to keep this post a bit shorter).

I have two questions:

  I'm not entirely sure how to do the other direction (NL$\subseteq$VNL).
  What I tried so far was: take L$\in$NL. $M_L$ is the logarithmic NDTM for it. I define M (of our new type) to treat the "witness" tape as a series of configurations. Somehow I'm supposed to verify its a legitimate configurations series resulting in M accepting w. Perhaps draw 2 consecutive configurations to the work tape and somehow verify the the transition between them is legitimate? Would love help with that.
  For another section of the question we remove the demand that the witness tape is read only to the right (which means I can read it as many times as I want). We're supposed to determine to which class VNL equals now. I thought about NP, but encountered some difficulties during the proof. Would also love help with that.

Thank you!

To your first question, suppose your non deterministic machine has two transition functions $\delta_0,\delta_1$ (if you allow arbitrary number of transitions, then you can construct an equivalent Turing machine with only two transitions by adding more states). In that case, it is intuitive how to use the one time read witness. Read $w\in \{0,1\}^{p(|x|)}$ as a computation sequence, i.e. the $i'th$ bit is $0$ if $\delta_0$ is used and $1$ otherwise. Follow the computation described by $w$, and accept iff the original non deterministic machine accepted in this computation. I leave it to you to complete the details.

As for your second question, the class generated is indeed $NP$. Obviously $VNL\subseteq NP$, so it remains to see why $NP\subseteq VNL$. Let $L$ be some language in $NP$, so we have $L\le_p SAT$, where the reduction can be computed in logarithmic space (verify that the reduction used in the proof of Cook-Levin's theorem can indeed be computed in logspace). Let $f$ be the reduction from $L$ to $SAT$ computable in logarithmic space. Given $x\in \Sigma^*$, we would like our witness $w$ to be a satisfying assignment for $f(x)$, since we can verfiy an assignment in logarithmic space. The problem is that $|f(x)|$ is polynomial in $|x|$, so we cant write it in our work tape. You can solve this by having $f(x)$ provided in the witness (along with an assignment), and your machine could verify for all $1\le i\le |f(x)|$ that $w_i = {f(x)}_i$. Luckily, since $f$ is computable in logspace, you can verify that the witness provided the correct $f(x)$, and check if the assignment satisfies $f(x)$.


Is there a complexity class QPP? The complexity class PP is not considered tractable, because the probability of success can get arbitrarily close to 50% from above as the problem instances get larger, so that (e.g. if this approach is exponentially fast) an infeasible number of repetitions may be required before we have a significant probability of confidently distinguishing satisfying inputs from non-satisfying ones. Nevertheless, PP is an interesting complexity class to study in its own right.

Is there a similar well-defined complexity class "QPP" of problems which a quantum computer has a greater than 50% chance of correctly solving in polynomial time? I understand that if so, this class of problems would not be feasible on a quantum computer, but are any nontrivial inclusions with the more "traditional" complexity classes either proven or suspected? How "big" do we think the class QPP is?

Yamakami showed in their paper Analysis of Quantum Functions that the quantum analog of PP is the same as classical PP. This is mentioned in the Wikipedia article on PP.


How to compute the sum of this series involving golden ratio, efficiently? Definitions

Let $\tau$ be a function on natural numbers defined as $\tau(n)=\lceil n*\phi^2\rceil$ where $n$ is some natural number and $\phi=\frac{1+\sqrt{5}}{2}$ is the golden ratio. This series can also be looked up here : A004957, with first few terms being $3,6,8,11,14...$ .
Let $t$ be the largest natural number such that $\tau(t) \le 10^{16}$.
Let $S_i$ for $1 \le i \le t$ be defined as $S_i=-(10^{16}-\tau(i)+1)*i+ 2*\sum_{j=\tau(i)}^{j=10^{16}} j $.

Problem
How can I compute the sum $(S_1+S_2+...S_t)$ % $7^{10}$ efficiently ? I tried thinking by matrix exponentiation, but can't come up with a method due to the form of the $\tau$ function.

PS: This question is my way of trying to solve the problem : stone game II.

As D.W. pointed out there should be some kind of recurrence involving the $\tau$ function. Turn's out there is, let us again look at the $\tau$ function series, the first few terms are

$$3,6,8,11,14,16,19,21....   \; \;(1)$$

Now let us look at the difference between consecutive terms of the series,

$$3,2,3,3,2,3,2..... \; \; (2)$$

Turns out sequence $(2)$ is the infinite fibonacci word ( again some sort of strong correspondence between golden ratio and fibonacci sequences ) made up of $2's$ and $3's$. This fibonacci sequence is as follows, the first two terms are

$a_0 = 3$ , and $a_1=3,2$ and for $n\ge 2$, $a_n=a_{n-1}.a_{n-2}$, where "." represents string concatenation. First few terms of the fibonacci word are

$$a_0=3$$
$$a_1=3,2$$
$$a_2=3,2,3$$
$$a_3=3,2,3,3,2$$

and so on. With this construction the summation I mentioned can be calculated very quickly. Also I did not make any use of the fact that modulo was taken by $7^{10}$. It would be interesting if this fact could be used somehow as D.W. suggested.

PS: I solved the question using the same formula in my question. Above I provide only a hint as coming from a non-math background I found the question really interesting and won't ruin it for others.


Time complexity of $O(n)$ loop which has a multiplication ($O(n^2)$) in it Assume we know that the implementation for the multiplication operator for a language is known to be $O(n^2)$.

Given this pseudocode:

func wibble_wobble(List<Integer> input):
    Integer constant = input.length;
    return List<Integer> { item * constant foreach item in input };

Since the loop inside the new list initialization is $O(n)$, but the multiplication operation inside is $O(n^2)$, is this function considered to have a time complexity of $O(n)$, $O(n^2)$, or maybe even $O(n*n^2)=O(n^3)$?

My gut instinct says it is $O(n)$ because a change in input would not change the time complexity of the multiplication operation, and thus would not need to be considered, but I am not sure.

The problem is that you are using $n$ to mean too many different things without really defining it. You can't say that an algorithm runs in $O(n)$ time without specifying what $n$ is, unless it is clear from context. In this case it is not clear, and that is what is tripping you up.

When we say an integer multiplication algorithm runs in $O(n^2)$ time, the tacit assumption is that $n$ is the number of bits in the two input arguments. In practice, a multiplication algorithm that runs in $O(n^2)$ is usually actually a multiplication algorithm that runs in $O(pq)$, where $p$ is the number of bits in the first argument and $q$ is the number of bits in the second argument.

When analyzing an algorithm such as the one in the question, it would be typical to define two variables: the number of elements in the list (let's call it $\ell$) and the maximum size of any element of the list (let's call it $s$). The bit size of the representation of $\ell$ is $\Theta(\log \ell)$. Given this information—and the assumption above that the multiplication algorithm runs in time $O(pq)$ for input bit sizes $p$ and $q$—then the runtime analysis is easy: the function runs in time $O(\ell s \log \ell)$.

It is possible to do runtime analysis on this procedure using only a single $n$ variable, if we define $n$ to be the total number of bits in the representation of the entire input. That is, we let $n$ be the sum of the bit lengths of all the integers in the input list. Since $\ell$ and $s$ above are obviously no greater than $n$, we can substitute $n$ for $\ell$ and $s$ in our previous bound to get a weak bound of $O(n^2 \log n)$. A more detailed analysis can actually prove $O(n \log n)$, since each bit of the input is only used in one left-hand side of a multiplication.

However, if we also drop the $O(pq)$ multiplication assumption and assume only the guarantee stated in the question of $O((\max\{p, q\})^2)$, then trying to get a bound better than $O(n^3)$ requires a lot more fiddly reasoning about tradeoffs between element size vs. list size, and probably isn't worth it. [*]

The moral of the story: when analyzing an algorithm whose runtime is affected by multiple factors, state your definitions clearly, and use as many variables as necessary for a straightforward analysis unless there is a strong reason to lump things together.

[*] This is based on me thinking about the problem for all of 5 minutes. Maybe someone else can volunteer a proof of $O(n^2)$ under these assumptions, but I couldn't think of one.


How to find loop invariant from weakest precondition? Consider this code:

Precondition:

Postcondition: rv == i <==> ∃i, 0 ≤ i ≤ a.length-1, a[i] == key

function Find(Array<int> a, int key) returns (int i) {
     i = a.length -1;
     while i ≥ 0 {
          if a[i] == key {return;}
          i = i - 1
     }
     return -1;
}

Looking at this code, it's basically searching for a key starting from the end of the array. What I am trying to find is a loop invariant using the Weakest Precondition, and prove it. However, I'm unsure if my weakest precondition is correct.I think the weakest precondition (and precondition) is nothing because nothing seems to have to be true before calling this function, maybe except a!=null. So if I have no weakest precondition or a != null(assuming this is the wp) how can I get a loop invariant? I can't see how you can derive a loop invariant from this. Aside from all this, I think the loop invariant is ∀i,j, j > i ∧ a[j] ≠ key but I didn't use the weakest precondition to come up with this loop invariant at all. Any ideas on what I am doing wrong here?

I'm only familiar with elementary hoare logic, which does not
account for returns/exits, which must be mimicked by booleans.
So let's rewrite your program to do just that.
In fact, it becomes easier to understand once we do so!

i ≔ N - 1 ;
found ≔ a[i] ≈ key;
while ¬found ∧ 0 ≤ i-1:
  i ≔ i - 1;
  found ≔ a[i] ≈ key;

Where we define

$$  N : a.length $$

Notice that we have 0 ≤ i - 1 instead of 0 ≤ i since after the decrement
i ≔ i - 1 the look-up a[i] in the next statement might not be well-defined.
So the loop guard ensures that the decrement is still non-negative and so
the look-up is well defined. In particular, look at case i ≈ 1; then
0 ≤ 0 ≈ 1 - 1 ≈ i - 1 and the loop decreases i to 0 and
the look-up is defined; afterwards the test 0 ≤ 0 - 1 fails and the loop
terminates.

Now your postcondition speaks of the return value, which is essentially just i, so let's simplify that to obtain

$$  R : 0 ≤ i < N ⇒ a[i] ≈ key $$

Now the postcondition ought to follow from the negation of the loop guard and the loop invariant: so let's take the invariant to be

$$P : i < N ∧ (found ≡ a[i] ≈ key)  % \text{  (we always have i < N and found is true iff a[i] ≈ key)} $$

then after the loop we have the post condition can be seen:

  after-loop we have the loop guard fails and the invaraint still holds
≡⟨ foramlise ⟩
  (found ∨ i-1 < 0) ∧ (i < N ∧ (found ≡ a[i] ≈ key))
⇒⟨ substitution ⟩
  (a[i] ≈ key ∨ i-1 < 0) ∧ i < N
⇒⟨ weakening: A ∨ B ⇒ A ∨ B ∨ C ⟩
  (a[i] ≈ key ∨ i-1 < 0 ∨ i < 0) ∧ i < N
≡⟨ arithmetic ⟩
  (a[i] ≈ key ∨ i < 0) ∧ i < N
≡⟨ implication ⟩
  (0 ≤ i ⇒ a[i] ≈ key) ∧ i < N
⇒⟨ weakening ⟩
  0 ≤ i < N ⇒ a[i] ≈ key

and that's the post-condition!

For ease of reference, let the guard be denoted by B; i.e.,

$$  B : ¬ found ∧ 0 ≤ i - 1 $$

We still haven't actually proved that P is an invaraint: ie that it does not vary with the
changes that occur in the loop body and that it is initally true i.e. we need to show

$$  \{ ? \}    i ≔ N - 1 ; found ≔ a[i] ≈ key \{P\} $$
  and
$$  \{P ∧ B\}  i ≔ i - 1 ; found ≔ a[i] ≈ key \{P\} $$

Initialisation is seen as follows:
the wp for assignment tells us: $$wp(Q , v ≔ e) = e \text{ well-defined } ∧ Q[e / v]$$, so applying twice means we need to have
the following as pre-condition:

  wp(P , i ≔ N - 1 ; found ≔ a[i] ≈ key)
≡⟨ sequence rule ⟩
  wp( wp(P , found ≔ a[i] ≈ key) , i ≔ N - 1)
≡⟨ assignment rule ⟩
  wp( a[i] well-defined ∧ P[ a[i] ≈ key / found ] , i ≔ N - 1)
≡⟨ definitions ⟩
  wp( 0 ≤ i < N ∧ i < N ∧ (a[i] ≈ key ≡ a[i] ≈ key) , i ≔ N - 1)
≡⟨ equivalence ⟩
  wp( 0 ≤ i < N , i ≔ N - 1)
≡⟨ assignment rule ⟩
  0 ≤ N-1 < N
≡⟨ arithmetic ⟩
  1 ≤ N

So the precondition is that the array is non-empty and in-particular is non-null (the well-definedness condition that you
mentioned).

For the invariance part we need to show

   {P ∧ B}  i ≔ i - 1 ; found ≔ a[i] ≈ key {P}
≡⟨ assignment rule ⟩
   {P ∧ B}  i ≔ i - 1 {0 ≤ i < N ∧ (found ≔ a[i] ≈ key ≡ a[i] ≈ key)}
≡⟨ reflexivitivy of equivalence ⟩
   {P ∧ B}  i ≔ i - 1 {0 ≤ i < N }
≡⟨ assignment rule ⟩
   P ∧ B ⇒ 0 ≤ i - 1 < N
≡⟨ definitions ⟩
   true

Sweet!

So the program now has annotations:

{ 1 ≤ N } // array is non-empty
i ≔ N - 1 ;
found ≔ a[i] ≈ key;
{invariant P }
while !found ∧ 0 ≤ i - 1:
  i ≔ i - 1;
  found ≔ a[i] ≈ key;
{ R }

We've only shown "partial correctness", for complete correctness we must
prove termination. In particular, we need to find a bound function bf
that is initially positive and
is decreased by the loop body: want bf such that for any constant t,

{ bf = t }   i ≔ i - 1; found ≔ a[i] ≈ key { bf < t }

Since during the loop body we always have P ∧ B and so namely 0 ≤ i - 1,
let's take the bound to be

$$  bf : i $$

Now since $B ⇒ 0 ≤ i-1 ⇒ 1 < i ⇒ 0 < bf$ we have that bf is initially positive.
(One might be tempted to try N-i as bound but that fails since the loop decreases
i which means that N-i increases!)
It remains to check that it is decreasing: for any t, we have

  { bf = t }   i ≔ i - 1; found ≔ a[i] ≈ key { bf < t }
≡⟨ assignment rule ; bf does not mention varaible `found` ⟩
  { bf = t }   i ≔ i - 1 { bf < t }
≡⟨ assigment rule ⟩
  bf = t ⇒ bf[ i-1 / i] < t
≡⟨ definitions ⟩
  i = t ⇒ i - 1 < t
≡⟨ arithmetic ⟩
  true

Alright! That was pretty fun!

One final note, if you write this, say in Python, or another language that
supports parallel assignment, you can make the program even more succinct!

i, found ≔ N - 1 , a[i] ≈ key;
while ¬found ∧ 0 ≤ i-1:
  i, found ≔ i - 1, a[i] ≈ key

Enjoy!


Introduction to number theory What is the best book for a beginner in Introduction to number theory?

I am new to this field and getting deeper into cryptography, so I think reading some intro books about number theory can be of help.

If you want to go deeper into cryptography and number theory, then of course you start here: Neal Koblitz, A Course in Number Theory and Cryptography.


Proving $L = \{0^i1^j0^i1^j\ |\ i+j > 0\}$ is not a context-free language I have the language $L = \{0^i1^j0^i1^j\ |\ i+j > 0\}$ I and want to prove that it is not context-free by using the Pumping lemma for context-free languages. I am new to this field and I am having some problems with the constant $n$ given by the Pumping Lemma. I do not know how to express $i$ and $j$ in terms of $n$. I have come up with a few example of expressing $i$ and $j$ as $n$ but some cases are always left out.

You do not need to express $i$ and $j$ in terms of $n$.

Now suppose $L$ were context-free; then there would exist an $n \geq 0$ such that for every $s \in L$ with $|s| \geq n$ there would be a partition of $s = uvwxy$ such that

$|vwx| \leq n$
$|vx| > 0$
$uv^iwx^iy \in L$ for all $i \geq 0$

Consider the example string $s = 0^n1^n0^n1^n$. Clearly, $s \in L$, and obviously $|s| \geq n$. You must now examine all the possible partitions of $s$ and show that none of them can satisfy all three of the above conditions.


Undecidability of two Turing machines acting the same way on an input So I need to find a reduction to the (undecidable) problem of deciding if two Turing machines $M_1$ and $M_2$ behave the same way on an input $x$. "Behaving the same way" is defined like this:

$M_1$ and $M_2$ behave the same way on an input $x$, when they both don't halt, or when they both accept $x$ or when they both halt and reject $x$.

I found a reduction from the halting problem which uses the fact that if the Turing machines behave in the same way, than they must have the same language. But this all breaks down in the case that $M_1$ rejects $x$ and $M_2$ doesn't halt, obviously they could have the same language, but they don't act in the same way.

I do think the best way to approach this is by reducing from the halting problem, but I just can't find a valid reduction. Any help would be appreciated.

You were very close to the answer. The special case you mentioned can be handled by hand. Modify the machines resulting from the reduction such that, for each transition, where the machine halts and rejects, let the resulting machine go into an endless loop instead.

Now each machine either accepts or goes into an endless loop. That means, checking if both machines are equivalent on an input $x$ is checking whether both accept the input $x$.


Alternate definitions of enumeration machines In my textbook, enumeration machines are defined as possessing a special write-only output tape, which they can write characters to, but not move the head of. When they hit the print state, the string on the output tape is enumerated and reset to a blank tape.

Is this equivalent to the model of enumeration machines where they have just one tape, the contents of which is enumerated (but not cleared) whenever they hit the print state? One direction seems easy, but I'm not sure how to prove you wouldn't need the extra tape.

Multitape machines are equivalent to single tape machines. You can simulate several tapes on a single tape. In particular, in order to simulate the "print state" model using the "write-only output tape" model, you simulate an extra output tape, and whenever the print state is reached, you copy the contents of the extra output tape to the write-only output tape. Therefore both models are equivalent.

More generally, all reasonable Turing machine models are equivalent. This is a special case of the Church–Turing hypothesis.


When proving NP-completeness do I only need one instance of a problem or all of them? I saw a proof of reduction of hamiltonian path to spanning tree with inner vertices having degree of k.

The person, who proved it, constructed a spanning tree from a hamiltonian path, basically u-x1-...-xi-...-xn-v, and where xi are inner vertices and then appended k-2 leaves to each one of those vertices.

I understand that that is indeed a correct spanning tree for the problem, and the u-v path does form a hamiltonian path.

But my question is, is this reduced algorithm supposed to find all such spanning trees or not?

I can create a spanning tree with inner vertices of degree k, in which there's no such hamiltonian path that spans all inner vertices, for example, and clearly this method won't work. So this makes the shown construction isolated, meaning it doesn't describe a general case of a spanning tree.

So is it enough to to just construct a certain instance of the problem B we want to prove to be NP-complete, or do we need to reduce a known problem A to the general case of B?

I am confused about this, because, for example, we can prove INDEPENDENT-SET to be NP-complete by reducing CLIQUE to it, and it involves just taking the inverse of the graph and then finding a clique in it. This case does reduce problem CLIQUE to the general case of INDEPENDENT-SET.

P.S. I am very new to NP-completeness.

When you reduce Hamiltonian-Path (HP) to Spanning-Tree-with-inner-degree-$k$ (ST), you show that if you could solve ST then you could solve HP, and moreover in a specific way. If the resulting tree is not completely general, say it is always a Hamiltonian path with attached leaves, then you are actually proving the stronger result that the corresponding promise problem is already NP-hard.

A promise problem is one in which it is guaranteed that the input is either a Yes instance or a No instance, and the task is to distinguish only those two cases. In your case, the promise version is defined in this way:

Yes instance: the graph contains a spanning tree formed by a Hamiltonian path backbone and $k-2$ leaves attached to all internal vertices;
No instance: the graph contains no spanning tree in which the degrees of all internal vertices are $k$.

If a graph falls into neither class, we don't care what the answer is. Your proof shows that it is NP-hard to distinguish the Yes instances from the No instances.

We usually don't formulate NP-hardness results this way since it is more cumbersome, but you're right that the proof shows something more. However, if you only cared about the NP-hardness of ST, then there is no need for the reduction to potentially produce all Yes instances of ST. This is because the proof that the reduction implies NP-hardness of ST doesn't require this feature. Here is the proof:

  Suppose $A$ is NP-hard, and $f$ is a polynomial time reduction from $A$ to $B$ such that $x \in A$ iff $f(x) \in B$. Since $A$ is NP-hard, for every $L$ in NP there exists a polynomial time reduction $g$ such that $x \in L$ iff $g(x) \in A$, and so $x \in L$ iff $f(g(x)) \in B$. Since $x \mapsto f(g(x))$ is also polynomial time, this shows that $B$ is NP-hard.

At no point of this proof do we use anything about the possible instances produced by $f$.

Another situation in which we can conclude an improved result is when the instance (rather than the solution) has a specific form. Suppose, for example, that we were able to reduce HP to ST, and the resulting graph never has triangles (I'm not claiming that this is possible; this is just for illustration). In this case, we could conclude also that ST-for-triangle-free-graphs is also NP-hard. It still remains true that ST itself is NP-hard; if a special case is NP-hard, then the general case is a fortiori NP-hard.


Maximize the sum of chosen numbers I have 2 problems that derive from a simple problem. I'll explain the simple one with the solution I found and after that the modified problem.

  Suppose there is a game with 2 players, A and B and a list of
  positive integers. Player A starts by taking out a number from the list, player
  B does the same and so on after the there are no longer numbers in the
  list. Both players sum up the picked numbers. Each player scores the difference between his sum and the opponent's one. The question is what is the
  maximum score player A can obtain if both players play in an optimal
  manner.

Now, for this I figured out that the optimal strategy for each player is to take the biggest number at each step.

The following 2 modification:

  At the beginning of the game player A should remove K numbers from the list. If he does this in an optimal manner and after that the games is the initial one, what is the maxim score he can obtain?

and

  At each step the players can pick the left-most or the right-most number from the list. Again they play in an optimal manner. Which is the maximum score player A can obtain?

For the second modification I can think of a brute-force approach, i.e. computing the tree of all possibilities, but this does not work for big input data. I believe that there is some kind of DP algorithm.

For the first modification I can't think of an idea.

Can someone help with some ideas for the 2 modifications, what algorithm to design in order to get the response?

[LATTER EDIT]

For the second variation I found the DP solution at https://www.geeksforgeeks.org/optimal-strategy-for-a-game-dp-31/

Here is the post for the 2nd modification, which is

At each step the players can pick the left-most or the right-most number from the list. Again they play in an optimal manner. Which is the maximum score player A can obtain?

The solution is based on DP. For the sub-problem (i-j) i.e. v[]i, v[i+1], ..., v[j] there are two choices:

The user chooses the i-th element with value v[i]: The opponent either chooses (i+1)-th element or j-th element. The opponent intends to choose the element which leaves the user with minimum value. i.e. The user can collect the value v[i] + min(F(i+2, j), F(i+1, j-1))

The user chooses the j-th element with value v[j]: The opponent either chooses i-th element or (j-1)-th element. The opponent intends to choose the element which leaves the user with minimum value.
i.e. The user can collect the value v[j] + min(F(i+1, j-1), F(i, j-2))

Following is recursive solution that is based on above two choices. We take the maximum of two choices.

F(i, j) represents the maximum value the user can collect from i-th coin to j-th coin.
F(i, j) = Max(v[i] + min(F(i+2, j), F(i+1, j-1)), v[j] + min(F(i+1, j-1), F(i, j-2)))
Base Cases
F(i, j)  = v[i] If j == i
F(i, j)  = max(v[i], v[j])  If j == i+1

Here is a pice of code in Python that solves it
def optimalStrategyOfGame(arr, n):

    # Create a table to store solutions of subproblems
    table = [[0 for i in range(n)] for i in range(n)]

    # Fill table using above recursive formula. Note that the table is
    # filled in diagonal fashion from diagonal elements to table[0][n-1] which is the result.
    for gap in range(n):
        for j in range(gap, n):
            i = j - gap

            # Here x is value of F(i+2, j), y is F(i+1, j-1) and z is
            # F(i, j-2) in above recursive formula
            x = 0
            if((i + 2) <= j):
                x = table[i + 2][j]
            y = 0
            if((i + 1) <= (j - 1)):
                y = table[i + 1][j - 1]
            z = 0
            if(i <= (j - 2)):
                z = table[i][j - 2]
            table[i][j] = max(arr[i] + min(x, y), arr[j] + min(y, z))
    return table[0][n - 1]

[SOURCE] https://www.geeksforgeeks.org/optimal-strategy-for-a-game-dp-31/


Recognizing strongly connected digraphs in NL This homework solution gives a proof that
$L = \{G \mid \text{G is strongly connected directed graph}\} \in N\mathcal{L}$. One suggested way to proof that $L \in N\mathcal{L}$ by proving that $\bar{L} = \{G \mid \text{G is not strongly connected} \} \in NL$ and then using the fact $NL = coNL$.

The tutorial uses the following algorithm for $\bar{L}$:

  Nondeterministically select two nodes $(a,b)$
  Run $PATH(a,b)$. If it rejects, then the graph is not strongly connected, so accept. Otherwise reject.

Since $PATH$ itself is a nondeterministic algorithm (or rather, we have to use a nondeterministic algorithm to still be $N\mathcal{L}$, it is not clear to me why this is correct. Why is it okay to invert the answer of $PATH$ in this case?

For example, assume our nondeterministic choices wrongly lead us to believe there is no path between $a$ and $b$, then this nondeterministic branch would accept (which means our whole TM $M$ would accept, because there is one accepting branch). But if there is also a branch of $PATH$, then our graph $G$ might actually be strongly connected and $M$ will return a wrong answer by accepting.

Because nondeterministic space classes are closed under complementation by the Immerman–Szelepcsényi theorem. So, you can't literally just invert the answer from $\text{PATH}(a,b)$ but the fact that there is an $\mathrm{NL}$ algorithm for $\text{PATH}(a,b)$ implies that there is also an $\mathrm{NL}$ algorithm for $\text{NOT-PATH}(a,b)$, and you use that.


Confusion regarding several time complexities including the logarithm I am new to Advanced Algorithms and I have studied various samples on Google and StackExchange. What I understand is:

We use $O(\log n)$ complexity when  there is division of any $n$ number on each recursion (especially in divide and conquer).
I know that for binary search, we have time complexity $O(n \log n)$, I understood $\log n$ is because each time it halves the full $n$ size number list in a recursive manner until it finds the required element. But why is it multiplied with $n$ even we just traverse half of the $n$ size element for each execution so why we multiply $\log n$ with $n$?
Please give me any example explaining the complexity $O(n^2 \log n)$. I hope this will help me in understanding much better the above two questions.

You are correct in thinking binary search is $O(\log n)$, it shouldn't be multiplied by $n$.
Popular (comparison-based) sorting algorithms are $O(n \log n)$.
3SUM (i.e. find 3 elements in an array that sums to zero) using binary search is $O(n^2 \log n)$.

The pseudo-code:

For each element
  For each other element
    Do a binary search for the 3rd element that will result in a zero sum.

Although the problem can be solved in $O(n^2)$ in a different way, this should still serve as a decent example.

Explanation of merge-sort complexity:

Merge-sort, for example, splits the array into 2 parts repeatedly (similar to binary search), but there are some differences:

Binary search throws away the other half, where merge-sort processes both
Binary search consists of a simple $O(1)$ check at each point, where-as merge-sort needs to do an $O(n)$ merge. This should already make the $O(\log n)$ vs $O(n \log n)$ make sense.

For a quick check, ask how many work, on average, is done for each element.
Note that a single merge is linear time, thus $O(1)$ per element.
You recurse down $O(\log n)$ times and, at each step there's a merge, so each element is involved in $O(\log n)$ merges.
And there are $O(n)$ elements.
Thus we have a time complexity of $O(n \log n)$.

There is also the more mathematical analysis: (source)

  Let $T(n)$ the time used to sort n elements. As we can perform separation and merging in linear time, it takes $cn$ time to perform these two steps, for some constant $c$. So,
  $T(n) = 2T(n/2) + cn$.

From here you work your way down to $T(1)$, and the remaining terms gives you your $O(n \log n)$ running time. Or use the master theorem.

If both of these are unclear, it should be easy enough to find another resource explaining the complexity of merge-sort.


Help with problem 4.1-1 from CLRS 2nd edition The exercise says "Show that the solution of $T(n) = T(\lceil{n/2}\rceil) + 1$ is $O(\lg(n))$." I came up with a solution for this exercise using the substitution method but I don't know if it is correct. My solution goes like this: I claim $T(n) \leq c\lg{n}$ and assume it holds for $\lceil{n/2}\rceil$, then
$$
\begin{aligned}
T(n) &\le c\lg(\lceil{n/2}\rceil) + 1 && \text{Inductive Hypothesis}\\
&= c\lg(n/2) + 1 && \text{Omitting ceiling}\\
&= c\lg{n} - c + 1 && \text{Algebra}\\
&\le c\lg{n} && \text{for $c\ge1$}
\end{aligned}
$$
I omit the ceiling function according to the text.
I, however, found another solution on the internet that is slightly more complicated which makes me think my solution is probably wrong. It states that $T(n) \leq c\lg(n - b)$ and assumes it holds for $\lceil{n/2}\rceil$, consequently:
$$
\begin{aligned}
T(n) &\le c\lg({\lceil{n/2-b}\rceil}) + 1 \\
&\lt c\lg(n/2-b + 1) + 1\\
&= c\lg\big(\frac{n-2b+2}{2}\big) + 1\\
&= c\lg(n-2b+2) - c\lg2 + 1\\
&\le c\lg(n - b)
\end{aligned}
$$
Where the last inequality requires that $b \ge 2$ and $c \ge 1$.
My question is if my solution is correct, then why subtract $b$ from $n$ in the second solution? If my solution is not correct, is subtracting $b$ from $n$ absolutely necessary and why is my solution not correct?

As pointed out in the comments, your proof is wrong since it is not true in general that $\log \lceil n/2 \rceil \leq \log n/2$. For example, if $n = 1$ then the left-hand side is zero while the right-hand side is negative.

In the comment you mention that the text states that they omit floors and ceilings. This is always wrong. You cannot "omit" stuff. It invalidates your entire reasoning. (Sometimes, however, you can use true inequalities to get rid of floors or ceilings: for example, $\lfloor x \rfloor \leq x$.)
Consider for example a divide-and-conquer algorithm which splits its input into two halves and performs some $O(n)$ processing. You often see its running time expressed as the recurrence
$$ T(n) = 2T(n/2) + O(n). $$
This is clearly wrong – what if $n$ is odd? What does $T(13.5)$ even mean? The argument has to be a positive integer! The real recurrence is probably more like
$$
T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + O(n).
$$
When the text states that they omit floors and ceilings, they are being sloppy. They allow themselves to do that since you can solve the true recurrence $T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + O(n)$ via the fake one $T(n) = 2T(n/2) + O(n)$, which should be interpreted as defining a function $T(n)$ for all positive values of $n$.
You can see this sentiment expressed formally in the Akra–Bazzi theorem, where floors and ceilings don't change the answer. Another way to see it is to consider only values of $n$ of the form $n = 2^m$. For these values, the recurrence $T(n) = 2T(n/2) + O(n)$ does hold. You can prove by induction that the solution to the recurrence $T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + O(n)$, and so it suffices (in this case) to determine the asymptotic rate of growth for $n$ of the form $n = 2^m$.

How do you solve your recurrence, $T(n) = T(\lceil n/2 \rceil) + 1$? First of all, you have to supply some base case, say $T(1) = C$. Given $n$, we now construct the following sequence: $n_0 = n$, $n_{i+1} = \lceil n_i/2 \rceil$. You can check that $T(n)$ equals $C$ plus the minimal index $i$ such that $n_i = 1$.
Since $\lceil m/2 \rceil \leq (m+1)/2$, we know that $n_1 \leq (n+1)/2$, and so $n_2 \leq (n+3)/4$, and $n_3 \leq (n+7)/8$, and so on. More generally, $n_i \leq (n+2^i-1)/2^i < n/2^i + 1$. Hence if $i = \lceil \log_2 n \rceil$ then $n_i < n/n + 1 = 2$, implying that $n_i \leq 1$.
In the other direction, clearly $n_i \geq n/2^i$, and so if $i = \lceil \log_2 n \rceil - 1 < \log_2 n$ then $n_i > 1$, implying that $T(n) > \lceil \log_2 n \rceil - 1 + C$.
We conclude that the minimal $i$ such that $n_i = 1$ is exactly $\lceil \log_2 n \rceil$. Hence $T(n) = C + \lceil \log_2 n \rceil$.


Finding an isomorphism between finite automata Im having trouble figuring out how to determine if two finite automata are the same apart from renumbered states.

More specifically, heres an example:

It's easy to generate a regular expression by hand and see that both FA produce:
b + (ab*a(a+b)), though their states are renumbered, they are identical.

What I'm trying to do is figure out a way to check if the two states are the same apart from state renumbering without generating a regular expression.

Since the states are just renumbered, I'm thinking it has something to do with permutations of the states(1 2 3 4) but am not seeing how to determine if they are equivalent. I'm thinking it has something to do with input like this and relating it to the 24 permutations of the states:

Left       Right
1 a 2      4 a 3
1 b 4      4 b 1
2 a 3      3 a 2
2 b 2      3 b 3
3 a 4      2 a 1
3 b 4      2 b 1

Im more so trying to figure out the algorithm to renumber the states Any ideas or help is greatly appreciated!

Here's a simpler approach to testing whether two descriptions of regular languages $L_1, L_2$ are descriptions of the same language ($L_1 = L_2$).

Compute the complement of $L_2$, denoted $\overline{L_2}$. If it's represented as a DFA, this can be done in polynomial time (linear I believe).
Compute the intersection of the automata, $L_1 \cap \overline{L_2} $. If they're both DFAs, then this is can be done in quadratic time and space.

If the intersection is null, then you know there's no word in $L_1$ which is not in $L_2$, meaning that $L_1 \subseteq L_2$.

Perform the same test with $L_1$ and $L_2$ interchanged. If $L_1 \subseteq L_2$ and $L_2 \subseteq L_1$, then the langauges are equal, meaning the minimal DFAs are isomorphic. If your input DFAs are known to be minimal, this will test for isomorphism.


How do NFA's make program design any better when converted DFA form can't remember original states? Here is some content from the book by Peter-Linz I read

"Consider a game-playing program where the machine needs to make the decision for the next move [say for tic-tac-toe]. Since there are multiple moves possible, we deterministically choose each move and evaluate the move and opt for the best one. Even though the selection process was deterministic and there were many possible moves, the final move made was a single one and was chose as best move while hiding all the tried move-computations from the opponent. [Here we assume that the evaluation process of each possible move was hidden from the opponent].
Hence only one choice was made and opponent is given a illusion such that the move was non-deterministic."

My question is: if an NFA is translated to a DFA for implementation purpose ,how does the DFA make(remember) the correct transitions to the states defined in the original NFA(the game)? My confusion stems from the fact that when an NFA is translated to an DFA it's states get mixed up.
Suppose in a simple game below ,Player is at center position and he wins if he moves leftwards:

if the above DFA is implemented it surely finds a winning state on a "m"(move),but how does it decide whether it was right or left move?

[i]f the above DFA is implemented it surely finds a winning state on a "m"(move),but how does it decide whether it was right or left move?

In the example you gave, it can't. The nondeterministic transition from the start state occurs when a "move" is made. That's all you can possibly know; the machine can't determine whether the winning move was left or right, because those aren't allowed possibilities.


Why is dominating set in $W[2]$, but independent set in $W[1]$ In Parameterized Complexity the Independent Set Problem for a Parameter $k$ ist $W[1]$-complete, and Dominating set is $W[2]$-complete. Now the prototypical $W[1]$ problem is deciding by a single-tape non-deterministic Turing machines if it has an accepting run with at most $k$ stepts, and for $W[2]$ it is the same notion with a multitape machine.

Intuitively they are both set selection problems, so a non-deterministic machine can guess in at most $k$ steps what elements to take into an independent (or dominating) set. So with this intuition, that the first problem ist in $W[1]$ is clear, but not why dominating set is not? So what am I missing, what is the distinguishing feature, why do we need a multitape machine for the second, but not for the first? My gut feeling would put domination set into $W[1]$, but that is not true as I know.

EDIT: I took the Turing machine definition of $W[1]$ from the following seminal paper Fixed-Parameter Tractability and Completeness I: Basic Results, but it is also written on wikipedia, together with the characterisation of $W[2]$. If you do not have access to the paper you can get a pdf from here, but the diagrams are missing in there (see page 6 for the definition of the Turing machine problem).

For deciding the independent or dominating set problem, it is not sufficient to guess the set. One must also verify that the guessed set indeed is an independent or a dominating set.

In the case of independent set, once the machine has guessed the set and stored it in the first $k$ cells of the tape, it checks for all pairs of guessed vertices whether they are indeed not equal and do not form an edge. There are $k\choose 2$ such pairs, so the overall running time is $O(k^2)$. Thus the reduction from independend set to short NTM acceptance is a parameterized reduction. The number of steps in the verification phase only depends on the parameter.

In the case of dominating set, one needs to checks whether all vertices are dominated. While above, we only had $k\choose 2$ pairs, now we have to deal with $n$ vertices. Which does not only depend on the parameter. (The way the multitape NTM solves this is by spending one tape per vertex.)

Of course, the above is only intended to give some intuition about why dominating set is not in W[1]. It does not give a proof. That would be way out of scope...

(For the sake of the casual reader, let me clarify that the NTMs above are not machines that solve the independent or dominating set problem. There is a reduction involved that converts instances of these problems into machines. Thus, a single such machine solves only a single instance of the problem, not the general problem.)