Is it possible to tell if two sequences of assembly instructions are semantically equivalent? In a modern instruction set like x86-64 there are many many many ways to accomplish the same task using a series of old simple instructions all the way up to the complex SIMD instructions. If one wanted to determine the semantic equivalence of a series of instructions, could this be done rationally or must it only be done experimentally?

For the sake of simplicity I am restricting the number of instructions in a series to something like ten.

The naive way to solve the problem would be to generate all of the potential inputs and experimentally check the results.

A slightly smarter way might be to determine the edges of the input states and only test those.

But I'm wondering if there's a way to represent each of the assembly instructions (and series of instructions) as a data structure that could be compared. Is this a tractable problem? Or is this clearly something like the halting problem?

Intuitively this feels like something similar to what happens inside a compiler.

If you restrict to programs of some fixed, finite length then yes, this is decidable. There are only a finite number of possible programs so there is a finite list of which ones are equivalent to one another. A program that is hard-coded with that list can answer the question just by looking up the two programs.

However, if you don't restrict the length of the programs, the problem becomes undecidable: if it were decidable, you could solve the halting problem ("Does program $P$ halt with input $I$?") by rephrasing it as "Is the program that simulates $P$ running on input $I$ equivalent to this trivial program that always halts?"

As an aside, why do you feel that a compiler would need to do this? Compilers just take a program represented in one form (source code) and translate it into another form (the executable image). The translation process guarantees that the two are semantically equivalent, so there's no need to check.


Finding the height of all nodes in a forest I have a forest, i.e., nodes with directed edges and no cycles (directed or undirected). I define the height of a vertex $v$ as 0 if it does not have any incoming edges, or the maximum number of edges to traverse in reverse to reach a vertex of height 0.

I also know that the average degree of a node is a small constant, say 2 or so. To find the height of all vertices, I can think of two algorithms:

Walking Algorithm

Go through and mark $h=0$ for vertices with no incoming edges.
For each vertex with $h=0$, follow the outgoing edges, updating the height of each encountered vertex if it's previous height is smaller.

Frontier Algorithm

Go through and mark $h=0$ for vertices with no incoming edges, and mark these as the frontier.
For every frontier vertex, see if it's parent has children at or below the frontier, If it does, mark the parent as having $1$ plus the largest height among its children. Mark the parent as being on the frontier.
Repeat 2 until there is nothing beyond the frontier.

My questions:

Is there a name for this problem, and a well known fastest solution?
I tend to think simply walking up from all the $h=0$ vertices is the fastest solution. Am I right?

First of all, it depends a bit how you can access your data to say which algorithms works best.

Anyway, I would suggest to determine the heights in a top-down fashion rather than bottom-up. I personally think that a top-down approach is conceptually nicer and easier to analyze. For any vertex $v$ in the forest it is true that

$$\text{height}(v)=\begin{cases}
\left(\max_{u\text{ child of }v}\text{height}(u)\right)+1 & \text{if $u$ is not a leaf} \\
\hskip4ex 0 & \text{otherwise}
\end{cases}.
$$

So you can scan for all roots, and then determine the heights by divide an conquer. You will touch every vertex at most twice (scanning for the roots + traversing). In the approach that you have suggested you might have to touch some vertices many times.

Btw, since you have a forest, you have less edges than vertices, so you know that you have average degree less than two (and therefore you can test for roots in linear time).


Is this problem about picking optimal entries of a matrix NP-complete? I am trying to solve a real-world problem that I was able to reduce to the problem described below. I would like to know the following things:

Is there literature about this problem?
Is the corresponding decision problem NP-complete?
Do you know an efficient algorithm to solve the problem?
If not, what would be a good technique to solve it approximately?

The problem is as follows. Given a $n \times m$ matrix $M$ with entries in $[0, 1]$, and a function $a \colon \{1, \ldots m\} \to \mathbb{N}$. For each column $j$, we want to pick $a(j)$ entries in that column, such that in each row, at most one element was picked. We want to do this in such a way that the sum of the picked values is maximized.

More formally, find a function $T\colon \{1, \ldots n\} \to \{1, \ldots m\} \cup \{\bot\}$ which maps each row to a column (or $\bot$), with the following two properties:

$\forall j \in \{1, \ldots m\} \colon \lvert T^{-1}(j)\rvert = a(j)$
The following expression is maximized: $$
 \sum_{\substack{i=1 \\ T(i) \neq \bot}}^n M_{i, T(i)}
$$

Of course, you could also define it the other way around, with each column mapping to a set of rows. Finally, the corresponding decision problem is in NP, as the function $T$ acts as a certificate.
I tried a reduction to knapsack, as the two seem quite similar, but I was unsuccessful.

Reduce to maximum-weight bipartite matching.

If you just wanted  for each j, pick at most a($\hspace{.015 in}$j) entries from the j-th column ,

then the reduction would be

One of the parts is    one vertex for each row.

The other part is    for each j, a($\hspace{.015 in}$j) vertices for the j-th column .

The weight of each edge is the corresponding matrix entry.

and the reasoning would be

The  one vertex per row  ensures that at most one element will be picked for each row.

The  a($\hspace{.015 in}$j) vertices for the j-th column  allows the j-th column to be

used a($\hspace{.015 in}$j) times but prevents it from being used more than that.

The weights of the edges make the total weights of the matchings

correspond to your objective function.

.

For  for each j, pick exactly a($\hspace{.015 in}$j) entries from the j-th column ,  you'd do:

Check whether-or-not    n  <  a(1) + a(2) + a(3) + ... + a(m-1) + a(m)  .

If that inequality is true, then there are no feasible solutions.

Otherwise, construct the bipartite graph like above but letting the edge weights be

a(1) + a(2) + a(3) + ... + a(m-1) + a(m) + 1  +  the corresponding matrix entry  .

This will make it so that all maximum-weight matchings use the whole column part,

thereby indicating exactly a($\hspace{.015 in}$j) entries for each j-th column.


How can we find a palindrome within a string? The problem requires us to find the substring within a string which happens to be a palindrome. Multiple palindromes are also allowed.
For example, in "LODHIHDAK"  "DHIHD" is a palindrome.

Comparing the reversed string with the original string to identify the common substring is one way but it isn't fool-proof.

For example,In the case of "KLXABAXYC", it would work.But in the case of "ABACDGFDCABA", it would not.

I was wondering if brute force could be used but I don't understand how.I'm looking to find the longest palindrome.

Of course, every letter is a one letter palindrome - so let's assume you are looking for a palindrome that is at least two letters long.

If your goal is just to find any palindrome in a string $\{a_i\}$(rather than finding all palindromes or finding the longest palindrome, for example) then you only need to consider two cases:

1) If $a_n=a_{n+1}$ for any $n$ then you have found a two letter palindrome.

2) If $a_n=a_{n+2}$ for any $n$ then you have found a three letter palindrome.

Any longer palindrome must contain a two or a three letter palindrome as a substring.


Meaning of L* if L is a language I can't find anywhere the meaning of $L^*$, given that $L$ is a language. I know $^* $ means repetition, for example $0^*$ = $\{ \epsilon, 0, 00, 000, \dots \}$. Or if $A$ is an alphabet $A^*$ are all the possible words.

Does $L^*$ mean the language whose words are the concatenation of the words of $L$?

For example if $L=\{ 01^n \mid n>0 \}$

then is $L^* = \{ 01^{n_1}01^{n_2} \dots \mid n_1>0, n_2>0, ... \} $?

Given a language $L$, let $L_0 = \{\epsilon\}$ and, for $i\geq 1$, let $L_i = \{w_1\circ \dots\circ w_i \mid w_j\in L \text{ for each } j\}$, where $\circ$ denotes concatenation.  Then the Kleene closure of $L$ is the language $L^* = \bigcup_{i\geq 0} L_i$.


Hint on median of two sorted lists, logarithmic time I'm looking for a hint to help me think through/solve the problem of finding the median of two sorted lists/arrays in O(log(m+n)) time, where m,n are the sizes/lengths of each list, respectively.

I can immediately think of an obvious O(m+n) time algorithm using big-theta of m+n space, as follows: Merge the two lists into a new list in O(m+n) time. Find the middle element of that list in O(1) time (more particularly, if the merged list is even in length, take the mean of the floor of the element at index (m+n)/2, and the ceiling of the element at index (m+n)/2, otherwise the merged list length is odd and just use the element at (m+n)/2... potentially update logic for off-by-one depending on zero- or one-indexing).

But I don't immediately see how the median could be found in logarithmic time. Any hints would be appreciated!

Hint: Given any element, you can determine its relative position (in the sorted merged array) in time $O(\log m + \log n)$ using binary search. Use this primitive together with binary search to determine the median.


Why Church-encoded types aren't sufficient to express inductive proofs? I've heard some claims that the calculus of constructions without inductive types isn't powerful enough to express proofs by induction. Is that correct? If so, why isn't the Church-encoding sufficient for that?

How would you prove inside the pure CoC that the induction principle holds of the Church numerals? See Thomas Streicher's, Independence of the induction
principle and the axiom of
choice in the pure calculus
of constructions.


Is this problem NP-complete? Let there be a set of cardinality $n\in \mathbb{N}$. Let there also be $n$ subsets of that set. What is the smallest k such that union of some $n-k$ of those subsets is of cardinality at most $k$? The problem is very similar to minimal $k$ union problem, but is more specific, how can I prove it is NP-complete?

Our problem is NP-complete by a reduction from MAXIMUM BALANCED BICLIQUE PROBLEM (MBBP).

MBBP problem:
Input: A bipartite graph $G(U, V, E)$ and an integer $k$
Output: YES if there exists $A\subseteq U$  and $B\subseteq V$ with $|A|=|B|=k$ and $G[A, B]$ is a biclique, NO otherwise

Given an MBBP instance $G, k$, output the following instance of our problem: $(\bar G, n-k)$ where $\bar G$ is the complement bipartite graph of $G$, namely $\bar G = (U, V, U\times V - E)$.
First, requirement that $|U| = |V|$ in our problem can be easily obtained by adding dummy vertices without harming the hardness of MBBP.
Second, we will show that $(G, k)$ is a YES instance of MBBP iff. $(\bar G, n-k)$ is a YES instance of our problem.
If $(G, k)$ is a YES instance of MBBP, then there exist $A\subseteq U$ and $B\subseteq V$ such that $|A| = k$ and $|B| = k$ and $G[A, B]$ is a biclique. It follows that in $\bar G$ the neighborhood of $A$ is a subset of $V - B$ (all the edges in the biclique are removed). And $|A| = k = n - (n - k)$ and $|V - B| = n - k$. Thus, $(\bar G, n - k)$ is a YES instance of our problem.
Conversely, if $(\bar G, n - k)$ is a YES instance of our problem, then there exist $A\subseteq U$ such that $|\cup_{v\in A}N_{\bar G}(v)| \leq n - k$. By complementing this, we have $|\cap_{v\in A}N_G(v)| \geq k$. So by arbitrarily choose $k$ vertices in $\cap_{v\in A}N_G(v)$ to form $B\subseteq V$. We have shown the existence of a biclique in $G$ satisfying requirement of the original MBBP instance. Hence, $(G, k)$ is a YES instance of MBBP.


