Optimization problem where penalty is sensitive to permutation Say, I have the situation where I am looking into all the possibilities to obtain a value of e.g. 20 (exactly) by taking all possible combinations of sums using values from 1 to 5. While doing this, I want to minimize my penalty P. There is no limit to the amount of values I use (I could do 4x5, 20x1 and any other possibility).

The penalty is not based on the amount of values I use, but instead on the intermediate values of the summation.

In this example, let's assume the penalties are as follows:

1 * k for 0 <= S < 2
2 * k for 2 <= S < 6
3 * k for 6 <= S < 11
4 * k for 11 <= S < 20

where k is the current value being added to my intermediate sum S.

So if I consider e.g. [1,2,3,4,5,5] (in that particular order), my total penalty would be P=1*1+1*2+2*3+3*4+3*5+4*5=56.

However, the penalty changes if I permute my array to e.g. [1,5,4,5,2,3] (P=53) or [2,4,5,1,3,5] (P=61).

In this simple example, we have 192 different sets of values that can together add up to 20. The number of possible permutations per set (taking into account non-unique values) varies between 1 (in case of 20x1, 10x2 etc) and 15840 (7x1, 3x2, 1x3, 1x4). The naive approach would be to just loop through all sets and their permutations, which is doable for the given example.

However, my actual problem has about 2000 possible sets of numbers and the number of permutations goes all the way up to ~1E+8. It is no longer fun to use a naive approach in this case.

