How can finite sets be represented as a type? Manually self-migrated from stack overflow.

A set of objects of a type T is often represented using its indicator function (set T = T -> bool).  However, for practical purposes this representation isn't necessarily very useful.  For instance, if T is the natural numbers, there's no way to print0 out all of the numbers in a given set, since it would require checking all of the natural numbers, which is an infinite task.1

However, say I'm only interested in finite sets, and I want to be able to print out all the members of a set.  (Obviously I also want to easily test membership, construct unions and intersections, etc.)  Is there a good way to do this using inductive types?

Edit:
To clarify, I need the set type to encapsulate all of the set invariants (no duplicates, unordered, etc) so that all members of that type automatically satisfy those properties.  The indicator function representation does this, but is impractical to use as a data structure for the above reasons.  Using sorted lists (set T = list T) is possible, but not all lists are valid (sorted without duplicates) representation of a set—I need the type system to enforce that all members of set T are actually sets.

0: Let's assume we're using some monad to encapsulate printing, etc.
1: In exchange, we do of course get the ability to represent infinite sets.

If you want a type system for finite sets that enforces the validity and unicity of all representations, then your type system must be able to model equality of elements. (Informal proof: insert x (insert y empty) has differently-shaped representations depending on whether x and y are equal.) This is impossible with algebraic datatypes alone, unless you're willing to restrict the domain of the sets to sufficiently simple sets (for example, you can use a bit vector to represent a finite subset of a finite set; you can use finite lists of positive integers to get a unique representation of finite sets of positive integers: store $\{x_1, \ldots, x_n\}$ as $[x_1, x_2-x_1, \ldots, x_n-x_{n-1}]$ where the $x_i$ are numbered in increasing order).

A sophisticated type system can of course represent anything you want. Basically, you need:

dependent types, so that the type definition can contain equality assertions;
induction, to build a data structure containing any number of elements.

For example, the calculus of inductive constructions admits representations of finite sets. You can look for examples in the Coq library and contributions.

If you're willing to relinquish either the requirement for unicity or for validity, you can make do with algebraic datatypes. Representing finite sets as finite lists yields a set representation where every datum is valid, but each set admits multiple representation ($n!$ representations for an $n$-element set if the elements have unique representations). Something like a sorted list or search tree can give a unique representation (assuming that the elements have a unique representation). For search trees, to have representation unicity, you need a balancing function that guarantees unicity (which may impact performance).

In the type systems found in typical programming languages, it is typical to implement sets with an underlying representation that may or may not be valid. The type system thus does not enforce that all representations are valid. It does, however, help to maintain this property: a finite set can be implemented as an abstract type. The type is implemented as a module which is sealed, ensuring that all elements of the finite set type have been built from constructors provided by the module. The correctness of the finite set modle code ensures the validity of set representations, and the type system helps by maintaining this invariant.


Why can the alphabet be represented in numbers in base 256 This is in context of hashing of strings. I'm not sure why a string like, CS, could be represented as CS = 'c'*256 + 's'

Does anyone know about this?

A number in base ten is just a sequence of digits 0–9, with the string $d_n\dots d_2 d_1 d_0$ representing the number $10^nd_n + \dots + 10^2d_2 + 10^1d_1 + 10^0d_0$. Similarly, a character in an 8-bit character set can be considered to be a "digit" between 0 and 255, so a sequence $d_n\dots d_1d_0$ of these "digits" represents the number $256^nd_n + \dots + 256^2d_2 + 256^1d_1 + 256^0d_0$.

Another way to see this is to write the number out in binary.  For example, a 32-bit binary number can be considered as having 32 binary digits (bits) or 4 256-ary digits by collecting the bits into groups of 8.  In the same way, an 8-digit decimal number can be considered as a 4-digit number in base-100.  For example

$$38572856$$

can be considered as

$$38\,57\,28\,56 = 38\times 100^3 + 57\times 100^2 + 28\times 100^1 + 56\times 100^0 = 38572856\,.$$

For the Latin alphabet, base 26 would be the most natural representation, since the letters can be treated as 26 different "digits".  You may also have heard of Base-64 encoding which uses the 64 characters A...Za...z0...9+/ in that order as 64 "digits".  The advantage there is that all 64 of the characters can easily be included in a text file and, by using Base-64, you can code three bytes of binary data (24 bits) into four characters (4x6 bits), which is a acceptably inefficient.


Decide whether a DFA accepts at least two strings Is the following language decidable? $$L = \{A : \text{A is a DFA and } |L(A)| \ge 2\}$$

First remove dead states(those which do not lead to accept states). Then run depth first search. If all accepts states are not reachable or there is a single path leading to an accept state then REJECT. If there are two different paths leading to an accept state (or accept states) then ACCEPT. If there is a cycle including a state from which an accept is reachable also ACCEPT.


Is there a general pattern/structure/format to most (if not all) computer functions? First time posting.

I know this is a very generalized question, sorry for that, I don't know how to more appropriately word this.

I've noticed a tread, a pattern in methods, it seems in almost all methods, for example, in Java (haven't programmed much in other languages although I would imagine it's the same) the method seems to share a general pattern in their creations.

It's something on the order of:
 - Create local variables to store/copy things from instance variables
 - Create a loop to iterate through things
 - Create a series of if statements/conditions, possibly accessing premade methods
 - Check for any sort of possible exceptions/problems along the way
 - Return the desired output of the operations from the above

And all the other aspects such as polymorphism, recursion, interfaces, inheritance seem to be conceptual features/additions to the codes performance and functionality

Is this true? I know that each method is unique and a special combination of the above is probably require. Generally speaking do most methods follow a pattern?
Is there a better way of writing out the above list, in a more formal way?

Thank you, I appreciate you taking the time to read this post.

A method is just a precise sequence of instructions (in the ordinary English-language sense of the word) of how to perform some specific task. It's certainly true that many tasks – and I mean this in a completely general sense, not just computer programs but things like recipes, travelling to work, repairing a bicycle, building a house – follow a general pattern of "get things ready, do the main part of the work, then tidy up." However, there's no reason that all tasks must follow this pattern, and certainly not at the level you suggest of looping, then doing conditionals, then returning something.  In general, methods do whatever it is that they need to do to accomplish the specific task at hand: ultimately, everything really is its own unique snowflake.

Having said that, we should note that we could, in principle, force everything to have a particular pattern. The CPU itself is essentially a loop of "read the next instruction, obey that instruction" where a particular effect of obeying an instruction might be to change what the "next instruction" will be – that would be a jump or goto. So, in principle, we could write every program in this style. However, people find this kind of program extremely difficult to write, understand and debug so, in practice, we use higher-level languages, and use compilers and/or interpreters to translate them into terms that the CPU understands.


Why Shannon's Entropy is said to be a measure of information? I got a bit of how Shannon explained to find the number of bits required to represent a message and Shannon's Entropy.But it's natural to know that to code alphabet letters you need 5 bits of information starting from 0000 to 11001.

Is that because at his time no one knew how to represent bits in information that Shannon came with looking at the unpredictability of the message to determine the number of bits needed to represent a message?

It's really getting confusing why would one need to consider terms like entropy,probability etc as said in Coding Theory to get the number of bits to represent a message when we already know that to represent 32 letters we need 5 bits.

Is there really any other reason behind why did Shannon came with these terms in the field of communication other than finding the number of bits required to represent a message?

Yes, of course. Shannon's work was on the transmission of information over discrete, noisy channels. It centred on the trade-off between bandwidth and signal-to-noise ratio, and, grossly over-simplifying it, in particular what the maximum transmission rates could be with and without the presence of noise induced error and how to construct suitable codes. This involves coding theory1 and probability theory, which is where some of things that have you confused come from.

It is also incorrect that you need 5 bits to encode letters. If we have a known frequency distribution of the letters, we can encode the more frequent ones with fewer bits, and less frequent ones with more, which will give much shorter messages that the simple 5-bits-for-everything coding. For example, the entropy given by the usual distribution of English is 4.219 bits per symbol, so we can encode common symbols like 'e' with perhaps 1 bit, and uncommon symbols like 'q' with 5 or 6 bits, an on average we use less than 5 bits per symbol. If we use more cunning coding schemes, for example ones that take into account digram and trigram frequencies, we can get this average down to a little over 2 bits per symbol by using short codes for common two and three symbol groups.

Also, notably, your title is backwards, Shannon's Entropy is a measure of information, not the other way around. It is not the only one possible, however Shannon argues that it is the most natural and intuitive.

The full extent of Shannon's (seminal) work on information theory is too large to encompass in this format, but there is plenty of further reading. The wikipedia entry on information theory is reasonably approachable, and the page on coding theory also adds something. For the real stuff of course, you can just read the paper in which Shannon invented information theory essentially out of whole cloth; "A Mathematical Theory of Communication"2.

Footnotes

This is not not suggest that Shannon was applying coding theory, he was inventing new ideas that would become large parts of coding theory.
Claude E. Shannon, "A Mathematical Theory of Communication", The Bell System Technical Journal, 27:379-423,623-656, 1948.


Machine Learning vs System Identification? Could anyone explain to me the differences & similarities between machine learning and system identifications? Are these just two names of the same thing? In this page, they say:

  Machine learning and system identification communities are faced with similar problems where one needs to construct a model from limited or noisy observations.

I've also read the early chapters of the famous book Pattern Recognition and Machine Learning by Christopher M. Bishop. So far, my conclusion is that the problem that system identification is trying to solve is a subset of what machine learning is trying to solve.

System identification is the science of constructing dynamical models from observed data. There are two main approaches: Prediction Error Identification (PEI) and Subspace Identification (SID). Both of them are delivering a so called parametric model, that is to say, a model of a fixed structure. Usually it is the case that the user selects the structure of the underlying system (especially in the PEI methods) or at least the order of the system (in both methods). Even though it is not necessary, a low order system is sought (that is to say, the number of the basis coefficients is relatively small) because it is often used for control purposes, so we have to keep it as simple as possible to avoid computational issues etc. This model can be used to make predictions about the future behaviour of the system given some inputs.

On the other hand, machine learning (ML) has two main branches, classification  and regression algorithms. The latter ones are also used for prediction purposes. Two of the most famous approaches in machine learning are Support Vector Machines (SVM) and Gaussian processes (GP). The main difference with the system identification techniques is that the ML techniques are delivering a non-parametric model. The latter means that the prediction for a new input is given as a function of the data points used for the "training" (learning, identification) of the model. Therefore, if we used N=1000 data points for the training, then the prediction would be expressed as a function of these data points. ML methods are more flexible since they don't require any structure selection from the user, but they face other limitations (e.g. computational effort).

Until recently the ML and the system identification techniques were developing independently. But in the latter years there is a great effort to establish a common ground (e.g. see the paper "Four encounters with system identification" from Ljung)


