Isomorphism of finite dimensional polynomial algebras over finite fields For a prime power $q$, consider polynomials $f_1,f_2 \in \mathbb{F}_q[x]$. Then, do we have an efficient way of checking whether there exists an algebra isomorphism between:

$$\frac{\mathbb{F}_q[x]}{\langle f_1 \rangle} \text{and} \frac{\mathbb{F}_q[x]}{\langle f_2 \rangle},$$

and computing one such isomorphism if it exists?

I think an intermediate step will be to factorise $f_1$ and $f_2$ into products of irreducible polynomials over $\mathbb{F}_q$, which can be done efficiently using Cantor-Zassenhaus algorithm. Any hints on how to proceed?

As you mentioned, you can factor $f_1$ and $f_2$ in polynomial time.  Consider the multiset $D_1$ of degrees of the factors of $f_1$, and the multiset $D_2$ of degrees of the factors of $f_2$.  If $D_1 \ne D_2$, they are not isomorphic.  If $D_1 = D_2$, they are isomorphic.  That takes care of determining whether they are isomorphic.

Computing an isomorphism explicitly is harder.  Let me focus first on the case where $f_1,f_2$ are squarefree, for ease of exposition.  Note that if $f = g_1 \times \cdots \times g_m$, then we have a sort of Chinese remainder theorem:

$$\mathbb{F}_q[x]/\langle f\rangle \cong \mathbb{F}_q[x]/\langle g_1 \rangle \times \dots \times \mathbb{F}_q[x]/\langle g_m \rangle.$$

Consequently, by matching factors of same degree, you can reduce the problem to the case where $f_1,f_2$ are irreducible and $\deg f_1 = \deg f_2$ (in the squarefree case).  Then both fields are isomorphic to $\mathbb{F}_{q^n}$, where $n= \deg f_1$.

Finding an isomorphism explicitly (if $f_1 \ne f_2$ and $\deg f_1 = \deg f_2$) looks related to the discrete log problem over $\mathbb{F}_{q^n}$.  The discrete log problem is believed to be hard in general: the fastest algorithms currently known have a subexponential running time, and it is conjectured that there is no polynomial-time algorithm.  In particular, it looks related to the Diffie-Hellman problem, and in most fields the Diffie-Hellman problem is probably as hard as the discrete log problem.  I don't know of a reduction from discrete log or Diffie-Hellman to prove that finding an isomorphism is as hard as those problems, but I suspect there might be some relationship.

I do know that if you can compute the discrete log efficiently in $\mathbb{F}_{q^n}$, then you can exhibit an explicit isomorphism: pick a generator $g$ for the first field, and a generator $h$ for the second field; the isomorphism sends $g \mapsto g'$, and sends $g^k \mapsto h^k$, so given $x$, we compute the discrete log $k$ of $x$ to base $g$, then $x$ maps to $h^k$.

There's lots written about the discrete log problem in such finite fields.  For the case where $q$ is small and $n$ is large, see for example https://crypto.stackexchange.com/q/228/351 and https://crypto.stackexchange.com/q/22332/351.

What about when $f_1,f_2$ are not squarefree?  Then I think the problem is at least as hard.  We can reduce to the case where $f_1 = p_1^e$ and $f_2 = p_2^e$, where $p_1,p_2$ are irreducible and $\deg p_1 = \deg p_2$.  Then I think it might be possible to use Hensel lifting, though I haven't thought through the details.  In particular, here is what happens with the discrete log.  Consider the case where $e=2$.  Let $g=a_1 p_1 + b_1$ be a generator of $\mathbb{F}_q[x]/\langle p_1^2 \rangle$.  Note that

$$g^k = (a_1 p_1 + b_1)^k = k a_1 p_1 + b_1^k.$$

Therefore, to compute the discrete log of $x = a_2 p_1 + b_2$, it suffices to first find $k_0$ such that $b_1^{k_0} = b_2 \pmod{p_1}$ (which is the squarefree case of the discrete log considered above), then find $k$ such that $k \equiv k_0 \pmod{q^n-1}$ and $k \equiv a_2/a_1 \pmod{q^n}$, where $n = \deg p_1$.  Such a $k$ can be found through the Chinese remainder theorem; you end up with $k = k_0 q^n - (a_2/a_1) (q^n-1)$.  This shows how to compute the discrete log in $\mathbb{F}_q[x]/\langle p_1^2 \rangle$ if you know how to compute the discrete log in $\mathbb{F}_q[x]/\langle p_1 \rangle$.
I think the same will apply to any $e>1$, not just $e=2$.


Is there a data structure that can find the kth smallest in constant time with logarithmic add and delete operations? I'm looking for a single or a conjunction of data structures that can find the kth smallest element in constant time, delete the kth smallest element in logarithmic time, and add a new element in logarithmic time. The closest I've found to this is the order statistic tree which achieves logarithmic add and delete operations but has logarithmic time complexity for accessing the kth smallest element.

Any ideas along these lines would be much appreciated.

Clarification: kth smallest means that for any variable k value (non-constant), the data structure should be able to retrieve that value

An array is the only thing that will get you consistent lookup in constant time.

Removal & Insertion time $\in O(n)$

If you can fit your data to a model (I.e. a polynomial) and the size of your elements remains somewhat constant you can have almost constant lookup with log addition/removal


If I have an MST, and I add any edge to create a cycle, will removing the heaviest edge from that cycle result in an MST? Let's say that I have an MST, $T$. I pick an edge not in $T$ and change its weight, and add it to $T$ to create a cycle. Will removing the heaviest edge from that cycle result in an MST?

MST means minimum spanning tree of a graph. I came across these two posts:

https://stackoverflow.com/questions/13437702/how-to-get-the-new-mst-from-the-old-one-if-one-edge-in-the-graph-changes-its-wei
https://sudeepraja.github.io/MST/

and I follow both until the case where $w_{old}>w$ and $e\notin T$. They both say  that deleting the heaviest edge will guarantee an MST, but I don't see how to prove that. The cycle property just says that IF you have an MST, it can't have an edge which is the heaviest edge in a cycle of the original graph $G$; it is NOT saying that IF you have a tree that doesn't contain an edge that happens to be the heaviest edge of some cycle in the original graph $G$, you are an MST.

To make the question more explicit in terms of the problem it was trying to solve, I will copy a part of the first link:

  If its weight was reduced, add it to the original MST. This will create a cycle. Scan the cycle, looking for the heaviest edge (this could select the original edge again). Delete this edge.

I don't understand why this guarantees that we find an MST. Sure, we get a spanning tree but why does deleting this heaviest edge yield a MINIMUM spanning tree?

The important part is that you start with an MST for the original graph. With this extra piece of information, you can build a proof by contradiction, as follows:

Construct the new tree as described (add the edge, check the cycle, remove the edge with the largest weight), now assume for contradiction that this tree is not an MST. This may be for several reasons:

The real MST of the new graph differs in an edge that's not in the cycle. Then the original MST wasn't an MST to begin with, and we have a contradiction.
The real MST differs in an edge that's in the cycle, but then, as the rest of the tree is the same, we can't have removed the heaviest edge from the cycle, and we have a contradiction again.

Therefore the new tree is an MST of the new graph.


Computer Architecture - Von Neumann With regards to introductory (beginner) Von Neumann computer architecture, how does a program change the order in which instructions are executed?

I know the control unit is responsible for retrieving the instruction from memory and then decodes and executes the instruction. Their connected by a bus. The control unit and ALU are together in the CPU.

I'm guessing different lines of code are stored in different addresses in the RAM?

Is it a easy question, and I'm just thinking its difficult?

You are getting into to much detail. You can think of a CPU as some kind of automaton which operates roughly as follows (ignoring pipelining). There is a register called (in x86) IP (Instruction Pointer). The CPU operates an infinite loop (ignoring interrupts):

Read the instruction $\iota$ at address IP; determine its length $\ell$, and increment IP by $\ell$.
Execute $\iota$; this might change IP.
Go back to 1.

This is implemented in some sophisticated way, but if you don't care about performance, it performs as if the CPU was actually running this infinite loop. Control instructions change IP and so control which instructions are executed.

Different programs are just collections of instructions. When you run a program, the operating system loads it into memory and then jumps to the first instruction (i.e., sets IP to the address of the first instruction). From there on, the program executes until it terminates and releases the token back to the operating system. (Modern operating systems, which are multitasking, are more complicated, but DOS ran much according to this description, ignoring interrupts.)


Algorithm and Formalism for Most Remote Vertices In the graph below, N and M are most remote, and H is also an extremum.

Has the problem of finding the most remote vertices been formalized? Could you point me to publications or references on the subject? Does an algorithm exist for finding the most remote edges of a graph?

Please note that I am not asking you to invent an algorithm, but I'm asking for information.

One way to formulate your problem is well known as finding the diameter of a graph as the following description in Wikipedia.

The diameter $d$ d of a graph is the maximum eccentricity of any vertex in the graph. That is, $d$ is the greatest distance between any pair of vertices or, alternatively, $d=\max_{v\in V}\epsilon (v)$. To find the diameter of a graph, first find the shortest path between each pair of vertices. The greatest length of any of these paths is the diameter of the graph.
A peripheral vertex in a graph of diameter $d$ is one that is distance $d$ from some other vertex—that is, a vertex that achieves the diameter. Formally, $v$ is peripheral if $\epsilon (v)=d$.

Similarly to the way we talk about the diameter of a circle, the term "diameter of a graph" is overloaded. It can also mean, although less frequently, any shortest path between any two vertices whose length is equal to the maximum eccentricity.
If the graph is a tree, there is an algorithm that finds its diameter using only two BFS scans. Choose an arbitrary vertex $v$. Do a breadth first search from $v$ that  finds a vertex that is farthest away from $v$. Call the vertex $u$. Do another BFS from $u$ that finds a vertex that is farthest away from $u$. Call the vertex $u'$. The distance between $u$ and $u'$ is the diameter of the graph.
In a general graph, many algorithms can be used to to find the diameter of a graph. Please check this CS StackExchange question and answer, where most algorithms are in fact designed to solve the all-pairs-shortest-path problem.
In the example graph given in the question, the distance between $N$ and $M$, 9, is the diameter. In fact, $N$ and $M$ are the only two peripheral vertices in that graph. (OP calls peripheral vertices as most remote). However, $H$ is not a peripheral vertex, since the furthest distance from any vertex to $H$ is only 8. ($H$ is not a pseudo-peripheral vertex, either.)
We could define an extremum of a graph as a vertex whose eccentricity is not smaller than the eccentricity of any of its neighbors. We could also define a strong extremum of a graph as a vertex whose distance to any vertex $v$ is not smaller than the distance from any of its neighbors to $v$. Every peripheral vertices is an extremum and every strong extremum is an extremum. We can recall a leaf vertex of a graph means a vertex of degree 1. Every leaf is a strong extremum. Note that $H$ is a leaf. All those algorithms that compute all-pairs-shortest-paths can be adapted easily to find all (strong) extremum vertices as well. A simple degree-counting algorithm will find all leaves of a graph. (Please note this definition of "extremum" might not be standard at all. As far as I have tried, I have not found a single article that defines that concept. Well, I can only check probably a negligible number of articles among a myriad of them. There is probably some existing term for it in papers about social network.)


A d-ary heap problem from CLRS I got confused while solving the following problem (questions 1–3).