Identifying events related to dates in a paragraph Is there an algorithmic approach to identify that dates given in a paragraph correlate to particular events (phrases) in the paragraph?
Example, consider the following paragraph:

In June 1970, the great leader took the oath. But it was only after May 1972, post the death of the Minister of State, that he took over the reins of the country. While he enjoyed popular support until Mid-1980, his influence began to fall thereafter.

Is there an algorithm (deterministic or stochastic)# that can generate a 2-tuple (date, event), where the event is implied, by the paragraph, to have occured on the date? In the above case:

(June 1970, great leader took oath)

(May 1972, took over the reins)
or better yet

(May 1972, the great leader took over the reins)

(1980, fall in influence)

#Later addition

In general, the problem of identifying dates and other temporal markers in text is called the problem of extracting temporal references. The search linked will take you to papers related to this.


Is there a regular grammar for the language $\{ w : |w|_0 = |w|_1 \}$? I need to prove whether the language $ L = \{w \in \{0,1\}^* \mid |w|_0 = |w|_1 \}$ can be written as a regular grammar. Obviously it can, but how do I prove it?

A language can be described by a regular grammar if and only if it is regular. Your language is nor regular, hence it cannot be described as a regular grammar.


Shortest path in graph by flipping binary colored nodes to one color Given a graph consists of two-colored nodes(e.g. white and black) and a starting node, and every time you visit a node, its color is switched(from black to white, or, white to black), how to find the minimum path such that all nodes are converted to black (or white, since it is equivalent)?

This problem is $NP$-complete, there is a quite simple reduction from Hamiltonian Path. Therefore, there's (likely) no way to solve this problem efficiently in general, so the solution method will need to be tailored to the inputs you are interested in solving (brute force for small instances, heuristic methods for large instances, specialized methods for instances with special structure,...).


What is `wasted space` parameter and why is it O(n) for a linked list I'm reading a book on data structures and there is a comparison between linked list, array and dynamic array. The parameter name is wasted space. Here are the values:

\begin{array}{cc}
    \text{Linked list} & O(n)\\
    \text{array}        & 0 \\
    \text{dynamic array}& O(n)
\end{array}

What is the wasted space parameter and why is it $O(n)$ for a linked list?

Different people seem to define "wasted space" in different ways. Some authors define it as any space in a data structure that's not used to store actual data; others define it as space that could be used to store data but isn't being so used at the moment.

So, in the first definition, a linked list has $O(n)$ wasted space because every entry of the list contains some piece of data but also a pointer, so a constant fraction of the space taken up by the data structure is "wasted". (I think this is a silly definition of "waste": the space taken up by the pointers isn't wasted; it's an overhead.)  In the second definition, a half-full hash-table has 50% wasted space (again, $O(n)$).


The most efficient algorithm for finding the highest valid number for an API I have many API endpoints that take IDs that are constantly increasing. I want an algorithm to find the highest number in the least amount of requests. I need to do this without knowing what the previous highest number was. I am thinking something like binary search would work but would it be the most efficient? I also don't know what the maximum would be.

Assuming $1$ is always a valid ID, you can solve your problem in about $2 \log v$ queries where $v$ is the maximum value by using exponential search and binary search.
Query the API using powers of two ($2,4,8,\dots$) until you find the smallest power of two $x$ such that $x > v$. Clearly $x \le 2v$.
This requires up to $1+\lceil \log_2(v) \rceil$ queries.
Then use binary search in the range $[v-1, 2v)$ to find the exact value for $v$. This requires at most $\lceil \log_2(1+v) \rceil$ queries.


Optimal myopic maze solver I was fooling around with Google Blocky's Maze demo, and remembered the old rule that if you want to solve a maze, just keep your left hand to the wall. This works for any simple-connected maze and can be implemented by a finite transducer.

Let our robot be represented by a transducer with the following actions, and observables:

Actions: go forward ($\uparrow$), turn left ($\leftarrow$), turn right ($\rightarrow$)
Observables: wall ahead ($\bot$), no wall ahead ($\top$)

Then we can build the left-hand maze solver as (pardon my lazy drawing):

Where seeing an observable will make us follow the appropriate edge out of the state while executing the action associated with that edge. This automaton will solve all simply-connected mazes, although it might take its time following dead ends. We call another automaton $B$ better than $A$ if:

$B$ takes strictly more steps on only a finite number of mazes, and
$B$ takes strictly fewer steps (on average; for probabilistic variants) on an infinite number of mazes.

My two questions:

Is there a finite automaton better than the one drawn above? What if we allow probabilistic transducers?
Is there a finite automaton for solving mazes that are not necessarily simply-connected?

If I understood well the question, I think that you can apply a speedup trick to get faster automata on an infinite number of mazes (providing that the exit is placed on one of the border): you can simply use the internal states to store a finite number of steps and recognize dead ends like the one in the figure:

When a right-hand following automaton is in position $A$ and its state "signals" that it has just followed a closed square (with fixed size encoded, not an arbitrary large square), then it can safely turn left and avoid visiting the dead end zone.
As underlined in my comment below, the automaton will apply the shortcut on every maze that contains one (or more) "submazes" like the one in the figure, so it will perform better on infinitely many mazes. On the mazes that don't contain a submaze like the one in the figure it will perform like a standard right-hand following automaton.

In a similar manner you can encode a finite number of different  fixed size shapes to avoid dead ends and speed up your automaton. As a consequence, there is no "optimal" myopic maze solver for simply-connected mazes with the exit placed on the border.

The trick works if the entrance is placed inside the maze and the exit on the border, too; but if the exit is placed inside the maze, then it doesn't work because all locations must be visited and in this case your myopic solver is optimal.

Obviously you can't apply the same trick to solve non-simply connected mazes (but it should work if there is a fixed upper bound on the size of each unconnected component).


How to resize a large, distributed hash table? Many hash table implementations found in programming languages (such as Java's HashMap or Python's dict) dynamically increase the size of the hash table once the number of items reaches a certain threshold. In these cases, resizing the hash table means allocating a new, larger memory area, re-hashing all the items and moving them from the old to the new memory region. Because resizing is done "rarely", insertion is still O(1) amortized.

This may be fine if the hash table is stored in memory and if the number of items is relatively small, however what about large distributed hash tables?

Suppose that I have a cluster of 100 PostgreSQL databases, each one containing terabytes of data. What happens if I add a new database to the cluster? Will all the items be re-hashed and moved around? I strongly doubt that, as the operation could take several days to complete.

Hence my question: what is the strategy adopted in those cases?

Yes, after storing many items in a distributed hash table spread over a hundred computers, if hypothetically we used the sort of hash function popular for in-RAM hash table, adding another computer would cause every item to be re-hashed and nearly every item to move from one computer to another, which could take days.

So instead we use special hash functions specifically designed for DHT applications, which allow us to add computers and more-or-less immediately start using them and only re-arrange a few items. (Ideally, with around 100 computers, about 1 percent of the items in each and every computer already in the DHT would move to the new computer).
Confusingly, some people use "consistent hashing" to refer to any such system where relatively few items are re-shuffled when a new computer is added or removed from the system, although most use "consistent hashing" to refer to the one particular such system described below.

I now know of 4 different hash algorithms solve the distributed hash table problem, all of them (coincidentally?) published in 2001.
(Are there others?)

rendezvous hashing, also called highest random weight hashing (HRW):
A client with a list of computers Cj looks up some key K by giving each computer a score Sj = hash( K | Cj ).
The key, value pair K,V is stored on the computer with the highest score.
(For two-failure-tolerant systems, the key,value pair K,V is stored on the three computers with the highest scores).
consistent hashing:
A client with a list of computers Cj maps each computer to a location on the the edge of a circle. The client looks up some key K by starting at the point where K maps onto the circle, and walking clockwise until it hits a computer. (Each computer is actually mapped to many "replica" points on the edge of the circle). (For two-failure-tolerant systems, the key,value pair K,V should be stored on the first three different computers it walks across).
The "distance" walked is d = (unsigned int)(hash(K) - hash(Cj)).
In some implementations, such as Chord and Pastry, none of the computers nor the client really knows all of the computers in the DHT. The client sends a request to a few of the closest computers ''that it knows'', asking about the key. Each such computer either responds with the (key, value) data item if it has it, or with a list of other, closer computers.
content addressable network (CAN) has some similarities to consistent hashing, except instead of a one-dimensional circle-edge, it uses a multi-dimensional torus.
Kademlia algorithm:
A client that only knows about a few of the computers in the DHT looks up some key K by finding the computers that are "close" to the key, where the "distance" is calculated as d = hash(Cj) XOR hash(K). (This abstract "distance" function is completely uncorrelated with the real, physical distance in miles between servers). The client sends a request to a few of the closest computers ''that it knows'', asking about the key. Each such computer consults its tables and reply with a list of the closest computers to the desired key ''that it knows''. The client sends a request to a few of those ever-closer computers, asking about that key, and repeats that process until no new nodes are returned that are closer than the best previous results. (For two-failure-tolerant systems, the key,value pair K,V should be stored on the three "closest" computers to that key K).

There is one additional technique often used to make adding a new computer to a DHT appear "instantaneous": indirection.
Immediately after adding a new computer to a DHT system, most items should remain in the same place, but there are typically lots of items that need to move from each old computer to the new computer -- it may take a day before all those items are moved, typically as a low-priority "background task".
Long before all those items are moved, each old computer sends a brief summary of those items to the new computer, and when some client asks the new computer for some particular item, the new computer either (a) admits to the client it doesn't have that file yet, and tells the client which one of the old computers still has that item, or (b) bumps up the priority of moving that item to a "foreground task", possibly streaming each block of that item to the client as soon as it is received from the old computer.


Check if K-Sum Variation is NP-Complete Problem

Given a range of integers $\{a,a+1,...,b-1,b\}$, find a subset of size $k$ such that the sum is equal to $s$.

Question

This problem came from evaluating some scheduling algorithms that I am interested in optimizing for some small home grown useless embedded system I am playing with. My problem is that I do not know if this problem is NP-Complete like the K-Sum problem. I am guessing it might be but it has been a while since I have dealt with proofs pertaining to NP problems. I remember something with SAT, but looking around did not jog any memories (at least any good ones).

How might I prove it is or is not NP-Complete?

Nice question!

  Given a range of integers $\{a,a+1,...,b−1,b\}$, find a subset of size $k$ such that the sum is equal to $s$.

Well, this problem can be solved in $O(n)$ time, where $n$ is the number of given integers.

(Continuity of $k$-sums). Given integers $\{a,a+1,...,a+n-1\}$, an integer $k$, $1\le k\le n$ and an integer $s$, there are $k$ integers whose sum is $s$ if and only if $ka+\dfrac{(k-1)k}2\le s\le k(a+n-1)-\dfrac{(k-1)k}2$

Here is the algorithm.

Check if $ka+\dfrac{(k-1)k}2\le s\le k(a+n-1)-\dfrac{(k-1)k}2$. If not, return none.

Let $sum = s$. Let $S$ be an empty set.
For $i$ from 0 to $n-1$ do the following.

Let $temp = sum -(b - i)$.
If  $temp\le (k-i-1)(a+n-1)-\dfrac{(k-i-2)(k-i-1)}2$,
let $sum = temp$ and insert $b-i$ into $S$. Otherwise, do nothing.
If $sum = 0$, break the loop.