Process synchronization problem The atomic fetch-and-set x,y instruction unconditionally sets the memory location x to 1 and fetches the old value of x in y without allowing any intervening access to the memory location x. Consider the following implementation of P and V functions on a binary semaphore S.

   void P (binary_semaphore *s) {
        unsigned y;
        unsigned *x = &(s->value);
        do {
            fetch-and-set x, y;
        } while (y);
    }

    void V (binary_semaphore *s) {
        S->value = 0;
    }

Which one of the following is true?

The implementation may not work if context switching is disabled in P()
Instead of using fetch-and–set, a pair of normal load/store can be used
The implementation of V is wrong
The code does not implement a binary semaphore

Option 1 is correct. I am unable to understand the reason for it. Please explain.

Explanations for the truth-value of each assertion:

(1) is true because any process running P() after another process has already run P() will see y==1 and so be stuck in the do-loop.  If context-switching is disabled inside P() [and we assume re-enabled on exit from P()], then the process stuck in the do-loop will be the ONLY running process, so no other process can release that one from the do-loop by calling V().

(2) is false because a context-switch may occur between the load of y and the store to x.  Consider processes P1, P2, both calling P().  The following sequence is possible: (a) P1 loads y, which happens to be 0; (b) The context switches to P2; (c) P2 loads y -which is still 0-, then sets x to 1 and exits the loop (because for it y==0) and enters the critical section; (d) The context switches back to P1, which now sets x to 1 -but still sees its version of y as 0, so it exits the loop and enters the critical section.  Verdict: Mutual-exclusion is NOT enforced!

(3) The implementation of V() is not wrong, given the implementation of P().  Execution of V() WILL set 'value' to 0, and by the atomicity property this must occur either entirely before or entirely after any test_and_set.  If before, then test_and_set will set y to 0 immediately; if after, the same thing will happen on the next do-loop iteration.

(4) [because of 2 & 3].


Can loops like this one be algorithmically transformed into multiplication Are there known techniques for converting a loop like the following to an if and a multiplication?

while (x < 0) {
    x += 60;
}

It seems clear that this could be replaced with something like the following

if (x < 0) {
    x += f(x, 60);
}

where f contains no loops, presumably using multiplication. This would have the benefit of being faster for sufficiently large negative numbers.

Is there a well understood algorithm for finding f for an arbitrary loop of this form?

The name for this optimization seems to be induction variable elimination, there are some nice slides explaining the idea here.


Minimum cut versus sparsest cut? My question is that I'm trying to find the sparsest cut in a connected, undirected graph (all weights are = 1). Basically, I am looking trying to find the smallest cut (i.e., number of edges cut since all weights = 1) while maximizing the number of vertices in the resulting subgraph. How do I approach this problem with flow?

The sparsest cut problem, in which one attempts to minimize the ratio between the number of edges cut to the size of the smaller size of the bipartition, is NP-complete. The "last word" on this problem theoretically speaking is the $O(\sqrt{\log n})$ algorithm by Arora, Rao and Vazirani (affectionately knows as ARV), which has found many uses in the area of approximation algorithms.

You might want to start with the simpler algorithm of Leighton and Rao, which gives an $O(\log n)$ approximation and has a relation to flows. See for example these lecture notes, or many others.


Is the following fuction computable? I'm trying to show that $K_1 \le_1 K$ where $K$ is the diagonal halting set $\{x : \varphi_x(x) \downarrow\}$ and $K_1=\{x: \exists y \,\, \varphi_x(y) \downarrow\}$, then I defined the function
$$\psi(x, y)= \begin{cases} 0 \, \, if \, \, x \in K_1 \\ \uparrow \, if \, x \notin K_1\end{cases}$$
By the Parameter Theorem there is a one to one computable function $f$ such that $\varphi_{f(x)}(y) = \psi(x, y)$ and it's easy to show that $x \in K_1 \leftrightarrow f(x) \in K$. All above works if and only if $\psi$ is partial computable, I think that function is partial computable because $K_1$ is r.e. Is this true? I mean, Can I always define a function computable by
$$\psi_A(x, y)= \begin{cases} 0 \, \, if \, \, x \in A \\ \uparrow \, if \, x \notin A\end{cases}$$
for each r.e. set $A$?

You're using the terminology of recursion theory. Let me rephrase the argument in terms of computer programs.

$K$ is the set of all programs $x$ which halt when run on $x$ as input.
$K_1$ is the set of all programs $x$ which halt on some input.

Given a program $x$, consider the following program $f(x)$:

For $n=1,2,3,\ldots$: run program $x$ on inputs $1,\ldots,n$ for $n$ steps, and halt if $x$ halts of any of them halt.

The program $f(x)$ halts iff $x \in K_1$. In particular, $x \in K_1$ iff $f(x) \in K$. Since $f$ is computable, this gives a reduction from $K_1$ to $K$.


Does a type-1 automaton always have to terminate? For push-down automata it seems obvious to me that a program must always terminate (given the input is finite), because for each input symbol they advance until eventually they run out of symbols and then terminate.

The opposite is true for Turing machines as they read their input from the tape and are able to alter the position in the input string.

Linear bounded automata are basically Turing machines that have to operate on a bounded range on the tape. As far as I can see, that doesn't prevent you from writing a program for such a machine that just toggles between two states infinitely and thus never terminates.

Is this assumption correct? And can we infer anything about the language an automaton is able to accept from the property if it must terminate eventually? I'm a bit confused about the fact that type-1 languages are a subset of the decidable languages, where the decidable languages require an always halting Turing machine, but I can't find any such restriction for linear bounded automata.

Pushdown automata do not necessarily halt. They are not forced to read input each step, they can also do so-called $\lambda$-instructions where the tape is not advanced.
Then we can have an infinite loop at a certain tape position.

Likewise, linear bounded automata may loop, and do not always halt. However, they can be simulated by a Turing machine, which stores each configuration, and tests for loops. That is not efficient of course, but can be done. In that way we get halting machines, but of a different type.


Check for balanced parentheses in an expression in log-space Given an expression (a word in the one-sided Dyck language), I want to write a program to examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”[“,”]” are correct in the expression.  For example, the program should print true with begin-end pair of symbols indices for exp = “[()]{}{()()}” and false for exp = “[(])”.

The naive solution with a stack has O(n) time-complexity and O(n) space-complexity.  Can we solve this problem in O(log(n)) space-complexity?  In other words, can we parse Dyck languages in logarithmic space?

The Dyck language on any fixed number of symbols can be recognised by a marking automaton, which is a two-way finite automaton that can mark a fixed number of input tape squares.
The automaton simply uses a different mark for each type of parenthesis.
Since a marking automaton is easily implemented by a Turing machine with a fixed number of logarithmic-sized regions of the worktape forming pointers into the input, Dyck languages can be parsed in logspace.

R. W. Ritchie and F. N. Springsteel, Language Recognition by Marking Automata, Information and Control 20, 313–330, 1972.
doi:10.1016/S0019-9958(72)90205-7


What's the problem of using the clock to generate random numbers? If the clock shows 14:15:36.909302, why not just use the fractions of a second part (09302) as a kind of random number?

What is wrong with this form of generating random numbers?

I am aware that obtaining truly random numbers is a difficult task, so I am assuming that there is something wrong with this method.

Quick answer:

If the run time of your algorithm to pick a random number is not random you could get a pattern of times which is not random.

As an example. Suppose the function to read the time is triggered by an event, and the event is timed to the clock, now your functions based on the clock.
If the run time of your algorithm is faster than the precision of the clock, then you will get duplicate times and thus duplicate numbers which are not random.

As an example. You write a function for use by others, and someone decides to generate 10,000 random numbers and store them. The loop is so tight for reading the clock and saving the values that you get 10,000 numbers all identical.

These are just cases that can make the data non-random. In reality if it is not security related I run a large sample through a test for randomness and if it were reasonable I would use it, but if it is security related I would ask at Security or Crypto


What are some practical problems which require the use of Kadane's algorithm? I've worked through Kadane's and love its elegance. I am worried though, unless asked specifically about arrays and it's obvious that's what's for dinner, I won't know to use it.

What are some real-life problems and applications where this algorithm is key? How would one go about recognizing them in the wild?

See the Wikipedia article on the maximum subarray problem for applications to genomic sequence analysis, computer vision, and data mining.


Determining time complexity of this function in python I would like to determine the time complexity of this function, in $\mathcal{O}$-Notation.

def g(x):
   if x == 0:
      return 1
   elif x == 1:
      return 2
   else:
      x_div = x//2              # // is integer division
      x_mod = x % 2
      return g(x_div)*g(x_mod)

Because it's recursive, I think it's $\mathcal{O}(\log{}n)$. Is this correct?
A small explanation would be great.

Another question, is there a relation between the return value of the function and the binary representation of $n$?

Let $T(x)$ denote the running time of the algorithm. The following recurrence captures the running time of the algorithm:

  $T(x)=T(\frac{x}{2})+c,\ x\geq3,\ c \in O(1)$
  where $T(0) = T(1) = a \in O(1)$

Solving this we get, $T(n) \in O(log_2 x)$


Create automata from non regular grammar I have two grammars:

 L → ε | aLcLc
 L → ε | aLcLc | LL

This two grammars are equals but the first one is regular, so it produces a regular language and a Finite State Automata. Instead, the second one is non regular but it might produces a regular language.
To prove it, I want to create two differentes automata: the first one should be a correct automata and if the second one can't be create then the language is not regular. Are all this statments correct?
If so, can someone help me build these two automata? Thank you!

Your first language isn't regular. Here is a simple way of showing this. Consider all words in your language of the form $a^*c^*$; if your language were regular, then so would be that language. However, the new language is generated by the grammar $L \to \epsilon \mid aLcc$ (this requires an argument), and so is $\{a^n (cc)^n : n \geq 0\}$, which is classically known to be irregular.

With more effort, you can show that your language consists of all words $w$ in which every proper prefix $x$ satisfies $\#_a(x) > 2\#_c(x)$, and furthermore $\#_a(w) = 2\#_c(w)$.

An identical argument works for your second language. With more effort, you can show that the language consists of all words $w$ in which every prefix $x$ satisfies $\#_a(x) \geq 2\#_c(x)$, and furthermore $\#_a(w) = 2\#_c(w)$.

Summarizing, both of your languages are irregular, and this can be shown by intersecting them with $a^*c^*$.


Minimum spanning subgraph of even degree I have an unusual problem that I am struggling to solve. I have a set of nodes (with positive distances between them) that I want to connect into a single component. In particular, I want to form a minimum-distance spanning subgraph such that all its nodes have an even degree. Note that the subgraph can have multiple edges between a pair of nodes (multigraph). Below are some examples:

A) We have 8 nodes arranged in a circle, where adjacent nodes are separated by distance 1. We connect them into a single cycle of length 8.

B) The top figure shows all the possible distances. If we use the three single edges then we will have a subgraph of weight 1+1+3=5. But we can do better if we use double edges, giving us a total weight of 1+1+1+1=4 (bottom figure). Note that the center node has degree 4, but this is ok since it is still even.

C) Here all adjacent nodes are separated by distance 1. If we use double edges in the shape of the Sum sign (Sigma) then we will get a subgraph of weight 8. But we can do better by using single edges, giving us a total weight of 6.

