Why do we need the valid-invalid bit in a page table? I'm reading about memory management in Operating System Concepts, by A. Silberschatz. The author says:

  [...] the user process by definition is unable to access memory it does not own.
  It has no way of addressing memory outside of its page table, and the table
  includes only those pages that the process owns.

Then, the author explains the need of having a valid-invalid bit:

  One additional bit is generally attached to each entry in the page table: a valid–invalid bit. When this bit is set to valid, the associated page is in the process’s logical address space and is thus a legal (or valid) page. When the bit is set to invalid, the page is not in the process’s logical address space.

Why do we also need a valid-invalid bit, if a process is by definition able to access only memory addresses stored in its own page table?

The two quoted sentences appear to be contradictory, in my opinion. There must be something I am missing here.

This exact same question has been already asked a few times;
however, none of the answers clarified my doubt. Source:

What’s the purpose of having valid-invalid bits in page table?
Valid-invalid bit in a process page table
What is the need for valid/invalid bit in paged memory technique?

The answers that other users have given don’t explain why the validity bit is needed to protect address spaces. The page table of a process contains only those pages that are valid for that process (i.e., that the process actually owns), so why do we need to replicate a security feature that is already present thanks to the way the page table is implemented?

As David Richerby says, it’s not clear what you don't understand.
Most of my answer here has already been presented in answers (or comments)
to the questions you linked to.

I’ll admit, though, that the Operating System Concepts book
is probably not as clear as it should be.

The book (going back to Figure 8.6
(Hardware support for relocation and limit registers) on page 361)
suggests that the processor knows the maximum user virtual address
for a context (process),
so if the process tries to access an address above this limit,
the access fails with an addressing error.
This concept seems to erode over the following pages;
for example, Section 8.4.2 (Segmentation Hardware) (pages 365 and 366)
introduces a limit field in each segment table entry,
but waves its hands over the question
of specifying the maximum virtual address
(and, correspondingly, the length of the entire segment table).

I would argue that Figure 8.9 (Example of segmentation), on page 367:

            [images copied from this 944-page PDF of the book]
adds to the confusion:

It’s clearly not to scale.
It says that Segment 0 is 1000* bytes long — both explicitly,
in the segment table, and in the map of physical memory $(2400-1400=1000)$.
Likewise, it says that Segment 4 is 1000 bytes long — both explicitly,
in the segment table, and in the memory map $(5700-4700=1000)$.
But Segment 4 is clearly larger than Segment 0 in the memory map,
while Segment 0 is clearly larger than Segment 4
in the nebulous logical address space on the left.
Why are the segments colored inconsistently?
Segments 2 and 3 are gray on the left and white on the right.
Does this mean something?
How do we know which “segment” a given address is in?
How do we know the length of the segment table?

Wandering Logic addresses the fourth bullet with their statement,
“Typically the page table is a tree of fixed size pages.”
(emphasis added).
So, looking at Figure 8.15 (“Valid (v) or invalid (i) bit in a page table”),
excerpted here,

it might be that the system has no way of knowing
which pages are valid (0-5) and which ones are invalid (6 and 7)
other than marking the entries for the invalid pages with an invalid flag.

But also, while Figure 8.9 is somewhat confusing,
it also contains the kernel of part of the answer to your question:
The user virtual address space may be
segmented / fragmented / sparse / discontiguous.
In other words, just because the maximum virtual address is $N$,
that doesn’t mean that every $M$ such that $0 \le M \le N$
is a valid address.
Just as the segments are explicitly shown as being discontiguous
(and out of order) in the physical memory (on the right),
and are implicitly shown as disassociated in the logical address space
on the left, with order being irrelevant**,
they may actually be discontiguous in the logical address space.
In fact, the book (somewhat) explicitly (but not clearly) tells us
that they are discontiguous,
in the last paragraph of Section 8.4.2:

  A reference to byte 1222 of segment 0
  would result in a trap to the operating system,
  as this segment is only 1,000 bytes long.

So the 1222nd byte of the logical address space
is not the 222nd byte of segment 1,
but rather falls in the gap between segment 0 and segment 1.
If we assume that the segments occur in numeric order
in the logical address space with addresses at multiples of 2000,
starting at 0,
then the complete (logical and physical) segment map/table
might look something like this:

segment               logical                                  physical
   #    | base  limit          range       ...     base  limit          range
--------------------------------------     ...     ----------------------------
   0    |    0   1000           0-999              1400   1000        1400-2399
   1    | 2000    400        2000-2399             6300    400        6300-6699
   2    | 4000    400        4000-4399             4300    400        4300-4699
   3    | 6000   1100        6000-7099             3200   1100        3200-4299
   4    | 8000   1000        8000-8999             4700   1000        4700-5699

(I’m sorry, but I just don’t see any reason
to display the limit to the left of the base, as the authors do.)
So, pretending that the page size is 100 bytes,
using a format inspired by Figure 8.15,
we would get a page table that looks like this:

virtual physical ┃ virtual physical ┃ virtual physical ┃ virtual physical ┃ virtual physical
page # | page #  ┃ page # | page #  ┃ page # | page #  ┃ page # | page #  ┃ page # | page #
   0   |   14    ┃   18   | invalid ┃   36   | invalid ┃   54   | invalid ┃   72   | invalid
   1   |   15    ┃   19   | invalid ┃   37   | invalid ┃   55   | invalid ┃   73   | invalid
   2   |   16    ┃   20   |   63    ┃   38   | invalid ┃   56   | invalid ┃   74   | invalid
   3   |   17    ┃   21   |   64    ┃   39   | invalid ┃   57   | invalid ┃   75   | invalid
   4   |   18    ┃   22   |   65    ┃   40   |   43    ┃   58   | invalid ┃   76   | invalid
   5   |   19    ┃   23   |   66    ┃   41   |   44    ┃   59   | invalid ┃   77   | invalid
   6   |   20    ┃   24   | invalid ┃   42   |   45    ┃   60   |   32    ┃   78   | invalid
   7   |   21    ┃   25   | invalid ┃   43   |   46    ┃   61   |   33    ┃   79   | invalid
   8   |   22    ┃   26   | invalid ┃   44   | invalid ┃   62   |   34    ┃   80   |   47
   9   |   23    ┃   27   | invalid ┃   45   | invalid ┃   63   |   35    ┃   81   |   48
  10   | invalid ┃   28   | invalid ┃   46   | invalid ┃   64   |   36    ┃   82   |   49
  11   | invalid ┃   29   | invalid ┃   47   | invalid ┃   65   |   37    ┃   83   |   50
  12   | invalid ┃   30   | invalid ┃   48   | invalid ┃   66   |   38    ┃   84   |   51
  13   | invalid ┃   31   | invalid ┃   49   | invalid ┃   67   |   39    ┃   85   |   52
  14   | invalid ┃   32   | invalid ┃   50   | invalid ┃   68   |   40    ┃   86   |   53
  15   | invalid ┃   33   | invalid ┃   51   | invalid ┃   69   |   41    ┃   87   |   54
  16   | invalid ┃   34   | invalid ┃   52   | invalid ┃   70   |   42    ┃   88   |   55
  17   | invalid ┃   35   | invalid ┃   53   | invalid ┃   71   | invalid ┃   89   |   56
                                                                              90   | invalid
                                                                              91   |    ︙

(Consider all entries that have physical page numbers
(not flagged “invalid”) to be flagged “valid” —
I left that out to save space.)
See also What is stored in the first memory address? Why can’t I
print the contents?, where Scott provides an answer
that includes a hypothetical (example)
virtual (logical) → physical memory map

Maybe Silberschatz, et. al., should have used something like
that instead of their Figure 8.9.
(Their Figure 8.17 comes close, but, IMO,
it is too complex and confusing,
and not really the same thing in any case.)

Also, as Pseudonym points out,
pages that are valid addresses in the process's virtual address space
might not be OK for the CPU to access:

A page might be swapped/paged out to secondary storage (disk or SSD),
or it might be located in a memory-mapped file.
The operating system would need to trap the access
so it can fetch the page from secondary storage.

[Downvoter also commented:
“What about pages swapped out to disk?”]

A page might have been allocated to the process,
but not yet zero-filled.
The operating system would need to trap an access to such a page
so it can set it to all zeroes.
(Note: I’m not sure the OS would use an “invalid” flag for that;
it should be possible to flag the entry as “valid”,
but turn off read, write, and execute permissions,
so any access to any address in the page will cause a trap to the OS.)
The conventional wisdom is that fork() copies a process’s memory image.
In reality, it probably copies the page table,
so both parent and child are pointing to the same physical memory.
If/when the child process does an exec(),
it relinquishes its claim on the memory, and everything is cool.
But you don’t want it to appear (behave)
as though the processes are sharing memory,
so, as soon as either process makes any attempt to modify any memory,
the kernel wants to intercede and make a copy of the page
(so each process can have its own copy).
This is the “copy-on-write” paradigm that Pseudonym refers to.
(Although, again, I’m not sure the OS would use an “invalid” flag for that;
it should be possible to flag the entry as “valid”,
but turn off write permission,
so any write access to any address in the page will cause a trap to the OS.)

So, the answer to your question,

  Why do we need a validity bit
  when the process has no way of addressing memory outside its page table?

is that there can be addresses within the process’s page table
that are not valid addresses to access.

  Why do we [also] need a valid-invalid bit?

Good question.
As Silberschatz’s Figure 8.15 suggests,
it might be good enough just to set the physical page address
(or frame number) to 0.
But, notwithstanding the issue raised in the What is stored
in the first memory address? Why can’t I print the contents? question
(which Pseudonym also mentions: “The first few pages
of the address space of a process are deliberately left invalid
so that any attempt to access memory through a NULL pointer
is trapped by the operating system.”),
page 0 is a valid physical page address.
To say that “0” means “invalid”
would make page 0 of physical memory inaccessible — even to the OS.
Pretty much by definition, anything that can fit into a field
that is sized to a physical page number
will be a (theoretically) valid page number.
Sure, you could use an all-ones value (e.g., 0xFFFFFFFF),
but even that could result in a situation
where a machine that had 128 terabytes*** of physical memory
might be unable to access the last 512 or 1024 bytes; that would be silly.

Consider also what Daniel Jour points out:

  Because the [page number] entry isn't used by the MMU
  [if the entry is flagged as invalid,]
  the operating system can use it to store its own information,
  like for example a reference to the filesystem entity
  (for example inode number)
  where it stored the data to free the main memory for some other processes
  (it swapped that page out).

So that’s why a page table entry contains a physical page number
and a valid/invalid flag.

___________________
*  Apparently these numbers are decimal! —
see the last paragraph of Section 8.4.2 (Segmentation Hardware).
This is, of course, totally unrealistic, but I guess it doesn't matter
as long as the numbers are handled consistently.
**  which is nonsense — they are numbers, so they have an order.
*** I'm pulling a large number out of my hat here;
I haven’t checked that the math on this exactly makes sense.


How to Generate Münchhausen Numbers in High Radices? A Münchhausen number is a whole number equal to the sum of its digits raised to powers of themselves. For the purpose of such calculations, the convention is that $0^0 = 1$. For example, in radix 10, the number 3435 is a Münchhausen number, since $3435 = 3^3 + 4^4 + 3^3 + 5^5$. In radix 4, the number 313 is a Münchhausen number, since $313 = 3^3 + 1^1 + 3^3$. On a curious property of 3435 covers more details, and shows that Münchhausen numbers in radix $b$ must be less than or equal to $2b^b$.