Return S.

Here are a few related exercises.

Exercise 1. Prove the proposition of continuity of $k$-sums.

Exercise 2. Show the algorithm is correct.

Exercise 3. Modify the algorithm so that it will try adding the smallest number first.

Exercise 3. Modify the algorithm so that it will run in $O(k)$ time.


Find pth percentile of a stream of numbers I want to find the pth percentile of a stream of integers, exactly (not approximately).

If we know the number of integers which will be coming in the stream and the numbers can fit into the memory then we can simply sort the integers and find the pth percentile.

But, what if all the numbers can't be fit in memory?  How can we do that?

We can assume all integers are 64-bit integers.

I'm afraid that it is not possible to solve this problem with above conditions. Sooner or later, while reading next element from stream, you will run out of memory and will have to throw away one of buffered elements. But without having any constraints on further elements in stream, it is always possible to construct such sequence of further elements in stream, so that thrown out element is the searched one.

A practical commercial-grade solution exists, though it produces approximate result:

Allocate memory for as many numbers as you can afford
Use reservoir sampling atop of allocated memory to sample numbers from stream
When end of stream is reached, search for percentile among samples

To get exact solution, you need to either know number of elements in advance, or to have enough memory, or to have knowledge of stream properties (e.g. stream is monotonic). Keywords are "running median" and "n-th order statistics".


Why are Oracle Separations Counted as Evidence toward Unconditional Separation? Particularly, we already have some oracle separation results such as $\mathbf{BPP}^A\neq \mathbf{BQP}^A$ [Simon], $\mathbf{NP}^A\not\subseteq \mathbf{BQP}^A$ [BBBV], and $\mathbf{BQP}^A\not\subseteq \mathbf{NP}^A$ [Bernstein and Vazirani]. But given that most problems are non-relativising, how does such oracle separation even counted as evidence of unconditional separation? Or do we need to discuss it case-wisely?

At best, the evidence given is only heuristic and informal, but it is still important. Oracles in the examples you gave do address the general question: how does quantum computing compare to nondeterminism and randomness, in power? The oracles definitely do not answer the original unrelativized questions, rather they provide a different (related) black-box model where the question provably has a negative answer. Since unconditional lower bounds are very difficult to come by, oracles can be useful information, but again it's only heuristic.


Data structure for interval subset queries I have a set $S$ of intervals.  I'd like to store them in a data structure, so that I can handle the following query efficiently: given a query interval $q$, count the number of intervals $s \in S$ that contain $q$, i.e., count the number of intervals $s \in S$ such that $q \subseteq s$.
(This is like a stabbing query, but now the query is an interval, not a single point.)
Is there an efficient data structure for this?  Ideally, one that can be constructed in $O(n \log n)$ time and where each query can be answered in $O(\log n)$ time, where $n$ denotes the number of intervals in $S$?

Let $F(I) = |\{s \in S : s \subseteq I\}|$ where $I$ is an interval.
If $[a, b]$ is our query interval, we can make the following partition where $R$ is our desired result:
$$R =n -F((-\infty, b)) - F((a, \infty)) + F((a, b))$$
The first two queries can be answered simply using a sorted data structure of respectively endpoints and startpoints.
The last query is the dual of this problem, which has an answer here on this site.


When is a 1-in-3 SAT clause satisfied? How does exactly 1 in 3 sat work given the variables Xi, Xy, Xz if one of the variables in the formula are negative.
We know that the results are if they are all positive given that:
R(Xi, Xy, Xz) =
TFF
FTF
FFT

How would the result look like if one or two of the variables were negative? R(-Xi, Xy, Xz) or R(-Xi, Xy, -Xz)

A 1-in-3 clause consists of three literals. It is satisfied if exactly one of these literals is true. For example, if the three literals are $\bar{x}_1,x_2,x_3$, then the three truth assignments (for $x_1,x_2,x_3$) which satisfy the clause are $(F,F,F)$, $(T,T,F)$, $(T,F,T)$.


How to solve this Planning Domain Definition Language (PDDL) question? These are 5 action descriptions with conditional effects:

Action(A, Precond:{X}, Effect:{when P : ~X), Z})
Action(B, Precond:{Y}, Effect:{when Z : ~P), ~Y,~Z,X})
Action(C, Precond:{~Z}, Effect:{when P : ~X), Y})
Action(D, Precond:{~X}, Effect:{when Q : X)})
Action(E, Precond:{Z}, Effect:{when Q : ~Z)})

What state would result from executing the action sequence [E,D,A,B,C] in the state {P,Q,Y,Z}?
I know the answer but I really don't know how to achieve it. Anyone please shed some light? (Please include workings)

I will turn my comment into an answer.  Recall that if your state is $\{P,Q,Y,Z\}$, and an effect of an action is $\sim\!Z$ (from now on written $\neg Z$), then the new state will not contain $Z$, i.e., the state will be, if nothing else is an effect, $\{P,Q,Y\}$.

Since the question asks what the result of a sequence of actions will be, we need to solve this in the order of that sequence.  The sequence asked was
$[E,D,A,B,C]$, and the state was $\{P,Q,Y,Z\}$?  Observe that we by square brackets denote a sequence (i.e., an ordered list) and by curly brackets, an unordered set (the usual kind).

Action $E$ in state $\{P,Q,Y,Z\}$:  Precondition $Z$ is good since $Z$ is in the state.  Effect is "when $Q$, $\neg Z$".  The new state will thus be $\{P,Q,Y\}$.  We omit writing $\neg Z$ since every element not occurring in the state will be assumed to be not held.

Action $D$ in state $\{P,Q,Y\}$:  Precondition $\neg X$ is good.  Effect: "when $Q$, $X$".  Hence new state will be $\{P,Q,X,Y\}$.

Action $A$ in state $\{P,Q,X,Y\}$:  Precondition is good, $X$ is in the state.  Effect: "when $P$, $\neg X$, and $Z$".  $P$ is in the state, hence we remove $X$ and we also add $Z$.  New state is $\{P,Q,Y,Z\}$.

Action $B$ in state $\{P,Q,Y,Z\}$: Precondition $Y$ is good.  Effect "when $Z$, $\neg P$, also $\neg Y$, $\neg Z$ and $X$".  $Z$ is true, hence we lose $P$.  We also lose $Y$ and $Z$ and gain $X$.  New state is $\{Q,X\}$.

Action $C$ in state $\{Q,X\}$: Precondition is $\neg Z$, so good.  Effect: "when $P$, $\neg X$, and $Y$".  This is the first time we encounter an implication in which the antecedent $P$ is false, so we don't remove $X$.  We still add $Y$, though.  Hence the new, and final state is
$$
\{Q,X,Y\}.
$$


Matrix Representation for logical gates? I have been trying to find if there are other matrix type representations logical circuits, in the example below, $$\begin{bmatrix} 1 & 0\\ 1 & 1\\ \end{bmatrix} \equiv \, \, \Rightarrow$$ where:

$$ \begin{bmatrix} X, \  \neg X  \end{bmatrix}\begin{bmatrix} 1 & 0\\ 1 & 1\\ \end{bmatrix} \begin{bmatrix} Y \\ \neg Y \\ \end{bmatrix} = \begin{bmatrix} X \oplus \neg X, \ 0 \oplus \neg X \end{bmatrix} \begin{bmatrix} Y \\ \neg Y \\ \end{bmatrix} = \begin{bmatrix} 1, \ \neg X \end{bmatrix} \begin{bmatrix} Y \\ \neg Y \\ \end{bmatrix}$$ $$ = Y \oplus (\neg X \neg Y) = X \Rightarrow Y$$

Note that the juxtaposition of two variables without an operator corresponds to conjunction i.e. $XY = X \wedge Y$ and of course $1 \wedge X = X$ and $0 \wedge X = 0$ and are written accordingly. Actually all of the propositional logical operators can be done with a unique binary $2 \times 2$ matrix - it is fascinating.

Yes, "all of the propositional logical operators can be done with a unique binary 2×2 matrix".

In fact, every possible map $g: \{0,1\}\times\{0,1\}\to\{0,1\}$ can be done with a unique binary 2x2 matrix.

Here is a proof.

$$\begin{align}
 &\quad \begin{bmatrix} X, \  \neg X  \end{bmatrix}\begin{bmatrix} A & B\\ C & D\\ \end{bmatrix} \begin{bmatrix} Y \\ \neg Y \\ \end{bmatrix} \\&= \begin{bmatrix} XA \oplus \neg XC, \ XB \oplus \neg XD \end{bmatrix} \begin{bmatrix} Y \\ \neg Y \\ \end{bmatrix} \\
&= XAY \oplus \neg XCY \oplus XB\neg Y \oplus \neg XD\neg Y\\
\end{align}$$

Suppose the above expression equals $g(X,Y)$.

Let $X=0, Y=0$, we get $0\oplus0\oplus0\oplus D=D=g(0,0)$.
Let $X=0, Y=1$, we get $0\oplus C\oplus0\oplus 0=C=g(0,1)$.
Let $X=1, Y=0$, we get $0\oplus0\oplus B\oplus 0=B=g(1,0)$.
Let $X=1, Y=1$, we get $A\oplus0\oplus0\oplus 0=A=g(1,1)$.

Conversely, if we have $A= g(1,1)$, $B= g(1,0)$, $C=g(0,1)$ and $D=g(0,0)$, the above expression can be verified to be equal to $g(X,Y)$ for all $X, Y$.

So we have proved that

$$ \begin{bmatrix} X, \  \neg X  \end{bmatrix}\begin{bmatrix} A & B\\ C & D\\ \end{bmatrix} \begin{bmatrix} Y \\ \neg Y \\ \end{bmatrix} = g(X,Y) \\ \Leftrightarrow A= g(1,1),\ B= g(1,0),\ C=g(0,1),\ D=g(0,0)$$

If we use in-fix notation for $g$, we have
$$ \begin{bmatrix} X, \  \neg X  \end{bmatrix}
\begin{bmatrix} 1g1 & 1g0\\ 0g1 & 0g0\\ \end{bmatrix}
\begin{bmatrix} Y \\ \neg Y \\ \end{bmatrix} = XgY, $$
or
$$ \begin{bmatrix} 1g1 & 1g0\\ 0g1 & 0g0\\ \end{bmatrix}
 \equiv g. $$
In particular, we can substitute $g$ by anyone of $\land, \lor, \oplus, \odot, \Rightarrow, \Leftarrow, \equiv$.

For more related concepts and computation, please check boolean rings.


How is this grammar LL(1)? This is a question from the Dragon Book. This is the grammar:

  $S \to  AaAb \mid BbBa $
  $A \to \varepsilon$
  $B \to \varepsilon$

The question asks how to show that it is LL(1) but not SLR(1).

To prove that it is LL(1), I tried constructing its parsing table, but I am getting multiple productions in a cell, which is contradiction.

Please tell how is this LL(1), and how to prove it?

First, let's give your productions a number.

  1 $S \to AaAb$
  2 $S \to BbBa$
  3 $A \to \varepsilon$
  4 $B \to \varepsilon$

Let's compute the first and follow sets first. For small examples such as these, using intuition about these sets is enough.

