Hardness of finding a true or a false assignment into a generic boolean formula? I read some research that analyzes the hardness of SAT solving in the average case.
In fact, for a 3CNF formula if you compute the ratio of clause to variables there is an interval (more or less between 4 and 5) in which solving the formula is hard. But it is easy (between 0 and 4) high probability of satisfiable assignment and high probability of unsatisfiable assignment after ratio 5.

My question is, what about a generic formula that is not in normal form. We can say something about its hardness?

You can always convert your formula or circuit to an equivalent CNF formula of polynomial size.

The result you mention is only for 3CNF formulas. In general for kCNF-SAT the assumed threshold phenomenon happens on a point depending on $k$, the values you mention are only for 3CNF-SAT.

Also remember what these result say is w.h.p. in a particular distribution of k-CNF formulas. It doesn't mean that this will hold for all formulas. In fact it is quite easy to come up with formulas that have values mentioned in the range but are easy and also formulas that are outside this range but are hard (think about padding formulas to obtain your desired ration). So given a particular 3CNF formula with some clause ration, you can't say anything about its difficulty (or the time it will take a particular SAT solver to solve it).


Minor Mistake in Computability, Complexity, and Languages? In the book Computability, Complexity, and Languages (2nd edition), Martin Davis writes in chapter 1 (Preliminaries), section 2 (Functions):

  A partial function on a set $S$ is simply a function whose domain is a subset of $S$. An example of a partial function on $\mathbb{N}$ is given by $g(n) = \sqrt n$, where the domain of $g$ is the set of perfect squares.

So far so simple. But he goes ahead and writes a couple lines later at the end of the section:

  We will sometimes refer to the idea of closure. If $S$ is a set and $f$ is a partial function on $S$, then $S$ is closed under $f$ if the range of $f$ is a subset of $S$. For example, $\mathbb{N}$ is closed under $f(n) = n^2$, but is not closed under $h(n) = \sqrt n$ (where $h$ is a total function on $\mathbb{N}$).

So in the first quote $\sqrt n$ on $\mathbb{N}$ is an example for a partial function, whereas in the second quote the same function is an example for a total function.

Both examples seem to contradict each other. Or am I missing something in regard to closures here?

There's no contradiction, here.  The first case defines the partial function $g\colon \mathbb{N}\to\mathbb{N}$ given by
$$g(n) = \begin{cases}
 x &\text{if $x\in\mathbb{N}$ and }x^2=n\\
 \text{undefined} &\text{if no such $x$ exists.}
\end{cases}$$
As the text says, "the domain of $g$ is the  set of perfect squares."

The second case defines the total function $h\colon\mathbb{N}\to\mathbb{R}$ given by
$$h(n) = x \quad \text{if }x\in\mathbb{R}_{\geq 0} \text{ and } x^2=n\,.$$
The domain of $h$ is the set of all the natural numbers.

You say that these are the same function, but they are not. $g(2)$ is undefined but $h(2)$ is defined (and equal to $\sqrt{2}$). $h$ associates a square root with every natural number but $g$ only associates square roots with natural numbers that are perfect squares.

$\mathbb{N}$ is closed under $g$ because, whenever $g$ is defined, $g(n)\in\mathbb{N}$. $\mathbb{N}$ is not closed under $h$ because, for example, $2\in\mathbb{N}$ but $h(2)\notin\mathbb{N}$.