Münchhausen numbers for base $b$ can be generated with a brute-force search, by checking whether each number from 1 to $2b^b$ is equal to the sum of its digits raised to powers of themselves. One way to improve upon this is to generate multisets of digits, and for each combination check whether the sum of digits raised to powers of themselves produces a number with the same multiset of digits. Even with parallelization, this seems infeasible for large bases. For example, for base 35, a Münchhausen number would have at most 36 digits. The number of combinations (with repetitions) of 36 elements from 35 digits is $\binom{35 + 36 - 1}{36}=\binom{70}{36}=109,069,992,321,755,544,170.$ This is in addition to those multisets with fewer than 36 elements that would also be checked.

If any, what algorithm(s) can be used to generate Münchhausen numbers feasibly for high bases (e.g., base 35)? OEIS sequence A166623 includes Münchhausen numbers for bases between 2 and 35.

Meet-in-the-middle

One approach is to use a meet-in-the-middle algorithm.  This will reduce the running time from  $2b^b$ to something in the ballpark of $\sqrt{2b^b}$.

In particular, let your candidate number be
$$A = a_b b^b + \dots + a_1 b + a_0.$$
We'll write this in the form $A=A^* + A^\dagger$ where
$$\begin{align*}
A^* &= a_b b^b + \dots + a_{\lfloor b/2 \rfloor+1} b^{\lfloor b/2 \rfloor+1}\\
A^\dagger &=a_{\lfloor b/2 \rfloor} b^{\lfloor b/2 \rfloor} + \dots + a_0.
\end{align*}$$
Finally, let $s(a_i b^i + \dots + a_0) = a_i^{a_i} + \dots + a_0^{a_0}$.  We'll look for all solutions to the equation
$$A^* + A^\dagger = s(A^*) + s(A^\dagger).$$
This is equivalent to
$$A^* - s(A^*) = s(A^\dagger) - A^\dagger.$$
We'll compute a table of all possible values for $s(A^\dagger)-A^\dagger$, where $A^\dagger$ varies over all possibilities of the form above.  Then, we'll compute $A^*-s(A^*)$, for each $A^*$ of the form above, and look it up in the table to check for a match.  Each match yields a solution to the equation above, and thus a valid Münchhausen number.  This can be used to enumerate all Münchhausens.

For $b=10$, the running time becomes something like $10^5$ steps of computation, which should be no problem.  However, this is entirely infeasible for $b=35$.  The algorithm is still exponential-time.

Linear programming

Another possible idea is to use integer linear programming.

Let $x_{i,d}$ be a 0-or-1 variable, with the intended meaning that $x_{i,d}=1$ means that $a_i = d$.  Then we can obtain a bunch of linear inequalities that characterize a correct solution.  In particular, we have
$$\sum_{i,d} x_{i,d} d b^i = \sum_{i,d} x_{i,d} d^d.$$
We also have $\sum_d x_{i,d} = 1$ for each $i$.

Next, given a lower and upper bound $L,U$, we could use integer linear programming to search for a valid solution in the range $[L,U]$, by adding the inequality
$L \le \sum_{i,d} x_{i,d} d b^i \le U$ and looking for a valid solution.  To enumerate all solutions, start with a broad range $[0,2b^b]$, then when you find a valid solution, split the current range in two and recurse.  Then, use an off-the-shelf ILP solver to find solutions.

I don't expect this to be very effective, but you could augment it with additional inequalities that might help the ILP solver run faster.  In particular, for each prime number $p$ less than $2b^b$, we have
$$\sum_{i,d} x_{i,d} d b^i \equiv \sum_{i,d} x_{i,d} d^d \pmod p$$
This can be encoded via the linear equality
$$\sum_{i,d} x_{i,d} d b^i = \sum_{i,d} x_{i,d} x_{i,d} d^d + y_p p$$
where $y_p$ is an integer variable.  Note that $d b^i$ and $d^d$ are integer constants, so you can reduce them modulo $p$. Thus we get the linear equality
$$\sum_{i,d} \alpha_{i,d,p} x_{i,d} = \sum_{i,d} \beta_{d,p} x_{i,d} + y_p p$$
where $\alpha_{i,d,p} = d b^i \bmod p$ and $\beta_{d,p} = d^d \bmod p$ are constants you can precompute.  You can do the same if $p$ is a power of a prime.

So, you might add linear inequalities of this form for several well-chosen prime powers (say, all of the prime powers below some bound; or all small prime numbers, plus the prime power factors of $b$, $b-1$, $b+1$, $b^2$, $b^2-1$, $b^2+1$).  One could hope that these help the linear solver find solutions faster.

I don't know whether this will be effective, but it is something you could try.  It would not be too hard to implement and see how well it works.


Looking for an algorithm to solve a specific Vehicle Routing Problem I am trying to figure out a way to create routes for trucks to complete a list of orders(drops/stops), while minimizing distance traveled.

There is only ever 1 company warehouse in the area.
The trucks have to deliver based on capacity.
Each truck can hold a maximum (usually 18 pallets).
Each order will be for a number underneath that maximum.
There will be a maximum number of trucks specified.
When trucks are finished with their route, they will return to the company
warehouse.

I already have all of the orders, the pallets they are requesting, and the distance between each point.

I am an absolute simpleton when it comes to complex problems like these...  I am hoping that someone has a simple (relatively) solution, or an article of some sort that could help me down my path.

A metaheuristic would do. I would opt for a Large Neighbourhood Search (LNS), a Genetic Algorithm (GA), or Tabu Search (TS).


Cost of solving a matrix equation using the FFT I am trying to calculate

$$V = (H^TH+I)^{-1} U$$

where $H\in\mathbb{R}^{m\times m}$ is a circulant convolution matrix corresponding to a convolution kernel $h$, and $U\in\mathbb{R}^{m\times n}$. The computation of $V$ can be done using the FFT algorithm.

I am confused about the computational complexity of using the FFT for this kind of problem. I will be most grateful if you could provide some suggestions or ideas for solving this problem. Thank you.

If $m \times m$ symmetric matrix $\rm H^{\top} H$ is circulant, then its spectral decomposition is
$$\rm H^{\top} H = Q \Lambda Q^*$$
where the eigenvalues of $\rm H^{\top} H$ are given by the Discrete Fourier Transform (DFT) of the first row of $\rm H^{\top} H$, and where the eigenvalue matrix is
$$\rm Q =  \frac{1}{\sqrt m} \, F_m$$
where $\rm F_m$ is the $m \times m$ Fourier matrix. Hence,
$$\rm H^{\top} H + I_m = Q \Lambda Q^* + I_m = Q \Lambda Q^* + Q Q^* = Q \, (\Lambda + I_m) \, Q^*$$
and
$$\rm  \left( H^{\top} H + I_m \right)^{-1} U = Q \, (\Lambda + I_m)^{-1} \, Q^* U = \frac 1m \, F_m \, (\Lambda + I_m)^{-1} \, F_m^* U$$
The Fast Fourier Transform (FFT) algorithm can now be used to factor the Fourier matrix $\rm F_m$ and its Hermitian transpose. What is the cost?

Computing $\Lambda$ requires one DFT of length $m$. Using the FFT, that costs $O (m \log (m))$.
Computing $\rm F_m^* U$ requires $n$ DFTs of length $m$. Using the FFT, that costs $O (n \, m \log (m))$.
Multiplying $\rm (\Lambda + I_m)^{-1}$ and $\rm F_m^* U$ costs $m$ additions and $m \, n$ divisions.
Computing $\rm F_m \, (\Lambda + I_m)^{-1} \, F_m^* U$ requires $n$ DFTs of length $m$. Using the FFT, that costs $O (n \, m \log (m))$.
Dividing $\rm F_m \, (\Lambda + I_m)^{-1} \, F_m^* U$ by $m$ costs $m \, n$ divisions.

Thus, the total cost is $O (n \, m \log (m))$.

References

Robert M. Gray, Toeplitz and circulant matrices: a review.
Complex matrices; fast Fourier transform, MIT 18.06SC Linear Algebra, Fall 2011.


Time complexity of a triple nested loop with squared indices I have seen this function in past year exam paper.

public static void run(int n){
    for(int i = 1 ; i * i < n ; i++){
        for(int j = i ; j * j < n ; j++){
            for(int k = j ; k * k < n ; k++){

            }
        }
    }
}

After give some example, I guess it is a function that with time complexity in following formula

let make m = n^(1/2)

[m+(m-1)+(m-2)+...+3+2+1] + [(m-1)+(m-2)+...+3+2+1] + ...... + (3+2+1) + (2+1) + 1

*Edit: I have asked this math question here, the answer is m(m+1)(m+2)/6

Is this correct, if no, what is wrong, if yes, how would you translate to big O notation.
The question that I want to ask is not only about this specific example; but also how would you evaluate an algorithm, let's say, I can only give some example to watch the pattern it appears. But some algorithm are not that easy to evaluate, what is your way to evaluate using this example.

Edit:
@LuchianGrigore
@AleksG

public static void run(int n){
        for(int i = 1 ; i * i < n ; i++){
            for(int j = 1 ; j * j < n ; j++){
                for(int k = 1 ; k * k < n ; k++){

                }
            }
        }
    }

This is an example that in my lecture notes, each loop is with time complexity of n to the power of 1/2, for each loop there is another n^(1/2) inside, the total are n^(1/2) * n^(1/2) * n^(1/2) = n^(3/2).
Is the first example the same? It is less than the second example, right?

Edit,Add:

How about this one? Is it log(n)*n^(1/2)*log(n^2)

for (int i = 1; i < n; i *= 2)
            for (int j = i; j * j < n; j++)
                for (int m = j; j < n * n; j *= 2)

For one of the loops, you've a complexity of $O(\sqrt n)$. You're nesting the loops three times, so you'll get the complexity of $O(\sqrt n^3)$, which is $O(n^{3/2})$.

If you want to be more precise, then for your original question, the complexity will be:

$O(\sqrt n)$ for the first loop
$O(\sqrt n - 1)$ for the second loop, which is the same as $O(\sqrt n)$, since the time complexity of 1 is constant.
$O(\sqrt n - 2)$ for the third loop, which is the same as $O(\sqrt n)$, since the time complexity of 2 is constant.

Therefore, the total complexity is still $O(\sqrt n^3) = O(n^{3/2})$.

EDIT/ADD:

You're pretty much correct, just make one more step to simplify the expression, remembering that $\log(n^2) = 2 \times \log(n)$.  There are three loops:

The first on is, correctly, $O(\log n)$.
The second one is just like in the first problem, so you get $O(\sqrt n)$.
The third one is on the square of $n$, therefore you get $O(\log(n^2))$, which is the same as $O(2\log(n))$, which is the same as $O(\log(n))$.

Combining the three, it's pretty much like a multiplication, you will get: $O(\log(n) \times \sqrt n \times \log(n))$, which is $O(\log(n)^2 \times \sqrt n)$.


Unsplittable flow in capacitated networks I have an undirected network with capacitated links/edges. Between some nodes unsplittable traffic has to be routed. All demands and capacities are known, but it is uncertain if all flows can be routed without capacity violations.

This problem seemed to be similar the classical unsplittable flow problem (UFP). However, I am not really interested in routing as many flows as possible. I rather want a solution where all flows are routed without violations or I will recompute different demands and try again.

Since this is just part of a bigger heuristic I am building, I was looking for fast and easy to understand algorithms that I could implement. I read some papers and presentations on the UFP (e.g. this). Unfortunately, in the algorithm description (slide 22) it doesn't descirbe how the possible paths are searched for and how the flow is routed.

I would be thankful for some fast and simple algorithms to solve my problem. If the UFP is not as similar as I thought, I am also glad to learn about new more applicable problem models.