Question

  A d-ary heap is like a binary heap, but(with one possible exception) non-leaf nodes have d children instead of 2 children.

  How would you represent a d-ary heap in an array?
  What is the height of a d-ary heap of n elements in terms of n and d?
  Give an efficient implementation of EXTRACT-MAX in a d-ary max-heap. Analyze its running time in terms of d and n.
   Give an efficient implementation of INSERT in a d-ary max-heap. Analyze its running time in terms of d and n.
   Give an efficient implementation of INCREASE-KEY(A, i, k), which flags an error if k < A[i] = k and then updates the d-ary matrix heap structure appropriately. Analyze its running time in terms of d and n.

My Solution

Give an array $A[a_1 .. a_n]$

$\qquad \begin{align}
 \text{root} &: a_1\\
 \text{level 1} &: a_{2} \dots a_{2+d-1}\\
 \text{level 2} &: a_{2+d} \dots a_{2+d+d^2-1}\\
 &\vdots\\
 \text{level k} &: a_{2+\sum\limits_{i=1}^{k-1}d^i} \dots a_{2+\sum\limits_{i=1}^{k}d^i-1}
 \end{align}$

→ My notation seems a bit sophisticated. Is there any other simpler one?
Let h denotes the height of the d-ary heap.

Suppose that the heap is a complete d-ary tree
$$
 1+d+d^2+..+d^h=n\\
 \dfrac{d^{h+1}-1}{d-1}=n\\
 h=log_d[n{d-1}+1] - 1
 $$
This is my implementation:

EXTRACT-MAX(A)
1  if A.heapsize < 1
2      error "heap underflow"
3  max = A[1]
4  A[1] = A[A.heapsize]
5  A.heap-size = A.heap-size - 1
6  MAX-HEAPIFY(A, 1)
7  return max