$$\mathsf{FIRST}(S) = \{a, b\}\\
\mathsf{FIRST}(A) = \{\}\\
\mathsf{FIRST}(B) = \{\}\\
\mathsf{FOLLOW}(A) = \{a, b\}\\
\mathsf{FOLLOW}(B) = \{a, b\}$$

Now let's compute the $LL(1)$ table. By definition, if we don't get conflicts, the grammar is $LL(1)$.

    a | b |
-----------
S | 1 | 2 |
A | 3 | 3 |
B | 4 | 4 |

As there are no conflicts, the grammar is $LL(1)$.

Now for the $SLR(1)$ table. First, the $LR(0)$ automaton.

$$\mbox{state 0}\\
S \to \bullet AaAb\\
S \to \bullet BbBa\\
A \to \bullet\\
B \to \bullet\\
A \implies 1\\
B \implies 5\\
$$$$\mbox{state 1}\\
S \to A \bullet aAb\\
a \implies 2\\
$$$$\mbox{state 2}\\
S \to Aa \bullet Ab\\
A \to \bullet\\
A \implies 3\\
$$$$\mbox{state 3}\\
S \to AaA \bullet b\\
b \implies 4\\
$$$$\mbox{state 4}\\
S \to AaAb \bullet b\\
$$$$\mbox{state 5}\\
S \to B \bullet bBa\\
b \implies 6\\
$$$$\mbox{state 6}\\
S \to Bb \bullet Ba\\
B \to \bullet\\
B \implies 7\\
$$$$\mbox{state 7}\\
S \to BbB \bullet a \\
a \implies 8\\
$$$$\mbox{state 8}\\
S \to BbBa \bullet \\
$$

And then the $SLR(1)$ table (I assume $S$ can be followed by anything).

    a     | b     | A | B |
---------------------------
0 | R3/R4 | R3/R4 | 1 | 5 |
1 | S2    |       |   |   |
2 | R3    | R3    | 3 |   |
3 |       | S4    |   |   |
4 | R1    | R1    |   |   |
5 |       | S4    |   |   |
6 | R4    | R4    |   | 7 |
7 | S8    |       |   |   |
8 | R2    | R2    |   |   |

There are conflicts in state 0, so the grammar is not $SLR(1)$. Note that if $LALR(1)$ was used instead, then both conflicts would be resolved correctly: in state 0 on lookahead $a$ $LALR(1)$ would take R3 and on lookahead $b$ it would take R4.

This gives rise to the interesting question whether there is a grammar that is $LL(1)$ but not $LALR(1)$, which is the case but not easy to find an example of.


I built a mechanical computer powered by marbles. What are its theoretical limitations? Over the last couple years, I built a mechanical computer powered by marbles and made a game out of it. It's similar to the old Digi-Comp II, except for two key differences:

Parts are repositionable on the board.
You can connect multiple 'bits' together using gears. When one of these bits is flipped, it flips the other bits connected to it.

The above link describes how it works. My question is, what are its theoretical limitations? My theoretical computing background is weak, so please ELI5.

edit: I'm not interested in the obvious limitations: speed (not going to win any races there...), board size, or # of marbles. I'm more interested in its theoretical limitations. Maybe it would help to split it into two questions:

How can it be proven (or disproven) to be Turing-complete?
If more than 3 gear bits are connected together, the friction becomes too great for a marble to turn all of them at once. Does that create additional limitations?

Thanks - I'm really excited to read your answers! I've been thinking about this for a long time.

What you have right now is a concrete computer. We cannot compare it to a computational model until it is properly formalized.

My intuition is that the board could be modeled as a dataflow architecture. Computational models conceived according to this paradigm can be Turing-complete, but (as was said in the comments) no concrete computer will ever be Turing-equivalent, and I don't think you should worry about this. All real computers are just (imperfect) working metaphors of formal computational models.

Should you come around to the idea of more closely imitating a Turing-equivalent dataflow machine, there are a few issues that could be addressed in order to "strengthen the metaphor", so to speak. Introducing cycles and composition of machines would be the two most important things, in my opinion, but I think your machine is already pretty amazing. It serves its purpose very well, and these "improvements" could sacrifice its usability.


Why do we not use CFGs to describe the structure of lexical tokens? This was an exam question for my course and I am struggling to actually answer it in a way that is not fluff.

Here is my current answer:

CFGs describe how non-terminal symbols are converted into terminal symbols via a parser. However, a scanner defines what those terminal symbols convert to in terms of lexical tokens. CFGs are grammatical descriptions of a language instead of simply defining what tokens should be scanned from an input string.

What is the correct way to answer this?

You don't use CFGs because typically lexical analysis can be performed using regular automata, and these are faster than context-free parsers. It's a question of efficiency.


Finding a perfect matching using an LP I have a basic question about the power of Linear Programming that has been bothering me for some time.  I believe there is something simple I am missing.

Linear Programming is $\mathsf{P}$-complete, which means that every problem in $\mathsf{P}$ can be reduced to it using an $\mathsf{NC}$ reduction.  (See the wiki for some nice background)

However, it has been shown that the perfect matching polytope has exponentially many facets (see this recent STOC paper for example. This shows it even has exponential extension complexity---i.e. even using extra dimensions we require an exponential number of inequalities).

However, the classic Blossom Algorithm can find a perfect matching in polynomial time--determining if a graph has a perfect matching is in $\mathsf{P}$.

This seems like a conflict to me: we can reduce the perfect matching problem to Linear Programming, but its polytope must be exponentially large.  What am I mising?  Is there processing during the reduction that avoids using the entire matching polytope?

The lower bounds on extended formulations (the one by Rothvoss for example) are lower bounds for a very specific way of using Linear Programming to solve a problem (matching in this case).

In this model, given a graph you would like to write one linear program, changing whose objective function gives you the right matching corresponding to any weight function on the given graph. This requirement results in the restriction that the feasible region of such an LP must project down to the matching polytope. The lower bound is not immediately applicable if you provide different LPs for different weights, or you use the objective function in a non-trivial way. (Note that in this model, we use the weights on the edges as the objective function without any modification)

Allowing different LPs for different weights obviously breaks the result: First solve the weighted problem and then produce a trivial LP whose feasible region contains exactly one point (the answer). This LP would trivially have small size.

Now, you can argue similarly that allowing weights to be manipulated arbitrarily allows you to "cheat" and write small LPs too.

The discussion about P-completeness of Linear Programming becomes interesting if you ask the following.

Q: Can you use Linear Programming to solve the matching problem in a "black box" fashion "with minimal extra computation"?

The answer in this case is yes, and the extra computation turns out to be just encoding the input graph in a trivial way as the objective function (by essentially taking the characteristic vector of edges with encoding digits +/-1 instead of 0/1). This extra computation seems reasonable and so the LP encoding of the matching problem in this case seems interesting. The LP in this case turns out to be of small size precisely because matching is in P and Linear Programming is P-complete.


Convention of a += operator in pseudocode I have to write some algorithm in pseudocode for a paper. For this I have the "$\leftarrow$" to assign a value.
$x \leftarrow y^2$
now I want to write a method which adds to the variable. In normal Python code I would write x += 1 for this. Is there a style convention how to layout this in pseudo-code in a paper? I dont really like the redundance of $x \leftarrow x+1$.

The +=et al are C shortcuts, adopted by many languages. Most anyone should understand them.
Then again, this is (pseudo)code, you certainly can make up you own variant. Just make sure to define clearly what any not-so-standard constructions mean (I'd go for += and so on, but then again, I'm a C fan...). But make sure to be consistent, i.e., use = for assignment and += for your operation, don't mix it with e.g. $\leftarrow$, and state that you'll use C notation for assignments.
Whatever you do, always keep in sight that the objective is understanding by your gentle reader, not extreme rigour or algorithmic details.


What does Stroustrup mean by 7/8ths of MIPS being in the vector units? In his article Software Development for Infrastructure Stroustrup states the following:

  Hardware improvements make the problems and costs resulting from
  isolating software from hardware far worse than they used to be. For a
  typical desktop machine,

  3/4ths of the MIPS are in the GPU;
  from
  what’s left, 7/8ths are in the vector units; and
  7/8ths of that are
  in the “other” cores.

  So a single-threaded, nonvectorized, non-GPU-utilizing application has access to roughly 0.4 percent of the compute power available on the device (taken from Russell Williams).

Now I understand the GPU and threading issues of performance. But since threading and vectorization are mentioned as separate things, I would like to know what does it exactly mean when you say that vector units are X% of the computing power.

Imagine you have a 256 bit vector floating point unit which can perform eight 32 bit operations in parallel. How many operations per second can you perform with or without using the vector FPU?

Imagine you have eight cores.  How many operations can you perform in one second using one core or all eight cores?


What is the number of expressions containing n pairs of matching brackets with nesting limit? I know the answer without nesting limit is the Catalan number. My question is, specifically, is there a recurrence relation that gives the number of expression containing $n$ pairs of matching brackets such that no more than $l$ open brackets are not closed at any given point?

For instance, for $n=3$ and $l=2$ the answer is $4$. All possible combinations are $(())()$, $()(())$, $()()()$, $(()())$. We cannot have $((()))$ since there are three open brackets that are not closed at the middle.

Okay. I think I may have figured it out myself. I invite everyone to check my answer to see if it makes sense. So the first bracket must be a left bracket and there must be some right bracket later on that corresponds to this first bracket. Inside these two brackets there is a valid bracket expression $A$ with depth at most $l-1$ and outside these two brackets there is another valid expression $B$ with depth at most $l$ (since it is not already contained in a pair of brackets like $A$). Also, just like the definition of Catalan numbers, if $n=0$ then the number of valid expressions is $1$. If $n\neq 0$ and $l=0$ then the number of valid expressions is $0$ (since if $n\neq 0$ then we must have at least one pair of brackets, but $l=0$ means that we cannot have more than $0$ open bracket at any time, meaning that there is no way we can construct any valid bracket expressions). So the recurrence relation I got is:
\begin{align}
C(i, j)= \begin{cases}
1 & i=0 \\
0 & i\neq 0, j=0 \\
\sum\limits_{k=0}^{i-1} C(k, j-1)\cdot C(i-k-1, j) & \text{otherwise.}
\end{cases}
\end{align}


Solution verification: solving $T(n) = T(n-1) + 2/n$ I was wondering if someone could possibly verify my solution to the following:

I'm trying to solve the recurrence relation $T(n) = T(n-1) + 2/n$. To get it into the form of the Master Theorem, I note that for sufficiently large $n$, $n - 1 \geq n/2$. Moreover, $2/n = O(1)$. Thus, we can rewrite the equation as $T(n) = T(n/2) + O(1)$. Since $\log_21 = 0$, it then follows directly from the Master Theorem that $T(n) = O(\log(n))$.

-Thanks!

Although the final result is correct, your solution is not.

The recurrences of the form $T(n) = T(n-1) + 2/n$ is often called "decrease and conquer"; while the ones of the form $T(n) = T(n/2) + O(1)$ is called "divide and conquer". Generally, they are different and cannot be reduced to each other.

Hint: To solve $T(n) = T(n-1) + 2/n$, you can expand it and notice that $1 + 1/2 + \cdots + 1/n = H(n) = \Theta(\lg n)$, the $n$-th partial sum of the harmonic series (wiki).


