To check if a chain with $n$ links can be "folded" into a size at most $L$ Given a chain of $n$ links, each of length $a_1, a_2,..a_n$, where each $a_i$ is a positive integer. $L$ defines the length of the "folded" chain. More formally, we want to decide whether there exists a $t \in [0, L]$ and $s_1,...,s_n \in \{-1, +1\}$ such that $t + \sum_{i=1}^j(s_ia_i)\in[0,L]$ for all $j\in\{0,..,n\}$.

For example, given $a_1 = 5, a_2 = 1, a_3 = 7, a_4 = 2, a_5 = 8,$ and $L = 9$ a possible solution could be $5+1-7-2+8$ such that the entire chain is contained within a space of $9$ units.

We need to provide an $O(nL)$ time algorithm to decide if the chain can be folded or not.

My approach:
I tried a couple of different approaches:

Greedy algorithm: starting with the first link, check if it is greater than $L$, if yes then subtract $(s = -1)$ the second link from the first link. If it is still greater than $L$, the repeat. If it was not greater than $L$ initially, then add the second link to the first. This approach failed.
Tree approach: For every link, we can have $s=1$ or $s=-1$, this gives us $2^n$ possible arrangements. We can create a binary tree of size (layers) $n$ from this. But this method won't work due to the sheer size of the tree.

Any hints or guidance is appreciated.

I was also thinking that if $L$ is not given, is there a way to determine $L$ such that it is the best folding possible?

The crux of the problem is to identify when we can extend a chain $t, s_1a_1, \cdots, s_ka_k$ to a longer chain?
Let $m$ be the length of that chain, i.e., $m= t +\sum_{i=1}^ks_ia_i$. If $m+a_{k+1}\in [0,L]$, then we can extend it with $+a_{k+1}$. If $m-a_{k+1}\in [0,L]$, then we can extend it with $-a_{k+1}$. Otherwise, the chain cannot be extended.
An approach by dynamic programming.
Create a $(n+1)$-row by $(L+1)$-column table $F$ (shorthand for foldable). All entries of $F$ are False initially. $F[k][j]$ will be true if there is a chain made from $a_1,\cdots, a_k$ with length $j$ and within space $L$.

Set $F[0][j]=\text{True}$ for all $j$, $0\le j\le L$. According to the analysis above, $F[k+1][j]$ is true in two cases.

$j-a_{k+1}\in [0,L]$ and $F[k][j-a_{k+1}]$ true.
$j+a_{k+1}\in [0,L]$ and $F[k][j+a_{k+1}]$ true.

In other words, we can fill all values at row $F[k+1]$ if we know all values at row $F[k]$.
If $F[n][j]$ becomes True in the end for any $j$, then we return yes. Otherwise, return no.
Explanation on 5, 1, 7, 2, 8
     0   1   2   3   4   5   6   7   8   9
t 0  T   T   T   T   T   T   T   T   T   T
5 1  T   T   T   T   T   T   T   T   T   T
1 2  T   T   T   T   T   T   T   T   T   T
7 3  T   T   T                   T   T   T
2 4  T       T   T   T   T   T   T       T
8 5  T                           T

The fourth row $F[3]$ corresponds to chains of the form $t$, $\pm5$, $\pm1$, $\pm7$. Their lengths can only be 0, 1, 2, 7, 8, 9. Now if you add $\pm2$ to them, you can get lengths
     2,  3, 4, 9, 10, 11 (for +2)
    -2, -1, 0, 5,  6, 7  (for -2)

So the possible lengths of chains of the form $t$, $\pm5$, $\pm1$, $\pm7$, $\pm2$ are 2, 3, 4, 9, 0, 5, 6, 7, which correspond to row $F[4]$.
How to find the smallest realizable $L$?

A binary search on integers in [a_1, 2M-1] should be a nice way to find the answer, where $M$ is the maximum value of $a_i$s. Binary search is feasible since, if $L$ is realizable, values larger than $L$ are realizable too.
Exercises
Exercise 1. (One minute or less) Show that the smallest realizable $L$ is at most $2M-1$, where $M$ is the largest of $a_i$s.

Exercise 2. Adjust the algorithm if $s_i\in\{-2,-1,1,2\}$ for all $i$ instead of $\{-1,1\}$.


generate possible inputs valid for automata I find lots of solution where you have an Automata and a input string , you can validate whether input string is accepted by automata or not.

Can we do the reverse ?

I am looking for solution which generates few possible inputs (not all) accepted by automata(NFA/DFA).

One of the Brute-force approach can be to randomly select inputs and validate with automata if passes then consider those as desired .

But really don't want that . What really am i looking for here, can we use automata itself for produce possible inputs which are accepted by automata.

Any approach also would be helpful.

Just do a BFS from the start state, and at every node keep track of what transitions you took to get there. Obviously this will only generate a finite number of words, as it doesn't follow cycles.


Minimising sum of consecutive points distances Manhattan metric I have two sets $X$ and $Y$ of 2-dimensional points. The points are floating point numbers. The objective is to sort them in such way that sum of differences in distances of consecutive sorted points is minimal.

I tried to solve this problem by localisation (dividing the plane by smaller grids of sorted points) and then connecting clusters - but this is a greedy and an approximate approach - the problem here is in setting grid size, but this is not guaranteed to give any bounds on how optimal the solution is, and it is rather time consuming (without a well-defined objective function).

Another attempt was to sort them by the x-coordinate, then find the minimum. But this approach fails. Normal sorting by two coordinates fails and is highly unstable.

The problem resembles the TSP problem, but the "path" is not closed and metric used is L1 (Manhattan, TaxiCab).

The solution I am looking for will probably be approximate. Finding the minimal and the second minimal distance from every point and connecting them gives good but for sure not minimal sum.

The problem I am having is with giving the objective function.

Your problem is very close to TSP on the plane with the L1 metric. For this problem, there is a PTAS due to Arora, while the problem itself is probably NP-hard. Practically speaking, if your goal were indeed TSP rather than its "Hamiltonian path" variant, you could apply any approximation algorithm that works for metric TSP.


NL - iterating all edges of a graph in log space Given a turing machine which has logrtmic space, and consists of an input tape and a working tape, Is it possible to iterate all egdes of an input graph? I know the answer is probably NO, because clique and other similer NP problems  belongs to NP and not to NL. Unfortunately, I can't find a satisfying and clear explanation to that fact. Can some one make it more clear for me?

There's absolutely no problem to iterate over all edges in a graph in logspace (even deterministic logspace!). The details depend on how the graph is encoded. For example, if the graph is encoded as an adjacency matrix, then you can simply go over all pairs of vertices.

However, this doesn't give an NL algorithm for clique. The problem is that you need to iterate on $k$-tuples of vertices, for non-constant $k$. This is something you cannot do in logspace.

NP is sometimes described in terms of witnesses. However, the "official" definitions is using nondeterministic Turing machines, which are allowed to have more than one correct move at any given point in time. The class of languages accepted by nondeterministic polytime Turing machines coincides with the class of languages which are given a polynomial size witness and can verify it in polynomial time. Unfortunately, there is no such alternative description for nondeterministic logspace Turing machines.


Generate the context free grammar for the following language: $\left \{ a^{3n}b^{m}c^{n}|n>0, m>0\right \}$ Given the following language, I am tasked with giving a context-free grammar that generates it.
$\left \{ a^{3n}b^{m}c^{n}|n>0, m>0\right \}$
Would this be correct?
$A \rightarrow aaaA$
$B\rightarrow Bb | b$
$C\rightarrow Cc|c$
$S\rightarrow ASBSCS|\epsilon $

Unfortunately your grammar generates only $\epsilon$ (which is not in the language, since $n$ and $m$ are greater than 0), as you don't delete the $A$; moreover you don't control that the number of $A$'s is thrice the numeber of $C$'s.
You can try something like this:
$S\rightarrow aaaS'c$
$S' \rightarrow aaaS'c | B$
$B\rightarrow Bb | b$


On the generalization of two recreational problems: request for references, if there's any I wonder if two famous (and, IMHO, very nice) recreational problems are been studied in some general form.

Here's the first.
We have 13 balls, all looking absolutely the same, with 12 of them having the same weight; we don't know whether the ball that has a different weight is heavier or lighter. We have a balance with two arms and, using it at most 3 times, it is required to identify the ball with different weight.
For the generalization below, I will consider a slightly different version of it: same scenario, but requesting the needed minimum number of times by which, in all cases, using the balance we can identify the different ball.

Here's the second.
We have three card and we are in front of a door with three slot in which we can insert the cards. Each card is the correct one for exactly one slot and vice versa.
Each slot is connected to a hidden circuit and, at the beginning, we don't know wheter a circuit is opened or closed (but at least one of them is opened).
The door will open only if all three circuits are closed.
We can change the state of a circuit solely by inserting all the three cards; when we insert all the cards, the circuits change state according to these rules: if a circuit is closed, it will open; if a circuit is opened, it will close only if the correct card is inserted in its slot.
In general, without knowing the initial states of the circuits, what is the minimum number of insertions by which the door will certainly open?

We can generalize the above problems in obvious ways: the first problem by having $n$ balls (possibly, with $k$ of them having different weight), the second problem by having $n$ cards/slots/circuits (possibly, each card being correct for more than a slot/circuit).

Are these general problems new? Any similar and well-studied one?

The first problem is well-known. Lots of different generalizations appear in this paper, which is listed in the Wikipedia entry on the 12 coins problem.

I've never heard of the second problem, but it is similar in spirit to the carrom board puzzle (which probably goes under other names as well), described in a note by Dijkstra. A further generalization appears in this writeup.


Master Theorem Usage I know how to use the master Theorem for a general formula e.g. $T(n) = a \cdot T(\frac{n}{b}) + f(n)$.

I saw some books suggest that we can use the mastere theorem for formulas like:
$T(n) = T(\frac{n}{5}) + T(\frac{7n}{10}) + O(n)$

How is that possible?

My guess: We use it separately. Once for $T(n) = T(\frac{n}{5}) + O(n)$ and once for $T(n) = T(\frac{7n}{10}) + O(n)$ and join between.

Thanks!

You can use the idea of the Master Theorem and apply it to these occurrences. That is what I have done here, I would recommend looking at that answer because it will answer your question.

Basically we can look at the fractional terms inside the recurrence calls. If the sum to less than $n$, then the "conquer" part of "divide-and-conquer" will dominate the "divide" part.

For your example we have the fractions: $\frac{n}{5} + \frac{7n}{10} = \frac{9n}{10} < n$. Therefore the $O(n)$ term will dominate and the overall time complexity will be $\Theta(n)$. This is an idea of the Master Theorem, figuring out which dominates: "divide" or "conquer". Again, I highly suggest looking at this answer for a more in-depth proof.


How are kernels (and operating systems in general) written in C? I'm trying to understand how you set about writing an OS in something like C.
I've always used C to write applications - using commands like malloc and fork and so on to request things from the OS. If these methods don't exist when you're programming the OS itself (or perhaps the Kernel in particular), how do you write them?
If I can summarise what I'm stuck on:

Am I right in thinking that fork, malloc, etc. are wrapper methods that call the Kernel?

Do the OS components' code call the Kernel the same way you would call a library? Is it more like it's a microservice you make calls to? When we say that Windows provides a 'hosted' implementation of C, is this what the methods are doing under the hood?

When you have a 'freestanding' implementation of C, are the standard libraries written in Assembler, but have C headers?

Are the freestanding components of a hosted C implementation implemented the same way they would be if they were freestanding?