I also thought about calculating the shortest paths using Dijkstra's algorithm while also updating the capacities. But that might not always find solutions, even if it is a feasible problem, i.e. when the order of the routed flows is of matter. Also, I'm not sure if this is a very efficient way.

The easiest algorithm to implement will probably be to use integer linear programming, and then use an off-the-shelf ILP solver.  I would suggest starting with that and seeing if it is efficient enough, and only dive into the literature if ILP does not meet your needs.

One formulation as ILP could go something like this.  For each edge $e$ and each source $s$ you have a variable $f_{e,s}$ that indicates how much flow from source $s$ goes through edge $e$.  You'll have a constraint saying that $\sum_s f_{e,s}$ has to be at least the demand and at most the capacity, for each edge $e$.  Also, you'll have a constraint representing conservation of flow.

Finally, to encode the unsplittable flow condition, for each edge $(v,w) \in E$ and each source $s$, add a variable $x_{v,w,s}$ that is $1$ if the flow from $s$ enters $v$ and goes next to $w$, or 0 otherwise.  To ensure that no flow splits, you'll have a constraint $\sum_w x_{v,w,s} \le 1$ for each $v,s$ and a constraint $f_{(v,w),s} \le K \cdot x_{v,w,s}$, where $K$ is a huge constant.

This should be relatively easy to implement.  You can formulate some code to produce the right ILP system in an hour or two, and then use an off-the-shelf ILP solver.  Therefore, you should be able to very quickly experiment with this approach and see whether it meets your needs or not, before diving into the research literature on multi-terminal unsplittable flow problems.


How to implement simulation on two LTSs? Does any one know how to implement the simulation relation on two labelled transition systems (LTS)?

I know how to do it for branching bi-simulation. The signature refinement theorem is used for that purpose which has the time complexity of $O(n^3)$ on cyclic LTSs. Is the signature refinement technique useful for simulation also?

Is there any binary relation called branching simulation? Any idea how to implement it?

What I would like to do is to write a program such that:

Input: Given two labelled transition systems with silent steps
Output1: Does one simulates the other one?
Output2: Are they bisimilar?
Output3: Are they branching bisimilar?
Output4: Does one branching simulate the other one?

The following illustrates the definitions of the above relations:

simulate: An LTS ($L_1$) simulates another LTS ($L_2$) if there exists a binary relation $R$ over the states of the two transition systems such that every transition of $L_2$ can be matched by a transition of $L_1$. Note that simulation is not an equivalence relation.
bisimilar: An LTS ($L_1$) and an LTS ($L_2$) are said to be bisimular if there exists a relation $R$ between the states of these transition systems such that both $R$ and $R^{-1}$ are simulations. Note that bisimularity is an equivalence relation.
branching bisimilarity: is same as bisimilarity but transition systems may have silent steps. Those silent steps ($\tau$ actions) that do not change the behavior of the process are eliminated. Note that branching bisimilarity is an equivalence relation.
branching similarity: I actually have never seen the definition of branching similarity in any context, but it should be the same as similarity. However, the transition systems may have the silent steps.

The paper Distributed Branching Bisimulation Reduction of State Spaces by S. Blom and S. Orzan explains an algorithm to reduce the size of an LTS with respect to branching bisimilarity. The signature refinement theorem is used for that purpose. How it works is roughly as follows:

the algorithm starts by constructing a partition (a set of blocks) of states and terminates once the partition is stable. In a stable partition, two states are branching bisimilar if they belong to the same block.

The above algorithm can also be used to verify whether two LTSs are branching bisimilar or bisimilar. How it works is as follows:

Let LTS, $L_3 = L_1 \cup L_2$, then if after branching reduction, using the above algorithm, the initial states of $L_1$ and $L_2$ both belong to the same block then they are branching bisimular. The above algorithm has time complexity $O(n^3)$ and space complexity $O(n^2)$.

Question: How can I do the same with branching simulate and simulate relations?

If you have doubts about whether a certain type of relation exists, a good place to search is Rob van Glabbeek's extensive catalogue of such relations. That article is a bit dated by now, but still extremely comprehensive.

Linear Time-Branching Time Spectrum II, Robert J. van Glabbeek, 1993.

There are several papers on the algorithmic aspect. I would suggest the one below.

Generalizing the Paige-Tarjan Algorithm by Abstract Interpretation, by Francesco Ranzato and Francesco Tapparo

This paper provides a design-pattern for implementing partition-refinement style algorithms for checking bisimulation and simulation. The later sections of the paper are quite algorithmic. You could contact the authors and ask about their implementation.

Computing Stuttering Simulations by Francesco Ranzato and Francesco Tapparo

You asked about branching and not stuttering, but I think the contents of the above paper are very related to what you want.

There are some implementations that may help your study.

The Edinburgh Concurrency Workbench
The Concurrency Workbench of the New Century
Concurrency Workbench, Aalborg Edition

All the tools above implement checking equivalences of processes with respect to preorders; the third one is more recent and is also offered online.


What is the difference between Big(O) and small(o) notations in asymptotic analysis? What is the difference between $O$ (big oh) and $o$ (small oh) notations in asymptotic analysis? Even though I understand that $o$ is used for a bound that is not tight, is it allowed to use $O$ notaion for a bound that is also not tight? For example can I say that $5n=O(n^3)$?

I am also confused by what this statement in CLSR means
 "The main difference is that in $f(n) =O(g(n))$, the bound $0 \le f(n) \le cg(n)$ holds for some constant $c > 0$, but in $f(n) = o(g(n))$, the bound $0 \le f(n) < cg(n)$ holds for all constants $c > 0$." As the value of $c$ will differ in the inequality "$0 \le f(n)< cg(n)$ for all $n > n_0,c>0$. " for different $n_0$.

Bigoh notation $O$:

This is anlogous to $\le$.
$f(n) = O(g(n))$ means that for large enough value of $n$ value of $f(n)$ will be within some constant factor of value of $g(n).$

Smalloh notation $o$:

This is anlogous to $<$ relation.
Now, $f(n) = o(g(n))$ means that if you are given any constant $c>0$ you will be able to find out some constant $n_0>0$ such that for all $n\ge n_0$, $f(n) < c.g(n)$ holds.

Intuitively smalloh notation says that $f(n)$ is asymptotically slower than $g(n)$.

For example $3n = O(5n)$ but $3n\ne o(5n)$ because for latter case if I give you $c=1/5$ you will not able to find out value of $n_0$ such that for all $n\ge n_0, 3n < c.5n$.


Is every Turing complete set for EXPSPACE autoreducible? I'm reading about autoreducibility, which is the following notion:

  A set $L$ is autoreducible
  if there is a polynomial-time oracle Turing machine $M$
  that accepts $L$ using $L$ as an oracle, with the caveat
  that $M(x)$ may not query whether $x \in L$.

I encountered some results that are confusing me. In  Using autoreducibility to separate complexity classes,  Buhrman et al. showed that every polynomial-time Turing-complete set for EXPSPACE is autoreducible (Theorem 4.1). In Diagonalization, a survey by Fortnow, there is a theorem stating that if every Turing-complete set for EXPSPACE is autoreducible then $NL \neq NP$ (Theorem 3.1). So using both theorems together, we have $NP \neq NL$! I want to know where is my fault.

The result from Buhrman et al. is about EXP rather than EXPSPACE.

Note that Theorem 3.1 from Fortnow's survey is taken from the very same paper of Buhrman et al.


Sub language is not Turing-recognizable, or could it be? Let A and B be languages with A ⊆ B, and B is Turing-recognizable. Can A be not Turing-recognizable? If so, is there any example?

This is something that confuses many students. The point here is that being subset of another language does not imply much about their difficulty of computation. You can always consider the trivial language $\emptyset$ and $\Sigma^*$ and any other language is between them w.r.t. set inclusion.

Therefore just knowing that a language contains or is contained in a easy to compute language doesn't say anything about the difficulty of computing it.


FPT algorithm for 1-BDD Given a graph $G = (V,E)$ and an integer $k$, the 1-BDD problem asks if there exists a subset $D$ of at
most $k$ vertices such that the degree of any vertex in $G[V \setminus D]$ is at most one.
Is there any FPT algorithm for the above problem running in time $O^*(2^k)$?