Why is the star property important According to the Bell-Lapadula model, write access is only to Subject $S$ on object $O$ provided if:
$L(S) \leq L(O)$ where $L$ is the clearance level for $S$ and classification for $O$. This seams counter intuitive. Are there any attacks that this protects against and what other benefits are presented by it?

This equation expresses a confidentiality property. There are two ways of looking at it: what does it permit and what does it prevent.

Prevented: writing secure information to an insecure place.
Permitted: writing insecure information to a secure place.

Clearly, the former is good, otherwise, for example, your PIN number (secure) could become accessible to untrusted third parties.

From a security perspective, the former is safe, because no secure information is leaked. It allows cases such as where you report your daily activities (insecure) to your manager (trusted).

One concern you may have is that writing insecure information to a secure place could lead to problems. These problems would be related to integrity. An integrity violation occurs when bad data from an untrusted source is written into a secure variable. If the data isn't checked for validity, it could mess up programs running securely.


What does it mean to "show algebraically" in propositional logic? The biconditional operator $\iff$ of Propositional Logic can be defined by the identity
$p \iff q \equiv (\lnot p \lor q) \land (\lnot q \lor p) \quad (1.1)$
Use the identity $(1.1)$ and identities from the list on page 2, to show algebraically that
$p \iff q \equiv (\lnot p \land \lnot q) \lor (q \land p)$
State which identity you are using at each step.

What does this question mean by asking to "show algebraically"? I have tried referring to my notes and online search but no luck with a definition! These propositions are already algebraic, are they not? Having some issues understanding the wording of the question. This is from a mock university test. I'm assuming it wants me to demonstrate using a truth table?

Although you haven't posted any of the logical rules the problem statement refers to, it is reasonable to assume they are similar to those found in many standard logic textbooks. To prove your identity, I will make use of
$$
\begin{align}
P \land Q & \equiv Q \land P, &\text{$\land$ commutativity} \\
P \land (Q \lor R) & \equiv (P \land Q) \lor (P \land R),  &\text{$\land$ distribution} \\
P \land \lnot P & \equiv \bot  &\text {(3)} \\
P \lor \bot &\equiv P, & \text{$\bot$ annihilation}
\end{align}
$$
where $\bot$ denotes falsehood. With that in mind
$$
\begin{align}
p \iff q \equiv & \\
(\lnot p \lor q) \land (\lnot q \lor p) \equiv &  & \text{By definition}\\
((\lnot p \lor q) \land \lnot q) \lor ((\lnot p \lor q) \land p) \equiv & &\text{By distribution of $\land$} \\
(\lnot q \land (\lnot p \lor q)) \lor (p \land (\lnot p \lor q)) \equiv & &\text{By commutativity of $\land$} \\
(\lnot q \land \lnot p \lor \lnot q \land q) \lor (p \land \lnot p \lor p \land q) \equiv & &\text{By distribution of $\land$} \\
(\lnot q \land \lnot p \lor \bot) \lor (\bot \lor p \land q) \equiv & &\text{By $(3)$} \\
(\lnot q \land \lnot p) \lor (p \land q) \equiv & &\text{By $\bot$ annihilation} \\
(\lnot p \land \lnot q) \lor (q \land p) \equiv & &\text{By commutativity of $\land$} \\
& &\square
\end{align}
$$
I've assumed throughout $\land$ to have higher precedence than $\lor$.