D) Here the best way to include the top-right node is to use double edges.

I have come up with an outline for an algorithm for solving this problem, but it is not quite complete. First we compute the minimum spanning tree. This will give us some of the edges of the subgraph. It will also give us some nodes (leaves of the tree) with degree 1. We now greedily connect these nodes to their closest neighbours. This is the bit that I haven't quite worked out. Because if we always pick the closest neighbour then we will get the same edges as the MST. Clearly this will fail in A. So perhaps we want to prioritise connections to other degree-1 nodes. Also at the end of this step, we may still have some nodes with an odd-degree remaining which also need to be connected.

Any help would be greatly appreciated!

I just realised that example A is an instance of the Travelling Salesman Problem, which is NP-hard. So the best we can hope for is an approximation algorithm.

I also realised that this is problem is an instance of b-matching, where you want to select up to b edges incident on each node of minimal total weight. Here we have the additional constraint that b is even. I found a couple of papers that solve b-matching:

http://www.aporc.org/LNOR/10/ISORA2009F12.pdf
http://proceedings.mlr.press/v15/huang11a/huang11a.pdf


How to find a condition which leads to deadlock in non-reentrant locks A multithreaded program P executes with x number of threads and uses y number of locks for ensuring mutual exclusion while operating on shared memory locations. All locks in the program are non-reentrant, i.e., if a thread holds a lock l, then it cannot re-acquire lock l without releasing it. If a thread is unable to acquire a lock, it blocks until the lock becomes available. The minimum value of x and the minimum value of y together for which execution of P can result in a deadlock are:

A. x=1,y=2
B. x=2,y=1
C: x=2,y=2
D: x=1,y=1

Though, answer is option D but is there any possibility to have deadlock in other 3 options. If yes, then what it is because not able to visualize other options. Kindly explain.

A single thread can get itself deadlocked by locking the same lock twice without an unlock in between. Which is obviously a stupid thing to do.

I don’t see your problem with the other cases: if one thread deadlocks itself, you have a deadlock, no matter how many other threads and locks you have.


Why is the name half-adder used to represent the half-adder? I have recently came across half-adders and full adders in my Logic Network lectures. I have somewhat understood the theory, but I am still unable to understand the reason why they called them in that name? I mean, is there any reason why half-adders have the name ‘half-adders’?

With a full adder, you can get all outputs from (0,0) to (1,1). With a half adder, you can never get (1,1), which makes it, in a way, incomplete.

Also, in practice a full adder is used more than a bare half adder. For example, addition of binary numbers (one of the most common operations needed by a microprocessor) is done by chaining full adders:

(4-bit adder, taken from Wikipedia)

In the end, since full adders are the ones used for adding, we call them "full" adders.

And since a full adder can be made by joining up two half adders with an OR gate, the half adder becomes "half" an adder.


Complexity of linear programming with restricted quadratic constraints A problem instance is a linear program with the following kind of quadratic inequalities allowed: For some of the variables $x_i$, there is a variable $s_i$ (intuitively for approximating $x_i^2$, and distinct from all the $x_j$) and positive constants $l_i,r_i$, such that the following constraints are also included:

$l_i ≤ x_i ≤ r_i$  (confined to boxes; this is the case for every variable in my application)

$l_i x_i ≤ s_i ≤ r_i x_i$  (minor improvement over $l_i^2 ≤ s_i ≤ r_i^2$)

$s_i ≥ x_i^2$  (the approximation is tightly constrained from below, only)

Only the third line is quadratic. I include the first two lines in case they make the problem more tractable.

Is this a convex optimization problem? Can it be formulated as a semidefinite program? I see that the regions confining the values of $x_i^2$ are convex, but I doubt that implies the solution space as a whole is. [edit: I was wrong; according to @Vincenzo it is indeed that simple.]

The reason I suspect it might be efficiently solvable is that it seems it can be approximated well (provided the intervals $[l_i,r_i]$ are small, which they will be in my case) with increasing numbers of linear constraints over the same variables. In particular, each $s_i ≥ x_i^2$ is replaced by some $k$ linear constraints defined by

$s_i ≥$ line tangent to $x_i^2$ at the point $x_i = a_1$

...

$s_i ≥$ line tangent to $x_i^2$ at the point $x_i = a_k$

where each $a_t$ is a constant in $[l_i,r_i]$.

Optional question: In case the set of infeasible such problems is coNP-hard, is there nonetheless some method that is said to work well in practice?

The intersection of convex sets is a convex set, therefore the region defined by your inequalities is convex. Essentially, that implies you can solve the problem efficiently within any fixed positive accuracy $\epsilon>0$.


How to define whitespace for certain rules but else ignore it I am trying to make a programming language for the first time and wonder how it handles whitespace. I can see CFG by default seem to just ignore whitespaces, but what if I want it to use it sometimes? Like when you declare an int people usually write "int b", and the whitespace separate these two items, but if I write something like "5 + 5" it should ignore the whitespace. Is that simply done by implementing in the rule for declarations like this:

Dcl --> int" " Id

Expr --> "int+int".

This should force a user to write a whitespace between the int and Id, but don't care whether there is a whitespace in the Expr rule. Is this correctly understood?

I think you're approaching this the wrong way. Writing spaces is better handled as a problem of parsing, not of defining your grammar. That is, your grammar should only concern itself with lists of 'tokens' and your parser is concerned with transforming text into 'tokens' properly.

In a sense, whitespace is something the grammar should be completely unaware of. Whitespace can be useful for your parser to determine whether something is one or two tokens, but I doubt that you want to consider whitespace as a token by itself.


Find the exactly correct separating hyperplane of SVM when the data is not perfectly linearly separable I am thinking about the following case where the data in region 1 is always positive and the data in region 2 is always negative, but the data in region 3 can be both positive and negative. Are there any existing results on finding exactly the $l_1$ and $l_2$ (or region 3)?

As far as my understanding of SVM when the data is not perfectly linearly separable, we can maximize the soft margin to find the separating hyperplane. We can control the penalty of misclassification to achieve different separating hyperplanes. But is there a method for finding the exactly correct separating plane like $l_1$ and $l_2$? I am not very familiar with SVM, and I would really appreciate it if you can provide some comments or references.

I think you can create a "half-hard" SVM problem. It will be like the hard SVM for positive labels (without the error term) but for negative example it will be the like the soft SVM (with the error term).
This wil guarantee you get the line that labels correctly all positive examples, but still tries to label as many of the negative examples as it can (and also create the largest margin it can)
You can do this twice to get both lines $l_1$ and $l_2$.


Is there a universal identity or zero value for folding? I'm using Haskell notation for illustration, hopefully it is known widely enough for this to make sense.

In the following fold function the second argument is what I'm calling the identity:

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

It is trivial to fold/reduce over a list of values with certain operations such as addition or multiplication. e.g.

mySum :: (Num a, Foldable t) => t a -> a
mySum = foldr (+) 0   --NB. Works because 0 is the additive identity

myProduct :: (Num a, Foldable t) => t a -> a
myProduct = foldr (*) 1  --NB. Works because 1 is the multiplicative identity

But not all operations have an obvious identity value.

My question is whether there is such thing as a universal identity value, or a function whereby you can find the identity value, or if you can contrive a scheme so that there now is one.

i.e. can you somehow define a z value such that:

foldrUniversal :: Foldable t => (a -> b -> b) -> t a -> b
foldrUniversal f = foldr f z

or could you have a function that determines it:

findIdentity :: (a -> b -> b) -> z  --is this possible?

foldrUniversal f = foldr f (findIdentity f)

or can you use some trick so that you always have an identity value even if you don't know what it should be?

(Note that I'm not stuck on a programming problem.  I already know about foldr1 in Haskell, or using the head of the list as the identity and then the tail of the list as the list argument.  I posted in cs.stackexchange instead of StackOverflow because I'm interested in the theoretical possibilities.)

Assume we can define

foldrUniversal :: Foldable t => (a -> b -> b) -> t a -> b

Then,

foo :: b
foo = foldrUniversal (\x y -> y) []

Is a way to form a value for any type b. If the type system is sane, this implies that foo does not terminate, as if we recursively defined foo = foo. Otherwise, all the types would be inhabited, making the logic associated to the type system to be inconsistent. A type system that allows this would be regarded as essentially "broken".

In real world languages, we do (grudgingly) allow some unwanted inhabitants. Non-terminating values ("bottom") are common ones, since they are mandatory in language with unconstrained recursion. null values are also used in many OOP based languages -- this is a so-called "billion dollar mistake", and should be avoided. Having a way to craft a "real" value of type b (say non-null, non-bottom) from nothing is too much.


Count all possible unions in a collection of sets Say we have a collections of sets $\mathcal X = \{X_1, \dots, X_n\}$ (not necessarily disjoint), and we want to count the number of possible unions of sets in $\mathcal X$, i.e. the size of $\{\bigcup_{Y \in \mathcal Y} Y \,|\, \mathcal Y \subseteq \mathcal X \}$.

Is there a name for this problem?
What are the fastest algorithms to solve this problem?

I found the answer here.
It is called the union closure and the complexity appears to be the same as computing the number of maximal independent sets in a bipartite graph.


Algorithm to find out if a set contains two number with sum in the same set using a blackbox function I need help with the following question -
There is a set S of n integers.
Given a black box which returns three integers a,b,c in S such that a+b+c = 0 if they exist.
One needs to devise an algorithm that makes only one call to the black box to find out if S contains
three integers such that a+b=c
The question also had a hint -
Construct a set S' such that there exists  a',b',c' in S' such that a'+b'+c'=0 if and only if
there exists a,b,c in S such that a+b=c
Thanks

Your question is essentially answered on the Wikipedia page on the 3SUM problem, specifically the part on 3 different arrays.


Fantasy premier league dream team algorithm? For those of you who are not familiar with FPL, here's a short version. You have players playing as either Goalkeeper, Defender, Midfielder or Forward. Each player has some price (either rounded to .5 or .0), and based on their real life performance you earn points. You have a budget of 100£ and you need to build a team, keeping in mind you have a limit for players on each position.