Let $v$ be an arbitrary vertex in your graph, of degree $d$. In any solution $D$, either $v \in D$, or at least $d-1$ of its neighbors are in $D$. In this case, we have one branch with parameter $k-1$, and $d$ branches with parameter $k-(d-1)$ (which is progress as long as $d \geq 2$).
If $d = 1$, then we can say more. Let $u$ be the unique neighbor of $v$. If $D$ is any feasible solution, then so is $D \setminus \{v\} \cup \{u\}$. In other words, we can assume without loss of generality that any solution does not contain $v$. Any such solution either contains $u$ or all neighbors of $u$ apart from $v$. If $u$ also has degree $1$ then there is clearly a solution not containing either $u$ or $v$, so we can assume that in this case $u$ has degree at least $2$. In this case, we have one branch with parameter $k-1$, and one branch with parameter $k-(d-1)$.
Denoting by $T(k)$ the worst-case size of the search tree when the parameter in $k$, our ideas so far show that
$$
T(k) = T(k-1) + \max_{d \geq 2} (dT(k-(d-1)).
$$
Unfortunately, if we choose $d = 2$ then we get $T(k) \geq 3T(k-1)$, whose solution is $T(k) = \Omega(3^k)$.
We can improve on this algorithm by noting that if all vertices have degree $2$ then the problem is easy to solve, since the graph is a union of disjoint cycles, and a cycle of length $\ell$ requires spending $\lceil \ell/2 \rceil$ vertices of $D$. Hence either $v$ has degree at least $3$, or $v$ has degree $1$ (and $u$ has degree at least $2$). This leads to the improved recurrence
$$
T(k) = T(k-1) + \max(T(k-1),\max_{d \geq 3} dT(k-(d-1))).
$$
Unfortunately, if we choose $d = 3$ then we get $T(k) \geq T(k-1) + 3T(k-2)$, whose solution is $T(k) = \Omega(\bigl(\frac{\sqrt{13}+1}{2}\bigr)^k)$, with a base of roughly $2.3$.
We can improve on this as follows. We can assume that the minimum degree is $2$. Let $v$ be a vertex of degree $d \geq 3$. Any solution either contains $v$, or all of its neighbors, or it contains all but a single neighbor $w$, and all the remaining neighbors of $w$. This leads to one branch with parameter $k-1$, one branch with parameter $k-d$, and $d$ branches with parameters at most $k-d$. Thus
$$
T(k) = T(k-1) + \max(\max_{d \geq 1} T(k-d), \max_{d \geq 3}(T(k-d) + \max_{e_1,\ldots,e_d \geq 2} T(k-(d-1)+(e_1-1)) + \cdots + T(k-(d-1)+(e_d-1)))).
$$
Using monotonicity, this reduces to
$$
T(k) = T(k-1) + \max(T(k-1), \max_{d \geq 3} (d+1)T(k-d)).
$$
Using base case of $T(0) = 1$, we can prove by induction that $T(k) = 2^k$. The lower bound is clear. For the upper bound, we need to prove that $(d+1) 2^{k-d} \leq 2^{k-1}$ for all $d \geq 3$, which reduces to $d+1 \leq 2^{d-1}$, an inequality which can be checked directly.


Nine-input sorting network of optimal depth with minimum number of comparators In the research on sorting networks, two parameters are typically of interest: The number of comparators required and the depth required.
They have practical implications for throughput and latency. Results in latter category are usually easier to achieve than  corresponding results in the former. Already in 1989, Parberry demonstrated that the optimal depth for nine-input and ten-input sorting networks is seven:

Ian Parberry. "A computer assisted optimal depth lower bound for sorting networks with nine inputs." In Proceedings of the 1989 ACM/IEEE Conference on Supercomputing, November 1989, pp.152-161

Not until 2014 was it shown by Codish et. al. that the optimal number of comparators for nine-input sorting networks is 25, while the optimal number of comparators for ten-input sorting networks is 29:

Michael Codish, Luís Cruz-Filipe, Michael Frank, and Peter Schneider-Kamp. "Twenty-five comparators is optimal when sorting nine inputs (and twenty-nine for ten)." In Proceedings 26th IEEE International Conference on Tools with Artificial Intelligence, November 2014, pp. 186-193

In general, sorting networks of optimal depth cannot necessarily be achieved by using the optimal number of comparators. Knuth (TAOCP, Vol. 3, 2nd ed.) states that often "one or two extra comparator modules" are required, and shows (Fig. 51) a  ten-input sorting network of optimal depth seven that requires 31 comparators, that is, two more than optimal.

In a multi-hour search of the literature and the internet at large, I have been unable to find a worked-out example of a nine-input sorting network of depth seven, nor have I been able to find information on the minimum number of comparators needed to construct such network. I am currently unable to construct any nine-input sorting networks of optimal depth with my home-grown software.

What nine-input sorting networks of depth seven are known? Following Knuth, they should require no more than 26 or 27 comparators.

I found a 2002 Reference of the Best-Known Sorting Networks for up to 16 Inputs by Ron Zeno including a diagram of a 9-input network that seems to fit the bill.

His nine-input sorting network of depth seven uses the following arrangement of comparators

{0, 7}, {1, 6}, {2, 5}, {3, 4},
{0, 3}, {1, 2}, {4, 7}, {6, 8},
{0, 1}, {2, 6}, {3, 4}, {5, 8},
{1, 2}, {3, 5}, {4, 6}, {7, 8},
{1, 3}, {2, 4}, {5, 7},
{0, 1}, {2, 3}, {4, 5}, {6, 7},
{3, 4}, {5, 6}

Wolfram demonstrations includes a beta about Sorting Networks, which in due course contains an example of an optimal (module count) nine-input network:

  {{1, 2}, {4, 5}, {7, 8}},
  {{2, 3}, {5, 6}, {8, 9}},
  {{1, 2}, {4, 5}, {7, 8}, {3, 6}},
  {{1, 4}, {2, 5}, {6, 9}},
  {{4, 7}, {5, 8}, {3, 6}},
  {{1, 4}, {2, 5}, {6, 8}, {3, 7}},
  {{2, 4}, {5, 7}},
  {{3, 5}, {6, 7}},
  {{3, 4}}

(That's probably about as close as I will get to providing a visualisation:
looks trivial to plug "the Flensburg" or above 7-level configurations.)


Why doesn't Quantum Turing Machine contradict with Church-Turing thesis I studied about Quantum Turing machine and i figured out that the difference between QTM and TM is in transition function and also if a problem is unsolvable by a TM then it is unsolvable by a QTM but I need a justifiable reason to claim QTM does not contradict with Church-Turing thesis.

Quantum Turing machines can be simulated by classical Turing machines. See Deutsch's fundamental paper Quantum theory, the Church-Turing principle and the universal
quantum computer.


Partition partition with constraint of equal size I see the problem here which is the well know partition problem but with constraint that the size of both sets must be equal.

I look at the answer and I don't understand that why Colin said add max(S)⋅length(S), and run the algorithm as normal would make the size of both sets equal. I think for long time.

And i think that his claim for send s∈S to 1+s⋅length(S) is wrong?

Example:

Initial set: 1 2 3 9

1+s⋅length(S)= 1+s(4)=5 9 13 37

After running the traditional Boolean algorithm, what I got is one set of 5 9 13, another set of 37?

Can anyone explain to me? Especially the max(S)⋅length(S) one.

The idea of Colin's algorithm is to try to force a multiset that has partitions where the cardinality of the subset is different, to have only partitions where the resulting subsets have the same size. So that the problem can only be solved if we can divide the multiset into two subsets with the same cardinality

For instance, think in the multiset

{1,1,1,2,2,3}.

This set has more than one way of partitioning it:

We can partition it into {3,1,1} and {2,2,1}

Or we can partition it into {1,1,1,2} and {3,2}

In the variant they talk about, only the first way to partition this multiset is valid.

So, what he does is adding to each number the following quantity:

Number + (number with highest value * cardinality of the set we want to divide)

In our example this results in:

{19,19,19,20,20,21}

And we can only partition this multiset of numbers only if we can partition it into two subsets with the same cardinality, in this case:

{19,20,20} and {19,19,21}

Why does it work?

It works because you add to each number the same quantity, so in a partition where the two subsets have the same cardinality, we add the number the same number of times to each subset, in a partition with subsets of different cardinality, we add the number to each subset a number of times that is not equal, so the subsets can't have the same sum.

For instance

We keep with the previous example

1 + 18 + 2 + 18 + 2 + 18

and

1 + 18 + 1 +18 + 3 +18

This partition has the same sum because we add the number eighteen three times to each subset.

But

1 + 18 + 1 +18 + 1 +18 + 2 + 18

and

3 + 18 + 2 +18

don't give the same result because we add eighteen to the first subset four times and only two to the other subset, as the two had the same sum before the transformation, by adding a number to each subset a number of times that is not equal, the two don't have the same sum anymore

Hope this is helpful


Non-existence of approximation algorithm for the knapsack problem I am working on the following exercise: Prove that if $P \neq NP$, there cannot exist an approximation algorithm $A$ for the knapsack problem (KP) such that $\exists k \in \mathbb{N}, \forall I \in S: OPT(I) - P_A(I) \leq k$ where $OPT(I)$ is the optimal profit on instance $I$ and $P_A(I)$ is the profit calculated by $A$.

I know that there is a FPTAS $A'$ for the KP which guarantees a solution with profit $P_{A'}(I) \geq (1 - \varepsilon)OPT(I)$ on any instance $I$ and $\varepsilon > 0$.

My approach is to create a contradiction. For this I consider $A = A'$ and aim to show that $P_A(I) \geq (1 - \varepsilon)OPT(I) \geq ... \geq OPT(I) - c$ where $c \in (0,1)$ is a constant. This way, for an adequate choice of $\varepsilon$ I would show that we obtain an optimal solution within polynomial time. However, I struggle how to choose $\varepsilon$.

I need some advice on how to proceed. Many thanks in advance!

Given an instance of knapsack, multiply all values by $k+1$. Any solution satisfyign $OPT(I) - P_A(I) \leq k$ is in fact optimal, so you could use such an algorithm to solve knapsack.


variable exponent in expression of a formal language Take a look at the following expression:

{(AnB)m|n>0,m>0}

Or, to put it simply: the words in the language, have repeating parts consisting of,  some A's followed by a single B.

There are TWO school of thoughts about this, which can be broken down, by this question:
Is the word ABAAB, a part of the language?

I say, that it's not, as each repeating part must have the same number (n) of A's in it.
Others claim that each repeating part can have it's own number of A's