distinction between $\textbf{P}^{\# \textbf{P}}$ and $\# \textbf{P}$-Complete We know that $\# \textbf{P}$ is closed under polynomial sums, i.e., sum of polynomially many $\# \textbf{P}$ functions is still in $\# \textbf{P}$.

Functions in $\textbf{P}^{\# \textbf{P}}$ are those which make polynomially many (non-parallel) queries to an oracle for a $\# \textbf{P}$-Complete problem. So, the computational complexity of such problems must be a sum of polynomially many $\# \textbf{P}$ functions. Due to the closure property, this sum will be in $\# \textbf{P}$.

If the above is right, then:
What is the difference between the classes $\# \textbf{P}$-Complete and $P^{\# \textbf{P}}$ ?

Thanks.

First they are different kind of problems. One is a class of decision problems, the other one is a class of function problems. So lets interpret the question as $\mathsf{FP^{\#P}}$ vs. $\mathsf{\#P\text{-}complete}$.

Second, the kind of reductions used for completeness are not simple polynomial time Turing reductions, see the definition of #P-complete.

A polynomial time TM with access to a $\mathsf{\#P}$ problem might be able to do things that a $\mathsf{\#P}$ machine cannot do. For example, it can check if a $\Sigma^p_2$ formula is satisfiable and output $1$ if it is and $0$ if it is not.


FInding the combination with the least number of elements from and array of integers, given an integer sum I'm doing and assignment where the problem is to find the combination with the least number of elements form an array of integers, given an integer sum. I have solved this using a gready algorithm which doesn't find the optimal solution, however I'm having problems finding the optimal solution using dynamic programming.

The gready algorithm I've written is:

Function min_comb(array, value)
    min = 0
    for i in 1:length(array)
        if array[i] <= value
            min += floor(value / array[i])
            value = value % array[i]
        end
    end
    return min
end

which works fine for Example 1 below, but of course not for Example 2.

Example 1: If given an array $A=[1000,500,100,20,5,1]$ and a sum $S=1226$, the least number of combinations would be $N=6$ ($1000+100+100+20+5+1$).

Example 2: If given an array $A=[4,3,1]$ and a sum $S=6$, the least number of combinations would be $N=2$ ($3+3$).

How should I go about solving this problem?

Let $f(s, i)$ be the minimum number of elements (only the first $i$ elements of the array are considered) required to sum up to $s$, then we have
$$f(s,i)=\min_{0\le j\le s/A[i]}\left\{j+f(s-jA[i], i-1)\right\}.$$

You can use this formula to compute $f(s,i)$ for all $s$ and $i$. With knowing $f$, you can figure out the optimal combination. This is left as an exercise for you.


Filling a 3x3 board with connected tiles long story short: I want to list all possible combinations of n tiles on a 3x3 board with the restriction that at least 6 tiles are part of a connected chain. Tiles are connected if the pattern continues from one to the other and a tile can be repeated any number of times (see image below for clarification, I would like to increase the number of available tiles at one point).

You can see some of my thoughts below, I would like to know if there's a more elegant solution to this problem or (if I'm on the right track) some ideas on optimizations and data structures that I would need to actually implement this.

It seems to me there are three separate problems:

I need to map out all connected graphs with 6 vertices
Try all the combinations of tiles that fit on those vertices
List item

Since I actually need to print all the solutions I was thinking that there's no way of avoiding backtracking, so all my ideas so far are basically optimizations of the process. The biggest time save so far is the fact that once you have a valid configuration you can also print out its rotations (see picture below), thus cutting the search time to a quarter, but the catch is i don't know how to deal with duplicate solutions :/

There's also the observation that since I need to have a minimum of six connected tiles, one of them will surely be in a corner (upper left corners seems like the logical place to start) so all the connected graphs would have to start out in that corner.

That's about everything I have right now, thank you for reading and any help is highly appreciated.

There are only $9^9$ possible ways to fill each cell with one of the 9 tiles.  That's a bit under 400 million possibilities.  So, I suggest a simple approach: enumerate all of them, and for each, check whether or not it meets your conditions.  That should run pretty fast: you should be able to very quickly test a candidate configuration to see if it satisfies your requirements, and then a computer should be able to do that 400 million times pretty rapidly.  Repeatedly doing some tedious task is what computers are really good at.

You could also use backtracking or other more sophisticated methods to reduce the number of configurations you need to examine, but it might not be worthwhile to implement.  You might spend 10 hours programming to save 1 hour of CPU time -- might not be worth it.  I suggest you try the simple, dumb, brute-force search first, before thinking too hard about more sophisticated algorithms.


How to formulate constraints in zero-one linear programming There is a factory which produces 5 types of ice cream. If the $i_{th}$ ice cream is produced then $b_i=1$ otherwise $b_i=0$

How can I express the following constraints:

The simultaneous production of all 5 types ice cream is not possible
The type 1 and type 2 must be either both produced or none be produced ($b1 \oplus b2$)
If type 4 is produced, type 5 must be produced too, but if type 4 isn't produced, type 5 can be produced or not.
If type 4 isn't produced, type 5 must not be produced, otherwise, if type 4 is produced, type 5 can be produced or not


Is possible to prove undecidability of the halting problem in Coq? I was watching the "Five Stages of Accepting Constructive Mathematics" by Andrej Bauer and he says that there is two kinds of proof by contradiction (or two things that mathematicians call proof by contradiction):

Assume $P$ is false... blah blah blah, contradiction. Therefore $P$ is
true.
Assume $P$ is true... blah blah blah, contradiction. Therefore
    $P$ is false.

The first one is equivalent to the Law of Excluded Middle (LEM) and the second one is to how prove negation.

The proof of the undecidability of the Halting Problem (HP) is a proof by contradiction: assume there is a machine $D$ that can decide the HP... blah blah blah, contradiction. Therefore $D$ does not exist.

So, let $P$ be "$D$ exists and can decide the HP".
Assume $P$ is true... blah blah blah, contradiction. Therefore $P$ is false.

This looks like the second kind of proof by contradiction, so is possible to prove the undecidability of the halting-problem in Coq (without assuming LEM)?

EDIT: I would to see some points about proving this using contradiction. I know that this can also be proved using diagonalization.

You're exactly right that the halting problem is an example of the second kind of "proof by contradiction" - it's really just a negative statement.

Suppose decides_halt(M) is a predicate that says that machine M decides if its input is a machine that halts (that is, M is a program that for some machine m and input i, decides if m halts on input i).

Forgetting for a moment about how to prove it, the halting problem is the statement that there is no machine that decides the halting problem. We might state this in Coq as (exists M, decides_halt M) -> False, or maybe we prefer to say any given machine doesn't solve the halting problem forall M, decides_halt M -> False. It turns out that without any axioms these two formalizations are equivalent in Coq. (I've spelled out the proof so you can see how it works, but firstorder will do the entire thing!)

Parameter machine:Type.
Parameter decides_halt : machine -> Prop.

(* Here are two ways to phrase the halting problem: *)

Definition halting_problem : Prop :=
  (exists M, decides_halt M) -> False.

Definition halting_problem' : Prop :=
  forall M, decides_halt M -> False.

Theorem statements_equivalent :
  halting_problem <-> halting_problem'.
Proof.
  unfold halting_problem, halting_problem'; split; intros.
  - exact (H (ex_intro decides_halt M H0)).
  - destruct H0.
    exact (H x H0).
Qed.

I think either statement isn't too difficult to prove as a diagonalization argument, though formalizing machines, computability, and halting is probably reasonably challenging. For a simpler example, it's not too hard to prove Cantor's diagonalization theorem (see https://github.com/bmsherman/finite/blob/master/Iso.v#L277-L291 for a proof that nat -> nat and nat are not isomorphic).

The diagonalization above gives an example of how you might go about deriving a contradiction from an isomorphism between nat -> nat and nat. Here's the essence of that proof inlined as a self-contained example:

Record bijection A B :=
  {  to   : A -> B
  ; from : B -> A
  ; to_from : forall b, to (from b) = b
  ; from_to : forall a, from (to a) = a
  }.

Theorem cantor :
  bijection nat (nat -> nat) ->
  False.
Proof.
  destruct 1 as [seq index ? ?].
  (* define a function which differs from the nth sequence at the nth index *)
  pose (f := fun n => S (seq n n)).
  (* prove f differs from every sequence *)
  assert (forall n, f <> seq n). {
    unfold not; intros.
    assert (f n = seq n n) by congruence.
    subst f; cbn in H0.
    eapply n_Sn; eauto.
  }
  rewrite <- (to_from0 f) in H.
  apply (H (index f)).
  reflexivity.
Qed.

Even without looking at the details, we can see from the statement that this proof takes the mere existence of a bijection and demonstrates it to be impossible. We first give the two sides of the bijection the names seq and index. The key is that the bijection's behavior at the special sequence f := fun n => S (seq n n) and its index index f is contradictory. The halting problem's proof would derive a contradiction in a similar way, instantiating its hypothesis about a machine that solves the halting problem with a carefully chosen machine (and in particular one that actually depends on the assumed machine).


Hash multiple integers directly using FNV-1a An alternative version of FNV-1a hash spread on the internet, which operates directly on integers instead of bytes. The offset basis and prime are the same used in the original version, which operates on bytes.

With this version, is the statistical quality of the produced hash similar to the original algorithm?

Alternative version operating on integers:

#include <cstdint>

#define OFFSET_BASIS 2166136261ul
#define FNV_PRIME 16777619ul

uint32_t hash(uint32_t i, uint32_t j, uint32_t k)
{
   return ((((((OFFSET_BASIS ^ i) * FNV_PRIME) ^ j) * FNV_PRIME) ^ k) * FNV_PRIME);
}

Original version operating on bytes:

#include <cstdint>

#define OFFSET_BASIS 2166136261ul
#define FNV_PRIME 16777619ul

uint32_t hash(char* data, size_t bytes)
{
   uint32_t h = OFFSET_BASIS;

   for (size_t i = 0; i < bytes; ++i)
   {
      h = (h ^ data[i]) * FNV_PRIME;
   }

   return h;
}

It's not equivalent, and I suspect there will be a loss of statistical randomization/mixing.

The core step that offers mixing of the bits is multiplication by FNV_PRIME modulo $2^{32}$.  The original version (operating on bytes) does this once for each byte of the input.  The alternative version (operating on integers) does this once for each integer, i.e., once for each four bytes.  Thus, the alternative version does only one-fourth as many of these mixing operations.

For these reasons, I anticipate that the alternative version will provide poorer mixing of the bits and might offer poorer statistical properties or weaker collision resistance.

For instance, here is one weakness of the alternative version that isn't present in the original version.  Suppose you simultaneously flip the high bit of i and j.  Then it turns out that the output (the hash value) will remain unchanged, with the alternative version.  This is a weakness in a hash function.  The original version doesn't have this weakness: there's no simple set of bit flips you can do to the input that will have a similar effect.  This is a result of the fact that the alternative version only does the multiplication-based mixing one-fourth as much as the original version.

Now, don't take this the wrong way.  This doesn't necessarily mean that the alternative version is flawed or useless.  The alternative version might still be good enough for applications; that will depend on the distribution of integers that you hash and the needs of the particular application.  But you can't make an equivalence argument that it's "just as good" as the original version.


What is known about this TSP variant? This question was cross-posted to cstheory.SE here.

Imagine you're a very successful travelling salesman with clients all over the country. To speed up shipping, you've developed a fleet of disposable delivery drones, each with an effective range of 50 kilometers. With this innovation, instead of travelling to each city to deliver your goods, you only need to fly your helicopter within 50km and let the drones finish the job.

Problem: How should your fly your helicopter to minimize travel distance?

More precisely, given a real number $R>0$ and $N$ distinct points $\{p_1, p_2, \ldots, p_N\}$ in the Euclidean plane, which path intersecting a closed disk of radius $R$ about each point minimizes total arc length? The path need not be closed and may intersect the disks in any order.

Clearly this problem reduces to TSP as $R \to 0$, so I don't expect to find an efficient exact algorithm. I would be satisfied to know what this problem is called in the literature and if efficient approximation algorithms are known.

Huck Bennett has answered this question on cstheory.SE here.

  This is a special case of the Travelling Salesman with Neighborhoods
  (TSPN) problem. In the general version, the neighborhoods need not all
  be the same.

  A paper by Dumitrescu and Mitchell, Approximation algorithms for TSP
  with neighborhoods in the plane, addresses your question. They
  give a constant factor approximation algorithm for a slightly more
  general problem (case 1), and a PTAS when the neighborhoods are
  disjoint balls of the same size (case 2).

  As a side comment, I think Mitchell has done a lot of work on
  geometric TSP variants, so you might want to look at his other papers.


How to compare two approximation algorithms We say that "An algorithm is a $\beta$-approximation to problem $X$, if for any instance of problem $X$, the solution returned by this algorithm is within a factor $\beta$ of the optimal solution".

Now assume that we have a $\log(N)$-approximation algorithm (called it Alg 1) for problem $X$ where $N$ is the size of problem $X$. Further assume there is one other algorithm (called it Alg 2) for problem $X$, but for that algorithm we could find an instance of problem $X$ with size $N$ such that the solution returned by Alg 2 is $N/2$ times of the optimal solution.

What is a correct way of saying this statement that clearly shows that Alg 1 is much more better than Alg 2? I was thinking about the following one:

"Alg 2 provides a $\beta$-approximation to problem $X$ where $\beta \geq N/2$."

Is this correct? Any better suggestion?

I would write something like this: whereas Alg 1 is a $\log(N)$-approximation algorithms, there are instances on which the approximation ratio of Alg 2 is only $N/2$. So Alg 1 is much better (in the worst case) than Alg 2.


Is Everything a Hardware Interrupt? Just need a little help understanding hardware interrupts.

As I understand (feel free to correct) a hardware interrupts occurs when hardware wants attention of the computer. In basic terms the hardware sends a message down the interrupt line which is then controlled by the PIC. The CPU receives the interrupt and carries out the instruction once it has completed the current one it is on.

Every time I've seen examples of interrupts they have been 'printer running out of paper', 'network adapter receiving data packet' etc. My question is, how is the process of the hardware interrupt any different from pressing a key on a keyboard or moving a mouse? Each of these actions requires attention from the CPU but as I understand they are never used as examples of interrupts. Are they interrupts? Does everything I do with an input device cause an interrupt?

Any clarification would be much appreciated.

In general, no, on modern platforms, not everything is a hardware interrupt -- though you could imagine a platform where it is.

On some platforms, hardware interrupts are used for all input events (including, yes, pressing a key on a keyboard or moving a mouse).

However, interrupts come with some performance implications.  Therefore, in modern platforms, we often use a combination of interrupts and other I/O mechanisms.  We might use interrupts for some input devices, but other input devices might use memory-mapped I/O.  For instance, your Ethernet card might use memory-mapped I/O, to write incoming packets into a region of memory dedicated for this use.  Memory-mapped I/O can be combined with interrupts or with polling.

You can find more on interrupts, polling, memory-mapped I/O, DMA, and related topics in a good operating systems textbook.


Two-Sum - Range Allowance Algorithm Design What is the best way to find if there are two individual capacities that sum to a total capacity within a range of plus and minus the total capacity?

Optimize for runtime over memory complexity.

The same item cannot be selected twice.

Inputs

An Int representing the total capacity
An Int representing the range above and below the total capacity sums are allowed to be within.
An Array of Int's representing items' individual capacities.

Output: A Boolean representing whether it is possible for two of the items to equal the total capacity plus and minus the given range.
Samples
1.

Input: [4, 5, 2, 6]
Total capacity: 10
Range Allowance: 0
Expect: true because 4 + 6 equal 10.

2.

Input: [4, 5, 2, 5]
Total capacity: 12
Range Allowance: 2
Expect: true even though there are no two numbers that equal 12 directly, there are two numbers that sum to 10 which is within the range allowance provided.

3.

Input: [4, 5, 2, 7]
Total capacity: 14
Range Allowance: 1
Expect: false

Create a Set searchSet to store the item's that have already been examined.

Iterate through the input Array of item capacities.
2a. Find the targetCapacity for the current item: totalCapacity - itemCapacity.
2b. Generate a targetCapacitiesArray plus and minus the totalCapacity and the range allowance provided.
2c. For each capacity in targetCapacitiesArray, see if each number is contained in the searchSet, and return true if found.
2d. Else, add the itemCapacity to the searchSet.

Return false if the entire input is iterated through without finding a match.


Why does the total credit associated with a data structure must be nonnegative at all times for the accounting method? I was reading CLRS and it said in the chapter for the accounting method (for amortized analysis):

  the total credit associated with the data the structure must
  be nonnegative at all times.

where total credit is defined as:

  The total credit stored in the data structure is the difference between the total amortized cost and the total cost.

It also mentions the following:

  If we denote the actual cost of the ith operation by $c_i$ and the amortized cost of the ith operation by $\hat{c}_i$, we require:

  $$ \sum^n_{i=1} \hat{c}_i \geq \sum^n_{i=1} c_i$$

  for all sequences of n operations.

CLRS does provide an explanation of why it requires it but I am not sure I understand it. I will paste its explanation and explain my confusion:

  If we ever were to allow the total credit to become negative (the result of undercharging early operations with the promise of repaying the account later on), then the total amortized costs incurred at that time would be below the total actual costs incurred; for the sequence of operations up to that time, the total amortized cost would not be an upper bound on the total actual cost. Thus, we must take care that the total credit in the data structure never becomes negative.

So this is what I am confused about. When it says it requires $ \sum^n_{i=1} \hat{c}_i \geq \sum^n_{i=1} c_i$ to hold for all operations, does it implicitly also mean that it requires it for all $n \in \mathbb{N}$? i.e. its for all sequences of $n$ operations for all $n$?

What would be the deal if it didn't hold for all $n$? I tried reasoning this and I think it means that there exists some sequence that overall, is undercharged if we were to stop doing stuff at the end of that sequence. Thus, we wouldn't actually have a valid run-time analysis for this specific sequence of $n$ operations. Right?

I do think that it does mean for all natural numbers $n$ too. The reason I think this is because the way I think of the accounting method is that we have credit for later operations. If it was ever negative it means that some operation on the data structure at some point doesn't have actual enough "prepaid work" for some operation. Is this right or am I missing something?

Is the goal just that at all times for any sequence of any time that we always have an upper bound on the cost of $n$ operations? Regardless weather its charging, accounting, potential method etc, the goal is that always we have an upper bound on the cost of a sequence of $n$ operations?

So in this line of thought, if we do the potential method with:

$$ \hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1})$$

then because of the telescoping property, do we require for all sequences of operations that:

$$ \Phi(I_n) - \Phi(I_0) \geq 0$$

Since:

$$ \sum^n_{i=1} \hat{c}_i =  \sum^n_{i=1} ( c_i + \Phi(D_i) + \Phi(D_{i-1}) ) =  \sum^n_{i=1} c_i +  \Phi(D_n) - \Phi(D_{0})$$

since we need: $ \Phi(I_n) - \Phi(I_0) \geq 0$

The amortized analysis calculates complexity for a sequence of $ n \in \mathbb{N} $ operations, no matter how large $ n $ is and what is the structure of sequence (i.e. which operations are within the sequence). If you would allow $ \sum_{i = 1}^{n}{\hat{c_i}} < \sum_{i = 1}^{n}{c_i} $ for some $ n $ and some sequence of operations, then the same inequality would hold for any multiplication of $ n $. Thus you would not have an upper bound, so no analysis would be possible. This reasoning is for both accounting and potential method.


Find longest path between two disjoint sub-sets of vertices $V_1, V_2 \subset V$ of a Graph I have a homework question which I would appreciate some help with:

Let there be a DAG $G=(V,E)$ with positive weights. For every two different vertices $v_1, v_2$ we will define $D(v_1, v_2)$ to be the maximum length between $v_1$ and $v_2$ in the graph.
For every two disjoint sub-sets of vertices $V_1, V_2 \subset V$ we will define "The detour length" between them to be: $w(V_1, V_2) = max\{D(v_1, v_2) \mid v_1\in V_1, v_2 \in V_2\}$
Describe an algorithm which runs at $O(|V|\cdot |E|)$ complexity, that receives as an input $V_1, V_2 \subset V$ and calculates $w(V_1, V_2)$
(Hint: You can add vertices and edges to the graph)

OK so I realize that this is a problem which is connected to finding the longest path in a DAG. I know that I can negate all the weights inside $G$ and run Bellman-Ford to find the longest path, (It will work without issues because this is a DAG). Because Bellman-Ford runs in the wanted complexity, I think this can be solved by doing some modification to B-F, but I can't seem to figure out what I can do to solve it.
Every solution I come up with will run in a higher complexity than needed - I thought about running B-F on every vertex on $V_1$ and then calculating the max, but this isn't efficient, and also doesn't really use the hint. I also though about creating a second graph by connecting the two sub-sets but that also will run at a higher complexity because I need to run over every vertex.
Any help is appreciated, Thx!

Hopefully not giving too much away: You need to add only two nodes.


Using Taylor series in 1D Grayscale Image Could someone point me in the direction of how to solve this?

I = [I1, . . . , In] is a 1D grayscale image and D = [D1, . . . , Dn] represents the second derivative of I. I am given the four pixel intensities I1, I2, In−1, In] and the second derivative values D3, . . . , Dn−2. How would I compute the rest of I’s intensities?

