Does the O(n) algorithm always run faster than the O(n^3) algorithm? Why? Assuming that the time complexity of the two algorithms $A_1$ and $A_2$ to solve the same problem are $O(n^3)$ and $O(n)$ respectively. If you write programs for these two algorithms and run them in the same environment, does the program of algorithm $A_2$ run faster than algorithm $A_1$ for sure? why?

$O(f(n))$ means: There is a constant c > 0, and an integer $n_0$, so that for every $n > n_0$ the time is less than $c \cdot f(n)$.
Note that the integer $n_0$ could be very, very large. And the constant c could be very, very large. If $n ≤ n_0$ then we know nothing whatsoever about the time; the $O(n)$ algorithm could be slower than the $O(n^3)$ algorithm until n is really large. And the constants could be very different. You could have an algorithm that takes $n$ years, and another that takes $n^3$ nanoseconds.
Just for fun, try to figure out for which n the O(n) algorithm is faster, and how long it runs when it runs faster. For example with n = 1,000,000 the first algorithm takes a million years, the second takes $10^{18}$ nanoseconds = $10^9$ seconds < 32 years.
PS. When you look closely at the definition of $O(f(n))$, it doesn't actually say that our function must be anywhere near f(n). For example, $n^{1/2} = O(n^3)$ according to the definition. You'll often see $\Theta(f(n))$ (big-Theta) which means your function isn't just less than c * f(n) but between c1 * f(n) and c2 * f(n). And there are situations where a function doesn't behave the same for all values. Say sometimes it's close to n^3, but at other values n it's much smaller. If f(n) cannot be replaced with a smaller function then we call it "asymptotic O(f(n))".
So you could have f(n) = n if n is even, 1 otherwise. And g(n) = 1 if n is even, n^3 otherwise. For even n, f(n) is larger, for odd n, g(n) is larger.


Give a Search Problem in co-NP Ex.1. Give a Search Problem whose deciding Problem is in co-NP.

Assuming 3SAT is in NP then asking wether a given Boolean formula has a Solution is a search problem in NP right?

Then would asking wether a given Boolean formula has no Solution be in co-NP?

Specifically speaking, 3-SAT is an example of NP-Complete problem. But your problem is only considered with NP problems.

We have the decision problem:

  Is a SAT problem in NP?

Obviously, it is. Because you could always verify a "certificate" in time linear to your input size (values of your literals, that is a sequences of 0s and 1s).

For your question:

  Is a un-SAT problem in co-NP? (complement to SAT problem)

We could find the following definition:

  A decision problem X is a member of co-NP if and only if its
  complement X is in the complexity class NP [1].

Therefore, un-SAT is co-NP by definition.


Prize collecting steiner tree I'm reading about the prize collecting steiner tree problem and an approximation algorithm that uses randomization to set a lower bound on the optimal solution (see Chapter 5.7 in  The Design of Approximation Algorithms  by Williamson and Shmoys). I don't understand the second line in the proof for Lemma 5.16: .

It seems to me that $V-V(T)$ is a much larger set than $U$. So, how can the total penalty for this set be upper bounded by the total penalty of a set that is much smaller?

$T$ is a tree that connects the chosen subset of terminals $U$. Thus $U$ is a subset of $V(T)$, and $V \setminus V(T)$ is a subset of $V \setminus U$ (we're summing $i$ not in $U$).


Page management in OS kernels I looked at some old OS theory books of mine and noticed that one glaring omission in all of these OS books is how to actually keep track of physical pages that are free (i.e. algorithms for actually implementing the free list). I know pretty well how userland memory allocators work, but a big difference with physical page allocation is that fragmentation of physical pages shouldn't be an issue, since the page table can just pick and choose the physical pages without having to care about whether they are contiguous or not. Since avoiding fragmentation is one of the main concerns of userland allocators, it seems like physical page allocation is fundamentally a different problem. I guess that this is not completely accurate if one wants to support superpages to reduce pressure on the TLB.

My question: What are techniques are used in modern high-performance kernels for this problem? Also, does this problem become significantly more complicated in NUMA systems?

Page frame management is conceptually very simple; all you really need is a linked list. However, there are two main factors which complicate things:

DMA. DMA is one of the few things that might need a physical buffer larger than a page in size. In addition, there are legacy devices to contend with; on x86, for example, 32-bit devices can only do DMA from physical addresses below the 4G limit. For ISA it's even worse.
Cache colouring, which is an extremely important optimisation.

Most operating systems use surprisingly simple techniques.

Windows, for example, just uses a bunch of linked lists (or at least it did, last time anyone said anything about it). It's hard to say since we can't see the source code, but there are probably N*M linked lists where N is the number of possible states a page can be in (e.g. in-use, free, waiting to be paged out) and M is the number of colours.

Linux famously uses a buddy allocator to manage physical pages, which is only slightly more complicated than a bunch of linked lists when you think about it.

Probably the most sophisticated management scheme that has been documented extensively is that of Solaris. See Bonwick & Adams, Magazines and Vmem: Extending the Slab Allocator to Many CPUs and Arbitrary Resources, USENIX 2001. There is also an extended discussion in the book Solaris Internals. The Solaris slab allocator goes to a lot of trouble to avoid lock contention, cache thrashing, and the like, and also can tune its implementation for different data types as needed.

What's interesting is that Solaris uses the same memory allocator to handle page frames that it uses to handle kernel objects, by nesting slab allocators inside slab allocators. The paper is definitely worth a read.


How is the Longest Path Problem NP complete? From the following link:

https://www.csie.ntu.edu.tw/~lyuu/complexity/2016/20161129s.pdf

So basically, in our iff proof, we have to show two directions:

Forward: If Hamiltonian Path has a yes-instance, so does longest path. This makes sense because we can just let "k" = |V| - 1 if hamiltonian path is yes. Then clearly there is a longest simple path with |V| - 1 edges.

I'm having trouble with the backward part

Backward: If Longest Path has a yes instance, so does longest path. Let's assume that there is a longest path from s to t of length k (this can be a different k than the one we defined above?). How does that guarantee that there is a hamiltonian path from s-t? If it is the same k, where k = |V| - 1, then I agree there is a hamiltonian path, but what if this k is something different?

How does that guarantee that there is a hamiltonian path from s-t?

It doesn't, but the Longest Path problem doesn't require a path between particular vertices, it only requires that some simple path of length $K$ exist in the graph.  To reduce Hamiltonian Path to Longest Path you just require that path to have $|V| - 1$ edges, which in a simple path must involve all the vertices in the graph, making it a Hamiltonian Path.


Turing machines and languages -- recursive (enumerable) or not For an assignment in my university, we have to answer multiple choice questions about theoretical computer science. This particular one I find very hard to understand. I wonder if some of you could explain it to me.

In this question, L1, L2, L3, L4 refer to languages and M, M1, M2 refer to Turing machines.

Let

L1 = {(M1,M2) | L(M1) is a subset of L(M2)},
L2 = {M | There exists an input on which TM M halts within 100 steps},
L3 = {M | There exists an input w of size less than 100, such that M accepts w},
L4 = {M | L(M) contains at least 2 strings}.

Decide whether each of L1, L2, L3 and L4 are recursive, RE or neither. Then identify the true statement below.

     a)      The complement of L3 is recursively enumerable.
     b)      The complement of L2 is recursive.
     c)      The complement of L2 is not recursively enumerable.
     d)      L1 is recursively enumerable.

What I do not understand is, how the definitions of L1, L2, L3, L4 can tell me whether or not they are recursive (enumerable).

My guesses (probably wrong) are:

L1: ?

L2: recursive enumerable (I thought this since obviously there are inputs on which the TM halts but we can not say if it halts every time – therefore only recursive enumerable and not recursive)

L3: recursive enumerable (Same explanation as for L2)