MAX-HEAPIFY(A, i)
1  assign depthk-children to AUX[1..d]
2  for k=1 to d
3      compare A[i] with AUX[k]
4      if A[i] <= AUX[k]
5          exchange A[i] with AUX[k]
6          k = largest
7  assign AUX[1..d] back to A[depthk-children]
8  if largest != i
9      MAX-HEAPIFY(A, (2+(1+d+d^2+..+d^{k-1})+(largest-1) )

The running time of MAX-HEAPIFY:

$$T_M = d(c_8*d + (c_9+..+c_13)*d +c_14*d)$$
where $c_i$ denotes the cost of i-th line above.
EXTRACT-MAX:
$$
       T_E = (c_1+..+c_7) + T_M \leq C*d*h\\
       = C*d*(log_d[n(d-1)+1] - 1)\\
       = O(dlog_d[n(d-1)])
       $$

→ Is this an efficient solution? Or there is something wrong within my solution?

Your solution is valid and follows definition of d-ary heap. But as you pointed out your notation is a bit sophisticated.

You might use those two following functions to retrieve parent of i-th element and j-th child of i-th element.

$\text{d-ary-parent}({\it i}) \\
  \ \ \ \ {\bf return}\ \lfloor (i-2)/d + 1 \rfloor$

$\text{d-ary-child}(i, j) \\
  \ \ \ \ {\bf return}\ d(i-1)+j+1$

Obviously $1 \le j \le d$. You can verify those functions checking that $\text{d-ary-parent}(\text{d-ary-child}(i,j)) = i$

Also easy to see is that binary heap is special type of $d$-ary heap where $d=2$, if you substitute $d$ with $2$, then you will see that they match functions PARENT, LEFT and RIGHT mentioned in book.
If I understand your answer correctly you use a geometric progression. In your case you get go $h = log_d(n\,d-1+1) - 1$, which is obviously $\log_d(n\,d) - 1 = \log_d(n) + \log_d(d) - 1 = \log_d(n) + 1 - 1 = \log_d(n)$, which in fact is a valid and correct solution. But just for sake of handling constant fluctuations you might wanna write $\Theta(\log_d(n))$.

The reason for this is that some heaps might not be balanced, so their longest path and shorthest path migt vary by some constant $c$, by using $\Theta$ notation you eliminate this problem.
You don't need to re-implement procedure given in textbook, but you must alter it a bit, eg assigning all children to $AUX$ table using given $\text{d-ary-parent}$ and $\text{d-ary-child}$ functions.

Because $\text{EXTRACT-MAX}$ was not altered, it depends on running time of $\text{MAX-HEAPIFY}$. In your analysis you now you must use worst-case time proportional to hight and number of children which each node must examine (which is at most d). Once again your analysis is very precise, in the end you got $O(d\ \log_d(n(d-1)))$, which can be transformed to:

$O(d\ \log_d(n(d-1))) = O(d(\log_d(n) + \log(d-1))) = O(d\ log_d(n) + d\ \log_d(d-1))$

For practical reasons we can always assume that $d \ll n$, so we can lose the $d \log_d(d-1)$ part of O notation, then we will get $O(d\log_d(n))$. Which is also valid solution. But not surprisingly you can also analyse function run time using Master theorem, which will show that $\text{MAX-HEAPIFY}$ is not only $O$ but even $\Theta$.
CLRS book already provides INSERT procedure.  Which looks like this:

$\text{INSERT}(A, key)\\
  \ \ \ \ A.heap\_size = A.heap\_size + 1 \\
  \ \ \ \ A[A.heap\_size] = -\infty\\
  \ \ \ \ \text{INCREASE-KEY}(A, A.heap\_size, key)$

It can be easy proven but common sense dictates that it's time complexity is $O(\log_d(n))$. It's because heap might be traversed all the way to the root.
Just like INSERT, INCREASE-KEY is also defined in textbook as:

$\text{INCREASE-KEY}(A, i, key)\\
  \ \ \ \ {\bf if}\ key < A[i]\\
  \ \ \ \ \ \ \ \ {\bf error} \text{"new key is smaller then current"}\\
  \ \ \ \ A[i] = key\\
  \ \ \ \ {\bf while}\ i > 1\ and\ A[i] > A[\text{d-ary-parent}(i)]\\
  \ \ \ \ \ \ \ \ A[i] \leftrightarrow A[\text{d-ary-parent(i)}]\\
  \ \ \ \ \ \ \ \ i = \text{d-ary-parent(i)}$

Complexity is obviously $O(\log_d(n))$ (see previous point).


How is Turing's Solution to the Halting Problem Not Simply "Failure By Design"? I'm having a hard time viewing Turing's solution to the Halting Problem as a logician, rather than as an engineer.

Here is my understanding of the Halting Problem:

  Let $M$ be the set of all Turing Machines.

  Let $i$ be the set of all inputs for all the Turing Machines in $M$.

  Let every element in $M$ be an element in $i$.

  Let the boolean values $true$ and $false$ be elements in $i$.

  Let $h(M,i)$ be a function that returns:

  $true$ if and only if $M(i)$ halts
  $false$ if and only if $M(i)$ does not halt

  Let $p(M)$ be a Turing Machine in $M$ that:

  calls $h(M,M)$
  halts if and only if $h(M,M)$ returns $false$
  doesn't halt if and only if $h(M,M)$ returns $true$

  What happens when we call $p$ by passing $p$ to itself, $p(p)$?

The part I take issue with is implementing $p(M)$ so that it will not halt when $h(M,M)$ is $true$. My gut understands this approach as follows:

  Given a method $h()$ that works, and a method $p()$ designed to break $h()$, when we combine these methods to build a machine, that machine is broken.

I understand proof by contradiction is a valid approach to problem solving in formal logic, but this particular application of proof by contradiction seems flawed somehow.

What am I missing?

In what follows, I'll distinguish a machine $M$ from its description, denoting the description of $M$ by $\langle M\rangle$.

Specification of the halt tester program, $H$

  $H$ takes as input a pair $(\langle M\rangle, i)$, where $\langle M\rangle$ is the description of machine $M$, and $i$ is the input required by $M$.

  $H$ halts on any input pair $(\langle M\rangle, i)$ and returns the correct answer, namely:

  $H(\langle M\rangle, i)$ returns true if and only if $M$ halts on input $i$.

Now, assuming that there is such a machine $H$, we can use $H$ as a subroutine to construct a program $P$ as follows:

Specification of the "perverse" program $P$

  $P$ takes as input a description, $\langle M\rangle$, of a machine $M$.

  $P$ works correctly on any input $\langle M\rangle$, namely

  $P(\langle M\rangle)$ halts if and only if $M$ doesn't halt when given input $\langle M\rangle$.

The key to this argument is that if we can define a machine $H$ that satiffies the specification above, then we can build a machine $P$ that satisfies the second specification.

However, $P$, when given $\langle P\rangle$, exhibits impossible behavior,

$\qquad\qquad\qquad P(\langle P\rangle)$ halts if and only if $P(\langle P\rangle)$ doesn't halt.

So $P$ fails to meet its second requirement on at least one input and consequently it must be the case that $H$ cannot satisfy its requirement, so consequently we cannot make $H$ as specified.

Now $H$ might very well behave as specified on lots of inputs $(\langle M\rangle, i)$, but the point is that no halt tester can be built that works on all possible inputs.


Find the smallest binary digit multiple of given number I was reading an article on Find the smallest binary digit multiple of given number. The problem is - We are given a decimal number N, we need to find the smallest multiple of N which is binary digit number.

There is an optimization done i.e. if a string with same mod value is previously occurred we won’t push this new string into our queue. The explanation given is-

Let x and y be strings, which gives same modular value with n. Let x be the smaller one. let z be another string which when appended to y gives us a number divisible by N. If so, then we can also append this string to x, which is smaller than y, and still get a number divisible by n. So we can safely ignore y, as the smallest result will be obtained via x only.

How can we say that, we can also append this string to x, which is smaller than y, and still get a number divisible by n ?

And how can we say that the smallest result will be obtained via x only?

No idea where you got that 9 from, in the last line of the question.

Having said that, You have to know that "concatenating" numbers is equivalent to multiplying the first number by a power of 10, followed by adding the second number. E.g. 42|7 = (42*10)+7.

Now obviously 42 is divisible by 6, but therefore so is 420. Furthermore, 42 mod 5 = 2, therefore 420 mod 5 = 20 mod 5. "42 is divisible by 6" in fact means "42 mod 6 = 0"


What is the formal justification for the correctness of the second formulation of rod cutting DP solution CLRS on section 15.1 3rd edition has a good discussion of the rod cutting problem. I will add a description at the end of the question for reference.

Define $r_j$ to be the optimal way to cut a rod of integer length $j$.
Since we do not know where is the optimal place to cut the rod we consider every location $ i  \in \{0,\cdots,j\}$ (essentially doing exhaustive search) to do the cut. Then we are left with two rods of length $i$ and $j-i$ to cut optimally.
If we consider every location we could do a cut and then cut the remaining rods optimally, then we have essentially solved $r_j$ optimally. i.e. we get the following recursion:

$$ r_j = \max \{p_n, r_1 + r_{k-1}, r_2 +r_{j-2}, ..., r_{j-1} + r_1 \}$$

However there seems to be an alternative (or maybe simpler strategy to solve such a problem):

$$r_n = \max_{1 \leq i \leq n} \{ p_i + r_{n-i} \}$$

CLRS has the following discussion about it:

  In a related, but slightly simpler, way to arrange a recursive
  structure for the rod- cutting problem, we view a decomposition as
  consisting of a first piece of length $i$ cut off the left-hand end,
  and then a right-hand remainder of length $n -i$. Only the remainder,
  and not the first piece, may be further divided. We may view every
  decomposition of a length-n rod in this way: as a first piece followed
  by some decomposition of the remainder. When doing so, we can couch
  the solution with no cuts at all as saying that the first piece has
  size $i = n$ and revenue $p_j$ and that the remainder has size $0$
  with corresponding revenue $r_0 = 0$.
  In this formulation, an optimal solution embodies the solution to only one related subproblem-the remainder-rather than two.

Personally I've always found it harder to convince myself that this in fact optimal (and that is therefore equivalent to the first one). Therefore I was wondering if anyone had a good argument or maybe a good formal proof to arguing why this second formulation is in fact optimal.

Usually I've tried to justify it to myself by having the following thought experiment: well, if I want to have an optimal revenue I need to make sure that I some how explore all good solutions exhaustively and not miss any. If I want the solution to the whole thing $r_j$ then it could be that the full rod is required, then the cut is at position $i=n$. That is if the optimal solution contains no cuts. But if we have a cut we will have some part of the rod that must remain un cut.
If that is the case, then just consider all possible full parts of the rod from the beginning of the rod to the end that remain uncut. Basically, it seems that the solution is as follow, every solution to $r_j$ must contain a piece of rod from the beginning that is uncut to some cutting location $i$.
Since this is part of the optimal solution, we just consider all beginnings that are "full" rods up to $i$ and then make sure to solve the remaining optimally.
This justification feels close to being the argument of correctness but for some reason it just seems to be missing something (wish I knew what it was).

Does someone know how to write a better clear proof of correctness of this? If its really formal or rigorous that is ok with me, I just sort of want some proof for the second recursion where there is no doubt that its correct.

Thanks for the help!

Recall the rod cutting problem.
You manufacture steel rods of some fixed length and sell them in segments of integer length and because of the laws of supply and demand, the price per length is not constant.
Given a set of prices (i.e. an array $p_i$ indicating the price for an integer cut of length $i$) for each possible length segment, how should you cut a given rod of length $n$ into integer length segments to maximize revenue?
You may assume that no cost or loss incurred with each cut.

The proof of $r_n = \max_{1 \leq i \leq n} (p_i + r_{n-i})$ is divided into two parts. In the first part, we prove that $r_n \geq \max_{1 \leq i \leq n} (p_i + r_{n-i})$. In the second part, we prove that $r_n \leq \max_{1 \leq i \leq n} (p_i + r_{n-i})$.

First part. It suffices to prove that for each $1 \leq i \leq n$, $r_n \geq p_i + r_{n-i}$. Indeed, consider first breaking the rod into a piece of size $i$ and a piece of size $n-i$, and then cutting the second piece optimally. This strategy guarantees a profit of $p_i + r_{n-i}$.

Second part. It suffices to prove that for some $1 \leq i \leq n$, $r_n \leq p_i + r_{n-i}$. Consider any way of cutting the rod. Let $i$ be the size of the leftmost piece, which results in a profit of $p_i$. The other pieces (if any), put together, form a rod of size $n-i$, and so the profit gained from them is at most $r_{n-i}$. In total, the profit is at most $p_i + r_{n-i}$. In particular, the optimal profit $p_n$ is at most $p_i + r_{n-i}$.


Matching training with Neural Network I have a matching algorithm that is based on making an comparison score. This score is divided into parts.
Example:

5 - Points for attributes (lets say they have 3 common attributes, would the score be ((3/5)*5) = 3 Points

5 - Points for location

10 - Points for content

Theses points are just something i have set though guessing, and they work well.
But to find what values would be best would i like to implement a kind of AI to test this, i have created 20+ test cases where i know what the correct matching is, so i though that i will be able to train my algorithm to have better values for the different value.
I am no expert in AI, i have only have one course about it, but would a neural network be able to help me here, or should i go with another AI?

I would suggest you use linear regression, or simply grid search (you can search over all possible number of points for each category, from 1..20; that's only $2^{13}$ possibilities, all of which can be easily tested one-by-one).

Make sure to use cross-validation: split the data set into training and test, and use the training data to derive the best parameters, then evaluate it on the test part.


Algorithm for maximizing correspondence between 2 sets I am trying to figure out how to solve the following problem: I have 2 sets of objects, set A and set B. I have a metric that calculates how closely a given object from set A corresponds to an object from set B. I'd like to maximize the overall correspondence of the entire set.

What I tried first was a sort of greedy algorithm, where I went through each object in set A and calculated that object's correspondence with each object remaining in set B. I then replaced the object in set B that had the highest correspondence with the object in set A. For the next object in set A, I did the same thing, leaving out the objects in set B that already had a correspondence.

The problem with this approach is that it works very well for the first part of the sets, but as I near the end, there are fewer objects in set B to match with, so objects from set A tend to have worse correspondence with those objects.

I think that it might be better to do a full calculation of the correspondence of each item in Set A to each item in Set B, and from there choose each item from set A that has the highest correspondence of the next item in set B.

However, I'm left wondering if you could have a situation where, for example, object 1 from set A has, let's say an 95% correspondence to object 6 in set B, but it's next best correspondence is only 50% with object 14 in set B. Meanwhile, object 2 from set A has a correspondence of 97% to object 6 from set B, but it has a 96% correspondence to object 28 in set B. In my mind, I think it would be better for object 1 from set A to be matched with object 6 from set B (95% correspondence) and object 2 from set A to be matched with object 28 (96% correspondence) in set B instead of matching object 2 in set A to object 6 in set B and object 1 in set A to match object 14 in set B.

Is there a name for such an algorithm? I feel like it's related to the Knapsack Problem, but is not exactly the same. There will always be the same number of objects in set A and set B. I suppose it's possible that there will be more than 1 set of mappings that are "most optimal". In that case, I don't care which one is chosen.

In my application there will be between a few hundred to 10 or 20 thousand objects in each set. The average will probably be around 5,000 or so.

This is known as the assignment problem.  There are polynomial-time algorithms for it.


Computing all paths from root to the leaf nodes in a tree I have a this tree, i want to print out all paths from root to all child nodes:

NOTE: I wanted to come up with a solution that does not involve passing state between recursive calls.

    a
  / | \
  b c  d
 / \    \
e  f    g
      / / | \
      h i j k

This is the my code to create and print the paths.

class Node:
    def __init__(self, data, children=[]):
        self.data = data
        self.children = children

tree = Node(
    "A",
    children=[
        Node("B", children=[Node("E"), Node("F")]),
        Node("C"),
        Node("D", children=[Node("G", [Node("H"), Node("I"), Node("J"), Node("K")])]),
    ],
)

i want to enumerate all the paths to reach from root node to all leaf nodes.This is what i have come up with.

def paths(root):
    x = []
    if root.children:
        for c in root.children:
            for el in paths(c):
                x.append(c.data + el)
    else:
        x.append("")
    return x

a = paths(tree)
print(a)

i get this output:

['BE', 'BF', 'C', 'DGH', 'DGI', 'DGJ', 'DGK']

This is partially correct, what is missing is the root node 'A' in all the paths, I am not able to think how to get that, even after thinking for 2 hours straight. I know why is it happening(because I start from child nodes of the root). what i cannot get is how to encode the root node itself.

I hope this pseudocode is clear:

function paths(N):
  path <- empty list
  if the node(N) has children
     for every child node `(C)` of `N`
        for every path `(P)` in paths(`C`)
           add to path <- `C.data` + `P`
   otherwise
      add to path <- + ""
   return path

The problem is that each node is adding its children to the list of paths. Instead, you can modify your recursive function so that each node only adds itself.

That is, $paths(v)$ returns a list $L_v$ of all paths from $v$ to the leaves of the subtree rooted in $v$.

If $v$ is a leaf, then the list $L_v$ returned by $paths(v)$ contains a single path consisting of $v$ itself.

If $v$ is not a leaf and $u_1, \dots, u_k$ are its children, then $paths(v)$ returns the union of $k$ lists $L'_{u_1}, \dots, L'_{u_k}$, where $L'_{u_i}$ is obtained by prepending $v$ to every path in $L_{u_i}$.


Does exist an algorithm to find all equivalence classes of given regular expression without kleene star? If yes then what is it? Does exist an algorithm to find all equivalence classes of given regular expression without kleene star?

If yes then what is it?

Note that alphabet of the given regular expression is binary, i.e. it contains only 2 symbols exactly.

This is important, because I can easily construct NFA from the given regular expression and then construct the DFA from that NFA, but the result DFA is not minimal and the result DFA's number of states is exponential.

Of course I can run Hopcroft's algorithm to minimize the DFA, but if DFA's number of states is Θ(2n) then Hopcroft's algorithm runs in Θ(2nlog(2n)) = Θ(2nn) = Θ(n2n) and this might take too much time to get the minimal DFA for the given regular expression.

Also my computer has only 4GB of RAM.

If the given regular expression is long and the result NFA is big, then in the middle time conversion from NFA to DFA, there might be out of memory exception thrown and my application won't make it to call Hopcroft's algorithm at all.

For the given regular expression, running the algorithm to find all it's equivalence classes is considered to be much better than constructing NFA from the regular expression, constructing DFA from the NFA and run Hopcroft's algorithm to minimize it, but if and only if the algorithm to find all the equivalence classes won't use too much resources and won't take too much time to finish, then I can use the equivalence classes to efficiently construct the minimal DFA quickly for the given regular expression.

I tried to google the answer for this question, but I didn't find it yet.

Thinking about this algorithm myself is very difficult and hard.

I am very curious to find out what is this algorithm already.

No such algorithm is forthcoming. As I mentioned in an answer to one of your other questions, you can encode SAT as a regular expressions that equals $(0+1)^n$ iff the given formula is unsatisfiable. This means that the algorithm you are looking for will be able to solve SAT.


Are Finite Automata Turing Complete? Something is Turing Complete if it can be used to simulate any Turing Machine.

So, can a Finite Automaton simulate a Turing Machine?

On the question Can regular languages be Turing complete? they say a Regular Language can be Turing Complete, but it does not make sense to me. I am not talking about the Language being parsed, but the Finite Automaton itself.

Finite Automatons and Regular Languages are not Equivalents. Finite Automatons are machines which accept or reject some Language. But Regular Grammars and Finite Automata are equivalents because I can convert one to another. Then, the question is, are Regular Grammars Turing Complete? Are Type 0 grammars Turing Complete? i.e., can I use a Regular Grammar or a Type 0 Grammar to do any computation I would like?

Can I write a Finite Automaton to do anything a Full-Featured General Purpose Computer can do?

No finite automaton can simulate a Universal Turing machine, so finite automatons are not Turing complete. This falls out immediately from them having a finite number of states. Universal Turing machines require an unbounded amount of space to work.

The source code of an Jot program can be recognized with a finite automaton. That automaton doesn't evaluate the program (and thus doesn't play the role of a Turing machine), it just determines whether or not it is well-formed enough to be run.

This is in contrast with most programming languages. For example, because JavaScript has nested () and {}, it's necessarily not regular (but is, at least approximately, context free). Indentation sensitive languages like Python aren't even context-free (without preprocessing of identation).

This isn't that interesting of an observation. For example, the following is a Turing-complete a subset of syntactically-valid JavaScript programs that is recognizable with a regular expression:

/^eval\("[^\n\"]+"\)$/

...just most of these will immediately throw a runtime error because eval will not parse its single argument -- essentially we can define a programming language to treat all inputs as "syntactically valid" by just defining a new runtime behavior for all the syntactically invalid ones.

What is maybe more interesting about Iota is that its grammar also naturally parallels the actual structure of programs, instead of being a weird encoding trick like the above.


Time complexity of mutually recursive functions Suppose I have two mutually recursive functions like this:

f1(x)
{
   .//some code
   .
   .
   f1(x-1)+g1(x-1);

}

g1(y)
{
   .
   .//some code
   g1(y-1)+f1(y-1);
  ..

}

How can I calculate time complexities in such cases?

If we set up recurrences, $T_1(n) = T_1(n-1) + T_2(n-1)$ and $T_2(n) = T_1(n-1) + T_2(n-1)$. So from there we can get that $T_1(n) = T_2(n)$, which implies that $T_1(n) = 2T_1(n-1)$. So for this, the two functions would be $O(2^n)$.


Master Theorem on oscillating function Consider a recurrence of the form

$T(n) = a T(n/b) + f(n)$

Master theorem's regularity condition excludes some cases (for example, when $f(n)$ is oscillating).

Suppose, however, that $f(n)$ is always less than or equal to a function $g(n)$ that does not violate the regularity condition, so that the master theorem is applicable if $g(n)$ is used instead of $f(n)$.
Consider then the following recurrence:

$T'(n) = a T'(n/b) + g(n)$

and assume that the master theorem gives the solution $T'(n)=\Theta(g(n))$.

My doubt is this: can I then safely conclude that $T(n)=O(g(n))$?

In other words, can I be sure that the solution of a recurrence with a term replaced by its upper bound is an upper bound of the solution of the original occurrence? After all, the recurrence establishes a relationship between $T(n)$ and $T(n/b)$ but says nothing about what happens between $n/b$ and $n$ (and $f(n)$ here is oscillating...).

Yes, you can.  You are defining the recurrence $T'$, so define $T'(1) = T(1)$.  Then, since $g(n)$ satisfies the regularity conditions, the Master theorem tells you that $T'(n) = \Theta(g(n))$.  Note that the Master theorem doesn't depend on the choice of $T'(1)$; it is a constant, and you get the same asymptotic bound for $T'(n)$ regardless of which constant you choose.

Now, you can prove by induction that $T(n) \le T'(n)$ holds for all $n$.  This is a simple induction.  The base case holds because you defined $T'$ that way.  The inductive step holds because $f(n) \le g(n)$ for all $n$.

Once you've proven that $T(n) \le T'(n)$ for all $n$, you are entitled to conclude that $T(n) = O(T'(n))$ and thus $T(n) = O(g(n))$.


If possible, use binary search to find an element in sorted array Given sorted array $A[1..n]$, we want to find an element such that,
$A[i]=i^2$,Can we use binary search to find such a element?

My Attempt:
initially, I read this link, but I can't understand the comments for why we can't find that element in $O(\log n)$. Any hint be appreciated.

No. Let's define an array $B$ as $B[i] = i^2 - 1$. Clearly it has  no solution, but it is sorted.
Now I define $A$ to be a copy of $B$, with exactly one element, $A[k]$ incremented by one. This array is still easily seen to be sorted, but there's no way to find out which $k$ I used to increment a single element other than scanning the complete array. After all, if you inspect $n - 1$ indices of this array, I could've chosen $k$ as the single index you didn't look at.


Algorithm for finding the minimum index in array with value exceeding x Given a set $S = \{s_1, \ldots, s_k\}$, find the minimum index $j$ such that $\sum_{i = 1}^j s_i \geq \frac{1}{2}\sum_{i = 1}^k s_i$.

I was reading in a paper about an algorithm for this problem that is described as follows:

  The idea is to construct an array of size $k$, whose $j$th position contains $\sum_{i = 1}^j s_i$. Then one can find the appropriate index $j$ in $O(\log(\min\{j, k - j\}))$ time by using a form of binary search simultaneously from both ends of the array.

Can someone explain how the binary search might work? I know that constructing the array still takes $O(k)$, but I want to use this in an algorithm where the array would be computed just once and used with recursive calls to this algorithm.

Assuming the $s_i$ positive (which wasn't said in the OP), the prefix sum of $s_i$ forms a monotonic sequence.

You can start a simultaneous exponential search from both ends, followed by a standard binary search when the half sum has been crossed. The left exponential search takes $O(\log(j))$ and the right one $O(\log(k-j))$. As they are performed simultaneously, the fastest "wins".


Complement of languages and coNP By definition, any language (decision problem) $L$ is defined as a subset of $\{0,1\}^*$, where $\{0,1\}$ is the alphabet.

$L^c$ is said to be the complement of the language, and it seems to be defined as follows - $\forall w, w\in L \implies w \notin L^c$ and $w \notin L \implies w \in L^c$.

Equivalently, according to Arora and Barak's book "Computational Complexity: A Modern Approach",  $L^c = \{0,1\}^* - L$.

I will demonstrate my question with an example - The definition of the complexity class $coNP$ is, as per Arora and Barak's book, $coNP = \{L : L^c \in NP \}$.

But if we take a specific case, lets say

$SAT = \{f(x_1, x_2,\cdots,x_n) : \exists x
\in \{0,1\}^n f(x) = 1\}$,

then the $coNP$ counterpart is supposed to be

$\overline{SAT} = \{f(x_1,x_2,\cdots,x_n) : \forall x \in \{0,1\}^n f(x) = 0\}$

Which means, $\overline{SAT}$ contains all the boolean formulae that are false for all inputs.

According to the definitions above though $(L^c = \{0,1\}^* - L)$, lots of random words should be included in the language $\overline{SAT}$ that are not even "well formed" boolean formulae to begin with.

Should the complement be over all boolean formulae instead of $\{0,1\}^*$?

Is the complement of every language always defined over a subset of words that are "well formed" instead of having been defined over $\{0,1\}^*?$

The complement (note spelling) of $\mathrm{SAT}$ is the set of all binary strings that do not encode a satisfiable Boolean formula. That is all strings that encode unsatisfiable formulas, and also any strings that don't encode any formula at all.

In practice, we tend to ignore strings that don't encode a valid input to the problem. For any sane encoding, recognising which strings are valid encodings is computationally very easy.  For any such encoding, the computational complexity of the two languages
$$\{w\mid w\text{ encodes an unsatisfiable formula}\}$$
and
$$\{w\mid w\text{ encodes an unsatisfiable formula or is not a valid encoding}\}$$
is the same, so we tend not to distinguish between them.

Alternatively, it's usually fairly straightforward to come up with an encoding where every string is a valid encoding of some input. For example, consider a problem whose input is a graph.  Naïvely (and normally!) we would encode a graph as the binary listing of its adjacency matrix. However, that means that only inputs whose length is a perfect square are valid.  We could make every string valid by adding zeros to the end until the length is a perfect square so that, e.g., the string $01101$ would encode the graph whose adjacency matrix is
$$\left(\begin{matrix}0&1&1\\0&1&0\\0&0&0\end{matrix}\right).$$
If our input is supposed to be an undirected graph, that's still no good, since the matrix isn't symmetric.  In that case, we could just encode the entries above the diagonal, again padding with zeros to reach the next triangular number.  In this encoding, $01101$ would encode the graph with adjacency matrix
$$\left(\begin{matrix}0&0&1&1\\0&0&0&1\\1&0&0&0\\1&1&0&0\end{matrix}\right).$$

But translating between these inputs is easy (it can be done in, e.g., deterministic logspace), so we usually just ignore these fine details.


runtime of 2 dependent nested for loops for (i=1; i<=n ;i=i*2){

  for (j=1; j<=i ;j++){

  basic_step;

  }
}

Regarding the above nested loops, I can't seem to understand why is the following runtime analysis is correct (specifically the first equality), when $k$ is defined as $\log i$, meaning $i=2^k$.
What is the process that one should come up with, in order to decide this setting and the sigmas' indices? While I do understand that the outer loop runs for $\Theta(\log n)$ times, I still can't grasp the setting of $k$. A clarification will be very much appreciated!

$$\sum_{k=0}^{\log n}\sum_{j=1}^{2^k}1$$

The value of $i$ at the $k$'th iteration (starting from zero) is $i_k := 2^k$. The inner loop runs $i_k$ times, for a total of $i_0 + i_1 + \cdots + i_K$, where $K$ is the largest number such that $i_K \leq n$, that is $\lfloor \log_2 n \rfloor$. Therefore the running time is
$$
\sum_{k=0}^{\lfloor \log_2 n \rfloor} 2^k = 2^{\lfloor \log_2 n \rfloor + 1} - 1 = \Theta(n).
$$


A relationship in a UML class diagram I am investigating a small database in a paper:

Each line is a selling record. For instance, Line 2 expresses that Store 100 in Week 383 sold Product 653; for this selling, the move was 16 and the price was 2.19, thus the profit was 16*2.19*2=7.01 (the other columns are not very important).

The authors then show a UML class diagram as follows:

What I cannot understand (and is not explained in the paper) is the relationship between OnSaleKey and DetergentKey. Could anyone tell me what it is about in a UML diagram language?

You can have many sales of the same product in the same store and in the same week. Also, a detergent can be sold in different weeks in different stores.

This means that you have to create a class Sale, that associates an OnSaleKey to a DetergentKey.

The Sale class is an association class.

From here you can find an explanation:

  An association may be refined to have its own set of features; that
  is, features that do not belong to any of the connected classifiers
  but rather to the association itself. Such an association is called an
  association class. It is both an association, connecting a set of
  classifiers and a class, and as such could have features and might be
  included in other associations.

  An association class can be seen as an association that also has class
  properties, or as a class that also has association properties.

  An association class is shown as a class symbol attached to the
  association path by a dashed line. The association path and the
  association class symbol represent the same underlying model element,
  which has a single name. The association name may be placed on the
  path, in the class symbol, or on both, but they must be the same name.

In this case it is easier to think about the Sale class as a table in a database that associates an id from OnSaleKey to an id from DetergentKey.


Determine if the language of words with same number of 1's and 2's is context-free or not $$L_2=\{w \in \{0,1,2\}^* : \text{$w$ has the same number of $1$'s and $2$'s}\}$$
I have tried creating PDA to determine if this was context-free or not. It seems like it would be because whenever a 1 is pushed onto the stack, there always is a 2 to get pop it out. The 0's are what is bothering me at the moment. Do we need to include them, or we can exclude them entirely?
I would do this with pumping lemma, but we did not learn that for our class.

When it comes up to deciding if a language is context-free or not, I try the following 'roadmap' to come up with an answer.
$1.$ Try to make a CFG for the given language. If we can make a CFG, we have proved that the language is context-free.
$2.$ If step $1$ did not work out, there is a probabilty that the language is not context-free. So try proving that the given language is not context-free by the pumping lemma.
$3.$ If I fail to prove that language is not context-free, I probably failed to make a CFG so I start to make a PDA.
Remark: This is my way to (dis)prove context-free languages, there are many other ways to do this. So don't take this as a general step-by-step plan.
In your example, we need to (dis)prove $$L_2=\{w \in \{0,1,2\}^* : \text{$w$ has the same number of $1$'s and $2$'s}\}$$
So when we think of a CFG, we should consider that whenever we add a $1$, we should also add a $2$ (and vice-versa), as $|1| = |2|$. We also know that the language can be empty and that the number of $0$'s do not matter.
So
$$S \rightarrow \epsilon $$
$$S \rightarrow 0S$$
$$S \rightarrow 1S2S$$
$$S \rightarrow 2S1S$$
As we were able to make a CFG, we can say that the language $L_2$ is a CFL.


$DTIME(f(n)) \subset of DSPACE(f(n))$ I think this is again an easy one:

  $DTIME(f(n)) \subset DSPACE(f(n))$

They say its trivial but I dont see it, why?

And would

  $DTIME(f(n^2)) \subset DSPACE(f(n^2))$

also be true? if yes why or why not?

If space is greater than time, as it must surf the space (in the related Turing machine), it will be contradicted by time is less than space. Hence, we can find that all problems which are in $DTIME(f(n))$ are in $DSPACE(f(n))$. and the proof is completed.

On the other hand, the size of input is important. Hence, if we set $m = n^2$ we reach to the first relation. Hence, it is true again.


Insertion sort on small arrays in Merge Sort Quick question on the wording of the question from CLRS Ch2 Problems. The question goes as follows:

Although merge sort runs in $\Theta(n\lg n)$ worst-case time and insertion sort runs in $\Theta(n^2)$ worst-case time, the constant factors in insertion sort can make it faster in practice for small problem sizes on many machines. Thus, it makes sense to coarsen the leaves of the recursion by using insertion sort within merge sort when subproblems become sufficiently small. Consider a modification to merge sort in which $n/k$ sublists of length $k$ are sorted using insertion sort and then merged using the standard merging mechanism, where $k$ is a value to be determined.

My question is: shouldn't there be $k$ sublists each of length $n/k$? The other way around is stated in the question. Because in merge sort, we keep halving the array, thus producing twice the number of arrays as in the previous level. Hence, each sublist is of length $n/k$ and we have $k$ of such sublists. Why does the question mention this the other way around?

The idea most probably is to chose sublist size $k$ such that merge sort likely is faster for bigger problem instances and insertion sort for smaller ones.
$\lceil s = n/k\rceil$ sub-lists may be suboptimal for merging lists of disparate size later on.
One alternative is splitting into $2^{\lfloor\log_2{n/k}\rceil}$ lists.


Variant to the Vertex Cover Problem Suppose that we are given an undirected graph, and we know that the maximum edges covered by $k$ vertices is $n$. If we let the greedy algorithm choose these $k$ vertices for us, I am told that it is capable of covering at least $n/2$ edges. Is there a way to prove this? If so, how should it be done?

Since the greedy algorithm removes the vertex with the maximum degree still left in the original graph (along with its incident edges) in each iteration, is it possible to find a connection between the minimal number of edges removed each time by the greedy algorithm to the optimal solution $n$?

I am truly clueless about how such a problem should be solved.

Hints or references are both welcome. Many thanks.

You haven't fully specified the greedy algorithm, so let's assume that at each step you select a vertex covering the most new edges. In that case, this is the greedy algorithm for the more general problem of Maximum Coverage, whose approximation ratio is known to be roughly $1-1/e$, which is even larger than $1/2$. For a proof, see for example here. There is also a less classical proof that doesn't use elements at all, but only the monotonicity and submodularity properties of the coverage function (the function getting ass input a set of vertices and outputting the number of edges covered).

There are somewhat better algorithms that use the fact that each edge is covered by only two vertices. Examples are the LP-based algorithm and the non-oblivious local search algorithm. It is also possible that the greedy algorithm performs better in this case.


Language of binary strings divisible by 7 There was a question something like, "Consider the language of all integers converted to binary form. The language of all strings divisible by 7 is :

1) Recognizable by a finite-automaton.

2) Recognizable by a Non-deterministic finite-automaton.

3) Recognizable by a deterministic Pushdown Automaton.

4) Recognizable by a Non-deterministic Pushdown Automaton.