What I have tried so far:
Each Ix intensity can be approximated via Taylor series: Ix = I(0) + x(dI(o)/dx) + (1/2)x^2(d^2I(x)/dx^2).

I am sure the trick is in using the sliding window algorithm for fitting a 2nd degree polynomial, and that a matrix is involved in solving.
However, I am unsure how big the sliding window should be (3, 5 pixels?), etc.

I am sure these are finite differences, so the first "derivatives" are just

$B_i := I_{i+1} - I_i$

and the second "derivatives" are the differences of those:

$D_i := B_{i+1} - B_i$

Write it out and solve for $I_i$.


Algorithms to prioritize equipment renewals I am looking for algorithms to prioritize equipment renewals.

Input: (years since last renewal, cost of renewal, importance of renewal).

Output: An ordering of the equipment according to which it will be renewed.

I do not know if there are any algorithms for this particular problem. If you have any idea how to fit this problem into a more general context, that would be useful too.

A way to rephrase the problem:

You have $n$ pieces of equipment $E_1,\ldots,E_n$. For each piece $E_i$ you have a triple $(\text{age}_i,\text{cost}_i,\text{importance}_i)$. At the beginning of the year you have $X$ amount of money. You want to spend these money in order to minimize the function $\sum_i \text{age}_i\cdot \text{importance}_i$ at the end of the year. So, during the year you have to select a subset $S$ of $\{1,\ldots,n\}$ such that:
$$\sum_{i\in S} \text{cost}_i\le X \text{ (cost constraint)}$$ and the sum $$\sum_{i\in S} \text{age}_i\cdot \text{importance}_i$$ is maximal among all subsets of $\{1,\ldots,n\}$ that satisfy the cost constraint.

Any help?

Given the clarification to the question, it is a 0-1 knapsack problem (your knapsack is the money available, the value is the objective function), and look for ways to solve that one, for example following the Wikipedia lead.