I do know that I can greatly reduce my number of permutations, as the order of my values does not matter if I stay within the same range (when I'm at S=11, it no longer matters in what way I add the final 9).

My question is how I can properly implement this knowledge to improve my naive algorithm such that it disregards those permutations a priori (first generating all permutations and then removing is not really an option, as even 8-bit unsigned integers will generate 15 GB arrays for all permutations). Furthermore, I was wondering whether there are any additional improvements that could be made here.

I will outline two different solution methods.  Either one will work -- pick whichever one you find easiest to understand and implement.

Dynamic programming

This can be solved using dynamic programming.  We'll fill in a one-dimensional table, so that $T[s]$ stores the penalty of the best (lowest-penalty) way to obtain a sum of exactly $s$.  Once we've filled in all of the entries, $T[20]$ will tell you the lowest penalty achievable for any combination that sums to 20.

So how do we fill in the table entries?  We can fill them in recursively:

$$T[s] = \min(T[s-1]+p(s-1,1), T[s-2]+p(s-2,2), \dots, T[s-5]+p(s-5,5))$$

where $p(s,k)$ is the penalty for adding the number $k$ when the intermediate sum is $s$.  In the question, you tell us that $p(s,k) = k$ for $0 \le s < 2$, $p(s,k) = 2k$ for $2 \le s < 6$, etc.

Also, we have the base cases $T[0] = 0$.  As a convention, we'll agree that $T[-1]=T[-2]=T[-3]=T[-4]=\infty$.  Then you can fill in $T[1],T[2],\dots,T[20]$ in that order, using the recursive formula above.

This will give you the penalty of the best way to achieve the sum $20$.  If you also want to output the specific combination that achieves that penalty, you can keep track of that with a small modification.  Basically, each time you fill in a $T[i]$ entry with some penalty value, on the side keep track of the combination that led to that penalty value.

Graph search

Construct a weighted directed graph, with vertices 0, 1, 2, .., 20.  Each vertex corresponds to a possible intermediate sum.  From each vertex (intermediate sum) $s$, add five outgoing edges, corresponding to the five possibilities for the number you add.  The length of the edge from $s$ to $s+i$ (for $i=1,2,\dots,5$) is the penalty for adding $i$ to an intermediate sum $s$, according to the rules described in your question.

Now find the shortest path from vertex 0 to vertex 20 in this graph.  That path will correspond to a combination of values that sum to 20, and the total length of that path will correspond to the penalty of that path.  The shortest path will correspond to the combination with lowest penalty.  You can use any standard algorithm for computing shortest paths in a graph, such as Dijkstra's algorithm.


How does cpu fetch active program data (using virtual address) from storage when there is a page fault? I read that cpu generates virtual address and using the same mmu translates to physical address and then fetches the data from RAM. But when there is a page fault, the data is fetched from the HDD(or Secondary Storage) where the program resides. But how does the cpu knows exact location of the program on storage device. Does it maps the virtual address to the address of storage device? If yes, how does it do ?

The CPU knows nothing about swapping. This is performed by the operating system.

When a memory access takes place, the MMU consults page tables to find the physical address that is associated to a virtual address. Each page tables contains a number of descriptors that explain to the MMU what the physical address is. A page fault occurs when the descriptor contains an invalid value (i.e. one that does not denote a physical address).

When a page fault occurs, the CPU transfers control to a predefined piece of code in kernel mode and sets a register to the problematic address. The kernel code looks up the address in its own tables to figure out whether it is swapped out or invalid. On many architectures, there are many unused bits in an invalid descriptor, which allows the kernel to store its own data in the page tables. Based on these values, if the kernel determines that the page is swapped out, it will allocate a physical memory page, load the content from swap, modify the content of the faulting descriptor to point to this physical page, and transfer control back to the program so that it executes the memory dereference again. If the kernel determines that the page is invalid, it typically terminates the application, or transfers control to its fault handler.

The layout of descriptors and of any additional kernel data structure is highly dependent on the processor architecture and the kernel. Here's a fictional, simplified example of how it might look like (real machines and operating systems tend to be a lot more complex).

The machine is capable of addressing 4GB of virtual memory and 8TB of physical memory. Each page is 4kB. A page table consists of 1048576 descriptors, each of which occupies 4 bytes. (In the real world, MMUs use 2 or 3, sometimes 4 levels of descriptors, rather than a single gigantic table.)
In each descriptor, the lowest bit indicates whether the descriptor is valid. If the lowest bit is 0, the descriptor is valid, and the corresponding physical page is $2^11 \times d$ where $d$ is the descriptor value. If the lowest bit is 1, the descriptor is invalid, and the MMU ignores the other bits. (In the real world, there are more bits in descriptors for permissions, cache maintenance, etc.)
The operating system uses the 31 higher bits of invalid descriptors to locate a swapped-out page. The OS supports up to 8TB - 4kB of swap; the special value all-bits-one indicates an invalid page. Separate data structures map ranges of swap addresses to ranges of disk locations.


Master theorem: When a $f(n)$ is smaller or larger than $n^{\log_b a}$by less than a polynomial factor I was trying to solve the following question while reviewing master theorem.

Which of the following asymptotically grows faster.

(a) $ T(n) = 4T(n/2) + 10n $

(b) $ T(n) = 8T(n/3) + 24n^2 $

(c) $ T(n) = 16T(n/4) + 10n^2 $

(d) $ T(n) = 25T(n/5) + 20(n\log n)^{1.99} $

(e) They are all asymptotically the same

My calculation says, (a) is $\theta(n^2)$ (b) is $\theta(n^2)$ (c) is $\theta(n^2\log n)$. Now how can I evaluate (d)?

If $f(n)$ is smaller or larger than $n^{\log_b a}$by less than a polynomial factor, how can I solve $T(n)$?

$ T(n) = 25T(n/5) + 20(n\log n)^{1.99} $

Note that $(\log n)^m=O(n^\epsilon)$ for all $m,\epsilon\in \Bbb R^+$. In plain words, all polynomials of $\log n$ grows slower asymptotically than all polynomials of $n$. Here we abuse "polynomials" to include functions like $x\to x^k$ for all $k\in\Bbb R^+$ such as $x\to x^{0.618}$ or $x\to x^{2019.46}$. This abuse of the term "polynomial" is common when we are talking about the asymptotic behavior of functions.

In particular, $(\log n)^{1.99}=O(n^{0.005})$.

Since $(n\log n)^{1.99}=n^{1.99}(\log n)^{1.99}= O(n^{1.995})=O(n^{log_525-0.005})$, you can apply the case 1 of Master theorem. $T(n)=\Theta(n^2)$.

If $f(n)$ is indeed smaller or larger than $n^{\log_b a}$by less than a polynomial factor, then we are running into the cases strictly between case 1 and case 2 or between case 2 and case 3. The master theorem you were reviewing cannot be applied any more.

You may look into this answer that handles some of those situations.

Exercise. Show that $(\log n)^m=O(n^\epsilon)$ for all $m,\epsilon\in \Bbb R^+$. (For example, $(\log n)^{10000000}=O(n^{0.000001}).$)


ML Algorithms to discriminate "known" from "unknown" instances I'm classifying different electrical devices based on features extracted from their electricity consumption into a household-specific model built from around 10 devices. Now I want to detect whether a classified testing instance is coming from a device which has not been present in the training set, i.e. I want to discriminate known from unknown devices.

I'm working with Weka and use the Classifier.distributionForInstance() method to give me the (classifier-specific) probability distribution for those 10 possible classes for each instance.

Now, the problem is that some classifiers (SMO, NaiveBayes, J48 and other trees) most of the time classify a not known device with a high probability of almost 1 to a class, whereas RandomForest (preferably with high amount of trees) and IBk (kNN) perform rather well in giving back lower probabilities of classification/more uncertain results.

The questions I have:
Can you think of alternative approaches or any other algorithms/methods?
Why is it, that the first stated algorithms strongly decide for one class. I would have expected them to return unclearer results.

thx, regards

I would use a two-step pipeline where the first step discriminates between known and unknown and the second step performs the actual classification. This approach has a number of benefits.

Separating the two problems allows you to judge the accuracy of each step. You can assess the quality of your known/unknown discrimination independently of your actual classifier and vice versa. This will tell you where you need to focus your efforts.
You don't need to worry about your classifier being over confident for examples you aren't actually interested in since presumably you're taking care of this beforehand.
The known/unknown discrimination is just the problem of outlier detection. There are lots of ways to approach this and you may be able to find methods designed to work within your specific problem domain. I frequently hear 1-class SVMs (support vector machines) come up in this context, but have never worked with them personally.

If you think about the way decision trees work it is pretty easy to see why a single tree is going to be overconfident. There are lots of different ways to learn decision trees, but in general you can think about them as trying to make the leaves as pure as possible, i.e., we want the leaves to contain instances that all have the same class. Since an unknown example is just going to follow some path down the decision tree, it will end up in a leaf, which by construction, contains little class variability. From this observation it is easy to see why combining many different trees (like in Random Forests) is going to help avoid this problem.

As for why Naive Bayes is being overconfident, I would guess this is due to some combination of one of the class priors $P(y)$ being larger than the others, and/or having most features be unknown for your unknown example (so $P(x_i|y)$ is approximately the same for all $y$ and most $i$ if you're smoothing the estimates) and a couple show up in one class causing the $\prod_i P(x_i|y)$ term to blow up for one $y$ relative to the others. This is just a guess without the data.


Exercise on Divide&Conquer's technique I need help on this exercise:
You are given an array of n elements, and you notice that some of the elements are duplicates; that is, they appear more than once in the array. Show how to remove all duplicates from the array in time O(n log n).

I find a solution but in O(n^2)... How can I apply D&C?

Given an array of elements $a[i], 0\le i\le n-1$, we know we can sort it in time $O(n\log n)$. Then do the following to produce an array $b[\;]$:

declare b to be of size n
old = a[0]
b[0] = a[0]
j = 1
for i = 1, ... , n
   if a[i] =/= old    // found a new value
      old = a[i]      // save it
      b[j] = a[i]     // store it in b[j]
      j = j + 1       // and increment the b index

It's clear that, first, this can be done in one pass through the $a$ array, so this part will take time $O(n)$ (along with $O(n)$ time to allocate $b$), and, second, after this part the $b$ array will contain all of the values of the original array, with no duplicate values.

Note. This may or may not be what you want. Starting with an initial array $\langle\,7, 3, 7, 4, 1, 3, 1, 7\,\rangle$, this will result in a $b$ array $\langle\,1, 3, 4, 7\,\rangle$, which has all the values without duplicates, but the original place order of the elements isn't preserved. There are at least two possibilities for the result, depending on whether you want to eliminate all the duplicate values after the first occurrence, (giving you $\langle\,7, 3, 4, 1\,\rangle$) or if you want to eliminate all the duplicate values before the last occurrence, giving you $\langle\,4, 3, 1, 7\,\rangle$.

For the first option, a fairly simple modification is to do a preprocessing step on the $a$ array, changing it to an array of pairs, $(value, index)$, where $index$ is the position of the element with that value. In the example above, this will give you a new array
$$
\langle\,(7, 0), (3, 1), (7, 2), (4, 3), (1, 4), (3, 5), (1, 6), (7, 7)\,\rangle
$$
Now, as we did originally, sort this array by the first element of the pairs, giving
$$
\langle\,(1, 4), (1, 6), (3, 1), (3, 5), (4, 3), (7, 0), (7, 2), (7, 7)\,\rangle
$$
(here we need to use a stable sort, like mergesort, to maintain the original place order). Eliminating duplicates, as above, we will have
$$
\langle\,(1, 4), (3, 1), (4, 3), (7, 0)\,\rangle
$$
and if we sort the result by the second index, we'll have
$$
\langle\,(7, 0), (3, 1), (4, 3), (1, 4)\,\rangle
$$
and looking at the first element, we'll have $\langle\,7, 3, 4, 1\,\rangle$, which is what we wanted.

This algorithm will take $O(n)$ steps to preprocess the array, $O(n\log n)$ steps to sort the result, $O(n)$ steps to eliminate the duplicate values, and $O(n\log n)$ steps to do the final sort, giving us an algorithnm that runs in time $O(n+n\log n+n+n\log n)=O(n\log n)$.


Adding elements to a sorted array What would be the fastest way of doing this (from an algorithmic perspective, as well as a practical matter)?

I was thinking something along the following lines.

I could add to the end of an array and then use bubblesort as it has a best case (totally sorted array at start) that is close to this, and has linear running time (in the best case).

On the other hand, if I know that I start out with a sorted array, I can use a binary search to find out the insertion point for a given element.

My hunch is that the second way is nearly optimal, but curious to see what is out there.

How can this best be done?

We count the number of array element reads and writes. To do bubble sort, you need $1 + 4n$ accesses (the initial write to the end, then, in the worst case, two reads and two writes to do $n$ swaps). To do the binary search, we need $2\log n + 2n + 1$ ($2\log n$ for binary search, then, in the worst case, $2n$ to shift the array elements to the right, then 1 to write the array element to its proper position).

So both methods have the same complexity for array implementations, but the binary search method requires fewer array accesses in the long run... asymptotically, half as many. There are other factors at play, naturally.

Actually, you could use better implementations and only count actual array accesses (not accesses to the element to be inserted). You could do $2n + 1$ for bubble sort, and $\log n + 2n + 1$ for binary search... so if register/cache access is cheap and array access is expensive, searching from the end and shifting along the way (smarter bubble sort for insertion) could be better, though not asymptotically so.

A better solution might involve using a different data structure. Arrays give you O(1) accesses (random access), but insertions and deletions might cost. A hash table could have O(1) insertions & deletions, accesses would cost. Other options include BSTs and heaps, etc. It could be worth considering your application's usage needs for insertion, deletion and access, and choose a more specialized structure.

Note also that if you want to add $m$ elements to a sorted array of $n$ elements, a good idea might be to efficiently sort the $m$ items, then merge the two arrays; also, sorted arrays can be built efficiently using e.g. heaps (heap sort).


Given a row sum vector and a column sum vector, determine if they can form a boolean matrix For example, for a boolean matrix of size $3x4$, the column sum vector $C = (3, 3, 0, 0)$ and the row sum vector $R = (2, 2, 2)$ form a match because I can construct the boolean matrix:
$$
\begin{matrix}
&
\begin{bmatrix}
1 & 1 & 0 & 0\\
1 & 1 & 0 & 0\\
1 & 1 & 0 & 0
\end{bmatrix}
&
\begin{pmatrix}
2\\2\\2
\end{pmatrix} = R
\\
C = &\begin{pmatrix}
3 & 3 & 0 & 0
\end{pmatrix}
\end{matrix}
$$
However, the row sum vector $R' = (4, 1, 1)$ doesn't form a match with $C$.
So given two vectors whose values are sorted in a non-increasing order $C_w$ and $R_h$, and whose accumulated sum is the same, $T = \sum_jc_j = \sum_ir_i$, how can I polynomically check if $C$ and $R$ form a matching because I can form a matrix $M_{h,w}$ having $C$ and $R$ as colum and row sum vectors respectively?
More specifically, in case it can help to make the check algorithm faster, in my specific case, C and R has the following properties:

$h \leq w$
The number of positive values of $R$ and $C$ is $> w$. For example, $C$, in the example, has two positive values and $R$ has three positive values, and it happens that $2 + 3 > w = 4$.

This problem is known as discrete tomography, and in your case two-dimensional discrete tomography. A nice approachable introduction is written Arjen Pieter Stolk's thesis Discrete tomography for integer-valued functions in Chapter 1. It gives a simple greedy algorithm for solving this problem:

While the proof of theorem (1.1.13) is somewhat involved, the reconstruction algorithm that comes out of it is actually quite easy.  It proceeds  one  column  at  a  time,  starting  with  a  column  whose  sum  is  the highest and working in order down to the lowest column sum. In each column, we place the 1’s in those rows where with the largest number of 1-positions left, that is, such that the row sum minus the number of 1’s already filled in is the largest.


Spacial complexity of an $O(2^N)$ time-complexity algorithm For the following code sample:

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

I understand that the time complexity is $O(2^N)$. However, what I don't understand is how the space complexity is $O(N)$. The argument I have heard for this is that although we have $O(2^N)$ nodes in the tree total, only $O(N)$ exist at any given time. What does that mean, how is that so? If the recursive calls are going to be made until the base case is reached, then don't we have $O(2^N)$ calls to make instead of $O(N)$?

The number of calls is indeed $O(2^{n})$. However, the memory footprint will be $O(n)$.

I guess the point is to clarify how the memory stack works during a recursion.
Perhaps the easiest way is to draw a recursion tree to follow the recursive calls.
Lets see how the size of the stack changes during these calls through a very small example.

Lets say you want to compute $f(1)$. Your tree will have only three nodes: the root ($f(1)$), a left child ($f(0)$) and a right child ($f(0)$).

Initially the stack is empty. We invoke the function with argument $n=1$.
We store what we need in the stack (e.g., temporary variables of this call).
This takes constant space, and for convenience lets say that stack size is now equal to $1$.

Next, we invoke the left child $f(0)$.
The stack size becomes 2.
But $f(0)$ returns immediately.
So the stack size is back to 1.

Next, we invoke the right child $f(0)$.
The stack size is now 2.
$f(0)$ immediately returns 1.
So the stack size is now back to 1.

Back at the root node, $f(1)$ has computed both the left and right child
and returns its value.
The stack size is now 0.

This was a very small example, but you see the stack size was never $3$ (equal to the size of the recursion tree) because the memory stack grows and shrinks as you traverse the tree.
For a larger example, you will see that when you visit a node (i.e. at some point of the recursion), any memory you used for the left subtree has now been cleared.
You only need memory for the nodes between the root and the current node.
Hence, the maximum size is equal to the depth of the tree which is $O(n)$.


What is a problem, a task, and a solution? I am attending algorithms and data structures course in my University and my professor gave me an interesting question the other day. He told me to think about it.

What is a problem, a task, and a solution?

It seems to me like it's more of a philosophical question. All of those 3 things correlate to one another.

To me, it seems like if we have a problem, we then have a task to solve it, which we might be able to do with an algorithm, which is a solution.

What do you guys think would be the answer to this question? Does it have some kind of deeper meaning about algorithms, or am I just overthinking it?

philosophically, a problem isn't a problem until there is unrest, and a way to explain it as such. i.e. an understanding leads to determining if it really is a problem, or just misunderstood.  Correctly specifying the problem then leads to its identification.

A bit morbid, but for ex, people dying from arsenic poisoning seems like a problem. Arsenic is poisonous, it will cause death. Is this the problem? No, the problem is exposure. (stated generally for brevity.) The task becomes solving exposure. And of course there may be multiple solutions. Detection, protective gear, isolation, etc.


How the language $\{a^nb^mc^nd^m | n \geq1, \ m\geq1\}$ is used to check whether formal and actual parameters are equal? How does the language $L=\{a^nb^mc^nd^m \mid n \geq1, m\geq1\}$ abstract the problem of checking that the number of formal parameters in the declaration of a procedure agrees with the number of actual parameters in a use of the procedure?

I simply didn't get what each of the variables $a,b,c,d,n$ and $m$ will represent? Seems $1^{st}$ pair $(n,m)$ is for formal parameters and later for actual. But I didn't get why there are $a$ and $b$? Couldn't only single variable be ample?

The language

$$L=\{a^nb^mc^nd^m \mid n \geq1, m\geq1\}$$

abstracts agreement of parameter and argument count for the case where there are exactly two procedures, one with $n$ parameters, declared with $a^n$ and used with $c^n$, and the other one with $m$ parameters, declared with $b^m$ and used with $d^m$. Each procedure is called exactly once and the calls are interleaved with the declarations. The interleaving makes it impossible for a context-free grammar to specify agreement.

One might be tempted to generalize to more uses of each procedure:

$$L'=\{a^nb^m\omega \mid n \geq1, m\geq1, \omega \in \{c^n,d^m\}^*\}$$

or more procedures (I'm not going to try writing that one out), but it just serves to make everything more complicated to no purpose.

The simple example is easily proven to not be context free, and the simplification can be justified by observing that context-free languages are closed under substitution which is a very powerful and useful proof technique. (The fact that declarations and uses can be reduced to repetition of a simple symbol is also justified by substitution. A starting point for Algol-style languages might be to remove all the parameters/arguments from a declaration/call, leaving only the commas and parentheses. For S-expressions it's even simpler.)

So the abstraction provides a simple proof (as well as some intuitive basis) for why parameter/argument agreement cannot be incorporated into a context-free grammar.


Calculate the number of elements after multiplying/adding two polynomials Suppose I have two polynomials $f(x)$ and $g(x)$ and I somehow represent their coefficients.
I have a couple of ways to hold a polynomial depending on how many significant coefficients the polynomial has.
I want to determine the amount of significant coefficients in the results of
$f(x) + g(x)$ ,$f(x) \cdot g(x)$ , $f(x) - g(x)$ etc. .

But I'd like to do it before I create the object that holds them, is there some efficient way of doing this without calculating the result twice?

I can assume that I know the current rank and number of elements in $f(x)$ and $g(x)$

If this is not possible knowing that the new polynomial's non-trivial coefficients will be at least half of the rank will suffice, but I'm unsure how to do it as well.

I did try to apply various heuristics but didn't come up with something consistent and fast.

If $F$ is the number of terms in $f(x)$ and $G$ is the number of terms in $g(x)$ then the number of terms in $f(x)\pm g(x)$ is between $|F-G|$ and $F+G$, and all cases can occur. If you want to calculate the number of terms, you can first run a loop that checks how many non-zero terms the result has, allocate the needed array, and then do the actual computation. The first pass could be faster, since you are only comparing coefficients, which might be faster than actually adding or subtracting them.

For $f(x) \cdot g(x)$, the number of terms is between $F+G-1$ and $FG$, and again these extreme cases can actually occur. Again you can run a first pass which calculates how many non-zero terms there are, though you'd have to be careful if you want to implement it using constant space and the same time (if it is at all possible). It might be better to calculate the product and then reallocate the result to its actual size.


Is subset sum with a fixed target sum NP-complete? I've read that subset sum is NP-complete. What happens when I change the decision problem to look for a  constant number? So the decision problem would look like this:

  Input:
  A collection of nonnegative integers A and a nonnegative integer b,

  Output:
  Boolean value indicating whether some subset of
  the collection sums to 10

Would this still be NP-complete? I don't believe you would be able to reduce every other NP-complete problem to it.

We can throw away all zeroes in $A$. If a subset of $A$ sums to $10$, then this subset contains at most $10$ elements. There are at most $10|A|^{10}$ such non-empty subsets, so we can go over all of them in polynomial time.


Detemine if two DFA's are non-disjoint in polynomial time? Given two DFA's , $M_1$ and $M_2$, I want to create an algorithm that determines if their languages are disjoint or not. The algorithm will run in polynomial time.

My idea is this: Let's say WLOG that $M_1$ has 1 accepting state. We run DFS from that state and look at paths from the state to a starting state. Ideally, a path will be of the form $abb (a\cup b)abbb(ba)^*$ The "or" operator will be used in places where the "path" from the root to the leaf node splits and then merges, and the "*" operator will be used in case of cycles.
We can then do the same thing for $M_2$ and then do an intersection of their paths to find if they have any common paths.

This is basically just an idea that I had; I'm not too sure about the fine details, like how cycle detection will work, and if I need to modify DFS a bit for this to actually work.

Am I totally wrong? Are there any issues with this algorithm?
Any help would be appreciated.

You want to know if there is any string accepted by both automata. There are standard techniques for producing an automaton that accepts exactly these strings, and there are standard techniques for seeing if the resulting automaton accepts any strings.


Where can I code in C? I have an upcoming CS course in uni that uses C and I want to get ahead a little bit this Christmas break but I'm having a hard time figuring out where I can actually code using C. My school uses this compiler called Seashell but it's not available until the term starts.

I've looked at visual studio but I only see C++, and I've heard of stuff like Vim, GCC, but I'm pretty new to CS and I don't know what any of that really means...

Help?

Visual Studio Code
Supports many languages including C/C++. It's a very simple IDE. Have a look at it.
https://code.visualstudio.com/


Unrecognizability of $L(M_1) \cap L(M_2) = \emptyset$ Let's define a language $$C = \{ \{M_1, M_2\} \mid M_1, M_2 \text{ are TMs s.t. } L(M_1) \cap L(M_2) = \emptyset \}$$
We have to show that $C$ is unrecognizable.
I am having trouble going on about with this proof. I am trying to do this by reduction, showing that this language is unrecognizable, but I am unsure on how to reduce this problem into a simpler problem.

Let $T$ be a Turing machine. Construct a Turing machine $T'$ that simulates $T$ on the empty input word and, when (if) the simulation ends, it accepts (regardless of the input to $T'$). Notice that $T'$ can be computed from $T$.
Pick $M_2$ as the Turing machine that immediately halts and accepts.
Then $\{T', M_2\} \in C$ iff $L(T') = \emptyset$, which happens iff $T$ does not halt on the empty input word. Therefore if $C$ were recognizable, the halting problem would be decidable (since the language of all Turing machines that halt on the empty input word is recognizable).
This shows that $C$ is not recognizable.


Fetching multi word instruction from memory A per, from my understanding, instruction decode is a subcycle of Instruction fetch. Now say I have a three-word instruction to be fetched from memory(1 word opcode and remaining words operand address).

My doubt here is: will fetch cycle makes one memory reference and remaining instruction will be fetched in ID stage of Execute cycle or fetch itself fetches the complete 3 word instruction?

With this knowledge I am trying to answer the following question:

Consider a three word machine instruction

ADD A[R0], @B

The first operand (destination) A[R0] uses indexed addressing mode with R0 as the index register. The second operand (source) @B uses indirect addressing mode.

A and B are memory addresses residing at the second and third words, respectively. The first word of the instruction specifies the opcode, the index register designation and the source and destination addressing modes. During the execution of ADD instruction, the two operands are added and stored in the destination (first operand).

The number of memory cycles needed during the execution cycle of the instruction is:

3 Cycles
4 Cycles
5 Cycles
6 Cycles

The total cycle can be 4 or 6 depending on how many cycles fetch is taking. If fetch takes one then Execute will take 6; if fetches take 3 cycles(to fetch complete instruction) then execution will take 4 cycles.

The answer: It depends on the implementation in that particular processor architecture. If this is just a made up example of an architecture, it probably hasn't been thought through properly, so nobody knows the answer.

That said, if I had to implement instruction fetch, then it would fetch the whole instruction.


Circuits vs Turing Machines in the "nonuniform model of computation" I just started learning about circuits in Chapter 6 of "Computational Complexity". There is an emphasis on the fact this model of computation allows different circuits for different input sizes of the problem. The authors refer to this as a nonuniform model of computation.

My question is: why do we need to use circuits for this type of model? Couldn't we just as well allow for a different Turing machine for each input size? Is there some subtle reason for why we need to use circuits in order to study this model of computation?

You can think of Turing machines as a finite description of a function whose domain is $\mathbb{N}$. When you want to specify a different behavior for each member in a collection of finite sets which covers the entire domain, Turing machines are not the natural object to discuss.

You could obviously talk about a sequence of machines $M_n$, where $M_i$ knows how to handle strings of length $i$, and you don't care about how it behaves on different strings (such a definition of nonuniform classes would be equivalent). However, in this case, you don't really use the power of Turing machines. What you care about is only $M_k|_{\{0,1\}^k}$, which is completely determined by a computation table of size $T_k\times T_k$ where $T_k$ is the maximal running time of $M_k$ on length $k$ inputs. This table corresponds to a circuit of size $\le T_k^2$ (this can be improved), which now becomes the more natural object to discuss.


Are Java and C# also purely interpreted languages? I was wondering about the nature of these managed languages i-e since c# and java both are converted into intermediate language and byte code respectively, and are interpreted by their respective runtime(s). So if they are somehow pure interpreted languages then is it feasible to develop any crucial application on these technologies?

It depends on what you mean by "crucial", "feasible", and "interpreted."  Certainly applications which many people consider to be crucial are written in C# and Java, so in some sense the answer to your question must be "Yes."  But we can try to dig a little deeper.

While it is true that Java and C# are both compiled into byte code, in general the  byte code is not directly run by an interpreter.  Instead it is Just In Time compiled (jited).  This means that when you run a C# program, the byte code is compiled into native code and cached by the Common Language Runtime (CLR)  (See the documentation for the ngen program for more details).  Many times the compilation will remain in cache until the runtime is updated, so the compilation is only happening a single time, when the the app is started for the first time (its a bit more complicated in practice, but you get the idea.)

Theoretically this means that as new optimizations are added to the framework, or as new processor features become available, the application will be automatically re-jited into a "better" executable.  This means that, theoretically, the performance of a C# or Java program can be better than a C program compiled for a generic processor.

Typically the applications that C# and Java are unsuitable for are embedded applications and realtime applications.  However, this is mostly due to the way that the most common garbage collectors are non-deterministic, and does not have much at all to do with the way the languages are compiled.  Additionally, applications that need to use native libraries, or access memory in very specific ways, may encounter performance problems or other obstacles when implemented in C# or Java, due to auto-boxing, pinning, etc.  However this has more to do with "managed memory" and safety then with compilation.


Lower bound on multiplication I was told that the fastest possible algorithm for integer multiplication is $O\left(n{\log}(n)\right)$. Why would this so?

Can you please show why the fastest multiplication algorithm would have such a time complexity?

There is a lower bound for multiplication of $\Omega(n\log{n})$ conditional on a conjecture in network coding. There is also an algorithm matching this bound.


How to handle missing attribute's value with ID3 algorithm? i am working with ID3 algorithm, and i know that classic ID3 basically can handle missing data. But i am trying to code this algorithm, so what should i do if there is missing attribute's value in training dataset? How can i classify the data point that has missing attribute's value?

One approach is to use imputation to estimate a value for the missing attribute, based on other attributes.

See also https://en.wikipedia.org/wiki/Missing_data#Techniques_of_dealing_with_missing_data and https://stats.stackexchange.com/questions/tagged/data-imputation and https://stats.stackexchange.com/questions/tagged/missing-data
and https://stats.stackexchange.com/q/208845/2921.


Question about proving that Rado's function is non-computable I am currently following the proof, found here, that Rado's function
$$
\Sigma (n) = \max \{ \text{# of 1's that may be written to a tape by an n-state turing machine} \}
$$
is non-computable. Within this proof, they say that there exists a Turing machine $M_F$, which we say has $n$-states, that writes $F(x)$ 1's to the tape.

However, they then go on to imply that there exists a Turing machine with $n$ states which writes $F(F(x))$ 1's to the tape! Surely, since $F(x) > x$ this should require more than $n$ states - since more states $\iff$ more 1's?

EDIT: For added clarity, I will now explain why I have interpreted this to mean that both $F(x)$ and $F(F(x))$ have $n$ states.

This proof first defines a Turning machine $M_F$ which has $n$ states and writes $F(x)$ 1's to the tape before halting. It then goes on to describe a (trivial) $x$-state Turing machine $M$ which "on input $\Lambda$" writes $x$ 1's to the machine's tape.

The proof then goes on to claim that
$$
\Sigma (x + 2n) \geq x + F(x) + F(F(x))
$$
which means that there exists a $x + 2n$ state Turing machine which prints $x + F(x) + F(F(x))$ 1's to the machines tape.

I am assuming that these $x + F(x) + F(F(x))$ 1's are written as follows:

The $x$ state Turing machine $M$ prints $x$ 1's to the tape.
Next, $F(x)$ 1's are written to the tape by the $n$ state Turing machine $M_F$
So far, we have written $x + F(x)$ 1's and $x+n$ states have been used to do so. Comparing this to the fact that $x + F(x) + F(F(x))$ 1's may be written using $x + 2n$ states, they are implying that there must exist a Turing machine which writes $F(F(x))$ 1's using $n$ states

I am probably interpreting this incorrectly, but I don't know why?

Thanks for the clarification! I really misinterpreted your question.

Okay, so we have the computable function $f$, the also computable function $F$ that is based on $f$, and the Turing machine $M_F$ with the following behavior:

  when started with a tape with $y$ $1$'s, writes a block of $F(y)$ $1$'s to the right, separated by at least one blank

Note that I used $y$ instead of $x$. So when our TM starts with a tape like

$$\Delta\underbrace{1\ldots1}_{\times y}\Delta$$

the resulting tape will be

$$\Delta\underbrace{1\ldots1}_{\times y}\Delta\underbrace{1\ldots 1}_{\times F(y)}\Delta$$

and we say that $M_F$ uses $n$ states. Note that $n$ is independent of $y$. The number of states doesn't depend on the input of the TM.

Now the machine $M$ does the following:

Start with blank tape: $\Delta$
Write $x$ $1$'s on tape: $$\Delta\underbrace{1\ldots1}_{\times x}\Delta$$
Now mimic $M_F$ with these $x$ $1$'s as a start, i.e. $y=x$: $$\Delta\underbrace{1\ldots1}_{\times x}\Delta\underbrace{1\ldots 1}_{\times F(x)}\Delta$$
Now we mimic $M_F$ again, but this time with the $F(x)$ $1$'s as a start, i.e. $y=F(x)$: $$\Delta\underbrace{1\ldots1}_{\times x}\Delta\underbrace{1\ldots 1}_{\times F(x)}\Delta\underbrace{1\ldots 1}_{\times F(F(x))}\Delta$$

So when we mimic $M_F$ a second time, we simply ignore the $x$ $1$'s at the leftmost of the tape and pretend they are not there. I think the text is implying that executing $M_F$ doesn't moves it too much left and that is understandable, since this behavior can be simulated by using a one-side bounded TM which is equivalent to our usual TM. So by mimicking $M_F$ two times, we would need about $2n$ states for that.


Is the height of the tree the number of edges or number of nodes? I'm so confused by some of the theorems online about tree heights. Does tree height mean the number of edges or nodes? if nodes, does it include the node it is counting from? Can the height of a tree start from 0?

As Yuval says, there's no standard definition. This is not because computer scientists are indecisive but because it's sometimes more convenient to use one definition and sometimes more convenient to use the other.  For example, a full, balanced binary tree of height $h$ has $2^h$ leaves if you define height as number of edges and $2^h-1$ vertices in total if you define height as number of vertices. Each of these statements becomes less convenient if you use the other definition and have to keep writing $h-1$ or $h+1$.

The situation is exactly the same as the natural numbers: sometimes, it's more convenient to say that zero is a natural number (for example, the natural numbers are a semiring only if zero is included); other times, it's more convenient to omit zero (for example, if you always want to be able to divide by a natural number).  In fact, similar things happen throughout mathematics. Another example is that it's common to insist that graphs have at least one edge (or at least one vertex) to avoid having to start all your theorems "If $G$ is not trivial, then..."


When is it best to use the second chance replacement algorithm? I'm going through 'Operating Concepts' by Silberschatz, Galvin and Gagne (The Dinosaur Book) and it mentions the Second-Chance Algorithm (not enhanced) as an improvement on the FIFO replacement algorithm.

My question is, is there ever a case where this algorithm would perform better than, say, the Least Recently Used algorithm or even something like the Farthest-in-Future Algorithm? The book describes how the algorithm works but doesn't offer a lot of information on when it would be useful, other than just in improving 'FIFO'.

To add to this, is there ever a case where 'second chance' would out preform LRU? I'm assuming the answer is yes, as no algorithm is perfect for every situation.

Farthest-in-future is optimal, second chance can't be better. Second chance is a way to approximate LRU when the required hardware (access times, sort them) isn't available. Both try to approximate the optimal strategy, there certainly can be cases where one or the other is better.


Amortized time cost of insertion into an Array list A dynamically resizing array list will resize when the number of elements reaches a power of two. So, after n elements inserted, we've resized at sizes 1, 2, 4, ... , n. This also means we've copied over into the newly resized array 1, 2, 4, ... , n number of copies. What then is the sum of this sequence? To answer that we see that the sequence written backwards is n + n/2 + n/4 + ... + 1. Until here I understand what has been said. Here is where my confusion starts, how is this sequence roughly equal to 2n? How do we know this? Once we settle that we can say that n insertions take O(2n) time, but from that how do we deduce that the amortized time for each insertion is O(1).

For the estimate,
$$
n + \frac{n}{2} + \frac{n}{4} + \cdots +1 <n \left(1 + \frac{1}{2} + \frac{1}{4} + \cdots \right) = 2n,
$$
since $1 + 1/2 + 1/4 + \cdots = 2$.

If $n$ insertions take $O(n)$ time, then the amortized time per insertion is $O(n)/n = O(1)$. This is by the definition of amortized time. (More accurately, the amortized time is at most $K$ if $n$ insertions take at most $Kn$ time, for every $n$.)


Storing $K$ numbers with ordering Let $S$ be a sequence of $k$ many numbers. The position of the number in the $S$ matters. In the $S$ there are only $j$ many different numbers are there means $S$ contains many duplicates. Position is a query which needed to be answered, position(i) returns the element at position $i$ in $S$.

Trivial way to store them is using array which will takes $O(S)$ space and position can be solved in $O(1)$ time.

I am looking for a representation that takes $O(j)$ space (or somewhere near to it) and such that position can be solved in $O(1)$(even in more time is also ok)?

Please suggest some papers also.

What you ask is impossible, assuming you don't really mean sets (as sets are orderless), but ordered tuples. Consider $j=2$, then you effectively have $k$-length binary strings. And those require $\Omega(k)$ storage.


Hardness of checking maximal magnitude of a sum of a subset of vectors The problem I wish to solve is the following:

Given a set $V \subset \mathbb{Z}^2$ find the set $S \subset V$ such that $|\sum_{v \in S} v|$ is maximal.

By simply enumerating subsets we can solve this problem in $O(2^n)$. This problem feels a lot like the euclidian traveling salesmen problem to me but I can't quite make it fit. I've tried other numerical optimization techniques like giving each vector an associated scalar variable, the idea being that if the variable was 0 then you'd exclude the associated vector it and if it was 1 then you'd include it. Then the goal is to find an assignment of the variables that maximizes this (I used Lagrange's method). That pretty much just got me back to a clearly equivalent problem that I had no more hope of solving efficiently. I can't seem to find any way to do this any faster. Additionally, I'm having trouble concluding that it's NP-hard but it's my bet that it is. For such a simple problem I'd imagine it's been considered before.

Is this problem known NP-hard? Is there a reduction I just haven't seen yet? Is there some efficient algorithm I just haven't seen?

I suppose you are talking about the euclidean norm. Consider the optimal solution $S$ and let $w=\sum_{v\in S}v$, and we assume there's no zero vector in $V$.

For any $v\notin S$, it must holds $v\cdot w<0$, otherwise $\|w+v\|^2\geq \|w\|^2+\|v\|^2>\|w\|^2$. Similarly for $v\in S$ it holds $v\cdot w>0$, otherwise $\|w-v\|>\|w\|$.

That means $S$ is exactly determined by the direction of $w$. You can exhaust the possibilities by sorting the polar angles of the vectors, and rotate the orthogonal line of $w$ which has only $n$ essentially different partitions.


Nested word automatons At the moment I'm trying to understand nested word automatons but I don't get the point quiet right. Let's say I have the alphabet $\Sigma = \{c,r\}$ and I want ot recoginize the  languge $\mathcal{L} = \{ \langle  c^n r\rangle^n \}$. On slide 14 of this presentation I found the following automaton which should recognize $\mathcal{L}$.

After reading the last $\langle c$ the automaton is is state $(q_1,p_1)$ and, since $\delta_r: Q \times P \times \Sigma \rightarrow  Q$, after reading the first $r\rangle$ it switches to $(q_2)$. So how does the automaton keep track of reading the same ammount of $\langle c$ and $r\rangle$? Do we have to keep the hierarchical state in mind for each call symbol? If so wouldn't we need a stack again for that?

Please note that the input to a nested word automaton is nested words instead of the usual words.

A nested word $n$ over $\Sigma$ is a pair $(a_1\cdots a_l; \leadsto)$, where $a_i\in\Sigma$ and $\leadsto$ is a matching relation of length $l$. Note that if there is no pending call nor pending returns (in which case $\leadsto$ is said to be well-matched), then the number of the calls and the number of returns are equal by the definition of a matching relation. This is the case when you use $\{ \langle  c, r\rangle\}$ as the alphabet of $L$ to represent the nested words.

What the nested word automaton in the question does mostly is, indeed, to check that all $\langle c$'s happens before $r\rangle$'s.

You are encouraged to read the seminal paper Adding Nesting Structure to Words by Rajeev Alur and P. Madhusudan. You might be delighted to find it is pretty easy to read, especially the relevant section 3.1.


probability wheel, redistribution of probabilities I have a contiguous ordered data structure (0 based index):

x= [1/3, 1/3, 1/3]

Let's say I selected index 1 and increased the probability by 1/3. Rest of the probabilities each decrease by 1/6 and the total probability remains P = 1.

x= [1/6, 2/3, 1/6]

Let's say I selected index 2 and increased the probability by 1/3. Rest of the probabilities in total need to decrease by 1/3 to make the total probability remain P= 1.

x= [1/10, 2/5, 1/2]

Is there a name for this kind of data structure? I'd like to research that name and use a library instead of my custom rolled code if possible.

This can be easily achieved by an  array $A$ and an additional variable $m$. The entry $A[i]$ stores the probability of $i$ times $m$.

In your example you start with

A=[1,1,1], m=3

The you increase the probability of the second element by 1/3. This can be carried out by setting $A[2]=4$ and $m=6$, which gives

A=[1,4,1], m=6

In general you could set the probability of element $k$ to $p$ by solving the system
$$\sum_i A[i] = m \text{ and } A[k]=p\cdot m,$$
for the unknowns $A[k]$ and $m$.

So all you need to do is to set $m$ to
$$ m = \frac{\sum_{i\neq k} A[i]}{1-p},$$
and $A[k]=p\cdot m$ for the new $m$.


Global Optimization of a well-defined function with gradient information I try to minimize the function
$$ f(x_1, …x_n)=\sum\limits_{i}^n-a_i\cos(4(x_i-b_i)) +\sum\limits_{ij}^\text{edge}- \cos(4(x_i-x_j)), \quad
x_i,b_i\in (-\pi, \pi)$$
where $\sum\limits_{ij}^{edge}$ only sums over predefined edges (the edges are sparse, typical there are 4 edges for each $i$). The variables $a_i, b_i$ are constants, $ a_i \in (0,1)$; many $a_i$s are 0.
The gradient at each iteration can be directly computed. I observe that Gradient Descent converges very fast, but produces very bad results (very easily falls into local optimal). I have no idea whether Conjugate Gradient Algorithm or BFGS algorithm will make a significant difference.$$$$
While general optimization such as simulated annealing and GA do not use the gradient information (they seem powerful but blind to local derivative), thus I am looking for techniques making good use of gradient information.

One alternative is to use Newton's method.  Newton's method uses information from the first and second derivative (i.e., the Hessian matrix), so it can converge in fewer steps than gradient descent (which uses only information from the first derivative) -- but the cost is that each single step is slower, because it requires more complex computations.

If Newton's method is too slow, there are faster variants, such as BFGS and other quasi-Newton methods or the conjugate gradient method.

Another approach is to continue using gradient descent, but make some adjustments.  One simple thing you can try is to apply it many times, each time with a different random starting point.  Also there are various tuning knobs you can tweak, such as adjusting the step size or using momentum.  A third possibility could be to try to make a "smarter" choice of starting point for gradient descent: you can approximate each cosine by a quadratic function (using the Taylor series expansion at a particular point), obtain a function $f^*$ that is a quadratic approximation to $f$, and then find the exact minimum for $f^*$ using least-squares method.  This basically amounts to applying one step of Newton's method and then continuing with gradient descent from there.

Trying several different methods shouldn't be too hard if you use the right software, as there are many software packages that let you specify the function and then make it easy to try multiple different optimization methods.


Get nodes that are participating in any cycle in a graph I have a problem that states the following :

  Given a cyclic graph , output for each node if the node removes all cycles in the graph.

The most trivial way to do this is using a Union-find disjoint set , and for each node , try not putting it in the Union-find disjoint set , if there are no cycles , then this node should output "Yes" , otherwise "No".

This approach would take about $\Theta(N^2)$ time and $\Theta(N)$ memory.

The problem also stated that $N \leq 1,000,000$ which would definitely get a TLE (Time Limit Exceeded) Answer on any problem.

So, my question is, What's the algorithm that would take $\Theta(N \lg N) $ or $\Theta(N)$ time and $\Theta(N)$ memory?

First use Tarjan algorithm to find all of the bridges in the graph. Then remove all of them. Remaining graph should be made of some cycles, such that all of them have at least one common vertex, otherwise we can return false for all vertices. Is possible to check this with DFS, further reasoning is easy, total running time is $O(|V|+|E|)$.


What is the difference between bounding and pruning in branch-and-bound algorithms? Could anybody please explain what the difference between "bounding" and "pruning" in branch and bound algorithms is?

I'd also appreciate references (preferably books), where this distinction is made clear.

In branch and bound algorithms, you essentially partition the original problem to be solved in a number of subproblems whose union is equivalent to the original problem you started with. The process of deriving new subproblems is called branching and leads to the so-called branch decision tree. Now, when you need to solve a subproblem, you can either determine its optimal solution, show that the subproblem is infeasible (so that you can discard it), or you can show that the subproblem solution is no better than the best known solution for the original problem. If you are not able to solve a subproblem, you branch again, partitioning it into sub-subproblems. Now, for each subproblem you can derive a lower bound for its solution and, if the lower bound is greater than or equal to the best known solution for the original problem, you can discard the subproblem since the best solution you can obtain for the subproblem is certainly worst with regard to the feasible solution of the original problem.
In order to get a lower bound you must relax the problem. The relaxation may be continuous, lagrangian etc.

Therefore, the word bound in branch and bound refers to the process of determining lower bounds for subproblems. Pruning refers instead to the process of discarding subtrees in the branch decision tree rooted at subproblems whose solution is impossible or worst with regard to the feasible solution of the original problem.


How to analyse the complexity of a problem with two or more size measures Consider this example: a problem of dimension $n$ and $m$ ($m,n$: any given integers).
has a search space of size $O(n^n * m^n)$.
It is clear that this problem is exponential in $n$,
whatsoever $m$ may be.
My question: is this same problem polynomial in $m$?
what are the assumptions if we can say that?
is this way of complexity analysis correct?

There's nothing wrong with your approach. You have a two-variable function with a known (almost, up to a multiplicative constant) upper bound. In that case, it's perfectly acceptable to take a "slice" through the function by holding one of the variables fixed and ask how the resulting one-variable function behaves. One does this sort of thing often, when, for example, we take the derivative of $f(x, y)$ with respect to $x$.


Which data structure can be used to determine most experienced person in a shift? Problem Statement: There are $n$ hours in a day and you have $w$
workers.  For each worker $i$ you will be given $x_i$ (work experience),
$s_i$ (shift start time) and $e_i$ (shift end time) on a separate line.
Here $s_i$ and $e_i$ are both inclusive.  At any given hour $t$ in a
day, you have to determine who is the most experienced worker available.
I thought of two approaches:

Keep an interval array of size $n$.  For each worker $i$, from index
$s_i$ to $e_i$ of the array, fill it with $x_i$ if current value in
the array is lesser.  This is memory intensive.

Store $\left( x_i, s_i, e_i \right)$ for each worker $i$ in a list.
Loop through the list for every $t$ provided to find the most
experienced person.  This is CPU intensive.

I want to know which data structure can be used to solve this problem
optimally.

Let $s_i$, $e_i$, $x_i$, be the shift start time, shift end time, and experience of the $i$-th worker.
For each worker define the following two events:

A shift-start event is a triple $(s_i, 0, i)$.
A shift-end event is a triple $(e_i, 1, i)$.

Collect all events in an array $E$ and sort it in increasing order (lexicographically). This requires $O(w \log w)$ time.
We will process these events in order. Maintain a pointer $p$ to the next event in $E$ to process. Also maintain a priority queue $Q$ that supports deletions (an implementation using a binary heap suffices). Initially $Q$ is empty.
For each hour $t$ of the day, in increasing order, do the following:

Scan $E$ by advancing $p$ to find all (shift-start) events of the form $(t, 0, i)$. For each such event, add key $i$ with priority $x_i$ to $Q$.
Look at the key $j$ at top of $Q$ (in constant time). Report $j$ as the most experienced worker at time $t$.
Scan $E$ by advancing $p$ to find all (shift-end) events of the form $(t, 1, i)$. For each such event, delete key $i$ from $Q$.

This requires $O(w)$ space to store $E$ and $Q$, and at most $O(n + w \log w)$ time since there are $2w$ insertions/deletions into/from $Q$, each of which requires $O(\log w)$ time.


Time Complexity of the code I am having trouble finding the time complexity of the below code.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """

        if root is None:
            return True

        def height(root):
            if root is None:
                return 0
            left = height(root.left)
            right = height(root.right)

            return 1 + max(left, right)

        def check(root):
            if root is None:
                return True

            if abs(height(root.left) - height(root.right)) < 2:
                return(check(root.left) and check(root.right))
            else:
                return False

        return check(root)

Is it O(n^2) or O(n) because first we are checking for the root, and that takes O(n) time and then we check for the left subtree and the right subtree, where the elements searched are halved each time?

Thanks!

Your code has worst-case complexity $\Omega(n^{1.5})$. Consider a tree of height $h$ which is composed of a "backbone" of $h$ nodes, out of the $i$th of which (counting from the root) there is a path to the right ending at depth $h$. As an example, here is the case $h=4$:

The height is computed along the entire backbone. The subtree rooted at the backbone node of depth $h-\ell+1$ has $\binom{\ell+1}{2}$ nodes (where $\ell=1$ corresponds to the backbone's leaf), and so computing the height of all subtrees along the backbone takes time proportional to
$$
\sum_{\ell=1}^h \binom{\ell+1}{2} = \binom{h+2}{3} = \Theta(h^3).
$$
In contrast, the tree contains $\binom{h+1}{2} = \Theta(h^2)$ nodes, so the running time in this case is $\Omega(n^{1.5})$ (in fact, it is $\Theta(n^{1.5})$ in this particular case).


Algorithm for deducing values I have a group of logical conditions and need to deduce values that would NOT satisfy them.  For example:

City != New York && Location = Museum
City = New York && Location = Store
City != New York && Location != Subway
Elevation = 100'

So some values that would NOT satisfy any of those conditions are:

City: New York, Location: Museum, Elevation: 110'
City: Moscow, Location: Subway, Elevation: 110'

I just need to derive values, any values, that will fail to satisfy all conditions.  (Application: Generating manual tests.)

It's easy to figure out values to violate any one condition, but I'm having trouble coming up with an algorithm to generate values that will violate them all.  I have all the logical conditions in a data format (JSON, e.g. { key: 'City', operator: '=', referenceValue = 'New York' }).

This solution worked for me, but I'm not making it an answer because it's not super-elegant and I'm not sure it would work in all cases.

Create a value hash for each key, populating it with all possible values for that key.
Each value for each key is marked ALLOWED initially, but can later be marked CONTINGENT or DISALLOWED. (I created a ValueDisposition class to manage this.)
Find relevant conditions for each key, and analyze their effect on values.  For example analyzing condition 4 above for elevation would mark 100' as DISALLOWED (because we are looking to find data that violate all the given conditions). Analyzing condition 2 above for City would mark New York as CONTINGENT because it is only a valid value if the contingent condition Location = Store is violated (I record contingent conditions in the ValueDisposition class as well).
Do a first pass finding an ALLOWED value for as many keys as possible.
Do a second pass on CONTINGENT values, violating the contingent conditions to derive acceptable value-sets (for example, with New York it's easy to violate Location = Store). I was able to do this easily for all of my condition-sets, but this could get challenging (requiring recursion?) if you had contingent conditions involving multiple keys.

As the comments indicated, if the goal is to invent fictional cities, and you allow more three or more conjuncts in a condition, then any SAT problem is reducible to your problem.

Depending on the type of constraints, this is probably a more general problem, called "SAT Modulo Theories" or SMT for short. It's the boolean satisfiability problem, plus the theory of whatever your constraints are.

For example, if you allow inequalities:

Elevation < 200

You now need to decide what kinds of constraints those are. If elevation is an integer, and you allow constraints between properties (e.g. number of subway stations is less than the number of suburbs), then solving the problem is, in general, an integer programming feasibility problem.

But chances are that you don't need to worry about that for your scale. If we allow the closed-world assumption, in the sense that the set of city names and locations etc is fixed, then backtracking search is probably good enough. A small Prolog program will do the job.

Here, I used GNU Prolog, and attached the finite domain solver for elevation:

city(new_york).
city(moscow).
city(london).
city(paris).

location(museum).
location(store).
location(subway).
location(grand_bazaar).

% The lowest city in the world is Jericho, and the highest city
% is La Paz.
elevation(Elevation) :- fd_domain(Elevation, -846, 11975).

satisfying_cities(City, Location, Elevation) :-
    city(City),
    location(Location),
    elevation(Elevation),
    (City = new_york ; \+ Location = museum),
    (\+ City = new_york ; \+ Location = store),
    (City = new_york ; Location = subway),
    (Elevation #\= 100).

And running the query:

?- satisfying_cities(City, Location, Elevation).

gives some answers, the first of which is:

City = new_york
Elevation = _#0(0..99:101..127@)
Location = museum

The FD constraint on elevation is a little hard to read, but it's essentially saying that any elevation between 0 and 99 or 101 and 127 will do.


Random award question I'm assisting with the design of an algorithm over the next week to fit the following use case:

A person walking in a store has a tablet and approaches possible customers to notify them of a competition. When a customer enters their details, upon completion of the form - a request is sent to the server, and the customer will be randomly drawn (at that point in time) for a prize.

A maximum of 4 customers are chosen, the number of customers walking into the store is not known. The store is open from 8am until 4pm.

Would there be any other way (other than the ones stipulated) to solve something like this without knowing the average customers visiting the store?

Solution 1

I was thinking a normally distributed probability is used, where the parameters could be tweaked over time to fit this allowing customers to be selected (more or less) equally through out the day.

Solution 2

Similar to solution 1, but the time throughout the day is partitioned into segments. Between the hours of 8am and 12pm, a maximum of 2 people can be chosen.

I don't quite like the idea of doing this because if a majority of the customers come in the morning, this could lead to less than the 4 prize hand out expected of the day.

There is no way to ensure that exactly 4 people win, and that all people have an equal likelihood of being chose.

For instance, suppose you see 100 people during from 8am-3pm, and have given out 3 awards.  Then, if 500 people all show up in the last hour, you have at most one more award to give out, so those people will have a much lower chance of winning.  Alternatively, suppose you see 100 people from 8am-3pm and have given out 0 awards.  Then, if 4 people show up the last hour, the only way to give out exactly 4 awards is to give each of them an award, so those people will have a much higher chance of winning.

As a result, there probably is no perfect solution -- you will just be trading off different kinds of imperfection.

One solution is to not give anyone an award, but that's not very useful.

A practical solution is probably to get some data beforehand on the estimated number of people who show up per day, and use that to choose the probability of winning for each person.  Once you've given out 4 awards, stop.  For instance, suppose on average 100 people show up per day.  Then as each person arrives, with probability $0.04$, given them an award.  If you hand out 4 awards, no one else gets one for the rest of that day.  That ensures that the expected number of awards handed out is a bit less than 4; that you won't hand out more than 4 awards; and that everyone's probability of winning is close to the same.

If you don't need to determine in real time whether each person has won, you can use reservoir sampling.


Is RAM always volatile? I understand that computer memory in typical modern computing systems (such as the laptop I am asking this question from) is generally involatile but in some exceptions, such as RAM, the memory is indeed volatile.
Is RAM always volatile? Isn't there any "exceptional" kind of involatile RAM by humans somewhere?

Go 45 to 65 years back in time when RAM was “core memory” - tiny magnetic rings with wires threaded between them. Core memory was not volatile.


What do assemblers translate macros into during assembling? I have dug in simple binaries, such as though like x86 bootloaders, sega video game binaries, etc. I know that these files tend to use assembler macros to define data, etc.
What I am having trouble figuring out is what assemblers tend to translate macros into exactly (are they instructions, custom formatted data entries used statically, addressing mode/special opcodes, etc.).

I do not know if this is the wrong place to ask. If so,  I am saving time by double-posting on reverse engineering 's SE.

From a semantic point of view, macros are expanded into assembly code. How macros are actually implemented probably depends on the assembler. One option would be to expand them in a preprocessing step, like in C compilers; another would be to expand them on the go. The end result is the same — it is as if the macros were expanded textually in a preprocessing step.

There are other mechanisms used in assemblers that you might consider macros but are different. For example, the x86 MASM uses db/dw/dd to define data. These are stored in the resulting executable, the exact way depending on the executable format, particularly how the binary is loaded into memory. Usually there is a specific data segment which is loaded into a specific address, the relevant pages being marked non-executable if the processor supports this.


What is Ironic complexity? What are some good resources to learn about it? The term "Ironic complexity" was coined by Scott Aaronson for the stuff Ryan Williams does in the area of complexity theory. Could anyone tell me what kind of problems and approaches does Ryan Williams work upon? And is there a survey or course on it for self-study?

Here is a quote from Scott Aaronson's survey on the P vs NP question, in which he coined this term:

  There is one technique that has had some striking recent successes in proving circuit lower bounds, and that bypasses the natural proofs, relativization, and algebrization barriers. This technique might be called “ironic complexity theory.” It uses the existence of surprising algorithms in one setting to show the nonexistence of algorithms in another setting. It thus reveals a “duality” between upper and lower bounds, and reduces the problem of proving impossibility theorems to the much better-understood task of designing efficient algorithms.

The survey contains some pointers which you might want to look at.

Ryan Williams has given a series of two talks on this recently at the Simons institute: part 1 and part 2.


Restricted Boltzmann machine confusing details Hi I'm new to RBM and machine learning/computer vision in general, and I'm using the code from: http://blog.echen.me/2011/07/18/introduction-to-restricted-boltzmann-machines/ while reading on https://en.wikipedia.org/wiki/Restricted_Boltzmann_machine for some theories. But right now i'm totally confused. In the code there is a part:

# Calculate the activations of the hidden units.
      hidden_activations = np.dot(visible, self.weights)
      # Calculate the probabilities of turning the hidden units on.
      hidden_probs = self._logistic(hidden_activations)

I assume the equivalence in wikipedia would be the conditional probability, but when I look that up, nothing makes sense! I mean, what are v and h, are they supposed to be vectors or values? (I assume they are in fact just values, as wikipedia only talks about each seperate samples while the code groups all of them into a matrix, but even them it's still hazy :( ). I'm new to this so my question may be a little dumb but please help me. Thank you very much!
P/s: Sorry I am unable to post the equations :(

The equation from the wikipedia implemented with this code is the one in picture bellow. Sigma function is logistic sigmoid (self._logistic()). The dot product is the sum of products bellow. bj is offset and might be included in the sum (some visible neuron is always 1) or it might be omitted completely for simplicity or something else.


An algorithm to compute a set of states that satisfy a specific CTL formula Working through a past exam question and I'm unsure where to start or what form they want the answer in:

Define an algorithm that receives as input a finite transition
system TS defined over the set of actions {a, b, c} and computes
the set of states of TS that satisfy the CTL formula ∃a U b.

Would anybody be able to give me a kick-start or a walk-through on how to answer this? Really appreciate any help.

edit: My attempt based on Klaus' answer

for all executions in TS
 for all states
  if **b** holds
   add current state to the stack, EXISTS = TRUE
  else if **a** holds
   if current state == next state in execution
    do nothing
   else if next state contains **a** or **b**
    add current state to the stack, EXISTS = TRUE
   else
    do nothing

The set of states satisfying $\exists a U b$ is the smallest set $S$ such that

$S$ contains all states satisfying $b$, and
$S$ contains all states satisfying $a$ which have a successor in $S$

Note that we specify the "smallest" such set because otherwise you could  pick the set of all states, or include arbitrary cycles of $a$-states, etc. Do you see how to get an algorithm from this?


How can random array access be considered $O(1)$ if bits must be stored in space and light travels at finite speed? Bits are usually stored linearly in space. We can say, thus, that the length of a memory chip, for example, is linearly proportional to the number of bits it can hold. Since signals must travel at finite speed in our universe, the time it takes to read the last element an array will always be proportional to the length of the array. Am I missing something?

When we talk about "running time" of algorithms, we don't mean literally time in seconds but number of operations in some abstracted machine model. In such a model, accessing a memory cell is taken to be a single operation, taking unit time.

Note that this is hiding much more significant details of real computers than the speed of light across a chip.  Whether or not the required data is in the cache will have a much more significant effect than any consideration based on the speed of light.


What is the name of the optimization that removes self eliminating multiplication-division statements? I have a compiler optimization which should be quite common, but I can not find a name for it, nor a reference that describes it.

Given an integer x, not known at optimization time, a known constant c and the following program

x_1 = x * c
x_2 = x_1 / c
print(x_2)

It's pretty clear that the code can be optimized to

print(x)

What is the name of this optimization? Is there a paper/book describing it?

Thanks!

It's probably most easily described as a two-step process. First a step of Copy Propagation to get

x_2=x*c/c
print(x_2)

followed by a step of Constant folding to remove the unecessary operations.


Algorithm To Compute The Gaps Between A Set of Intervals Problem
Given a set of intervals with possibly non-distinct start and end points, find all maximal gaps. A gap is defined as an interval that does not overlap with any given interval. All endpoints are integers and inclusive.
For example, given the following set of intervals:
$\{[2,6], [1,9], [12,19]\}$
The set of all maximal gaps is:
$\{[10,11]\}$
For the following set of intervals:
$\{[2,6], [1,9], [3,12], [18,20]\}$
The set of all maximal gaps is:
$\{[13,17]\}$
because that produces the maximal gap.
Proposed Algorithm
My proposed algorithm (modified approach taken by John L.) to compute these gaps is:

Order the intervals by ascending start date.
Initialise an empty list gaps that will store gaps
Initialise a variable, last_covered_point, to the end point of the first interval.
Iterate through all intervals in the sorted order. For each interval [start, end], do the following.

If start > last_covered_point + 1, add the gap, [last_covered_point + 1, start - 1] to gaps.
Assign max(last_covered_point, end) to last_covered_point.

Return gaps

I have tested my algorithm on a few cases and it produces the correct results. But I cannot say with 100% guarantee that it works for every interval permutation and combination. Is there a way to prove this handles every permutation and combination?

The key to prove your algorithm is correct is to find enough invariants of the loop, step 4 so that we apply use mathematical induction.

Let $I_1, I_2, \cdots, I_n$ denote the sorted intervals. When the algorithm has just finished processing $I_i$, we record the values of gaps and last_covered_point as $\text{gaps}_i$ and $\text{last_covered_point}_i$ respectively.
Let us prove the following proposition, $P(i)$, for $i=1, 2, \cdots, n$.

$\text{gaps}_i$ is the set of all maximal gaps for $I_1, I_2, \cdots, I_i$ and $\text{last_covered_point}_i$ is the maximum of all right endpoints of $I_1, I_2, \cdots, I_i$.

When $i=1$, $\text{gaps}_1$ is the empty set and $\text{last_covered_point}_1$ is the right endpoint of $I_1$. So $P(1)$ is correct.
For the sake of mathematical induction, assume $P(i)$ is correct, where $1\le i\lt n$. Let $I_{i+1}=[s, e]$. There are two cases.

If $s\gt\text{last_covered_point}_i+1$, then $$\text{gaps}_i\cup[\text{last_covered_point}_i +1, s-1]=\text{gaps}_{i+1}.$$
Let $m$ be any point between the start point of $I_1$ and the maximum of all right endpoints of $I_1, I_2, \cdots, I_{i+1}$. Suppose $m$ not covered by any of $I_1, I_2, \cdots, I_{i+1}$.

If $m\le\text{last_covered_point}_i$, the induction hypothesis says that $m$ is covered by some interval in $\text{gap}_i$.
Otherwise, $m\gt\text{last_covered_point}_i$. Since $m$ is not covered by $I_{i+1}$, we know $m<s$. So $m$ is covered by $[\text{last_covered_point}_i +1, s-1]$.

In both cases, $m$ is covered by some interval in $\text{gaps}_{i+1}$. Since $\text{last_covered_point}_i$ is the largest point covered by one of $I_1, I_2, \cdots, I_i$ and $s$ is the smallest point covered by $I_{i+1}$, $[\text{last_covered_point}_i +1, s-1]$ is a maximal gap.

Otherwise, we have $s\le\text{last_covered_point}_i$+1. We can also verify that $\text{gaps}_{i+1}=\text{gaps}_{i}$ is the set of all maximal gaps for $I_1, I_2, \cdots, I_{i+1}$.

Finally, since step 4.2 says $\text{last_covered_point}_{i+1}=\max(\text{last_covered_point}_i, e)$ and $\text{last_covered_point}_i$ is the maximum of all right endpoints of $I_1, I_2, \cdots, I_i$, $\text{last_covered_point}_{i+1}$ is the maximum of all right endpoints of $I_1, I_2, \cdots, I_{i+1}$.
So, $P(i+1)$ is correct. $\quad\checkmark$.


reduction from MAX-CUT to MAX-3-CUT MAX-3-CUT gets a graph and a number $k$, and determines whether three sets of vertices can be found within that graph, where at least $k$ edges are in the cut.
We define the cut as all edges $(u,v)$ where $u$ and $v$ are in a different set.

MAX-CUT also gets a graph and a number $k$, and does the same but by dividing it to two sets of vertices.

It is known that MAX-CUT is NP complete and I'm trying to show that MAX-3-CUT is also NP Complete by reducing from MAX-CUT.

What I've done so far:

Showing that MAX-3-CUT in NP is easy using a verifier.
I think the reduction should be, given $\langle G=(V,E),k \rangle$ return $\langle G',k+|V| \rangle$,
where $G'=(V'=V+{w}, E'=E+\{(w,v) : v \in V\})$.
Proof of correctness:
doing so, It's easy to show that if $\langle G,K \rangle$ is in MAX-CUT then $\langle G',k+|V| \rangle$ is in MAX-3-CUT by setting the third group to be $\{w\}$.
The problem is I can't do the opposite direction: if $\langle G,k \rangle$ isn't in MAX-CUT than $\langle G',k+|V| \rangle$ isn't in MAX-3-CUT.
I also tried to show that if $\langle G',k' \rangle$ is in MAX-3-CUT then $\langle G,k \rangle$ is in MAX-CUT but I get stuck with how to turn 3 sets into 2.

Note: I was able to show that MAX-3-CUT is NPC by reducing from 3COL (pretty straightforward), but I need it to be reduced from MAX-CUT.

Hint : Consider  $G '=(V'=V \cup\{w_i|i\in [1,|V|]\},E'=E\cup\{(w_i,v)|v \in V , i\in [1,|V|]\})$ and $k'=|V|^2+k $

Consider a partition of V' in 3 parts, call $P $ the one with the smallest number of nodes in  $V $.

Note that by putting a w in P , if it were not in it, you increase the number of edges in your 3cut.

Then, note that if all the ws are in the same part, then removing a node of V from that part increases the number of edges in your 3cut.


What is the difference between a simulator, emulator, and cross compiler? As far as I understand, cross compilers, emulators, and simulators are all ways that one computer system to be able to behave like or run another computer system.
What is the difference between these concepts? Are some of them equivalent?

Cross-development environment involve

a host computer (such as a PC) that runs the development tools,

a target computer (such as an embedded processor) that is where the code will eventually run.

A cross-compiler* generates the code that the target can understand, though compilation takes place on the host. The compiled code is sent to the target for execution.
An emulator is an ad-hoc piece of hardware that is able to mimic the behavior of the target, but is better suited for evaluation and testing.
A simulator is a software running on the host and able to mimic the behavior of the target without a physical target being present. Even though it runs on the host, it is able to execute the cross-compiled code.
A typical development scheme goes as follows:

cross-compile and debug with a simulator to obtain the correct functional behavior,

then cross-compile and debug with an emulator to check real-time performance and possibly interaction with real peripherals,

finalize the product on the real target.

*A compiler that compiles for the platform it runs on is called native.


Proving recursion depth of merge sort Hello I want to prove the recursion depth of merge sort, which is $O(\log(n))$.
I think I can prove this by recurrence equation and the master theorem:
$T(N)=2 T(n/2)+O(N) $ however i need to get $O(\log(n)) $. Basically I want only to calculate the complexity of the deviding and remove the conquer part from this equation. How can I do this? Or is there another way to prove the height of the recursion tree?

In the picture below you can see I want to prove the height from red to gray.

First of all, let me correct the recursion for the running time of merge sort:
$$
T(n) = \begin{cases} T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + \Theta(n) & \text{if } n > 1, \\ \Theta(1) & \text{if } n = 1. \end{cases}
$$
The corresponding recursion for depth is:
$$
D(n) = \begin{cases} \max(D(\lfloor n/2 \rfloor), D(\lceil n/2 \rceil)) + 1 & \text{if } n > 1, \\ 0 & \text{if } n = 1. \end{cases}
$$
(The value of $D(1)$ could also be $1$, depending on how you define depth.)

The solution of this recurrence is $D(n) =\lceil \log_2 n \rceil$.

When $n$ is a power of 2, you can calculate the depth of the recursion tree by noticing that the value of $n$ decreases by a factor of 2 at each level. For the general case, the main observation is that the depth is monotone in $n$, using which you can easily conclude $D(n) \leq \lceil \log_2 n \rceil$ by considering the smallest power of 2 which is at least $n$.


Are supersets of non-regular languages also non-regular? I have to proof that if $L_1 \subset L_2$ and $L_1$ is not regular then $L_2$ it not regular. This is my proof. Is it valid?

Since $L_1$ is not regular, there does not exists a finite automata $M_1$ such that $L_1$ is the language of $M_1$. Pick $x\in L_1$. So $x \in L_2$ and suppose that $L_2$ is regular. Then there exists a finite automata $M_2$ such that $L_2$ is the language of $M_2$. Since $x \in L_2$ and $L_2$ is regular, there exists a state $s\in S$ such that from the initial state in $M_2$ there is a path $x$ to this final state $s$. Since this holds for all $x \in L_1$, we can construct a finite automata which language is $L_1$, so $L_1$ is regular, so we reached a contradiction, so $L_2$ is not regular.

Can this be done easier?

Since this holds for all $x\in L_1$, we can construct a finite automata which language is $L_1$.

And how would you do this? You have an infinite amount of paths in hands which you have to mold into a finite set of states and edges.

In fact, the statement does not hold.

   Remember that $\Sigma^*$ is regular but there are non-regular languages.


Definition of InLeft and InRight So in reading I have come across the terms "InLeft" and "InRight" and I am unable to find a concrete definition for it.

I have found it used in the specification for COQ, and in some notes on compilers (there it was refered to as INL and INR).

As far as I am able to ascertain it is to do with making a difference between two options. However the seems like a weird nomenclature for something so simple.

The page you reference for Coq defines inLeft and inRight as constructors of the inductive type sumor. The names themselves come from "left/right injection", as in the left/right injection into a sum type. Other names commonly used are inl/inr, Left/Right, $\iota_0$/$\iota_1$, and variations on these (e.g. that Coq file also defines left/right in the definition of sumbool). It also defines inl/inr as the constructors of the general sum type. sum, sumor, and sumbool are minor, technical variations of each other.

Which terms are used depends on the author, but they are most commonly used for injections into a sum type, particularly in a type theory/category theory context. Of course, an author is always free to use them for something else if they provide a definition.


How do neural networks learn concepts? I've been learning neural networks and some back propagation stuff, and I heard about google's Tensorflow and how it could learn things like how to carry on conversations. It got me thinking about how someone could give a computer data so that it could learn how to do that. So I was trying to figure out how you could teach a computer something like how to round a number to the nearest ten if a neural network can only output a number between 0 and 1. My question is how does someone teach a neural network concepts such as rounding a number to the nearest ten. For example how would you give a neural network data so that it could solve...

  What is 47 to the nearest 10?

The answer is obviously 50. Another example also having to do with math is teaching a computer the concept of PEMDAS (Order of operations).

The answer I am looking for would be basically the steps for training neural networks to understand for example how to round numbers to the nearest ten.

Computers don't learn - they compute.  They are given a set of instructions and generally follow those instructions to the letter, with the occasional blue screen of death.

The computer uses an algorithm that is developed to solve a particular problem.  The algorithm will iterate on a problem using the criteria and input data it is given.  As the algorithm progresses it's internal state is modified in some way, which you could say it is "learning", based on however it is processing of the data.

So in the case of learning how to do basic math - the network would have to be given the input of the numbers and operations, it would need to be "trained" on how to use them, and then given data to operate on.

The problem with that is... computers are really, really good at doing basic math - it's pretty much what they are designed for doing, but they are not good a "learning" things, because deep down they are just build to move the ones and zeros around really fast.

What could be more useful is to train the network to try and understand if a question is a math question or not, e.g "what is one plus one" vs "is that a banana over there", and/or do natural language processing on it to determine the logic of the problem, resolved as a trivial problem for a computer "1+1=?".

i.e. the actual math itself is the easy bit for the computer - processing understanding how you are phrasing a question is what the network would need to do.

And the answer of course is 42.


Computation Complexity books for a mathematician I recently attented to some computational complexity talks (or complexity theory, I am not sure which is the correct name) and I fell in love with it. I would like to find some books, online courses... in general resources of any kind to self-study this (securely) wonderfull subject.
My backgrund is pure mathematics with emphasys in discrete mathematics (graph theorey, crypto, coding thoery, combinatorics...), with no background in computer science. I am not sure if the last one is mandatory.

Michael Sipser's text book Introduction to the Theory of
Computation
is a classic introduction to computation theory, and gives an
introduction to complexity theory in the end.
I don't know how to answer the question better than just providing the
table of contents of the book.
PART 1: AUTOMATA AND LANGUAGES.
1. Regular Languages.
2. Context-Free Languages.

PART 2: COMPUTABILITY THEORY.
3. The Church-Turing Thesis.
4. Decidability.
5. Reducibility.
6. Advanced Topics in Computability Theory.

PART 3: COMPLEXITY THEORY.
7. Time Complexity.
8. Space Complexity.
9. Intractability.
10. Advanced Topics in Complexity Theory.


How do I measure the reliability of a confidence value in a predictive algorithm? Supposing I have some algorithm that is able to provide me with a confidence value for some event occurring. Let's say on day 1 it tells me that there is a 80% chance it will rain, on day 2 it tells me there is a 20% chance that the mail will be late, and on day 3 it tells me that there's a 90% chance my milk will go off.

3 days later, I measure what actually happened and come up with this result:

Confidence  Occurrence
80.000%         false
20.000%         false
90.000%         true

In other words, it did not rain on day 1, the mail was not late on day 2, and my milk did go off on day 3.

Supposing that the data set is large, but that the confidence values remain distributed and not confined to any particular range, how do I go about measuring the "reliability" of my algorithm, and what metrics could I use?

Note that the floating-point precision of the confidence value is high (say a 8-byte double). I know I could simply divide each confidence up and measure the samples in "buckets", but this would reduce the reliability of the result as it would require me to trade off between reducing the sample set for each range or accepting a larger error in the form of a broader test range. I want to use all of the information to get an accurate a result as possible.

Measuring probability given a single occurrence doesn't really make sense, because the only data that can fit such a sample is 100% or 0%. If you have many samples, that is, if you have some sample distribution, then you can do some measuring.

For example, you could take the KL-Divergence as a measure (although it's not symmetric).

Once you have a certain reliability measure on your algorithm, you can update this data every time you have an additional sample, in an on-line manner.

If you have more details regarding the specific algorithm, or the specific type of predictions, you can probably tailor something that suits better your scenario.


Given a Turing Machine $M$, if I know $L(M)$ is finite, can I solve the halting problem? Say I'm given an oracle that tells me whether or not $L(M)$, the set of words accepted by a Turing Machine $M$, is finite.
By leveraging this oracle, can I solve the halting problem? That is, on an arbitrary input $<M, x>$, can I tell if M is going to halt on $x$ or will it loop forever?
My intuition says no because I don't see a  way to leverage the oracle.
For example, even with a stronger oracle that tells me if $x \in L(M)$, I still don't know, for inputs $x \notin L(M)$, how $M$ is going to behave. It could either reject (and halt), or loop forever.
Hence, I can't seem to solve the problem even with a stronger oracle that computes $L(M)$ explicitly in case it's finite. So, I believe merely knowing $L(M)$ is finite or not doesn't lead to a solution for the  halting problem.
Is my reasoning correct, or am I overlooking something here?

Yes, with such a powerful oracle, the halting problem can be solved.
To be clearer, given an arbitrary Turing machine, the oracle will tell the set of words accepted by that Turing machine is finite or not.
Suppose we are given a Turing machine $M$ and an input $x$. Let us construct Turing machine $M'$ such that on all inputs, $M'$ will simulate $M$ running with input $x$. Furthermore, when the simulation of $M$ halts (because $M$ halts on $x$), $M'$ will accept, regardless of whether $M$ accepts or rejects.
Note that $M'$ either always accepts or always runs forever. Now let us apply the oracle to $M'$.

If the oracle says $L(M')$ is not finite, it implies $M'$ always accepts. That means $M$ halts on $x$.

If the oracle says $L(M')$ is finite, it implies $M'$ always runs forever. That means $M$ on $x$ runs forever.

So, we have solved the halting problem on $(M,x)$, thanks to the oracle.

Here is a similar question, which might be the question intended by the OP as well.
Suppose (without any oracle) we are given an arbitrary Turing machine $M$ that accepts only finitely many words and an arbitrary word $x$, can we decide whether $M$ will halt on $x$?
The answer is no.
Otherwise, we can solve the original halting problem in the following way, which is known to be impossible.
For a pair of Turing machine and input $(M,x)$, we construct Turing machine $M'$, which checks if its input is $x$. If yes, it will run as $M$; otherwise, it will loop forever. Since $M'$ accepts at most 1 word, our assumption says that we can decide whether $M'$ on $x$ will halt or not. But that is exactly the same as whether $M$ halts on $x$ or not.


Algebra for min/max bounds I am trying to model some set operations which are only well-defined if one is a subset of the other. The way the sets are constructed, I'll have a series of constraints of the form $x \subseteq y$, including the two sets in question and some other ones too. I won't know anything about individual element membership, so need to operate at the set level, and would like to be able to determine whether $a \subseteq b$ is implied by the given constraints.

This sounds like the sort of thing that's been studied before (e.g., for SMT solvers or linear programming), but I can't seem to hit the right keywords to search on. Are there known efficient representations/algorithms for this sort of problem?

Here's what I've roughly thought of doing:

type Set = Symbol;
type Bound = {kind: 'upper' | 'lower', arg: Set};
type Constraint = {kind: 'lt' | 'gt', arg: Bound};

const max = (b1: Bound, b2: Bound): Bound => ...;
const min = (b1: Bound, b2: Bound): Bound => ...;
const checker = (a: Constraint, b: Constraint): bool => ...;

My idea would be to build two Constraints, one for $a$ and one for $b$. $a$ would have a lt constraint and $b$ would have a gt constraint. I suspect Bound forms an algebra with max and min, which would allow me to put two Bounds in quasi-canonical form and break things down that way.

I'm not certain this will work, so before I spend several hours fleshing this out figured I'd ask if this had been solved before!

After posting the above I realized there was a possible solution with a different model. By viewing sets as nodes in a directed graph and edges as constraints, where $x \subseteq y$ would be translated to x -> y, the final checker would simply look for a path between $a$ and $b$ in this graph. (Using DFS or BFS per this SO question).


Showing that 3-colorable is NP-complete Just as a background, 3-colorable problem is as follows: Given a graph $G = (V, E)$, is it possible to color the vertices using just 3 colors such that no neighboring vertices have the same color?

I'm aware we can show that 3-colorable is an NP-complete problem by reducing 3-SAT to it. But I'm wondering is it possible to reduce clique to it?

I know for example that if a graph with n vertices contains a subgraph which is a clique of size k, then you need at least k colors (that is, the chromatic number is at least k).

So could we say that if a graph contains a clique of size 4, then it is not 3-colorable, and vice versa?

Edit: Hmm..upon further thought, maybe the reduction wouldn't work because in order to reduce clique, you can't fix ahead of time that you're looking for a clique of size 4? The size of the clique would be arbitrary..

No, you couldn't say that, because it's not true.

A helpful method is to prove all your claims.  Don't just guess -- try to find a proof.  If you're struggling to find a proof, the first thing to check is whether maybe the thing you're trying to prove is false, so look for a counterexample.  In this case you should easily be able to find a counterexample to your claim.  Alternatively, if you can't find a proof and can't find a counterexample, look for a different approach or a different way to solve the problem that uses only facts you do know how to prove correct.


What goes wrong with sums of Landau terms? I wrote

$\qquad \displaystyle \sum\limits_{i=1}^n \frac{1}{i} = \sum\limits_{i=1}^n \cal{O}(1) = \cal{O}(n)$

but my friend says this is wrong. From the TCS cheat sheet I know that the sum is also called $H_n$ which has logarithmic growth in $n$. So my bound is not very sharp, but is sufficient for the analysis I needed it for.

What did I do wrong?

Edit:
My friend says that with the same reasoning, we can prove that

$\qquad \displaystyle \sum\limits_{i=1}^n i = \sum\limits_{i=1}^n \cal{O}(1) = \cal{O}(n)$

Now this is obviously wrong! What is going on here?

What you are doing is a very convenient abuse of notation.

Some pedants will say that what you write is nonsense, as $\mathcal{O}(f)$ denotes a set and you cannot do arithmetic operations on them the way you are doing.

But it is a good idea to ignore those pedants and assume that $\mathcal{O}(f)$ stands for some member of the set.
So when we say $f(n) = g(n) + \mathcal{O}(n)$, what we really mean if that $f(n) - g(n) \in \mathcal{O}(n)$.
(Note: some pedants might shudder at this statement too, claiming that $f(n)$ is a number and $f$ is the function!)

This makes it very convenient to write expressions like

$$ n \le \sum_{k=1}^n k^{1/k} \le n + \mathcal{O}(n^{1/3})$$

What this means is that there is some $f \in \mathcal{O}(n^{1/3})$ such that

$$ n \le \sum_{k=1}^n k^{1/k} \le n + f(n)$$

In your case of

$$\sum_{k=1}^{n} \frac{1}{k} = \sum_{k=1}^{n} \mathcal{O}(1) = \mathcal{O}(n)$$

you are abusing it even further and you need to be careful.

There are two possible interpretations here: Does the $\mathcal{O}(1)$ refer to a function of $n$, or a function of $k$?

I believe the right interpretation is to interpret it as a function of $k$.

If you try thinking of it as a function of $n$, thought not incorrect, it might lead to potential fallacies, like thinking $k$ is $\mathcal{O}(1)$ and trying to write $\sum_{k=1}^{n} k  = \sum_{k=1}^{n} \mathcal{O}(1)$

If you try thinking of it as a function of $k$, then it is true that, if $f = \mathcal{O}(g)$ (as the argument goes to $\infty$) and $g$ is never $0$,  that

$$ S(n) = \sum_{k=1}^{n} f(k) = \sum_{k=1}^{n} \mathcal{O}(g(k)) =  \mathcal{O}(\sum_{k=1}^{n} |g(k)|)$$

Note that in the middle, we have used the convenient abuse of notation $\mathcal{O}(g(k))$ to mean that for some function $h \in \mathcal{O}(g)$ the sum is $\sum_{k=1}^{n} h(k)$. Note that the final function inside the $\mathcal{O}$ refers to a function of $n$. The proof is not that difficult, but you have to cater to the fact that you are dealing with an asymptotic upper bound (i.e. for sufficiently large arguments), but the sum starts right at $1$.

If you try thinking of it as a function of $n$, then it is also true that if $f = \mathcal{O}(g)$ (as the argument goes to $\infty$) then

$$ S(n) = \sum_{k=1}^{n} f(k) = \sum_{k=1}^{n} \mathcal{O}(g(n)) = \mathcal{O}(n g(n))$$

So your proof is essentially correct, in either interpretation.