5) Not recognizable by any of the above.

I'm curious to know the answer and its reason.

The langauge is regular, so answers 1–4 are all correct.

The (deterministic) automaton has seven states, $0, \dots, 6$ corresponding to the remainder when the number is divided by 7. The initial state is $0$, which is also the only accepting state.  We adopt the convention that the empty string represents zero (as does the string "$0$", obviously).

To describe the transition function, suppose you're reading in some binary string and the bits you've read so far correspond to the natural number $n$ and the state you're in is $r=n\%7$ (the remainder when $n$ is divided by $7$). Let the next bit be $b\in\{0,1\}$.  When you read that, you'll have seen the number $2n+b$, so you need to move to state

$$r' = (2n+b)\%7 = (2r+b)\%7\,.$$

And, of course, there's nothing special about $7$.


What is the use case of multi-type-parameters generic interface? Previously, I ask a similar question, but the answer given only demonstrates the usage of multiple-type-parameters(MTP) data structure, but not MTP generic interface.

Based on my experience, generic interface is useful for generalizing algorithms. For example, the sorting algorithm can be defined as such:

// Java code

interface Comparable<T> {
    Boolean compareTo(T other)
}

void <T extends Comparable<T>> sort(List<T> elements) {
    // body
}

So, the code above demonstrated the usage of single-type-parameter generic interface.