L4: not recursive (This is only a guess, I don't get how the number of minimum strings of the language can imply any type of recursiveness.)

Hints.

If you're trying to figure out some property of a Turing machine and the only thing you can think of is, "Check every input" then it's probably not recursive.
If a language is RE and so is its complement, both are actually recursive (this is a good way of proving that languages aren't RE: for example, the language of pairs $\langle M,x\rangle$ such that Turing machine $M$ does not halt on input $x$ is not RE for this reason).
If a Turing machine halts within 100 steps, how much of its input has it seen?

Note that L2 and L3 are subtly different so you can't use the same explanation for both (the answers are actually different).


Understanding a proof for the existance of a non-computable function For school, we have a proof that some functions are not Turing computable.
The example is:
$$ G(k) = \begin{cases} f_k(k) + 1 & \text{ if $f_k(k)$ is defined}, \\ 1 & \text{ otherwise}.\end{cases} $$

Claim: $G$ is non computable.

Proof: In view of obtaining a contradiction, let's say $G$ is computable, say by the $k$th Turing machine.
Give the encoding of this $k$th Turing machine as an argument for $G$.
This leads to a contradiction: if $f_k(k)$ is defined, then $f_k(k)$ is not equal to $g(k) = f_k(k) + 1$. Else $f_k(k)$ is undefined and not equal to $g(k) = 1$.

I don't understand the contradiction, help please...

The contradiction reached is that $0 = 1$ which violates one of Peano's axioms. Assume $G$ is computed by the $j$-th Turing machine. Observe that $G$ is everywhere defined. Then
$$f_j(j) = G(j) = f_j(j) + 1$$
and by canceling $f_j(j)$ on both sides we get
$$0 = 1.$$


SAT for positive CNF clauses with exactly half of the variables being true I am focusing here on positive even SAT problems, that is a CNF for which all literals are positive, and in which an even number  n of variables occur. This is obviously trivial : just set all variables to true and all clauses are satisfied. The same if we look for an assignment that would have all but one variables being true (unless the problem is 1-SAT, which is also trivial)

But I am wondering if we could find an algorithm that searches for some solution (or proves the absence of solutions) with exactly half of the variables being true, the other half being false.
Have you an idea of how to create this algorithm ? And what could be its complexity ?

Your problem is NP-complete by the modern presentation of Schaefer's dichotomy theorem.

You can also prove its NP-completeness by direct reduction of SAT to your problem.  If a CNF formula has $n$ variables $x_1 \dots x_n$ introduce $n$ new variables $y_1 \dots y_n$ and add 2-CNF clauses that force each $y$ variable to have the opposite value of the corresponding $x$ value.
I.e.
$$(x_1 \lor y_1)$$
$$(\lnot x_1 \lor \lnot y_1)$$
$$(x_2 \lor y_2)$$
$$(\lnot x_2 \lor \lnot y_2)$$
$$\dots$$
$$(x_n \lor y_n)$$
$$(\lnot x_n \lor \lnot y_n)$$

All solutions to the resulting formula will have half the variables with true values and half false.

For unaltered formulas, you don't need a special algorithm to find half-true half-false solutions.  Take any CNF formula with an even number of variables and then add CNF clauses encoding a chain of adder circuits that sums the values of all the variables.  Next, add a comparison circuit that is only satisfied if the sum is one-half the total number of variables.  Run a normal SAT solver on the result and it will output only solutions where one-half the original variables have a true value.  This is a somewhat naive solution but it gets the job done.

Search the literature a bit more and you will discover SAT solvers that accept pseudo-Boolean constraints in addition to CNF.  With these you can write out the $x_1 + x_2 + x_3 + \dots + x_n = n / 2$ equation explicitly and the solver will either churn out the adder circuits for you or just handle the equation internally.

Your special SAT problem is also readily transformed into a 0-1 integer programming problem for which there are solvers available.


How to make a language homoiconic According to this article the following line of Lisp code prints "Hello world" to standard output.

(format t "hello, world")

Lisp, which is a homoiconic language, can treat code as data in this way:

  Now imagine that we wrote the following macro:

  (defmacro backwards (expr) (reverse expr))

  backwards is the name of the macro, which takes an expression
  (represented as a list), and reverses it. Here’s "Hello, world" again,
  this time using the macro:

  (backwards ("hello, world" t format))

  When the Lisp compiler sees that line of code, it looks at the first
  atom in the list (backwards), and notices that it names a macro. It
  passes the unevaluated list ("hello, world" t format) to the macro,
  which rearranges the list to (format t "hello, world"). The resulting
  list replaces the macro expression, and it is what will be evaluated
  at run-time. The Lisp environment will see that its first atom
  (format) is a function, and evaluate it, passing it the rest of the
  arguments.

In Lisp achieving this task is easy (correct me if I'm wrong) because code is implemented as list (s-expressions?).

Now take a look at this OCaml (which is not a homoiconic language) snippet:

let print () =
    let message = "Hello world" in
    print_endline message
;;

Imagine you want to add homoiconicity to OCaml, which uses a much more complex syntax compared to Lisp. How would you do that? Does the language has to have a particularly easy syntax to achieve homoiconicity?

EDIT: from this topic I found another way to achieve homoiconicity which is different from Lisp's: the one implemented in the io language. It may partially answer this question.

  Here, let’s start with a simple block:

Io> plus := block(a, b, a + b)
==> method(a, b,
        a + b
    )
Io> plus call(2, 3)
==> 5

  Okay, so the block works. The plus block added two numbers.

  Now let’s do some introspection on this little fellow.

Io> plus argumentNames
==> list("a", "b")
Io> plus code
==> block(a, b, a +(b))
Io> plus message name
==> a
Io> plus message next
==> +(b)
Io> plus message next name
==> +

  Hot holy cold mold. Not only can you get the names of the block
  params. And not only can you get a string of the block’s complete
  source code. You can sneak into the code and traverse the messages
  inside. And most amazing of all: it’s awfully easy and natural. True
  to Io’s quest. Ruby’s mirror can’t see any of that.

  But, whoa whoa, hey now, don’t touch that dial.

Io> plus message next setName("-")
==> -(b)
Io> plus
==> method(a, b,
        a - b
    )
Io> plus call(2, 3)
==> -1

You can make any language homoiconic. Essentially you do this by 'mirroring' the language (meaning for any language constructor you add a corresponding representation of that constructor as data, think AST). You also need to add a couple of additional operations like quoting and unquoting. That's more or less it.

Lisp had that early on because of its easy syntax, but W. Taha's MetaML family of languages showed that it's possible to do for any language.

The whole process is outlined in Modelling homogeneous generative meta-programming. A more lightweight introduction to the same material is here.


Status on Naoki Katoh's "Rectangle Wiring Problem" (minimum length tree to cover a partitioned rectangle)? I have found this interesting problem in graph theory and geometry which is allegedly an open problem but latest status seems to be from 01/25/02. I can't seem to find any more information about it, not even other papers describing it.

This problem has been studied since 2002, under the name minimum-length corridor problem.

The problem is known to be NP-complete[1,2], but there is a constant factor polynomial time approximation algorithm[3].

There is more work on this problem, which you can find by searching the citation network of the papers below.

[1]: GONZALEZ-GUTIERREZ, Arturo; GONZALEZ, Teofilo F. Complexity of the minimum-length corridor problem. Computational Geometry, 2007, 37.2: 72-103.

[2]: BODLAENDER, Hans L., et al. On the minimum corridor connection problem and other generalized geometric problems. Computational Geometry, 2009, 42.9: 939-951.

[3]: GONZALEZ-GUTIERREZ, Arturo; GONZALEZ, Teofilo F. Approximation Algorithms for the Minimum-Length Corridor and Related Problems. In: CCCG. 2007. p. 253-256.


Some basic questions on halt and move in Turing machines Im trying to learn about and set up Turing Machines (TMs) the simplest ways using the simplest definite rules. I am using my previous knowledge on simple Cellular Automata to do this. I want to write the computer code, but first I have to get some understanding of the restrictions and possibilities of TMs.

Firstly i define an operation as follows:

Operation (Op)

Do operation based on current color ($C$) and its state ($S$) i.e. $Op(c, s)$:

replace color $C$ with $0$ or $1$. (at current position of tape head) move
tape-head (change its position).
change state $S$ with $0$ or $1$ (at new position).

For each operation:

In general does a TM only have only one halting-operation?
(i.e. can only one operation promote the halting or can more than one operation do that?).
Can the tape-head also stop at a fixed position? (i.e. not move its head).
Instead of the rules $0$ (move left) and $1$ (move right), it can also $2$ (not move anywhere) or even jump two units to the left or right?

My last question is basically the same as the last question..

Can the tape-head move more than one unit to the left or right?

The reason I ask this, is because if there is only one halting state in no more than one operation, the number of rules (in my setup) can be reduced. And if the tape-head can move more than one unit either to the left or right or both my guess is that it can produce more complex outputs. But my questions are concerning what is the limitations of a Turing Machine.

Example

If something was unclear I can try this example:

  inp:    outp:
Op(0,0) => 110
Op(0,1) => 101
Op(1,0) => 111
Op(1,1) => 001*

Of the output ($b_2b_1b_0$), where the first bit ($b_0$) represent the tapehead-move direction, $b_1$ represents the new state, and $b_0$ represents the changed color.
The asterisk shows that a halting operation should be performed.

The first question I asked wether there was possible to have more than one halting operation in a TM. Basically I ask wether I can have two or more asterisks like this, or if its not allowed:

  inp:    outp:
Op(0,0) => 110
Op(0,1) => 101
Op(1,0) => 111*
Op(1,1) => 001*

Recap

So can more than one operation perform the halting operation?

Can we move the tape head more than one unit to the left or right, or can it stand still?

To answer any kind of question like this, you need to choose one of the standard definitions of Turing machines (there are several but they're all essentially the  same) and prove that adding the feature you want doesn't increase the computational power. You do that by showing how to simulate the feature using the standard machine.

  In general does a TM only have only one halting-operation? (i.e. can only one operation promote the halting or can more than one operation do that?).

It doesn't matter. If you want three halting states and I insist that there can be only one, then have three states called $h_1$, $h_2$ and $h_3$ and design the transition function so that, if the machine ever enters one of those, its next transition is to $\mathrm{HALT}$.

  Can the tape-head also stop at a fixed position? (i.e. not move its head). Instead of the rules 0 (move left) and 1 (move right), it can also 2 (not move anywhere) or even jump two units to the left or right?

Again, it doesn't matter. If I insist you must move left or right, you can move one step left and then move back to the right; you can move two steps to the right by moving one step, twice.

  Can the tape-head move more than one unit to the left or right?

Even that doesn't affect things: random-access Turing machines have an "address tape" onto which you can write a number and a special state that causes the head to move straight to the tape cell indexed by that number. Again, same power.

Multiple tapes, inserting and deleting characters, two-dimensional (or more!) tapes. Almost anything you can imagine makes no difference, and proving these things are standard exercises in computation theory textbooks.


Subset partition problem variant Given a set S of integers, the task is to partition the set into subsets such that:

Total number of partitions is maximized
Each partition has sum at least K

This looks like a variant of bin-packing problem, in which the bin has to filled upto a minimum capacity and the objective is to maximize the number of bins. I looked up the solutions of bin-packing problem, turned out ffd was the best approximation solution to it.

Could someone please tell me how to approach the partition problem?

For its complexity, note $N$ the sum of all your integers. Then, the number partitioning problem injects itself into your problem with $K=\frac{N}{2}$

I found this paper which deals with almost your problem. It aims to maximise the number of bins used, but instead of working with each partition must have a sum of at least $K$, you have each partition cannot be completed with another item.

Edit: Another user already asked almost the same question: https://scicomp.stackexchange.com/questions/8216/bin-packing-maximise-number-of-bins-fukubukuro-problem


Data structure and algorithms for a medical diagnosis software For an academic question, I plan to design a medical diagnosis system. Given a description of symptoms, produce a list of probable diseases (with closeness matching). I'm having some trouble finding papers for getting started. Which algorithms and data structure should I consider?

Machine learning algorithms and techniques are very successful and best practice in this area (clustering and classification techniques could be uses). For example in Machine Learning Techniques for AD/MCI Diagnosis and Prognosis or Medical decision support systems based on machine learning, thesis written by Chih-Lin Chi.

You can use simple records in database as the data model.


When is cumulative type universes useful? AFAIK, a hierarchy of type universe(Type^0: Type^1: Type^2: ...) was introduced to avoid inconsistency caused by Type: Type.

But some functional language(e.g. Idris) also allows subtyping of these type universes(x: Type^n then also x: Type^n+1). From my understanding, this is not mandatory to solve the inconsistency. So it leads me to guess there should be some advantages from this redundant subtyping rule.

When is cumulative type universes useful?

Without cummulative universes, if you have $A : \mathsf{Type}_3$ then you do not have $A : \mathsf{Type}_7$. Instead, we also have to introduce lifting functions $\iota_{i,j} : \mathsf{Type}_i \to \mathsf{Type}_j$ for all $i \leq j$ and write $\iota_{3,7}(A)$ to port $A$ from the third universe to the seventh one. But this is not all, we also want to know whether $\iota_{3,5}(\iota_{5,7}(A)) = \iota_{3,7}(A)$, i.e., can we lift in several steps? So we need to add a bunch of equations $\iota_{i,j}(\iota_{j,k}(A)) = \iota_{i,k}(A)$ for $i \leq j \leq k$. And this is not all, we also need things like $\iota_{i,i}(A) = A$ and $\iota_{i,j}(\Pi(x : A), B(x)) = \Pi (x : A) \iota_{i,j}(B(x))$, and on and on. It's all very annoying.

With cummulative universes we can just drop all the lifting functions $\iota_{i,j}$.

So why would anyone reject cummulative universes? There are several reasons. An important one is that with cummulative universe it is not true that every expression has at most one type, since a type is an element of many universes. This complicates various algorithms for inferring and checking types. Another reason is semantic: there are interesting models of type theory in which universes are not cummulative.


Is there a reason to NOT wrap preprocessor macros in parens? I'm writing a design document for a macro expansion language that is specifically intended for arithmetic operations on integers. I've already determined that not wrapping macros with parens can lead to unexpected behavior. Rather than expect users to practice impeccable code hygiene, implementing automatic parens will save the users time and reduce bugs.

If a preprocessor adds enclosing parentheses every time a macro is expanded, is any useful functionality lost?

#define PLUS +

3 PLUS 5

Any more questions?


Is better than O(n^2) possible for getting pairs that sum to a multiple of 10? Is it possible to solve a problem with a worse case less than $O(n^2)$, when the input is an an array of numbers and the output is all pairs that sum to a number divisible by 10?  for example

int [] a = {1, 2, 15, 25, 28};
// would produce [2, 28], [15, 25]

I don't think so because when all sums are divisible by 10 then the total number of pairs is $n(n-1)/2$ which is $O(n^2)$.

int [] a = {5, 15, 25, 35, 45};
// n(n-1)/2 = 5(4)/2 = 10
// pairs [5, 15], [5, 25], [5, 35], [5, 45], [15, 25], [15, 35], [15, 45], [25, 35], [25, 45], [35, 45]

It is not possible to have an algorithm that is faster than $O(n^2)$ as the output can be $O(n^2)$ — all pairs. This can happen when all numbers are divisible by 10, or all are returning 5 when taken modulo 10.


Fundamental algorithms in formal language-automata theory I'm willing to take a course in formal languages and automata theory , where we will explore side by side a functional programming language to implement the different algorithms we will encounter ,despite i am new to the language , i am assuming i've learned what's nessecary to move to the theoretical part , so i'm wondering what are the must-knows of FL & AT to a programmmer , that is what are the most fundamentals algorithms one necesserily have to know while studying formal languages and automata theory ?

They're simple, but the various DFA $\leftrightarrow$ NFA $\leftrightarrow$ RE conversions are quite handy.

Also, being able to find the Parikh mapping of a semilinear language is quite useful for more advanced applications (especially when you get out of the regular languages), since it lets you answer a lot of decidable properties.


What is the difference between a page and thread? "Each process that is executed is divided into blocks of same size, called pages."
"Thread is a part of process being executed."

Are pages and threads both part(s) of process? Whats the difference between thread as a part of process and page as a part of process?

You're looking at very vague descriptions and asking "What's the difference between these things that haven't been described properly?" For a more detailed understanding, you should, well, look for more detail, which is widely available.

A page is a block of memory; a thread is a sequence of instructions to be executed.


Union and intersection of a regular and a non-regular language Lets say we have $L_1$, which is a regular language and $L_2$ which is not. Are $L_1 \cap L_2$, $L_1 \cup L_2$ , $L_1$ \ $L_2$ and $L_1 \cdot L_2$ are always non-regular languages?

We know that two regular languages always gives us a regular language under all of the above. I can't find anywhere any proof that combination of two languages, one regular and one non-regular results always in a regular or a non-regular language. It seems for me that it should be a non-regular in all above cases. Am I wrong?

Note that the languages $\emptyset$, $\{\epsilon\}$ and $\Sigma^*$ are regular. Let $L_2$ be any non-regular language over $\Sigma$.

Union. $\emptyset \cup L_2 = L_2$, which is non-regular; $\Sigma^*\cup L_2 = \Sigma^*$, which is regular.

Intersection. $\Sigma^*\cap L_2 = L_2$; $\emptyset\cap L_2 = \emptyset$.

Subtraction. $\Sigma^*\setminus L_2 = \overline{L_2}$, which is non-regular, since regular languages are closed under complementation.  That is, if $\overline{L_2}$ were regular, then $\overline{\overline{L_2}}=L_2$ would also have to be regular.  $\emptyset\setminus L_2 = \emptyset$, which is regular.

Concatenation. $\{\epsilon\}\cdot L_2 = L_2$; $\emptyset\cdot L_2 = \emptyset$.


if $L\in NP\cap Co-NP$ is NP-Hard, then $NP=Co-NP$ I'm looking for a proof to the claim stated in the title:
if $L\in NP\cap Co-NP$ is $NP$-Hard, then $NP=Co-NP$.
I read the proof from my professor's recitation, but couldn't understand it, and I was hoping to find more easy-to-understand version of that proof.
It goes something like that:
Let $L\in NP\cap Co-NP$ be an $NPH$ problem, and let $L'\in Co-NP$, our goal is to first show that $L'\in NP$.
We know that there exist a Cook reduction from $L'$ to $\bar{L'}$ (any problem can be reduced to its complement with Cook reduction), and since $\bar{L'}\in NP$, we also know that there exist a Karp reduction from $\bar{L'}$ to $L$.
So by transitivity, we have a reduction from $L'$ to $L$.
The only problem is, $NP$ is not closed under Cook reduction (if a problem $A$ can be reduced to a problem $B\in NP$ with Cook reduction, that doesn't mean that $A\in NP$...)
So define the relation $R_{L'}$, associated with $L'$ (meaning $R_{L'}$ is the search problem of $L'$) as follows:
$R_{L'}=\left\{(x,[(z_1,\sigma_1,w_1),(z_2,\sigma_2,w_2),...(z_t,\sigma_t,w_t)]) \right\}$
Now if we can prove that $R_{L'}$ can be decided with a deterministic polynomial verifier, and that for all $(x,y)\in R_{L'}$, $|y|\leq p(|x|)$ for some polynomial $p$, we're done, and that will prove that $L'\in NP$...
Now comes the part where I really lost him, he starts to rattle on and on about "questions" and "answers", and I completely lost track.
Can anyone provide a link that explains the rest of that proof more clearly?

Suppose $L$ is an NP-hard problem in coNP, and let $M$ be any problem in NP. Since $L$ is NP-hard, there is a polytime reduction $f$ such that $x \in M$ iff $f(x) \in L$. Since $L$ is in coNP, this gives a coNP algorithm for $M$: given an input $x$, compute $f(x)$ and apply the coNP algorithm for $L$. This shows that $M$ is in coNP. In other words, NP is a subset of coNP. The same argument also shows the reverse inclusion, and so NP equals coNP.

The key idea is to avoid Cook reductions, for the reasons you mention.


Check if given vertices form a connected subtree in a graph The approach described in this question is wrong. It'll find false positives for disconnected components with multiple vertices. See D.W.'s answer for a reliable alternative.

This might be a simple question, but I can't seem to find a clear cut algorithm for this. I'm given a set of vertices from a graph and I need to determine whether they form a connected subtree in this original graph. I also have the neighbors of each of the vertices and an edge list to work with.

My approach would be to loop over the vertices and check if each one has at least one of the other given vertices as a direct neighbor. If one of them hasn't, it must be disconnected from the rest of the vertices, so the set can't form a connected subtree and we can return false early. So like this:

foreach (vertex in input)
{
   connectedToAny = false;

   foreach(other in input)
   {
          if (vertex.neighbors.contains(other))
          {
                 connectedToAny = true;
                 break;
          }
   }

   if (!connectedToAny)
   {
          return false;
   }
}

return true;

I'm aware this doesn't preclude the existence of cycles, but I'm happy to ignore this for now.

My main question is if this approach is in fact correct, or whether I'm missing cases where this could lead to false positives or negatives.

I'd also be happy to hear if there's a more efficient approach. I have also considered using a more conventional depth first search from any of the input vertices to see if they're connected, but I think I'd have to compute $neighbors \cap input$ at each recursion to specialize from simply connected (possibly via other vertices) to directly connected subtree, right?

You can do this in linear time.  You can tell if they're connected by keeping only those vertices and edges between them, and testing if the resulting graph is connected using standard algorithms (e.g., DFS).  You can tell if they're a tree by testing if the resulting graph has any cycles (e.g., using DFS).


Thomas write rula andview serializability Yesterday our Professor told in the class that Thomas Write rule ensures view serializability, but while surfing on this topic today on internet I am not able to find any information about that claim. So is it always $TRUE?$

What he told was this-->

  Timestamp ordering ensures conflict serializability

  Thomas write rule ensures view serializability

Timestamp ordering ensures conflict serializability

proof :

Assume that in precedence graph of schedule, we have edge $T_i \rightarrow T_j$.

Now, When $T_j$ puts it's request for this conflicting operation it will be continue only if $\text{timestamp}(T_i) < \text{timestamp}(T_j)$.

Now, for schedule to be non conflict serializable there must exist a cycle in precedence graph of that schedule and let say that cycle is $T_i, T_{i+1}, ...., T_i$.

Now, note that that cycle can't exist because existence of cycle implies $\text{timestamp}(T_i) < \text{timestamp}(T_i)$. (As timestamp are unique.)

So, we conclude that there can't be any such cycle which in turn implies that timestamp ordering protocol allows only conflict serializable schedules.


Algorithm to find optimal currency denominations Mark lives in a tiny country populated by people who tend to over-think things. One day, the king of the country decides to redesign the country's currency to make giving change more efficient. The king wants to minimize the expected number of coins it takes to exactly pay any amount up to (but not including) the amount of the smallest paper bill.

Suppose that the smallest unit of currency is the Coin. The smallest paper bill in the kingdom is worth $n$ Coins. The king decides that there should not be more than $m$ different coin denominations in circulation. The problem, then, is to find a $m$-set $\{d_1, d_2, ..., d_m\}$ of integers from $\{1, 2, ..., n - 1\}$ which minimizes $\frac{1}{n-1}\sum_{i = 1}^{n-1}{c_1(i) + c_2(i) + ... + c_m(i)}$ subject to $c_1(i)d_1 + c_2(i)d_2 + ... c_m(i)d_m = i$.

For instance, take the standard USD and its coin denominations of $\{1, 5, 10, 25, 50\}$. Here, the smallest paper bill is worth 100 of the smallest coin. It takes 4 coins to make 46 cents using this currency; we have $c_1(46) = 1, c_2(46) = 0, c_3(46) = 2, c_4(46) = 1, c_5(46) = 0$. However, if we had coin denominations of $\{1, 15, 30\}$, it would take only 3 coins: $c_1(46) = 1, c_2(46) = 1, c_3(46) = 1$. Which of these denomination sets minimizes the average number of coins to make any sum up to and including 99 cents?

More generally, given $n$ and $m$, how might one algorithmically determine the optimal set? Clearly, one might enumerate all viable $m$-subsets and compute the average number of coins it takes to make sums from 1 to $n - 1$, keeping track of the optimal one along the way. Since there are around $C(n - 1, m)$ $m$-subsets (not all of which are viable, but still), this would not be terribly efficient. Can you do better than that?

This is related to the well-known change-making problem. So well-studied, in fact, that this question has been investigated for $m \leq 7$ [1] using brute force. As of 2003, the hardness of finding optimal denominations appears to be an open problem.

If you check the articles citing Shallit, it seems as if denominations enabling greedy change-making strategies were of particular interest. It is clear that such denominations have advantages in practice.

What This Country Needs is an 18c Piece
 by Jeffrey Shallit (2003)


Last digit of polynomial value There is a simple-looking problem.

Given integer coefficients $c_{0}, c_{1}, c_{2}, \dots, c_{n - 1}$ of polynomial $$ p(x) = c_{0} + c_{1} x + c_{2} x^{2} + \dots + c_{n - 1} x^{n - 1} $$ and integer value $x$, find last digit of polynomial value at point $x$, or, equivalently, $p(x) \mod 10$.

My approach was to use Horner's rule for $p(x)$:

$$ c_{0} + c_{1} x + \dots + c_{n - 1} x^{n - 1} = c_{0} + x \left( c_{1} + x \left( c_{2} + x \left( c_{3} + \dots + x \left( c_{n - 2} + x c_{n - 1} \right) \dots \right) \right) \right) ,$$

but for every multiplication we take current value modulo 10. Here is a Python function implementing this algorithm.

def solve(c, x):
    xmod = x % 10
    value = c[-1] % 10
    for i in range(len(c) - 2, -1, -1):
        value = (value * xmod + c[i]) % 10
    return value

Are there better algorithms in sense of computational complexity (i.e. faster)?

Remainder modulo 10 instead of last digit
What is the last digit of -206? It is 6 by convention. It is not 4, the least positive remainder of -206 divided by 10.
For simplicity, we will compute the value of polynomial modulo 10. We will just say "the remainder of some number" to mean the least positive remainder of that number divided by 10. (The idea and algorithm in this answer can be adapted easily if 10 is replaced by another number.)
Periodicity of the remainders of powers
The remainder of $x, x^2, x^3, x^4, \cdots$ are periodical for any integer $x$. Let $r(n)$ be remainder of $n$.

$r(x^k)=0$ if $r(x)=0$
$r(x^k)=1$ if $r(x)=1$
$r(x^k)=x$ if $r(x)=5,6$
$r(x^k)=r(x^{k+2})$ if $r(x)=9$
$r(x^k)=r(x^{k+4})$ if $r(x)=2,3,4,7,8$

$k$ goes over all positive integers if $r(x)=0,2,4,5,6,8$.
$k$ goes over all nonnegative integers if $r(x)=1,3,7,9$.
Algorithm
Because of the periodicity, we can reduce the number of multiplication to at most 4 and the number of modulo operation to 2 without increasing the number of additions.
Here is the algorithm in Python, which should speak for itself. Note for a list lst, lst[s::g] means the subsequence lst[s], lst[s+g], lst[s+2*g], ... all the way to the end.
# c = [c_0, c_1, ..., c_{n-1}]
# remainder([3,12,5], 2) is 7
def remainder(c, x):
    x = x % 10

    if x == 0:
        return c[0] % 10
    if x == 1:
        return sum(c) % 10
    if x == 5 or x == 6:
        return (c[0] + sum(c[1:]) * x) % 10
    if x == 9:
        return (sum(c[::2]) + 9 * sum(c[1::2])) % 10
    if x == 2:
        return (c[0] + 2 * sum(c[1::4]) + 4 * sum(c[2::4]) + 8 * sum(c[3::4]) + 6 * sum(c[4::4])) % 10
    if x == 3:
        return (sum(c[::4]) + 3 * sum(c[1::4]) + 9 * sum(c[2::4]) + 7 * sum(c[3::4])) % 10
    if x == 4:
        return (c[0] + 4 * sum(c[1::2]) + 6 * sum(c[2::2])) % 10
    if x == 7:
        return (sum(c[::4]) + 7 * sum(c[1::4]) + 9 * sum(c[2::4]) + 3 * sum(c[3::4])) % 10
    if x == 8:
        return (c[0] + 8 * sum(c[1::4]) + 4 * sum(c[2::4]) + 2 * sum(c[3::4]) + 6 * sum(c[4::4])) % 10

If remainder(c,x) will be called repeatedly for the same polynomial c, then we can precompute table d[i], where d[i] = remainder(c,i) for i from 0 to 9. Then for that polynomial c, we can return d[x%10] given x in $O(1)$ time.
We can also cache the result on the fly. This can be done nicely by returning a closure that computes each result fully at most once. That is linear time the first time and constant time later on for numbers with the same remainders.
# For example, r = remainder([3,12,5]); print(r(2)); print(r(2));
def remainder(c):
    d = [None] * 10

    def remainder_c(x):
        x = x % 10

        if x == 0:
            return d[0] if d[0] else c[0] % 10
        if x == 1:
            return d[1] if d[1] else sum(c) % 10
        if x == 5 or x == 6:
            return d[x] if d[x] else (c[0] + sum(c[1:]) * x) % 10
        if x == 9:
            return d[9] if d[9] else (sum(c[::2]) + 9 * sum(c[1::2])) % 10
        if x == 2:
            return d[2] if d[2] else (c[0] + 2 * sum(c[1::4]) + 4 * sum(c[2::4]) + 8 * sum(c[3::4]) + 6 * sum(c[4::4])) % 10
        if x == 3:
            return d[3] if d[3] else (sum(c[::4]) + 3 * sum(c[1::4]) + 9 * sum(c[2::4]) + 7 * sum(c[3::4])) % 10
        if x == 4:
            return d[4] if d[4] else (c[0] + 4 * sum(c[1::2]) + 6 * sum(c[2::2])) % 10
        if x == 7:
            return d[7] if d[7] else (sum(c[::4]) + 7 * sum(c[1::4]) + 9 * sum(c[2::4]) + 3 * sum(c[3::4])) % 10
        if x == 8:
            return d[8] if d[8] else (c[0] + 8 * sum(c[1::4]) + 4 * sum(c[2::4]) + 2 * sum(c[3::4]) + 6 * sum(c[4::4])) % 10

    return remainder_c

There are further micro-tuning for various special situations.
If you are interested in parallel algorithm, you can check Estrin's scheme that can speed up the computation.


Is the set of non-deterministic Turing machines countable? We know that deterministic TMs are countable (enumeration). Does the same hold for NTMs? Are TMs and NTMS equinumerous?

Why is the class of DTM countable? Because you can code every DTM as a string (the program) over some alphabet. Now you can sort these strings lexicographicaly. Then the function
$$f(i\in \mathbb{N}):=\text{the $i$th string in the sorted sequence of DTMs},$$
is a bijection between the natural numbers and the set of DTMs. Hence the set of DTMs is countable.

Now here is the point. You can argue the same for NTMs. Hence the set of DTMs and NTMs are both countable and therefore equinumerous.


Independence of order of insertion hashtable with open addressing I'm taking a data-structure class, and the lecturer made the following assertion:

  the number of attempts needed to insert n keys in a hash table with linear probing is independent of their order.

No proof was given, so I tried to get one myself. However, I'm stuck.

My approach at the moment: I try to show that if I swap two adjacent keys the number of attempts doesn't change. I get the idea behind it, and I think it's going in the right direction, but I can't manage to make it into a rigorous proof.

Aside, does this fact also hold for other probing techniques such as quadratic or double hashing?

You can get from any order to any other order by making a series of swaps (see e.g., https://en.wikipedia.org/wiki/Cyclic_permutation#Transpositions).  So, if you can prove that making a single swap never changes the number of attempts, then it follows that the number of attempts does not depend on the order.


How can I multiply a binary representation by ten using logic gates? So I’m currently working on something and I have converted all decimal digits 0-9 into binary.
But now I want to take say 6 in binary and increase its order of magnitude by base 10 (turning 6 into 60) without converting back to base 10.
Is this possible and if so is there a way to do it with any number, X --> X0 ?

EDIT 1: sorry the first part of the question was super vague and I forgot to mention I’m trying to do this with logic gates.

I assume that the task is to compute $mul(10, a)= 10a$. You don't need to do multiplication. A single binary adder is enough since $$10a = 2^3a + 2a$$
meaning you add one-time left-shifted $a$ to 3-time left-shifted $a$.
For general multiplication $mul(x,y)$ please see this article.


Why is $\Omega(\log\log n)$ a lower bound for the depth of polynomial-width circuits computing parity? I'm working on an exercise from The Nature of Computation concerning polynomial-width circuits computing parity. In particular the exercise asks to sketch a proof that the depth of such a circuit has the lower bound $\Omega(\log\log n)$ where $n$ is the number of input variables.

There is quite a large amount of literature on the subject flying around the web and I have seen claims for lower bounds of $\Omega(\log^* n)$ as well as $Ω(\log n/\log\log n)$. However the proofs of these statements completely defeat me.

Does anybody see a simpler way to arrive at the desired result?

After some more thought here is my own attempt at a solution:

Assume for contradiction that the depth $d$ isn't $\Omega(\log \log n)$. Then it must be that

$\forall C,N:\exists n > N: d < C \lg \lg n$.
(Base 2 is an arbitrary choice for the logarithm.)

In particular if $C = \frac 1 2$ then

$\forall N: \exists n > N: 2^{2^{2d}} < n$.

At this point the Switching Lemma is required. The Switching Lemma is stated in The Nature of Computation as follows:

  Consider a circuit with $n$ inputs $x_1,...,x_n$ consisting of a layer of OR gates which feed into a single AND gate, where both types of gates have arbitrary fan-in. Now suppose that we randomly restrict this circuit as follows. For each variable $x_i$, with probability $1-n^{-\frac 1 2}$ we set $x_i$ randomly to true or false, and with probability $n^{-\frac 1 2}$ we leave it unset. For any constant $a$, if there are $O(n^a)$ OR gates, then with probability $1-o(n^{-a})$ the resulting circuit can be expressed as a layer of a constant number of AND gates, which feed into a single OR gate.

The Switching Lemma is symmetric with respect to AND and OR. So every time the Switching Lemma is applied the top two layers are switched and the second and third layer can then be merged into a single layer leaving a circuit of depth $d-1$. Thus after applying the Switching Lemma $d-2$ times the circuit has depth $2$ remaining.
Applying the Switching Lemma one last time no longer reduces the depth of the circuit but does leave a circuit that only depends on a constant number of inputs. (This follows from details of the proof of the Switching Lemma.)
At the same time the number of remaining unset variables is

$\sim n^{\frac{1}{2^d}} > (2^{2^{2d}})^{\frac{1}{2^d}} = 2^{\big(\frac{2}{\sqrt 2}\big)^{2d}} = 2^{2^d}$.

And since a previous result established that Parity isn't in $AC^0$, we know that $d$ and for that matter $2^{2^d}$ eventually exceeds any constant.
If we were then to set those variables on which the circuit still depends, we'd arrive at a constant circuit computing Parity with some variables still unset, which yields a contradiction.
Also note that the width remained polynomial since the Switching Lemma increases it by a constant factor $m$ each time it is applied. So the width is multiplied by

$m^{d-1} < m^{\frac{1}{2} \lg \lg n} = (\lg n)^{\frac{1}{2} \lg m} = poly(n)$.

Hence $d = \Omega(\log \log n)$.

I want to point out however that this proof is fairly out of my personal comfort zone. So I don't want to make any guarantees.


Construct regular expression for language How to construct regular expression for language L which contain all words in which there is a letter 'a' and the letter 'b'?
Of course, I understand that it's easy problem but I just start to learn this science? Please, any advices and hints.

Assuming that the input alphabet is $\Sigma = \{a,b\}$, the term $(a|b)^*a(a|b)^*b(a|b)^*$ describes all words where there is an $a$ followed by a $b$, and the term $(a|b)^*b(a|b)^*a(a|b)^*$ describes all words where there is a $b$ followed by an $a$. If we combine both, we get
$$
((a|b)^*a(a|b)^*b(a|b)^*)|((a|b)^*b(a|b)^*a(a|b)^*)
$$
which describes the set of all words in which at least one $a$ and one $b$ occurs.

Edit: An even shorter solution would be
$$
(a|b)^*(ab|ba)(a|b)^*.
$$
However, this solution requires the alphabet to contain exactly $a$ and $b$ whereas the first solution can easily be extended to arbitrary alphabets.


Grid Puzzle Split Algorithm I want to generate a random partition of an $N\times N$ grid into $N$ connected groups having $N$ tiles each. How would I do this?  Max grid size will be 10x10. Below is an example for a 5x5 grid.

A possible technique to generate random tilings is:

Represent all possible solutions as a Zero Suppressed BDD (see for example The Art of Computer Programming volume 4, chapter 7.1.4, or this page). Every way to place any piece on the board corresponds to a variable in the ZDD. The constraints are that every tile is covered exactly once, which can be done by making an "exactly once"-ZDD for every tile, and then intersecting all those ZDDs. An "exactly once"-ZDD is easy to make, it's a single chain of nodes where a constrained variable (a piece-placement that covers this tile) corresponds to a node with a HI branch to TOP and a LO branch to the next node, and an unconstrained variable has both LO and HI going to the next node.
For each node in the ZDD, count how many solutions it leads to. Runs in time proportional to the size of the ZDD (not the number of solutions) if memoization is used.
Then, top down, randomly choose between the two children of a node using the ratio of solution counts as threshold. That would uniformly choose a random solution from the space of solutions. Runs in time proportional to the number of variables (depth of the ZDD).


Given a set of 2D vectors, find the furthest reachable point Input: a set of 2D vectors $S=\{v_1,v_2,\dots,v_n\mid v_i\in \mathbb{Z}^2 \}$
  Question: name $P=\{\sum_{v_i\in S'}v_i\mid S'\subseteq S \}$
  for all subsets of $S$ (obviously $|P|=O(2^n)$). In
  words, $P$ is the set of all possible vectors we can form by adding
  vectors from $S$.
  What is the length of the longest vector in $P$?

An idea:
(An easy observation is that if all $v_i\in S$ are in one orthant (or quadrant?) we just have to add them. If the vectors are in on hyperplane this is not true.)
Start from an arbitrary vector $v_1\in S$, get the next one $v_2$ (either left or right) and add $V=v_1+v_2$. Generally, at each step $V=V+v_i$. Continue this while $|V|$ is increasing.

At some time we find $v_j$ such that $V=V+v_j$ shortens. Set $V=V-v_1+v_j$ and continue. The idea is to maintain a "window" where we add all the vectors inside. If the next vector (the one side of the window) does not add, remove the first one (the other side of hte window).

I know I am not clear enough but hope you get the idea.

Is this correct? Am not sure...
An other ideas/approaches?

(This, of course, can be generalized to any dimension $k$. I mentioned the 2D case because it is easy to visualize.)

I am looking for algorithms with polynomial time on $n=|S|$.

Related problem: lattice problems.

Let set $S$ be the basis of the lattice $L$. Then $L$ is defined as
$$L(S)=\{\sum_{i=1}^{n}a_i v_i \mid v_i\in S, a_i\in\mathbb{Z}\} $$

Our set $P$ is a special case if, instead of $a_i\in\mathbb{Z}$ we let $a_i\in \{0,1\}$.

Suppose you knew the direction $\hat{d}$ of a longest vector sum. Then finding a subset of vectors that should be included in the longest-vector sum is trivial:

Include $v$ when the dot product $v \cdot \hat{d} > 0$.
Exclude $v$ when $v \cdot \hat{d} < 0$.
There won't be a $v$ where $v \cdot \hat{d} = 0$, unless $v=0$, because that contradicts $\hat{d}$ pointing towards a longest vector sum.

Now consider what happens if we vary $\hat{d}$ away from the optimal direction to get $d^\prime$. The sum-along-directions stays constant... until we turn so much that one of the dot products $v \cdot d^\prime$ switches sign. That only happens when $d^\prime$ is perpendicular to a $v$.

Since we're working in 2-d, we can think in terms of angles instead of directions. We have a function $f(\theta)$ that adds up all vectors $v$ even-slightly-aligned with the angle $\theta$. And we know this function only changes values when $\theta$ is perpendicular to one of the vectors $v$. And we know there are at most $2n$ such critical angles.

Ah.

Algorithm

Make a list of all the critical angles where $f(\theta)$'s value changes due to $\theta$ being perpendicular to a $v$. Sort the list. Find a maximizing $\theta$ by sampling $f$ at the midpoint between each contiguous pair of critical points (remembering to include the midpoint where the angles wrap around). Use that $\theta$ to recover a best set of vectors.

By adjusting the total as vectors cross in and out of alignment, instead of recomputing it every time, the algorithm will run in time $O(n \log n)$ with the most expensive step being the sorting of the critical points.

Here's some quick and dirty pseudo-code. WARNING: THIS CODE WAS WRITTEN BY HAND WITHOUT BEING RUN OR TESTED. IT WILL CONTAIN BUGS.

import math

def dot(u, v):
    return u[0]*v[0] + u[1]*v[1]

def vec_sum(vecs):
    t = [0, 0]
    for v in vecs:
        t[0] += v[0]
        t[1] += v[1]
    return tuple(t)

def vectors_along(vec_set, angle):
    d = (math.cos(angle), math.sin(angle))
    return [v for v in vec_set if dot(d, v) > 0]

def transitions(vecs):
    # compute (critical-angle, vector, entering-vs-leaving) tuples
    results = [(t % (2*math.pi), v, b)
               for v in vecs
               for (t, b) in [(math.atan2(v[0], -v[1]), True),
                              (math.atan2(-v[0], v[1]), False)]]
    return sorted(results, key=lambda e: e[0])

def longest_subset(vecs):
    best_angle = None
    current_total_vec = None
    best_norm = 0
    for transition, vec, entering in transitions(vecs):
        # TODO: If two transitions are less than 0.00001 apart this fails
        # TODO: In particular, equal/opposite vectors cause equal transitions.
        angle = transition + 0.00001
        if current_total_vec is None:
            current_total_vec = vec_sum(vectors_along(vecs, angle))
        else:
            current_total_vec += vec * (1 if entering else -1)
        current_norm = dot(current_total_vec, current_total_vec)
        if current_norm > best_norm:
            best_norm = current_norm
            best_angle = angle
    return vectors_along(vecs, best_angle)

Higher Dimensions

This idea works quickly in 2d, but in 3d the boundaries that add/remove a vector from the along-direction sets are great circles instead of points. So everything gets more complicated and more expensive there and continues to get more complicated as you go to higher dimensions.


Zero-knowledge proof: Abstract example So I was reading about ZKP on wikipedia, the abstract example in summary goes like this:

  Peggy wants to prove to Victor that she knows the secret to a door inside a cave that connect A and B together (see diagram) without revealing the secret word to Victor.

  Peggy takes a random entry not know to Victor
  Victor shouts to Peggy to come out of path A or B (randomly choosen)
  and so it follows that she must know the secret word in order to come out of the path that Victor chooses without revealing to Victor the secret word. Victor builds confidences the more times this is done.

However, why is Victor not allowed to see which path Peggy chooses to enter from? As this does not reveal any extra information about what the secret word is.

Why can't Victor see which way she enters and asks her to demonstrate the 4 possibilities, that is:

Enter from A and exit from A
Enter from A and exit from B
Enter from B and exit from A
Enter from B and exit from B

I believe this is done to illustrate two things.

(i)
The small probability, that $P$eggy ($P$rover) might be lying. If she really does not know the magic word and $V$ictor ($V$erifier) sees her taking Path $A$, he would always ask her to come back via path $B$, thus the probability of $P$ succeeding when cheating is $0$.

However, $ZKP$s usually involve a small chance of $P$ succeeding while cheating, which is illustrated by $V$ not seeing the path $P$ takes to get to the magic door.

(ii) $V$ does not learn the secret. If $V$ stands at the crossroad of the paths $A$ and $B$, while $P$ walks to the magic door to say her magic word, it might be conceivable for $V$ to be able to hear $P$ saying her secret word. The only way to make sure that $V$ does not learn the magic word, is for him to wait outside of the cave, until $P$ has chosen a path.


Algorithms with O(sqrt(N)) SPACE complexity? Are there any known algorithms for formulated problems that require a SPACE complexity of O(sqrt(N))? I know that algorithms with that big-O time complexity exist.

$\sqrt{n}$ space is somewhat unusual; the most likely reason for such a complexity to emerge is as a result of a so-called meet in the middle scheme.

Two notable examples off the top of my head are the classical sieve of Eratosthenes and the baby-step giant-step algorithm for the discrete logarithm over a finite group.


Decomposing an Algorithm into Local Transformations/Perturbations Is it common to try to improve an algorithm by decomposing its action on a topological piece of data (e.g. graphs, geometric data) into a series of steps, each of which only makes a local change/perturbation in a confined neighborhood of the data while fixing the rest?

One benefit of this "breakdown" is improved conceptual understanding, and it also facilitates induction proofs (possibly based on invariants that are preserved by each step). Does this "decomposition" have a name in algorithm design? The idea might be similar to Divide and Conquer.

One might say that every individual step in an algorithm, like deleting an edge or labeling a vertex of a graph, is small enough to be considered "local", but I'm talking more about the "decomposition" in a higher-level description, like how truncating a polyhedron is local but sorting a list is not (even though at the lowest level, comparisons, insertions and deletions are local).

Examples of decomposing into local transformations

Augustin Cauchy's proof of his Rigidity Theorem relied on his "Arm Lemma" that opened up a convex planar chain by sequentially opening at each vertex. Although his proof was found to be wrong, he decomposed the opening algorithm into a series of "local opening moves", and he tried to prove that each local move preserved convexity of the chain. By induction, convexity would still hold after iterating over all vertices.
The pivot algorithm for self-avoiding walks (SAW) transforms a SAW into another by rotating or reflecting part of the original SAW. Markov Chain Monte Carlo can employ this transformation as a transition between SAW states to sample the space of SAWs.
As an application of the above, one technique of protein folding prediction is to force an amino acid chain into several known protein structures, choose the one with the lowest energy (due to intermolecular forces), then let the chosen structure "relax" into a configuation with lower energy. Relaxation involves the prescription of a few "local moves", where small parts of the chain can "wriggle around" (e.g. subchains pivoting around their ends), and random wriggles are allowed for a period of time to let the chain "stabilize". Modelling the chain as an SAW allows pivots to be used as a "wriggle".

there are several ways to measure this "local vs global" decomposition dichotomy of problems which does show up in a wide variety of CS contexts.

how many local minima there are versus a global minimum for optimization problems. if there are many local minima it is harder to find the global minimum. roughly this is also a measure of how effective greedy algorithms are on that problem.
algorithmic speedup due to parallelism. this metric is sensitive to both the problem and the algorithm chosen. for example the problem may not be very "decomposable", or a problem may be decomposable but it is not solved with a most efficient algorithm. for more decomposable problems, algorithmic speedup is nearly linear in increasing processors. for less decomposable problems, it is more an asymptotic sub-linear relationship.
communication overhead of parallel processing. the decomposability is known as "granularity". for problems that are not as granular, there is more communication required between separate parallel threads or processors. problems with very "fine" granularity ie not requiring much or any communication between processors are called embarrassingly parallel.
NC is the class of efficiently parallelizable algorithms. NC=?P is an open question. ie in short are all P-time algorithm efficiently parallelizable, or not?

one paper that does attempt to study these concepts more formally/systematically within the context of parallel computing is Landscape of parallel computing, the view from Berkeley. see eg "7+ dwarves" for the basic algorithmic patterns that seem to appear in practice and commentary on their decomposability wrt parallelism.

another influential researcher recently looking into the inherent limits/ceilings/gains of parallelism in CPU design (ie multicore) which relates to the general decomposability of everyday running code is Esmaeilzadeh.


Why do the swap step in Prim's algorithm for minimum spanning trees? I was watching the video lecture from MIT on Prim's algorithm for minimum spanning trees.
Why do we need to do the swap step for proving the theorem that if we choose a set of vertices  in minimum spanning tree of $G(V,E)$and let us call that $A$ such  $A\subset B$,  the edge with the least weight connecting $A$ to $V-A$ will always be in the minimum spanning tree ?  The professor has done the swap step at point 59:07 seconds in the video.

Charles Leiserson is presenting a proof to what is known as the blue rule in Tarjan's "Data Structures and Network Analysis" book.

The proof goes by contradiction, that is you assume that the edge $(u,v)$ is not in the MST $T$. Don't be confused by the board, it has to be $(u,v)\not \in T$. Let $(a,b)$ the edge that we swap with $(u,v)$. Bot edges are cut edges between $A$ and $A\setminus V$.
The tree $T'$ after the swap has weight
$$w(T')=w(T)+w((u,v))-w((a,b)).$$
As a consequence $w(T')<w(T)$, which is a contradiction and therefor the assumption $(u,v)\not\in T$ was wrong.

Notice that this proof uses the assumption that all edge weights are distinct, however it is easy to modify it for general edge weights.


Method to construct a finite state machine for a finite-size language L I need to define a method to construct a finite automata for a finite language L (part of my proof for something else).
My idea:

Create $|L|$ accepting states.
For each input string $s$ from $L$, create appropriate transitions from a starting state to unique accepting state of s.

I don't know how to formally describe this, or if this idea is even good.

Let $S$ be the list of all prefixes of words in $L$. Create a DFA with a state $q_s$ for each $s \in S$, and an additional sink state $q_\bot$. The starting state is $q_\epsilon$, and a state is accepting if it corresponds to a word in $L$. When at a non-sink state $q_s$, upon reading $\sigma$, move to $q_{s\sigma}$ if $s\sigma \in S$, and to $q_\bot$ otherwise. When at $q_\bot$, always stay there.

To show that this works, prove inductively that when reading a word $w$, if $w \in S$ then the DFA is at state $q_w$, and otherwise it's at state $q_\bot$.


How does DFS produce MST and All pairs shortest paths in unweighted graphs? I was reading Application of DFS from here where I came to a statement which I cannot really understand. Would anybody mind explaining this to me.

For an unweighted graph, DFS traversal of the graph produces the minimum spanning tree and all pair shortest path tree.

My doubt: Is there anything  "Minimum spanning tree" for unweighted graph. I mean after all it is unweighted so what is sense of MST here? And I completely don't understand how DFS produces all pair shortest path. Would anybody mind elaborating this a bit.

There are two claims here.

  For an unweighted graph, DFS traversal of the graph produces the minimum spanning tree.

This is true; in unweighted graphs, every spanning tree is minimal since they all have the same number of edges, $n-1$.

A nitpick I'd have is "the"; they should write "a minimum spanning tree".

  For an unweighted graph, DFS traversal of the graph produces the all pair shortest path tree.

This is false, it doesn't even produce a single-source shortest path tree. See here.

In general, an APSP tree may not even exist. There are $n(n-1)$ shortest paths to encode, and it would be quite the coincidence if they shared only $n-1$ edges. Which can happen, e.g. in acyclic graphs, but it is certainly not always true. I'll leave it to you to come up with a small counter example.


Why is there no permutation in Regexes? (Even if regular languages seem to be able to do this) The Problem

There is no easy way to get a permutation with a regex.

Permutation: Getting a word $$w=x_1…x_n$$ ("aabc") to another order, without changing number or kind of letters.
Regex: Regular expression.

For verification:

"Regex permutations without repetition" The answer creates JavaScript code instead of a regex, assuming this would be more simple.
"How to find all permutations of a given word in a given text" – The answer doesn't use regexes either.
"Regex to match all {1, 2, 3, 4} without repetition" –  The answer uses regexes, but it's neither adaptable nor simple.
This answer even claims: "A regular expression cannot do what you're asking for. It cannot generate permutations from a string".

The kind of solution I am searching for

It should have the form:

»aabc« (or anything else you could use a opening and closing parentheses)
(aabc)! (similar to (abc)? but with another symbol in the end)
[aabc]! (similar to [abc]+ but with another symbol in the end)

Advantages of these solutions

They are:

easy
adaptable
reusable

Why this should exist

Regexes are a way to describe a grammar of a regular language. They have the full power to be any kind of regular language.
Let's say, regular languages are powerful enough for permutations (proof below) – why is there no easy way to express this?

So my question is:

(Why) Is my proof wrong?
If it is right: Why is there no easy way to express permutations?

The proof

Regular expressions are one way to note the grammar of a regular language. They can describe any regular languages grammar.
Another way to describe any regular languages (that have a finite number of letters within their alphabet) grammar are non-deterministic Automatons (with a finite number of states).

Having a finite number of letters I can create this automaton: (Example. Formal: see below)

Grammar that accepts permutations of "abbc":

(sry for numbers on top, maybe someone knows how to make this part looking better)

s -> ah¹

s -> bh²

s -> ch³

h¹ -> bh¹¹

h¹ -> ch¹²

h² -> ah¹¹ (no typo! equivalence)

h² -> bh²²

h² -> ch²³

h³ -> ah¹²

h³ -> bh²³

h¹¹ -> bc

h¹¹ -> cb

h¹² -> bb

h²² -> ac

h²² -> ca

h²³ -> ab

h²³ -> ba

More formal: (using a finite-state-automaton but this could be made with grammar as well)

A word q (with finite length) to which any permutation should reach an accepting state.
X is the finite alphabet.
Set of states S contains any order of letters up to the length of q. (So the size of S is finite.) Plus one state of "any longer word".
state transition function d which takes a letter and moves on the state that corresponds to the now read part of the word.
F is a set of that states that are exact permutations of q.

So it is possible to create a finite-state automaton for accepting permutations of a given word.

Moving on with the proof

So I have proven that regular languages have the power to check for permutations, haven't I?

So why is there no approach to reach this with Regexes? It's a useful functionality.

The fundamental theorems of formal language theory are that regular expressions, regular grammars, deterministic finite automata (DFAs) and nondeterministic finite automata (NFAs) all describe the same kinds of languages: namely the regular languages. The fact that we can describe these languages in so many completely different ways suggests that there's something natural and important about these languages, in the same way that the equivalence of Turing machines, the lambda calculus and all kinds of other things suggests that the computable languages are natural and important. They're not just an artifact of whatever random decisions the original discoverer made.

Suppose we add a new rule for creating regular expressions: if $R$ is a regular expression, then $\pi(R)$ is a regular expression, and it matches every permutation of every string matched by $R$. So, for example, $L(\pi(abc)) = \{abc, acb, bac, bca, cab, cba\}$. The problem is that this breaks the fundamental equivalences described above.  $L\big(\pi((ab)^*))\big)$ is the language of strings that contain an equal number of $a$s and $b$s and this isn't a regular language. Compare this with, for example, adding a negation or reversal operator to regular expressions, which doesn't change the class of languages that are accepted.

So, to answer the title question, regular expressions can't do permutations and we don't add that ability because then regular expressions wouldn't match regular languages. Having said that, it's possible that "regular expressions with permutations" would also be an interesting class of languages with lots of different characterizations.


Turing machine with a countably infinite alphabet Suppose you have a Turing machine, but with a countably infinite alphabet.

How does such a Turing machine differ from an ordinary Turing machine, either in terms of computability or of complexity classes?

Do complexity classes for ordinary Turing machines hold up in such a model?

Edit: quick addendum - it seems obvious that the existence of a countably infinite alphabet leads to uncountably many state transition functions. I'm curious for the answer to both my original question, and to the restriction in which the only transitions allowed are recursive.

Your model accepts all possible languages over the countably infinite alphabet.

The first step is to convert the input word to a single symbol, in some one-to-one fashion. We can do that since $\bigcup_{n=0}^\infty \aleph_0^n = \aleph_0$. You can then encode your language in the transition function.

More generally, to get a non-trivial model you need to ensure that the description length of the machine is smaller in cardinality than the number of words over the alphabet.


What is the best algorithm known to learn the regular expression from a set of positive examples? I have a blackbox program that generates a set of strings. What is the best regular expression learner that I can use to learn (approximate) what the blackbox program uses as a generator? Note that I only have positive examples. (Checking whether a string is accepted or rejected is possible but rather costly). I see that algorithms like RPNI and L* requires both positive and negative examples.

I especially want to avoid over-generalization.

Update: I have been making do with using Sequitur to identify repeating patterns in single strings, and then lining up the resulting patterns to identify common repetitions. However, this feels really kludgy and I would like to improve it. Is this the best one can do? are there better ways?

I have wondered something similar and failed to find much in the way of satisfying answers in the literature.  Here is what I tentatively came up with.

It seems perhaps what we need is some kind of regularization.  If $\theta$ is a model (say, a regular expression), let $c(\theta)$ denote some measure of the complexity of the model (say, the size of the regular expression).  Also, let $\ell$ be a loss function, so that $\ell(\theta(x),y)$ denotes the loss incurred based on the model's prediction on string $x$, given that the ground-truth label is $y$.  Given a training set $(x_1,y_1),\dots,(x_n,y_n)$, define the total loss as

$$L(\theta) = \sum_i \ell(\theta(x_i),y_i) + \lambda c(\theta),$$

for some hyperparameter $\lambda>0$.

Then we could frame the learning task as finding a model $\theta$ that minimizes $L(\theta)$.

In your case, $\theta$ is a regexp, $c(\theta)$ is the length of the regexp, $x_i$ is a string, $\theta(x_i)$ is true or false according to whether $\theta$ matches $x_i$ or not, and you have only positive examples so all of your $y_i$'s are true.  You could also consider other models as well, such as a finite-state automaton (whose complexity is given by the number of states) or a neural network (e.g., a CNN or RNN).

The term $\lambda c(\theta)$ is a regularization term that penalizes model complexity, and thereby combats overfitting.  Basically, we're applying Occam's razor, that simpler explanations are more likely to be true.  If we omitted this term (or equivalently, set $\lambda=0$), we would indeed overfit and obtain poor generalization: e.g., we might learn the regexp $x_1|x_2|\cdots|x_n$.  If we over-regularize (and set $\lambda=+\infty$, say), then we underfit and might learn the regexp $.*$, which also is not good.  The hope is that the regularization term will find a happy medium between these two extremes.

So now the problem reduces to, how can we solve the optimization problem above?  Unfortunately, I don't know of any good ways to do this, for the case of regexps.

One approach would be to set an upper bound on the size of the regexp, i.e., choose some hyperparameter $s$, and limit consideration to regexps of length $\le s$; then try to find a regexp $\theta$ that minimizes $\sum_i \ell(\theta(x_i),y_i)$ subject to $c(\theta) \le s$.  (This formulation is closely connected to the formulation at the top of the question; the theory of Lagrange multipliers tells us that there is a one-to-one correspondence between $\lambda \leftrightarrow s$ that yields equivalent solutions to the optimization problems.)    Unfortunately, I don't know of any good algorithms for solving this optimization problem, i.e., for finding such a regexp $\theta$ that minimizes this loss.  Perhaps you could use a SAT solver to solve it; I don't know.

Another possibility is to choose a different model.  With CNNs or RNNs, it is easier to fix the size of the neural network architecture (thus implicitly fixing an upper bound on the complexity of the model), and then use gradient descent to find weights $\theta$ that minimize $\sum_i \ell(\theta(x_i),y_i)$.    Or, you could use a DFA instead of a regexp as your model, and then I think there are methods you could use to solve this optimization problem.  In particular, there are known algorithms for using a SAT solver to find whether there exists a DFA with $\le s$ states that matches every string in a given set of strings; and to minimize $\sum_i \ell(\theta(x_i),y_i)$, you culd plausibly repeatedly choose random subsets of $x_1,\dots,x_n$, find a DFA that matches every string in the subset, and check its total loss on the entire training set.

It seems hard to imagine that these are the best one can do, but I haven't been able to find better methods in the literature yet; this is the best I've been able to come up with so far.

Related: https://datascience.stackexchange.com/q/16115/8560.


Poly-time computability of inversion of poly-time real functions At pp. 7-8 of Ker-I Ko's Computational Complexity of Real Functions (1991), the following is stated for one dimensional cases:

  Let $INV_1$ be the operator that maps a one-to-one function $f:[0,1]\rightarrow [0,1]$ to its inverse function $f^{-1}$. Then $INV_1(f)$ is polynomial-time computable for all polynomial-time computable, one-to-one real functions $f$ on $[0,1]$.

And for two dimensional cases:

  Let $INV_2$ be the operator that maps a one-to-one function $f:[0,1]^2\rightarrow [0,1]^2$ to its inverse function $f^{-1}$. Then $P=NP$ implies that for all polynomial computable, one-to-one real functions $f$ on $[0,1]^2$, $INV_2(f)$ is polynomial-time computable, and this in turn implies $P=UP$.

How is the one-dimensional case derived? And how can the two-dimensional case be extended to n-dimensions?

In 1-dimensional case, the function has to be strictly-monotone.
Given $y_n$ do a binary search to find $x_n$.

If $\mathsf{P} = \mathsf{NP}$,
given $y_n$ we can guess $x_n$ and then verify that $f(x_n) = y_n$.
The dimension doesn't matter for this part.

For the other part, that is, if $INV_d$ is polytime then $\mathsf{P} = \mathsf{UP}$,
we can reduce it to $INV_2$ by noting that every 2-dimensional function
can be extended to a $d$-dimensional one by letting other coordinates map as identity.
So for $d'<d$,
$INV_d$ being polytime computable implies that $INV_{d'}$ is also polytime.
Therefore $INV_d$ being polytime implies that $INV_2$ is polytime and therefore $\mathsf{P}=\mathsf{UP}$.


Is $L = \{a^jb^ia^{j-i}\mid i,j \ge 0\ , j > i\}$ context-free? I'm exercising for an upcoming exam and I find this exercise:

  Say whether or not the language
  $$L = \{a^jb^ia^{j-i}\mid i,j \ge 0\ , j > i\}$$
  is a context-free language. Justify your answer.

I have already tried (using the pumping lemma for CFL) with two different words:
$$w1 = \  a^pb^{p-1}a$$
$$w2 = \  a^{2p}b^pa^p$$

but I'm stuck when the case is that $vwx$ (considering $uvwxy = w$) take letters from both the first group of $\bf{a}$ and the group of $\bf{b}$.
Have I chosen a wrong format for the word or am I simple missing some trivial condition?

You are trying the wrong way. It is context-free.

(added.) The structure of the language (to guide the grammar construction) is better seen by setting $k = j-i$, so $j=k+i$. Then the language becomes $\{ a^ka^ib^ia^k \mid i\ge 0, k>0 \}$.


Why does Akra-Bazzi need that toll-function g is bounded? Following up on vonbrand's answer I want to write a small document about stronger master theorems for our students, one of which is the Akra-Bazzi theorem. I have copied the theorem from their paper [1] and found -- besides a small notational confusion² -- the following problem.

The authors require (emphasis mine):

  $g(x)$ is defined for real values $x$, and is bounded, positive and nondecreasing function
  $\forall x \geq 0$

Here, $g$ is the toll function, that is the recurrence has the form

$\qquad\displaystyle T(n) = g(n) + \sum_{i=1}^k a_i T\bigl(\lfloor n b_i^{-1} \rfloor\bigr)$.

Now, at the end of their paper (p209) they give multiple examples for applying their result and they use functions in $\Omega(n)$ which are clearly not bounded.

From skimming the proof they mainly seem to require that integrals of the form

$\qquad\displaystyle \int_a^b \frac{g(x)}{x^{p+1}} dx$

have finite values. So, requiring $g$ to be bounded on every compact interval might be sufficient; I did not work through the proof in detail. Is it possible they mean that?

My question is: How should the Akra-Bazzi theorem be stated so that it is consistent with proof and examples?

On the solution of linear recurrence equations by M. Akra and L. Bazzi (1998)
They require $a_i \in R^{*+}$. Is this some notation I don't know, or a typo? I assume the intended meaning is $(0,\infty) \subseteq \mathbb{R}$.

Take a look at Tom Leighton's notes, referenced from the Wikipedia article.
His notes apparently have less typos then the original paper. The condition he demands of $g$ is having polynomial growth, which means that if you scale the argument by a constant, then the amount that the function scales is also bounded by a constant.


Call by value-result vs. call by reference? From my Googling, it appears that call by value-result is similar to call by reference in that it changes values in the caller, but it's different in that the changes don't take place until the callee exits, and that if the same variable is passed as more than one argument, it'll be treated as separate values in the callee instead of the same value as in call by reference.

Neither fact helps me explain why call by value-result produces different output than call by reference in the following code:

program Param (input, output);
var
  a, b: integer;
  procedure p (x, y : integer);
  begin
    x := x + 2 ;
    a := x * y ; (1)
    x := x + 1   (2)
  end;
begin
  a := 1 ;
  b := 2 ;
  p (a, b) ;
  writeln (a)
end.

Edit: here's my understanding of things:
The insight here is that in CBR, in line (1), both a and x point to the same thing, so assigning to a updates both a and x to x * y which is 6. But in CBVR, a and x point to different things, so line 1 only updates a to 6. x remains 3. Then CBR updates a right away so a ends up being 7 outside p. But CBVR updates a to whatever x is at the end of p, which is 4, so even though a was 6 in line (1), after p exits it's changed to 4.

EDIT:
An addendum: if you want to "simulate" call by value-result in Pascal (or in another language that supports only call by reference); you can use this trick:

procedure p(var x, y : Integer); // simulates call by value-result
var
  xtmp, ytmp : Integer;

  procedure p_hidden(var x, y : Integer); // nested "hidden" procedure
  begin
  ... YOUR ORIGINAL CODE HERE ...
  end;

begin
  xtmp := x; ytmp := y; // use auxiliary variables
  p_hidden(xtmp,ytmp);  // call by ref the nested procedure
  x := xtmp; y := ytmp; // copy values before return
end;

A simple method to "visualize" what is happening, is "inserting" the procedure in the point where it is called:

CALL BY REFERENCE:

a := 1; b := 2;
p(a, b)
//// procedure p (var x, y : integer);
//// x is the same as a, y is the same as b
//// begin
  a := a + 2 ;  // a = 3
  a := a * b ;  // a = 3 * 2 = 6
  a := a + 1    // a = a + 1 = 7
//// end;
writeln (a)     // prints 7

CALL BY VALUE-RESULT:

a := 1; b := 2;
p(a, b)
//// procedure p (valres x, y : integer); // by value result
//// x is the same as a, y is the same as b like in a by reference call
  xt := a; yt := b;  // xt and yt are two "new" variables
  //// begin
  xt := xt + 2 ;  // xt = 3
  a := xt * yt ;  // a = 3 * 2 = 6
  xt := xt + 1    // xt = 3 + 1 = 4
//// end;
//// the values of xt and yt are copied back to a and b (x and y) before return
  a := xt;       // a = 4
  b := yt;       // b = 2
writeln (a)      // prints 4


Terminology about the word Function : General vs Computable I've seen two different concepts referred to by the term "function":

A small part of a program specified by the composition of constants and other functions as paramaters, such as the "functions" in Lisp
A set of tuples, as referred to in formal logic, which is not necessarily computable

The first concept is very fundamental to software design.  The second concept is very fundamental to formal reasoning.  However, a task I've been working on is analyzing software with formal logic, so the conflation of the terms is a bother.

Is there any agreed upon, concise, unambiguous terminology to distinguish these two ideas?  I can think of several verbose terms, such as "Computable Function" and "General Function", but imagine having to type that out with the specification of every modular component.

Any references, ideas, or supported opinions are appreciated, thanks.

A (mathematical) function $f$ with domain $X$ and range $Y$ is a set of pairs $(x,y) \in X \times Y$ such that for each $x \in X$ there is exactly one pair of the form $(x,y)$; we say that $f(x) = y$.

A computable function $f$ is a function computed by some program.

A function in a programming language is an entity whose exact definition depends on the programming language. For example, in Pascal a function is a subroutine returning a value, in C a function is any subroutine, and in functional languages a function is either a declared subroutine or an "anonymous" function arising as some lambda expression.

Summarizing, the meaning of function depends on context. In a mathematical context or in some parts of theoretical computer science (say, complexity theory), a function is an arbitrary mapping; this is also probably the case in programming language theory, but I'm not qualified to say. In software engineering the meaning might depend on context. Computable functions (also known as recursive functions) are always called that.


Can we get any subsequence of size $\ge \lfloor \frac{n}{2} \rfloor$ in a sorted order from a sequence in linear time? Given a sequence $A$ of $N$ distinct integers, does there exist a strategy to get at least one subsequence with size $\geq \lfloor \frac{N}{2} \rfloor$ of the sequence in sorted order in $O(n)$ time?
For example, let's say that $A = [4, 11, 6, 2, 9, 7]$. Then, one of the required sequences can be $[2, 7, 11]$, which is the sorted version of the subsequence $[11, 2, 7]$. Your strategy can give any such subsequence in a sorted order.
Yes, I think that it's 99.99% impossible. But, I don't know for sure. Can anyone show that there cannot exist such a strategy or prove otherwise?

It's impossible (assuming you only use comparisons). First, we augment all elements with indices: $a[i] \to (a[i], i)$. We'll need this when we'll remove the sequence from the array in linear time.
Consider the following sorting algorithm:
def sort(a):
    subseq = get_sorted_subseq(a)  # Your function. Assume takes O(n) time
    b = a.exclude(subseq)          # Since we know indices, takes O(n) time
    return merge(subseq, sort(b)). # Takes O(n) time (see merge sort) + recursive call of size <= n/2

In result, the running time is $O(n + \frac n2 + \frac n4 + ...) = O(n)$, which violates a well-known lower bound for sorting.


Karp hardness of a vector system allocation Given an undirected graph $G(V,E)$, a vector system is a set $S$ of ordered pair (intuitively called vector) $(u,v)$ (we shall call $u$ the initial point, and $v$ the terminal point) that satisfies the following criteria:

For each vector $(u,v)\in S$, we have that $uv \in E(G)$. So, each vector must be an orientation of an edge
No two vectors share the same initial point. Formally, for every two vectors $(u,v),(w,x)\in S$, we have that $u\neq w$
An initial point of a vector cannot be the terminal point of other vector. Formally, for every two vectors $(u,v),(w,x)\in S$, we have that $v\neq w$

Now, our problem is defined as follows:

  Input: An undirected graph $G(V, E)$ and a natural number $k$

  Output: YES if it is possible to allocate a vector system of size $k$ in $G$, otherwise NO

What is the hardness of this problem?

Omitting the second requirement (allowing vectors to share initial points):

This becomes $\mathrm{NP}$-complete since it is exactly $\mathrm{MAX}$-$\mathrm{CUT}$.

Consider the set of all terminal points of the vector system. Exclude all the edges between any two vertices of this set. All the edges inwards constitute the cut.

Putting back the second requirement (vectors required not to share inital points)

This is $\mathrm{NP}$-complete by a reduction from $\mathrm{DOMINATING\ SET}$.

Reverse the direction of the vector system.

We see that now the set of initial points (originally terminal points) are dominating the set of terminal points (originally initial points). Note that these two sets are disjoint.

So, given an instance $(G,k)$ of $\mathrm{DOMINATING\ SET}$. Our reduction just produces $(G,n-k)$ where $n=|V(G)|$ as an instance of the vector allocation system.

If there is a dominating set of size $k$, then for each of the dominated $n-k$ vertices, we can assign for it a dominating vertex among $k$ dominating vertices. The direction is from the dominating vertex to the dominated vertex (this is the reversed direction). We have formed a (reversed) vector system of size $n-k$.

Conversely, if there exists a vector system of size $n-k$. The set of terminal points (originally initial points) are of size exactly $n-k$. Take the remaining $k$ vertices as a dominating set. This shows that the original instance of $\mathrm{DOMINATING\ SET}$ is a YES instance.


Regex for bit strings with at least two zeros but no consecutive zeros This is what I have:

$$(1^*011^*011^*)^*\,.$$

But I don't think this is accounting for an odd number of zeros, like "$10101010101111$". I think I have the right expression that satisfies no 2 consecutive zeros and even number of zeros. Can someone help? Thanks!

The shortest regex I came up with is: 1*01+0(1+0?)*

Start with arbitrary amount of 1s (1*)
Exactly one 0 (0)
One or more 1s (1+)
Another 0: (0)
Arbitrarily often ((...)*):

One or more 1s (1+)
At most one 0 (0?)


Find number of candidate keys given non-trivial functional dependency X->Y, where X is some set of attributes and Y is some prime attribute In a relation R, if X is some set of attributes and Y is some prime attribute such that X uniquely determines Y is a non-trivial FD. Then is it true that R has at least two candidate keys?

For instance, take the relation schema R(Class_Id, Course_Number, Instructor_Name, Text). {Class_Id, Course_number} is a candidate key. This makes Course_Number a prime attribute.
The following functional dependency holds on R:

{Instructor_Name, Text} uniquely determines {Course_Number}

How to determine if another candidate key exist or not?

EDIT: A Relational table
Class_Id | Course_Number | Instructor_Name | Text

    2             b            Jodi           E
    3             c            Jack           N
    2             c            Jack           N
    4             b            Peny           E
    5             e            Jodi           N

X -> Y non-trivial means that X does not include Y. Since Y is a prime attribute, we know that there is at least a candidate key that include it. Let's call this key K1.
Now we have two cases: either X is a superkey, or not.
If X is a superkey, then it contains at least a candidate key K. We can easily convince that K ≠ K1, since it differ from K1 by at least one attribute.
So in this case in the relation there are at least two different candidate keys, K and K1.
Now suppose that X is not a superkey, and consider X ∪ (K1 - {Y}). This is surely a superkey, since it determines K1, which determines all the attributes. This superkey does not contains Y, but contains at least a candidate key K', so again we have at least two different candidate keys, K' and K1.
Edit
Let's see in a more formal way why X ∪ (K1 - {Y}) is a superkey.
A superkey is a set of attributes that determines all the attributes of the relation, and we can check this property by computing its closure and see if it contains all the attributes of the relation (let's call them T).
Since K1 is a candidate key, we know that:
(1) K1 -> T

we also know:
(2) X -> Y
(3) Y ∈ K1

So we can calculate the closure of X ∪ (K1 - {Y}) in this way:
(4) (X ∪ (K1 - {Y}))+ = X ∪ (K1 - {Y})
(5) (X ∪ (K1 - {Y}))+ = X ∪ (K1 - {Y}) ∪ Y = X ∪ K1  by (4) and (2)
(6) (X ∪ (K1 - {Y}))+ = X ∪ K1 ∪ T = T by (5) and (1)

so we can conclude that (X ∪ (K1 - {Y}))+ contains T, and, consequently, that (X ∪ (K1 - {Y})) is a superkey.


What does $n^{O(1)}$ mean? I read an example that said explain what "$f(n)$ is $n^{O(1)}$" means.

I can't interpret the $n^{O(1)}$ syntax. I know what Big $O$ notation is, its just that this example looks odd to me.

It's short-hand for "$n^{f(n)}$ for some function $f(n)\in O(1)$".  In other words, the function is at most $n^c$ for some constant $c$.

You can see this by directly substituting the definition of $O(1)$ in the expression.  $g(n)=n^{O(1)}$ if there's constant $c$ such that, for all large enough $n$, $f(n)\leq n^{c\cdot 1} = n^c$.

This includes all polynomially-bounded functions.  For example, for $n>0$,
$$n^2+3n = n^2(1+\tfrac3n) = n^{2+\log(1+3/n)/\log n} = n^{O(1)}\,,$$
since, for $n\geq 3$, we have $1<1+\tfrac3n\leq 2$ and $\log n>1$, so the exponent is between $2+\log 2$ and $2$.


Every state in subset automaton is reachable I'm currently trying to prove that following NFA $\mathcal{M}_0 = (Q, \Sigma, \delta_0,0,\{0\})$ (see picture below) has an exponentially larger DFA $\mathcal{M}$ accepting the same language.

$\mathcal{M} = (2^Q,\Sigma,\delta,\{0\},F)$ is constructed using the subset/powerset algorithm and I'd like to show that $\mathcal{M}$ is minimal (i.e. $F = \{q \in 2^Q \mid 0 \in q\}$).

My problem is to show that every state $q \in 2^Q$ is reachable. I'm trying to prove this by induction over $|q|$.

It is clear for $|q| = 0$ since $\delta(\{0\},b) = \emptyset$.
For $|q| = 1$ it follows directly from the NFA: $\Delta(\{0\},a^i) = \{i\}$ for $1 \leq i \leq n-2$.

The problem starts in the inductive step. Let $q = \{i_1,\dots,i_k\}$ with $0 \leq i_1 < i_2 < \cdots < i_k \leq n-2$.

For states with $i_1 = 0, i_k=n-2$ (using the induction hypothesis) or $i_1 = 0, i_2=1$ (using the first case mentioned) it is easy to show but in other cases I have no clue how to do it.

EDIT: Beware that the dotted states also have a $b$ loop to themselves (!), i.e. $\delta_0(i,b)=\{0,i\}$ for $1 \leq i \leq n-3$.

Any regular language is accepted by arbitrarily large automata with no inaccessible states. Let $M = (Q, \Sigma, \delta, q_0, F)$ be an automaton with no inaccessible states.  For any natural number $n$, we can write $[n]=\{0, \dots, n-1\}$ and define a new automaton

$$M_n = (Q\times [n], \Sigma, \delta_n, (q_0,0), F\times [n])\,,$$

where $\delta_n((q,i),\sigma) = (\delta(q,\sigma), i+1\bmod n)$ for any $q\in Q$, $i\in[n]$, $\sigma\in\Sigma$.

The effect is that each state counts modulo $n$ the number of characters that have been seen so far, but this has no effect on the behaviour of the automaton, other than making the state space bigger.

The automaton $M_n$ might have inaccessible states, so delete them. But note that, after reading any word of length $0\leq \ell<n$, the automaton is in some state of the form $(q,\ell)$, so at least $n$ states are accessible.  Setting $n = 2^{|Q|}$ gives you an exponentially bigger automaton, but why stop there? :-)

Thanks to @holf for the elegant fix to the problem of the disconnected state space.


Contiguous Subarray Max I'm trying to solve the contiguous subarray problem on CodeSignal & I came up with the following solution which is based off of Kadane's Algorithm. My implementation passed the given test data set however upon submission, it failed. There's no reason given on CodeSignal & I can't look at it since I just started doing it & have less coins.
I can't figure out why my solution is failing but the solution based on online pseudo code works, even though my solution passed the preliminary tests. I think it might have to do with integer overflow or some other reason that's why I've come here to seek help from experts.
My implementation:
 public int findConsecutiveSubarray(int nums[]) {
    int currentSum = 0;
    int max =Integer.MIN_VALUE;;

    int i=0;
    while(i < nums.length) {
        currentSum += nums[i];

        if(max < currentSum)
            max = currentSum;

        if(max < nums[i]) {
            max = nums[i];
            currentSum = nums[i];
        }

        i++;
    }
    System.out.println("maxSum : "+ max);
    return max;
}

Solution based on online:
int arrayMaxConsecutiveSum2(int[] nums) {
        int currentMax = 0;
        int globalMax = 0;

        globalMax = currentMax = nums[0];

        for(int i=1; i<nums.length; i++) {
            currentMax = Math.max(nums[i], currentMax + nums[i]);
            globalMax = Math.max(globalMax, currentMax);
        }

    return globalMax;
}

The issue is that you might not enter the second "if" when the current sum is smaller than nums[i].
Imagine, e.g., that at the beginning of the iteration you have  currentSum=-5, max=100, nums[i]=10.
At the end of the iteration you have currentSum=5 and max=100, yet the desired state is currentSum=10, max=100.
A corresponding instance where your algorithm fails is: 100, -105, 10, 95.
To fix this, the condition of the second "if" should be currentSum < nums[i].
Notice that, once you change this condition, you'll also have to revise other parts of your code accordingly: you can no longer unconditionally assign max to nums[i] in the body of the second "if" statement. This can be easily fixed by removing that assignment and swapping the order of your two ifs.
[...]
        if(currentSum < nums[i])
            currentSum = nums[i];

        if(max < currentSum)
            max = currentSum;
[...]


How to Compute the Fixed Point on a DataFlow Lattice Wondering the general overview of how to compute the fixed point on a program's dataflow lattice.

A fixed point of a function $f(x)$ is one where the output of the function equals the input, so:

$$f(x) = x$$

Given $f$ is an order preserving (monotonic) function
$x ⊑ y \Rightarrow f(x) ⊑ f(y)$, in this presentation, they have $x_\bot$ be the least fixed point of $f: L \to L$, so $f(x_\bot) = x_\bot$, where $L$ is a program lattice. Then they say:

  Now, let $x_0 = \bot$ [the end of the lattice] and $x_i = f(x_{i−1})$

  By induction, $x_i ⊑ x_\bot$.
  Also, the chain $x_i$ is an ascending chain.
  If $L$ has no infinite ascending chains, sooner or later $x_i = x_{i+1} = x_\bot$

I'm wondering what this means. What happens algorithmically (the high-level steps) when we are iterating toward a fixed point. In the presentation they say "Do computation by simulating execution of program until reach fixed point".

This doc says "In this situation [data flow], the mathematical function is the flow function [so $f$], and the fixed point is a tuple of the dataflow analysis values at each point in the program (up to and including the loop)". They define flow function as a map from the dataflow info immediately before to after the program point / instruction.

So essentially, we divide the program into nodes or points where each point is an instruction/statement. We create a function showing the change of values from before and after each point (in and out, the flow function). We then iterate on the values somehow, that's where I'm unclear about. Wondering if we are iterating through the program points, calling $f$ for each point, or if we stay at one point and iterate on it with some sort of input until we reach a fixed point. Then wondering how that works. Not sure how the iteration works, or how $x_\bot$ works (if its part of some subset of the program points $L$ for each point (kind of like a neighborhood) or what.

You don't compute the least fixpoint of a lattice; you compute the least fixpoint of a function $f$.  The standard method is to use a method called chaotic iteration, which is exactly the iterative algorithm described in your quote: set $x_0 := \bot$, $x_1 := f(x_0)$, $x_2 := f(x_1)$, etc., and keep iterating until you reach $i$ such that $x_i = x_{i+1}$; the resulting $x_i$ is the least fixpoint of $f$.

In some cases it is possible to speed this up for a particular function $f$, but don't worry about this at this stage.

It's possible to view the process above as in some sense simulating the execution of the program, but I find it likely that this viewpoint is going to lead to confusion, so I'm not sure I would recommend trying to understand it that way.  Iteratively evaluating $f$ is not the same as iterating through the program points of the program.

Talk about splitting the program up is largely irrelevant to your question about how to compute a least fixpoint.  There are two steps: convert the program to a function $f$; find the least fixpoint of $f$.  The business about dividing up the program is relevant to how you convert the program to $f$, but not relevant to how you compute the fixpoint of $f$ (at least, not at the basic level).