How do you implement memory and process management in C, what is exposed to allows you to do this in the language? (what do you call to interact with memory / devices / interrupts?)

I can imagine this isn't a small question, so I'm more than happy for an answer that includes some further reading but if you'd be able to summarise the main points related to each question that would be super handy for me!
Thanks in advance!

Today, you can definitely write an OS in C because you have compilers readily available on some OSes. You just have to decide with what executable format you are going to go and then parse it from a bootloader like a UEFI bootloader which has to be written in C as well. Linux is compiled to an ELF executable which is then compressed. Linux follows the multiboot specification (https://www.gnu.org/software/grub/manual/multiboot/multiboot.html) which allows one bootloader (GRUB) to boot the Linux kernel by following the specification.

Am I right in thinking that fork, malloc, etc. are wrapper methods that call the Kernel?

You are quite right. For example, when you write a C app on Linux, you are probably using gcc to compile your app. gcc comes with glibc which is the library implementation of the C standard on Linux. You can look at the source code of glibc (https://github.com/lattera/glibc) to look at the implementation.
For example, malloc is in malloc/malloc.c. Its definition is a one liner like strong_alias (__libc_malloc, malloc) (https://code.woboq.org/userspace/glibc/malloc/malloc.c.html#malloc). I didn't study the source code much but I think this means that a malloc call is a __libc_malloc call. The link I provided is good because it has the function definitions to the right that you can click on to go to the line.
__libc_malloc definition
void *
__libc_malloc (size_t bytes)
{
  mstate ar_ptr;
  void *victim;
  void *(*hook) (size_t, const void *)
    = atomic_forced_read (__malloc_hook);
  if (__builtin_expect (hook != NULL, 0))
    return (*hook)(bytes, RETURN_ADDRESS (0));
#if USE_TCACHE
  /* int_free also calls request2size, be careful to not pad twice.  */
  size_t tbytes;
  checked_request2size (bytes, tbytes);
  size_t tc_idx = csize2tidx (tbytes);
  MAYBE_INIT_TCACHE ();
  DIAG_PUSH_NEEDS_COMMENT;
  if (tc_idx < mp_.tcache_bins
      /*&& tc_idx < TCACHE_MAX_BINS*/ /* to appease gcc */
      && tcache
      && tcache->entries[tc_idx] != NULL)
    {
      return tcache_get (tc_idx);
    }
  DIAG_POP_NEEDS_COMMENT;
#endif
  if (SINGLE_THREAD_P)
    {
      victim = _int_malloc (&main_arena, bytes);
      assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
              &main_arena == arena_for_chunk (mem2chunk (victim)));
      return victim;
    }
  arena_get (ar_ptr, bytes);
  victim = _int_malloc (ar_ptr, bytes);
  /* Retry with another arena only if we were able to find a usable arena
     before.  */
  if (!victim && ar_ptr != NULL)
    {
      LIBC_PROBE (memory_malloc_retry, 1, bytes);
      ar_ptr = arena_get_retry (ar_ptr, bytes);
      victim = _int_malloc (ar_ptr, bytes);
    }
  if (ar_ptr != NULL)
    __libc_lock_unlock (ar_ptr->mutex);
  assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
          ar_ptr == arena_for_chunk (mem2chunk (victim)));
  return victim;
}

__libc_malloc calls _int_malloc which does the main work. It is very long so you can browse it on the link I provided. It is defined as:
/*
   ------------------------------ malloc ------------------------------
 */
static void *
_int_malloc (mstate av, size_t bytes)

I'm pretty sure that this is the malloc you are looking for. In _int_malloc there are these lines:
/* There are no usable arenas.  Fall back to sysmalloc to get a chunk from
     mmap.  */
  if (__glibc_unlikely (av == NULL))
    {
      void *p = sysmalloc (nb, av);
      if (p != NULL)
        alloc_perturb (p, bytes);
      return p;
    }

If there are no usable free chunks in already allocated memory, fallback to mmap to get more memory. sysmalloc is again very long but it calls mmap as a macro defined like:
#define MMAP(addr, size, prot, flags) \
 __mmap((addr), (size), (prot), (flags)|MAP_ANONYMOUS|MAP_PRIVATE, -1, 0)

Do the OS components' code call the Kernel the same way you would call a library? Is it more like it's a microservice you make calls to? When we say that Windows provides a 'hosted' implementation of C, is this what the methods are doing under the hood?

When you write a C app on Linux, you include headers from glibc to use the standard functions like malloc, fork etc. When you compile your app, you either compile it statically or dynamically. When you compile it statically, you include all the kernel code in the executable like mmap's code. Basically, when mmap is called from your main function, the CPU jumps to the function which is mapped in virtual memory. Where it "stops" including the code, is when you jump to kernel code using int 0x80 on older x86 32 bits processors. I don't know about the system call convention for x86-64 honestly. It is probably similar. When your code calls int 0x80 on x86, it interrupts the CPU and it jumps to shared-by-all-processes kernel code. This kernel code cannot be included in your executable because it is interrupt code. So mmap is included in your executable up until the system call. The rest of the work is done in the interrupt handler and then returns to mmap which now has the new address of the allocated memory chunk. mmap then returns to the glibc caller which, like you said, is a wrapper around kernel code calls. When you link dynamically, it is the same except linking happens just before runtime.

When you have a 'freestanding' implementation of C, are the standard libraries written in Assembler, but have C headers?

You don't need to write the implementation of C in assembly. glibc is written completely in C. Most of the Linux kernel is also written in C. Some parts of the kernel code needs to be written in inline assembly. For example, the system calls need to be done with a int 0x80 call that you can't make from pure C.

Are the freestanding components of a hosted C implementation implemented the same way they would be if they were freestanding?

This is a lot of terminology and I don't get what you mean by freestanding and hosted here. A freestanding implementation means that you use only the base of C because you don't have access to library functions like you would in a development environment like Windows or Linux. For example, an OS needs to be written in static, freestanding C because you need all code to be included in the final executable and because you can't depend on a runtime which includes things like standard libraries, system calls and other stuff like that. Actually, freestanding means that you really use only the components of C that you know are going to be included in the final executable and which are going to be compiled to assembly which doesn't depend on a particular runtime.

How do you implement memory and process management in C, what is exposed to allows you to do this in the language? (what do you call to interact with memory / devices / interrupts?)

C includes pointers which allow to do all that and more. In a freestanding environment (like when you develop an OS), you can just use absolute addresses and it just works because you don't have things like memory protection. You do have memory protection but you are the one in control of it. If you just type something like int* pointer = (int*) 0x8000;, you have a pointer of type int which points to 0x8000. If you type *pointer = 0x34, then at the address 0x8000 is now 0x00000034. That is because an int is 4 bytes. If you type unsigned char* pointer = (unsigned char*) 0x8000, and then *pointer = 0x34, at the address 0x8000 is now 0x34. That is because a char is one byte. You see that you can control memory pretty easily in C. You can put whatever values you want at the byte level. You can even work at the bit level using bitwise operators.
Today, most devices have memory mapped registers. By accessing memory using pointers, you can write commands to the registers of these devices and tell them to do stuff. If you ever need to access some IO ports or to do a system call like with int 0x80 then you have inline assembly from C which allows to do it. Also, the BIOS builds ACPI tables in RAM in conventional position which allows the OS kernel to find the location of the different registers.
Hope this answers your questions.


Is "Reachable Object" really an NP-complete problem? I was reading this paper where the authors explain Theorem 1, which states "Reachable Object" (as defined in the paper) is NP-complete. However, they prove the reduction only in one direction, i.e. from 2P1N SAT to Reachable Object. This only proves that the problem is NP-hard; do we not need to prove the reverse direction (2P1N to Reachable Object) to prove NP-completeness?

A problem $P$ is NP-complete if:

$P$ is NP-hard and
$P \in \textbf{NP}$.

The authors give a proof of item number 1. Item number 2 is probably apparent (and should be clear to the paper's audience). For the proof of item number 1, you only need a (many-one) reduction from some NP-complete problem (e.g., SAT) to $P$; there is no need to construct a reduction in the opposite direction.


Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and physics requires the tiling to satisfy one more condition:

The tiling should satisfy some proportionality, say, Tile 1 should appear with frequency 1/16, Tile 2 with frequency 9/16, Tile 3 with 6/16, Tile 4 with frequency 0...

The most important decision problem is the following:
Could a given set of Tile tile a grid of size NxN satisfying the frequency constraint within a error of +-epsilon.

For example: could the set {Tile 1, Tile 2, Tile 3, Tile 4} tile the NxN grid with frequency 1/16+-0.01, 9/16+-0.01, 6/16+-0.01, 0+-0.01 respectively....

From one of my previous post:

Algorithms for NP complete problem

I realize the decision problem of tiling without such constraint could be modeled by SAT... With this constraint the problem becomes ridiculously difficult and I eagerly seek for solutions towards this finite decidable problem.... (we could forget epsilon for a moment if the problem with epsilon is too hard)...

So here is the question: how do we model this problem in MIP or SAT or any other optimization algorithm?

For more detail why this problem is practical in material science and physics, see my previous post:

coloring in lattice

reference for wang tile

Computational approach deciding whether a set of Wang Tile could tile the space up to some size

P.S. this is a bounty question from mathoverflow without yet a applicable solution...

Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality

Use a SAT solver that also allows you to express pseudo-Boolean constraints.

Encoding the verification of the existence of the tiling of an NxN grid as a CNF formula is straightforward.  Each grid position will have a set of variables associated with it of which only one will be set true if a particular tile occupies that position.  Add clauses that force exactly one of each set of variables to be set true.  Add other clauses that demand grid neighbors be the correct sort of tile out of the available choices.

The epsilon requirement means requiring that only a fixed number of the grid position variables for each tile type be set true, or that the number set be within a certain range.  This is complicated by the fact that the naive expression of such constraints in CNF takes a number of clauses exponential in the number of variables involved.  There are more efficient encodings that involve adder and comparison circuits, but a solver that accepts pseudo-Boolean constraints directly will either work without such encodings or will save you the trouble of creating these circuit encodings yourself.


Is there any real difference between a compiler and an assembler? Is there any difference between the two?  As per Ullman's book, compilers  convert one language to another (usually low level) language, and so does an assembler. How are the two different?

An assembler translates assembly code to machine code. The translation is mechanical, and can be done in only one way. In contrast, a compiler has more freedom when it compiles the relevant programming language - it can optimize, for example, and even non-optimizing compilers produce different code. Also, compilers can be written in a way that separates the "front-end" (corresponding to the programming language) and the "back-end" (corresponding to the computer architecture), whereas with assemblers the two are always the same.


Definition of Closed Under Left Polynomial Composition I am studying Computation complexity using Papadimitrious's book: "Computational Complexity".
While doing Problem 7.4.4, I came across the definition of what it means for a class of functions $C$ to be closed under left polynomial composition.
Here is Problem 7.4.4:

"Let $C$ be a class of functions from nonnegative integers to nonnegative integers. We say that $C$ is closed under left polynomial composition if $f(n) \in C$ implies $p(f(n)) = O(g(n))$
for some $g(n) \in C$, for all polynomials $p(n)$. We say that $C$ is closed under right polynomial composition if $f(n) \in C$ implies $f(p(n)) = O(g(n))$ for some $g(n) \in C$, for all polynomials $p(n)$.
Intuitively, the first closure property implies that the corresponding complexity class is "computational model-independent", that is, it is robust under reasonable changes in the underlying model of computation (from RAM's to Turing machines, to multistring Turing machines, etc.) while closure under right polynomial composition suggests closure under reductions (see the next chapter).

My doubt is what is the correct way of interpreting this definition and proving that a given class of functions $C$ is closed under left polynomial composition. The definition got me confused since the part "for all polynomials $p(n)$" appeared after the part "for some $g(n) \in C$". I thought about two interpretations.

Given arbitrary $f(n) \in C$ and $p(n)$, exhibit some $g(n) \in C$ such that $p(f(n)) = O(g(n))$. Then, you have proved that $C$ is closed under left polynomial composition. I think this makes more sense, since by this definition I was able to prove that the class $C = \{n^k: k > 0 \}$ is "computational model independent", which makes sense to me.

Given an arbitrary $f(n) \in C$, exhibit some $g(n) \in C$ such that for all polynomials $p(n)$ we have that $p(f(n)) = O(g(n))$. While assuming this definition, I gave a counterexample and proved that the class $C = \{n^k: k > 0 \}$ is NOT "computational model independent", which sounds awkward to me.

Which interpretation is the correct one?
Thanks in advance.

The correct interpretation is as follows. A class $\mathcal{C}$ is closed under left polynomial composition if the following holds:

For any $f(n) \in \mathcal{C}$ and any polynomial $p(n)$ there exists $g(n) \in \mathcal{C}$ such that $p(f(n)) = O(g(n))$.

In particular, the class $O(n)$ isn't closed under left polynomial composition.
Why are we interested in this definition? Here is an example. We can convert a $k$-tape Turing machine running in time $T(n)$ into a single-tape Turing machine running in time $5kT(n)$, see this question. If we start with a multi-tape Turing machine running in linear time, we don't necessarily end up with a single-tape Turing machine running in linear time. But if we start with a multi-tape Turing machine running in polynomial time, then we do end up with a single-tape Turing machine running in linear time. It thus makes sense that $O(n)$ isn't closed under left polynomial composition, but $n^{O(1)}$ is.


Priority in formal grammar From my recitation class, I have the following exercise:

  $\mathrm{EXP} = 0 \mid 1 \mid b \mathrm{EXP} \mid \mathrm{EXP} a \mid \mathrm{EXP} m \mathrm{EXP}$

  The above grammar is ambiguous.

  Make an unambiguous grammar which produce same language as the above.

  In the new grammar, $a$ has priority over $b$ and $b$ has priority over $m$.
  Also $m$ is associative.

Can you explain what the phrases

"has priority over" and
"$m$ is associative"

mean?

b0a has two subtly different productions (Note: I always expand the leftmost non-terminal):

EXP --> bEXP --> bEXPa --> b0a and
EXP --> EXPa --> bEXPa --> b0a,

so that's an example of an ambiguous string.

To give a priority over b means that if you have b0a it will always be parsed as b(0a)  (i.e. the first production I showed).

For the bit involving b and m, can you find two different productions for b0m0?

1m1m0 also has two subtly different productions:

EXP -> EXPmEXP --> 1mEXP --> 1mEXPmEXP --> 1m1mEXP --> 1m1m0 and
EXP -> EXPmEXP --> EXPmEXPmEXP --> 1mEXPmEXP --> 1m1mEXP --> 1m1m0.

To make m associative is to remove this ambiguity, so that only one of these parses is possible (from the question, it doesn't seem to matter which one exactly, as long as you choose one and stick to it!)


Proving that vertex labeling is NP-complete Given a graph $G=(V,E)$, all the vertices $v \epsilon V$ are labeled with values from $\{1,2,...\ldots n\}$ where $|V| = n$ such that for all edges $(x,y) \epsilon E$ such that $|label(x) - label(y)| \ge 2$. We have to determine whether such a labeling is possible for a graph.

Now I have to prove that doing so is a NP-complete problem. While showing that it belongs to NP is straightforward, I am unable to think of which NP-complete problem to be considered for reduction in polynomial time to this problem as part of the proof?

Given a graph $G$, consider its complement $G'$. The graph $G'$ is a yes instance of your problem if its vertices can be ordered so that adjacent vertices are not connected by an edge in $G'$. In other words, $G'$ is a yes instance of your problem if the vertices of $G$ can be ordered so that adjacent vertices are connected. So $G'$ is a yes instance of your problem if and only if $G$ has a Hamiltonian path.


Is there an NFA whose corresponding DFA has lesser number of states than the given NFA? (without unreachable states or epsilon moves) I'm stuck with another homework question - "Design an NFA with $n$ states such that the corresponding equivalent DFA constructed using the subset-construction method has less than $n$ states."

What I have learnt is that using subset (or powerset) construction, you can convert a given NFA with $n$ states to it's equivalent DFA with atmost $2^n$ states. I've tried constructing NFA's and tried converting them to check their equivalent DFA's number of states, with multiple attempts, but in vain.

DFA with less states than NFA

The above question tackles the possibility of a DFA having less than equivalent states to it's corresponding NFA. The question, as mentioned in some comments, doesn't take into account the fact that a DFA can have multiple equivalent NFAs, and also suggests the solution of having unreachable states to solve the problem.

Now, this does offer a solution to my homework problem, as the given problem doesn't specify that I shouldn't use unreachable states. Regarding epsilon moves, I believe my professor mentioned not to use them, if not said in the question, or indicated as an option to use, in the given question. Regardless, I can solve my problem by adding unreachable states. But that is not my question, here.

My question is, given an arbitrary NFA with $n$ states, to begin with. (without $\epsilon$ moves or unreachable states). Is there any specific case, where the  NFA (please provide an example) under said conditions is such that I can use subset construction and get a DFA with less than $n$ states?

Consider an automaton with $n$ states, all final, and a transition between every pair of states for every symbol.

There are two variants of the subset construction.  A "formal" one where always $2^n$ subsets are considered, and a "practical" one, where you consider only states that are reachable. Of course only the latter interpretation of subset construction will work.


Algorithm to find the correct word Imagine you are given a word samw and it is an invalid word (for the word same), and you need to find the correct word from the dictionary. The dictionary contains a list of words ordered by the frequency of the occurrence of the word with the most frequent word in the beginning.

There are the following rules on how to get the solution:

The wrong character should be adjacent to the correct character on the qwerty keyboard. In this case, w is adjacent to e.
You are given a method to get the list of adjacent characters of the keyboard

List<Character> getAdjacent(Character char)

You are also given method to find out if two characters are adjacent

boolean isAdjacent(Character a, Character b)

The wrong character can appear anywhere in the string and can be any number of characters also.
If there is more than one character matched for the wrong character, then return the string which is most frequent.

public String autoCorrect(String wrongWord, List<String> dictionary){

Question:  What is an efficient way to do this?

There are many strategies, and which is best will  likely depend on a number of details not listed in the question.

For short words, the most efficient solution is to precompute everything.  For each word in the dictionary, compute all possible words that can be obtained from it.  Store these in a giant hashtable.  If a word can be obtained in multiple ways, keep only the way with highest frequency.  Then, finding the correction for a new word is as simple as looking it up in the hashtable.

For long words, one approach would be to consider only the first K letters of the word (for some K) and ignore the remaining letters, and then use the precomputation method above.  The hash table will have to list all ways to complete the first K letters to a full word.  You would choose K to balance off the space needed for the hashtable and time needed for the precomputation, vs the time to correct a word.

Other strategies you could consider: (1) iterate through the dictionary in decreasing order of frequency, check whether it matches the input word; (2) generate all possible variants of the input word (by all possible combinations of replacing each letter by some adjacent letter or leaving it unchanged), look each up in the dictionary, and keep the highest-frequency match; (3) use locality-sensitive hashing to find all matches in the dictionary, and keep the highest-frequency one.  I suspect precomputation may be better than all of these in practice, though.


Why create more faster processors despite of Processor Memory Bottleneck? The shared bus between the program memory and data memory leads to the von Neumann bottleneck, the limited throughput (data transfer rate) between the central processing unit (CPU) and memory compared to the amount of memory. Because the single bus can only access one of the two classes of memory at a time, throughput is lower than the rate at which the CPU can work. This seriously limits the effective processing speed when the CPU is required to perform minimal processing on large amounts of data. The CPU is continually forced to wait for needed data to be transferred to or from memory. Since CPU speed and memory size have increased much faster than the throughput between them, the bottleneck has become more of a problem, a problem whose severity increases with every newer generation of CPU.

Source : https://en.m.wikipedia.org/wiki/Von_Neumann_architecture#Von_Neumann_bottleneck

There can be up to a 53% difference between the growth in speed of processor speeds and the lagging speed of main memory access.

So, if the processor-memory performance gap is so big then isn't creating more powerfull processors useless ?

Creating faster processors with more cores makes sense because more speed and more cores is not the only change.

Big changes are:

Bigger caches. Ryzen Threadripper has up to 288MB of cache. My iPhone has more than 16 MB of cache. Your processor can do an awful lot of work without ever touching RAM.
More memory bandwidth. Data transfer has gone from 32 bit to 64 bit to 128 bit to 256 bit transfers in parallel and not stopping there.
Improved streaming. The time needed to move consecutive data is very much improved, so the right algorithms can process data at massive speed.
Changed algorithms. If I know that memory access speed has become the bottleneck, then I can change algorithms that were optimal with a processor of ten years ago to be optimal on today's processors.


Would it be feasible to use a breadth first search algorithm for finding a solution to the 3x3x3 rubiks cube? I am trying to implement a rubiks cube solving program,and I am trying to figure out which algorithm to use,so far I have only come up with using breadth first search to find a shortest path from the initial configuration node to the solution node.
Each edge of the graph would be a 90 degree turn of a face of the rubiks cube(180 degree turns considered as 2 turns).
As for representing each configuration of the rubiks cube in a node I am thinking of using a 3x3x3 array of integers.Each element of the array would be an int from 1 to 6 representing each of the colours.
So if I used the Breadth First Search Algorithm for finding an optimal solution to the rubiks cube, would it run without taking up too much memory or too much time on an average computer?

For given Rubik's cube, the maximal number of moves required to solve any permutation of valid configuration is 26 in quarter-turn metric, but only 20 as half-turn metric, it means that if you have the most distant configuration amongst all possibilities the height of the tree is 20 levels, using BFS you have to store the previous level, using only quarter-turn metric the number is 26, but using unconstrained BFS the algorithm will terminate after 20 steps. It would also be nice to keep the path from current configuration to solved state if you wish to use it later. With majority of solutions at 18 moves as high as about $29*10^{18}$, the straightforward application of BFS is not really feasible for memory usage.

The worst case time required to solve puzzle from any configuration will traverse all solutions space, this is not feasible either. To put it in numbers, the empirical result to find the worst case number of moves took 35 cpu years, checking only solutions that require less than 20 moves, not aiming at the optimal state, reducing problem by symmetry and splitting to 55,882,296 sets that require checking shrinking actual number of states even further. These observations are not available using vanilla BFS. So the time usage is also not feasible.

As for the comments, using any algorithmic system of solving cube by human will not yield optimal solution, but will span at about 40 to 80 moves, but would be really straightforward to implement and both time and space would be negligible.

The Rubik's Pie (Domino) from the other answer is significantly easier, not only by removal of one layer, but some quarter turns are not possible to perform, but still it requires 18 moves in Half-turn metric and 19 in Quarter-turn metric, with solution space with only $406 425 600$ possible positions which is small when compared with $43 252 003 274 489 856 000$ ($10^{11}$ times smaller).


Is it possible to derive a string in this rewriting system? Rewriting system is a set of rules in the form of  $A \leftrightarrow B$.
If we apply that rule to a string $w$ we replace any substring $A$ in $w$ with a substring $B$ and vice versa.

Given a starting string $AAABB$ can we derive $BAAB$ in the system with the following rules:

$A \leftrightarrow BA$
$BABA \leftrightarrow AABB$
$AAA \leftrightarrow AB$
$BA \leftrightarrow AB$

Is there a general algorithm for that?

Notice that the parity of the number of $A$s does not change. Since one string contains an odd number $A$ and the other even, they are not reachable.

I believe in general (for an arbitrary set of rules, not your specific example), this is likely to be an undecidable problem. If the transforms are one way(i.e rules of the form $A \to BA$) it is so , for eg see: Tag System.


Why is simulation by non deterministic Turing machine faster than a deterministic one? A deterministic universal Turing machine $U_D$ can simulate a deterministic turing machine $M_D$ in $O(T(n)log(T(n)))$ where $M_D$ runs in $O(T(n))$. But I came across an exercise in Sanjeev Arora and Boaz Barak that a non-deterministic universal Turing machine $U_{ND}$ can simulate a non deterministic Turing machine $M_{ND}$ in $O(T(n))$ where $M_{ND}$ runs in $O(T(n))$.
The hint to the exercise is that $U_{ND}$ first non deterministically guesses tape contents of $M_{ND}$ and verifies then later. But how does this help as any branch of $U_{ND}$ can simulate a branch of $M_{ND}$ in $O(T(n)log(T(n)))$, similar to the deterministic case. Am I missing something ?

First of all, simulation of non-deterministic universal TM is better than simulation of deterministic universal TM only time-wise. But number of parallel executing threads is very high. In parallel algorithms parlance, $T(n)$ will be smaller but another metric $T(n)P(n)$ will be higher.

Deterministic UTM has extra $\log T(n)$ factor because it has to simulate multiple working tapes in a single working tape. If we use it as a simple multiple track tape, then to simulate a single step we will need to go to and forth for maximum $T(n)$ steps. We can improve this time by a clever trick. Instead of moving heads on the multiple tracks, we keep the head of the track(s) stationary and move the content of the tracks. We also keep a gradually increasing number of  interspersed blank spaces (another special blank space, instead of regular blank space) on both sides of head to do the shifting of tape content efficiently. By successfully executing this trick, each step can be simulated in amortized $O(\log T(n))$ steps.

We have to see how we can simulate non-deterministic UTM cleverly that does not require us to go to and fro, thus saving us $O(\log T(n))$ factor. Going to and fro in $k$ working tapes is the real bottleneck. We assume input and output tape are separate in both UTM and simulated TM, so they do not matter much.

Let us think how we can simulate a single work tape without going to and fro.
What we do, is whenever we need to go left, we do not go left, instead we guess what is in the left, maybe 0 or may be 1 (or maybe $B$ ot may be >, beginning of tape), and proceed to the right (non-deterministically of course, for both the cases), but we write what we guessed on a work tape. Since we are not moving left correctly, we cannot know tape symbols when we move right too. So whether we move left or right, we non-deterministically guess what is under the head, make note of our guess, and move on.

After the computation is over (by a series of $T(n)$ fake or  correct guesses and writings), for each thread of computation we have the content of guesses on a work tape, and we can check if the guesses and writings on the tape match in linear time $O(T(n))$ by actually going to and fro in yet another work tape. If we need our UTM not to exceed $T(n)$ execution time then we need to keep a counter for $T(n)$, some of the errant threads may go on executing for infinite time (there is a requirement on some non-deterministic TM models that every thread should stop after $T(n)$ time for acceptance, while in others only accepting threads need to stop after $T(n)$ time).

If we do this for all $k$ tapes together in a single tape, then too will be able to do this trick, but we will have to go to and fro $k$ times, one for each tape, to check if the guesses of each tape are consistent with what we are writing and what we are guessing later. This checking will take $O(kT(n))$ additional time overall for all tapes. So total running time of the non-deterministic UTM will be $O(CT(n)+kT(n))$.


Induction on typing derivation in refinement types system From the text Principles of Type Refinement page 14:

The author introduces in definition 2.2.7 the rule:

$$ \dfrac{\Pi \vdash t : R \qquad R \le S}{\Pi \vdash t : S} $$

and gives the following contravariant form:

$$ \dfrac{\Omega \le \Pi \qquad \Pi: t : R}{\Omega \vdash t:R} $$

where $\Omega,\Pi \sqsubset \Gamma$ and $\Omega \le \Pi$ is interpreted as if the type assigned to each variable in $\Omega$ is a subtype of the type assigned to the same varaible in $\Pi$.

The author then states that this rule is admissible in the refined simply typed lambda calculus and that this can by shown by induction on typing derivations.

I'm used to natural and structural induction. But what does it mean to perform induction on typing derivations? Can you given an example?

It's a form of structural induction.

As we see on page 12 of the text, the typing relation is defined inductively by four rules.

For example, the rule abs says that given a deduction $\Gamma, x:r \vdash t : S$ we can form the new deduction $\Gamma \vdash \lambda x.t : R \to S$.

Compare with how, given a natural number $n$ you can form a new natural number $n+1$.

To prove a proposition $P(n)$ about an arbitrary natural number by induction you note that $n$ is either

$0$, or
$m+1$ for some $m$

In the first case, you prove $P(0)$ directly. In the second, you assume you have a proof of $P(m)$ and use this to prove $P(m+1)$.

Similarly, to prove a proposition about an arbitrary derivation $\Delta$ of the type judgement $\Pi \vdash t :R$ you note that $\Delta$ is either

$ \dfrac{}{\Pi \vdash x : R}\textsf{ var}$ and $t=x$ a variable
$\dfrac{\Pi \vdash s : S \to R, \Pi \vdash u : S }{\Pi \vdash s(u) : R}\textsf{ app}$ and $t=s(u)$, an application, for some derivations $\Delta_1, \Delta_2$ of the type judgements $\Pi \vdash s : S \to R, \Pi \vdash u : S $
$\dfrac{\Pi, x:r \vdash s : S}{\Pi \vdash \lambda x.s : R \to S}\textsf{ abs}$ and $t=\lambda x.s$, an abstraction, for some derivation $\Delta_1$ of the type judgement $\Pi \vdash s : S$
$\dfrac{\Pi \vdash t:S, R \leq R}{\Pi \vdash t : R}\textsf{ sub}$, for some supertype $S$ of $R$ and a derivation $\Delta_1$ of $\Pi \vdash t : S$

In the first case, you prove $P(\Delta)$ directly, and in the other three you assume $P(\Delta_1)$ and $P(\Delta_2)$ and then prove $P(\Delta)$.

There is an example in the proof of lemma 2.3.10 of the text, page 33.


Covering grid with constrained rectangles I need to place N rects on a 2-dimensional grid with constraints.

For the each rect height/width and placing limitations($x_{min}$-$x_{max}$) are known.

The problem is to place all rects on a grid with no intersections that every rect's bottom left $x$ is in rect's $x_{min}$-$x_{max}$.

I've implemented the naive solution where I just iterating over rects and incrementing $x$ by some fixed step while checking for intersections. If no place found then I increment $y$ and iterate again.

The question: I'm sure that there are algorithms/data structures that will help me to solve this task faster, but I do not know where to start.

I suggest you use a constraint solver, like Minion.  The following paper shows that they are effective for a related problem:

Almost Square Packing, Helmut Simonis and Barry O’Sullivan.

My thanks to András Salamon for pointing to this information.

You could also try using a SAT solver.


minimum subset of dominating 2D points From an initial set $S$ of 2D points, how to efficiently compute a minimum(-size) dominating subset $M$ ?

$M$ is a dominating subset of $S$ if for any $(x,y)$ in $S$ there is at least one point (a,b) in M such that $x \le a$ and $y \le b$

Another related question: is any minimal set also minimum?

It is trivial to find a minimal set in $|S|^2$ time complexity.

$O(N^2)$ solution

First of all define dominant relation for points:

  Point $d(x_d, y_d)$ is dominating point $p(x_p, y_p)$ iff $x_p \le x_d$ and $y_p \le y_d$. Also easy to see that this relation is transitive, i.e. if $a$ dominating $b$ and $b$ dominating $c$, then $a$ dominating $c$.

Let $M$ be minimum(-size) dominating subset of set $S$. Now we need to check which point will be in $M$. Let answer on the question:

  Is $p \in S$ is $M$ or not?

We have 2 cases:

$\nexists d \in S, d$ is dominanting $p$, then $p \in M$, if we will not include $p$ in $M$ we will not be able to find a point that will dominate $p$.
$\exists d \in S, d$ is dominanting $p$, then $p \notin M$, because it will be more optimal include $d$ in $M$ and exclude $p$, as every point in $A$ that is dominated by $p$ is dominated by $d$ also, but $d$ is dominating at least one more point (itself).

First case make sure that $M$ will dominate $S$, second case that $M$ is minimal among all dominating subsets.

And now we have easy $O(N^2)$ solution: for each point $p \in S$ check membership in $M$; to do that we need to check that there is no point $d \in S$ that dominating $p$.

$O(N \log N)$ solution

To construct solution with $O(N \log N)$ time-complexity, let see some example of sets $S = \{A, B, C,..., N\}$ and $M = \{N, B, I, H\}$:

To find $M$ we need to sort points in $S$ by $x$ in descending order, and if $x's$ the same by $y$ in descending order (it can be done in $O(N \log N)$, let call this sorted list $L$.

Include first point from $L$ in $M$ and remember this point as $T$.
Iterates through $L$ (let $C$ current considered point from $L$):

if $C$ is dominated by $T$ than skip $C$ and go to next point in $L$;
else include $C$ in $M$ and set $T = C$
This step can be performed in $O(N)$.


Lempel-Zilv-Welch Algorithm Decoding Question Hello i am studying about LZW algorithm by watching this video:
https://www.youtube.com/watch?v=j2HSd3HCpDs&t=481s

I couldnt fully understand decoding process.
At current 258,how does 116 come at add to dictionary part ?
At current 256,how does 101 come at add to dictionary part ?

Let us look at the very first line. There is a 104 at the end of the line. Where does that 104 come from? It is the first number of the number(s) that are represented by 104 in the next column. Since 104 is in the 0-255 range, 104 just represents itself.

The same procedure happens on the line at the end of which you see a 106. Where does that 106 come from? That 106 is the first number of the number(s) that are represented by 256 in the next column. How? Since 256 is outside of 0-255 range, we have to consult the dictionary we have built. As given by the last column of the first line, 256 represents for two numbers, 116 104, of which 106 is the first one.

I will let you figure out why the above procedure is correct, where 101 on the last line come from and why the numbers in the output column are correct.

By the way, it should be helpful if you can also take a look at the encoding procedure at the nearby lines when you try to understand the decoding procedure.


P/NP - Polynomial Reduction vs Certificate I am learning about the P/NP problem right now, and I don't understand when to use polynomial reduction and when to use a certificate.

How I understand polynomial reduction is that you can use it to show that:

Problem A is in P if:

B is in P and you can reduce A to B in polynomial time -> A $\leq_p$ B

Problem A is in NP if:

B is in NP and you can reduce B to A in polynomial time -> B $\leq_p$ A

Then I read about certificates and this is how I understand the basic Idea/Components behind it:

Problem: Problem to solve
Certificate: possible solution
Certifier: Checks if the Certificate is correct

What I don't understand is:

What do you want to show with solution that uses a certificate?
When do you use one over the other ?

Problem A is in NP if:
  B is in NP and you can reduce B to A in polynomial time -> B $\leq_p$ A

Not quite right. The class P is a subset of NP anyway, and hence A is already NP if it is in P. The question is whether A is in P or not.

By reducing B to A in polynomial time, you prove that any polynomial solution of A is a polynomial solution of B. Assuming B is in NP gives no useful information about A, since it is possible that B is in P as well (remember that P $\subseteq$ NP). However, assuming (and probably that is what you meant), that B is NP-Hard, then, by reducing B to A, we prove that A is also hard for NP class, and hence unless P=NP, the problem A is not in P.

Now back to the question. What we know so far, P $\subseteq$ NP. There are more classes above NP like EXP and under P like L for example. Which means,
$$L \subseteq P \subseteq \mathit{NP} \subseteq \mathit{EXP}.$$
Check the link for more information about the classes. However, one characterization of problems in NP, is that they all admit a certifier, that can in polynomial time in the size of the input, say if the given instance is a yes instance. For example, for travelling salesman, which is an NP-Complete problem, the certificate is a path. You can clearly certify it, by checking if it visits all cities and each city exactly once and return to the beginning. Since P $\subseteq$ NP the same works for P problems. Like shortest path. given a shortest path between two vertices, you can certify it it is a shortest path. For example, the certifier can compute a shortest path in polynomial time and compare the lengths.

Now the interesting part about certificates, is to certify if a problem admits a certificate for the negative answer. That means, given an instance and a certificate, the certifier can tell in polynomial time, if the instance is not in the language. Problems that admits such a certifier belong to the class co-NP. It is believed that NP $\neq$ co-NP unless P = NP. The class P belongs to the intersection of both classes and hence we can certify both negative and positive answers in polynomial time.

Summary

Reducing $A$ to a polynomial problem proves that it is solvable in polynomial time.
Reducing an NP-Hard problem to $A$, proves that $A$ is NP-Hard and probably not in P. In this case, even if the problem is in NP and hence is NP-complete, we can only say about $A$ that it is NP-hard, we still do not not if it is in NP.
A problem is in NP if there is for each instance that belongs to language of the problem, a certificate, that can be certified in polynomial time in the size of the instance.
A problem is in co-NP if there is for each instance, that odes not belong to the language of the problem, a certificate, that can be certified in polynomial time in the size of the instance.
The class P belongs to the intersection of P $\cap$ co-NP.


Thought process to solve tree based Dynamic Programming problems I am having a very hard time understanding tree based DP problems. I am fairly comfortable with array based DP problems but I cannot come up with the correct thought process for tree based problems and I was hoping somebody could please explain their thought process.

I will talk about my thought process behind array based problems and then explain my troubles with tree based DP problems.

My thought process for array problems

The way I think about DP in array based problems is as follows. Let us consider a problem like Minimum Path Sum. Here the objective is to get from the top left to bottom right positions in a matrix such that we minimize the cost of the path. We can only move left and right.

The way I would approach problems like this is as follows:

First I would construct a recurrence. In this case the recurrence is as follows

The recurrence is:

f(i, j) = a[i][j] // if i == m and j == n
f(i, j) = a[i][j] + f(i, j+1) // if i == m
f(i, j) = a[i][j] + f(i+1, j) // if j == n
f(i, j) = a[i][j] + Math.min( f(i, j+1), f(i+1, j) ) // Otherwise

Next I look at the equations which tells me the problem can be solved using DP as there are overlapping subproblems in f(i+1, j) and f(i, j+1). There is also an optimal substructure.
I can also tell the time/space complexity just by looking at the recurrence.

Because we must compute all states which is all (i,j) pairs and because time per state is O(1) (adding a[i][j] to result) the time complexity is O(n^2).
Looking at the recurrence, i depends only on i+1 and not on i+2, i+3 ... similarly j depends only on j+1 and not on j+2, j+3... so we can get away with using only 1 extra row (either i+1 or j+1) instead of the entire matrix so space complexity is O(n).

Hence I would come up with a n^2 time and n space solution. I can do this without any problems.

My thought process for tree problems

However I am having a hard time applying the same thought process to tree based DP problems. As an example let us consider the problem Diameter of Binary Tree where the objective is to find the longest path between any 2 nodes in the tree.

I can come up with a recurrence for this problem which is as follows:

f(n) = 0 // if n == null
f(n) = max( 1+height(n.left) + height(n.right),         // longest path passing through root
            f(n.left),                                  // longest path in left subtree
            f(n.right) )                                // longest path in right subtree

Because f(n.left) for example is computed by doing 1+height(n.left.left) + height(n.left.right) I can tell that DP must be used.

So my approach would be to create a cache of size 'n' that stores all the heights of the nodes. So the space complexity would be O(n).

However the optimal solution of this problem has a space complexity of O(1) and I am having a hard time figuring that out just by looking at the recurrence. How does the recurrence tell you that space complexity can be reduced and that O(1) space is enough and O(n) is not needed? How do you know what value(s) to store in this case? In array based problems I can get the answers to both these questions just by looking at the recurrence but for tree based dp it is not so obvious to me.

My questions:

What can you tell about this problem just by looking at the recurrence for the tree problem? Putting aside my own thought process, if I gave you this recurrence and nothing else what conclusions would you reach and how would you write the program? I am curious about your thought process.
For array based problems I can tell just by looking at the recurrence both how much space I needed to solve the problem AND what exactly I needed to store (I need to store values of row i+1 in min path sum and nothing else). How can I do the same for the tree problem?

Thanks.

I don't know if this helps, but I also struggled a great deal with DP problems on trees, and what helped for me was considering some simpler problems first, and really do a bunch of exercises of this type.  It also really helps to program them in (e.g.) Python so that you get some hands-on experience.

So, perhaps it is better to start with a simpler tree problem first, like (weighted) Vertex Cover or (weighted) Independent Set?

In both these cases (they are similar, but let us focus on Vertex Cover), the
entire solution of a subtree can be summarized in the root of the subtree with
two numbers: the optimal solution if the root of the subtree is in the vertex
cover, and the optimal solution if the root of the subtree is not in the
vertex cover (but covered from below).

So the plan is to store, for each node $u$, two numbers, $u_{\text{in}} = c_i$
and $u_{\text{in}} = c_o$, and in the end, we will look at what are the values
in the root node $r$, i.e. $r_{\text{in}}$ and $r_{\text{out}}$.

The Algorithm

The algorithm is then quite simple.  For the base case, starting at the leaves, in leaf node $v$, you store $v_{\text{in}} = w(v)$ and $v_{\text{out}} = 0$.  Clearly, in the subtree with only one node, there are no edges to cover, so this is quite easy.

Then the rest of the algorithm is given a node $v$ with children $u_1, \dots, u_d$, we need to compute two cases.

$v$ is in the vertex cover: then the optimal solution is $v_{\text{in}} = w(v) + \sum_{u \in u_1 \dots u_d} \min(u_{\text{in}}, u_{\text{out}})$
$v$ is not in the vertex cover, so all children must be, hence $v_{\text{out}} = \sum_{u \in u_1 \dots u_d} u_{\text{in}}$

Now, the only thing we need to do is return the result of the root node $r$, which can either be in or not in the vertex cover, so we return
$$ \min( r_{\text{in}}, r_{\text{out}}) $$

In other words, we found out what information we need in the "separator" of a
subtree, and how can combine the information from the subtree with the rest of
the tree.

Exercise: Solve Weighted Vertex Cover and Weighted Independent Set on trees.
Exercise 2: Solve Weighted Dominating Set, which needs one more state, namely in the dominating set, not in the dominating set but dominated, not yet dominated (dominated from above).


Is vwwx regular language? I think I understand pumping lemma for regular and context free languages, but there is this one, which I have no idea if it is regular or context free or not context free.

$L = \{vwwx : v,w,x \in \{0,1\}^* \wedge w\neq \epsilon\}$ - I think it may be regular, because I think that this is language, which accepts set of all words with $00,11,0101,1010$ substrings. I am sure that $\{vww^Rx : v,ww,x \in \{0,1\}^* \wedge w\neq \epsilon\}$ is regular here is proof, because it is set of all strings, with $00$ or $11$ as substring, but without reversing $w$ I am not so sure. I do not understand if idea of "expanding" $v$ and $x$ in $vww^Rx$ as shown in proof (reducing language to language which accepts set of all string with $00$ or $11$ as substring) also applies to $vwwx$. What do you think ?

I would be glad if you could help me with this one.

Let's try to figure out which words are in $L$ and which aren't. If a word $w$ contains 00 or 11 then it is certainly in $L$. Otherwise, it alternates between zeroes and ones. If it contains 0101 or 1010 then it is in $L$. We are left with the words of length at most three, that is $\epsilon,1,0,10,01,101,010$. These are the only words not in $L$. Since $L$ is cofinite, it is regular.


Can quantum computers be modelled as a classical computer with access to an oracle? Quantum computers can solve certain problems faster than classical computers e.g factoring numbers.
and this is because quantum computers can do a fourier transform on $n$ bits in $O(n^2)$ time as opposed to $O(n2^n)$ time.
We can usually reduce time complexities by pretending that we can do some thing faster - introducing oracle's that can solve a problem instantly.
Is there an oracle that encoded all the quantum speed ups we get?

Technically, the main differences between classical and quantum algorithms are super-position and entanglement that make the concept of oracle in quantum algorithms. As these two are only meaningful in quantum mechanics, you can't have that oracle with the same cost as the quantum algorithms, in classical algorithms.


What values do $y_i$ in training data for binary classification problems attain? In case of binary classification problem, what are the $y_i$ 's in the training data set $\{(x_1, y_1), (x_2, y_2), \dots (x_n, y_n)\}$?

I guess they are from $\{1,-1\}$. Now I see a method for finding a scoring function $f(x) = w^Tx + b$ by minimizing the squared error between the $f(x_i)$'s and $y_i$'s over $w$ and $b$. Now is it correct to minimize the error between $f(x_i)$'s and $y_i$? The latter is a sign while the former is a value? They seem incomparable to me.

If your prediction is $f(x) = \text{sign}(w^T x + b)$ then the 0-1 loss will simply be
$$
L_{\text{0-1}}(w) = \sum_{i=1}^n \mathbb{I}\{y_i \neq f(x_i)\},
$$
where $\mathbb{I}$ is the indicator function, i.e., $\mathbb{I}\{a\} = 1$ if $a$ is true and $0$ otherwise. If you were to minimize this directly using subgradient descent you would get the perceptron algorithm. A more common approach is to upperbound the 0-1 loss with some other function, like the hinge loss, log loss, squared loss, etc and minimize that.


Time complexity formula of nested loops I've just begun this stage 2 Compsci paper on algorithms, and stuff like this is not my strong point. I've come across this in my lecture slides.

int length = input.length();
for (int i = 0; i < length - 1; i++) {
    for (int j = i + 1; j < length; j++) {
        System.out.println(input.substring(i,j));
    }
}

"In each iteration, the outer loop executes $\frac{n^{2}-(2i-1)n-i+i^{2}}{2}$ operations from the inner loop for $i = 0, \ldots, n-1$."

Can someone please explain this to me step by step?

I believe the formula above was obtained by using Gauss' formula for adding numbers... I think...

Your intuition is correct, the work is in identifying the things you're adding together.

The first bit is that printing a string of length $m$ takes $m$ operations, so the

System.out.println(input.substring(i,j));

line takes $j-i$ operations. (A side note here is that this code is in Java, unless I'm very much mistaken, and the substring(start, end) method gives the substring beginning at index start and ending at end-1)

So then at each iteration of the outer loop, we're printing a bunch of substrings, starting with a string of length one (just the character at index $i$) and ending with the substring that starts at $i$ and goes to the end of the string input.

To put that a dash more mathematically we're printing strings of length $1, 2, \ldots, n-i$. As the number of operations  required to print a string is the same as its length, we're doing $\sum_{k=1}^{n-i}k$ operations. Substituting Gauss's formula for this sum, we get that the number of operations is equal to:
$$
\frac{(n-i)(n-i+1)}{2}
$$

Then multiplying everything out gives the formula you have in your slides.


Error bound for minimum-degree spanning tree I am reading The Design of Approximation Algorithms (Williamson and Schmoys; page 50 of this PDF) about solving the minimum-degree spanning tree problem of maximum degree 2 in polynomial time. The text states that we are going to find a tree $T$ with maximum degree at most $2\mathrm{OPT} +\lceil\log_{2} n\rceil$ in polynomial-time. $n$ is the number of the vertices in the graph.  Could someone clarify why $\log_{2} n$ is placed there? The text gives no explanation what it is.

It is $\sf NP$-complete to decide if a given a graph has a minimum-degree spanning tree of maximum degree 2. Because the problem is hard, we would like to compute an approximate solution (to the optimization problem).

What they do is that they show how to find a tree $T$ with $\Delta(T)$ being at most $2\text{OPT} + \log_2 n$. The intuition is that the local search tries to make local improvements to a candidate tree, and when it can't make any improvements, it has found a locally optimal tree. It can then be shown that for any locally optimal tree, the maximum degree is at most $2\text{OPT}+\log_2n$, where $n$ is the number of vertices. The explanation for the logarithmic term is given in Theorem 2.19; it results from a tight analysis.

The best we can hope to do assuming $\sf P \neq NP$ is to find a tree $T$ with $\Delta(T)$ being at most $\text{OPT}+1$. This in fact possible to do, and is shown in a later section of the book.


CCS process for a drink dispenser with two different prices A drink dispenser requires the user to insert a coin ($\bar c$), then press one of three buttons: $\bar d_{\text{tea}}$ requests a cup of tea $e_{\text{tea}}$, ditto for coffee, and $\bar r$ requests a refund (i.e. the machine gives back the coin: $\bar b$). This dispenser can be modeled by the following CCS process:

$$ M \stackrel{\mathrm{def}}= c.(d_{\text{tea}}.\bar e_{\text{tea}}.M + d_{\text{coffee}}.\bar e_{\text{coffee}}.M + r.\bar b.M)$$

A civil war raises the price of coffee to two coins, while the price of tea remains one coin. We want a modified machine that delivers coffee only after two coins, and acquiesces to a refund after either one or two coins. How can we model the modified machine with a CCS process?

You can easily profit from warfare that way:

$$ M \stackrel{\mathrm{def}} =
  c.(
    d_{\text{tea}}.\bar e_{\text{tea}}.M
    + r.\bar b.M
    + c.(
      d_{\text{coffee}}.\bar e_{\text{coffee}}.M
      + r.\bar b.\bar b.M
    )
  )
$$

note that you have to press refund to get a tea if you put too many coins. If you don't want that, you can adapt it (or maybe set up a (finite is enough) counter) :

$$ M \stackrel{\mathrm{def}} =
  c.(
    d_{\text{tea}}.\bar e_{\text{tea}}.M
    + r.\bar b.M
    + c.(
      d_{\text{coffee}}.\bar e_{\text{coffee}}.M
      + d_{\text{tea}}.\bar b.\bar e_{\text{tea}}.M
      + r.\bar b.\bar b.M
    )
  )
$$


Algorithm to efficiently determine whether a magazine contains all the letters in a search string Title pretty much states the question, I was looking for some assistance with the following:

You are given a search string and a magazine. You seek to generate all the characters in a search string by cutting them out form the magazine. Give an algorithm to efficiently determine whether a magazine contains all the letters in a search string.

I wrote: "Create a count sort which just buckets every occurrence of each specific letter in the magazine down the line. Then use that to compare vs. the search string. If the magazine contains all the letters in the search string, then great you're done; otherwise you need a new magazine."

I feel like that's not enough of an answer for this problem, can someone help?
Thanks!

If this was a real life problem, and the search string contained n letters, while the magazine contained m letters, then this would take O (n + m) in time. Typically you would assume that n is very small compared to m, so this solution would take a lot more time than needed.

I'd create a counted set of the letter in the search string. If that counted set is empty (because the search string was empty) I'm done. Then iterate through the letters in the magazine; if a letter is in the counted set then remove it and I'm done if the set became empty. Otherwise, if the iteration finishes then I have a counted set of all letters that cannot be provided by the search string.

This will usually end quite quickly, long before all the letters in the magazine are examined.


What data structure to use for large scale DHCP server What data structure would one use to keep a large number of IP addresses (v4 and v6, but not at the same time if that makes a difference), and I'm talking about millions, preferably hundreds of millions at a time for fast look-up.
The preference would be for fast look-up. Initial filling of the data structure is not too big of a concern. To have a small memory footprint is not also a big concern, but it would be nice to have that part as small as possible.
I was thinking in lines of using some sort of binary tree, but don't know if hash map would suffice...
Thanks in advance!

A good data structure for IPv4 translation is a 256-way trie, this means any lookup always requires exactly 4 memory accesses, and shared prefixes will be hot in cache.
You can do the same for IPv6 but implementing a unique suffix check (instead of always expanding trie nodes) is probably worth it.


Spanning tree in a graph of intersecting sets Consider $n$ sets, $X_i$, each having $n$ elements or fewer, drawn among a set of at most $m \gt n$ elements. In other words
$$\forall i \in [1 \ldots n],~|X_i| \le n~\wedge~\left|\bigcup_{i=1}^n X_i\right| \le m$$
Consider the complete graph $G$ formed by taking every $X_i$ as a node, and weighing every edge $(i,j)$ by the cardinal of the symmetric difference $X_i \triangle X_j$.
An immediate bound on the weight of the minimal spanning tree is $\mathcal{O}(n^2)$, since each edge is at most $2 n$, but can we refine this to $\mathcal{O}(m)$?
For illustration, consider $2 p$ sets, $p$ of which contain the integers between $1$ and $p$ and $p$ of which contain the integers of between $p+1$ and $2p$. A minimal spanning tree has weight $p$ but a poorly chose tree on this graph would have weight $(p-1)p$. Intuitively, if there are only $m$ values to chose from, the sets can't all be that different from one another.
EDIT:
Contributor Dmitry gives a nice counterexample below in which $m$ is nearly but not quite $n^2$.
A counterexample or proof would still be of interest in the case where $m = \mathcal{O}(k n)$. Can the weight of spanning-tree be bound by $\mathcal{O}(f(k) n)$? By $\mathcal{O}(f(k) n \log^c n)$?

Interesting question.
The right intuition should probably be along the guideline that two random subsets of cardinality $n$ drawn from some $cn$ elements for some constant $c$ differ from each other significantly with a probability very close to 1 and, hence, the weight of the minimum spanning tree of the graph $G$ should be $\mathcal\Theta(n^2)$ on average. I cannot prove that guideline is correct, however.
Instead, I will present one series of such examples. More specifically, from some $n$ (that can be arbitrary large), there are $n$ sets, each having $(n-1)/2$ elements drawn from a set of $n$ elements, such that the cardinality of the symmetric difference between any two sets is no less than $(n-1)/2$. So the weight of the minimum spanning tree is no less than $(n-1)^2/2=\mathcal\Theta(n^2)$.

Here is the construction, using quadratic residue.
Example. Let $n=p$ be an odd prime. Let $X_0$ be the set of all non-zero quadratic residues of $p$ between 0 and $p-1$ inclusive. In other words, $$X_0=\{0\le k\lt p: \left(\frac {k}p\right)=1\}$$ where $\left(\frac{\cdot}p\right)$ is the Legendre symbol. For $0\le i\lt p$, let $X_i$ be "$X_0$ plus $i$", i.e., $$X_i=\{0\le k\lt p: \left(\frac {k-i}p\right)=1\}.$$ Then $|X_i|=\frac{p-1}2$ for all $i$ and $|X_i \triangle X_j|\ge \frac{p-1}2$ for all $i\not=j$.
Proof: Since $\left(\frac{\cdot}p\right)$ is either $-1$, $0$, or $1$, we have $1+\left(\frac{\cdot}p\right)\ge0$. Hence,
$$\begin{aligned}
&\quad\quad \sum_{0\le k\lt p}\left(1+\left(\frac {k-i}p\right)\right)\left(1+\left(\frac {k-j}p\right)\right)\\
&\ge\sum_{0\le k\lt p\,\land\,\left(\frac {k-i}p\right)=1\,\land\, \left(\frac {k-j}p\right)=1}\left(1+\left(\frac {k-i}p\right)\right)\left(1+\left(\frac {k-j}p\right)\right)\\
&=\sum_{0\le k\lt p\,\land\,\left(\frac {k-i}p\right)=1\,\land\, \left(\frac {k-j}p\right)=1}4\\
&=4\,|X_i\cap X_j|
\end{aligned}$$
On the other hand, we have
$$\begin{aligned}
&\quad\quad \sum_{0\le k\lt p}\left(1+\left(\frac {k-i}p\right)\right)\left(1+\left(\frac {k-j}p\right)\right)\\
&=\sum_{0\le k\lt p}\left(1 + \left(\frac {k-i}p\right) + \left(\frac {k-j}p\right)+ \left(\frac {k-i}p\right)\left(\frac {k-j}p\right)\right)\\
&=p + 0 + 0 + \sum_{0\le k\lt p} \frac {k^2-(i+j)k+ij}p\\
&=p-1
\end{aligned}$$
Since $p\nmid(-(i+j))^2-4ij=(i-j)^2$, the last equality above comes from the case of $p\nmid b^2-4ac$, theorem 1 in the paper On Certain Sums with Quadratic Expressions Involving the Legendre Symbol. So we have $|X_i\cap X_j|\le \frac{p-1}4.$
Since $|X_i|=|X_j|=\frac{p-1}2$, $\ |X_i \triangle X_j|=|X_i|+|X_j|-2|X_i\cap X_j|\ge \frac{p-1}2.$ $\quad\checkmark$

For people who appreciate concrete examples, here are the sets when $n=17$, where $|X_i \triangle X_j|\ge 8$.
$$\begin{aligned}
X_{0}&=\{\phantom{1}1, \phantom{1}2, \phantom{1}4, \phantom{1}8, \phantom{1}9, 13, 15, 16 \}\\
X_{1}&=\{\phantom{1}2, \phantom{1}3, \phantom{1}5, \phantom{1}9, 10, 14, 16, \phantom{1}0 \}\\
X_{2}&=\{\phantom{1}3, \phantom{1}4, \phantom{1}6, 10, 11, 15, \phantom{1}0, \phantom{1}1 \}\\
X_{3}&=\{\phantom{1}4, \phantom{1}5, \phantom{1}7, 11, 12, 16, \phantom{1}1, \phantom{1}2 \}\\
X_{4}&=\{\phantom{1}5, \phantom{1}6, \phantom{1}8, 12, 13, \phantom{1}0, \phantom{1}2, \phantom{1}3 \}\\
X_{5}&=\{\phantom{1}6, \phantom{1}7, \phantom{1}9, 13, 14, \phantom{1}1, \phantom{1}3, \phantom{1}4 \}\\
X_{6}&=\{\phantom{1}7, \phantom{1}8, 10, 14, 15, \phantom{1}2, \phantom{1}4, \phantom{1}5 \}\\
X_{7}&=\{\phantom{1}8, \phantom{1}9, 11, 15, 16, \phantom{1}3, \phantom{1}5, \phantom{1}6 \}\\
X_{8}&=\{\phantom{1}9, 10, 12, 16, \phantom{1}0, \phantom{1}4, \phantom{1}6, \phantom{1}7 \}\\
X_{9}&=\{10, 11, 13, \phantom{1}0, \phantom{1}1, \phantom{1}5, \phantom{1}7, \phantom{1}8 \}\\
X_{10}&=\{11, 12, 14, \phantom{1}1, \phantom{1}2, \phantom{1}6, \phantom{1}8, \phantom{1}9 \}\\
X_{11}&=\{12, 13, 15, \phantom{1}2, \phantom{1}3, \phantom{1}7, \phantom{1}9, 10 \}\\
X_{12}&=\{13, 14, 16, \phantom{1}3, \phantom{1}4, \phantom{1}8, 10, 11 \}\\
X_{13}&=\{14, 15, \phantom{1}0, \phantom{1}4, \phantom{1}5, \phantom{1}9, 11, 12 \}\\
X_{14}&=\{15, 16, \phantom{1}1, \phantom{1}5, \phantom{1}6, 10, 12, 13 \}\\
X_{15}&=\{16, \phantom{1}0, \phantom{1}2, \phantom{1}6, \phantom{1}7, 11, 13, 14 \}\\
X_{16}&=\{\phantom{1}0, \phantom{1}1, \phantom{1}3, \phantom{1}7, \phantom{1}8, 12, 14, 15 \}\\
\end{aligned}$$


Can a list with $\mathcal{O}(1)$ access have an insertion complexity better than $\mathcal{O}(n)$? It seems intuitive that there's no list data structure which has $\mathcal{O}(1)$  worst case time complexity for random access and a worst case complexity better than $\mathcal{O}(n)$ for insertion: if insertion is allowed to affect only a small part of the list, then there's no way for it to always keep the entire list in a structure that allows for constant time element access.

Is there any proof (or counterexample) of this?

Yes, you can have both as fast as possible random access and faster-than-full-rebuild insertion time.

I assume you know how dynamically growing arrays work. Also, I assume you know how to make them work in $O(1)$ worst-case. These techniques allow us to focus on the problem for lists of limited size only.

Let $n$ be the maximal size (capacity) of the list. Let’s divide the list into $O(\sqrt{n})$ blocks of equal size $B$ (which is $O(\sqrt{n})$ too). Let also $b_j$ denote a cyclic shift of the $j$-th block.

When you need to access $i$-th element of the list, you calculate its position as follows in $O(1)$:

$$f(i) = (b_j + i \mod B) + B \times j$$

where $j = \lfloor \frac{i}{B} \rfloor$.

When you need to insert something into $i$-th position, you first make a cyclic shift of everything from $j$-th block to the end:

Decrement all $b$ values starting from $j$.
Swap the elements on the boundaries of consequtive blocks, so that every element is in its right place.
Then you fix $j$-th block by rebuilding it from scratch.

This gives you $O(\sqrt{n})$ insertion complexity.


Dependent Type Theory Implementation of a Graph In Haskell you find graphs defined like this:

data Graph a = GNode a (Graph a)

Or this:

data Graph a = Empty | Vertex a | Overlay (Graph a) (Graph a) | Connect (Graph a) (Graph a)

class Graph g where
  type Vertex g
  empty   :: g
  vertex  :: Vertex g -> g
  overlay :: g -> g -> g
  connect :: g -> g -> g

Or this:

type Graph = Table [Vertex]
type Table a = Array Vertex a
type Bounds = (Vertex, Vertex)
type Edge = (Vertex, Vertex)
type Vertex = Int

I am wondering why it is not implemented more like this (this is JavaScript):

class Graph {
  constructor() {
    this.nodes = []
    this.edges = []
  }
}

Or perhaps in Haskell-ish:

data Graph = Graph
  { nodes :: [Node]
  , edges :: [Edge]
  }

For example, in this Graph in Coq, it looks more like the JavaScript version (though I don't understand the Structure in Coq):

Structure Graph := {
  V :> nat ; (* The number of vertices. So the vertices are numbers 0, 1, ..., V-1. *)
  E :> nat -> nat -> Prop ; (* The edge relation *)
  E_decidable : forall x y : nat, ({E x y} + {~ E x y}) ;
  E_irreflexive : all x : V, ~ E x x ;
  E_symmetric : all x : V, all y : V, (E x y -> E y x)
}.

Finally, here seems to be a complete Coq graph definition:

Inductive Graph : V_set -> A_set -> Set :=
  | G_empty : Graph V_empty A_empty
  | G_vertex :
      forall (v : V_set) (a : A_set) (d : Graph v a) (x : Vertex),
      ~ v x -> Graph (V_union (V_single x) v) a
  | G_edge :
      forall (v : V_set) (a : A_set) (d : Graph v a) (x y : Vertex),
      v x ->
      v y ->
      x <> y ->
      ~ a (A_ends x y) -> ~ a (A_ends y x) -> Graph v (A_union (E_set x y) a)
  | G_eq :
      forall (v v' : V_set) (a a' : A_set),
      v = v' -> a = a' -> Graph v a -> Graph v' a'.

My question is, what a proper definition of a graph is in Dependent Type Theory in formal type theory notation. Mathematically $G = (V, E)$, but in Coq and Haskell, things are a lot more functional/recursive. It seems weird that Haskell is defining it sometimes as a recursive structure. Wondering how to model this using the abstract type theory notation (using dependent types) and recursion if necessary, to get a better sense of realistic data structures in dependent type theory, and how to parse the formal notation. The types of graphs I am thinking about are directed, cyclic, and finite, non-hypergraphs.

So, there are two different things you are talking about.

The definition of a graph
The encoding of a graph

A Graph is always defined as a set of vertices and edges. This tells us what vertices are in the graph, and for any pair of vertices, whether there is an edge between them.

However, this definition is purely mathematical. A set isn't a "thing" that you can store in memory. So we need an encoding of a graph, so that the abstract mathematical set operations can be mapped onto concrete algorithmic operations.

Once you're talking about encoding, there are many different ways to implement a graph, all of which will give you something that is (in a sense) equivalent to the mathematical definition. But, there are practical trade-offs with different encodings:

What operations are fast?
What operations are easy to implement?
How much memory does the graph take?
How easy is it to use the graph in different settings.

In JavaScript, all types are dynamic, so it's easy to just say "A graph is a list of nodes and a list of edges", because the language doesn't ever require that you formally specify what a node or an edge looks like. It doesn't care, and if you make a mistake, it will just crash at runtime.

Notice that your JavaScript version of a graph doesn't actually specify how nodes and edges are represented. What does an edge look like? If you insert an edge as a 2-element array, but try to access it as an object, you will have a runtime error.

Haskell and Coq's definitions try to solve this issue with type safety. They have a formal definition of the different forms a Graph can take, so that you always know at compile-time which operations on it are valid or not.

Let's look at the versions and their tradeoffs:

data Graph a = Empty | Vertex a | Overlay (Graph a) (Graph a) | Connect (Graph a) (Graph a)

This version is interesting, because it is an inductive definition of a graph, that allows you to implement graph operations easily as recursive functions. So you know that a graph is always empty, a single vertex, the overlay of two graphs, or the connection of two graphs, and you can safely pattern match on these 4 cases.

class Graph g where
  type Vertex g
  empty   :: g
  vertex  :: Vertex g -> g
  overlay :: g -> g -> g
  connect :: g -> g -> g

This isn't actually an implementation of a graph, but instead is an interface for a graph. It says what operations are available on a graph, but not how they're implemented. Users could provide their own Graph instances, and can write code that is generic over which Graph implementation is used. This helps bring back some of the flexibility that we had in JavaScript but lost when adding types.

type Graph = Table [Vertex]
type Table a = Array Vertex a

This is a classic "Adjacency List" implementation of a graph: we store the outgoing edges for each vertex. It is space efficient, and allows for quick BFS and DFS, but is slower for checking the existence of an edge, or deleting an edge.

Structure Graph := {
  V :> nat ; (* The number of vertices. So the vertices are numbers 0, 1, ..., V-1. *)
  E :> nat -> nat -> Prop ; (* The edge relation *)
  E_decidable : forall x y : nat, ({E x y} + {~ E x y}) ;
  E_irreflexive : all x : V, ~ E x x ;
  E_symmetric : all x : V, all y : V, (E x y -> E y x)
}.

This is an interesting representation. First, it's similar to a typeclass, in that it's abstract: it works for any types $V$ and $E$ so long as they can be coerced into numbers and edge-lookup functions. This isn't saying "this is how you can represent a graph", it's saying "here's an interface for graph representations".

Second, because we are in a dependently typed setting, we want to encode some properties of the graph, so that we can't create ill-formed graphs. We can then use these properties when proving things about graphs later on. Here, there are three properties that we require all graphs to have:

The encoding must be irreflexive i.e. there are no self edges
The encoding must be symmetric i.e. any time there's an edge u->v, there's also an edge v->u
The edge relation is decidable i.e. we can take

The third condition is important because Coq is a total language. It doesn't allow for any non-terminating code, so we need to prove that our edge lookup actually halts.

Finally, there's the Coq graph definition:

Inductive Graph : V_set -> A_set -> Set :=
  | G_empty : Graph V_empty A_empty
  | G_vertex :
      forall (v : V_set) (a : A_set) (d : Graph v a) (x : Vertex),
      ~ v x -> Graph (V_union (V_single x) v) a
  | G_edge :
      forall (v : V_set) (a : A_set) (d : Graph v a) (x y : Vertex),
      v x ->
      v y ->
      x <> y ->
      ~ a (A_ends x y) -> ~ a (A_ends y x) -> Graph v (A_union (E_set x y) a)
  | G_eq :
      forall (v v' : V_set) (a a' : A_set),
      v = v' -> a = a' -> Graph v a -> Graph v' a'.

This version provides a concrete implementation, that (I think) fulfills the interface you gave. In particular, it says we can build a graph in 4 ways:

A graph can be empty
We can add a vertex to a graph
We can add an edge to a graph
We can map an equality over a graph

The beauty of this implementation is that the vertex and edge sets are stored at the type level. This is the magic of dependent types: the type of the graph depends on the values it contains. So, when adding an edge, the type system ensures that we can't possibly add an edge between two vertices that aren't in our vertex sets.

Secondly, this implementation is inductive, similar to the Haskell one, so writing proofs about this graph by induction will be easy.


Optimal pivot selection for quick-sort The actual runtime of applying quick-sort to an integer array heavily relies on the choice of pivots.

It is well known that picking a random pivot does not work as good as taking the median of three, or the ninther of the array.

Obviously, for comparison we need to fix a model of computation / cost per operation.

Assume we are working in a model where each comparison between elements costs $1$, while swapping two elements costs $\gamma$ for some $\gamma>0$.

If we invest more effort in finding a good pivot (e.g., take the median of $k$ random samples), we might make more comparisons, but swap less elements.

  Under this model, what is the optimal (in terms of expected cost) pivot choosing strategy (i.e., if our array is of size $n$, how many elements $k$ should we sample before deciding which pivot to use)?

(We assume that the input might be adversarial, so taking as pivot the median of uniformly sampled elements seems like the right thing to do).

The first thing to note specifically for integer arrays is that quicksort might not be the best choice for sorting depending on the possible range of values.  A counting sort may be more appropriate, for example.

In the general case (i.e. not specific to integers), Martinez and Roura analyzed this problem for both quicksort and (single order statistic) quickselect. See "Optimal Sampling Strategies in Quicksort and Quickselect" SIAM Journal on Computing http://dx.doi.org/10.1137/S0097539700382108

The short answer is that the optimal strategy is to pick as the pivot element the median of a sample of elements, with the sample size roughly proportional to the square root of the number of elements in the array to be sorted, unless swapping is extraordinarily expensive.  Specifically for simple types (e.g. integers), swapping is not expected to be expensive; it may be less costly than comparison via a function call, as in qsort.

That strategy also changes the worst-case (adversarial input) performance from quadratic to polynomial with an exponent of 1.5; see also McGeoch and Tygar "Optimal Sampling Strategies for Quicksort" Random Structures and Algorithms http://dx.doi.org/10.1002/rsa.3240070403

Instead of using the exact median of the samples, a lower-cost option is to approximate the median with a pseudomedian. One which can be scaled with sample size and which provides an increasingly accurate estimate of the median as sample size increases is the remedian as described by Rousseeuw and Bassett in "The Remedian: A Robust Averaging Method for Large Data Sets" Journal of the American Statistical Association http://amstat.tandfonline.com/doi/pdf/10.1080/01621459.1990.10475311   See also Battiato et al. "An Efficient Algorithm for the Approximate Median Selection Problem"  in Proceedings of the 4th Italian Conference on Algorithms and Complexity http://dl.acm.org/citation.cfm?id=648257.753042 (it's the same remedian, "rediscovered" by the authors about a decade after Rousseeuw and Bassett).

For an even deeper dive (especially regarding the importance of quality of sampling as well as quantity), see https://github.com/brucelilly/quickselect/blob/master/lib/libmedian/doc/pub/generic/paper.pdf or the video at https://www.youtube.com/watch?v=iWmAf4RMMiM  There you'll also find a way to get the adversarial performance to remain linearithmic (as opposed to going polynomial) without deterioration in non-adversarial input performance.

You say

  If we invest more effort in finding a good pivot (e.g., take the median of k random samples), we might make more comparisons, but swap less elements.

What typically happens (for uniformly distributed random input) is that a better (i.e. closer to the true median) pivot results in fewer overall comparisons during sorting but more swaps.  With a pivot close to the median every time, the number of comparisons to sort (ignoring comparisons for pivot selection) is $N \log _ 2 N$ and the number of swaps (if efficiently arranged) is 1/4 $ N \log _ 2 N$.  On the other hand, a randomly selected pivot element leads to 1.386 $N \log _ 2 N$ comparisons but only 1/6 $N \log _ 2 N$ swaps (more than 8 times as many comparisons as swaps).  The two are related; a reduction in the number of swaps implies a lopsided partition (about 78.9%/21.1% for 1/6 $N \log _ 2 N$ swaps) and that leads to an overall increase in the number of comparisons because the problem size is reduced by less than half.  The key to minimizing comparisons is using an efficient pseudomedian, one which provides a good estimate of the median with much fewer comparisons than the ~2N which are expected to find the exact median.  The remedian with base 3 computed on a sample of size $\sqrt {N}$ costs about 1.5 $\sqrt{N}$ comparisons, which is much less than 2N for reasonable N.


Find the centre of a circle given two points lying on it and its radius We have been given 2 points on a circle and its radius. Now I want to find out the centre point of such a circle. How can I code this efficiently without solving the quadratic equations?


Applying a permutation on a sequence with multiplication We are given a sequence of $n$ numbers called $\alpha$ and an arbitrary number $x$. Give an algorithm to find a permutation $\pi$ of size $n$ such that $\sum_{i=1}^n{\alpha_i.\pi_i} = x$ or tell if there is none.

Well I wasn't able to solve it in polynomial time and I'm not sure whether it's possible. So if it's NP would you give me some observations on the reason?

The problem is NP-complete. Here is a reduction from 3SAT.

Given an instance of 3SAT with variables $v_1,\ldots,v_n$ and clauses $c_1,\ldots, c_m$, construct numbers as follows. We represent a number as the form $\lambda_1p^{\mu_1}+\lambda_2p^{\mu_2}+\cdots$ where $p$ is a very large number (we will estimate $p$ later) so that we can assume there is no carry when performing addition of numbers.

Construct $2n-1$ numbers $u_1,\ldots,u_{2n-1}$: $p^0, p^1, \ldots, p^{2n-2}$.
For each variable $v_i$, if $v_i$ shows up in clauses $c_{j_1},c_{j_2},\ldots$ and $\bar{v}_i$ shows up in $c_{k_1},c_{k_2},\ldots$, construct two numbers $y_i=p^{2n-2+i}+mp^{3n-2+j_1}+mp^{3n-2+j_2}+\cdots$ and $\bar{y}_i=p^{2n-2+i}+mp^{3n-2+k_1}+mp^{3n-2+k_2}+\cdots$.
For each clause $c_j$, construct numbers $z_j=p^{3n-2+j}$.
Add $0$s to make there are $(13n+1)m$ numbers in total.
The target
$$
\begin{align}
x=\;&(n+1)p^0+(n+2)p^1+\cdots+(3n-1)p^{2n-2}\\
&+4np^{2n-1}+4np^{2n}+\cdots+4np^{3n-2}\\
&+16nmp^{3n-1}+(16nm+1)p^{3n}+\cdots+(16nm+m-1)p^{3n-2+m}.
\end{align}
$$

Since there are $(13n+1)m$ numbers and the coefficient of $p^{\mu}$ is at most $m$, we can choose $p=(13n+1)m^2+1$. The construction is in polynomial time.

Now we can see in a valid permutation, the first $2n-1$ numbers must occupy the positions from $n+1$ to $3n-1$, and the next $2n$ numbers $y_1,\bar{y}_1,\ldots$ must occupy the positions $1,\ldots, n$ (say low positions) and $3n,\ldots, 4n-1$ (say high positions), where for each $i$, one of $y_i,\bar{y}_i$ occupies a low position and the other occupies a high position.

Suppose the instance of 3SAT is satisfiable. If $v_i$ is assigned $1$, we arrange $y_i$ at a high position and $\bar{y}_i$ at a low position; otherwise we arrange $y_i$ at a low position and $\bar{y}_i$ at a high position. Now the numbers constructed in steps 1 and 2 are arranged. Consider $\sum\alpha_i\pi_i=\cdots+\lambda_1p^{3n-2+1}+\cdots+\lambda_m p^{3n-2+m}$ for these numbers. We can arrange $z_j$ at position $16nm+j-\lambda_j$ to satisfy the sum goal. Note at least one literal in a clause must be assigned $1$, i.e. its corresponding number ($y_i$ or $\bar{y}_i$) must be at a high position, hence we have

$$m\cdot 3n < \lambda_j\le m\cdot (4n-1+4n-2+4n-3)<12nm,$$

i.e. $4nm+j<16nm+j-\lambda_j<13nm+j\le (13n+1)m$, thus the positions for $z_j$'s are valid. Also note $\lambda_j$ is a multiple of $m$, then $16nm+j-\lambda_j \equiv j \pmod m$, which means these positions do not conflict with each other. As a result, we have arranged these numbers such that $\sum\alpha_i\pi_i=x$.

On the other hand, if there is a permutation satisfying $\sum\alpha_i\pi_i=x$, then for each $i$, if $y_i$ is arranged at a high position, we assign $v_i=1$; otherwise we assign $v_i=0$. Consider $\sum\alpha_i\pi_i=\cdots+\lambda_1p^{3n-2+1}+\cdots+\lambda_m p^{3n-2+m}$ for numbers constructed in steps 1 and 2, then the position of $z_j$ must be $16nm+j-\lambda_j$, which is a valid position, meaning $16nm+j-\lambda_j\le (13n+1)m$, i.e. $\lambda_j>(3n-1)m$. This means at least one number ($y_i$ or $\bar{y}_i$) related to clause $c_j$ is arranged a high position, which means the clause is satisfied.

For example, consider an instance with two clauses $\bar{v}_1\vee v_2\vee v_3$ and $v_1\vee \bar{v}_2\vee v_3$, the numbers are:

           p^0  p^1  p^2  p^3  p^4  p^5  p^6  p^7  p^8  p^9
                                    v_1  v_2  v_3  c_1  c_2
u_1        1
u_2             1
u_3                  1
u_4                       1
u_5                            1
y_1                                 1                   2
\bar{y}_1                           1              2
y_2                                      1         2
\bar{y}_2                                1              2
y_3                                           1    2    2
\bar{y}_3                                     1
z_1                                                1
z_2                                                     1
0
0
...
-----------------------------------------------------------
x          4    5    6    7    8    12   12   12   96   97

There are $80$ numbers in total. (One of) the permutation(s) corresponding to the solution $v_1=v_2=v_3=1$ is $\bar{y}_1\bar{y}_2\bar{y}_3u_1u_2u_3u_4u_5y_1y_2y_30\cdots 0z_1z_20\cdots$ where $z_1$ is at position $73$ and $z_2$ is at position $74$.

If the numbers are upper-bounded by a constant, say $100$, then the problem can be solved in polynomial time.

Let $f(\alpha, x)$ denote whether such permutation exists. Note for any permutation $\pi$, suppose $\alpha_k$ is placed at the first position (i.e. $\pi_k=1$), we have
$$\sum \alpha_i\pi_i=\alpha_k+\sum_{i\neq k}\alpha_i\pi_i=\sum \alpha_i+\sum_{i\neq k}\alpha_i(\pi_i-1),$$
which means the primary problem has a valid solution iff there exists $k$ such that the subproblem for sequence $\alpha-\alpha_k$ (meaning the sequence $\alpha_1,\ldots,\alpha_{k-1},\alpha_{k+1},\ldots$) and target $x-\sum \alpha_i$ has a valid solution, so we have

$$f(\alpha,x)=\bigvee_{i=1}^n f\left(\alpha-\alpha_i,x-\sum_{j=1}^n \alpha_j\right).$$

Note we do not care the order of the sequence, so every subsequence of $\alpha$ can be expressed as "$n_1$ $1$s, ..., $n_{100}$ $100$s", which means there are up to $n^{100}$ different subsequences of $\alpha$. Therefore, we can compute $f(\alpha,x)$ using the recursion formula above in $O(n\cdot xn^{100})=O(n^{103})$ time.


Pumping-Lemma regular languages: Consider multiple cases? The language $ L = \{ a^nb^mc^m : n,m \in \mathbb{N} \} $ is non regular. Suppose this needs to be proven using the pumping lemma for regular languages:
Be $ z = ab^nc^n $ such that $ z=uvw, |v| \geq 1, |uv| \leq n $.
Obviously $uv^2w \notin L $ with $ v=b^{k}$ and $ 1 \leq k \leq n-1$.
Is this proof finished now? Or do I need to consider $ v=ab^{n-1} $ as well?
More general: Using the pumping lemma for regular languages, do i need to consider all possible combinations for $uv$?

Of course, you have to consider all possible cases. Otherwise you do not prove that "there exists a factorization" is false. So you actually have to consider all $ab^k$ with $k < n$. Here you get some prefix $ab\cdots bab\cdots b$ and therefore the words are outside tha language. Or you chose a different word $z$ if $n=0$ is allowed, which depends on your definition of the natural numbers - then you only have one case.

For the case you treat, probably stating that $uv^2w = ab^{n+k}c^n$ would be more complete than saying "obviously."