However, I have not encountered any use case for multiple-type-parameter generic interface up until now.

Thus, I am hoping that some one could provide me some use cases regarding multiple-type-parameter interfaces.

Also, if possible, please explain how multiple-type-parameter could improve some situation.

(For example, the Comparable interface allows the sort function to be generalized, so that one do not need to define multiple sort function for different types of element)

P/S: I ask this question because I am considering whether to include MTP generic interface in my new programming language.

The most typical usecase I've encountered is generic idea of container, parameterized by both the container type and contained type. F.e. you can describe generic type class of containers providing get/set/delete operations for arbitrary types providing hash() operation.

Even more complicated usecase is type+container+monad, involving concrete monad where all update operations on the container occur, but this is mainly interesting in the Haskell realm.


Why does this Pumping Lemma example show irregularity? the first 4 steps of these are my own work - however the following steps are from my book, and I don't understand what it's saying, and I have not found any resources. Could someone clarify this?

Show C = {w|w has an equal number of 0s and 1s} is not regular. Show by contradiction.

1) Assume C is regular, and thus the Pumping Lemma conditions hold.

2) Assume a pumping length of p.

3) Let the string s = $0^p$$1^p$.

4) s = xyz and let x and z be the empty string. Therefor for i > 0, x$y^i$z always has an equal number of 0s and 1s, so it seems like it can be pumped.

5) But since condition 3 of the pumping lemma says that |xy| <= p, then y must consist of only 0s.

How does step 5 justify y consisting of only zeros? If we said ealrier that x and z are the empty strings, then doesn't that imply that s = y = $0^p$ $1^p$?

How does this make y only zeros?

Thanks!

$s$ consists of $p$ zeroes followed by, well, it doesn't matter what. $xy$ is the start of $s$ and consists of at most the first $p$ characters of $s$. All of those $p$ characters are zeroes so, in particular, $y$ is all zeros.

Step 4 of your proof is invalid because you can't choose what $x$ and $z$ are. The pumping lemma tells you that, if $C$ is regular, there is some way of writing every appropriate $s\in C$ as $s=xyz$ such that blah, blah, blah. It doesn't tell you that writing $s=\varepsilon y\varepsilon$ will work.


Are Huffman trees and optimal binary search trees for solving the same problems? Huffman trees are used in a specific application - Huffman coding - for finding the minimum-expected-length binary-coding for a set of strings, with respect to a probability distribution over the string set.