Edit: A simple approximate algorithm would be just sort equipment on increasing cost per unit (age * importance), and in that order include each if it fits (doesn't run over maximal cost). In the case of continuous knapsack (i.e., can include a fraction of a item) that strategy is optimal. Should work fine if there are many items, and the data isn't too spread out.


Relation between size of hashtable and number of values to keep expected number of collisions below/equal to 1 This is an exam question from my algorithms and data structures course.

You imagine an hash function with h: U->{0,..m} (this is from the original question, but i think m-1 would be correct) and n values to hash.
You want to keep the expected number of collisions below or equal to 1.
How do you determine m in dependence to n.

My initial idea was following formula to determine the number of collisions:
$n- E(\text{occupied locations}) = n-m+E(\text{empty locations}) \\$
$= n-m+m(1-\frac{1}{m})^n$

For our question this would give: $ 1 \geq n-m+m(1-\frac{1}{m})^n$

I know that following solution would have been correct (and i know why now):

$E[x]=\frac{n(n-1)}{2} \cdot \frac{1}{m} = m \geq \frac{n(n-1)}{2}$

Well i know i did not solve the first Equation for m (i do not know how), but my question is if both solutions would be correct and if not why?

I got the first Equation from Darthmouth ([Link]:https://math.dartmouth.edu/archive/m19w03/public_html/Section6-5.pdf)

No, your solution is wrong.  The expected number of collisions is not $n- E(\text{occupied locations})$, so you went wrong in the first step of your approach.  Try working through a small example or two and hopefully you will see why.

It's possible that your confusion has to do with how we count the number of collisions.  If items A,B,C all go into the same hash bucket, we consider that as 3 collisions: A,B are a collision, B,C are a collision, and A,C are a collision.


Using Rice's theorem to prove undecidability of $E_{TM}$ I saw this proof and I wondered if I could prove $E_{TM}$ with Rice's theorem similar to the one described in the answer. Can you do the same thing by letting $M$ to only accept empty strings? (the $M$ that is described in the answer of the proof)
So

If $x$ is empty, accept

If $x$ is any non-empty string, reject.

You have to be careful when you talk about accepting empty strings. Using the language from the linked question, what you are suggesting would yield $L(M_x)$ = $\{\epsilon\}$ instead of $L(M_x)$ = $\emptyset$.
You can use the same construction for machine $M_x$, but just change the the non-trivial property to "whether this machine accepts on no inputs". It's clearly a non-trivial property since it's not empty (there are machines with empty language), and it's not the set of all Turing Machines (since not all Turing Machines have empty language).


Primitive Recursive Function for Division and Hailstone function Are division and Hailstone primitive recursion function?

$$\text{Div}(x,y) = \begin{cases}
x/y,  & \text{if $y$ divides $x$ } \\
0, & \text{otherwise}
\end{cases}$$

$$\text{Hailstone}(n) =\begin{cases}
3n + 1,  & \text{if $n$ is odd } \\
n/2, & \text{if $n$ is even}
\end{cases}$$

I tried to solve division in this way
$$\text{Div}(0,y) = 0 $$
$$\text{Div}(x+y,y) = \text{Div}(x,y) + 1$$

I do not know how to proceed from here. Can anyone help me?

For your division example, what would the case be if y was equal to zero?

The function is undefined if y = 0.  Thus, it is not a total function.  Thus, division is not primitively recursive, as all primitively recursive functions are total functions.


Solve Max 3 color problem using 3 color decision problem I've been stumped on this question for a while and can't find a solution. How can I find the max 3 colorability of a graph(optimization problem) with 3 colorability (decision problem) without brute force searching every combinations of edges?

The problem "Can a given graph $G$ be 3-colored so that at least $m$ edges are bichromatic?" is in NP, and therefore can be reduced to 3-colorability (since 3-colorability is NP-hard). Using this, you can solve maximum 3 colorability, employing a simple binary search that invokes a 3-colorability oracle $O(\log n)$ times.

There might be a more direct reduction (which might have been the point of the question), but there is no real problem with this answer as well.


Quick sort analysis confusion Is randomized quick sort runtime is independent of the sequence of input? but depends on the numbers in the input?

Let say A1 = [1,2,3,4,5] , A2 = [5,2,3,4,1] A3 = [5,4,3,2,1] , Will the randomized Quick sort will have same runtime in terms of big O for A1, A2, A2

but for B1 = [1,2,3,4,5] B2 = [11,12,13,14,15] will have different runtime i.e. depends on the digits in the input?

Will the randomized Quick sort will have same runtime in terms of big O for A1, A2, A2

Statements like this do not make any sense. For any given input, any algorithm has running time O(1).

Note that Landau notation (here) inherently contains a "for size to infinity" clause. Therefore, it makes only sense for infinite input sets.

Then, yes, the result depends a lot on the input sequences you consider. If you average over all inputs, you get $\Theta(n \log n)$. If you average over all worst-case inputs, you get $\Theta(n^2)$.


How can I fit a sine function to a SVR? I have a time series which represent the sine curve. Now I want a regressor to learn this curve, and being able to predict for future values.

PS:
Sine curve is only for testing purposes. What I want is to learn that function and its parameters as well which need not be sine.

Use nonlinear regression: https://en.wikipedia.org/wiki/Nonlinear_regression.  Write down a model, e.g., $f(x) = \sin(\alpha x + \beta)$, and then try to find parameters $\alpha,\beta$ that minimize the regression error (the sum of the squared error at each point; i.e., square of difference between model's prediction and observed value).  You can use gradient descent or other forms of mathematical optimization for that.  If a sin function isn't the right model, you can write down some other model (with some parameters) and use optimization to find the best values for the parameters.


What do we benefit from using ternary search trees rather than binary search trees? Ternary search trees are very common in the text editing area. They could be used to implement Auto complete feature, spell checking, Partial-Match searching, Near-Neighbor Searching & many many other options.
The reason behind them being famous is their space efficiency compared to tries (Although tries are faster) & their flexibility (Compared to Hashtables).
Ternary search trees have three pointers in their data node : lokid the left kid, hikid the right kid & midkid the middle kid.
The thing that I'm missing is why do we need the middle kid ? What is the particularity of this pointer ? In which things it would be better to have that pointer rather than not having it at all ?
I was drawing some trees & i think we can realize the same thing using only 2 pointers (A binary search tree) with insertions going to the left kid if current character in the string to insert is equal or less than the character on the current node and insertions going to the right the other way around.

The following picture shows a binary tree generated from inserting words: KARIM, KARAS, SARAS.

The insertion algorithm of the above tree could be something similar to the following pseudo code :

insert(root, word){

    if(!root) {
        root = new node()
        root->char = *(word++)
    }

    if(*word > root->char)
        insert(root->right, word)

    else {
        if(*word == root->char)
            insert(root->left, word++)
        else
            insert(root->left, word)

    }
}

What could possibly be wrong with the above conception ? Am i missing something about the ternary trees which makes them superior to binary trees ?

I'd challenge you to write the code which queries your data structure. For example, how could you determine that "SARAS" is in your tree, but "KSARAS" is not?

The problem with your data structure is that we cannot tell the difference between searching and selecting a letter. This is what the middle child of the ternary tree is used for: when you've found the letter you're looking for, you step to its middle child.

Here's what a ternary tree for your set of words might look like. I've marked word ends with *.

    K
    | \
    A  S
    |  |
    R  A
    |  |
    I  R
  / |  |
 A  M* A
 |     |
 S*    S*

Querying for "SARAS", for example, would look like this:

[Looking for "SARAS", at node K] S > K, so go right.
[Looking for "SARAS", at node S] S = S, so go down and advance to next character.
[Looking for "ARAS", at node A] A = A, so go down and advance to next character.
etc... (eventually returns true)

Querying for "KSARAS", however, would look like this:

[Looking for "KSARAS", at node K] K = K, so go down and advance to next character.
[Looking for "SARAS", at node A] S > A, so go right.
[Looking for "SARAS", fell off tree] return false.


Could someone check my recursive program correctness proof that returns $F(x, y) \rightarrow x + y$? For $k \in \mathbb N$, we define $Q(k)$ as follows:

$Q(k): $ let $x, y \in \mathbb N$ and $x$ is a multiple of $3$ and $k = x + y$, then $FUN(x, y)$ terminates and returns $x + y$

I will prove $Q(k)$ using induction

Base Case: let $k = 0 \to iff (x = 0, y = 0)$

By line 1, 2, 5, $FUN(x, y)$ terminates and returns $0 + 0 = x + y$ as wanted

Inductive step: Let $k > 0$. Suppose $Q(j)$ holds whenever $0 \leq j < k$ [I.H]

What to prove: $Q(k)$ holds

Since $k > 0$, it follows that line 3-7 could run since line 1 is not satisfied.

Therefore two cases: $y > 0$ and $y \leq 0$

Case 1: If $y > 0$, then line 3, 4, and 7 will run.

Since $0 \leq k - 1 < k$, this mean IH will apply to $FUN(x+3, y - 1)$

By IH, $FUN(x+3, y - 1)$ terminates and returns $x + 3 + y - 1$

By line 3, 4 and 7. $FUN(x, y)$ terminates and returns $x + 3 + y - 1 - 2 = x + y$ by algebra, and as wanted

Case 2: If $y \leq 0$, then line 5, 6, and 7 will run since line 1, 3 are not satisfied

Since $0 \leq k - 1 < k$, this mean IH will apply to $FUN(x - 3, y )$

By IH, $FUN(x - 3, y )$ terminates and returns $x - 3 + y$

By line 5, 6 and 7. $FUN(x, y)$ terminates and returns $x - 3 + y + 3 = x + y$ by algebra, and as wanted

Therefore $Q(k)$ holds as wanted

This is my attempt above, not sure if I'm correct. I'm pretty confused on how to use IH in this or if my input size is even good. Is it correct?

As mentioned by Apass.Jack, you cannot apply IH to the $y>0$ case, since $ (x+3)+(y-1)=x+y+2>k$. I think you will want to do induction on $k=\min(x,\,y)$. Then you have no problem applying IH, since either $x$ or $y$ will always be smaller in the recursive call. The only difficulty here is that in your base case, you now need to cover when one of $x$ or $y$ is zero and the other is arbitrary. I will omit the case when both are zero, for brevity.

In the case that $y$ is zero, then the result will be $\text{FUN}(x-3,\,0)+3$. If $x$ is a multiple of 3 and positive, then this will eventually give $\text{FUN}(0,\,0)$ and then 3s will be added until you get $x$ again. This is what you wanted, since $x+y=x+0=x$. Note that the recursive calls retain the conditions that $x\geq0$ and a multiple of 3.

In the case that $x$ is zero, then the result will be $\text{FUN}(3,\,y-1)-2$, assuming your algorithm terminates, since if the algorithm took the $\text{FUN}(-3,\,y)+3$ branch, then there would be an infinite recursion. This implies that $y>0$ initially. Then this branch will continue to be taken until $y=0$, in which case we will return $\text{FUN}(3y-3,\,0)+3$. This is the case when $x>0$ and $y=0$, covered above. Then we get $3y-3+3-2y=y=0+y=x+y$. The $-2y$ comes from subtracting 2 recursively $y$ times.


Graph coloring with fixed-size color classes I'm interested in coloring a graph, but with slightly different objectives than the standard problem. It seems like the focus of most graph-coloring algorithms (DSATUR etc) is to minimize the number of color classes used.
My goal, in contrast, is to maximize the number of color classes of fixed size N.
As a concrete example, say I have a graph with 100 nodes, and I'd like to color the graph with color classes of size N = 30. With an optimal algorithm and the right graph, I could find 3 such groups that color 90 total nodes, with 10 nodes left over. A lesser algorithm might only produce 2 such groups, with 40 nodes left over that cannot be colored with a size-30 color class.
I figure I can solve this problem with a Greedy Algorithm, but it won't be optimal. Or I could model this in a constraint solver, but it might not employ some clever graph-specific tricks that could come in handy.
Does this specific problem have a name? Or an established algorithm to solve it? Thank you!
EDIT:
It was rightfully pointed out that my question is ambiguous! I can explain much more thoroughly, my apologies for the confusion.
First, let me define the size of a color class. I've seen this terminology elsewhere but might be using it incorrectly. The size of a color class is the number of nodes assigned to that color. I will denote this: size(C_i) = <number of nodes colored C_i>.
Now, to define a fixed size color class. This is a color class with size N. To use the example above, I'm interested in colorings with colors such that size(C_i) = 30.
As far as the optimization objective: I want to color a graph to maximize the number of size-30 color classes. If you'll permit me some Python pseudocode:
n_size_30_colors = len([c for c in colors if size(c) == 30])
maximize(n_size_30_colors)

To complete the example, take these two possible colorings of a graph with 100 nodes. Each number represents the number of nodes colored by that color:
Coloring 1: {55, 25, 20} (n_size_30_colors = 0)
Coloring 2: {30, 30, 20, 20} (n_size_30_colors = 2)
Coloring 3: {30, 30, 30, 10} (n_size_30_colors = 3)

Even though Coloring 1 uses fewer colors, Coloring 3 is optimal because it returns the most size-30 color classes. The size-55 color class in Coloring 1 is "wasteful" in that those 25 extra nodes are not useful; an optimal solution for this problem would distribute those nodes to other color classes, hopefully yielding more size-30 colors.
I hope this clarifies things somewhat, and thanks again!

This problem is NP-hard: it is at least as hard as independent set.  In particular, if you want to know whether there exists an independent set of size $N$, ask for a coloring with as many colors of size $N$; if you find any coloring where a single color occurs $N$ times, you know there's an independent set of size $N$.  So, you should not expect any efficient algorithm for this problem that works on all problem instances.
One plausible approach is to use a ILP solver.  You can define zero-or-one variables $x_{v,c}$, where $x_{v,c}=1$ means that vertex $v$ is assigned color $c$.  Then it is easy to express the requirement that a color $c$ be assigned to exactly $N$ vertices: we require $\sum_{v \in V} x_{v,c} = N$.  The constraint that two adjacent vertices $v,w$ be assigned different colors can be expressed by $x_{v,c} + x_{w,c} \le 1$ for all $c$, and that each vertex $v$ receive a color by $\sum_c x_{v,c} = 1$.  Without loss of generality, to test whether it is possible to have $k$ colors be assigned to $N$ vertices, you can constrain the first $k$ colors to have $N$ vertices and put no constraints on the remaining colors.  Then, use binary search on $k$ to find the largest $k$ for which a solution exists.
Another plausible approach is to use a SAT solver.  You could define variables $x_{v,c}$, where if $x_{v,c}$ is true then vertex $v$ is assigned color $c$, and express your constraints in SAT.  You can require that color $c$ be assigned to exactly $N$ vertices, by requiring that $N$ out of the variables $x_{\cdot,c}$ are set to true (see Encoding 1-out-of-n constraint for SAT solvers and links for methods).  Otherwise, this is similar to using an ILP solver.
These might work if $N$ is small enough and the graph is small enough, but eventually will run into exponential behavior once the problem gets large enough.


Sum of Maximum of continuous blocks of length k Given a array of N elements and a number k, then find the sum of maximum of a all continuous blocks of length k?

Examples :

A = {2,5,2}, k = 2, Max for 1st block = 5, 2nd block = 5, So sum is 10.
A = {3,1,8}, k = 2, Max for 1st block = 3, 2nd block = 8, So sum is 11.
A = {2,5,2}, k = 1, Max for 1st block = 2, 2nd block = 5, third block = 2. So sum is 9.
A = {2,5,2}, k = 3, Max for only block = 5. So sum is 5.

For an appropriate data structure $D$, which maintains the last $k$ elements, it is natural to consider the following solution:

Initialize $D$ with $A_1,\ldots,A_k$, and initialize the sum $S$ with $\max D$.
For $i=k+1,\ldots,n$:

Remove $A_{i-k}$ from $D$.
Add $A_i$ to $D$.
Add $\max D$ to $S$.

Return $S$.

The data structure has to support three kinds of operations:

Adding an element.
Removing an element.
Calculating the maximum.

I'll let you figure out what data structure is most suitable, and what is the resulting complexity.


Why do mainstream speech models no longer require a personalized training step? Back in the Windows XP era, when setting up Windows OS-built-in speech/dictation, I had to speak out a bunch of programmed-in text samples to the speech-to-text engine to personalize my voice profile.

Today, with networked speech-to-text engines like Siri or Cortana, I can just start dictating.

The quality of the text-to-speech conversion seems equivalent, though my memory may be faulty on that aspect.

Have speech models advanced past the need for any personalization of the training data? Or, do they just do the personalization under the covers now, without an explicit training wizard? Or, do they not do training, even though it would still be beneficial (e.g. because it's inconvenient)?

Have speech models advanced past the need for any personalization of the training data?

There were two aspects which improved accuracy significantly:

Deep learning and neural networks greatly improved the accuracy.
Amount of training data that major companies use has grown over years by order of magnitude. Companies collected so much data that effect of adaptation decreased.

  Or, do they just do the personalization under the covers now, without an explicit training wizard?

There is a small adaptation usually going on, but it is very marginal in effect. It is basically matching your voice with some baseline voices and produces a vector of similarities and then this vector is used in realtime and adjust neural network input (so called i-vector adaptation). This kind of adaptation is pretty fast, you can adapt from 2-3 seconds of speech. For technical details you can read

https://www.microsoft.com/en-us/research/uploads/prod/2018/04/ICASSP2018_CortanaAdapt.pdf

  Or, do they not do training, even though it would still be beneficial (e.g. because it's inconvenient)?

There are some cases where adaptation would be beneficial but again there are multiple aspects here:

It works good without adaptation.
Neural network recognition does not fit well with adaptation actually. You need many many GPU nodes to train a big neural network, it is very hard to adjust it afterwards. You can adjust a small layer with adaptation data but effect is usually small just because neural network is pretty tightly tied thing and you can't simply modify a bit without retraining.
Like I said above the amount of training data is so huge that your custom data is probably already in the training set and adaptation will not help much
Adaptation can also harm. Imagine your speech had an unusual crack or beep from background or something like music and system adapted to it. Then it will actually decode your normal clean speech with less accuracy than unadapted system.
Adaptation is not very convenient for users. Why do you need to adapt when you can simply start using the system.

So the system design moved to the "it just works" and it is a good direction.