Why are problems in P easy and other problems not Problems in $P$ have polynomial time algorithms. Problems in e.g. $NP-complete$ are only solvable in "probably exponential time" (Shen Lin's PET).

Problems in $P$ are considered easy while others (most likely) are not.

What does easy mean?
I've always thought of hard and easy this way:

Our computing power grows exponentially over time. A problem is called easy if we can solve exponentially more instances of it (in reasonable time) after each time unit. A problem is hard if we can only solve polynomialy more instances of it after each time unit.

I'm well aware of complexity analysis, the definitions and their meaning. I'm trying to propose a reasonable, intuitive and easy to understand explanation of hard and easy. Would the explaination above explain it correctly and would someone who never heard of the subject understand it?

Your definition of "easy" doesn't make much sense. What exactly does "solving more instances at each time unit" mean?

Usually our notion of hardness refers to our ability to "solve" one instance. More formally, let $T(n)$ be the amount of operations required (proportional to time) for inputs of size $n$, then by "hard" we usually mean that $T$ grows too fast.

As for why polynomial $T(n)$ is considered easy, see this question.


How to find all "nearly roots"? Let $G=(V,E)$ a directed graph. We define $v \in V$ to be "nearly root" of there's a path from $v$ to at least $|V|/2$ vertices. How do you find the set of all "nearly roots" in linear time?

What we've tried is to build the strongly connected graph $G_{scc}$ obtained from $G$ and then to do a topological sort. Now we went backwards and for each $U\in G_{scc}$ we count how many vertices it can reach by scanning all outgoing edges and summing up all vertices reachable from it's successors. This seems wrong since we may count vertices more than once.

The following algorithm will solve your problem

Strategy

The task is decomposed into 2 subtasks:

Derive an annotated DAG from $G$.
Contract cycles in $G$ to single nodes while traversing the implied spanning tree of a DFS, creating a graph $G'$,
Conduct a BFS on $G'$ with reversed edge orientations, identifying and marking nearly roots.

Details

Perform a DFS on $G$. It's used as a tool to identify and contract cycles while keeping tabs on the number of contracted nodes.
For cycle contraction it suffices to detect backward edges ( mark/unmark nodes when entering a node for the first time / leaving it for the last time ). Each time a backward edge $(w, v)$ has been detected, all nodes on the current DFS path $p = v \stackrel{*}{\rightarrow} w$ are coalesced into a new node $v'$, edges from nodes on $p$ are retained. These modifications can be done in situ ( $V_{i} := (V_{i-1} \ \{ x \in V_{i-1} | x \in p \}) \cup \{ v' \}$, $E_{i} := (E_{i-1} \ \{ (x,y) \in E_{i-1} | x \in p \}) \cup \{ (v',y) \in V_{i}^2 | y \notin p \})$ for the $i$-th contraction, starting with $(V_0, E_0) := (E, V)$). Mark each node in $V_{i}$ with an attribute represents containing the number of nodes from $V$ it represents (i.e. initialising this attribute with $1$ and adding the cycle length subtracted by $1$ for each contraction). in case of contracted nodes also record the represented nodes by adding it to a stack attribute.
The resulting graph $G'$ is cycle-free (in particular: irreflexive). Next perform a BFS on $G'$ with all edges reversed. Propagate an attribute reachable: $V \rightarrow \mathbb{N}$ along the way which locally computes as $\text{reachable}(v) := (\text{represents}(v) - 1) +  \sum_{w \in pred(v)\subset V'} \text{reachable}(w)$ with pred denoting the set of predecessors  and reachable being initialised to $0$ for all maximal elements in $G'$. for all nodes $v \in G'$ with $\text{reachable}(v) \geq |V|/2$, mark all represented nodes from the original graph $G$ as nearly roots.

Complexity

Complexity of this operation is $O(E)$, as each edge is traversed at max 2 times in the course of the DFS and the contraction while the bookkeeping operations are $O(V)$ in total.
Complexity of this operation is $O(E)$, as each edge in $G'$ is traversed once during the BFS and $|E'| \leq |E|$. Updating reachable is $O(V')$ while marking the nodes from $G$ as nearly roots costs at most $O(V)$.


Intuitive explanation of Hoare assignment axiom $\small\textit{''The obvious things are the most difficult to understand''}$

May be the question does not make sense, but let me ask it anyway.

The Hoare assignment axiom is
$$
\dfrac{}{\{Q[v \mapsto expr]\} \;\; v:=expr \;\; \{Q\}}
$$

Is there an intuitive explanation of the axiom?

I "agree" with the Floyd assignment axiom:
$$
\dfrac{}{\{Q\} \;\; v:=expr \;\; \{\exists old: Q(old,..) \land v=expr(old,...)\}}
$$
which can be thought as "if Q holds before the assignment, then after the assignment we know that the variables should satisfy: 1) Q(old) holds for some old variables (since we assume Q holds), 2) variable v has the new valueexpr(old,...)".

Is there a similar intuition for the Hoare assignment axiom?

Hoare Logic proceeds backwards. It is a method to compute a precondition such that the desired postcondition holds. In fact, the inference rules given in your standard Hoare Logic deductions compute weakest preconditions, or the most "specific" precondition that still guarantees that the post-condition holds at the next program point.

I think this is the salient difference. There's no comparable interpretation (of reasoning about the next program point) for backwards predicate transformers because we have to reason about the "state" before an operation given that we know its "state" after. In comparison, the alternative axiom reasons about the postcondition given a precondition.

Now, the two axioms are duals of each other, in the sense that the backwards axiom computes a weak precondition while the forward axiom computes a strong postcondition (most "general" postcondition such that all possible postconditions are subsumed). Logically, they are equivalent. Therefore, not only do we have a singular backwards intuition of the Hoare axiom, but we should also have some sort of connections between the intuitions behind the backwards axioms and those behind the forward axioms.

The intuition behind the backwards axiom: This is actually relatively easy to see, given that you know what the deduction system is doing. Let's look at the Hoare assignment rule:
$$
\frac{}{\{P : Q [x \mapsto e]\} ~x = e ~\{Q\}}
$$
which roughly says that the weakest precondition of $Q$ preceding an assignment $x = e$ is just $Q$ with every occurrence of $x$ replaced by the expression $e$. To see this in action, say you have the goal $Q = (x^2 = 4)$ and you want to see if $x = 3$ satisfies this goal. Well, the assignment axiom tells us that we should transform this post-condition into $(x^2 = 4)[x \mapsto 3] \to (9 = 4) \equiv \bot$, which says that there is no precondition that can get us to the goal. On the other hand, a goal of $Q = (x^2 = 9)$ allows us to compute a weakest precondition of $(9 = 9) \equiv \top$, so any precondition will satisfy this program.
The connection between the forward and backward systems: Recall that we said that the two deduction systems are duals of each other. In other words, given a deduction (in the form of an inference rule) in the forward system, we can infer a similar deduction (in the backward system) by joining the leaves/exit points of this tree together, and inverting the proof. In other words, there's a (rough) correspondence. Suppose that the forward system is characterized by the rule function $F$, such that $F(\{\phi_1, \dots\}) e$ returns the set of propositions that might hold after executing $e$ given that we know $\{\phi_1, \dots\}$ before hand. Similarly, we also have a backwards rule function $B$, such that $B(\{\psi_1, \dots\}) e$ returns the set of propositions that must be true before $e$ so that $\{\psi_1, \dots\}$ holds afterwards. We can see that
$$
Q = B(F(Q))
$$
(though the other direction $Q = F(B(Q))$ does not necessarily hold, since $B$ can produce $\bot$ and $F(\bot) = \bot$)


Enumerate all valid orders of subset sums Given an positive integer $n$, we define an order of subset sums (or simply, an order, when there is no ambiguity) to be a sequence of all subsets of $\{1,\ldots,n\}$. For example, when $n=2$, the sequence $\emptyset,\{1\},\{2\},\{1,2\}$ is an order.

We call an order $S_1,\ldots,S_{2^n}$ valid if there exist real numbers $0<x_1<\cdots<x_n$ such that $\sum_{i\in S_1}x_i<\cdots<\sum_{i\in S_{2^n}}x_i$. For example, when $n=2$, the sequence $\emptyset,\{1\},\{2\},\{1,2\}$ is a valid order, but the sequence $\emptyset,\{1\},\{1,2\},\{2\}$ is not because we cannot make $x_1+x_2<x_2$.

The question is, given $n$, how to enumerate all possible valid orders. To output an order $S_1,\ldots,S_{2^n}$, it is sufficient to output an algorithm that generates this order, i.e., an algorithm with no input (the parameter $n$ is built-in) that outputs $S_1,\ldots,S_{2^n}$ in order, as long as the algorithm runs in $O(n2^n)$ time. Even so, this problem still cannot be solved in time polynomial in $n$, because there may be exponentially many valid orders, thus an algorithm running in exponential time is welcome.

A trivial algorithm would be to iterate over all possible orders, and check for each one if it is valid. But I cannot even find an (efficient) way to check if an order is valid.

Here is one algorithm that runs in doubly exponential time -- so probably useless.  In other words, this answer is probably not useful.

You can check whether an order is valid in $2^{O(n)}$ time (i.e., $\text{poly}(2^n)$ time) by reducing to linear programming: you obtain $2^n+n-2$ linear inequalities in $n$ variables, and you can test for feasibility in time polynomial in the number of inequalities and variables.  Then, enumerating over all possible sums and checking if each is valid would yield a $(2^n)! 2^{O(n)} = 2^{n 2^n + O(2^n)}$ time algorithm.  This will be ridiculously slow in practice.

To improve this, you could use an iterative pruning / branch-and-bound style algorithm.  Given a prefix $S_1,\dots,S_k$ of an order, we can test whether it is valid using linear programming as above.  If it is not, we don't consider any order that starts with this prefix.  In other words, do breadth-first search: first choose $S_1$, then choose $S_2$, then choose $S_3$, and so on, at each step checking whether the prefix obtained so far is valid.

This may still be extremely slow, as there is the possibility that a prefix $S_1,\dots,S_k$ is valid but there is no way to complete it to a full order $S_1,\dots,S_{2^n}$ that is valid, so this might do a lot of wasted work.


Checking the existence of a pattern in a given prefix I need to design an algorithm that given a string $T$ of length $n$, performs $O(n)$ preprocessing, and can then answer queries of the sort "does a string $P$ of length $m$ appear in $T$ before position $k$" in time $O(m)$. The algorithm should use a suffix tree.
Unfortunately there are not any good bioinformatics books with fair examples and practical methodologies. Dan Gusfield's book does not offer a solution manual.

Recall that in a suffix tree for $T$, each leaf corresponds to a suffix of $T$, and is labeled by its position. Furthermore, each internal vertex corresponds to a common prefix of some suffixes of $T$. We label each internal vertex with the minimal position of a suffix covered by it.
Construct a suffix tree for $T$, and augment it by labeling the internal vertices as described above. Given a pattern $P$, traverse the suffix tree to find the vertex corresponding to $P$ (it might correspond to some extension of $P$), and check whether the minimal position written there implies that $P$ occurs before position $k$.


How can I write this simple function in mathematical notation? POINTS_TABLE = [3, 5, 7, 1]

function score(answer) {
  result = 0
  for i in 0..4
    result += POINTS_TABLE[answer[i]]
  return result
}

answer = [1, 2, 1, 0]

s = score(answer)

The sum performed is 5 + 7 + 5 + 3 = 20. It uses the values from the input as the indexes to read from the POINTS_TABLE.

This is the style of the answer I'm trying to work out:
\begin{equation}
score(answer) = \sum_{i=1}POINTS\_TABLE_{answer_i}
\end{equation}

While you are free to use whatever notation you want, as long as you explain it, it seems that the simplest solution here would be

  $$ score(answer) = \sum_{i=0}^3 POINTS\_TABLE[answer[i]] $$

This should be self-explanatory in most circumstances.


How should I design a hash table where all the keys are permutations? I need to create a hash table to store values for (possibly all) permutations of 123456789, which is exactly 362 880 keys.

Given that I know how all the keys look up front, it seems I that there should be an optimal hashing function, and an optimal size of the table to store the values in.

Is this true? If so, how can I create the perfect hashing function? And also, how can I determine the optimal size for the hash table?

update: I'm looking to store all of the possible permutations, where each will be stored only once, which means the table should in the end contain exactly all 362 880 keys (since I have a hard limit on my algorithm for which I need to optimize my worst case scenario.)

Simply compute the index of the permutation into the sorted list of all permutations and use that as your hash key. This can be achieved with a relatively simple algorithm: https://stackoverflow.com/questions/5131497/find-the-index-of-a-given-permutation-in-the-sorted-list-of-the-permutations-of

Once you have that index, you can make a table with exactly 9! slots - you have a perfect hash over your input domain.

For example, for n=3, the hash function produces

123 -> 0
132 -> 1
213 -> 2
231 -> 3
312 -> 4
321 -> 5


How large is the seed in an encryption algorithm such as stream cipher? The stream cipher is an encryption algorithm that was designed to approximate an idealized cipher, known as the One-Time Pad. It's crucial for a stream cipher to remain secure is to have a pseudorandom generator that hard to predictable and a seed that was never used. For this to be achieved, I assume we need to have a really large seed that the most powerful computer can't predict, but I can't approximate how large the number is.

The seed of a pseudorandom generator that is used as a stream cipher is called a key.
The most common key sizes are 128 bits and 256 bits. (That's symmetric keys, where there's no cheaper way to break than brute force. Asymmetric cryptography typically relies on keys having certain mathematical properties that make the algorithm work, but also enable better attacks than brute force.)
To understand how hard it is to break a 128-bit key, meaning that you have to try $p \cdot 2^{128}$ possibilities for a chance of success $p$, consider these orders of magnitude:

A fast processor might be able to try about one billion keys per second (1GHz).
A powerful attacker might be able to afford one billion processors.
The universe is about 1 billion billion seconds old (a little over 30 billion years).
1 billion is slightly less than $2^{30}$ ($2^{30} = (2^{10})^3 = 1024^3 \gtrsim (10^3)^3 = 10^9$).

So if you're extremely rich and willing to wait until the universe is twice as old, you can enumerate about $2^{120}$ keys. If you're only willing to wait 30 years, you can only enumerate about $2^{90}$ keys, giving you a chance of breaking any particular key of less than one in 250 billion. Conclusion: a 128-bit key is sufficient for security against brute force.
A 256-bit key provides a security margin that can cover:

Hypothetical advances in cryptanalysis that make the algorithm slightly easier to break.
Hypothetical advances in computation, such as quantum computers, which effectively halve the key size.
A very powerful adversary who tries to break basically every encrypted communication, and is interested in even succeeding for a tiny fraction.
A very powerful adversary who records basically every encrypted communication, and would detect if the same key is used twice, which could then let them discover the key by non-cryptographic means (exploiting a bug, demanding it at gunpoint, a subpoena, …). Due to the “birthday paradox”, there's a macroscopic chance that two instances will generate the same random key if the number of instances is at least about the square root of the number of possible keys, so 8 billion people using a billion different keys each (about $2^{63}$ keys in total) would be around the threshold for 128-bit keys.

In practice, key size just isn't an issue except in legacy software and protocols that are at least 2 decades out of date (keys shorter than 128 bits became obsolete when AES became the de facto standard in the early 2000s). Cryptography gets broken by non-cryptographic means or due to implementation weaknesses such as side channels, or gets circumvented altogether due to non-cryptography-related security vulnerabilities (binary exploits, escaping exploits, misconfigured controls, phishing, …). Cryptographic algorithms are usually the strongest part of information security.


How are Complex Numbers and Complex Analysis used in CS? The world is 3D and data of it is usually (as far as I know) represented and processed with real numbers. I've seen very few cases where complex numbers are used in programming and none when it comes to processing anything that doesn't explicitly require complex numbers.

How are complex numbers used it Computer Science and Programming? Which areas in CS/IT use it?

I haven't seen them pop up a lot in "Computer Science" per say but there are quite a few closely related fields where they are very present.

I can think of signal processing for example, where Fourier transforms and other complex transformations are fundamental tools. Designing filters for signals also often boils down to placing poles in the complex plane.

In  control theory and the analysis of complex systems you also sometimes analyse the stability of systems by looking at complex poles of algebraic fractions.

I imagine complex numbers must pup op a lot in quantum computing also, as a pure quantum state is represented as a complex vector in some basis.

I am only passingly familiar with the fields I mentioned so there might be a lot more ways complex numbers are used in them, and also a lot more fields I am not familiar with.


Example of typed lambda term with recomputed argument What is an example of a typed lambda term $\lambda x.\phi : A \to B$ and a term $a : A$ such that, when $\beta$-reducing the term $(\lambda x.\phi)(a)$, the argument $a$ must be repeated/recomputed several times?

In the simply typed $\lambda$-calculus with pairs, a simple example is

$$(\lambda x :T. (x,x))a$$

where $a$ is a term of type $T$.


Why is RTS/CTS optional? I was reading in Wikipedia about it and one of the main things that were pointed out was that it is only an optional mechanism. This bugs me more than it should as I cannot find any information that I can understand about it.

Can anyone explain to me like I am a five-year-old why are they optional?

Besides RTS and CTS, there are a few other "optional" signals such as DTR, DCD,...

These signals are mostly about checking if the other end of the cable is ready. Ready can mean that the internal buffer is not full, or related to some hardware condition, such as being powered or that the phone line is up ("DCD"=Data Carrier Detect).

These signals can be made optional in several cases :

The buffers are very large, or the datarate is low, and there is no practical risk of losing data. The endpoints are always ready. This is the case nowadays with computers used as terminal emulators over asynchronous serial lines.
Some flow control mechanism is used to signal over the data lines when to start and pause transmissions : For example XON / XOFF https://en.wikipedia.org/wiki/Software_flow_control
The protocol has messages and answers, for example an initiator sends a message of predefined lenght, and waits for the answer of the target. There are many other options, such as time-triggered communications. Serial lines can be used for many purposes. There are traditional terminal or teletype connections, there are also gazillions communications protocols for embedded or industrial applications. The protocols can be designed to not need hardware flow control signals.


Algorithm to determine which neighborhoods of a graph contain a given set of vertices S This question concerns determine which sets in a collection of sets contain a given subset S:

An undirected graph (V,G) is given with V= {1,..,m}, and   given via its neighborhood sets,  N(v_1),.., N(v_m).  A subset S  of V is given {v_{i_1}, .., v_{i_k}}.   The output will be the vertices whose neighborhoods contain S.  The size of the instance is m + |N(v_1)| +…+ |N(v_m)} =n.

Does there exist a linear time algorithm, or an n log n algorithm, or even a sub-quadratic algorithm for this problem?

My naive approach would be remove from set neighborhood set N(v_i) all vertices not in S and count remaining vertices—if |S|, put vertex i  in the output, and if not, do not put vertex i in S.

I don’t have experience with hash sets (learning on my own)   and don’t really understand why they are so efficient  (self-studying that) but any idea on a quick algorithm would be appreciated.

-Steve

In fact, the set of the vertices whose neighborhoods contain S is exactly

$$\bigcap_{j=1}^mN(v_{i_j})$$

Proof:

since it's an undirected graph, $v\in N(u) \Leftrightarrow u\in N(v)$. A vertices $v$ whose neighborhoods contain S means that $\forall u\in S, u\in N(v) $, which is equivalent to $\forall u\in S,v\in N(u)$, thus $\bigcap_{j=1}^mN(v_{i_j})$ is the desire set.

So the problem is equivalent to that:

  Given m (unordered?) lists, get the intersection of them

One can solve it in $O(n\log n)$ easily by maintain a balanced BST like a std::set.

Or just solve it in $O(n)$ by hashing.


Creating a binomial heap from an array in Θ(n) time I'm studying binomial heaps. A book tells me that insertion of a node to a binomial heap take $\Theta(\log n)$ time. So given an array of $n$ elements it would take $\Theta(n \log n)$ time to convert it to a binomial heap.

Does anyone know a method that can convert an array of numbers to a binomial heap in $\Theta(n)$ time? Wikipedia claims that insertion takes $O(1)$ amortized time but I need to refer to the worst case.

$O(f(n))$ amortized time means that if we make $k$ consecutive operations, total time does not exceed $k \cdot cf(n)$ for a chosen positive constant $c>0$.

In your case, each insertion is worst-case $O(\log n)$. However, they're amortized $O(1)$. It means that if you make $n$ consecutive insertions (that is, build a heap from an array), total time is bounded by $c \cdot n$ for some constant $c>0$ - that is, the total time is $\Theta(n)$.

If you want to prove formally that the total time of constructing $n$-element heap is $\Theta(n)$:

Denote $k$ as the current number of items in our heap (in the beginning, $k=0$).
Write $k$ in binary; if its $i$-th bit is set, we have a binomial tree of size $2^i$.
If you insert next element when there are already $k$ of them, you create a new tree of size $2^0$; if there was already a heap of size $2^0$, you merge them into a heap of size $2^1$; if there was already a heap of size $2^1$, you merge them and so on, until you find out there was no heap of size $2^t$ in a previous state. Time needed is thus proportional to the number of ones in the end of binary representation of $k$ (plus 1).
Note that we make first heap for every $k$; we'll make the second heap for each odd $k$, third heap for each $k \equiv 3 \mod{4}$ and so on. It means that $i$-th operation inside "merge-heap" will be done roughly once in $\frac{n}{2^i}$ insertions.

Now note that number of (constant time) create-tree/merge-tree operations cannot exceed
$$ \frac{n}{2^0} + \frac{n}{2^1} + \frac{n}{2^2} + \dots = 2n. $$

Thus, the total time for the algorithm "just make $n$ consecutive insertions" is $\Theta(n)$.


No number is equal to Zero, is this statement true or false? While reading an article on logic, there is a sentence "No number is equal to zero" and we have to assign truth values to this sentence. I hope this is true and the article says it as false.

Can someone explain me why it is false? Or the author of the article is wrong?

It is false if and only if there is a number that is equal to zero.

"There is a number that is equal to zero" is true if and only if zero is a number. Without any context (there might e.g. be some very strange definitions given earlier in the exercise), we cannot say whether zero is considered a number in this case. If there is no other context given in the exercise, it should be clear that zero is a number.

For example, the domain of discourse might be only positive integers*, when zero is not a number, but then it would be very weird to use the word "zero" in the sentence in the first place.

*The set of natural numbers has two contradicting definitions, $\mathbb{N}=\{0,1,2,\dots\}$ (non-negative integers) and $\mathbb{N}=\{1,2,\dots\}$ (positive integers). This might be the source of confusion in your case.


Why aren't there computers with a base different than 2? Wouldn't non-digital computers, those that use a base higher than 2, be faster and more efficient? Especially with Moore's law reaching its limit, wouldn't circuits that have three, four or five states have advantages? Are there computers like that?

As mentioned in this thread here, this is more due to the electronics of how computers work.  It's a lot easier to create an on-off switch then it is an on-off-middle switch.  If you're really curious about this, I'd recommend reading about how a computer works at the electronic level, as just doing this on-off switch took a lot of time for people to make properly.

That being said, there are computers coming that work with more than one state, mainly in the form of quantum computers.  They can have an on and off state, as well as a "both" state if I'm not mistaken.  There are of course advantages such as potential speed boosts from computers like this (though mostly from the way they work physics wise), but then there are also physical limitations imposed as well, such as the fact that they need to be kept incredibly cold to work properly from what has been experimented with so far.  Quantum computers are the "main focus" of how to solve the issue of Moore's Law currently though.

But long story short, yes, computers that "use a base higher than 2" could be faster and more effecient, and there are computers like that, but they aren't ready for the mass populations of the world to use yet.


Equivalence from multi-tape to single-tape implies limited write space? Suppose I have the following subroutine, to a more complex program, that uses spaces to the right of the tape:

$A$: "adds a $ at the beginning of the tape."

So we have:
$$
\begin{array}{lc}
\text{Before }: & 0101\sqcup\sqcup\sqcup\ldots\\
\text{After }A: & \$0101\sqcup\sqcup\ldots
\end{array}
$$

And it is running on a multi-tape turing machine. The equivalence theorem from Sipser book proposes we can describe any multi-tape TM with a single-tape applying the following "algorithm", append a $\#$ at every tape and then concat every tape in a single tape, and then put a dot to simulate the header of the previous machine, etc, etc.

With $a$ and $b$ being the content of other tapes, we have:
$$
a\#\dot{0}101\#b
$$
If we want to apply $A$ or another subroutine that uses more space, the "algorithm" described in Sipser is not enough, I can intuitively shift $\#b$ to the right, but how to describe it more formally for any other subroutine that uses more space in the tape? I can't figure out a more general "algorithm" to apply in this cases.

Sipser's book handles this case:

  If at any point $S$ moves one of the virtual heads to the right onto a $\#$, this action signifies that $M$ has moved the corresponding head onto the previously unread blank portion of that tape. So $S$ writes a blank symbol on this tape cell and shifts the tape contents, from this cell until the rightmost $\#$, one unit to the right. Then it continues the simulation as before.


An algorithm for k-way array partitioning I am trying to implement samplesort in MPI. The first step of samplesort is to partition the array with $n - 1$ splitters $s_1, s_2, \cdots, s_{n-1}$ into $n$ subsequences, where subsequence $i$ all have values in the range of $[s_i, s_{i + 1})$ (let $s_0 = -\inf, s_n = \inf$).

My question is: how to implement this efficiently, preferably in place?

I can't even figure out how to do it out of place, other than allocating $n$ dynamic sized arrays and finally concatenating them together. In the case of single splitter, we can successively push the values smaller and larger than the splitter to the two ends respectively, but for more splitters, I don't know how to do it efficiently.

I can't even figure out how to do it out of place, other than allocating n dynamic sized arrays and finally concatenating them together.

Which is the approach used by the explanation in Wikipedia, so it's not necessarily a bad one.

  My question is: how to implement this efficiently, preferably in place?

I assume you know how to do a quicksort partition. To do the multi-way split in place, you can turn it into a series of quicksort partitions.

# Splitters are sorted
# min and max indices are inclusive
multipartition(array A, int Amin, int Amax, array Splitters, int Smin, int Smax):
    if Amax <= Amin:
        return
    if Smax < Smin:
        inner_sort(A, Amin, Amax)
    else:
        Smid = Smin + (Smax - Smin) / 2
        split_idx = partition(A, Amin, Amax, Splitters[Smid])
        multipartition(A, Amin, split_idx - 1, Splitters, Smin, Smid - 1)
        multipartition(A, split_idx + 1, Amax, Splitters, Smid + 1, Smax)

I assert that this is as efficient as the non-in-place approach based on binary search given in the Wikipedia article, because each element of A will take place in $\log(|\text{Splitters}|)$ calls to partition, which is linear time.


How the deletion takes place in B+ Tree My professor was giving a lecture on B+ Trees deletion, and I got very confused. According to him for deleting any key from a B+ Tree:

1- First navigate to the leaf *L* where it belongs.
2- If the *L* is at least half full if you can simply delete it.
3- If it contains d-1 elements then you need to redistribute and merge.

If you see the below image, here I want to delete 19 and 20 from the B+ Tree.

After deleting 19 and 20 from the B+ Tree.

Question:

I am confused why the redistribution and merging is required here at all? If you just simply delete 19 and 20 from the leaf nodes without any distribution it should work right? Why redistribution is performed here? Could anyone explain?

  Is it because the left pointer of 24 is pointing to 20 but no 19.
  Thats why redistribution is required for 20 but not 19.

Okay I understood the issue.

Properties of B+ Tree.

All leaves should be at the same depth, and the mininum element in each leaf node should be equal to depth of the tree. See the example below:
All the leaves are in same depth, and here d = 2.
Each leaf node must contain d number of elements, otherwise redistribution and merging has to be performed.
All the data pointers are contained in leaf nodes.
All elements should be contained in leaf nodes.
There should be between d to 2*d keys at node except possibly the root.
There should be between d + 1 to 2*d + 1 child pointers.

In the B+ Tree given below, each node has 2 and 2*2 data entries except possible the root. Each node has a mininum of 2 keys.

Only root of the B+ Tree can only fewer than d keys, its the only exception we have.

In my question, when you remove 19, the property of B+ Tree is not violated but when you remove 20, the total number of elements contained in the node is less than d. Hence redistribution and merging have to be performed so that the property of B+ tree is not violated.


Capacity of Binary Erasure Channel Consider the the binary erasure channel, with input and output alphabet $\{0,?,1\}$ and channel matrix
\begin{bmatrix}
1-\lambda-\mu & \mu & \lambda\\
0 & 1 & 0\\
\lambda & \mu & 1-\lambda-\mu
\end{bmatrix}
I want to determine its capacity, i.e. maximize $I(X;Y)$ over the probabilities distribution of the input.
I have tried writing and rewriting $I(X;Y)$ in different ways but the expression gets too complicated and I can't find a way to assign values to $p(x)$ so that $I(X;Y)$ is maximized. Any suggestions? Thank you in advance.

By symmetry, we can assume that $\Pr[X=0] = \Pr[X=1] = p$, and so $\Pr[X=?] = 1-2p$. We can then express $I(X;Y)$ as a function of $p,\lambda,\mu$. The capacity of the channel is the maximum of $I(X;Y)$ over all $p \in [0,1/2]$. You can find this maximum using calculus.
In more detail, let us first note that $\Pr[Y = 0] = \Pr[Y = 1] = (1-\mu)p$ and $\Pr[Y=?] = 1-2(1-\mu)p$. Furthermore, $H(Y|X=?) = 0$ and $H(Y|X=0) = H(Y|X=1) = H(1-\lambda-\mu,\lambda,\mu)$. Therefore
$$
I(X;Y) = H((1-\mu)p,(1-\mu)p,1-2(1-\mu)p) - 2pH(1-\lambda-\mu,\lambda,\mu).
$$
The derivative of this with respect to $p$ is
$$
-2(1-\mu)\log((1-\mu)p)+2(1-\mu)\log(1-2(1-\mu)p) - 2H(1-\lambda-\mu,\lambda,\mu) = \\
2(1-\mu) \log \frac{1-2(1-\mu)p}{(1-\mu)p} - 2H(1-\lambda-\mu,\lambda,\mu).
$$
Equating this to zero, we get
$$
\log \frac{1-2(1-\mu)p}{(1-\mu)p} = \frac{H(1-\lambda-\mu,\lambda,\mu)}{1-\mu}
$$
and so
$$
\frac{1-2(1-\mu)p}{(1-\mu)p} = e^{H(1-\lambda-\mu,\lambda,\mu)/(1-\mu)}.
$$
Massaging this, we finally get
$$
p = \frac{1}{(1-\mu)(2 + e^{H(1-\lambda-\mu,\lambda,\mu)/(1-\mu)})}.
$$


Is there an always-halting, limited model of computation accepting $R$ but not $RE$? So, I know that the halting problem is undecidable for Turing machines. The trick is that TMs can decide recursive languages, and can accept Recursively Enumerable (RE) languages.

I'm wondering, is there a more limited model of computation which accepts only recursive languages, and not RE? And if so, is there such a model which is always guaranteed to halt?

Obviously this model would be strictly less powerful than TMs and strictly more powerful than PDAs.

I'm open to a machine-style model, or a lambda-calculus style model.

As an example of what I'm thinking: the Coq language has a restriction that for any self-recursive calls, the first argument must be strictly decreasing in "size" i.e. if it is a natural number, it must be smaller, if it is a list, it must be shorter, etc. This guarantees that it always halts, but I have no idea if you can compute all of R this way.

Yes, there are as many models of R as there are of RE! Take a model of RE, and restrict it to the total elements of the model. For example, take Turing machines that halt. Or take total recursive functions. Or take your favorite programming language (idealized to remove memory limitations) but in addition to requiring that the source code be syntactically valid, also require that the program halt on every input.

The catch is that, since the halting problem is undecidable, for any model of R, given a recursive syntax for the elements, there cannot be any algorithm to decide whether a candidate element is valid. For example, a normal programming languages has syntactic rules, and sometimes a type system, to decide whether a program is well-formed; the parser or type checker implements a decision procedure to verify that the source code is an element of the language. If you want a programming language that is a model of RE rather than R, there is no way to decide whether some source code is a valid program.

Coq only allows a subset of all recursive functions:
$\mathsf{Coq} \subsetneq \mathsf{R} \subsetneq \mathsf{RE}$. Both bounds of this inequality chain have decidable models but the middle item doesn't. Intuitively speaking, Coq only contains recursive functions whose termination can be proved by sufficiently simple arguments. While “sufficiently simple” covers just about anything mathematicians do, it is still very limited in a theoretical sense. (More precisely, Coq's theory is equivalent to I think the Peano axioms with a schema for recursion that goes up to a certain ordinal, but at that point it gets beyond my comprehension.)


Problems in $\textbf{DSPACE}(\log^2 n)$ Let some problem $P$ is in $\textbf{DSPACE}(\log^2 n)$  and $Q$ is a problem in $\textbf{DSPACE}(\log n)$. I can claim that $P$ is polynomial time solvable as number of turing machine configurations for problem $Q$ is polynomial many.

Question :  Can I say that $\textbf{DSPACE}(\log^2 n)$ is in polynomial time complexity class?

There are about $2^{\log^2n}$ possible configurations, and $2^{\log^2n} = n^{\log n}$, which is not polynomial (it's "quasipolynomial"). So, no, you can't claim that $\mathrm{DSPACE}[\log^2 n]\subseteq \mathrm{P}$.


Why does this graph show the tightness of MST heuristic's 2-approximation bound? This is a homework problem I've been given and I've been raking my brain for hours (so I'm satisfied with some pointers). I know already that the approximation ratio cannot be worse than $2$. I have a wheel graph, where each edge has cost $1$ and the distance between all nodes which are not connected by edges is $2$. The wheel graph $W_6$ is this one:

I have marked in blue what I believe to be the output of an MST heuristic algorithm. But I also think this is the optimal solution, since all nodes can only be visited once. So the cost of the tour would be $7$ for both optimal and MST.

I do not see how this type of graph shows that the $2$-approximation bound of MST heuristic is tight (not necessarily this instance, but the graphs $W_n$ in general). Can someone enlighten me?

There is a lot of freedom in the algorithm: several minimum spanning trees, and several corresponding Eulerian tours. Try to find the worst choice and show that it produces an inferior tour. What you are showing is that the algorithm could make this choice, and so could produce an inferior approximation.

If you don't like this idea of choice, you can sometimes guarantee that the algorithm makes the choices you want by slightly tweaking the weights.


Collisions of prefixes of MD5 hashes in some fixed interval I was wondering, if there is an MD5 hash collision in the UNSIGNED MEDIUMINT Range (0 - 16777215). Sadly, I'm unable to run a script to check this myself, due to Memory (RAM) limitations. The answer is probably no; the next step would be - how many characters are even needed, until the first collision is found?

An MD5 hash has 32 Characters. If you only would use, lets say, the first nine characters from all MD5 hashes in the MEDIUMINT range, would they still all be unique?

The reason behind this: I'm trying to find a simple way to basically use an MD5 hash for every number in the MEDIUMINT range, to create a short, unique string, preferably not longer than 9 letters -- as abstraction to the actual number (so instead of an 1, you get something like c4ca4238a)

Are the first nine characters of all MD5 hashes in the UNSIGNED MEDIUMINT (whitout 0) range unique?

Just to complete Yuval's answer, there are plenty of collisions if you pick the first 9 digits of the MD5.

For example:

md5('40236')  = f46657d67 3d95ccf8d12b1075ab7c653
md5('400704') = f46657d67 e7a3de02f64013bfcbd932c

Let $m = 2^{36}$ (nine hex digits), $n = 2^{24}$ (three bytes for an UNSIGNED MEDIUMINT);
assuming that MD5 is a good hash :), the probability $P(n)$ of a collision is:

$1 - m! / (( m - n )! * m^n) \approx 1 - e^{-n^2/2m} = 1 - \frac{1}{e^{2048}}$

And you'll find a collision on the first 9 digits with high probability ($P(n) \approx 0.99$) every $n = 2^{20}$ strings picked (whatever they are). See Birthday problem on Wikipedia.

So even if you use the binary encoding (three bytes) you obviously get plenty collisions:

Starting from 000000, the first  is:

md5( 0x013701 ) = 8015b8be cf7b0a7e744cd54ac76a302f
md5( 0x0725c6 ) = 8015b8be cf8140319e919766901824bf

Note that 0x0725c6 is a 19 bit number.


Is interaction more powerful than algorithms? I've heard the motto interaction is more powerful than algorithms from Peter Wegner. The basis of the idea is that a (classical) Turing Machine cannot handle interaction, that is, communication (input/output) with the outside world/environment.

  How can this be so? How can something be more powerful than a Turing Machine? What is the essence of this story? Why is it not more well known?

Turing machines can handle interaction just fine, using oracle tapes. It works are follows: from the point of view of a computer that handles interaction, the input of the operator is simply another sequence of bits that it sent into the computer from time to time. We all know that a lazy sysadmin could write a script to send the input to the program when it is requested, so that the sysadmin could go on break earlier.  The interaction machine has no way to know if there is really a live operator at the console, or if the input is being piped from another program.

Having all the interaction input prepared ahead of time is the same, in theoretical terms, as having all the input on a separate tape that is used by an oracle Turing machine. Whenever the computer would normally request interaction from the operator, the machine instead reads from the input tape. If the thing read from the tape seems invalid in some way, the Turing machine does exactly what the interaction machine would do on receiving that input.

I would guess that Wagner is aware of the ability to use oracle tapes to code input, so you have to take his comments with a grain of salt, or you have to ask what he actually means.  I believe that people who think about interaction are generally worried about two things:

"Real" computers do have interaction, but algorithms as defined by Turing don't. We can get around this by coding the input on oracle tapes, but this still does not match the way that real computers operate. It might be nice to study models of computation that are more closely aligned with real computers.
Oracle-based algorithms are not often considered in day-to-day computing because normal computers don't come with a magic "oracle" to supply data. But we might be able to actually just use a person as the oracle. If the person understands the data that is being requested, they may even be able to help the algorithm along, thus improving its performance. In other words a human may be able to provide a useful oracle tape rather than simply a random one, and in principle this might lead to faster or more powerful computing methods compared to non-oracle-based ones. A similar thing happens with randomized computing, after all, where the machine is given a sequence of random bits as an extra input.


When the stall is actually going to happen? Suppose in a 5 stage pipeline when the stall will actually happen if there is a RAW hazard? The stall will start after Instruction Fetch(IF) stage or Instruction decode(ID) stage? In few cases I see that the stall start after IF that is before executing ID and in multicycle pipeline, the stall starts after decode stage (ID). Can someone please clarify it?

As part of the instruction decode phase, the operands are fetched for the instruction. In a very naive pipeline implementation, the operands for read  will only be visible after the write instruction has written back its changes to the internal registers (so the last stage).
To prevent such long stalls, a CPU can apply tricks like forwarding the store to the load as soon as the value is determined instead of needing to wait for the write to the registers.
Check out the following for a more detailed answer:
https://youtu.be/EL8uqzSsg_Q?t=433


Are the implications of the diagonalization language different from those of the halting problem? Revised:
In my previous question, I was confused about the implications of the diagonalization language. I concluded that it proves there are languages for which there are no recognizable turing machine. However, how is this implication different from the halting problem? Do they both just reinforce the limitations of computability?

Old post:

I'm in an introductory computer theory course. The professor went over the diagonalization argument and showed how the diagonalization language is not decidable.

The diagonalization language is the set of all pairs of turing machines and strings that they accept. In other words, $L = \{ (s_i, M_i) | M_i$ accepts $s_i \}$. We can encode each turing machine as a binary string and sort them in lexographic order. We can then fix an alphabet $\Sigma$ and then put $\Sigma^*$ in lexographic order. By creating a table with these lists, where the values in the table are either 1 for accept or 0 for reject, we define a language to be any diagonal row in the table. Now we consider the complement of the diagonal language, which takes the complement of each value in the main diagonal. We quickly see that there is no turing machine that recognizes this language - as we switch every accept value to reject. Thus we have proved that exist languages for which there is no recognizing turing machine.

In class the professor actually said that this argument proves undecidability.

I don't see the more general implications of this argument. For the purposes of a intro course on CS theory, what are the implications of the existence of undecidable languages on our understanding of turing machines? Do they mention it to show that there are limits to what is computable (but isn't that the purpose of the halting problem)?