Optimal binary search trees (as defined in CLRS's Introduction to Algorithms) are used for finding the optimal binary search tree for a set of elements, so that the expected look-up time is minimized, with respect to a probability distribution over the set.

Noticing how similar they are to each other, I have some questions

Is it correct that  the applications of Huffman trees are not limited to Huffman coding?

What kinds of problems can Huffman trees be used to solve?

Can Huffman trees be used for solving the same problems that optimal binary search trees can?

Can optimal BSTs be used for solving the same problems that Huffman trees can?
One difference I notice between Huffman trees and optimal binary
search trees is that

In Huffman trees, all the elements are stored in the leaves, so that a successful search always end up in a leaf.
In optimal binary search trees, not all the elements are stored in the leaves, and a successful search may end up in an internal node.

So if Huffman trees and optimal BSTs can both solve a problem, then
is the Huffman tree always higher than an optimal BST, and thus will
the Huffman tree take longer on average to look up an element?

Thanks.

Both Huffman trees and optimal binary decision trees can be though of as mechanisms for playing the (probabilistic) 20 questions game optimally. In the 20 questions game you are given a set of items $X$ and a probability distribution $\pi$ over $X$, and then you are presented an unknown item $x \sim \pi$. Your task is to discover $x$ using the least expected number of questions. The difference lies in which questions are allowed:

In the case of Huffman trees, you can ask any Yes/No questions of your choice.
In the case of BSTs, you can ask a 3-way question of the form "$x < t$, $x = t$, or $x > t$?".

Neither Huffman trees nor binary search trees are described in this way usually. Instead:

Huffman trees can be viewed as a way of coding elements drawn from $\pi$ in a prefix-free way (no codeword is the prefix of another). The code of an element consists of the path that takes you from the root to the appropriate leaf ($0$ for taking a No edge, $1$ for taking a Yes edge).
Binary search trees allow searching $x$ inside a list $y_1,\ldots,y_n$. The answer is either $y_i$ (this corresponds to items stored in internal nodes), or $y_i < x < y_{i+1}$ (this corresponds to items stored in leaves; this includes the cases $x < y_1$ and $y_n < x$).

This should answer most of your questions.


Transform 2D range query matrix into segment tree to make memory usage lower Let's say we have given matrix $N\cdot N$, with zeros and ones only at $P$ position at it. We want to implement queries $q(x_1, y_1, x_2, y_2)$ which will return the number of ones in the sub-rectangle described with those two points. Since $N$ can be up to $10^4$ we cannot create standard DP matrix for answering the queries in $O(1)$. Is it possible to answer such queries without generating the DP matrix?

You could use a quadtree or kD-Tree. They are multidimensional indexes (your case only needs 2D) that perform insertion, deletion and window queries (rectangle defined by two coordinates) in $O(log (n))$.

In your case you would simply insert all coordinates/cells with '1' into the quadtree/kd-tree. Then you can perform a window query that returns all '1' in a given rectangle. For example, to define a '1' at $(3,7)$:

KDTree<Boolean> tree = new KDTree<>(2); //2 dimensions
tree.put(3, 7, 1); //You could ommit the '1', since all entries will have a '1'.

To perform a query between $(1,1)$ and $( 4,6)$:

Iterator<Entry> iter = tree.query(1,1,4,7);

The iterator contains a sequence of Entries, where each entry has coordinates and a value, such as '1'. The example should return exactly one Entry for $(3,7)$. The syntax will differ between implementations, but they should all be similar.

Be aware that this is only useful if $N$ is large and $P$ is small, because there is some storage overhead.

There are example implementations all over the web, also referenced from the Wikipedia pages. I also have my own Java implementations here, however, they are implemented to work with any dimensionality and take any Object as values so they are a bit overkill if you just use 2D and only store boolean 1/0.


Binary strings such that the sum of 0's is not equal to twice the sum of 1's Construct a context-free language for $L=\{w\in \{0,1\}^* \mid n_0(w)\not= 2n_1(w)\}$. Here $n_b(w)$ is the number of $b$'s in $w$.

I can construct a CFL in the case $n_0(w)=2n_1(w)$, but I have no idea how to construct it when they are not equal, considering that CFL is not closed under complement operation.

Distinguish $n_0(w) < 2n_1(w)$ and $n_0(w) > 2n_1(w)$. That is, in your grammar for $n_0(w) = 2n_1(w)$ either generate extra $0$ or (in a separate half of the grammar) extra $1$.


How to generate all $n$-bit numbers with certain bits fixed? Consider the example where $n = 4$, bit 0 is fixed at 1, and bit 2 is fixed at 0. I would like to generate all $n$-bit numbers with those bits fixed. Essentially, everything I generate would have the form:

$$1*0*$$

where $*$ represents a bit that can vary. The fixed bits can be in arbitrary positions, and there can be arbitrarily-many of them (anywhere from 1 bit fixed to $n-1$ bits fixed). Ideally, I would prefer these to be generated in lex order; what I'm looking to generate for the example case would be:

$$1000, 1001, 1100, 1101$$

I've only found solutions for doing something like this when specific bits are set to 1 - my question is more general, as it allows bits to be set to 0 or 1. What is a good algorithm (in terms of simplicity and efficiency) to do this for arbitrary $n$?

Practically speaking, here is one thing you could try:

Make a list $A[1],\ldots,A[m]$ of powers of two corresponding to free bits.
Generate a list of all XORs of elements from $A[i]$ (in the correct order), XORed to a mask consisting of the fixed bits.

If you don't care about the order, then an efficient way to generate the list is using a Gray code. Otherwise, you could use a recursive procedure.


Problem with understanding the lower bound of OPT in Greedy Set Cover approximation algorithm From what I know of analyzing and designing approximation algorithms, we need to find a lower bound on the optimum (in the case of minimization). For example if our solution is greedy ($SOL_G$) and if we find a lower bound $L_B$ on $OPT$ then $$L_B \leq OPT$$

and if we correctly analyze the following $$SOL_G \leq f . L_B$$ Then we can conclude that $$SOL_G \leq f. OPT$$ where $f$ is the approximation factor of our greedy solution.

Vijay Vazirani in his book approximation algorithm on page 16 proposed the Greedy Set cover and his analysis of the lower bound on the optimum (Lemma 2.3). I have problem with understanding this Lemma:

From his convention at the beginning of the book, $OPT$ stands for the optimum solution of the problem instance (not the optimum that is obtained by the approximation algorithm).

At the beginning of the Lemma he says

  In any iteration, the leftover sets of the optimal solution can cover the remaining elements at a cost of at most OPT

It is clear because $\sum_{e \in U} price(e) = OPT$. (The price assignment is based on the selection of the sets)

In the next sentence he says

  Therefore, among these
  sets, there must be one having cost-effectiveness of at most $OPT/|\bar{C}|$ where $\bar{C} = U - C$

and $C$ is the current list of selected sets.

I can't understand, why is it true? $OPT$ is the optimum of problem instance not the algorithm. Because in the algorithm the price of each set is distributed among its elements, it seems he uses this fact but $OPT$ is not about the algorithm! it is the optimum of problem instance

Thanks.

Let's assume for simplicity that $C = \emptyset$; I'll let you work out the general case. Note that there are at most $|U|$ sets in OPT. Let $OPT = \{O_1,\ldots,O_m\}$, where $m \leq |U|$. We have
$$
\sum_{i=1}^m \frac{c(O_i)}{|O_i|} \frac{|O_i \setminus (O_1 \cup \cdots \cup O_{i-1})|}{|U|} \leq \sum_{i=1}^m \frac{c(O_i)}{|O_i|} \frac{|O_i|}{|U|} = \frac{OPT}{|U|}.
$$
On the left-hand side we have a weighted average of the quantities $c(O_i)/|O_i|$, so one of them must be at most $OPT/|U|$. The greedy algorithm selects a set $S$ with $c(S)/|S|$ minimal, so in particular
$$
\frac{c(S)}{|S|} \leq \min\left(\frac{c(O_1)}{|O_1|},\ldots,\frac{c(O_m)}{|O_m|}\right) \leq \frac{OPT}{|U|}.
$$


Indexing Edge Permutations for the Rubik's Cube I'm working on a Rubik's Cube solver that implements Korf's algorithm, as published in his 1997 paper, Finding Optimal Solutions to Rubik's Cube Using Pattern Databases.  His method involves creating three pattern databases: one for the 8 corner cubies; one for 6 of the 12 edge cubies; one for the remaining 6 edges.

My question is about indexing the permutations of the edge pieces.  Mind you, each edge can be oriented in one of two ways, but my questions is not about the orientations, only the permutations.

With 6 edge positions and 12 edge cubies that could occupy them, there are 665,280 possible permutations (12 pick 6, or 12! / 6!).  For simplicity sake, let's say the edge cubies are numbered 0-11.  The 6-element partial permutations of these 12 cubies in lexicographical order is thus (0 1 2 3 4 5), (0 1 2 3 4 6), (0 1 2 3 4 7), ... (11 10 9 8 7 6).  Is there an efficient way to index those permutations?  Sequential indexing would be preferred, although that may not be possible.

One thought I had is to simply iterate through all 665,280 permutations and store the associated index.  That's doable, although it's rather memory intensive.  I'm looking for more of a minimal perfect hash approach.

For example, I have the indexing for the 8 corner cubies figured out.  For the 8 corner cubies, the Lehmer code for each permutation can be computed, and then that Lehmer code can be converted to a sequential index.  Korf describes how to do this in his 2005 paper, Large-Scale Parallel Breadth-First Search.  However, that paper does not address indexing partial permutations.

Related questions:

Indexing into a pattern database - Korf's Optimal Rubik's Cube solution
https://math.stackexchange.com/questions/97813/a-positional-number-system-for-enumerating-fixed-size-subsets

The Lehmer code is easily adapted. Instead of using $\binom{n}{k} = \frac{n!}{k! (n-k)!}$, which counts unordered subsets, use $\frac{n!}{(n-k)!}$, which counts ordered subsets.

In Python:

from functools import reduce
from operator import mul

def falling_factorial(n, k):
    return reduce(mul, range(n-k+1, n+1), 1)

def lexicographic_rank(n, perm):
    if len(perm) == 0:
        return 0

    a = perm[0]
    return a * falling_factorial(n - 1, len(perm) - 1) + \
        lexicographic_rank(n - 1, [i if i < a else i - 1 for i in perm[1:]])

Online demo


Is the outer loop in typical bubble sort algorithm precise? I analized  the bubble sort algorithm and I cannot see why they "implemented this way". I wrote down the results as the two loops performed their works and, with my small testing arrays, the outer loop condition to stop was always too much (the array was sorted when "i" was like 2, when the loop conditon to stop was 5.

this.bubbleSort = function(){
     var length = array.length;

      for (var i=0; i<length; i++){ //this loop seems too much

         for (var j=0; j<length-1; j++ ){

            if (array[j] > array[j+1]){

               swap(array, j, j+1);
               }
             }
           }
        };

Is there a possibility that the outer loop will have to reach its limit?  I mean the "i - 1 < length" will be necessary to sort. Is the array length on the outer loop really a precise choice or just a good choice, because it gives a clue of how many inner loop iterations will be needed with some leftover if necessary?

For me it means that the algorithm could be written, somehow, like this

var length = array.length;

  for (var i=0; i< 10; i++){ //I used 10 instead of the array length

     for (var j=0; j<length-1; j++ ){

        if (array[j] > array[j+1]){

           swap(array, j, j+1);
           }
         }
       }
    };

Let's assume that the input has is a reversed array like  a = 5 4 3 2 1.
every iteration of the outer loop all the 5 - 1 - i smallest elements will be shifted one cell to the right(i is zero in the first iteration) and the 5 - i th element will be moved to the 5 - i th cell. as one can see it takes 4 iteration to sort this.

at every iteration of the outer loop, the n - i th element will be moved to the n - i th cell so it will take at most n - 1 iteration and the worst case (descending array) will always take that many iteration ( the last element will be sorted by itself).


Reduce PDA for a given language I drew a Push-down Automata, accepting the following language:
$$
\{ xcy : x,y \in (a+b)^*, \#_a(x) > \#_{bb}(y) \}.
$$
Here $\#_{bb}(y)$ counts the number of times that $bb$ appears in $y$, with overlaps. For example, $\#_{bb}(bbb) = 2$.
My question here. Is it possible to reduce my PDA to less states? Thanks.

Yes. You can obtain a PDA with only one state by "encodng" the state of your PDA into the stack of the new PDA. See this document.


What's a trivial property? I have to show a property P is trivial.

This problem has to do with Rice's Theorem, which I do not completely understand. Can someone explain the difference between trivial and non-trivial properties?

A "trivial" property is one that holds either for all languages or for none.


Connecting strings in a graph is a PSPACE problem We define the following problem as:

Let $M$ be a TM with alphabet $\Gamma$, with $\{a,b,$ #$\} \subset \Gamma$.

We define, for every natural number $n$ the graph $G_{M,n}$ by:

$V_{M,n} = \{a,b\}^n$, the vertices

$E_{M,n} = \{(x,y) : x,y \in V_{M,n} $ and  $M$ accepts the string $x$#$y$ with a run that requires at most $n^{73}$space$\}$

Now define the following language $L$:

$L = \{(<M>, x, y) : x,y \in \{a,b\}^*, |x| = |y|$ and $x,y$ are connected by a path in the above graph$\}$

I want to show $L \in PSPACE$, without using Savitch's theorem.

My attempt:

Define the following algorithm $M_0$

On input $(<M>, x, y)$ with $M$ with the above requirements:

Check if $M$ accepts the string $x$#$y$ in space $|x|^{73}$ or less; if so accept, else go to step 2.
Keep track of the set $Strings = \{x,y\}$ as a second tape.
For every string $z \in \{a,b\}^{|x|} - Strings$, add $z$ so $Strings$ and run $M_0$ on

a. $(<M>, x, z)$

b. $(<M>, z, y)$

If both accept, accept. If all strings in $\{a,b\}^{|x|}$ have not yielded accept, reject.

Now I think it's rather obvious that $L(M_0) = L$ but I'm unsure it solves it in poly. space:

Step 1. requires computing $|x|^{73}$ in unary, which takes poly. space in $|x|$. From here it is known that testing whether a machine accepts a string in some specific space, given in unary, is possible in poly. space when that unary representation is given in the input, using a universal machine. So step 1. requires poly. space in $|x|$.

Each step of the recursion in 2. requires keeping track of the strings tried which is fine. But the depth of the recursion seems to be $2^{|x|}$ which is problematic.

Can you suggest if this solution may still work, or a hint for another?

You say that you need to solve this "without Savitch", but what you're doing is (almost) implementing Savitch's proof within your algorithm.

That's perfectly fine, of course, as long as you're aware of that.

As for the space analysis of your algorithm - indeed, you present an exponential-space algorithm, in particular because you keep track of an exponential number of strings.

Consider the following change: in your subroutines (in the recursion), instead of limiting the set of vertices you're allowed to visit, how about limiting the number of steps you're allowed to take?

That is, define the subroutine that takes $<M>,x,z,t$ and checks whether $z$ is reachable from $x$ within $t$ steps, with $t$ encoded in binary.

Then, in the recursion, you can divide $t$ by $2$ at each step, thus obtaining a polynomial recursion depth.

This is, in fact, exactly how we prove Savitch's theorem, so it's no surprise that it works...


Given $L$ and $D$ find $X, \text { such that } X * 10^L + D \equiv 0 \mod M$ Given $L$ and $D$ find $X, \text { such that } X * 10^L + D \equiv 0 \mod M$. Integer $M$ is given and it is the same for all calculations however we need to solve for $X$ for more different numbers.  One important thing that we know is that $\gcd(M, 10) = 1$.

I rewrited the equation in this type:
$X * 10^L \equiv M - D \mod M$. If $M$ was prime number we could just multiply $M-D$ by $(10^L)^{M-2}$. However $M$ might be arbitrary integer. How can we use the fact that $\gcd(M, 10) = 1$

Since $10$ is relatively prime to $M$, it has an inverse modulo $M$, which can be found efficiently using the extended GCD algorithm. So you can simply calculate $X = -10^{-L}D$ (all computations modulo $M$).


What is the time complexity of finding the FIRST and FOLLOW sets? Given how important these are for parsing, I'm surprised I wasn't able
to find anything about their complexity. I'm interested in all combinations of:

What is the (edit: best known) time complexity of calculating
<FIRST | FOLLOW | FIRST and FOLLOW> of a <single | all> nonterminals of a <context-free | LR> grammar?

Links to resources or partial answers are welcome.

$\mathbf{first}_1$ and $\mathbf{follow}_1$ as relations over the symbols of a grammar $\mathcal{G}$ can be computed for a given non-terminal in $\Theta(|\mathcal{G}|)$, wnere the size of $\mathcal{G}$ is defined in a an intuitive way (basically, the sum of the lengths of the productions).

It's clear that $|\mathcal{G}|$ is a lower limit since no algorithm could work without considering every symbol of every production of the grammar. An algorithm which takes time linear to the size of the grammar (with a proof of time complexity) is provided in section 5.5 of Parsing Theory, Vol. 1 (S. Sippu & E. Soisalon-Soininen, 1988). (If $k\gt 1$, a polynomial term is introduced because of the size of the $FIRST_k$ sets.)

Thus, to compute the entire relation requires $O(|\mathcal{G}|\cdot|T|)$, where $T$ is the set of terminal symbols in $\mathcal{G}$. The $|T|$ factor (which could, in the worst case, be $O(|\mathcal{G}|)$) is the result of having to perform set union operations on sets of up to $|T|$ elements. In practice, there is no advantage to attempting to compute the $FIRST$ and $FOLLOW$ sets for an individual non-terminal; there is a lot of overlap in the individual computations.

These results were not new; the bibliography credits Donald B. Johnson & Ravi Sethi (1976) A characterisation of LL(1) grammars, but a paywall impedes my verification. The algorithms are also cited in Hunt, Szymanski & Ullman (1977) Operations on Sparse Relations, which refers to a 1974 paper by the same authors, with roughly the same name (paywalled, but you might be able to find it).

By way of a side note, the framework of relational expressions developed and used by Sippu & Soisalon-Soininen throughout the two volumes of Parsing Theory is a thing of beauty which for me was sufficient to justify my investment in the textbook. But you might be able to find it in a good academic library.


Prove complexity bound without reduction? The most common method of proving that some problem, P, is at least as difficult as some other problem, Q, is to demonstrate that Q can be solved in terms of P (with the usual caveats for the complexity of the reduction itself).

In particular, I'm thinking about the fact that breaking RSA encryption is believed to be at least as difficult as factoring a composite number into primes, but nobody has ever figured out how to express prime factorization in terms of RSA decryption. My question is: if somebody wanted to go about proving that breaking RSA is at least as difficult as prime factorization without relying on reduction, what techniques might be available to them?

As mentioned on Wikipedia, there is no known proof that breaking RSA is at least as difficult as prime factorization -- and there are reasons to believe it might not be.  In other words, we don't currently expect any such proof to exist.  See the reference listed in Wikipedia.


What is the big-$\Omega$ complexity of Fermat's Little Theorem? Fermat's Little Theorem states that if an integer $n$ is prime them
$$
a^n \equiv a \pmod n \hspace{10mm} (*)
$$
for any $a \in \mathbb{N}$

My question is, is it correct to say that testing $(*)$ for some given $a$ has complexity $\Omega (n)$, since we would have to calculate $a^n$ which would require $n$ (multiplication) operations?

Additionally, what is the big-O complexity of testing this congruence?

Modular exponents can be computed efficiently using repeated squaring. This is a recursive method (which can also be implemented iteratively) that relies on the following two identities:
$$
a^{2k} = (a^k)^2, \qquad a^{2k+1} = a(a^k)^2.
$$
This allows us to give a recurrence for $f(a,b,n) = a^b \bmod n$:
$$
f(a,b,n) =
\begin{cases}
1 & \text{if } b = 0, \\
f(a,b/2,n)^2 \bmod n & \text{if $b$ is even}, \\
af(a,(b-1)/2,n)^2 \bmod n & \text{if $b$ is odd}.
\end{cases}
$$
This shows that $a^b \bmod n$ can be computed using $O(\log b)$ many multiplications. Since we keep reducing modulo $n$ in each step, each of these multiplications takes time polynomial in $O(\log n)$ (naively, $O(\log^2 n)$, but this can be significantly improved using fast integer multiplication methods). In total, we obtain an algorithm running in polynomial time.


Tile Problem : Dynamic Programming Came across the following tile problem :

Given a “2 x n” board and tiles of size “2 x 1″, count the number of ways to tile the given board using the 2 x 1 tiles. A tile can either be placed horizontally i.e., as a 1 x 2 tile or vertically i.e., as 2 x 1 tile.

Recurrence formula is as mentioned below :

count(n) = n if n = 1 or n = 2
count(n) = count(n-1) + count(n-2)

Explanation is as follows :

count(n-1) : If the first tile is placed vertically, then problem reduces to a grid of size "2 x (n-1)"
count(n-2) : If the first tile is placed horizontally, then problem reduces to a grid of size "2 x (n-2)", because we will need to place two tiles horizontally one above the other

But my doubt is, the above recurrence is fine if we always place the tiles at the left most side of grid. What if I place the first vertical tile at center of grid instead of the left most. Should not be covering all the permutation and combinations possible on basis of where we place the first tile?

Your understanding of reducing the given problem to a subproblem is flawed. Say you have to place the tiles, if you start from the centre and keep on placing the tiles, finally the arrangement  you have can also be obtained by placing tiles from the left hand side.  You don't want to double count. So the recurrence relation you mentioned is correct.


Loop invariant initialisation confusion Consider the algorithm LastMatch below, which returns the offset (shift) of the last
occurrence of the pattern P in text T, or -1 if P does not occur in T:

LastMatch(T,P)
 for(s = T.length - P.length downto 0)
   j = 1
   while(j =< P.length and P[j] == T[s + j])
     j++
   if(j == P.length + 1)
     return s
 return -1

I've been given a loop invariant for the while loop:

$\forall k(1 \leq k<j \rightarrow P[k] ==T[s+k])$

The initialisation of this invariant confuses me. Before we enter the while loop, $j=1$. So we're asking is there a $1\leq k<1$ such that $P[k] ==T[s+k]$?

I cannot find a $k$ which satisfies this inequality, so I do not understand what this is saying. So why is the invariant satisfied before we enter the loop? Is it because when I cannot find a $k$ it implies that $P[k]$ and $T[s+k]$ are both equal to the empty set?

An implication is true if the antecedent is false.

If j is 1 then the antecedent is false no matter what k you choose, which means that the implication is vacuously true for every k. So the assertion is true.


Undecidable predicate logic is decidable by people? Logic in computer science (By Michael Huth,Mark Ryan, second edition, page 132) says

  Every φ can, in principle, be discovered to be valid or not, if you
  are prepared to work arbitrarily hard at it; but there is no uniform
  mechanical procedure for determining whether φ is valid which will
  work for all φ.

For me, it sounds contradictory because I take your ability to decide any formula as a uniform mechanical procedure. If you can do it, then you have a uniform mechanical procedure. What do I fail to understand?

Just to be clear what validity means here, the discussion happens in the context of validity definition:

  Given a logical formula φ in predicate logic, does ⊨ φ hold, yes or
  no?

The author is incorrect. A consequence of Godel's incompleteness is that any sufficiently complex logic has statements that are true, but have no proof of truth.

If every statement had a proof or disproof, then we could iterate through all strings, check if it was a proof or disproof, and eventually we'd find one, making logic decidable. We know that this isn't the case, since this could solve the halting problem.

In the context of your question, this means there are valid formulas with no proofs of validity.

Humans have an excellent set of heuristics for proving things. We are good at seeing patterns and incorporating past knowledge. But ultimately we can't find proofs that don't exist.


Minimum index Array Product Given an array A(1 indexed based) of positive  integers.For each element A[i] find the minimum index (say idx) such that the product of all the elements from index 1 to idx is divisible by A[i].where(1<=idx<=i).

constraints are: the number of elements of the array 1<=n<=10^5 and

1<=A[i]<=10^5.

For example let A[]={2,4,6,8}

The output should be {1,2,3,2}

I could only think of O(n^2) solution but that gives a T.L.E.

I also looked up to the code of successfully accepted solution but could not understand the logic.I only understood that it is first calculating the smallest prime factor using seive and then calculating the prime factors of each A[i] using its smallest prime factor.However I am not able to understand the later part of the solution.

Here is the code of one of the accepted solution.

int main() {

ll n,arr[500001],minP[500001];
cin>>n;
for(int i=0;i<n;i++){
    cin>>arr[i];
}
for(int i=2;i<=500000;i++){
    minP[i]=i;
}
for(ll i=2;i*i<=500000;i++){
    if(minP[i]==i){
        for(ll j=i*i;j<=500000;j+=i){
            minP[j]=min(minP[j],i);
        }
    }
}
vector<ll> v[500001];
for(int i=0;i<n;i++){
    ll temp = arr[i],mx=0;
    while(temp>1){
        v[minP[temp]].push_back(i);
        temp/=minP[temp];
    }
    temp = arr[i];
    while(temp>1){
        ll x=minP[temp],cnt=0;
        while(temp%x==0){
            temp/=x;
            cnt++;
        }
        mx=max(mx,v[x][cnt-1]);
    }
    cout<<mx+1<<" ";
}

}

Also,Suggest me some relevant material to understand the underlying concept used above.

Here I have tried to implement the solution using binary search can anybody point the error as I am still getting the wrong answer upon submission.

 void Bsearch(int low,int high,int key,long long product[])
    {

    int ans;
    int mid;
    long long midVal;
    while (low <= high)
    {
    mid = low + (high - low + 1) / 2;
    midVal = product[mid];

    if (midVal% key!=0)
    {
        low = mid + 1;
    }
    else if (midVal%key==0)
    {
        ans=mid;
        high=mid-1;
    }
}
     cout<<ans+1<<" ";
}
  int main()
  {
int n;
cin>>n;
int arr[n];
long long product[n];
int i;
for(i=0;i<n;i++)
cin>>arr[i];
product[0]=arr[0];
for(i=1;i<n;i++)
product[i]=product[i-1]*arr[i];//prefix product array
for(i=0;i<n;i++)
{
    int temp=arr[i];
    Bsearch(0,n-1,temp,product);//Using binary search to find the minimum
                                  index.
}
}

Here's a simple $O(n \log n)$ solution if multiplication and the modulus operator is always assumed to be $O(1)$ (which is a big assumption -- see the note at the end).

Create a new array, $B$, in which the first element is $A[1]$ and every future element at index $i \in 2..n$ is $A[i] * B[i-1]$. This gives you an array of all "partial products".

This array is nondecreasing, and $B[j]$'s factors are a superset or $B[i]$'s factors whenever $i < j$. Therefore, for any $A[i]$ (or even for every integer $k$), you can use binary search to find the smallest index $i$ for which $k$ divides $A[1] * A[2] ... * A[i]$. This takes $O(\log n)$ time per lookup, or $O(n \ log n)$ in total for all of $A$.

--

Regarding the initial assumption. As it turns out, assuming arithmetic operations can be done in constant time gives you a bit more power than what most people consider reasonable. For example, one can factor arbitrary integers in polynomial time under this assumption, by constructing pathologically large multiplications/divisions that let them "carpool" many different operations into one. Do you know which cost model we are operating under?


Is there any count-preserving cellular automata which tends do "10101010..."? Suppose that I have a bit string of finite length. Is there any bit rewriting rule rewrire :: (Bit,Bit,Bit) -> (Bit,Bit,Bit), that doesn't change the total count of 1s on the bit string, and that when applied to arbitrary triplets in any order will converge to a bit string that will begin with an arbitrarily long sequence of 10, followed by either all 0s or all 1s.


building NFA for { a^p; p is a prime number, m is a fixed number and m >p >0 } $\{a^p; p$  is a prime number, $m$ is a fixed number and $m\geq p \geq 0 \}$
I know this is regular since it is finite, but I don't understand how to build an NFA for this if we do not know what $m$ is. Is there a way to draw the NFA regardless?

Your DFA has states $S_0$ to $S_m$ and E. You start at state $S_0$.
Any state transitions to E if the next input symbol is not a. States $S_m$ and E transition to state E on any input; state $S_i$ for 0 ≤ i < m goes to state $S_{i+1}$ on input a.
$S_i$ is an accepting state if and only if i is a prime. All other states are non-accepting.


How much can we reduce the number of clauses by converting from $k$-SAT to $(k+m)$-SAT? If we suppose that we start with an instance of $k$-SAT, and try converting the problem to an instance of $(k+m)$-SAT, where there are $(k+m)$ literals per clause, can we guarantee a reduction in the total amount of clauses?

I realized after posting that we can't guarantee that the number of clauses can be reduced.  However, I wonder if we have $n$ clauses, could we get something like $n/k + O(1)$ clauses by some "reduction" technique?

If so, how much can we guarantee the total number of clauses can be reduced by? For instance, if we start with $k$-SAT with $n_k$ clauses, what is the smallest guaranteed $n_{k+m}$, the new amount of clauses, that will result if we convert this instance to $(k+m)$-SAT?

More importantly, how do we carry out this conversion?

One type of conversion is simply the reverse of the k-sat-to-3-sat conversion:

Recall, the conversion of k-sat to "j"-sat, $j<k$:

$$\begin{eqnarray*}
&& (x_1 \vee x_2 ... \vee x_j \vee ... \vee x_k)\\
\rightarrow && (x_1 \vee x_2 ... x_j \vee d)
               \wedge (\overline d \vee x_{j+1} \vee x_{j+2} ... x_k)\\
\end{eqnarray*}$$

Here, $d$ is a dummy variable, which means something like "This clause isn't true, but another clause I know is". The other clause being the next clause that was split off of the original. The above is an example where $2j \geq k$, otherwise the 2nd split node will still be larger than $j$, and we must split that one again, in the same way.

Reversing the conversion

$(x_1 \vee x_2 ... x_j)
 \wedge (\overline x_j \vee x_{j+1} \vee ... x_k)$ then you can combine the clauses into:

$(x_1 \vee x_2 ... x_{j-1} \vee x_{j+1} \vee x_{j+2} \vee ... x_k)$

Notice the missing $x_j$ in this new formula.

Of course, you aren't guaranteed to find clauses like this in an arbitrary formula so the smallest guaranteed $n_{k+m}$ is equal to $n_k$.

However, on ordinary formulas, a variable and its negation will appear in the formula; otherwise you can perform pure-literal-elimination (described here). For simplicity, lets also assume that $k+m \geq 2k-2$. Then we can combine any two clauses that contain a literal in one and its negation in the other. Since every literal should have another clause with a negation, one can empirically guess that you should be able to approximately halve the number of clauses (you might get stuck with some literals and their negations in already joined clauses, and thus you will be stuck with some unjoinable clauses at the end; optimally joining clauses like this might be another interesting problem).

EDIT:

After reflection, I realized that $x_j$ must be free and not used elsewhere in the formula in order to collapse the two clauses that it belongs to. Therefore, these type of clauses (one containing a literal, and the other its negation, with this literal not being used elsewhere in the formula) is much rarer than I previously thought above. So the real answer is, there is no guarantee of how much we can reduce the number of clauses in the formula.


Prove that if you can derive w from α in n steps, it's possible with n left-derivations as well My university's automata theory book claims that the following claim can be proved by induction but it doesn't bother showing the proof.

I've tried to prove it myself but I got stuck at the Inductive Step.

Let $G=(V,T,P,S)$ be a context free grammar.

Prove by induction on $n$ where $n\geq 1$ that:

For every $w\in T^*$ and for every $\alpha\in (V\cup T)^+$ , if $\alpha \Rightarrow^n w$ then $\alpha \overset{_{lm}}{\Rightarrow}^n w$

I.e

$\forall w\in T^*, \forall \alpha\in (V\cup T)^+, \alpha \Rightarrow^n w \rightarrow \alpha \overset{_{lm}}{\Rightarrow}^n w$

(The leftmost derivation relation is denoted as $\overset{_{lm}}{\Rightarrow}$)

(From a high level point of view the claim says that if some terminal word $w$ can be derived form $\alpha\in (V\cup T)^+$ then there exist a leftmost derivation to derive $w$ from $\alpha$)

My try:

Basis

If $n=1$ then we must show that $\forall w\in T^*, \forall \alpha\in (V\cup T)^+, \alpha \Rightarrow^1 w \rightarrow \alpha \overset{_{lm}}{\Rightarrow}^1 w$:

Let $w\in T^*$ and let $\alpha\in (V\cup T)^+$ such that $\alpha \Rightarrow^1 w$.

by definition of the $\Rightarrow$ relation we get that:

$\exists \psi,\chi,\gamma\in(V\cup T)^*, \exists A\in V, \alpha = \psi A \chi \land w=\psi \gamma \chi \land (A\rightarrow \gamma)\in P$

Now since $w\in T^*$ and since $w=\psi\gamma\chi$ we get that $\psi \in T^*$ and so:

$\exists \psi\in T^*,\exists \chi,\gamma\in(V\cup T)^*, \exists A\in V, \alpha = \psi A \chi \land w=\psi \gamma \chi \land (A\rightarrow \gamma)\in P$

And we get by definition of $\overset{_{lm}}{\Rightarrow}$ relation that $\alpha \overset{_{lm}}{\Rightarrow} w$ as was to be shown.

Induction hypothesis

Suppose that for some $n=k\geq 1$ we get: $\forall w\in T^*, \forall \alpha\in (V\cup T)^+, \alpha \Rightarrow^k w \rightarrow \alpha \overset{_{lm}}{\Rightarrow}^k w$

Induction step

Now we'll prove that: $\forall w\in T^*, \forall \alpha\in (V\cup T)^+, \alpha \Rightarrow^{k+1} w \rightarrow \alpha \overset{_{lm}}{\Rightarrow}^{k+1} w$

Let $w\in T^*$ and let $\alpha \in (V\cup T)^+$ such that $\alpha \Rightarrow^{k+1} w$,
And so we get that $\exists \beta \in (V\cup T)^*$ such that $\alpha\Rightarrow\beta\Rightarrow^k w$. Since $k\geq 1$ we get that $\beta \in (V\cup T)^*V(V\cup T)^*$ and so $\beta\in(V\cup T)^+$.
Now since $w\in T^*$ and since $\beta \Rightarrow^k w$ we get by the induction hypothesis that $\beta \overset{_{lm}}{\Rightarrow}^k w$

Now I do not know how to proceed.

I got that $\alpha \Rightarrow^1 \beta$ but how can I show that $\alpha \overset{_{lm}}{\Rightarrow}^1 \beta$ and from there conclude that $\alpha \overset{_{lm}}{\Rightarrow}^{k+1} w$ using the facts I've shown above?

thanks for any help.

Your method of proof can't work, since it implies that every derivation is a leftmost derivation. Indeed, here is a paraphrase of your proof:

  Let's prove by induction on the length of the proof that if a word $w$ can be derived from a sentential form $\alpha$ in $n$ steps, then $w$ can be derived from $\alpha$ in $n$ steps using a leftmost derivation.
  The case $n = 0$ is trivial.
  Now suppose that $n > 0$, and suppose that the first step of the derivation is $\alpha \Rightarrow \beta$. By induction, $\beta \Rightarrow^* w$ can be converted to a leftmost derivation of length $n-1$, so $\alpha \Rightarrow \beta \Rightarrow^* w$ would be a leftmost derivation of length $n$.

Unrolling the proof, your suggested derivation is actually the same as the original derivation (prove it by induction!), and since not all derivations are leftmost, since can't work.

Concretely, consider the derivation $AB \Rightarrow Ab \Rightarrow ab$. The first step $AB \Rightarrow Ab$ cannot belong to a leftmost derivation. Answering your question, you can't prove that $\alpha \stackrel{lm^1}{\Rightarrow} \beta$, simply because it isn't true.

Here is a different approach. Consider the derivation tree used to derive $\alpha$ from $w$. Try to use this tree to generate a leftmost derivation. Note that the length of the derivation is exactly the number of nonleaf nodes in the tree.


Is there any way to get "around" the halting problem? As I understand it, one proof of the Halting Theorem is done by contradiction; we assume we have program X which can determine if any program terminates. We input program X into program X (with some modifications at the output), and we arrive at a contradiction. However, is it possible for a program Y to exist, where program Y can determine if any program (except variants of Y itself, or most loosely any finite set exceptions) halts?

If the set of exceptions must be infinite, can we have at least the set of permissible inputs be infinite itself?

Please try to keep the answers at a lower level, I know a little bit of mathematics but I am a complete layman in computer science.

Say that two programs are equivalent if they have the same halting behaviour and output on every input.  The problem for your "finite exceptions" idea is that there are infinitely many programs equivalent to any program you choose.  Given a program $P$, we can always modify it in infinitely many ways without changing its output or halting behaviour: for each natural number $n$, we can write a program that essentially counts to $n$ and then runs $P$.

I suppose the good news is that this means we can decide the halting problem on an infinite class of programs. For example, let $P_n$ be the program for i = 1 to n do [nothing]; halt;: the halting problem is easily decidable on the set of all programs $P_n$.


Example of height-balanced tree that is not weight-balanced Following this question : Two definitions of balanced binary trees

I am having a hard time making sense of the proofs provided and I'm looking for an example of a simple binary tree that is height-balanced but not weight-balanced.

This would mean that we could clearly see the height differences of two sub-trees being more than one while the maximum depth difference of any two leave nodes would never be more than one.

Does such an example exist?

EDIT: This question was asked because I misunderstood the inner-node concept. I was looking for a tree example where the height of two sub trees differed by more than one while the the maximum depth and minimum depth had a difference of no more than one.

Take a complete binary tree of height 2 (with 7 vertices), and add two children to the two left leaves. The tree is height-balanced but the root is not weight-balanced.


Numerical ratio between the length of a string and the transited states If we have a finite automaton that accepts a string,

is there any numerical relationship that always is true like S ≥ |w| or something similar?

Where |w| the length of the string and S the number of transited states (counting multiplicities).

For example, if we have this automata and the string w = 010 :

S = 3 and |w| = 3.

In this case, S = |w|

I'm new in computer science and i was thinking there has to be a rule of that kind but I have not found explicitly in the books that I started on computational theory.

The way you have defined S, we will always have $S \ge |w|$.  Why?  Because each time the automaton reads one symbol from $w$, it follows one transition and visits the state at the end of that transition, incrementing $S$ by one.  In other words, we add one to $S$ for each symbol in $w$.  Thus $S$ is at least as large to the number of symbols in $w$.  (It might be larger if you follow $\epsilon$-transitions, as they don't consume any symbols in $w$ but do visit a state.)

Try working through a few examples and it should become clearer.