Now, the problem is: If you have all players prices, their positions and total number of points they scored in a season, how do you find the highest scoring team (team score is equal to sum of all players' individual points) with, for example, 4-4-2 formation? (1GK, 4DEF, 4MID, 2FWD)

I guess this is a variation of knapsack problem, where you have limitations to have exactly 11 players, and exactly 4-4-2 formation.
So is that the best way to solve this problem and how would you solve it with these modifications/limitations, or is there a better solution?

You can formulate an integer program for this problem. For each player $i$ let $a_i$ be the number of points the player scored, $p_i$ is his price. Moreover, let $G, B, M, F$ be the set of goal keepers, backs, midfielders and forwards, respectively, $P := G \cup B \cup M \cup F$ the set of all players, and $C$ is the salary cap. We use binary variables $x_i \in \{0, 1\}$ for each player $i$, were $x_i = 1$ iff player $i$ is in the optimal roster, $0$ otherwise. The optimal roster is then induced by the solution of the following program:
$$\begin{aligned}
\text{maximize } & \sum_{i \in P} a_i x_i\\
\text{subject to } & \sum_{i \in P} p_i x_i \leq C\\
& \sum_{i \in G} x_i = 1\\
& \sum_{i \in B} x_i = 4\\
& \sum_{i \in M} x_i = 4\\
& \sum_{i \in F} x_i = 2\\
& x_i \in \{0, 1\} & i \in P
\end{aligned}
$$
Now you may have noticed that the objective function + capacity constraint is indeed a knapsack problem but you have additional constraints on the formation.

Although you can use a MIP solver of your choice, you might even exploit this knapsack structure as a subproblem by using a knapsack solver (I think there is some very popular dynamic programming approach).


Number of elements with lower index equal to some element, for all items on an array Let $A$ be an array of size $n$, and $f(i, r, a_r)$ be the number of indices $k$ such that $a_k$ = $a_r$ and $i \le k \le r$.

Example to clarify:

Imagine the array: $[1, 2, 3, 2, 2, 3, 4, 5]$. $f(0, 3, a_3)$, for example, would be equal to 2, because there are 2 elements in the array that appear before $a_3$ (which is 2) and are equal to it.

I've heard one of my colleagues talk about using a Fenwick Tree, but I don't see how that could be done.

I'd like to know if there´s a way to solve this problem in $O(n)$. By solving it I mean finding every value of $f$ for a fixed $i = 0$ and $r = [0, n-1]$

Space isn't really a problem, as long as it's polynomial.

Do a linear scan over the array, and use a hashtable.  Each time you see an element, add it to the hashtable (with a count of 1) if it's not already present, or increment the count of the item in the hashtable if it is already present.  As you see each element $a_r$, you can compute $f(0,r,a_r)$ by looking up $a_r$ in the hashtable and finding its count, and then record this value of $f$.  This will lead to an expected running time of $O(n)$ if you use a suitable hash function.

If you want deterministic running time, use a balanced search tree instead of a hashtable; that will achieve $O(n \log n)$ worst-case running time.


Problem using the Arden's Lemma on one automata I am trying to find the regular expression of this automata using the Arden's Lemma:

Let $L_{i}$ be the language accepted from the state $i$, this is what I got:

$L_{1} = 1^{*}0L_{2}$
$L_{2} = 1L_{1} + 0L_{3}$
$L_{3} = \epsilon + 0^{*}1L_{2}$

As the first state is the initial one, I have to solve $L_{1}$. As $L_{1}$ is expressed using $L_{2}$, I have to first solve $L_{2}$.

$L_{2} = 1(1^{*}0L_{2})+0(\epsilon + 0^{*}1L_{2}) \\ L_{2}=11^{*}0L_{2} + 0\epsilon + 00^{*}1L_{2} \\ L_{2}=(11^{*}0+00^{*}1)L_{2} + 0$

Using Arden's Lemma, I get $L_{2}=(11^{*}0+00^{*}1)^{*}0$

Thus we have now:

$L_{1}=1^{*}0L_{2}=1^{*}0((11^{*}0+00^{*}1)^{*}0)$

Yet, based on this expression, the word "000" isn't accepted. Where is my issues?

The mistake is in the equation for $L_3$: it should be $0^*$ instead of $\epsilon$.


How can I efficiently generate the shortest list of arguments for the range() function that will generate a given list of integers? I ran into an interesting problem at work when trying to generate the inputs for an API given the expected output. I've tried to formalize and anonymize the problem below. I've been trying to design a fast algorithm that works here but I'm a little stuck. Thanks in advance for the help! I'm not an experienced question writer so please feel free to edit this to make it clearer. I'll do my best to answer any clarifying questions.

Background

In python 2.7, the range function takes 3 arguments (start, stop, and step) and returns a list of integers.

  The full form returns a list of plain integers [start, start + step,
  start + 2 * step, ...]. If step is positive, the last element is the largest start + i * step less than stop; if step is negative, the last element is the smallest start + i * step greater than stop.

Documentation

Examples

>>> range(0, 30, 5)
[0, 5, 10, 15, 20, 25]
>>> range(0, 10, 3)
[0, 3, 6, 9]

Problem

Given a list of positive integers, I, generate a list of 3-tuples that when fed into the range() function that will generate the same set of integers as I. The answer list must be the minimum possible length. If more than one minimum length solution exists, return any of the solutions.

Examples

Input: [1, 2, 3]
Output: [(1, 4, 1)]

Input: [1, 2, 3, 5, 7, 9]
Output: [(1, 4, 1), (5, 10, 2)] or [(1, 10, 2), (2, 3, 1)]

Input: [1, 2, 4, 5, 6, 11, 12, 13]
Output: [(1, 3, 1), (4, 7, 1), (11, 14, 1)]

I'm assuming the input does not have duplicates, e.g. not [1, 2, 2, 5].

No, an efficient (polynomial time) algorithm does not exist to our best knowledge, as per "Covering a set with arithmetic progressions is NP-complete" by Lenwood S.Health.

But we can make a recursive algorithm regardless, it will just be exponential time as our input grows.

Note that the first element not covered by previous ranges must be the start of the next range. Furthermore, you can always cover at least two elements with each range. And even better, the second element you choose to cover with a range also fully determines that range. The stop condition doesn't really matter - you'd just stop when the next element generated wouldn't be in the set.

With this information you can write a recursive algorithm (which assumes l is given sorted):

def cover_ap(l):
    if not l: return []
    if len(l) == 1: return [(l[0], l[0])]

    candidates = []
    a = l[0]
    for b in l[1:]:
        ap = [a, b]
        step = b - a
        k = b + step
        while step > 0 and k in l:
            ap.append(k)
            k += step
        stop = ap[-1] + 1

        remain = sorted(set(l) - set(ap))
        candidates.append([(a, stop, step)] + cover_ap(remain))

    return min(candidates, key=len)


Pumping Lemma with Prime Number $\text {Could someone please help me with this proof: }$
$L:=\left\{a^{n} d^{m} b^{k} | n, m, k \in \mathbb{N} \wedge m \text { is a prime number}\right\}$

$\text {Maybe we can say, that } w=a^{n}d^{m_s}b^{k} \text { and } d^{m_s} \text{ is a prime number with } |w| \ge n. \text{And we choose xyz arbitrarily with } w= xyz \text { } \wedge |y| \ge1 \wedge |xy| \le n\text {. And now I don't know how to go on. Maybe someone can help me, please.}$

Helpful property of prime numbers: The gaps between consecutive prime numbers become arbitrarily large. That means for every r, there is a prime p such that none of the numbers p+1 to p+r are primes. That means $a^nd^mb^k$ is not in the language for p+1 ≤ m ≤ p+r.

That would generally work for "m is a member of an infinite set with arbitrarily large gaps between members of the set", like "m is a square, a cube, a factorial" and many others.


$L \in RE/R$ such that $L^R \cup L \in R$ Prove/disprove: $\exists L \in RE/R$ such that $L^R \cup L \in R$

Where in my context, $R$ is the turing decidable, and $RE$ is the recursively enurmable. I tried to find such an $L$ but couldn't. What I know for sure is that I need a language in $RE/R$ such that $L \cup L^R = \Sigma^*$, or am I also wrong?

Since this sounds like a homework question to me, I will give the answer as a series of hints. (You should make a serious effort to solve the question after each hint, instead of just reading them all in short succession.)

First: Such an $L$ exists and $L \cup L^R$ is not necessarily $\Sigma^*$.

   Try $L \cup L^R = \{a^nb^n\} \cup \{b^na^n\}$.

   For each $n$, $L$ should contain exactly one of the words $a^nb^n$, $b^na^n$. How can you do this so that $L$ is in $RE/R$?

And finally the solution:

   Let $K$ be any set in $RE/R$ and let $L = \{a^nb^n \mid n \in K\} \cup \{b^na^n \mid n \notin K\}$.


How much bits need to add to 100bit of data in order to correct up to 10bits? I'm trying to calculate how much minimum bits need to be added to data of 100bits, in order to correct 10 bits that are messed up by:

bits that deleted (Erasure Correcting)
bits that corrupted (Error Correcting)

I tried Hamming code and Reed-Solomon codes but didn't figured out the answer of 1 or 2.

There are some other more-efficient algorithm for that problem ?
Thanks in advance !

This seemingly innocent question, is actually quite difficult to answer. Let me try to give some more information on the parameters that get into the game here, and give a partial survey of common results and bounds.

As mentioned in Qalnut's answer, to deal with $10$ bits of errors (in the worst case) we must have distance at least $d=2\cdot 10+1$. This is given. Another parameter that is implied by your question is that the basic unit is a bit. You ask, what is the minimal length $n$ of a (binary) code that has distance $d$ and contains, at least $2^{100}$ codewords.

The lower Bound

Let's first try to ask a slightly more general question:

  Given an alphabet of size $q$, what is the maximal number of codewords in code of length $n$ that has minimal distance $d$. [Let's denote this number by $A_q(n,d)$].

The answer to this question is not simple at all, but there are several well known bounds. One very useful bound is the singleton bound, which states that
$$ A_q(n,d) \le q^{n-d+1}$$

This immediately tells us that in order to have $2^{100}$ codewords with distance $d=21$, you must take $n>120$, that is, to add at least 20 bits. But this is only a bound, it never says that such a code (with length 21) actually exists, or how to find it.

More generally, this bound tells us that the relation between the rate of the code $R=n/k$ and the relative distance of the code $\delta=d/n$ behaves, for $n\to \infty$, as
$$ R \le 1-\delta + o(1)$$

Since you wished the relative distance of your code to be $d/n =0.175$, the maximal rate is $\approx 0.825$, which is exactly what we got ($k/n = 100/120 = 0.833 = 0.825 + 1/n)$. The moral of this story is: if you aim for distance $\delta$ (which can correct $\approx \delta n /2$ errors), you will have to add at least
$$(n-k) = n-Rn \approx \delta n $$
more symbols. This is a nice rule of thumb. In the asymptotic case (that is, when $n$ is very very large) that would be approximately the answer.

As said, this bound is, in many cases, not really tight. For other lower bounds, look for the Plotkin bound (for binary codes) and the Johnson bound.

The upper bound

So we know we can't get $n$ smaller than, say, 120. But this is not very helpful from a practical point of view, since we don't even know if a code with $n=120$ exists, or maybe in this case the first code with $d=21$ and $k=100$ shortest $n=137$??

Gilbert and Varshamov come to our help, and show that there always exists a code for which
$$ A_q(n,d) \ge \frac{q^n}{\sum_{j=0}^{d-1}\binom{n}{j}(q-1)^j}$$

So now you just need to plug in $A_q(n,21)=2^{100}$ and find $n$. Let me WolframAlpha this for you, it gives $n<189$ (actually, a tighter version of the GV bound for binary code will gives $n\le 185$. The GV bound even tells you how to find this code, in a greedy way (thus, doesn't expect it to be efficient).

The "answer"

As I said, the real answer may be difficult to find, and depend on $q$ (why are you so fixed on binary codes? maybe considering the message as symbols of a larger alphabet would give a better code? But then the noise pattern need to be properly defined, so I'll skip this explanation here), and on $k$ (why 100 bits? ain't 127 bits make much more sense?), and on efficiency (which you asked, but I will not get into), etc.

The bottom line, is that many people thought on such questions over the last century, for various parameters. The problem is to find the code you need. For this purpose you can look at some Code tables that aggregate codes of various parameters.

For instance, for short binary codes, there is this work,
"Bounds for binary codes of length less than 25" (IEEE Trans. Inform. Theory 24:81-93, 1978).
A more extensive list can be found, for instance, at
Code Tables: Bounds on the parameters of various types of codes. Searching in Table of Nonlinear Binary Codes for a code with the parameters you gave in your question, I found that the shortest code for distance 21 that has at least $2^{100}$ codewords has length $n=191$. The reference is H. J. Helgert and R. D. Stinaff. "Shortened BCH codes", IEEE Trans. Inform. Theory, 19:818--820, 1973. Damn, this is worse than the GV bound, but it allows you to code messages of up to $k=116$ bits!
instead, If you are willing to settle with messages of length $k=91$ bits, you will be able to do that with $n=173$ bits. (M. Kasahara, Y. Sugiyama, S. Hirasawa, and T. Namekawa., IEEE Trans. Inform. Theory, 22:462--468, 1976). Using this table for linear binary codes, there is a constructive code with $k=100$ and $n=176$. There references are inside this link.

So back to you innocently looking question: the answer(1) is 76.

(1) At least, the best answer I was able to google.   (ADDENDUM, found a better one:) and re-google.


Something wrong with this definition of factorial with structural recursion? In The Algebra of Programming page 5, the authors defined structural recursion foldn (c, h) over natural numbers:

f  0    = c
f (n+1) = h (f n)

They then went on to defin factorial as follows:

fact = outr . foldn ((0, 1), f)
outr (m, n) = n
f (m, n) = (m + 1, (m + 1) * n)

This doesn't seem right, first of all, foldn ((0, 1), f) does not comply to its definition, secondly, this fold will never terminate, will it?

This definition is correct. The syntax is almost Haskell code, so you can run it in a Haskell interpreter:

foldn (c, h) = g where
  g 0 = c
  g n = h (g (n - 1))

fact = outr . foldn ((0, 1), f)
outr (m, n) = n
f (m, n) = (m + 1, (m + 1) * n)

Usage in ghci:

Prelude> :load fact.hs
[1 of 1] Compiling Main             ( fact.hs, interpreted )
Ok, modules loaded: Main.
*Main> fact 0
1
*Main> fact 1
1
*Main> fact 2
2
*Main> fact 3
6
*Main> fact 4
24
*Main> fact 5
120

I don't know what you mean by “foldn ((0, 1), f) does not comply to its definition. If you mean that it's missing an argument, then this is not a problem. It's a function waiting to be applied. foldn is a curried function: it takes an argument and returns a function, which itself takes an argument and returns something; this makes foldn look like a function that takes two arguments (the first of which is a pair).

You can't evaluate foldn ((0, 1), f) any further (except to replace it by an anonymous function for which there is no source syntax) because its definition is by case on its argument: there's no way to know which one of g 0 = … or g (n+1) = … to use until you know whether the argument is 0.

Once you pass an argument, you can evaluate the call.

foldn ((0, 1), f) 0 = (0, 1)

so

fact 0 = (outr . foldn ((0, 1), f)) 0
       = outr (foldn ((0, 1), f) 0)
       = outr (0, 1)
       = 1

fact 1 = (outr . foldn ((0, 1), f)) 1
       = outr (foldn ((0, 1), f) 1)
       = outr (f (foldn ((0, 1), f) 0))
       = outr (f (0, 1))
       = outr (0 + 1, (0 + 1) * 1)
       = outr (1, 1)
       = 1

I'll let you work out other values by yourself.

The computation always terminates, regardless of the function h (assuming only that h terminates), by a simple induction argument: each nested call to foldn is applied to a smaller integer. For any nonnegative parameter, eventually the argument will be 0 which does not involve recursion.


How to use the Pigeonhole Principle to prove a DFA has a minimum number of states? $A = \{w \in \{a, b\}^* | $ 10th character from the end of $w$ is $b\}$
Prove if DFA $M$ has $L(M) = A$ then $M$ has at least 1024 states.

So there's only 2 characters possible at any state, aside from the 10th character, which has to be $b$. Any character after that can be a or b, since we know the 10th character from the end is $b$.
I was told that the Pigeonhole Principle would be used to prove this, as well as contradicting or using the contrapositive was the way to go.
My answer was that if we took a string $w$ with a length of less than the number of states, say 9, then the principle says that a state will have to be repeated. So a string of 10 $b$'s in a row won't reach an accepting state because the path will waste a transition to loop or repeat a state that has been traveled to. Because a string failed when it shouldn't have, that contradicts the language?
I also have a few other reasonings that may work with the Pigeonhole Principle, but I am just wondering if my reasoning makes sense.

http://www.owenstephens.co.uk/blog/2014/09/28/NFA_DFA.html

https://cseweb.ucsd.edu/~ccalabro/essays/fsa.pdf

Evil's link and this other link seem to show how to apply the Pigeonhole Principle to show how to answer my problem. The second one explains it more visually and in a more noob friendly fashion.


Can product DFA for intersection of two disjoint languages be minimal? I know that it isn't necessary that cross product automaton for two minimal DFAs be minimal, but according to my analysis, if two DFAs do not have any common string then their cross product of minimal DFAs would be minimal. What should I do to prove this?

No.

Counterexample:

Let alphabet $\Sigma = \left\{ 0, 1 \right\}$, languages $L_1 = \left\{ w0 \,\middle|\, w \in \Sigma^\ast \right\}$ (i.e. the last digit is $0$), $L_2 = \left\{ w1 \,\middle|\, w \in \Sigma^\ast \right\}$ (i.e. the last digit is $1$). Note that $L_1 \cap L_2 = \emptyset$.

Then the following DFAs $M_1$ and $M_2$ are minimal for $L_1$ and $L_2$ respectively:

And the cross product of $M_1$ and $M_2$ (for the intersection of languages) is:

But this is not minimal for the empty language. A minimal DFA for the language is:

In fact, cross-product DFA of $M_1$ and $M_2$ recognizes an intersection of languages $L(M_1) \cap L(M_2)$ (if a state of cross-product DFA is accepting when the original two states are both accepting on original DFAs). So in this case a generated cross-product DFA always recognizes the empty language. Since a minimal DFA for the empty language has only one state and cross-product DFA has ((#states of $M_1$) × (#states of $M_2$)) states, almost all cross-product DFAs are non-minimal.

Also, even though if you define a state of cross-product DFA is accepting when either of the original two states is accepting, the above $(L_1, L_2)$ is a counterexample. Since $L_1 \cup L_2 = \Sigma^\ast$, the minimal DFA has only one state.


How do you analyse the time complexity of a piecewise function? Is there a method to apply when trying to finding out the time complexity of a piecewise function?

\begin{align*}
F(x) &= \begin{cases} 2^x & x < 8, \\ x^2 & x \geq 8. \end{cases} \\
\end{align*}

This case seems straightforward as the function is $\Theta(x^2)$ for a large enough value of $x$, but what should be done in a more complex case... for example a function that gives a result for an odd value of $x$ and another one for an even value of $x$?

There seems to be a misconception here: every function $f$ has a "nice" asymptotic form, in the sense that $f = \Theta(g)$ for some function $g$ given by a reasonable formula. Some examples of reasonable formulas include $c^nn^k\log^\ell n$ for various values of $c,k,\ell$. However, this isn't always the case. Consider for example the function
$$
f(n) =
\begin{cases}
n & \text{if $n$ is odd}, \\
n^2 & \text{if $n$ is even}.
\end{cases}
$$
There is no "nice" function $g$ such that $f = \Theta(g)$. It is apparent that $f = \Omega(n)$ and that $f = O(n^2)$, but there is no value of $k$ for which $f = \Theta(n^k)$.

In practice, such examples occur only rarely, and so usually it is the case that we can find a nice order of growth for functions that occur in practice.

This discussion is related to another misconception, that we can always compare two functions asymptotically. That is, that for any two functions $f,g$, either $f = o(g)$, or $f = \Theta(g)$, or $f = \omega(g)$. While these three possibilities are indeed mutually exclusive, there is a fourth possibility, namely, that $f$ and $g$ are incomparable. As an example, if we take the function $f$ considered above and try to compare it to $g(n) = n^{3/2}$, then we find that none of $f = o(g)$, $f = \Theta(g)$, $f = \omega(g)$ holds. However, the trichotomy does hold when $f$ and $g$ are "nice" functions (defined using only arithmetic operations, logarithm, and exponential).

Finally, there is one special case which is easy to handle: if
$$
f(n) = \begin{cases}
g(n) & \text{if } n < C, \\
h(n) & \text{if } n \geq C,
\end{cases}
$$
Then $f(n) = \Theta(h(n))$. This is the case in your example.


Push-down Automata Construction Construct a push-down automata to recognize the language $ A = \{u\#v \in \{0,1,\#\}^{*} | u = v^{\complement} \} $. Here, $v^{\complement}$ is the bit-complement of v.

I don't see how to perform this with a LIFO stack. I would like some hints (not a solution) if possible.

Thanks,

There is no such PDA because $A$ is not context-free. This can be proved by pumping.


Is there purely recursive functions? Is there any problem that can be only solved with recursion, and not with iteration? (haven't been able to find anything online).

If there isn't any, is there a reason why?

Thanks in advance!

The Böhm–Jacopini theorem states that everything can be implemented using just IFs and WHILEs. Indeed, your CPU essentially implements an infinite WHILE loop with conditional execution.

Recursion can be simulated iteratively using a stack; this is how recursion is implemented under the hood. Conversely, the same construction as in the theorem shows that everything can be implemented using only tail recursion (which is essentially a WHILE loop). So iteration and recursion are equivalent.


Big O Tires Question? My question is regarding the last paragraph of this excerpt from "Cracking the Coding Interview." (For some reason, my table is not formatting here.)

What's the runtime of this code?

int f(int n) {
  if (n <= 1) {
    return 1;
  }
  return f(n -1) + f(n -1);
}

The tree will have depth N. Each node (i.e., function call) has two children. Therefore, each level will have twice as many calls as the one above it. The number of nodes on each level is:

Level
#Nodes
Also expressed as…
Or…

0
1

20

1
2
2 * previous level = 2
2^1

2
4
2 * previous level = 2 * 2^1 = 2^2
2^2

3
8
2 * previous level = 2 * 2^2 = 2^3
2^3

4
16
2 * previous level = 2 * 2^3 = 2^4
2^4

Therefore, there are 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^N (which is 2^n+1 - 1) nodes. (see "Sum of powers of 2 on page 630.)

Try to remember this pattern. When you have a recursive function that makes multiple calls, the runtime will often (but not always) look like O(branches^depth), where branches is the number of times each recursive call branches. In this case 2, so O(2^n).

As you may recall, the base of a log doesn't matter for big O since logs of different bases are only different by a constant factor. Howerver, this does not apply to exponents. The base of an exponent does matter. Compare 2^n and 8^n. If you expant 8^n, you get (2^3)^n, which equals 2^3n, which equals 2^3n * 2^n. As you can see, 8^n and 2^n are different by a factor of 2^2n. That is very much not a constant factor.

I do not understand the last paragraph. What base of a log? What is that and why do they say this here? What do they mean?

This requires some basic logarithm concepts. You may have come across logarithmic equations with general definition as:

logb(x) = y is valid if by = x | Here b is the base, y is the exponent value that makes by = x

Let's consider x having a value 64. Below are some logarithmic outputs (y) with different bases:

log2(64) = 6 | As, 64 = 26 (base 2)
log4(64) = 3 | As, 64 = 43 (base 4)
log8(64) = 2 | As, 64 = 82 (base 8)

If you notice above, the logs of different bases are only different by a constant factor. (between 6, 3 and 2)
Now let's consider no change in base and this time we will consider exponential base, a general expression would be something like:

loge(x) = y , or ln(x) = y

Let's consider x having value 2n. So y will be:

y = loge(2n), or y = ln(2n)

Now if we change value of x to 8n then y would be:

y = loge(8n) = loge(23n)

23n can be represented in terms of 2n as:

23n = 22n * 2n (or 23*n or 2n * 2n * 2n)

If you notice, the difference between x being 2n and x being 23n is not by any constant factor.
Hence validating the statement:

The base of an exponent does matter. Compare 2^n and 8^n. If you expand 8^n, you get (2^3)^n, which equals 2^3n, which equals 2^3n * 2^n. As you can see, 8^n and 2^n are different by a factor of 2^2n. That is very much not a constant factor.


Is it possible to prove closure of decidable languages under union and intersection, using enumerators? We can use multi-tape enumerators.
(Of course it is not valid to use turing machines albeit the fact that any enumerator has an equivalent TM)

What we need is to prove that if $A$ and $B$ are decidable then $A\cup B$ and $A\cap B$ are also decidable.

Can it be done? If so, what is a possible approach?

Given a decidable language $L$ consider the following enumerator:

EnumL
 loop on strings x over 0 and 1 in canonical/lexicographic order
   if x in L then print x
 end
end

This procedure enumerates/emits all strings in $L$ in lexicographic order. So you can decide if $x \in L$ by running EnumL until it prints the first string of length $|x| + 1$. If it does print $x$ until that time then it means $x \in L$, otherwise $x \notin L$. Thus, using both enumerators EnumA and EnumB you can decide $x \in A\cup B$ and $x \in A\cap B$. In other words, if one of EnumA or EnumB eventually emits $x$ then $x \in A\cup B$, and if both EnumA and EnumB emit $x$ then $x \in A\cap B$.


Can non-metric TSP be approximated within some non-constant value? It is known that metric TSP can be approximated within some constant value, such as 3/2 through Christofides' algorithm. It is also known that non-metric TSP cannot be approximated within some constant value (unless P= NP), thanks to Sahni and Gonzalez.

It isn't clear however if non-metric TSP can be approximated within some non-constant value, such as the number of nodes of the instance, or the largest cost on its edges? Does Sahni and Gonzalez's result still hold for these values?

Indeed, it trivially can.
If each edge has positive integer weight $w_e$, then any algorithm that outputs a valid tour has approximation ratio $w_{max} = \max_e w_e$, since the optimal solution costs at least $n \cdot 1 = n$ while the cost of any valid tour $T$ is at most $\sum_{e \in T} w_e \le n \cdot w_{max}$.

Note: If edges can have weight zero this argument won't work, because in that case even deciding if a tour of cost zero exists is NP-hard; you can reduce Hamiltonian Cycle to it. Hence your algorithm will sometime output a nonzero cost tour, when a zero cost tour exists, which means the approximation ratio cannot be bounded.


Bit errors and hamming distance I'm trying to learn for my exam and had the following practice question:

Take a code with the following code words.

101100010111
110001001001
101110111011

Errors of how many bits can be corrected?

The answer i received was:

The hamming distance is: 4.

Therefore only single bit errors can be corrected.

How did they conclude that only single bit errors can be corrected just by looking at the hamming distance?

If you need four bit changes to change from A to B, then you can make two bit changes from A to some A' followed by two more bit changes from A' to B. If you receive A' then you don't know whether it is a double bit error coming from A, or a double bit error coming from B. Therefore, you cannot fix double bit errors.

Since four bit errors are needed to go from one valid code to another, you can detect double bit errors.

You also have the choice of either fixing single bit errors and detecting double bit errors at the same time (assuming that there will be no triple bit errors), or detecting triple bit errors. You cannot both fix single bit errors and detect triple bit errors, since I can get the same result by changing a single bit in A and changing three bits in B.


What does the leading turnstile operator mean? I know that different authors use different notation to represent programming language semantics.  As a matter of fact Guy Steele addresses this problem in an interesting video.

I'd like to know if anyone knows whether the leading turnstile operator has a well recognized meaning.  For example I don't understand the leading $\vdash$ operator at the beginning of the denominator of the following:

$$\frac{x:T_1 \vdash t_2:T_2}{\vdash \lambda x:T_1 . t_2 ~:~ T_1 \to T_2}$$

Can someone help me understand?
Thanks.

On the left of the turnstile, you can find the local context, a finite list of assumptions on the types of the variables at hand.

$$
x_1:T_1, \ldots, x_n:T_n \vdash e:T
$$

Above, $n$ can be zero, resulting in $\vdash e:T$. This means that no assumptions on variables are made. Usually, this means that $e$ is a closed term (without any free variables) having type $T$.

Often, the rule you mention is written in a more general form, where there can be more hypotheses than the one mentioned in the question.

$$
\dfrac{
  \Gamma, x:T_1 \vdash t : T_2
}{
  \Gamma\vdash (\lambda x:T_1. t) : T_1\to T_2
}
$$

Here, $\Gamma$ represents any context, and $\Gamma, x:T_1$ represents its extension obtained by appending the additional hypothesis $x:T_1$ to the list $\Gamma$. It is common to require that $x$ did not appear in $\Gamma$, so that the extension does not "conflict" with a previous assumption.


How all values hash to the same value with a given formula When looking at hashing, and given the following question:
Given ASCII values: a = 97, b = 98, c = 99, d = 100, e = 101

Given keys: {e, ae, be, ce, de, abe, ace, ade, bae, cae, dae, bce, bde, cbe, dbe}

If we choose: h(k) = k mod 2^6 to map these keys to hash tables indexes, what do you notice?

The answer to this is that all of them hash to 37 but when I try this on a calculator they do not and I do not understand how to get 37. I think this has something to do with the low order bits reference in CLRS and the fact that it is not using a prime number but if I add for example:
a + e = 97 + 101 = 198 % 64 = 6
b + e = 98 + 101 = 199 = 199 % 64 = 7
When I look at the the binary for 6 and 7 they do not end up being the same and neither of the values above ends up resulting in 37.
Any help understanding this is appreciated!

They want you to interpret a string of characters as a multi-byte integer.
So for example abe is intended to mean:
256^2*a + 256*b + e


Is unary language with polynomial power context sensitive? I suppose that $\Sigma = \{a\}$.

Prove or Disprove: For every polynomial $p(n)$ with coefficients in $\mathbb{N}$, $L = \{a^{p(n)} \; | \; n \in \mathbb{N}\}$ is a context sensitive language.

It seems that it is a context sensitive language. I guess making LBA or context sensitive grammar is not easy for this language.  Can I prove this with closure property of CSL for example like complement?  Can any one help me to prove for instance $L_1 = \{a^{n^7+n^5+n^3+n^2+1} | n\in \mathbb{N}\}$ is context sensitive. Maybe I can get an idea from this to prove my first question.

Not true for linear polynomials.  E.g let $p(n)$ be $3n+2$, then L is generated by the regular grammar  'S --> aaaS | aa'.  [unless you mean 'at most context-sensitive', not 'exactly context-sensitive']

The Pumping Lemmas for both regular and context-free grammars seem to imply that any language over a 1-letter alphabet can be decomposed into a (not necessarily disjoint) union of sub-languages corresponding to linear polynomials.  If the set of linear polynomials in question can be made finite (which I suspect must be true, but I can't prove or disprove off the top of my head [and I am not sure it even matters]), then any higher-degree polynomial must take on values not achieved by any polynomial in the linear set, in which case such languages must be at least context-sensitive.

Also: A strategy for building a context-sensitive grammar for a polynomial language over one alphabet is to construct a sequence of $k$ sub-grammars, each of which takes $m$ consecutive $a$'s and transforms it into $b_km+c_k$ consecutive $a$s for some constants $b_k$, $c_k$ [think "Horner's Method"] and then 'cascades' to the next sub-grammar.

So if you mean 'at most context-sensitive', then yes.


Constructing a PDA for the language $\{a^m b^n : m < 2n < 3m \}$ I'm having a lot of trouble constructing a PDA for the language: \begin{equation*}
\{a^m b^n : m < 2n < 3m \}
\end{equation*}

I know if I push a symbol for each $a$ I see, then pop 2 symbols for each $b$ I see, then I should run out to satisfy the $m < 2n$ part of the inequality. But I really don't understand how to include the requirement $2n < 3m$. I'm assuming it has something to do with clever branching based on non-determinism, but I can't wrap my head around it. Any help would really appreciated.

To handle the inequality $m \lt 2n$, you arrange to push a marker for each $a$, and pop two markers for each following $b$. This way the number of markers on the stack indicates the number of $a$'s. When the stack is empty, the equality is reached.

To handle the inequality $2n \lt 3m$, you could to arrange to push three markers for each $a$ and pop two markers for each following $b$. However, a stack won't let you push different numbers of markers.

There is no general way of “merging” two automata in this way. If the two automata use the stack at different rates, it may not be possible to merge them without having two stacks. This is reflected in the properties of languages recognized by pushdown automata: the intersection of two context-free languages is not always context-free.

To get an idea of what to do here, I think it helps to write a context-free grammar for this language. A grammar needs to break down the language into some recursive structure, which leads us to expressing elements of the language as expansions of shorter elements. I'll look at what happens when $b$s are added; you could obtain a different grammar by similar means by looking at what happens when $a$s are added.

If you add $1$ to $n$, what happens to the possible values of $m$? For the maximum value, it's easy: it increases by $2$, because $m \lt 2n \iff m+2 \lt 2(n+1)$. For the minimum value, it's more difficult: we need to find the threshold for $\frac{2}{3}n$, so it depends on whether $n$ is a multiple of $3$, which we cannot express in a grammar rule. However, if we add three $b$s at a time, it's easy: the minimum number of $a$s increases by $2$, because $2n \lt 3m \iff 2(n+3) \lt 3(m+2)$.

Let $L$ be the desired language. The rule above tells us how words in $L$ can be constructed from shorter words; we still need to check the base cases.
$$ \begin{align}
  L \cap a^* &= \varnothing \\
  L \cap a^* b &= \{ab\} \\
  L \cap a^* b^2 &= \{a^2b^2, a^3b^2\} \\
  L \cap a^* b^3 &= \{a^3b^3, a^4b^3, a^5b^3\} \\
\end{align} $$
We have all the information needed to construct a grammar for $L$.
$$
\begin{array}{rl}
  S &\to a b \\
  S &\to a^2 b^2 \\
  S &\to a^3 b^2 \\
  S &\to a^3 b^3 \\
  S &\to a^4 b^3 \\
  S &\to a^5 b^3 \\
\end{array}
\qquad
\begin{array}{rl}
  S &\to a^2 S b^3 \\
  S &\to a^3 S b^3 \\
  S &\to a^4 S b^3 \\
  S &\to a^5 S b^3 \\
  S &\to a^6 S b^3 \\
\end{array}
$$
If you're unsure about the correction of this construction, prove that all words in $L$ are recognized by this grammar (construct a derivation) and prove that all the words recognized by this grammar are in $L$ (by induction over the rules).

Now you can apply a systematic method for constructing a non-deterministic pushdown automaton from a grammar. Since the right-hand part of every rule is the same, it is enough to have a single element in the stack alphabet. Push this symbol for each batch of 2 to 6 $a$'s (this is non-deterministic); pop it for 3 $b$'s.


LP formulation and integer solution existance I’m trying to prove that the following problem has an integer optimal solution. This will hold if the corresponding linear program would have totally unimodular constraint matrix.

We have $m$ pieces of contiguous land parcels $\{1,...,m\}$ and $n$ agents with a simple valuation function that assigns $0$ to all the subset of parcels but $S_i = \{l,l+1,l+2,...,k\}$ for which it assigns $v_i(S_i)$. We would like to find such an allocation of agents to the parcels that maximizes welfare (sum of obtained values).

Let’s define $S=\{S_1,S_2,...,S_n\}$. My try for a relaxed LP is as follows:
$$\max \sum\limits_iv_i(S_i)*x_i\\
s.t.\\
x_i\leq 1 \ \forall i\\
\sum\limits_{x_i: S_i\in T} x_i\leq 1\ \forall T\subseteq S: \cap T \neq \emptyset, T \textrm{ is maximal}\\
x_i\geq 0$$

First off, is it the correct formualtion? I add the second constraint to mean „for each set of agents with contiguous set of parcels that share at least one parcel, and which is a maximal set with that property, only one agent at most can get its desired plot of land”. In other words, I sum $x_i$’s of those agents who chose their subset of lands sharing at least one plot. I do not want repetetiveness so I only take maximal amount of agents with that property each time.
The other constraints are just relaxed constraint in $x_i$ which means that either agent $i$ gets his desired set or not.

Secondly, I do not really see why would constraint matrix be totally unimodular. It will have an identity matrix in is upper part and sth that cannot be specified in general in its bottim part. Perhaps there’s some simpler LP formulation that I haven’t thought of?
I must add I did not leverage the form of the sets valued by the agents anywhere, so it can be that I am missing something.

I kindly ask for your help.

Example:
We have $3$ plots of land $\{1,2,3\}$ and $3$ agents with valuations $v_1(\{1,2\})=2$, $v_2(\{2,3\})=3$, $v_3(\{3\})=2$, so $S_1=\{1,2\}$, $S_2=\{2,3\}$, $S_3=\{3\}$. Then the corresponding LP is
$$\max v_1(S_1)*x_1 + v_2(S_2)*x_2 + v_3(S_3)*x_3\\
s.t.\\
x_i\leq 1 \ \forall i\\
x_1 + x_2 \leq 1\\
x_2 + x_3 \leq 1\\
x_i\geq 0$$
The contraints mean that "at most one from $S_1$ and $S_2$ can be chosen and at most one from $S_2$ and $S_3$".

I don't know why you added this in your second constraint:

  ..., and which is a maximal set with that property, ...

I would model it simply as: "For every two agents $x_i$ and $x_j$, if their sets $S_i$ and $S_j$ intersect, then $x_i + x_j \leq 1$"
$$
x_i + x_j \leq 1 \quad \forall (i,j): i \lt j \text{ and } S_i \cap S_j \neq \emptyset$$

Notice that every row in the constraint matrix has exactly two ones, and we can think of it as a bipartite graph, which is TUM.

This matrix is not TUM, and there is no guarantee that it will provide Integer Solutions, as we can see in the counter-example:
$$ S_1 \cap S_2 \neq \emptyset, S_1 \cap S_3 \neq \emptyset, S_2 \cap S_3 \neq \emptyset $$
\begin{bmatrix}
1 & 1 & 0\\
1 & 0 & 1\\
0 & 1 & 1\\
\end{bmatrix}

That doesn't mean that your problem does not have an integer optimal solution, simply that this Linear Formulation will not always yield an integer solution. For example, the solution of your LP might be $x_1 = 0.23848$, which satisfies all the constraints and is the optimal solution, but it is not integer.

If your goal is to solve this problem, and get the Integer Optimal Solution, you can use an Integer Linear Formulation and use any ILP solver to get to that solution.

The Integer Linear Formulation allows constraints like $ x_1 \in \{0, 1\}$, that will ensure that this variable will be either 0 or 1.

The purpose of proving that it is TUM, is to avoid using Integer Linear Formulations, since they are slower to solve than Linear Programs.


Circular queue problem In ciruclar queue the following command statement is very useful to use the determine the unused location. What is its importance? I know that without this line it won't be a circular queue. But how to say it in theoretical way?
rear=(rear+1)%max

Suppose that we arrange the numbers $0,\ldots,n-1$ in an oriented cycle. The number which follows $i$ is $i+1$ for $i \neq n-1$, and $0$ for $i=n-1$. We can combine both cases by saying that the number following $i$ is $i+1 \bmod{n}$.


How to detect intersecting segments based on length of the segments As part of a larger problem, I am trying to detect based on the distance matrix which segments intersect in the original 2D space that originated the matrix. I don´t have coordinates (lat/long, x/y or any other for the points).

As an example, on the image below, the answer to the question for the top graph would be: AD, BC. While for the bottom graph would be AC, BD.

The information that we have is just the distance matrix:

DISTANCE MATRIX TOP

$
\begin{align}
 && A && B && C && D \\
A&& 0 && 1 && 1 && \sqrt{2} \\
B&& 1 && 0 && \sqrt{2} && 1 \\
C&& 1 && \sqrt{2} && 0 && 1 \\
D&& \sqrt{2} && 1 && 1 && 0
\end{align}
$

DISTANCE MATRIX BOTTOM

$
\begin{align}
 && A && B && C && D \\
A&& 0 && 1 && 1 && \sqrt{2} \\
B&& 1 && 0 && \sqrt{2} && \sqrt{5} \\
C&& 1 && \sqrt{2} && 0 && 1 \\
D&& \sqrt{2} && \sqrt{5} && 1 && 0
\end{align}
$

I have tried so far to use the triangular inequality and some other (probably) naive geometric knowledge but I can´t figure out what conditions must be met.

First assume that you know where $A,B,C,D$ are.  In this case, you can write $D$ uniquely in the form $\alpha_A A + \alpha_B B + \alpha_C C$, with $\alpha_A + \alpha_B + \alpha_C = 1$. The tuple $(\alpha_A,\alpha_B,\alpha_C)$ are called the barycentric coordinates of $D$.  You can read off which of the segments $Dx$ ($x\in \{A,B,C\}$) cross a side of the triangle $ABC$ from the sign pattern of the barycentric coordinates.

It's not particularly difficult to find suitable coordinates either.  You can just assume that $A=(0,0)$, $B=(d(A,B),0)$, and $C$ is either intersection point of the appropriate circles around $A$ and $B$.  This will then uniquely determine $D$ by intersecting three circles.


Injectivity verification in o(n) space and O(n) time The problem I want to solve is this: Given a list $A$ of $n$ elements, I want to verify that they are all distinct. If I were to do this "myself", I would need $O(n)$ space and $O(n\log n)$ time to solve it, e.g. via a hashmap or binary tree. Luckily, I have an untrustworthy but omnipotent oracle ally who is willing to give me hints on how to solve the problem.

The oracle is allowed to provide me $O(n)$ of hints, and I want an algorithm that will read $A$ and the oracle input (both read only) and determine either that $A$ has no duplicates, or that the oracle has given me a bad hint, in time $O(n)$ and much smaller read-write space ($O(1)$ or $O(\log n)$).

Can it be done?

You haven't specified your exact computation model, so let me assume that you measure space in words of length $\Theta(\log n)$, and that each element in the array occupies one word. Let me assume furthermore that you can compare two elements in constant time.

The oracle should provide you with the relative order of the elements, say as an array $B$ whose entries are the numbers $1,\ldots,n$ in the appropriate order. This advice takes $O(n)$ words, and can be verified in $O(n)$ time and $O(1)$ additional space.

In slightly more detail, here is the verification algorithm:

for i from 1 to n:
  verify that 1 ≤ B[i] ≤ n
for i from 2 to n:
  verify that A[B[i-1]] < A[B[i]]

Let us prove that  there exists an array $B$ for which the verification succeeds iff $A$ consists of distinct elements.

$\longleftarrow$ Suppose that $A$ consists of distinct elements. Order $A$ in increasing order: $A[j_1] < \cdots < A[j_n]$. If we take $B[i] = j_i$ then the verification will succeed.

$\longrightarrow$ Suppose that the verification succeeds for some array $B$. Then $A[B[1]] < \cdots < A[B[n]]$. This implies that $A$ contains at least (and so exactly) $n$ distinct elements.


Show that,with the array representation for sorting an n-element heap, the leaves are the nodes indexed by n⌊n/2⌋+1,⌊n/2⌋+2,…,n The Question of the CLRS $6.1-7$ exercise reads as:

    Show that, with the array representation for sorting an n-element heap, the leaves are the nodes indexed by $\lfloor n / 2 \rfloor + 1, \lfloor n / 2 \rfloor + 2, \ldots, n⌊n/2⌋+1,⌊n/2⌋+2,…,n$.

I looked for the solution here:
https://walkccc.github.io/CLRS/Chap06/6.1/

The solution was provided like this:

Let's take the left child of the node indexed by $\lfloor n / 2 \rfloor + 1.$

\begin{aligned} \text{LEFT}(\lfloor n / 2 \rfloor + 1) & = 2(\lfloor n / 2 \rfloor + 1) \\ & > 2(n / 2 - 1) + 2 \\ & = n - 2 + 2 \\ & = n. \end{aligned}

I can't understand this statement:
$LEFT(⌊/2⌋+1) > 2(/2−1)+2$

Please help me out.
Thank you.

So, basically in heap representation, $LEFT(i)$ refers to the index of $i's$ left child. What we want to show is that index $⌊/2⌋+1$ is a leaf and is not a middleware node which can be proved if we could show the index of the left child is larger than the number of elements in the heap.

On the other hand, $LEFT(⌊/2⌋+1) = 2(⌊/2⌋+1) = 2⌊/2⌋+2 $ and with removing those brackets around the $n/2$ we can show that it is larger than $2(n/2-1)+2 = n$.


optimal flow for index multiple source and destination in directed graph I am facing the similar problem to max flow in multiple source-destination directed graph (which has a familiar solution of connecting all the sources to one source and the same for the destination, and solving it with some algorithms like Ford-Fulkerson), but the difference in my problem is that :

all edges has capacity of 1 (the flow is discrete so once an edge is used - it can't be used again)
each source need to flow to a specific destination (e.g. $v_1$ needs to flow to sink $u_1$ - other sinks can't consume $v_1$ flow).

I need to find the max sources that can reach to their destination on a given graph. Is there a solution for this or I have to compute all the possiblities ?

This is an instance of a multi-commodity flow problem.  Unfortunately the problem is NP-hard (even when all edge capacities are 1).


Are there other ways to describe formal languages other than grammars? I'm looking for mathematical theories that deal with describing formal languages (set of strings) in general and not just grammar hierarchies.

There are plenty of possibilities. Others have already mentioned automata which offer a rich selection. Consider the following frameworks, too:

Some languages can be defined directly by (co)inductive definitions. For instance, the smallest fixpoint of
$\qquad \begin{align*}
  \phantom{a} \\
  &\phantom{\Rightarrow}\ \varepsilon \in L \\
  w \in L &\Rightarrow aw \in L \\
  aw \in L &\Rightarrow baw \in L \\
  \phantom{a}
\end{align*}$
is the same language as the one described by $(ba\mid a)^*$, the largest fixpoint is $(ba\mid a)^\omega$. Note that such a definition can also be written in calculus or inference rule form:
$ \qquad \begin{align*} \phantom{a}\\
  \frac{}{\varepsilon}, \quad \frac{w}{aw}, \quad \frac{aw}{baw} \\
  \phantom{a}
\end{align*}$
Words define word structures that can be used as models of logical formula. Essentially, every word defines the domain of its positions $D_w = \{1, \dots, n\}$, predicates $P_a : D \to \{0,1\}$ so that $P_a(i) \Longleftrightarrow w_i = a$ for all $a \in \Sigma$, a predicate $<$ that is $<$ from $\mathbb{N}$ restricted to $D_w$ and a predicate $\operatorname{suc} : D_w \times D_w \to \{0,1\}$ that is true if and only if the second parameter is the direct successor of the fist.
So for instance, if $w = aababaab$ then
$ \qquad \begin{align*} \phantom{a}\\
  S_w \models \forall\, i. \forall\, j.\ (P_b(i)\ \land\ \operatorname{suc}(i,j)) \to \lnot P_b(j); \\
  \phantom{a}
\end{align*}$
in fact, this first-order formula defines---via the set of all word structures that fulfill it---the same language as $(ba\mid a)^*$. The corresponding $\omega$-language $(ba\mid a)^\omega$ is described by the LTL formula
$ \qquad \begin{align*} \phantom{a}\\
  \square\,(P_b \to\bigcirc(\lnot P_b)) \\
  \phantom{a}
\end{align*}$
Several equivalences between classic language classes and certain logics are known. For example, FO corresponds to star-free languages, weak MSO to regular languages and MSO to $\omega$-regular languages. See here for references.
Something orthogonal to classic classes are pattern languages. Assume a terminal alphabet $\Sigma$ and a variable alphabet $X=\{x_1, x_2,\dots\}$. A string $p \in (\Sigma \cup X)^+$ is called a pattern. Let $\mathcal{H}= \{\sigma \mid \sigma : X \to \Sigma^*\}$ the set of substitutions. We define the language of a pattern $p$ as
$ \qquad \begin{align*} \phantom{a}\\
  \mathcal{L}(p) = \{\sigma(p) \mid \sigma \in \mathcal{H}\}. \\
  \phantom{a}
\end{align*}$
Note that $\sigma$ is extended to work on patterns; terminal symbols are left unchanged.
As an example, consider $\mathcal{L}(x_1abbax_1)= \{wabbaw\mid w \in \{a,b\}^*\}$.
Note that we allow substitutions to delete variables; some properties of the class of pattern languages are hugely different for deleting vs. non-deleting substitutions. Pattern languages are of particular interest in Gold-style learning.


What was the major breakthrough between Hoare-Floyd logic and Scott–Strachey semantics? I'm reading through a commentary on Milner's "The use of machines to assist in rigorous proof" by Mike Gordon. In this paper, he explains how LCF was born from the ideas of denotational semantics by Dana Scott and Strachey.

It seems to me that Floyd-Hoare logic wasn't enough for developing LCF, but I'm not sure why this is the case. At the end, in Hoare logic we deal with program states that satisfy some precondition $P$ and that through a relation $r$ conform to some postcondition $Q$ and I can provide a formula for this. Wikipedia claims that denotational semantics:

  is an approach of formalizing the meanings of programming languages by
  constructing mathematical objects (called denotations) that describe
  the meanings of expressions from the languages.

I'm familiar with some intuitions on how for instance recursion is modeled in this approach as a fixed point of some relation while in Hoare logic I didn't really remember dealing with recursion. Still both approaches seem to try to describe relations between inputs and outputs using mathematical relations.

Question

So what is it that made a difference between Hoare logic and denotational semantics? Does denotational semantics manage better some complexities of programs? If so, please illustrate with an example.

Maybe the following quote of Milner referring to denotational semantics is interesting to guide your answer:

  I could write down the syntax of a programming language in this logic
  and I could write the semantics in the logic.

I don't know why people didn't develop Hoare logics for lambda-calculi earlier. The first work to get this right was Honda et al's

A Compositional Program Logic for Polymorphic Higher-Order Functions

There were some earlier attempts before this, but they didn't quite nail the problem, for example: how do you denote the value of a functional program? What piece of syntax corresponds to the function space constructor? There are a couple of little things that need to be gotten right.

Let me speculate: maybe the main issue was that Hoare logic was typically concerned with stateful computation. If you combine state and higher-order functions, you immediately have to deal with aliasing, e.g. programs like

$$\lambda x^{\mathsf{Ref(Nat)}}.\lambda y^{\mathsf{Ref(Nat)}}.(x := !x+1; y := !y+1),$$ as well as local store and recursion through the store. These were only solved in the early 2000s in works like An observationally complete program logic for imperative higher-order functions (recursion through the store); A logical analysis of aliasing in imperative higher-order functions (aliasing), Logical Reasoning for Higher-Order Functions with Local State (full local store). At the same time Separation logic tackled the aliasing problem form a different angle.

This work has been implemented in Coq by A. Charguéraud in his work, and that  is also used in the Javascript semantics now.


How does the cache / memory know where to return results of read requests to? The pipeline of a modern processor has many stages that may issue read
requests to main memory, e.g. in fetching the next command or loading
some memory location into a register. How is the result of a read
request returned to the right pipeline stage, given that there are more than one possible recipients?
Since most CPUs access main memory via a cache hierarchy, the question
becomes: how does the L1 cache know which part of the pipeline to
return a result to?
I imagine that access to the L1 cache is queued, but each access
presumably needs a 'return address'. How is this typically handled?
Processors tend to have a LSU (= load-store unit), see [1, 2] for example, but those descriptions tend not to mention how  read data finds its recipient.

RISC-V Boom, The Load/Store Unit (LSU).

Arm, Load Store Unit (LSU).

Every machine instruction encodes the source and destination registers and/or memory locations. For memory location, some temporary buffer (register) within the processor is used. If the memory location happened to be in the cache, the stage of pipeline which depends on the content of memory location, stalls for few cycles.
Also, there are buffer registers between every pipeline stage, that stores the input for next stage and output of previous stage. If the processor is superscalar, i.e., multiple instructions can be in flight at a certain point of time, then multiple copies of buffers are maintained. Since the instruction can be executed Out-of-Order on superscalar processors, buffers like ROB (re-order buffers) are maintained for every hardware (SMT) threads. Put simply, multiple register sets which are copies of processor register sets are maintained within a processor.
In other words, Control unit that control the instruction execution cycles, appropriately route the content of memory location to marked registers. Registers are either specified by instruction code or determined by control unit itself.


Why does MergeSort have O(n) space complexity if it splits the array log(n) times? I know this is a common algorithm with plenty of analysis, but when I searched for an answer the only one I found was "Merge Sorting has O(n) auxiliary space because it copies the array into L and R".

I don't understand this because as it is called recursively, before performing any operations, the entire array is still split log(n) times. When following the binary tree diagram representing the recursion, we see (if n=16) it splits into 2x8, 4x4, 8x2, 16x1.

Since all of these splits occur prior to any merging, why is the auxiliary space O(n) and not O(nlog(n))?

Yes, you can implement merge sort inefficiently, but you don’t have to.

If you sort an array, notice that you don’t need to create any copies while splitting into subarrays. You only need two integers to identify each of them. Combined with the fact that the number of nodes in the recursion tree is $O(n)$, this gives you $O(n)$ bound on space.


How can I teach computer science without using computers? In some places in the world, people don't usually have access to (and hence little knowledge of) computers, and even if they have, hard- and software are outdated and usage plagued by power outages and such. Access to (good) books also tends to be lacking. How can I teach computer science under such circumstances?

I'm worried that without being able to do experiments and apply what they learn, they won't learn (well) at all even though they are incredibly motivated and devote most of their time to this hobby. Is it possible to teach CS only theoretically?

Asking how you can study computer science without computers is a bit like asking how you can study cosmology without telescopes. Sure, it's nice to be able to look at the things you're studying and it's often very helpful to be able to play around with things. But there's a whole lot you can do without access to a computer: in extremis, you could probably do almost all of a undergrad course with no computers.

In practical terms, access to computers helps reinforce a lot of what you learn in a computer science course. Programming courses are, obviously, much more natural with access to a computer. On the other hand, being forced to write code on paper does encourage people to think about their code and make sure it really works, rather than just running it through a compiler again and again until it compiles and then running trivial test cases again and again until the obvious bugs go away.

Topics that would be most natural without computers would be the more mathematical ones. All the background mathematics, such as combinatorics and probability. Computability, formal languages, logic, complexity theory, algorithm design and analysis, information and coding theory. Anything to do with quantum computation!


How is the Longest Common Sub-sequence of two sequences is a special case of the Sequence Alignment problem? Could anyone briefly show me how the Longest Common Sub-sequence of two sequences is a special case of the Sequence Alignment problem? I cannot wrap my head around this. Thank you.

The problem of finding a longest common subsequence can be answered by
computing the alignment where match is rewarded by +1 while mismatch and
insdel penalty are both 0.