I'm truly trying to understand why this proof is used in every textbook, because I don't grasp how it connects to the other sections about turing machines.

I think that "limits of computation" is a good entry point. Usually, computer scientists learn how to solve problems in an logical and algorithmic way. The whole concept of undecidability is to show that there are problems which cannot be solved in this way, which may sounds surprising but also exciting, that there is an actual limit to what is possible with computers (even with infinite memory).

You actually do not need the diagonalization language to show that there are undecidable problems as this follows already from a combinatorical argument:
You can enumerate the set of all Turing machines (sometimes called Gödelization). Thus, you have only countable many decidable languages. But the set $2^{\{0, 1\}^\ast}$, i.e. the set of all languages over $\{0, 1\}$, is uncountable, so there have to be undecidable languages.

The diagonalization language (I assume $D = \{\langle M \rangle \mid M \text{ halts on } \langle M \rangle\}$ is by all means very constructed but the proof that this language is undecidable is a good stating point because the proof via diagonalization is easy and the usual variations of the halting problems are not really far away. The next steps are probably Turing reductions from this language to some of these variations.


Is a Turing Machine "by definition" the most powerful machine? I agree that a Turing Machine can do "all possible mathematical problems". But that is because it is just a machine representation of an algorithm: first do this, then do that, finally output that.

I mean anything that is solvable can be represented by an algorithm (because that is precisely the definition of 'solvable'). It is just a tautology. I said nothing new here.

And by creating a machine representation of an algorithm, that it will also solve all possible problems is also nothing new. This is also mere tautology. So basically when it is said that a Turing Machine is the most powerful machine, what it effectively means is that the most powerful machine is the most powerful machine!

  Definition of "most powerful": That which can accept any language.
  Definition of "Algorithm": Process for doing anything.
  Machine representation of "Algorithm": A machine that can do anything.

Therefore it is only logical that the machine representation of an algorithm will be the most powerful machine. What's the new thing Alan Turing gave us?

I agree that a Turing Machine can do "all the possible mathematical problems".

Well, you shouldn't, because it's not true. For example, Turing machines cannot determine if polynomials with integer coefficients have integer solutions (Hilbert's tenth problem).

Is Turing Machine “by definition” the most powerful machine?

No. We can dream up an infinite hierarchy of more powerful machines. However, the Turing machine is the most powerful machine that we know, at least in principle, how to build.  That's not a definition, though: it is just that we do not have any clue how to build anything more powerful, or if it is even possible.

What's the new thing Alan Turing gave us?

A formal definition of algorithm. Without such a definition (e.g., the Turing machine), we have only informal definitions of algorithm, along the lines of "A finitely specified procedure for solving something." OK, great. But what individual steps are these procedures allowed to take?
Are basic arithmetic operations steps? Is finding the gradient of a curve a step? Is finding roots of polynomials a step? Is finding integer roots of polynomials a step? Each of those seems about as natural. However, if you allow all of them, your "finitely specified procedures" are more powerful than Turing machines, which means that they can solve things that can't be solved by algorithms. If you allow all but the last one, you're still within the realms of Turing computation.
If we didn't have a formal definition of algorithm, we wouldn't even be able to ask these questions. We wouldn't be able to discuss what algorithms can do, because we wouldn't know what an algorithm is.


Finite Automata -- Determine if a set is regular I have been at this for hours. The question is:

Prove that the language $A = \{0^kx \mid k > 0, x \in \{0,1\}^*, \text{ and } \#(0,x) \geq k\}$ is regular,
where $\#(n, x)$ denotes the number of $n$ in string $x$.

So far, I have used the pumping lemma to determine that the opposite is not regular, i.e. that if $\#(0,x) \leq k$, the language is not regular.
I have also constructed a nondeterministic finite automaton that I thought I could use to prove that this set is regular since that is generally the way to go about proving regularity. I can't really draw it, but at start state $s$, if $0$ is read in, then move to state 1 (or state $'0'$). If a $0$ is read in, either stay in state 1 or move to state 2. If a $1$ is read in, move to state 2. However, I honestly don't know what to do further.

Hint: Show that a word belongs to $A$ iff it starts at $0$ and contains at least one more $0$. That is, $A$ is accepted by the regular expression $01^*0(0+1)^*$.


Finding a tree that approximates the distances and total weights Given an undirected graph $G=(V,E)$ could we build a tree $T$ that approximates the distances from given vertex $r$ and the total weight, i.e. $\forall x \in V, d_G(r,x) \le d_T(r,x) \le 3 \cdot d_G(r,x)$ and $w(T) \le 3\cdot w(\text{MST}(G))$, where $\text{MST}$ is the minimum spanning tree and $w(\cdot)$ is the weight function i.e. $w:\Bbb E \to \Bbb R^+$. $d_G(v,u)$ denotes the shortest path distance between $v$ and $u$ in $G$, and $d_T(v,u)$ is the shortest path distance between $v$ and $u$ in $T$.

Could any one help me to understand how to build this tree and if there is any material that would help?

Your problem is solved in the following paper by Khuller, Raghavachari, and Young. They show that you can construct a tree in which distances from the root are stretched by at most $\alpha$ and the total weight of the tree is at most $1 + 2/(\alpha - 1)$ times the weight of the MST. So, with $\alpha=3$, you can get $2$ times the weight of the MST. The algorithm does a depth-first traversal of the MST, and  adds paths from the shortest path tree when necessary, roughly speaking maintaining a shortest path structure in the current graph, which consists of the MST edges and the edges added from the shortest path three. Check the paper for details.

As I mentioned in the comment, there are graphs in which the weight of the shortest path tree rooted at some vertex is greater than the MST weight by $\Omega(n)$. One example is a path of unit weight edges, and edges from the first vertex in the path to the $i$-th vertex of weight just slightly less than $i-1$.


Running time of greedy scheduling algorithm Here is an algorithm to output a subset of activities S such that no activities in S overlap and profit(S) is maximum.

Define $p[i]$ to be the largest index $j$ such that $a_j$ does not overlap $a_i$.

$\#$ Return maximum possible profit from $a_1,...,a_n$

def rec_opt(n):
    if n == 0:
        return 0
    else:
        return max(rec_opt(n-1), w_n + rec_opt(p[n]))

It doesn't mention what $w_n$ is in the slide, but I think it is the profit of the activity $a_n$.

  Consider a set of $n$ activities where there is no overlap at all. Then $T(n) = 2T(n − 1) + c$. This recurrence has an exponential closed-form, $O(2^n)$.

"return max(rec_opt(n-1), w_n + rec_opt(p[n]))": I think this line takes time $2T(n-1)$.
"if n == 0": this line takes time $c$.

Am I correct?

One more question, how can we get $O(2^n)$ from $T(n) = 2T(n − 1) + c$?

You are asking several questions. I will only answer the second one.

Suppose that $T(n) = 2T(n-1) + c$, and that $T(0) = a$. Define $S(n) = T(n) + c$. Then $S(n) = T(n)+c = 2T(n-1)+2c = 2S(n-1)$, and so $S(n) = 2^nS(0) = 2^n(a+c)$. We conclude that $T(n) = 2^n(a+c)-c = 2^na+(2^n-1)c$.


set complement and superset If 'S is a set complement of S, then a set complement of a superset of S' is a subset of S.

Just want to verify that above is true just based on the definition of set complement and superset.

I'm not sure what you mean by "a set complement of $S$."

If you mean to allow complements with respect to different universal sets, then the statement in the question is not true. For example, let $S=\{1\}$. Its complement $S'$ with respect to $\{1,2\}$ is $\{2\}$. $\{1,2\}$ is a superset of $S'$ but its set complement with respect to $\{1,2,3\}$ is $\{3\}$, which is not a subset of $S=\{1\}$.

On the other hand, if you mean "the set complement of $S$" with respect to some fixed universal set $U$,the statement is true. We have $S'=U\setminus S$ and choose some $T \supseteq S'$. Then $U\setminus T \subseteq U\setminus S' = S$.


Is the set-partition problem polynomial time reducible to the subset-sum problem? There are many solutions on the web showing that the subset-sum problem is polynomial time reducible to the set-partition problem. However, during my search, I came across the following powerpoint presentation (slide 12), where it says that the inverse is also true. i.e. the set-partition problem is polynomial time reducible to the subset-sum problem.
So far, I have been unable to find any proofs to show the same.

So, my question: How is the set-partition problem polynomial time reducible to the subset-sum problem, or was there an error on the presentation above?

First, both problems are NP-complete, and are therefore reducible to each other. A concrete reduction can go through the Cook-Levin theorem (i.e. SET-PARTITION$\le_p$SAT$\le_p$SUBSET-SUM).

However, in this case there is a fairly trivial direct reduction: given an instance $\{x_1,...,x_n\}$ for SET-PARTITION, compute $t=\sum_{i=1}^n x_i$ and output $\{x_1,...,x_n\},t/2$ as input for SUBSET-SUM. The correctness of this is very easy to show.


Relation between Lattice and Boolean Algebra In discrete math, I have read that lattice is a generalized form of boolean lattice. But those places where boolean algebra is mentioned, they don't tell about lattices (digital logic, binary,...). Whether the meet and join is same as and and or in boolean logic? If we are thinking in terms of lattices how you define 1 and 0 = 0? We consider only a two element lattice?

I would hardly describe a lattice as a generalized form of boolean algebra, since there are many more things that a lattice can describe.

A better description would be to say that boolean algebra forms an extremely simple lattice. It has two elements, $\top$ and $\bot$, with $\bot \sqsubset \top$. The meet corresponds to conjunction (AND), and the join corresponds to disjunction (OR), though you can make a dual lattice with these flipped.

But, we don't teach this with boolean algebra for the same reason we don't teach group theory when teaching children about the whole numbers.

Lattice theory is way more than you need to understand booleans, and while it's a neat fact that booleans form a simple lattice, the mechanics of lattice theory, fixpoints, continuity, etc. were made to solve much harder problems than arise with booleans.


$L^{\prime}=\{x \# y \mid x y \in L, y x \notin L\}$ where $L$ is regular Hey I'm trying to prove that the following Language is regular so far couldn't find a way, hope someone can help me $L^{\prime}=\{x \# y \mid x y \in L, y x \notin L\}$ where $L$ is regular.

You can write this language as the intersection of two languages:
$$
\{ x \# y \mid  xy \in L \} \cap \{ y \# x \mid xy \notin L \}
$$
I assume you know how to handle the first one. As for the second one, construct an NFA that acts as follows:

Start with a DFA for $L$.
Guess which state the DFA will be on after reading $x$.
Based on this guess, verify that after reading $xy$, the DFA reaches a rejecting state.
Now read $x$ and verify your guess.

You take it from here.


Proof of Space Hierarchy Theorem incompatible with Linear Speed Up Theorem for time In this proof of the Space Hierarchy Theorem the following language is defined
$$
 L =  \{ (\langle M \rangle, 10^k) : M \mbox{ does not accept } (\langle M \rangle, 10^k) \mbox{ using space } \le f(|\langle M \rangle, 10^k|) \}.
$$
And then stated:

  Now, for any machine $M$ that decides a language in space $o(f(n))$, $L$ will differ in at least one spot from the language of $M$. Namely, for some large enough $k$, $M$ will use space $\le f(|\langle M \rangle|, 10^k|)$
  on $(\langle M \rangle, 10^k)$ and will therefore differ at its value.

I get the diagonalization argument, but what makes me wonder according to the linear speed up theorem for space we have [see for example Hopcroft/Ullman, 71]:

  If $L$ is accepted by an $S(n)$ space-bounded Turing machine with $k$ storage tapes, then for any $c > 0$, $L$ is accepted by a $cS(n)$ space-bounded Turing machine.

As shown in the linked wikipedia article $L$ is accepted by a Turing machine using $f(n)$-bounded space, then by linear speed up $L$ is also accepted by some machine $M'$ using at most $\frac{f(n)}{2}$ tape cells. But then we get a contradiction on the inputs $(\langle M' \rangle, 10^k)$, as $M'$ accepts $L$ if $(\langle M' \rangle, 10^k)$ is accepted, then $(\langle M' \rangle, 10^k) \notin L$, contradiction, and similar for the case if it is not accepted. If $(\langle M' \rangle, 10^k)$ is not accepted by $M'$ then $(\langle M' \rangle, 10^k) \in L$ by definition of $L$, but $(\langle M' \rangle, 10^k) \notin L(M') = L$, a contradiction.

My reasoning seems to be fine, but it should not be... what am I missing here? In my argument, the problem is with the speed up and essentially it derives that if speed up is possible, then we can separate $f$ and $cf$ for $0 < c < 1$, i.e., speed up is not possible. The only valid conclusion would be that linear speed up is not possible, but that is certainly not true...

The Wikipedia proof is bogus.

As you have proven, the description for $L$ is incomplete. It should read:
$$
 L =  \{ (\langle M \rangle, 10^k) : M \mbox{ does not accept } x = (\langle M \rangle, 10^k) \mbox{ using space } \le f(|x|)
 \; \textbf{and time} \; \le 2^{f(|x|)} \}
$$

This corrects the proof because now $M$ (or $M'$) can still accept $x = (\langle M \rangle, 10^k)$ and take space $\le f(|x|)$. Actually, $(\langle M \rangle, 10^k) \in L$ has a quite reasonable explanation in that $M$ attempts to simulate $M$, which (as a subroutine) attempts to simulate $M$ again, and so forth and so on, until eventually $2^{f(|x|)}$ steps elapse and the whole procedure is interrupted. Hence, $M$ does not accept $x$ using space $\le f(|x|)$ and time $\le 2^{f(|x|)}$, although it does accept it taking space $\le f(|x|)$ (well, perhaps actually $O(f(|x|))$) and time $> 2^{f(|x|)}$.

As a matter of fact, the purported algorithm for $L$ in the article explicitly states it runs its simulation with a $2^{f(|x|)}$ stopwatch. This is precisely the detail that is missing from the definition of $L$.


Applications for boolean logic operations in zero-one integer linear programming (ILP) It is nice to know that every boolean formula can be expressed by zero-one
integer programming by this answered question. But are there any applications?

To be more precise: Are there papers which use the existense of zero-one
integer programming for boolean operations?

Yes, there are many applications.  To find some, go to that question and look through the linked and related questions on the sidebar; that will already show you several applications.  Next, do a search for the search term "ILP" on this site, and browse through the search results.  You will find many examples of problems that can be solved with zero-one ILP using these techniques.


Simultaneous regression of multiple curves in the same dataset or image? I am getting the pattern shown in the picture from an experiment. To my human brain it is evident that it consists of some 20 straight lines. I need to find position and slope of all these lines (perform a regression). But I need to do it completely automatically. If this were a a single sequence I would have used RLS(Recursive Least Squares) or Kalman filter. But how can I go about if I want to make 20 simultaneous regressions that do not conflict with each other?

What would be the most generic way to solve these kind of problems (say if I have an image of 20 overlapping boxes and need to find size, position and angle of all of them, at once)? I suppose the solution is more than well-known since this would be fundamental for any image recognition, but I cannot find a generic description of the method.

There are many possible methods.  In your picture, there aren't too many dots, so the following algorithm might be good enough:

For each pair of points, find the line through them.  Count the number of points that are approximately on that line.
Choose the line that has the most number of points on it.  Output that line.  Delete all points that are approximately on that line from the figure.
Repeat until no points remain.

For fancier methods (e.g., if you have a huge number of points, or some prior model for what kinds of lines you expect to see), you can look at RANSAC and the expectation maximization (EM) algorithm, but given your sample picture, the above simple method might be adequate in your setting.


Calculate boolean matrix multiplication (BMM) using transitive closure Let us say I am given an algorithm that calculates the transitive closure of a given graph $G = \{ V, E \}$.
How can I use this algorithm in order to perform the Boolean Matrix Multiplication of two matrices $X$ and $Y$?

I know that in order to calculate the transitive closure of a matrix $I$ need to compute $I^{(V-1)}$. But what else?

Let us build the tripartite graph $G = (S := U\dot\cup V \dot\cup W, E)$, where $U := \{u_1, \dots u_n\}$ and similarly $V := \{v_1, \dots v_n\}$ and $W := \{w_1, \dots w_n\}$. Define $E$ as follows:
For $i, j \in [n]$, we add $(u_i, v_j)$ to $E$ for $u_i \in U$ and $v_j \in V$, if and only if $X_{ij} = 1$. Similarly we add $(v_i, w_j)$ to $E$ for $v_i \in V$ and $w_j \in W$ if and only if $Y_{ij} = 1$.

Let $G^T := (S, E')$ be the transitive closure of $G$. This means $(x, y) \in E'$ if and only if there is a path from $x$ to $y$ in $G$.

Claim. Let $Z := X \cdot Y$ be the matrix resulting from the multiplication. We claim that $Z_{ij} = 1$ if and only if $(u_i, w_j) \in E'$.

Proof. $Z_{ij} = 1$ if and only if $\bigvee\limits_{k=1}^nX_{ik}\land Y_{kj}$ if and only if there is a $k\in [n]$ such that $X_{ik} = 1$ and $Y_{kj} = 1$ which is the case if and only if there is a $k\in [n]$ such that $(u_i, v_k) \in E$ and $(v_k, w_j) \in E$ which is the case if and only if$^{(*)}$ there is a path in $G$ from $u_i$ to $w_j$ and hence $(u_i, w_j) \in E'$.

Try to prove $(*)$ as an exercise. Hint: for the harder direction use the fact that the graph is directed.


Effective AI for one player-one ghost pacman I am thinking of a modified version of pacman. In this version, it will be a two-player game. Each player will have one pacman and one ghost. So there are 2 pacmans and 2 ghosts in the board at a time. No additional ghost is there. A player will control both his pacman and ghost separately- there is no predefined or random move of ghosts. Ghost of a player will try to catch the opponent's pacman. Pacman of a player will try to avoid the ghost of the opponent. Collision of ghost and pacman of the same player won't affect anything. So the pacman and the ghost of the same player need to cooperate with each other. "Moving Target Search" seems promising for the ghost, but what about the pacman? Will minimax (with alpha beta pruning) work in this multi-agent cooperative environment? I am saying this cooperative because my ghost will try to catch the opponent's pacman and my pacman will use this opportunity to eat more food. I have separate functions for the pacman move and the ghost move to simplify the gameplay. So returning a single tuple (including the moves of both pacman and ghost) from a function is not possible here.

This is an adversarial game problem where you need to find the optimal behavior from each position. There are several approaches to attack such problem.

You can do Minimax with alpha beta pruning to find the best move.
It will provide you an optimal move after exploring the entire tree up to some level (not too deep if the branching factor is too high, here your branching factor is $4*players$) using a handcrafted heuristic by you. So the quality of the results heavily depends on the quality of the heuristic. If you improve the pruning you can achieve better results, as you can explore more.

Another approach is Montecarlo Tree Search. This algorithms performs really good in several games, and doesn't depend on any previously knowledge of the game. Roughly speaking, it seeks the best option by expanding the tree from the state you are in and calculates the quality of a state by performing a random simulation of the game.

There is a novel approach, Reinforcement learning, that you can use to find the answer. The idea behind it is approximate the optimal policy that gives you the maximal reward. Here you can understand by policy the action you will make at any position an the rewards are the points you get after each action. You can read more about it here.


In this example of determinising an NFA, isn't there an edge missing in the result? I am reading a computer theory book and came across the following example converting a NFA to a DFA:

My question is, would you not need an edge labeled $b$ going from the $x_4$ node on the right to the null collection state?

The standard definition of DFAs involves a transition function, that is total. That means that, from every state, there should be an arrow for each symbol. So, yes, there is a missing $b$ arrow from $q_4$ to $\emptyset$ and also, missing $a$ and $b$ arrows from $\emptyset$ to itself. While we're at it, the diagram also has no indicated start state.

Note, though, that some authors use the convention that, if there's no transition given for some symbol from some state then, when the automaton reads that symbol in that state, it goes to a "dead" state. The dead state is non-accepting and the automaton cannot leave it (reading any character keeps it in that state).  The author of your book might be using that convention inconsistently: the dead state is $\emptyset$ but they've only shown some of the transitions that lead to it.  I think that's bad style: in my opinion, it's clearest to either show all the transitions to the dead state, or none of them.


Reduction of Hamiltonian cycle to Hamiltonian cycle & clique I've been given a homework problem to prove that determining whether a graph G has both a Hamilton cycle and a clique of size k is NP-complete.

Based on this question, I know an "easy" reduction exists from Hamiltonian path to Hamiltonian path & clique (or someone has said it exists), and I assume that the same is true for reducing Hamiltonian cycle to Hamiltonian cycle & clique.

My thought is to somehow insert a clique of size k into G such that it's in the original cycle. (If I can make it lie in the path of the original cycle, it shouldn't disrupt the cycle, as all cliques have a Hamiltonian path through them.) But there are two problems with this approach:

I'm not sure how to insert a clique in such a way it can't create or destroy a cycle. I've tried:

Inserting the clique on an arbitrary edge of the graph (can result in a G' without a Hamiltonian cycle)
Adding k-2 vertices and creating a clique between them and two adjacent vertices in G (can result in G' without a Hamiltonian cycle)
Inserting the clique between input & output nodes connected to two different vertices on the original graph (can result in G' with a Hamiltonian cycle where G did not have one, if the points are arbitrary, or G' without a Hamiltonian cycle if inserted across adjacent vertices)

More generally--if I can find a way to insert a clique while preserving G's original Hamiltonian cycle--does this actually satisfy the iff requirement of the reduction? I don't feel like it does, because the existence of the clique in G' is in no way contingent on the existence of the Hamiltonian cycle in G.

Could someone give me a push in the right direction on this? I'm totally stumped on another way to approach it.

For NP completeness, two things must be demonstrated.

That a solution to the problem can be verified in polynomial time (usually easy).
That the input to another NP Complete problem can be formatted as an input to the potentially NP complete problem (also that a solution from the potential NP Complete problem can be turned into a solution to the NP complete problem) all in polynomial time.

It looks like you are trying to go the wrong direction with your question. You are asking about inserting a Clique into a graph, but you only need to concern yourself with a graph that would be sent to a HP solver and modify the inputs so they are appropriate for a HP+Clique solver.  The HP part of the candidate problem doesn't require any modification - it just takes an undirected graph G(V,E).  A clique takes an undirected graph G(V,E) and a goal, k.  So you need to define a k that is in $G_{HP}$.  what if you set k=1?.  This way, the only graphs that your solver will fail to find a solution for are those that don't have a HP since every node is a clique with itself. This takes O(1) to define k=1.

Now, you just need to modify the output of the HP+Clique so it is the same as the output for the HP problem.  e.g. If the candidate problem produces a solution, you would only return the path part and drop the clique part.   If a solution is not found, you return NO.


Complexity of finding binomial coefficient which equals to a number Assume you are getting a number $m$ (using $O(\log m)$ bits in binary encoding).

How fast can you find (or determine such does not exist) $$n,k\in \mathbb N, 1<k\leq\frac{n}{2}:{n \choose k}=m$$
?

For example, given the input $m=8436285$, one may output $n=27, k=10$.

A naive algorithm for the problem would go over all possible values for $n$, and search for a value of $k$ which satisfies the property.

A simple observation is that there no need to check values of $n$ smaller than $\log m$ or larger than $O(\sqrt m)$. However (even if we could check only $O(1)$ possible $k$ values per $n$ value) this ends up in an inefficient algorithm which is exponential in the input size.

An alternative approach would be to go over the possible values of $k$ (it's enough to check $\{2,3,\ldots,2\log m\}$) and for each check for possible $n$ values. We can then use:
$$\left(\frac{n}{k}\right)^k<{n\choose k}< \frac{n^k}{k!}$$

So for a given $k$ we only need to check $n$ values in the range $[\sqrt[\leftroot{-2}\uproot{2}k]{m\cdot k!},\sqrt[\leftroot{-2}\uproot{2}k]{m}\cdot{k}]$, Doing so using binary search (when $k$ is fixed, $n \choose k$ is monotonically increasing in $n$), this gives a polynomial algorithm running in $O(\log^2m)$.

This still seems inefficient to me and I guess that this could be solved in linear time (in the input size).

It is not true that $(n-k)^k<{n\choose k}$. For example ${9\choose 2} = 36 < 49 = (9-2)^2$.

I haven't (yet) found a subtle solution using arithmetic properties of the binomial coefficients, however I can suggest a somewhat bruteforce one if that helps :-)

You could, for each $k$, solve for $n$ by taking an initial guess (say $\sqrt[k]{k!\cdot m}$) and using an analytical method such as Newton-Raphson. You want to solve ${n\choose k} - m = 0$. The derivative of the left hand side with respect to $n$ is $(\psi(n+1)-\psi(n-k+1)){n\choose k}$ where $\psi$ is the digamma function, which is easy to compute.

The complexity of a Newton-Raphson search only depends on the complexity of computing the function and its derivative, and the number of digits required for the solution (in our case we just need the closest integer).

So overall for each $k$ the search should be $O(1)$ (assuming, as you seem to have done, that computing a binomial coefficient takes constant time), hence the total complexity for the algorithm using your bounds for $k$ would be $O(\log(m))$.


Loop invariant for an algorithm I have developed the following pseudocode for the sum of pairs problem:

  Given an array $A$ of integers and an integer $b$, return YES if there are positions $i,j$ in $A$ with $A[i] + A[j] = b$, NO otherwise.

Now I should state a loop invariant that shows that my algorithm is correct. Can someone give me a hint of a valid loop invariant?

PAIRSUM(A,b):
YES := true;
NO := false;
n := length(A);
if n<2 then
  return NO;

SORT(A);
i := 1;
j := n;
while i < j do  // Here I should state my invariant
   currentSum := A[i] + A[j];
   if currentSum = b  then
      return YES;
   else
    if currentSum < b then
      i := i + 1;
    else
      j := j – 1;
return NO;

First simplification: this algorithm, by inspection, cannot say YES when it shouldn't, since saying YES is immediately after a test verifying that the sum at the current positions is $b$.

Second simplification: It always terminates, since $i$ and $j$ move in a monotone way up and down respectively, and one always moves.  Thus, eventually they become equal and the loop ends.

So let's assume that that answer is YES, and $x$ and $y$ are the indices we are interested in, after sorting, with $x$ as small as possible and then $y$ as large as possible (we may have several possible pairs with the right sum).  Here is the invariant:

At the start of the loop, $i\le x$ and $j\ge y$.

If $i=x$ and $j=y$, then the algorithm will stop and say YES.  The loop invariant is trivial at the start, and also trivial when $i<x$ and $j>y$.  But if $i=x$, and $j>y$, then, since the array is sorted $A[i]+A[j]>b$, because of how $y$ was selected.  So $j$ decreases in all future iterations until it reaches $y$.  The other case, where $j$ gets to $y$ first is symmetric.

As noted above, the algorithm always terminates, which implies the algorithm will actually say YES, so we are done.

Edit: Since this question is about proof writing, here is another option, which I think is more confusing and more gritty.  I do not know if Tony Hoare would approve or not.

Here is the invariant:  A the top of the loop,

If $s<i$, then, for any $x\in [n]$, $A[s] + A[x] \neq b$
If $t>j$, then, for any $x\in [n]$, $A[x] + A[t]\neq b$

Again, this holds vacuously at the beginning.  Now we check some cases:

If $i = j$, then in any pair of indices $x$ and $y$ at least one of $x$ or $y$ is smaller than $i$ or bigger than $j$.  This rules out the input being a YES.  The loop ends and says NO, so we are in good shape.
Assume the loop did not end. If $A[i] + A[j] = b$, the answer is YES, and the algorithm works.
Assume $A[i] + A[j] \neq b$.
Subcase: If there is a $j'$, by hypothesis $j'<j$, such that $A[i] + A[j'] = b$, then $A[j'] < A[j]$ because the array was sorted, so $A[i] + A[j] > b$, which causes $j$ to decrease.  This shows that the invariant is maintained for $i$.  To see it for $j$, just note that if there is an $x$ such that $A[x] + A[j] = b$, then $x < i$, which is ruled out by the inductive hypothesis.
Subcase: If there is a $i'$, by hypothesis $i'>i$, such that $A[i'] + A[j] = b$, then $A[i'] > A[i]$ because the array was sorted, so $A[i] + A[j] < b$, which causes $i$ to increase.  This shows that the invariant is maintained for $j$.  To see it for $i$, just note that if there is an $x$ such that $A[i] + A[x] = b$, then $x > j$, which is ruled out by the inductive hypothesis.
Subcase: If neither of the other two cases holds, then the invariant is maintained trivially.

Finally, we note that the gap between $i$ and $j$ always gets smaller, so they must eventually become equal, and the algorithm will stop.

Remarks: This is the exact same argument, but more difficult to follow.  You too can write proofs like this using some expert techniques:

Don't say what the algorithm does.  Here, if the input is a YES, the algorithm ALWAYS gives you certifying indices that are as close to the ends as possible.  The 2nd proof cleverly hides this in a case analysis.
Don't give names to things.  Having hidden what the algorithm does, also don't name the stopping point.
Don't factor out easy cases.  This algorithm clearly works for NO instances.  By not noting that up front, we get a more complicated invariant.


Algorithm to get the number of iterations needed, if possible, to get an specific 2 element array I am fairly new to algorithms and I am dealing with a problem I cannot fully translate into mathematical language.
So, I am given the array [1,1] and I can only perform one sum between their numbers per step, ie you can only pick between:
[x(s+1), y(s+1)]=[x(s)+y(s),y(s)]

or
[x(s+1),y(s+1)]=[x(s), x(s)+y(s)]

but not both at the same time
Thus,
0: [1,1]
1: [2,1],                      [1,2]
2: [3,1],        [2,3],        [3,2],        [1,3]
3: [4,1], [3,4], [5,3], [2,5], [5,2], [3,5], [4,3], [1,4]
...and so on.

The goal is to know how many steps are needed in order to get a given [x,y] array.
This far, I know that
if (min(x,y)==1) --> steps =max(x,y)-1

if (x%2 ==0 and y%2==0) (both even) --> steps= not possible
if (max(x,y)%min(x,y) == 0) (one is multiple of the other or x,y are the same ) --> steps= not possible
if (x%3 ==0 and y%3==0) (both divisble by 3) --> steps= not possible

Also I plotted for each pair (x,y) how many steps are needed, and I can see a pattern happening for every multiple of x or y, but I can't write it as a mathematical function when x or y is >= 5.
Any guidance will be much appreciated.

You have observed several impossible situations for $x$ and $y$, such as when $x$ and $y$ are both even or multiples of $3$, etc. More generally, we have the following characterization. For all positive integer $x$ and $y$,
$$(x,y)\text{ is reachable} \iff \gcd(x,y)=1$$
where $\gcd(x,y)$ is the greatest common divisor of $x$ and $y$. That characterization can be proved easily by mathematical induction on $n=x+y$, since $$\gcd(x,y)=\gcd(x, x+y)=\gcd(x+y,y).$$
"The goal is to know how many steps are needed in order to get a given pair $(x,y)$." Here is a simple Python program that should be fast enough. It takes less than a hundredth of a second even if $x$ and $y$ have hundreds of decimal digits. The crux of the program is, count += x // y and x, y = y, x % y, which uses integer division and remainder to reduce $x$ to be smaller than $y$.
def number_of_iterations_needed(x, y):
    count = 0

    if x < y:
        x, y = y, x
    # Now x >= y

    while x % y != 0:
        count += x // y
        x, y = y, x % y
    # Now x % y == 0

    if y != 1:
        return None  # impossible
    else:
        count += x - y
        return count

In fact, the above program is just an augmented version of the well-known Euclidean algorithm, the granddaddy of all algorithms. Its time-complexity should be about the same as the time-complexity of the Euclidean algorithm, which is $O(\ln(\min(x,y))$. It uses about $O(1)$ space.
If you are searching for a closed form for the number of iterations needed given $x$ and $y$, you will probably not be able to find one since, as indicated on that Wikipedia page, nobody has come up with a closed form after more than two thousand years.


How to find a possibility of match in Naive Bayes Classifier? My math level is very very poor so I can't get the statistics.
Can anyone explain in simple words?
I.e. if I have frequency data:

Apple:
    Colors:
        Green = 3, Red = 2, Orange = 0;
    Shape:
        Sphere = 5, Ellipsoid = 0.
Orange:
    Colors:
        Green = 0, Red = 0, Orange = 5;
    Shape:
        Sphere = 5, Ellipsoid = 0.

I have many so fruits with frequencies, of course.
How can I get a possibility for object {Color: Red, Shape: Sphere} that it's an apple?

Let $A$ and $O$ be the events apple and orange (fruit). Let $R$ and $S$ be the events red and sphere.

By Bayes' law,
$$\Pr[A | R \wedge S] = \frac{ \Pr[R \wedge S | A] \Pr[A] }{ \Pr[R \wedge S] };$$
$$\Pr[O | R \wedge S] = \frac{ \Pr[R \wedge S | O] \Pr[O] }{ \Pr[R \wedge S] }.$$
By total probability adding to 1, we also have
$$\Pr[A | R \wedge S] + \Pr[O | R \wedge S] = 1$$
and therefore
$$\Pr[R \wedge S | A] \Pr[A] + \Pr[R \wedge S | O] \Pr[O] = \Pr[R \wedge S]$$
so
$$\Pr[A | R \wedge S] = \frac{\Pr[R \wedge S | A] \Pr[A] }{ \Pr[R \wedge S | A] \Pr[A] + \Pr[R \wedge S | O] \Pr[O]}.$$
By the Naive Bayes assumption of independence of features conditioned on class,
$$\Pr[R \wedge S | A] = \Pr[R | A] \Pr[S | A];$$
$$\Pr[R \wedge S | O] = \Pr[R | O] \Pr[S | O].$$
Putting it together, we get
$$\Pr[A | R \wedge S] = \frac{\Pr[R | A] \Pr[S | A] \Pr[A] }{ \Pr[R | A] \Pr[S | A] \Pr[A] + \Pr[R | O] \Pr[S | O] \Pr[O]}.$$

Now plug and chug. From the data $\Pr[R | A] = \frac{ \Pr[R \wedge A] }{ \Pr[A] } = \frac{2}{5}$, etc. Note: I am assuming the empirical distribution is the true distribution, an assumption your teacher probably expects you to make but not made in practice.


Metaheuristic for NP-complete problem without exact algorithms other than brute-force Computing Pure Nash Equilibria (PNE) is a Game Theory related problem.
Deciding if there exists PNE in a given game has been shown to be NP-Complete (Gottlob et al.).

I want to design a metaheuristic algorithm that spits out a strategy that is either a PNE or an approximation of such. A metaheuristic algorithm would not guarantee a global optimal solution but might produce a sufficiently good solution. i.e. I want to view the problem as an optimization problem.

To the best of my efforts, I couldn't find any exact algorithms that solves the decision problem other than iterating over all possible strategies (brute-force).

I've tried implementing some basic metaheuristics (evolutionary algorithm, GSAT-like algorithm, ...) and find 'good' solutions in a 'timely' fashion. I put quotation marks because I can't prove if the algorithm is in fact good and/or fast (it uses metaheuristics). Hence the following question:

Is it useful to design metaheuristic algorithms for a problem like this when its performance can not be shown by comparing it to other (exact) algorithms?

Thanks to user AdrianN (see comments) I was able to find a paper which presents a Mixed 0-1 Linear Program to find all Pure Nash Equilibria in n-player games. The method is an exact method and the authors provide performance results.

Zhengtian Wu et al. “A Mixed 0-1 Linear Programming Approach to the Computation of All Pure-Strategy Nash Equilibria of a Finite n-Person Game in Normal Form”

This, however, only answers half the question.
This question remains:

  Is it useful to design metaheuristic algorithms for a problem like
  this when its performance can not be shown by comparing it to other
  (exact) algorithms?

I realize this is a subjective question as, I think, D.W. tried to point out. I would like to answer this question myself by agreeing to D.W. and saying: It might be, it depends.

As a lot of references on metaheuristics will point out, it is important to be fully aware of the state-of-the-art before trying to design one. Metaheuristics tend to perform better than alternatives in certain (preferably interesting) situations, which should be shown by comparing them to said alternatives. Even if there is only a brute-force algorithm, it is likely that the brute-force algorithm will perform better in certain (interesting) situations and your metaheuristic will perform preferably much better in other situations. As D.W. said: "It depends what you're looking for, but sure, [metaheuristics] might be (useful), if you can accept the limitations."


Simplification of CFG Recently i was studying removal of useless symbols in productions given in Ullman Hopcroft.

The grammar goes as follows

S-> aAa | aBC

A -> aS | bD

B - > aBa | b

C-> abb | DD

D -> aDa

In the explanation that follows, we eliminate D obviously, but the removal of C still baffles me. As D is non generating, but C is both generating and reachable. So why delete C?

The resultant grammar is shown as

S->aAa

A->aS

B->aBa | b

Here is the link to the photo of the page in the book just in case

Page 240:

Page 241:

C isn't Part of the grammar recursion. As it expands to Terminals only, it is artificial in the Sense That it is only used for notational convenience while it is unnecessary for expressing the CFG.

The simplified grammar obviously contains a typo, as no words containing b are derivable contradicting S -> aBC -> abC -> ababb which the original grammar allows.

The first rule should probably read S -> aAa | aBabb.


What set of primitive operations are assumed to be constant time in complexity analyses? Different set of primitive operations lead to different complexity of certain problems. For example, sorting by comparison is only O(N*log(N)) if one assumes both integer comparison and random array indexing are O(1). While this might hold for bounded N, I believe complexity analysis is, theoretically, supposed to speculate about the asymptotic growth of a function, whereas it is obvious that you can't implement constant-time comparison or array indexing for arbitrarily large values. This makes me question the theoretical merits of such complexity analyses.

My question is: when there is a literature result such as X algorithm is found to be quasipolynomial, which set of primitive operations are assumed to be constant time?

It depends on the "model of computation".  The model of computation specifies things like what can be done in a single step and what operations are available.  There are different models of computation, each of which can sometimes lead to a slightly different running time.

If the model of computation makes an important difference and the paper is being careful, it will usually mention which model of computation it is working in.  Sometimes we don't care about the difference (or the difference is negligible) and then the model of computation might not be mentioned.

So, your model of computation could specify that pointers and integers (large enough to hold numbers in the range $[0,N]$) fit in a single word and can be accessed in $O(1)$ time.  Or, it might specify that this takes $O(\log N)$ time and space.  A circuit-centric model of computation might count the number of gates in a circuit needed to do the computation.  There are many others.

One example of a model of computation is the RAM model.


Relation between witness and problem statement Are there any known upper/lower bounds on the size of a witness of some np-complete/hard problem, or more precisely the relation between the problem size and the witness size.
For example, I'm interested in subset sum, set cover, SAT, hamiltonian cycles. If there is something known for other problems, I'd also be interested.
To be a bit more clear, I'll explain what I mean in detail for two of those problems.

UPDATE:
I assume the problem has a solution. So I am not interested in the decision version, but rather I assume there does exist a (positive) solution and I'm trying to find it.

For example, I give you a SAT problem and I tell you there is a solution, please find at least one. This should also be NP-complete. Now if the SAT Problem has 3 literals, it's easy to solve. If it has n/2 literals and n clauses, it's probably not easy. So my question is at what point it becomes easy and why.

In the case of subset sum. I give you a subset sum problem instance and ask you to find me one of the solutions, which I tell you exist. This is still hard to do, but is it also hard to do if I tell you that the/a solution will be a subset of number of size n/2 for a list of length n?
Again, I'm interested in understanding at which sizes of the solution the problem becomes easy.

For hamiltonian cycles, I ask you to find a cycle of size $k$ in a graph of size $n$, for which $k$ is the problem hard and so on...

I looked at the analysis of Fixed Tractable Problems, but they seem to focus on parameters that are fixed to constants, which is not necessarily what I want to know I think.

My intuition would be that most (NP-hard) search problems become easy once the witness size is smaller than $log(n)$ or bigger than $n-log(n)$, but I don't know how to actually support this claim formally.

I hope my question is a bit clearer now.

Consider a problem named 3SAT_NORM which is a version of 3SAT restricted to instances wherein the number of literals used is equal to the number of clauses. For 3SAT_NORM, every input of $n$ clauses requires the witness to give $n$ values for the satisfying assignment. Thus, you can't simply limit the size of the witness and relate the difficulty of the new problem -- the witness size is a function of the instance size.

But, you could conceive of a different witness than the usual one for 3SAT_NORM. You could take a convention where if the witness to 3SAT_NORM only defines some subset of the literals, then the other ones are automatically assumed by convention to be given an assignment of "true".

Now, suddenly, we can limit the size of the witness and make observations about the relationship -- in particular, restricting our witness to be smaller is the same as restricting 3SAT_NORM to include only formula where satisfying assignments are guaranteed to have a lot of "true" values.

What I'm trying to get at is the witness is a property of a solution to the problem, not a property of the problem itself. SAT and subset sum seem to have "natural" witnesses, but there still could be other witnesses and some problems may have witnesses that are less natural. Some witnesses can be restricted in size, and others can't.

With this in mind, there is still one major observation we can take in mind. If we limit witnesses to size $f(n)$ then there are only $2^{f(n)}$ possible witnesses so for small functions $f$ we can simply evaluate each possible witness to see if it works. In other words, by looking only at small enough witnesses, the problem is easy. This means if witnesses to inputs of size $n$ are guaranteed to be $log(n)$ in size, then the original problem can be solved in pseudo-polynomial time, and if the witnesses are guaranteed to be constant size then the original problem can be solved in polynomial time.


Terminology for Digitally Interpretting Environment I am looking into coding a program that can Analyse an image and identify objects in that environment (incl their depth and contours/shape).

What is the term for this? Is there a term or area of expertise for this? 'Computer Visualisation' is too broad a term I believe. Maybe Computer Vision and Pattern Recognition (CVPR)? Object Detection? Environment Analysis?

A real world example of what I am looking to develop; autonomous cars with software that can identify and classify objects in its path (pedestrians, curb, centre line, cars, etc.). I am most likely going to use OpenCV, code in C++ and the video stream will come from a cheap drone camera. The drone wont have an infrared/ultra violet hardware component so detecting depth will need to be performed using alternate methods - maybe there are image processing algorithms that can provide a crude idea of the depth of objects.

This falls within the broad field of computer vision.  It's related to object recognition, which is about the following problem: given a picture of an object, figure out what kind of object it is.  More generally, there's "scene analysis" (I think that's the right phrase): given an image, identify the objects in the scene and work out some understanding of their relative position and relationship.


Differences between substitution and rewriting? I am continuing with my self-study of formal languages.

Given two alphabets $\Sigma$ and $\Delta$, a string substitution is a mapping from $\Sigma$ to $\mathcal P(\Delta^*)$, which induces a mapping from $\Sigma^*$ to $\mathcal P(\Delta^*)$.

In case that a string substitution is a string homomorphism, it  is a mapping from $\Sigma$ to $\Delta^*$, which induces a mapping from $\Sigma^*$ to $ \Delta^*$.

A rewriting system, however, seems to be a relation on $\Sigma^* \times \Delta^*$.

So I wonder if the main difference between rewriting and substitution is that rewriting is a relation, which might not be a mapping, while substitution is a mapping? Thanks.

There are three differences between substitutions and rewriting systems:

Substitutions happen one symbol at a time, while a rewrite rule can rewrite an entire substring at once.
Substitution is a single-valued function while in a rewriting system, several rewriting rules can apply to any given substring.
A substitution must specify what value is substituted for each symbol. Rewriting systems need not apply in all situations.

I would say that the first two are the major differences. You can define substitutions so that they are partial functions, and then the third difference doesn't apply.