I am willing to concede, that had the expression used +, instead of n>0, then each repeat, could have been different (although, I don't like this concession).

The question is: Is the variable in the inner part "locked", or can that variable have different values in each iteration of the part.

What I'd like, is a credible source that I can point to that explains which way is correct.

(ps, if my understanding of the expression is the correct one, it means the language is not regular; if I am wrong, it is regular).

Thank you all.

Whenever $m,n$ are chosen, there is only a single interpretation for $(A^nB)^m$. The variables are "locked" in the set builder notation $\{ \dots \mid m,n>0\}$. I mean, the string $(A^2B)^3$ equals $AABAABAAB$, there are no schools here.

If you want to have repetitions of variable length sequences of the form $A\dots AB$ then the regular expression $(A^*B)^*$ is appropriate.

The point here is that for each $m,n$ the $(A^nB)^m$ here is only a single object, not a set of strings (a language).

Consider the domain of natural numbers, which probably is better known. Let us analogously define the set $S = \{ (n+1)^m \mid m\ge 2,n>0\}$. Here it is quite clear that every $m,n$ is a single number, the $m$th power of a specific $n+1$. We would not consider choosing another $n$ for each multiplication. So we have $(2+1)(2+1)(2+1)\in S$ and not $(2+1)(5+1)(10+1)$.

The confusion is perhaps that in formal languages we consider both powers of single words and powers of languages. The $(A^*B)^*$ is an abbreviation for $\bigcup_{m\ge 0}\{ A^nB\mid n\ge 0\}^m$. In this case for any $m$ we compute the $m$th power of the language $\{ B, AB, AAB, AAAB, \dots \}$ which is the concatenation of $m$ copies of the language. Then we can choose a different string (i.e., a different $n$) in each term.

Another example that shows the difference between these confusing notations is the following. For a language $L$ its square is $L^2 = L\cdot L = \{ uv\mid u,v\in L\}$. This is the concatenation of two copies of $L$, and we may choose two diferent strings: $\{aa,b\}^2= \{aaaa,aab,baa,bb\}$.
Squaring all words is different: $\mathrm{sq}(L) =\{ w^2 \mid w\in L \}$. Same example $\mathrm{sq}(\{aa,b\}) = \{aaaa,bb\}$.

But again, the formal reason is set builder notation, as in my first paragraph.


How to design a formal grammar to convert EBNF description to a list of CFG production rules I would like to write a grammar to convert EBNF description to a list of CFG production rules, instead of an algorithm.
Can CFG production rules is generated from an EBNF description by a rewrite system rewrite EBNF description to halt state that final string is composed by CFG production rules and separate character for that list (for example character '/')?
For example: From intuition view, I could convert as below:
EBNF Description:
letter = "A" | "B" | "C" ;
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
identifier = letter , { letter | digit | "_" } ;
Generated production rules:
letter ⟶ "A"
letter ⟶ "B"
letter ⟶ "C"
digit ⟶ "0"
digit ⟶ "1"
digit ⟶ "2"
digit ⟶ "3"
digit ⟶ "4"
digit ⟶ "5"
digit ⟶ "6"
digit ⟶ "7"
digit ⟶ "8"
digit ⟶ "9"
identifier ⟶ letter
identifier ⟶ letter noname_nonterminal
noname_nonterminal ⟶ letter noname_nonterminal
noname_nonterminal ⟶ digit noname_nonterminal
noname_nonterminal ⟶ "_" noname_nonterminal
noname_nonterminal ⟶ letter
noname_nonterminal ⟶ digit
noname_nonterminal ⟶ "_"
Thank you for your reading,

I have a solution as below:

Given G0 = (N0, Σ0, P0, S0) is grammar of object language generated by EBNF descriptions. Where: N0 and P0 is unknown and needed to be generated by another language.
Given G1 = (N1, Σ1, P1, S1) is grammar of language generating EBNF descriptions.

G = (N, Σ, P, S) is EBNF description to production rules conversation grammar which is defined as below:

N = {'(', ')', '∣', ',', '[', ']', '{', '}', '='}
Σ = N0 ⋃ Σ0 ⋃ {'→', '/'}

Production rules:
A = α, (γ), β ⟶ A = α, YA, β / YA = γ
Where:

A, YA ∈ N0
α ∈ N1 ⋃ Σ1 ∖ {'('}
β ∈ N1 ⋃ Σ1 ∖ {')'}
γ ∈ N1 ⋃ Σ1 ∖ {'ε'}

A = α ∣ β ⟶ A = α / A = β
Where:

A ∈ N0
α ∈ N1 ⋃ Σ1 ∖ {'(', ')', '[', ']', '{', '}'}
β ∈ N1 ⋃ Σ1 ∖ {'(', ')', '[', ']', '{', '}'}

A = α[γ]β ⟶ A = α, (γ), β / A = α, β
Where:

A ∈ N0
α ∈ N1 ⋃ Σ1 ∖ {'['}
β ∈ N1 ⋃ Σ1 ∖ {']'}
γ ∈ N1 ⋃ Σ1 ∖ {'ε'}

A = α{γ}β ⟶ A = α , YA, β / YA = γYA / YA = ε
Where:

A, YA ∈ N0
α ∈ N1 ⋃ Σ1 ∖ {'{'}
β ∈ N1 ⋃ Σ1 ∖ {'}'}
γ ∈ N1 ⋃ Σ1 ∖ {'ε'}

A = B,C ⟶ A = BC
Where:

A, B, C ∈ N0

A = B ⟶ A → B
Where:

A, B ∈ N0

Start rule:
S ⟶ a

Where a ∈ Σ1

This grammar will re-write EBNF description to a terminal string like: A → B / B → C / B → D which means that the generated production rules are the set {A → B, B → C, B → D}. The token '/' is list seperator.


Queue that can sort by multiple priorities? I have a high interest in priority-queues (E.g., see my answers on: Does there exist a priority queue with $O(1)$ extracts?), and was wondering if there is a priority-queue or similar data-structure where you can sort by multiple values?

For example, if I wanted to sort by numval and sort by strval, and be able to get the highest (Gödel numbering for str) in $\mathcal{O}(1)$.

struct Node {
    int numval;
    std::string strval;
};

Easily I can think to just maintain two priority-queues, but this would require twice the memory.

Is there a better way?

Simple solution: use two queues
If you want to keep track of multiple priorities that are unrelated then you'll have to use 2 priority queues.
You don't have to duplicate all the data, because you can just put a reference (pointer) to the data in your queue.
That way you only have 1 location where your object resides and two pointers to it in the two priority-queues.

So the memory load would be $O(nk+2n)$ where $k$ is the length of your object and $n$ is the number of objects.
As long as $k$ is significantly long the $2n$ factor will be insignificant.

Complex solution: intertwine the queues and use COW semantics
If the priorities are related, then you can lessen the memory load by implementing the priority queue as a linked structure where shared items link to the same node.
You'll have to use copy-on-write semantics on the shared nodes for this to work.

For an example see B(+)Trees in databases
Something very similar happens in databases, where the tables are represented as B-trees.
When a change is made a reference to the tree is copied and copy-on-write is applied to all nodes that are changed.
When the change is committed the pointers for the changed tree and the original tree are exchanged.
While the transaction is in progress the old tree and the new tree are intertwined.

Beware the running time of COW
You can do the same to your priority queue, but this only makes sense if most of the data will be the same for the queues or writes are rare, otherwise the copy-on-write semantics will kill your running time.


How to show a function is primitive recursive by induction? I know, loosely speaking, if we can define a function $f$ in term of
\begin{align}
&f(0,\vec{x})=g(\vec{x})\\
&f(n+1,\vec{x})=h(f(n),n,\vec{x})
\end{align}
where functions $g,h$ are primitive recursive. Then $f$ is primitive recursive.
However, what it means to show a function is primitive recursive by induction?

I had read above explaination on page 93 on book $\textit{Computability}$ by Epstein and Carnielli, but still I'm not sure if I got the idea. Could someone provide some examples about how a inductive definition shows a function is primitive recursive?

Wikipedia gives such an example. You haven't stated the definition of basic functions or basic operations, so I will assume the Wikipedia definition.
The successor function $S(x) = x+1$ is a basic function, and so is assigned 0. Projection functions such as $P_1^1(x) = x$, $P_2^3(x,y,z) = y$ and $P_3^3(x,y,z) = z$ are also assigned 0. The constant function $z(x) = 0$ is also assigned 0.
The function $g(x,y,z) = S(P_2^3(x,y,z)) = y + 1$ is a composition of two functions assigned 0, and so is assigned 1.
Using these functions, we can define a function $h(x,y)$ by primitive recursion: $h(0,y) = P_1^1(y) = y$, and $h(S(x),y) = g(x,h(x,y),y) = h(x,y) + 1$. This function is assigned 2, and you can check that $g(x,y) = x + y$.
The function $r(x,y,z) = h(P_2^3(x,y,z),P_3^3(x,y,z)) = g(y,z) = y + z$ is assigned 3.
We can define a function $k(x,y)$ by primitive recursion: $k(0,y) = z(y) = 0$, and $k(S(x),y) = r(x,k(x,y),y) = k(x,y)+y$. This function is assigned 4, and you can check that $k(x,y) = x\cdot y$.


Practical hard 3-sat instances The $3-SAT$ problem is known to be NP-complete problem. Which means that (as far as I understand), unless $P \neq NP$, for every algorithm $A$ which decides $3-SAT$, $A$ runs in super polynomial time (I know that this is not well defined). A stronger assumption is the "Strong Exponential Time Hypothesis " which states that every algorithm has to run in worst case exponential time.
Does that mean, for example, that every algorithm $A$ (here I refer to a "real" or practical implementation, such as Glucoses, DPLL, Z3, etc.), has an instance of size, say 200, which $A$ will not be able to solve in a reasonable time? I see many sat solvers solving formulas with millions of variables in very short time; and I am aware of subsets of $3-SAT$ which are easy, such as Horn clauses, or a random instance with a known density - but it seems that these solvers work amazingly fast without any assumptions on the input.
I have searched for Sat benchmarks, or instances which should be hard, but when running them on a modern sat solver, it doesn't seem to be a problem.
It is known that complexity assumptions (or claims) are about the asymptotic behavior, my question is: do we know for which $n_0$ these assumptions "kick in" in the case of $3-SAT$? Can we generate, or at least be confident of the existence of a relatively small formula ($< 200$), such that every algorithm requires $\sim2^{200}$ operations?

do we know for which $n_0$ these assumptions "kick in" in the case of $3-SAT$? Can we generate, or at least be confident of the existence of a relatively small formula ($< 200$), such that every algorithm requires $\sim2^{200}$ operations?

$3-SAT$ is known to be solvable in time $O(1.321^n)$. Therefore, there is no instance that would force a $\Omega(2^n)$ run time. SETH does not hold for $k-SAT$ for any bounded $k$; it is only expected to hold for general Satsifiability (with no limit on clause size). We don't really know what asymptotic runtime to expect for $k$-SAT for any $k$ (other than something exponential).

Also, for any $SAT$ formula, there is an algorithm solving it in $O(n)$ time. You could never hope to find a single example hard for all algorithms.

One way to generate hard SAT instances is to reduce from Integer Factorization.


NP-complete reduction for a k-dumbbell graph A k-dumbbell is a graph that consists of 2 cliques each of size k with one and only one edge between them. How do I show that finding if a graph is a k-dumbbell is NP-complete?

Proof it is in NP: Given the cliques of size k, I can verify if it they are the cliques of size k.

Proof of NP-hardness: If there is only one edge between them, how can I be sure that this is the edge I need for the reduction?

I'm trying to reduce from the k-clique problem as it seems to be the easiest choice.

I'm new to this so, if I'm wrong somewhere, please help me out !

Hint: Following your idea, you want to reduce the clique problem to the dumbbell problem, to show that the latter is NP-hard. Given an instance $(G,k)$ of the clique problem, it is natural to consider two copies $G',G''$ of your original graph, connected in some way, so that if the original graphs contains a $k$-clique, then the new one contains a $k$-dumbbell.

If the new graph contains a $k$-dumbbell restricted to one of the copies, then the original graph certainly contains a $k$-clique. You want to arrange matters so that if the $k$-dumbbell straddles both copies, then it is composed of a $k$-clique in each one.

This is just a hint, so I'm not giving a full solution. Indeed, there might be several ways of using this idea to get an NP-hardness reduction. Some of them require you to slightly change the value of $k$ from the clique instance to the dumbbell instance.


Solving $T(n) = 3T(n-1) + 2$ I am trying to get better at solving recurrence relations, so I am making my own simple relations and try to solve them. I have made the following recurrence:

$$T(n) = 3T(n-1) + 2, \quad\quad T(1) = 1$$

My work at solving it:
$$\begin{align*}
T(n) &= 3^2T(n-2) + 3*2 + 2 \\
     &= 3^3 T(n-3) + 3^2*2+ 3*2 + 2 \\
     &= 3^4 T(n-4) + 3^3*2 + 3^2*2 + 3*2 + 2 \\
    &= \dots \\
  &= 3^k T(n-k) + 3^{k-1}*2+3^{k-2}*2 +\dots+3*2+2 \\
 &= 3^k + 3^{k-1}*2+3^{k-2}*2 +\dots+3*2+2 \\
&= 3^k +[\sum_{i=1}^{k-1} 3^i*2 ] + 2
\end{align*}$$

where $k = n - 1$.

I guess the Big O would be exponential since the above would be less than $3^n$ which is $O(c^n)$?

I am stuck on how to finish this and find out what the time complexity is in Big O notation.


What happens to the cache contents on a context switch? In a multicore processor, what happens to the contents of a core's cache (say L1) when a context switch occurs on that cache?

Is the behaviour dependent on the architecture or is it a general behaviour followed by all chip manufacturers?

That depends both on the processor (not just the processor series, it can vary from model to model) and the operating systems, but there are general principles. Whether a processor is multicore has no direct impact on this aspect; the same process could be executing on multiple cores simultaneously (if it's multithreaded), and memory can be shared between processes, so cache synchronization is unavoidable regardless of what happens on a context switch.

When a processor looks up a memory location in the cache, if there is an MMU, it can use either the physical or the virtual address of that location (sometimes even a combination of both, but that's not really relevant here).

With physical addresses, it doesn't matter which process is accessing the address, the contents can be shared. So there is no need to invalidate the cache content during a context switch. If the two processes map the same physical page with different attributes, this is handled by the MMU (acting as a MPU (memory protection unit)). The downside of a physically addressed cache is that the MMU has to sit between the processor and the cache, so the cache lookup is slow. L1 caches are almost never physically addresses; higher-level caches may be.

The same virtual address can denote different memory locations in different processes. Hence, with a virtually addressed cache, the processor and the operating system must cooperate to ensure that a process will find the right memory. There are several common techniques. The context-switching code provided by the operating system can invalidate the whole cache; this is correct but very costly. Some CPU architectures have room in their cache line for an ASID (address space identifier) the hardware version of a process ID, also used by the MMU. This effectively separates cache entries from different processes, and means that two processes that map the same page will have incoherent views of the same physical page (there is usually a special ASID value indicating a shared page, but these need to be flushed if they are not mapped to the same address in all processes where they are mapped). If the operating system takes care that different processes use non-overlapping address spaces (which defeats some of the purpose of using virtual memory, but can be done sometimes), then cache lines remain valid.

Most processors that have an MMU also have a TLB. The TLB is a cache of mappings from virtual addresses to physical addresses. The TLB is consulted before lookups in physically-addressed caches, to determine the physical address quickly when possible; the processor may start the cache lookup before the TLB lookup is complete, as often candidate cache lines can be identified from the middle bits of the address, between the bits that determine the offset in a cache line and the bits that determine the page. Virtually-addressed caches bypass the TLB if there is a cache hit, although the processor may initiate the TLB lookup while it is querying the cache, in case of a miss.

The TLB itself must be managed during a context switch. If the TLB entries contain an ASID, they can remain in place; the operating system only needs to flush TLB entries if their ASID has changed meaning (e.g. because a process has exited). If the TLB entries are global, they must be invalidated when switching to a different context.


Optimization in multivalued logic. Optimal strings with given patterns This question comes from an application in multivalued logic.

Suppose, we are given an alphabet of three letters $A, B, C$ and a set of indices $1,2,3,4,5$. Consider items formed by subscripting the letters with one of the indices. Examples are the following:

$$A_1 \\ B_4 \\ C_3 \\ ... $$

Suppose, additionally, that there is a total binary relation $\mathcal{R}$ on items $*_i <= *_j$ for each pair $ i, j \in \{ 1,..., 5 \} $ where $*$ denotes one of the letters $A,B$ and $C$. The relation is reflexive and transitive.

Consider a set of strings of length $5$ freely generated by the alphabet $A, B, C, ...$ disregarding ordering. Examples are the following:

$$ AABBC \\ AAAAB \\ AABCC \\ ... $$

Since order doesn't count, a string $AABBC$ is the same as $ABBAC$.

Let's call such strings templates. The templates can be "filled in" with the indices to form tuples of items using the following rules:

R1: there may be no repetitions of indices disregarding the letter type, e.g.

$$A_1, A_1, B_2, C_3, C_4$$

and

$$A_1, A_2, B_2, C_1, C_4$$

are both forbidden since the index $1$ is used two times.

R2: ordering in a tuple does not count, e. g.

$$\left( A_3 A_2 B_1 B_4 C_5 \right)$$

is the same as

$$\left( A_2 A_3 B_1 B_4 C_5 \right)$$

One can think of such "filling in" the templates as filling in a truth table with several logical levels in general.

Let us denote the set of all freely generated strings of length $5$ from the $A,B$ and $C$ by $\mathbb{Tmp}$. Let $\mathbb{Tpl}$ denote the set of all tuples generated by index assignments according to the rules R1 and R2. We can define a mapping $U:\mathbb{Tpl} \mapsto \mathbb{Tmp}$ which removes the indices from a tuple and gives its underlying template. For example:

$$ U \left( A_2 A_3 B_1 B_4 C_5 \right) = AABBC  $$

We say that a tuple $T$ satisfies the template $t$ if $U(T) = t$. We say that $T$ satisfies a set of templates $\tau = \left(t_1, t_2, ..., t_l \right)$ if there exists a template $t_i \in \tau$ for some $i \in \left( 1,2,...,l \right)$ s. t. $U(T) = t_i$.

Suppose, that we are given a set of templates $\tau$ and a total binary relation $\mathcal{R}$ on items.

What is the greatest item (greatest in the sense of the binary relation $\mathcal{R}$) of all the least items of all the tuples satisfying the templates $\tau$. In other words, what is the maximin item of the tuples?

The bruteforce algorithm is evident: take a template, build all the corresponding tuples, compare elements in each tuple and find the least, compare all the outcomes of the previous step, take the greatest. I am sure this is an $NP$-complete problem if the underlying truth table is irreducible.

What if we order all the items to obtain a sequence like this:

$$ C_2 <= B_4 <= C_1 <= C_5 <= B_1 <= A_2 <= C_3 <= A_3 <= B_3 <= C_4 <= A_4 <= A_5 <= B_5 <= A_1 <= B_2$$

Let's call this sequence $S$.

Can it simplify the problem by any chance?

For instance, consider the templates:

$$\tau = \left( AAAAB, AAABB, AAABC \right)$$

Can there be an algorithm more effective than the bruteforce? I was thinking in the following way: one can start in the sequence $S$ form left to right and "drop" items until there is no more letters to drop (otherwise, the templates are violated) or if the indexing requirement is violated.

Example of such a procedure goes like this:

drop $C_2$, drop $B_4$, drop $C_1$, drop $C_5$, drop $B_1$, drop $A_2$, drop $C_3$, drop $A_3$, $B_3$ must be picked

So no tuple may contain an item greater than $B_3$.

It seems to offer a minor complexity reduction and only for simple templates. For more complex ones, there are subtleties which I won't discuss here. But I am suspicious that there is a fundamental limitation in this problem which makes every algorithm not really better than the bruteforce.

As stated, it looks like the solution is trivial: if $\omega$ is the largest value in the underlying domain of values, then $\omega \omega \cdots \omega$ is the optimal value for the tuple.

Let's take your example, templates $AAAAB$, $AAABB$, and $AAABC$.  Suppose the underlying domain of allowable values is $\{0,1,\dots,9\}$.  Then $99999$ is the optimal tuple.  It satisfies $AAAAB$ by the assignment $A_1A_2A_3A_4B_5$.  It satisfies $AAABB$ by the assignment $A_1A_2A_3B_4B_5$.  In fact it satisfies every template.  For any template, there exists an assignment of values to each $X_i$ that makes the tuple $99999$ match that template: just assign the value $9$ to every $X_i$, for all levels $X$ and all variable indices $i$.

Perhaps you meant to provide both the templates and the assignment of values (all $m^2$ values for all the $X_i$'s, where $X$ and $i$ range over all possibilities) as input.


How come the Bernstein operator creates a polynomial of the same degree as its input function? I read that the Bernstein operator

$$
\mathfrak{B}_f(t) = \sum_{i=0}^n f\left(\frac{i}{n}\right) \; B^n_i(t)
$$

applied to a polynomial $f(x)$ of degree $m \leq n$ with the Bernstein polynomial

$$
B^n_i(t) = \binom{n}{i} \; t^i \; (1-t)^{n-i}
$$

returns a new polynomial also of degree $m$. In other words, the Bernstein operator does not increase its degree when applied to $f$.

How is this possible? Since we're only sampling $f$ at a certain interval, wouldn't the original degree of $f$ become irrelevant? How can the degree of the result be smaller than $n$, since we will have at least one $t^n$ in the expression resulting from one of the Bernstein polynomials?

The coefficients of $t^k$ for $k \gt m$ can cancel out.

For instance, let $f(x) = x^m$ and consider the coefficient of $t^n$ for $n \gt m$.

The coefficient we get is

$$n^{-m}\sum_{i=0}^{n} \binom{n}{i} i^m (-1)^{n-i}$$

which can be shown to be zero by starting with

$$\sum_{i=0}^{n} \binom{n}{i} x^{i} (-1)^{n-i} = (x-1)^{n}$$

And differentiating and multiplying by $x$, $m$ times, and then setting $x=1$.

For $m \lt n$, this indeed comes out to be zero.


Conversion of fractional part of a hexadecimal number to binary The Number is given as : (C012.25)Hexadecimal
I have to convert it into octal .
So I converted it into Binary First and got the result as : 1100000000010010.01000000
(Since each bit in hexadecimal represents 4 bit in binary so C=1100,0=0000,1=0001,2=0010 and for 0.25=.01000000 )
The Solution mentions the Binary conversion as 1100000000010010.00100101
Please guide me about the what was done wrong !
Also if I got the binary representation...How can I convert the binary no's fractional part (0.00100101) into octal .

Here is how to convert the fractional part from hexadecimal to binary:
$$
(0.25)_{16} = \frac{2}{16} + \frac{5}{16^2} =
\frac{0 \cdot 8 + 0 \cdot 4 + 1 \cdot 2 + 0 \cdot 1}{16} +
\frac{0 \cdot 8 + 1 \cdot 4 + 0 \cdot 2 + 1 \cdot 1}{16^2} = \\
\frac{0}{2} + \frac{0}{4} + \frac{1}{8} + \frac{0}{16} + \frac{0}{32} + \frac{1}{64} + \frac{0}{128} + \frac{1}{256} = (0.00100101)_2
$$
As you can see, we simply replace $2$ with its base 2 representation, and then adjoin the base 2 representation of $5$. I included this calculation to show why this works.
Note also that $(0.25)_{16} \neq 1/4$.


Formula for returning the size of a circular array I've come across a way of implementing a circular array that represents a double ended queue.

Let the circular array have the following instance variables:

int[] array;
int front = 0;
int rear = -1;
int size = 0;
int capacity = x;  // where x is a parameter in the constructor

The operations of the queue are:

dequeue - return array[front], increment front by 1,

enqueue - increment rear by 1, set array[rear] = value.

I have come to the conclusion that it is not possible to get the size of this queue by using the formula (front - rear + 1) % capacity. However, it is said that it's possible to get the size of the array using the same formula if we let the constructor set the capacity by:

BoundedQueue(int capacity) {
    this.capacity = capacity + 1;
}

With this technique the array will never actually get full and the formula for giving the size of the queue should work (it is said).

However I can't figure out how these modifications to the queue would result in the formula returning the correct size of the queue? We're only making the array one size bigger than it actually is, and we're always leaving at least one element unused. Could someone with a better insight explain to me why these modifications will lead to (rear - front + 1) % capacity giving the correct size of the queue?

Thanks in advance!

I've not checked if your formula is correct but the point appears to be that $x\%y$ can only give answers in the range $\{0, \dots, y-1\}$, whereas you're performing a calculation where the answer could be anything in the range $\{0, \dots, y\}$, including $y$. This means that any formula of the form blah%capacity is necessarily wrong.


Neural Network Weights per input nodes Sorry, I'm really new to neural networks and this question is probably pretty obvious. If you have any resource that can help clarify these concepts to me it would be much appreciated.

The way I understand neural networks is that each input node, x i  goes to each hidden layer. Is there a unique weight for each input that goes into each hidden node?

with xi being inputs, h being hidden layers, and O being the output. Would the weight from x1 to h1 be different from the weight from x1 to h2? If I'm not on the right track, please correct me!

Yes, each input value is weighted before being fed into the nodes in the next layer.  Each input/output pair of "neurons" has its own weight and it is these weights that are adjusted by the neural network training process.  The initial weights are typically random values before training begins.


Criteria for selecting language for first programming course As a university-level CS educator, the issue of which programming language to teach in the first programming course often comes up for discussion. There are thousands of languages to choose between, and lots of religious fever (or fevour) supporting one language camp over another. All of this subjective bias surrounding each programming language makes it very difficult for an educator to choose one.

My question is:

  What objective criteria can an educator use to select a programming language to use as the basis for a first year university programming course? What is the basis for these criteria?

Note: I do not want to see a list of programming languages and why they are the best one to use. The question isn't about the best language, it is about the criteria for selecting a language. Answers may however be use programming languages to illustrate particular points.

This question was inspired by another question which was deemed off-topic: https://cs.stackexchange.com/questions/1946/criteria-for-choosing-a-first-programming-language.

I'll throw in my own two cents although I believe this subject is a bottomless pit. Don't get me wrong, I think it's a fascinating question, but probably not one we will solve here to everybody's satisfaction.

In a nutshell, I'd say that the language should do what you want it to do, in a simple and unambiguous a way as possible, and not more.

My own experience comes from tutoring several generations of first and second year students with the Oberon programming language. People who know this language will recognize its influence in my opinions. Note that this language was used to teach "Algorithms and Data Structures". At the time (back then), functional programming and object-oriented design were taught in separate courses as of second year.

Important: Before going into the specifics of any language, however, I would like to emphasize that the most important thing is to be absolutely clear, to yourself and to your students, about what the goals of your course are. Are you teaching programming per se? Or algorithms and data structures? Or software engineering? Before choosing a language, it's worth it to think a moment about where you're going with it. Differences at this level (goals) is what probably, in my opinion, leads to most disagreements on this topic.

The points I consider important may overlap with several things that have already been said, but I believe most end up being subsets of one of the following four:

Simplicity: The students are usually there to be taught programming, algorithms and data structures, and not the features and intricacies of any specific programming language. Wirth used the Einstein quote "Make it as simple as possible, but not simpler" as a guiding principle in the design of Oberon, and there are several other languages out there that do it just as well. Your programming language of choice should be able to implement all the concepts required in your lecture, but should do this with the smallest possible set of features/details. The programming language is usually just the tool, not the goal.
Unambiguity: A close sibling of simplicity, there should be one construct for each concept, with as little overlap as possible. Think of it as there being only one "right" way of implementing every concept. Three different types of loops that semantically all do the same thing? Or fifteen different ways to increment a variable? Not good. This also makes correcting homework or generally just understanding your students' code a lot easier. Your teaching assistants will appreciate it.
Portability: Students will go to class with Linux, Windows and OSX machines, and the programming environment should be as similar (identical) as possible under all three. The results of any program should also be identical. This is another point that the teaching assistants, responsible for marking homework and dealing with questions/problems, will greatly appreciate.
Industry preference: Seriously, we should start worrying about this only if "Industry" itself ever decides what programming language it likes best. Since the invention of computers this has been a constantly-moving target. For the moment, if your students really learn how to program, then it won't be language-dependent. There are, however, some areas where industry manages to agree on a standard, e.g. VHDL for circuit design or SQL for database queries, so this is still a valid point.

Again, how a language fits this list is strongly dependent on what it is you're trying to teach!


Optimizing a join where each table has a selection Consider the following query:

SELECT Customer.Name FROM Customer
INNER JOIN Order on Order.CustomerId = Customer.Id
WHERE Customer.Preferred = True AND
      Order.Complete = False

Let's suppose all of the relevant attributes (Customer.Preferred, Order.Complete, Order.CustomerId and Customer.Id) are indexed. How can I evaluate this as quickly as possible?

Standard optimization advice would say that I should do the select on each table first, then the join using sort-merge or whatever the cardinality would imply. But this involves two passes through the data - I'm wondering if there's a better way.

EDIT: I think asking if there was a "better way" was too ill-defined. Suppose we are trying to find $\sigma_a(A)\bowtie_j\sigma_b(B)$. Observe that we can find this in $O(\alpha)$ (where $\alpha$ is the cardinality of $\sigma_a(A)$) with the following pseudocode:

for each a in A:
   find foreign tuple in B  // constant-time, if using hash table
   check if foreign tuple meets foreign constraint  // again, constant time

As mentioned by some answerers, there are various minor permutations (do the for loop over B instead, etc.). But they all seem to be $O(\alpha)$ or $O(\beta)$. Is there a better way?

Note that if it the query were a self join, we could just do the merge part of a sort-merge join, (since our indexes would already be sorted) which would run in time proportional to the number of results. So I ask if a similar thing can be done here.

I am more than happy to accept a proof that there is no better method as an answer. I believe that there is no faster algorithm, but I'm unable to prove it.

When an SQL statement is turned into an execution plan, several optimization techniques are used. The use of indices allow to efficiently (without a full scan) select tuples that agree with a selection condition. Another technique in use is semantic optimization, id est, to turn a query into an equivalent one with better behaviour. To do so, identities of relational algebra are used.

For specifically, in the example, the identity between selection and product

$\qquad \displaystyle \sigma_{\alpha}(C \times O) = \sigma_{\beta \wedge \gamma \wedge \delta}(R \times P) = \sigma_{\delta}(\sigma_{\beta}(R) \times \sigma_{\gamma}(P))$

(with $\beta$ being the part of the condition $\alpha$ which refers only to attributes from $C$ and $\gamma$ the one with attributes from $O$) can be used. Informally worded this identity is "pushing selection through joins/product" (the identity holding for join too). The identity can be thought as a kind of rewrite rule, reading it from left to right. So the following identity holds in the example :

$\qquad \displaystyle \begin{align}
  &\pi_{Name}(\sigma_{Preferred=True \wedge Complete=False}(C \Join_{CustomerId = Id} O)) \\
= &\pi_{Name}(\sigma_{Preferred=True}(C) \Join_{CustomerId = Id} \sigma_{Complete=False}(O))
\end{align}$

Doing so, you do not waste time computing the product of irrelevant tuples of $C$ and $O$. The more selective the $\beta$ and $\gamma$ predicates are, the larger the gain is. And IMO, I don't think you can ever lose some time using this rule.
For a more formal treatment of this aspect of optimization, one can look at the Static Analysis and Optimization chapter of the Foundation of Databases book.


Language is non-empty is recursively enumerable (intuitive way) $M$ is some Turing machine, $\left<M\right>$ is the code of the Turing machine.

$L =\{\left<T\right> | L(T) \ne \emptyset\}$

How to see intuitively that $L$ is partially decidable?

We can try running a given $M$ on all strings and accept if $M$ accepts.
However, what if the simulated $M$ gets into an infinite loop?

A language $L$ is partially computable if there is a machine $M$ that on input $x$:

If $x \in L$ then $M$ halts.
If $x \notin L$ then $M$ doesn't halt.

This is equivalent to the other definitions.

To answer your question, what we do is to run the input machine $M$ on all inputs in parallel. If it never accepts on any input, then we never halt, but that's ok.

In order to run $M$ on all inputs in parallel, we use the technique of dovetailing:

We run $M$ for one step on the first input.
We run $M$ for one step on the first two inputs.
We run $M$ for one step on the first three inputs.
And so on.


How would the use of an external lookup table affect file compression? It occurred to me that, the way compression essentially works, is that you have a mapping of long patterns to short patterns, which you replace one way to compress and the other to decompress. My understanding of the way compression algorithms work, is that they create this mapping dynamically, with things like huffman coding being used to create the lookup table.

And so I wonder: if a general lookup table was pre-built, and not derived in any way from the input file, how would this affect the compression? My guess would be that if would make the compression slightly less effective (because the ordering of the mappings would not be optimized for the specific case), but would make it much faster to run, since it doesn't need to build the table as it goes.

There are compression programs such as zstd which explicitly allow a separate dictionary text, and stream-based compressors such as LZW can be easily converted to use a dictionary by prepending it on the input. The dictionary appears as a fixed prefix on the output and can be removed, ie $C(xy)=C(x)C(y|x)$.

The benefit of using one text as a dictionary for another is a function of their mutual information, which is based on Kolmogorov Complexity (an incomputable minimum).   However a compression algorithm turns out to be a good way to approximate it, using a technique known as Normalized Compression Distance.  The texts are compressed separately and together as above, and the difference between $C(y|x)$ and $C(y)$ measures similarity.  So, while it's difficult to predict the benefit, measuring it empirically has some uses.


Find a source-sink-path that touches a subset of edges I have a directed graph that has a source node and a sink node and a subset of marked edges.

I need to find a path from source to sink that contains at least one marked edge and is cycle-free.

If the path did not have to be cycle free this would be easy: let $s$ and $t$ be the source/sink, take two copies of the graph, say $(V_1, E_1)$ and $(V_2, E_2)$, and for any marked edge $\{v_i, v_j\}$ in the original graph, add $\{v_{1i}, v_{2j}\}$ and $\{v_{2i}, v_{1j} \}$ to the new graphs (connecting them), then find a path from $s_1$ to $t_2$.

For the cycle-less case, the best I can think of is a solution using max flow: iterate over all marked edges $\{u, v\}$, add a supersource and supersink to the graph, add edges from the supersource to the original source and sink $s$ and $t$, and edges from $u$ and $v$ to the supersink. Then find two vertex disjoint paths from the supersource to the supersink (we consider two paths to be vertex disjoint if the only shared vertices are the supersource and supersink, there are at most two of these paths). If no two paths exist, you cannot use the edge $\{u, v\}$, otherwise you can reconstruct the full path using the flow you found.

Finding these vertex disjoint paths is not entirely trivial, you'll need to transform the graph a little (see e.g. here), but it will only increase the size of the graph linearly.


How to divide an unsorted list in linear time where every element in the first part is smaller than every element in the second list How to divide an unsorted list into two equal parts in linear time, where every element in the first part is smaller than every element in the second part

I tried to use QuickSort but in can result in $O(n^2)$ worst-case time complexity.

Use the median of medians with quickselect allows you to find the $k$th element in linear time. Set $k = n/2$ to find the exact median and use it to partition your array in one more linear time step.


Does array always have a wasted space of O(n)? In this question it's stated that dynamic array wasted space is O(n). Here is the explanation why:

  Because, when a dynamic array is full, its size is increased by some
  factor α. This means that, immediately after growing, a dynamic array
  holding n items has size about nαnα, so the amount of wasted space is
  n(α−1)=O(n)n(α−1)=O(n).

I'm wondering if it's always O(n). Maybe there is some logic similar to this one which proves that wasted space is not O(n)?

It depends on the algorithm used. Someone made the assumption that when an array has space for n items, and the n+1st item needs to be added, the array would be resized to a size c·n for some constant c > 1. But there is nothing forcing us to do this; we could resize from n items to f (n) items, where f (n) ≥ n+1 obviously but f (n) - n = o (n).


If there is an polynomial time approximation to an NP-complete problem, is P approximately NP? Deciding bipartite hypergraph coloring is NP-hard:

  While for bipartite graphs a 2-coloring can be found in linear time, it was shown by Lovasz [10] that the problem to decide whether a given k-uniform hypergraph is bipartite is NP-complete for all k≥3.

Bipartite hypergraphs are colorable in expected (average) polynomial time:

  The purpose of this note is to present an algorithm that colors a hyper-graph chosen uniformly at random from the family of all labeled, 3-uniform, bipartite hypergraphs on n vertices in O(n^5 * log (2n)) expected time.

Does this imply that P is approximately NP?

Source: https://www.math.uni-hamburg.de/home/schacht/abstracts/09eurocomb.pdf

No, it doesn't prove that P = NP.

This has nothing to do with approximations; it has to do with average-case hardness vs worst-case hardness.  The two results are showing that solving the problem for a randomly chosen hypergraph is usually easy; but there exist hypergraphs where the problem is hard.  Presumably, choosing a hypergraph at random is very unlikely to give you one that's hard, but they do exist.

NP-completeness is about worst-case hardness: even if a problem is easy on average, it can still be NP-complete.

I have no idea what "P is approximately NP" would mean in any precise sense.


How to decode multiple-digit gamma codes and get the gap sequence? How to decode gamma code ($\gamma$ code):

1110001110101011111101101111011

and get the gap sequence?

Detailed information about Gamma codes ($\gamma$ codes) with a brief example of decoding can be found here.

But in their example there is only one case when gamma code ($\gamma$ code) consists of one digit only, how to deal with multiple digits binary string?

The above sequence it read as a concatination of 5 numbers:

You start from the left side, read the first unary code. It let's you know what is the length of the first number. The 2nd number starts right after the 1st, and you interpet it the same way.

First, read the first unary code, it is 1110 - so the first number
is "1110:001", which is 9
The next unary code is right after this, and is: "110" - so the 2nd number is "110:10" which is 6
The next unary code is "10", and the 3rd number is "10:1", which is 3
The next unary code is "111110", and the 4th number is "111110:11011", which is 32+16+8+2+1=59
Next unary number is "110", which gives you the 5th and last number, which is "110:11", which is 7.

So, the decoding of the given gamma code is actually 9,6,3,59,7


exercise on Huffman encode I have these 4 symbols with their probabilities:

 x   P(x)
 --------
 1   0.3
 2   0.3
 3   0.2
 4   0.2

I built the Huffman tree in this way:

and I obtainded:

 x   P(x)   C(x)
 ----------------
 1   0.3     0
 2   0.3     10
 3   0.2     110
 4   0.2     111

it's correct? Because according to the solution the results should be:

 x   P(x)   C(x)
 ----------------
 1   0.3     00
 2   0.3     01
 3   0.2     10
 4   0.2     11

Why?
Yet I followed the steps shown here.

A quick way to check whether your answer has a chance of being correct is to compute the average code length. Your encoding gives the average length of $2.1$, which is greater than using a code of fixed length $2$, so it can't be correct.

If you follow the priority queue algorithm from the source you cite, then you would notice that after merging nodes 3 and 4 you get one supernode of priority 0.4. Now your queue would have three elements of priorities $0.3, 0.3,$ and $0.4$. Thus, you would next merge elements corresponding to priorities $0.3$ and $0.3$ (the algorithm works by merging two nodes with lowest priorities), which happen to be nodes 1 and 2.


Turing machine that does not halt on any input I'm struggling to find a way to show that
$$T = \{ \langle M \rangle\mid M \text{does not halt on any input}\}$$
is undecidable.
Should I use reduction? If so, reduce this to what &ndashp the halting problem?

To use reduction, you would need to show that the halting problem reduces $T$, not the other way around.

The reduction* in this case is a standard one. You want to know if $M$ halts on input $w$ but all you have is this lousy T-shirt a procedure that tells you if a machine loops on every input. So you construct a machine $M'$ such that does the same thing on every input, so that whether or not $M'\in T$ tells you whether or not $M$ halts on input $w$.

* Well, strictly a reduction: if there's one, there are infinitely many.


Binary symmetric sources and information theory How can we generate 3 or more binary Sources using BSC channel.
As we know, BSC can be easily used to generate 2 binary sources with some cross-over-probability(say p). Eg, length of codeword(say n) n = 1000; p = 0.2, then input and output binary codeword will be having Hamming distance of approx 200. In this way we generate 2 Binary sources with 200 Hamming distance from each other.

My question is: How can we generate multiple Binary with same cross-over-probability or multiple binary sources with approx similar Hamming distance from each other. E.g: X, Y , Z, W. and they should have similar Hamming distance from each other(all combinations(X-Y)(X-Z) and so on).

And, there should be some way to calculate the joint entropy for them.
I am trying to make some scheme to do that, if u have some ideas .. just discuss it.
please let me know for any questions.. I will surely clear them

Thanks

You want to generate $n$-bit random variables $X_1,\dots,X_m$ such that the Hamming  distance between $X_i,X_j$ is about $pn$.  Let me start by showing you how to do this for the special case where $n=1$; then I'll generalize.

Set $q = (1 - \sqrt{1-2p})/2$.  Pick a set $S \subseteq \{0,1\}^m$ of $m$-bit values, such that every element $s \in S$ has Hamming weight $qk$.  Now pick a random $s$ from $S$, randomly permute the bit positions of $s$, and assign this to $X_1,\dots,X_m$ (i.e., $X_i$  is the $i$th bit  of $s$).  I claim this will have your desired property.  Why?  Well,

$$\Pr[X_i \ne X_j] = \Pr[X_i=0,X_j=1] + \Pr[X_i=1,X_j=0] = 2q(1-q) = p,$$

so the expected value of the Hamming distance between $X_i,X_j$ will be about $p$, as desired.  The joint  entropy is easy to calculate: it is simply $\log_2 |S|$.

What if we want $n>1$?  Then we can just sample the first bit of $X_1,\dots,X_m$ as above; then sample the second bit of $X_1,\dots,X_m$ in the same way (iid; i.e., pick another  $s$ from $S$, and randomly permute its bit-positions); and so on.  This gives us a source where the expected value of the Hamming distance between any  two $X_i,X_j$ is about $pn$, and where the joint entropy is $n \log_2 |S|$.


Camera position w.r.t. basketball court I am new in Computer Vision. Suppose you have 8 points (players in a basketball court) in a 2D image (png photo), that is we know the pixel coordinates of each. I would like to compute camera position w.r.t. the field. We have the actual dimensions of the field. Also, I can write the equations of two or three transversal lines in the field that are parallels lines from top view. With this data can we find a position vector of the camera w.r.t. the field ?

  Any idea on where to read about this ?

You said you could see lines, so I assume you could see their intersections. If you could assume to have at least 4 fixed points of the court which are always visible (corners might be a good choice), this problem is similar to the 3D pose estimation problem, since you are essentially looking for a pose (position and orientation) of a known 3D object in a 2D image.

You might find it useful to read about POSIT, an iterative algorithm published in 1992 and there is also this algorithm from 1999. Both algorithm solve the 3D pose estimation problem.


Decidability of prefix language At the midterm there was a variant of the following question:

  For a decidable $L$ define  $$\text{Pref}(L) = \{ x \mid \exists y \text{ s.t. } xy \in L\}$$
  Show that $\text{Pref}(L)$ is not necessarily decidable.

But if I choose $L=\Sigma^*$ then I think $\text{Pref}(L)$ is also $\Sigma^*$, thus decidable. Also $L=\emptyset$ gives the same result. And since $L$ must be decidable I cannot pick the halting problem or such..

How can I find $L$ such the $\text{Pref}(L)$ is not decidable?
Which conditions on $L$ will make $\text{Pref}(L)$ decidable, and which will make it undecidable?

Note that using an existential quantifier in front of a decidable language we can obtain any r.e. language, i.e. every r.e. language is expressible as

$$ \{ x\in \Sigma^* \mid \exists y \in \Sigma^* \ \langle x,y \rangle \in V \} $$

where $V$ is a decidable language. These include undecidable r.e. languages like
$$A_{TM} = \{ \langle e, x\rangle\ \mid \text{$e$ encodes a Turing machine which accepts $x$} \}$$.

The only difference here is that here we have to separate $x$ and $y$ ourselves. The standard trick is to use a new symbol to separate the two parts (assume that the separator belongs to $y$). Therefore any r.e. language including undecidable ones can be expressed in this format.

For the second question, there is no general algorithmic way to check if the prefixes of a  given decidable language is undecidable. This follows from Rice's theorem.


How can we construct a TM with a Halt1 Oracle that decides if a TM halts on all inputs? Can we construct an explicit Turing Machine with a Halt1 oracle that decides if a standard Turing Machine halts on all inputs?

By a Halt1 oracle I mean that we have the ability to decide if Turing Machines with a Halting oracle halts or not.

I think that I have an answer to this, putting together my question helped me clarify things enough to come up with this idea
def X(T : TM0):
   for n = 0 and up:
      if !Halt0('T(n)')
        return

Now if we ask Halt1('X(T)') we should get an answer

yes => T diverges on some input
no => T halts on all inputs

Does this all make sense logically?


How are graph representations containing only (i, j) instead of both (i, j) and (j, i) named? When working with undirected graph algorithms using an adjacency-list type structure, it's sometimes enough to store a given edge (i, j) just stored in the list of edges of i or on the list of edges of j. Other times, it's important to have an (i, j) on i and a (j, i) on j.

I was wondering how do you call graph representations of one type and graph representations of the other type? Without concrete names to give to each one of them, code or even conversations about certain algorithms get confusing really fast.

Your second kind of representation is simply called the adjacency list representation.  It's a standard representation for graph data structures.

To my knowledge, there is no standard name for your first kind of representation; it's a weird and non-standard kind of representation.  That's probably because it's not sufficient for most algorithms on undirected graphs (most algorithms require more), whereas the adjacency list representation is sufficient for most algorithms on undirected graphs.  So, it would be rare to find situations where your first kind of representation is sufficient and useful.

You say that your first kind of representation is sufficient for Kruskal's algorithm, but this might be a bit misleading.  In fact, Kruskal's algorithm is fine with something even more minimal: merely having a list of all edges is sufficient for Kruskal's algorithm.  In other words, Kruskal's algorithm does not require the edge (i,j) to be associated with either i or j (it's OK if it's not associated with either, as long as you have a list of all edges).

In general, your first kind of representation does not seem like a natural choice for any graph algorithm that I can think of right now, so it's not surprising if it doesn't have a standard name.


Count Sketch probability bound I have been reading up on the Count Sketch algorithm, and I stumpled upon the Count Sketh algorithm explained in section 5 of https://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf. Then, I tried to solve some of the exercises. However, exercise 5-3 is causing me some problems.
If we let $\hat{f}_a$ denote the estimated frequency associated with a key $a$ and $f_a$ be actual frequency associated with key $a$, then it can be show that $E[\hat{f}_a]=f_a$. Furthermore, for $j\in[n]$, we let $\mathbf{f}_{-j}$ be the $(n-1)$ dimensional vector obtained by dropping the $i$th entry of frequency vector $\mathbf{f}.$ It can then be shown that
$$
\text{Var}[\hat{f}_a]=\frac{||\mathbf{f}_{-a}||_2^2}{k}
$$
when we use the hash function $h : [n] \rightarrow [k]$. Thus, using Chebyshev's inequality, it can be shown that
$$
\text{Pr}[|\hat{f}_a - f_a| \geq \epsilon ||\mathbf{f}_{-a}||_2] \leq \frac{1}{3}
$$
for $k=\frac{3}{\epsilon^2}$.
In exercise 5-3, $\textbf{f}_{-a}^{\text{res}(\ell)}$ denotes the $(n-1)$-dimensional vector obtained by setting the $\ell$ largest (by absolute value) entries to zero in $\mathbf{f}_{-a}$. The exercise then essentially asks the reader to show that
$$
\text{Pr}[|\hat{f}_a - f_a| \geq \epsilon ||\mathbf{f}_{-a}^{\text{res}(\ell)}||_2] \leq \frac{1}{3}
$$
where $k=\frac{6}{\epsilon^2}$ and $\ell=1/\epsilon^2$. However, I don't know how to show that the inequality above holds. I have tried using Chebyshev's inequality, but I still can't seem to make it work. Any help would be appreciated.

$\newcommand{\norm}[1]{\left\lVert#1\right\rVert}$
Denote the support of $f$ by $f_1\le f_2\le...\le f_s$. Given a frequency sequence $f$, denote by $E_{f,a}$ the random variable $\hat{f}_a$ where the stream frequencies are given by $f$ (the evaluation depends on the inner randomness of the sketch and the input stream).
The probability that the hash of one of the top $\ell=1/\epsilon^2$ elements collides with the hash of some given element $a$ is bounded by $\frac{\ell}{k}$ (union bound). Conditioning on the event that such a collision did not occur, the evaluation $\hat{f}_a$ does not depend on the top $\ell$ entries, as they do not affect the hash entry of $a$. More formally, conditioned on the event $C=\bigcap\limits_{i=0}^{\ell-1}\mathbb{1}_{h\left(f_{s-i}\right)\neq h(a)}$, $E_{f,a}$ and $E_{f^{res(\ell)},a}$ are equally distributed. This yields:
$$\Pr\left[\left|\hat{f}_a-f_a\right|\ge \epsilon\norm{f_{-a}^{res(\ell)}}\right]=
\Pr[C]\cdot \Pr\left[\left|\hat{f}_a-f_a\right|\ge \epsilon\norm{f_{-a}^{res(\ell)}}\big| C\right]+\\
\left(1-\Pr[C]\right)\Pr\left[\left|\hat{f}_a-f_a\right|\ge \epsilon\norm{f_{-a}^{res(\ell)}} \big|\overline{C}\right]\le\\
\Pr\left[\left|\hat{f}_a-f_a\right|\ge \epsilon\norm{f_{-a}^{res(\ell)}}\big| C\right]+\frac{1}{6}$$
Since $E_{f,a}, E_{f^{res(\ell)},a}$ are equally distributed (conditioned on $C$), the left hand term equals $\Pr\left[\left|\hat{f}_a-f_a\right|\ge \epsilon\norm{f_{-a}}\right]$, which you can bound by $1/6$ with your original result.