What are the advantages of using PRNG over TRNG? True random number generators use an unpredictable physical means to generate numbers, whereas pseudo-random numbers utilize mathematical formulas to produce a certain sequence of numbers that will appear random. I know that for PRNGs the efficiency is very high because they tend to generate a large quantity of random numbers in a short amount of time. Beside reproducibility  and efficiency, what are the advantages of using PRNG over TRNG?

It's an apples and oranges comparison.
When you want something to be truly random, you must use a TRNG. Examples include a lottery, or a secret/private key in cryptography.
When you want something repeatable, you must use a PRNG. An example is a large secret keystream for XOR encryption, generated (imperatively: identically) on both the transmit and receive side from a short common shared secret key.

What are the advantages of using PRNG over TRNG?

PRNGs can be portable to different computers and languages. Their implementations are easy to validate. They have a mathematical security definition, and it's easy to make fast PRNGs that experimentally match it (on the other hand, we don't know how to prove that).
TRNGs are not portable (they are not entirely software anyway), and are much more complex (typically there's a hardware source, tests ofthat at power-up and in use, and a conditioning stage). It's hard to convince a neutral party that a TRNG works.
In practice, the best choice is almost always a Cryptographically Strong PRNG, seeded by a public constant when one wants repeatability, or seeded by the output of a TRNG (or a secret constant changed manually as needed, perhaps combined with a counter, or time from a truly strictly increasing reference) otherwise. The CSPRNG will mask any small imperfection of the TRNG there will be, and have a high throughput: modern CSPRNG are extremely fast (in the order of 10 CPU cycles per byte generated for Salsa20, which supports "skip-ahead").


How many tapes would Turing Machine require to find the sum of 2 integers (expressed in base2)? Suppose I wished to devise an algorithm (to be run on a turing machine) which could find the sum of 2 integers (expressed in base2). How many tapes would this require?

My intuition tells me that 4 tapes would be required: 1 for each of the two numbers being added together, 1 to store the 'carry over' value, and 1 to store the output.

Is this correct? Could it be done with fewer tapes?

Anything that can be computed with any reasonable extension of a Turing machine can be computed with the standard Turing machine that has a single one-way infinite tape.

For example, you can simulate a four-tape machine by interleaving the characters of the tapes so that, e.g., the four tapes

$$\begin{array}{cccc}
    a_1 & a_2 & a_3 & \cdots\\
    b_1 & b_2 & b_3 & \cdots\\
    c_1 & c_2 & c_3 & \cdots\\
    d_1 & d_2 & d_3 & \cdots
\end{array}$$

with the single tape
$$a_1\ b_1\ c_1\ d_1\ a_2\ b_2\ c_2\ d_2\ a_3\ b_3\ c_3\ d_3\ \cdots$$


Selective Background Updating in Running Gaussian Average Method for Background Subtraction I am studying the Running Gaussian Average Method for background subtraction. One alternative, as described in Wikipedia, also known as Selective Background Updating, is to only update the distribution of background pixels.

I have two questions on this topic:

(1) To determine whether a pixel is foreground or background, we need to calculate ${\mu}_t$ as follows:
$${\mu}_t = M{\mu}_{t-1} + (1-M)(I_t{\rho}+(1-{\rho}){\mu}_{t-1})$$

But the $M$ in this formula depends on whether the pixel is foreground (in this case, $M=1$) or background (in this case, $M=0$). So it becomes a circular dependence. Currently I tried to solve this by calculating:
$$(I_t{\rho}+(1-{\rho}){\mu}_{t-1})$$

Then after deciding the pixel is foreground or background, I determine $M$ and use the first formula to update the value of ${\mu}_t$. Is this correct?

(2) The Wikipedia page only suggests to update the mean of each background pixel using the first formula above. Shall we update the variance as well, like as follows?
$${\sigma_t}^2 = M{\sigma^2_{t-1}} + (1-M)(d^2{\rho}+(1-{\rho}){\sigma^2_{t-1}})$$

1) You start with first frame of video. Gather several frames to calculate accumulators, denote everything like background - at first frame you do not know which is which. Yes, recalculate.

2) Yes we shall update variance.

Never used unmodifief version: remember to use illumination infependent color space. Think about taking running variance on your own.


Modeling a sequential circuit as a transition system I was asked to model the following sequential circuits C1, C2 as transition systems (i.e. identify the output y function and register functions r1, r2, r3)

For C2 there appears to be not input x and only output y with a register R3. I assumed that there would be two possible states R3 = 0, R3 = 1 and then Y2 = !R3. But then what is the register function for R3?

For C1 I really had no idea how approach the problem as it was just an intimidating maze and while I thought it may be possible to break the circuit up and try find the functions that way, I wasn't sure.
I would like to know how I can find the output and register functions of these circuits

To build a transition system from a sequential circuit, in general, one needs to define three components:

the states of the transition system, which are all possible combinations of
values of your inputs and registers in the circuit
transitions between states in the transition system, which result from the functions that determine the output and the registers (according to used logical circuits and wire connections)
labels for states in the transition system, which consist of all variables and registers that are evaluated true given the valuations in the circuit

As per the (contrived) circuit in C2, the states reflect only the possible values of the single register. In turn, the function of the output equals to the register (Y2=R3), while the current value of the register is the negation of its previous value. This should give you enough insights to build the transition system.

The circuit given in C1 is indeed more convoluted, but it can be decomposed into functions on how values (for the registers and the output Y1) change, which then can be used to derive possible transitions in the system. (This is done with respect to possible changes of the input X.) For example, Y1 = R1 && R2 and the form for the value of R1 is R1 = (X AND ...) OR (... AND ...), while the missing values ... can be traced down according to the wire connections of the circuit.

More details on modelling sequential circuits as transition systems can be found in [1].

[1] Baier, Christel, Joost-Pieter Katoen, and Kim Guldstrand Larsen. Principles of model checking. MIT press, 2008.


How many recursive calls are made by this gcd function? In the following function, let $n \geq m$.

int gcd(n,m)
{
 if (n % m == 0) return m;
 n = n % m;
 return gcd(m, n);
}

How many recursive calls are made by this function?

$\Theta (\log_2 n)$
$\Omega (n)$
$\Theta (\log_2(\log_2 n))$
$\Theta ( \sqrt{n} )$

I think the answer is $\Theta (\log_2(\log_2n))$, but my book is saying $\Theta (\log_2 n)$.

My reasoning is as follows. Here we are not dividing the number. If there was a division then it would be $\log n$. But here operation is $\bmod$. So we will get a very small number after the first call. So it must be $\log \log n$. Am I thinking correctly?

Hint: on input $F_{n+1},F_n$, gcd makes a recursive call with inputs $F_n,F_{n-1}$. Now use the asymptotic formula $F_n = \phi^n + \Theta(1)$, where $\phi = (1+\sqrt{5})/2 > 1$.

Also, while we're at it, $\Theta(\log_2 n) = \Theta(\log n)$, and similarly $O(\log_2 n) = O(\log n)$ (and the same fore $\log\log n$); try to figure out why (here the base of $\log n$ can be arbitrary, but for definiteness you can choose base $e$).


Possible combinations of soccer results I'm trying to calculate the best and worst position for each team in the ranking based on the weekly matches.

Suppose we have 4 teams with these position:

Pos.| Name   | Pts.

1  | Team A | 12

2  | Team B | 10

3  | Team C |  8

4  | Team D |  6

And during the week there are 2 matches A vs C and B vs D

If you don't know, in soccer you can win, lose or draw. A win are 3 points, draw 1 points each, lose 0 points.

In this scenario we have 9 possible combinatiosn [3^(number of matches)].

What I want to do is calculate the best and worst position each team can get based on all combination.

Of course is fairly simple to do with 4 teams (2 matches), but in real case scenario we would have about 10 matches (59000 combinations).

I guess the best way to approach the problem is to use recursion but I can't get to a real starting point.

Any help?

Here's an alternative to recursion:

You have 3 different outcomes. You can assign each outcome to a digit in $[0, 1, 2]$. E.g. 0 means loosing, 1 means draw, 2 means win.

Then you can represent one combination as a series of digits, e.g. $[1, 1, 2, 0, ...]$ (first two matches ended in a draw, the third one was won, ...).
And you can interprete this series as the digits of a number in base 3.

So obviously all combinations can be described using a number between $0$ and $3^{\#matches}-1$ and you can very easily iterate over them:

for combination in 0 .. 3^(#matches)-1:
    results = combination in base 3 (exactly #matches digits)
    process results


Steiner tree problem in graphs of diameter 3 I have an unweighted undirected graph $G(V, E)$ of diameter 3 and a subset $T\subseteq V$ of these vertices. I want to find the minimum tree $(V', E')$ that contains all vertices in $T$, minimizing the number of nodes $|V'|$.

Is it true that $|V'|\le 2|T|$? If $G$ is of diameter 2 it is easy to prove that this is true. Also for diameter 4, it is not true always since we can take a path graph of 5 vertices with $T$ as two leaves.

This is an interesting question.

It is not true that $|V'|$ is always less than or equal to $2|T|$. Here is the smallest example of $G$ and $T$ where $|V'|$ must be greater than $2|T|$.

Graph $G$ as depicted above has 9 vertices $A,A_1,A_2,B,B_1,B_2,C,C_1,C_2$ and 12 edges $AA_1, A_1A_2, A_2A,$ $BB_1,B_1B_2,B_2B,$ $CC_1, C_1C_2, C_2C,$ $A_1B_2, B_1C_2, C_2A_1$. It is easy to check the diameter of $G$ is 3.

Let $T=\{A,B,C\}$. Suppose $T'=(V',E')$ is a minimal tree in $G$ that spanns $T$.

If $V'$ contains all 9 vertices, then $|V'|=9$.
Otherwise, WLOG, assume $V'$ does not contain $A_1$. If anyone of $A_2$, $C_1$, $C_2$ and $B_1$ is not in $T'$, then $A$ and $B$ will not be connected in $T'$. Since $A$ and $B$ are connected in $T'$, all of those 4 vertices must be in $T'$. So $|V'|\ge3+4=7$.

So $|T'|\gt 6= 2|T|.$

Exercise 1. Verify that the following two graphs are also examples where $|V'|$ must be greater than $2|T|$ with $T=\{A, B, C\}$

Exercise 2. (less than 1 minute) If $|T|=3$, then $|V'|\le7$.

Exercise 3. Let $n\ge3$. Construct $G$ and $T$ such that $G$ is connected of diameter 3, $|T|=n$ and $|V'|\gt 2|T|$. (Hint, imitate the simpler example in exercise 2.)


range / interval query algorithm I've an hash (base 32 for what it's worth):

hash = 'ab352eghjhngd4'

And I've subscribers that want to listen to new hashes in a range.

   listener = { startAt: 'ab31', endAt: 'ab40', obj }
   listener2 = { startAt: 'ab350', endAt: 'ab351', obj }

In this case listener1 should be notified of the new hash while listener2 shouldn't.

I'd like to find another algorithm than just iterating through all listeners to find if they fit.

I was thinking of holding an array for startAt

startAtOrderedArray = [
       { startAt: 'ab31', endAt: 'ab40', obj },
       { startAt: 'ab350', endAt: 'ab351', obj },
       { startAt: 'uc', endAt: 'uc2', obj }
    ]

Then using binary search I can forget the third item because it's above the hash which was ab352eghjhngd4.

Then I can do the same with endAt.

endAtOrderedArray = [
       { startAt: 'uc', endAt: 'uc2', obj },
       { startAt: 'ab31', endAt: 'ab40', obj },
       { startAt: 'ab350', endAt: 'ab351', obj },
    ]

So I end up with:

 before = [
           { startAt: 'ab31', endAt: 'ab40', obj },
           { startAt: 'ab350', endAt: 'ab351', obj },
        ]

 after = [
           { startAt: 'uc', endAt: 'uc2', obj },
           { startAt: 'ab31', endAt: 'ab40', obj },
        ]

So now if an item is in both array then it's interested in the hash.

The issue however is the complexity is still linear so I'm wondering how can I do better ?

I'd like the question to be as general as possible but for my specific use case it is likely that the first char of startAt and endAt are the same. So { startAt: 'ab', endAt: 'u23' } is not likely.

Use an interval tree.  It is designed to support exactly this. In particular, the query "find all ranges that contain this value" is known as a stabbing query, and it can be answered in essentially $O(\log n)$ time.


Pseudo random, unqiue integer numbers in a given range I need an algorithm that gives me integer numbers with the following features:

Numbers must be in a given range $[n..m]$;
Numbers must be returned in pseudo-random order (random at visual inspection is enough; it is more important that numbers are well distributed over the given range);
Numbers may not repeat before each number in the range $[n..m]$ has been returned once;
Range may be huge (up to $2^{64}$; this excludes all list/shuffle based algorithms);
It should be possible to seed the function so it returns numbers in different order on repetition;
Algorithm should be as fast as possible and should return in constant time.

I wrote code that uses table based bit swapping and optionally XOR and/or addition. It works very well for bit-aligned $n$ and $m$. However it is a bit slow and if the range $n..m$ is not aligned to bits (i.e., $n$ other than $2^x$ and $m$ other than $2^y$), I get either gaps within the returned numbers or extremely non-constant runtime behavior.

How can this be solved?

Without loss of generality, we can assume you need numbers in the range $\{0,..,n-1\}$.  (Just add the appropriate offset.)

This can be solved by constructing a random permutation $f:\{0,\dots,n-1\} \to \{0,\dots,n-1\}$, then outputting the values $f(0),f(1),f(2),f(3),\dots$ as your sequence of pseudorandom numbers.  Those numbers won't repeat until each number in the range has been defined.  If $f$ can be computed efficiently, this will be fast.

So how do we construct such a random function $f$?  One approach is to use format-preserving encryption, a technique from cryptography that allows you to construct a function $f$ that is a bijection on the set $\{0,\dots,n-1\}$ (for any $n$ of your choice), and that appears pseudorandom.  There are many FPE algorithms.

See https://blog.cryptographyengineering.com/2011/11/10/format-preserving-encryption-or-how-to/ and https://crypto.stackexchange.com/questions/tagged/format-preserving for more (e.g., https://crypto.stackexchange.com/q/41450/351, https://crypto.stackexchange.com/q/504/351, https://crypto.stackexchange.com/q/29073/351, https://crypto.stackexchange.com/q/20035/351, https://crypto.stackexchange.com/q/16561/351, https://crypto.stackexchange.com/q/18988/351).


Two-Sum - Pre-sort Optimization Algorithm Design Is it possible to optimize the runtime of a two-sum solution by receiving a pre-sorted input either in ascending or descending order?
 Original Two-Sum
Determine whether there are two items whose individual capacity will perfectly equal the total capacity while ensuring the same item cannot be selected twice.

Input: An Int representing the total capacity and an Array of Int's representing items' individual capacities.
Output: A Boolean representing whether it is possible for two of the items to equal the total capacity.
Time complexity: Linear growth, $O(n)$
Space complexity: Linear growth, $O(n)$

Samples
Input: [4, 5, 2, 6]

Total capacity: 10
Expect: true

Input: [4, 5, 2, 5]

Total capacity: 10
Expect: true

Input: [4, 5, 2, 7]

Total capacity: 10
Expect: false

Pseudocode

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

Iterate through the input Array of item capacities.
2a. Find the targetCapacity for the current item: totalCapacity - itemCapacity
2b. If searchSet contains the targetCapacity, return true.
2c. Else, add the itemCapacity to the searchSet.

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

 Pre-Sort

Save a new var lastTargetCapacity
If the current itemCapacity < lastTargetCapacity, there are no possible two-sums and return false.

i.e.
Input: [6,2,1,0]

Total capacity: 9

Iterations

targetCapacity = 9 - 6, lastTargetCapacity = 3
Return false because the itemCapacity of 2 < lastTargetCapacity of 3.

The Two Sum solution can be optimized for runtime performance given the input Array is pre-sorted in ascending or descending order.
If Binary Search is used to find the targetCapacity above, it will run in logarithmic, $O(logn)$, average runtime. This is faster than the pseudocode above that runs in linear, $O(n)$, runtime using iteration and hashing.
If sorting was not provided in the input then it would not be possible to sort and search faster than $O(n)$. The best that could be done would be $O(nlogn)$ with a strategy such as Quicksort and Binary Search.
See: Stanford - Two Sum Explanation


Beam size is a parameter in some RNNs like TensorFlow's Magenta. What is beam size? Magenta's melody_rnn_generate method includes a parameter beam_size. What is it and how does affect the melody?

Beam size, or beam width, is a parameter in the beam search algorithm which determines how many of the best partial solutions to evaluate. In an LSTM model of melody generation, for example, beam size limits the number of candidates to take as input for the decoder. A beam size of 1 is a best-first search - only the most probable candidate is chosen as input for the decoder. A beam size of $k$ will decode and evaluate the top $k$ candidates. A large beam size means a more extensive search - not only the single best candidate is evaluated.

Beam search is a heuristic search algorithm that uses breadth-first search to build its search tree and reduces the search space by eliminating candidates to reduce the memory and time requirements.1 Without the beam search, the worst time and space complexity for the best-search would be $\mathcal{O}(b^m)$ where $b$ is the branching factor and $m$ is the maximum depth. With beam search, the worst time complexity is $\mathcal{O}(kb)$ and the worst case space complexity is $\mathcal{O}(k)$2.

In the case of melody creation with Magenta, a beam size larger than the default of 1 will build a search tree for each candidate evaluation, as visible in this incomplete sketch of the graph ('h' represents an arbitrary heuristic cost):

A larger beam generally means a more accurate prediction at the expense of memory and time. In one trial using attention_rnn, for example, modifying the beam width from 1 to 4 decreased the average negative log-likelihood of sequence (melody) generation from 84.2 to 38.6.

1 - Beam search (Wikipedia)

2 - Notes on the Complexity of Search
 (MIT)


What are some constant time operations? I know that some operations are definitely constant time, such as accessing an item in a list, however there are other operations that are assumed constant time sometimes, but non-constant other times, such as multiplication.

So if we were to deal with very, very large operations, which operations would be truly constant time, or at least polynomial for exponentially large data

To answer this question properly, one needs two things: a model of computation and a notion of (time) complexity. Especially when talking about sub-linear complexity, the influence of the model of computation is extremely important. Starting from linear-time (and especially when dealing with polynomial time), it becomes mostly irrelevant and people avoid mentioning it. Consider addition for example:

Turing machine1 with classical time complexity: addition takes linear time on the size of the input because the machine has to read the inputs and that takes linear time.
Straight-line program(SLP) counting number of instructions: addition is in constant time because there is an instruction for that.
Boolean circuit with depth complexity: addition takes logarithmic time in the size of the input (using an optimized adder).

In fact Turing machines are not a very accurate model of current computers because they cannot do random accesses2 and very little can be done in constant time. This why counter machines and RAM models are more accurate, but also come with their drawbacks. Models such as SLP where addition is a constant time operation are known to be unrealistic because they can produce numbers of exponential size in the number of instructions.

When dealing with numbers, it is common to refer to "bit-complexity" and what it really means is a model that deals with bits and has random access memory. In this kind of model, addition can be done in linear time and multiplication in $O(n\log n \log\log n)$ where $n$ is the number of bits. Wikipedia has a page listing other operations.

1I am going to ignore the possible variations on the number of tapes, in this example we can consider that the two numbers are on different tapes and we have a dedicated output tape.

2Though one can argue that current computers are really only finite automata because they are finite, but this is not necessarily a useful point of view; or that computers really have logarithmic time random access in the size of the memory.


Knight's tour from all starting positions Is it true that for all $n\geq 5$, there is a knight's tour of an $n\times n$ chessboard beginning at every square?

For example, is it correct, that there is no solution for a $5\times5$ board,
with start position $(5,4)$?

The Wikipedia article links to several useful papers. According to the paper Solution of the knight’s Hamiltonian path problem on chessboards, there is no such tour; see Theorem 3.1(ii). They show that a knight's tour on the 5x5 board always starts or ends at a corner. It's also easy to see that both endpoint squares have the same color. Since the (5,4) square has a different color than the corners, no knight's tour starts at (5,4).


Algorithm to find if exists a k-length acyclic path with negative weight on an weighted undirected graph Consider the following problem:
given an undirected graph with weighted edges (positive and negative) I would like to know if there is a k-length acyclic path with negative weight.
Is there an algorithm for that with a good complexity?
Maybe I can find the lighter k-length acyclic path and check if is negative, but it could be that this approach may have a bigger complexity.
Let me know what do you think.

(Sorry for the lousy english)

If $k$ is part of the input to the algorithm (as opposed to a constant chosen ahead of time), and if "acyclic path" means a path that does not visit any vertex more than once, then this problem is already at least as hard as Hamiltonian Path, which is NP-hard: to reduce the latter to this problem, just give every edge some negative weight (e.g., -1) and set $k=n−1$.


Universal family of hash functions How to prove that a $k$-universal family of hash functions is $(k-1)$-universal family?

I tried to prove it by definition of k-universal family of hash functions but I didn't know how to use the definition.

If I prove it, Is it necessary that a $1$-universal family of hash function is universal family?

Definitions:

Let $U$ be a universe of keys, and let $H$ be a finite collection of hash functions mapping $U$ to $\{0,\dots,m-1\}$.

$H$ is universal if $\forall x,y\in U$ where $x\neq y$: $\Pr[h(x)=h(y)] \leq \frac{1}{m}$ where $h$ is chosen randomly from $H$.

$H$ is k-universal if $\forall x_1,x_2,\dots,x_k\in U$ distinct elements and $\forall i_1,i_2,\dots,i_k\in \{0,\dots,m-1\}$: $\Pr[h(x_1)=i_1 \land h(x_2)=i_2 \land \dots \land h(x_k)=i_k] = \frac{1}{m^k}$ where $h$ is chosen randomly from $H$.

For your first question, here is a hint:
$$
\Pr[h(x_1) = i_1 \land \cdots \land h(x_{k-1}) = i_{k-1}] = \\
\sum_{i_k} \Pr[h(x_1) = i_1 \land \cdots \land h(x_{k-1}) = i_{k-1} \land h(x_k) = i_k].
$$

Regarding the connection between universal and $k$-universal: Consider the family consisting of all constant functions. This family is 1-universal but not universal (for $|U|>1$).

However, it turns out that every 2-universal family is universal (exercise). The converse isn't true: for example, the family of all functions $h$ such that $h(x_1) = 0$ is universal but not 2-universal (for $m>1$).


Different topologically sorted order based on DFS vertex ordering The algorithm for topological sort, in CLRS goes as follows :

call DFS(G) to compute finishing times v.f for each vertex v
as each vertex is finished, insert it onto the front of a linked list
return the linked list of vertices

Let's we have a directed graph, as in the figure here:

If we start DFS from arbitrary vertices, we get different topological orders -- for instance, if the top level DFS loop goes through vertex b first, then d, then i and finally a, one possible ordering of finishing times (largest to smallest) is :

(a), (i), (d,h,l,k,j), (b,c,f,e,g)

where each grouped term within the parenthesis indicates one iteration of DFS from the starting vertex.

If the vertices are taken in a different order, say a first, then d, and then i, the order of finishing times becomes:

(i), (d,h,l,k,j), (a,b,c,f,e,g).

If these were to indicate valid orders of events, how can they both be valid topological orders? The sorting algorithm does not mention any specific order of vertices to use in DFS.

A topological ordering of a DAG $G$ is any ordering $v_1,\ldots,v_n$ of the vertices in which $(v_i,v_j) \in G$ implies $v_i \leq v_j$. That is, if there is an edge from $x$ to $y$, then $x$ must precede $y$ in the ordering (assuming $x \neq y$). A DAG can have many topological orderings. For example, the empty DAG on $n$ vertices has $n!$ topological orderings. In contrast, a path $v_1 \to v_2 \to \cdots \to v_n$ has a unique topological ordering.


Is every graph with minimum degree $n/2$ connected? Claim: Let $G$ be a graph on $n$ nodes, where $n$ is an even number. If every node of $G$ has degree at least $n/2$, then $G$ is connected.
Decide whether the above claim is true or false, and give a proof of either the claim or a counter example.

I drew out a few examples and the claim seems to hold, and I cannot find a counter example to prove it is false, which leads me to believe the claim is true.  However, I am having a really hard time generating a proper proof.

Suppose that $G$ is not connected. Consider the smallest connected component of $G$.

You take it from here.


How does an operating system implement the C library? I have an idea of how a C program is turned into machine code by the compiler. I also know how the processor processes the instructions (https://www.youtube.com/watch?v=cNN_tTXABUA this video has a good introduction). But what I don't understand, is how an operating system (most times written in C or some low-level language) can run programs also in C (or other low-level language). I don't understand this. Does the OS read the code and then processes it with some internal functions, or does it only open the machine code and send it to the processor, that makes the rest? In case of the second option, how the OS take care of which instructions are allowed to be executed, and which are not? (example: I may write a program that has an instruction that jumps to a forbidden part of the memory RAM, how the OS protect it from happening?)

I don't expect to understand it fully in this post's answers, but if you guys could give me an idea and then some books or tags to search, I'd be happy!

It's hard to give a full answer to this question, as it would basically amount to an introductory text in operating system design, so I will try to give some pointers.

First of all, if you really want to know (including all the gritty details) how an operating system actually works, there's probably no way around looking at an actual implementation of one. Luckily, there's xv6 providing quite a good example, see xv6 and follow the references there.

Before diving into the code, it's probably a good idea to have a look at the basic components of an operating system, see Operating System Components.

I think your question has three main aspects

How does an operating system load a (compiled) C program?
How does such a program interact with the system it runs on?
How does the operating system prevent bad things from happening and regain control once the program is running?

(Warning: The following might be oversimplifying things)

For the first question, see Loader. A compiled C program is just binary data. When loading (let us ignore some bookkeeping that is also going on around this), the operating system copies this binary data simply into memory, does some initialisation (e.g. copy arguments at places the program can find it) and then sets the instruction pointer to the start of the loaded program. Basically, from this point on the program is in control (see below). Eventually, the program (hopefully) will issue a system call, namely exit, when it is done, thus handing control back to the operating system, see Exit (system call (it might also terminate by using a simple return in main, but let us ignore that case for the moment).

This leads to the second question. The interaction with the operating system takes place via system calls. These, in turns, are implemented via interrupts. Roughly speaking, you can think of a special processor instruction being called (i.e., it's a feature of the processor), which stops the execution of the current code and starts the execution of an interrupt handler, which is part of the operating system. The interrupt handler than tries to figure out why it was called and will act accordingly. How does the processor know where to find the interrupt handler? This is part of the loading process of the operating system at boot time, see e.g. Kernel startup stage.

For the third question, see Process management:

  There are two possible ways for an OS to regain control of the
  processor during a program’s execution in order for the OS to perform
  de-allocation or allocation:

  The process issues a system call (sometimes called a software interrupt); for example, an I/O request occurs requesting to access a
  file on hard disk.
  A hardware interrupt occurs; for example, a key was pressed on the keyboard, or a timer runs out (used in pre-emptive multitasking).

The situation is slightly different on multi-core architectures, as there obviously the operating system and the loaded program can run concurrently.

For the memory related question, see Memory protection. Again, the short answer is that this is supported by processor features, i.e., the operating system can set boundaries when loading a program leading to an interrupt when these boundaries are violated. Another important feature related to this are CPU modes.

To sum things up, in order to understand operating systems, it's also important to understand computer architecture, as many features of an operating system are based in corresponding features of processors. I always found the following a good introductory textbook: "Computer Organization and Design: The Hardware/Software Interface" by David Patterson and John Hennessy.

Finally, the following (Linux-specific) example might help. The usual

#include <stdlib.h>
#include <stdio.h>

int main(void) {
    printf("Hello, world!");
    exit(0);
}

will turn into assembler code as follows (more or less..., stolen from the Wikipedia article on Netwide Assembler)

; compile on 64-bit Linux using
; nasm -f elf syscall.asm
; ld -m elf_i386 -s -o syscall syscall.o

global _start

section .text
_start:
    mov eax, 4 ; system call number 4: write
    mov ebx, 1 ; file descriptor 1: stdout
    mov ecx, msg
    mov edx, msg.len
    int  0x80  ; Passes control to interrupt vector
                   ; invokes system call, in this case system call
                   ; write(stdout, msg, strlen(msg));

    mov eax, 1 ; system call number 1: exit()
    mov ebx, 0 ; exit status 0
    int 0x80   ; Passes control to interrupt vector
               ; invokes system call, in this case system call
               ; number 1 with argument 0, i.e., exit(0)

section .data
msg:    db  "Hello, world!", 10
.len:   equ $ - msg

Once actually compiled, this will look like (just the part between the first and last column, the rest is for illustration purposes, generated using xxd programName)

0000000: 7f45 4c46 0101 0100 0000 0000 0000 0000  .ELF............
0000010: 0200 0300 0100 0000 8080 0408 3400 0000  ............4...
0000020: cc00 0000 0000 0000 3400 2000 0200 2800  ........4. ...(.
0000030: 0400 0300 0100 0000 0000 0000 0080 0408  ................
0000040: 0080 0408 a200 0000 a200 0000 0500 0000  ................
0000050: 0010 0000 0100 0000 a400 0000 a490 0408  ................
0000060: a490 0408 0e00 0000 0e00 0000 0600 0000  ................
0000070: 0010 0000 0000 0000 0000 0000 0000 0000  ................
0000080: b804 0000 00bb 0100 0000 b9a4 9004 08ba  ................
0000090: 0e00 0000 cd80 b801 0000 00bb 0000 0000  ................
00000a0: cd80 0000 4865 6c6c 6f2c 2077 6f72 6c64  ....Hello, world
00000b0: 210a 002e 7368 7374 7274 6162 002e 7465  !...shstrtab..te
00000c0: 7874 002e 6461 7461 0000 0000 0000 0000  xt..data........
00000d0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000e0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000f0: 0000 0000 0b00 0000 0100 0000 0600 0000  ................
0000100: 8080 0408 8000 0000 2200 0000 0000 0000  ........".......
0000110: 0000 0000 1000 0000 0000 0000 1100 0000  ................
0000120: 0100 0000 0300 0000 a490 0408 a400 0000  ................
0000130: 0e00 0000 0000 0000 0000 0000 0400 0000  ................
0000140: 0000 0000 0100 0000 0300 0000 0000 0000  ................
0000150: 0000 0000 b200 0000 1700 0000 0000 0000  ................
0000160: 0000 0000 0100 0000 0000 0000            ............

This is the thing (or rather, a binary representation thereof) the operating system loads into memory. We might also want to have a look at it with objdump -s -d programName which gives some more information

Contents of section .text:
 8048080 b8040000 00bb0100 0000b9a4 900408ba  ................
 8048090 0e000000 cd80b801 000000bb 00000000  ................
 80480a0 cd80                                 ..
Contents of section .data:
 80490a4 48656c6c 6f2c2077 6f726c64 210a      Hello, world!.

Disassembly of section .text:

08048080 <.text>:
8048080: b8 04 00 00 00       mov    $0x4,%eax
    8048085: bb 01 00 00 00       mov    $0x1,%ebx
804808a: b9 a4 90 04 08       mov    $0x80490a4,%ecx
    804808f: ba 0e 00 00 00       mov    $0xe,%edx
8048094: cd 80                int    $0x80
    8048096: b8 01 00 00 00       mov    $0x1,%eax
804809b: bb 00 00 00 00       mov    $0x0,%ebx
    80480a0: cd 80                int    $0x80

You see that this program has two system calls. The first one is write which outputs the "Hello, world!", the second one is the exit. These two system calls correspond to the int 0x80 in the assembler code that generates a software interrupt, see INT instruction and http://www.linfo.org/int_0x80.html Before making a system call via int 0x80 we need to tell the Linux, which system call we want (plus set up any other relevant parameters). System calls are identified by numbers, e.g. 1 is exit, 4 is write, see http://syscalls.kernelgrok.com/

Again, to sum this part up: System calls are translated into int 0x80 instructions (plus necessary parameter handling before that). Once the program runs and hits an int 0x80 instruction, the processor will give control to the operating systems interrupt handler which sees that it has to handle a system call and then does things accordingly.


Manber's graph-partitioning implementation I'm having trouble understanding a part of Manber's graph-partitioning algorithm, presented in A Text Compression Scheme that Allows Fast Searching Directly in the Compressed File.

Generally speaking he wants to divide vertices of a weighted, directed graph $G=(V,E)$ into two sets $V_1$ and $V_2$ in such a way, that the sum of the weights of the edges that go from $V_1$ to $V_2$ is maximized.

He states that since this is a NP-problem he chose to first partition the graph randomly and then examine each vertex to see if switching this vertex to the opposite set would improve the total. This whole process is repeated several times for several random initial partitions to see which one of them yields the best results.

The following pseudocode is provided:

Best_Non_Overlapping_Pairs(G: weighted graph)
    repeat k times { k is a constant; we used 100 }
       randomly assign each vertex to either V1 or V2 with equal probability;
       for each vertex v in V do
          put v on the queue;
       loop until the queue is empty
          pop v from the queue;
          if switching v to the opposite set improves the sum of weights then
             switch v;
          if switching v caused other vertices, not already on the queue, to
          prefer to switch then put them on the queue;
       store the best solution to date;

I'm not sure what I'm supposed to code for the bolded part. How do I check for the "preference" of non queues vertices? Is it even needed? I've implemented the algorithm without this part and it seems working as intended.

How do I check for the "preference" of non queues vertices?

The previous step was

          if switching v to the opposite set improves the sum of weights then
             switch v;

so clearly you already know how to check for the preference of a vertex. Whether or not it is in the queue is immaterial.

To do it efficiently requires some additional data storage and pre-calculation which is not explicitly described in the pseudocode. In more detail,

Best_Non_Overlapping_Pairs(G: weighted graph)
    repeat k times
       randomly assign each vertex to either V1 or V2 with equal probability;

       initialise two arrays of edge weight sums, internalSums and externalSums
       for each edge e = (s, t) in E do
          if s and t are in the same partition
             increment internalSums[s] and internalSums[t] by weight(e)
          else
             increment externalSums[s] and externalSums[t] by weight(e)

       for each vertex v in V do
          put v on the queue;
       loop until the queue is empty
          pop v from the queue;
          if internalSums[v] > externalSums[v]
             switch v;
             swap internalSums[v] and externalSums[v]
             for each edge e = (v, u) in E do
                update internalSums[u] and externalSums[u] appropriately
                if u is not in the queue and internalSums[u] > externalSums[u]
                   enqueue u
       store the best solution to date;

  Is it even needed? I've implemented the algorithm without this part and it seems working as intended.

I must confess that I would be unable to distinguish easily between the algorithm working as intended and the algorithm selecting a purely random partition and skipping the rest of the process.


Proving that max flows of undirected graph and equivalent directed graph are equal There is an undirected graph $G$. A graph $H$ is constructed by changing each edge $(a,b)$ in $G$ to a pair of directed edges $(a,b)$ and $(b,a)$. How to prove that the maximum flow in $H$ is equal to the maximum flow in $G$?

I don't really have any idea how to start it. I just know that I can use Ford-Fulkerson on $H$ and update the reverse edge such that $f(a,b)+f(b,a)=c(a,b)$ but that's it.

If $f_G$ is a valid flow for $G$, then there exists a valid flow $f_H$ for $H$ such that $|f_G| = |f_H|$.  This is true since there is always a flow $f'_G$ for $G$ such that $|f'_G| = |f_G|$ and no edge is traversed in both directions in a flow decomposition of $f'_G$. If some edge $(u,v)$ is traversed by $x$ units of flow from $u$ to $v$ and $y \le x$ units of flow from $v$ to $u$ then you could redefine the flow to only send $x-y$ units of flow from $u$ to $v$. If $(u,v)$ is used from $u$ to $v$ you can then define $f_H(u,v) = f'_G(u,v)$  and $f_H(v,u)=0$. (If $(u,v)$ is unused then $f_H(u,v) = f_H(v,u) = 0$).

If $f_H$ is a valid flow for $H$, then there exists a valid flow $f_G$ for $G$ such that $|f_H| = |f_G|$.
Notice that if $f_H$ uses both $(u,v)$ and $(v,u)$ (assume w.l.o.g., that $f_H(u,v) \ge f_H(v,u)$) then the flow $f'_H$ defined by $f'_H(u,v) = f_H(u,v) - f_H(v,u)$, $f'_H(v,u)=0$, and $f'_H(x,y) = f_H(x,y)$ for $(x,y) \not\in \{ (u,v), (v,u) \}$ is also a valid flow for $H$ and $|f'_H| = |f_H|$. This shows that you can define $f_G(u,v) = f'_H(u,v)$.


Looking for a dictionary of math/CS notation There is an at-times dizzying array of symbols used in math and CS papers. Yet many assume basic familiarity that seems rarely taught in one place. I am looking for a dictionary something like the following, especially from a CS perspective.

It would list all the basic mathematical symbols and give their meanings and examples. It would talk about symbols that are sometimes used in equivalent ways. It would note common beginner mistakes.
It would talk about the subtleties surrounding different meanings of a single symbol (much like multiple definitions of the same word in a dictionary).
It would not merely be a very terse description of each symbol, such as one word descriptions like "subset".
It would show how symbols are sometimes "overloaded". For example, $\binom{x}{y}$ could have $z$ as an integer, but sometimes $z$ can be a set with this notation and it means to choose elements from this set. $[n]$ sometimes means a set of integers $1 \ldots n$, or other times its a one-element array.
It might talk about how to describe all kinds of different "objects" in terms of different symbols or equivalent ways of referring to them (but which are more clear) and the operations possible on those objects. In other words, kind of like an API for math objects.

I.e. it would be also at times a "style manual" for different nuances in how to present mathematical writing. This would be a very helpful resource for anyone writing questions in mathematical stackexchanges, where many questions fail to make sense based on not fitting into tricky mathematical conventions.

Some book introductions have many of these features. however ideally it would be a separate treatment. Also, ideally of course it would be online. There are tables of latex symbols, but they don't really fulfill many of the above criteria.

  Has anyone seen a "dictionary of symbols" that matches these features?

(Alternatively, it seems like an excellent wiki or FAQ project if good references like this don't exist.)

You can use this sheet. It has a lot of handy formulas and some definitions.

You can also use Wikipedia's list of mathematical symbols propsed by Kyle Jones in comments.

There is also Worfram MathWorld which is a great resource, but you need to know what are you looking for.

When it comes to printed resources, each volume of The Art of Computer Programming has a great reference of mathematical notations, especially volume 1.


How are lookup tables described from the perspective of complexity theory? Lookup tables can convert a piece of computational time into space. I remember that it was a part of a complexity theory course, but I cannot recall how it's called in its terms. I know how to use lookup tables in code to increase performance of my applications, so I don't need a definition of it in common sense.

I want to know a formal definition of an approach like lookup tables in complexity theory.

Lookup tables take a key, and either provide a value according to the key or tell you that there is no value under this key.

Time and space requirements will depend on the implementation. It's usually not further mentioned if it is obvious what kind of implementation a reasonable person would use.


Is there an algorithm to overapproximate a context free grammar by a regular expression? I understand that a context-free grammar is strictly powerful than a regular expression in that a context free grammar can represent any regular language, but not all context free languages can be represented by a regular expression. However, an over-approximation of context-free languages is possible with regular expressions. For example, .* over approximates all context-free languages.

My question is, does there exist a more tighter approximation of a context free language by a regular expression? In particular, given a context free grammar, can I turn it into an (over-approximate) regular expression?

One option I can think of is to

Start with the start symbol, and produce a regular expression from its alternates by joining each alternate with |.
Replace any tokens in the alternate with its regular expression representation as above.
Replace any recursion (direct or indirect) with .*.

Has there been any research in this regard?

One classical answer to this question is Parikh's theorem. Parikh's theorem states that the histograms of all words in a context-free language form a semilinear set. Conversely, the language of all words whose histogram belongs to a semilinear set is regular. Since the proof of Parikh's theorem is constructive, you can in principle take a context-free grammar and come up with a regular over-approximation.

Another classical answer is the Chomsky–Schützenberger theorem, which states that every context-free language can be written in the form $h(D \cap R)$, where $h$ is a homomorphism, $D$ is a Dyck language, and $R$ is a regular language. You can over-approximate your language by $h(R)$, which is regular. Once again, the proof is constructive, so the over-approximation is algorithmic.

Another option is to take all parse trees of your language of a given depth $d$, and replace all nonterminal leaves with $\Sigma^*$. This generalizes your approach. However, generally speaking it won't be the case that the languages $L_d$ produced in this way will converge to the original language, even if you only consider parse trees corresponding to leftmost derivations.

A similar option is to convert your context-free grammar to a PDA, and take the language of all  words whose length-$n$ prefix has some corresponding partial computation. The language $L_n$ do converge to the original language, for trivial reasons.

Even simpler, you can take all words of length up to $n$ in your language, together with $\Sigma^n\Sigma^+$.

These methods can of course be combined. For example, starting with the Chomsky–Schützenberger theorem, you can consider more intelligent over-approximations for the Dyck language $D$, for example taking all parse trees of length $d$ corresponding to the grammar containing the rules $S \to \epsilon$ and $S \to (_i S )_i S$.


How to mathematically determine row, column, and sub-square of cell in nxn array where n is a perfect square? Given an one dimensional array of size nxn, where n is a perfect square

How can one mathematically determine the row, column, and/or sub-square the cell resides in? Additionally, is there a mathematical way to traverse the subsquare?

Let the one-dimensional cells be $c_1, c_2, \cdots, c_{n^2}$.

Assume the top-left cell is at $(1,1)$, i.e., the first row and the first column. Assume the top right cell is at $(1,n)$, i.e., the first row and the $n$-th column. Then the $i$-th cell, $c_i$ is at $(i/n + 1, i \%n +1)$. Here $i/n$ is the integer division and $i\%n$ is the modulo operation in any popular programming language.  For example, let $n=9$. Then the $42$-th cell, $c_{42}$ is at $(42/9+1, 42\%9+1)=(5, 7)$.

Suppose the subsquares are lined up in the same order as the cells, so that we have subsquares $S1, S2, \cdots, Sn$. Consider each subsquare as a kind of "large cell". So that we would have the following coordinates for subsquares.

Note that $c_i$ belongs to the $(i/n+1)$-th subsquare, i.e. subsquare $S(i/n+1)$. For example, $c_{37}$ belongs to the $5$-th subsquare, i.e, subsquare $S5$. We are in the same situation as before, but with the $(i/n+1)$-th "large cell" and a $\sqrt n\times\sqrt n$ of "large cells". So similarly we see that the $(i/n+1)$-th subsquare is at $((i/n+1)/\sqrt n + 1,(i/n+1)\%\sqrt n + 1)$, using the coordinates for subsquares.

Suppose we want to traverse the subsquare at $(j,k)$ (where $(j,k)$ is in the coordinates for subsquares).

The first cell (the top-left cell) of that subsquare is $c_{(j-1)\sqrt n\cdot n + (k-1)\sqrt n +1}$
The first cell of the second row of that subsquare is $c_{(j-1)\sqrt n\cdot n + (k-1)\sqrt n +1 + n}$
$\cdots$
The first cell of the last row of that subsquare is $c_{(j-1)\sqrt n\cdot n + (k-1)\sqrt n + 1 + (\sqrt n -1 )n}$

So we can traverse all cells in that subsquare by the following pseudocode.

$\quad$ for $row$ in $1, 2, \cdots, \sqrt n$
$\quad\quad$ for $column$ in $1, 2, \cdots, \sqrt n$
$\quad\quad\quad$ visit the cell at $row$-th row and $column$-th column of the subsquare at $(j,k)$, which is $c_{(j-1)\sqrt n\cdot n + (k-1)\sqrt n + (row -1 )n + column}$

Note "$row$-th row and $column$-th column" are referring to cells in that subsquare.

For example, we will traverse the cells at subsquare (2,3) in the following order.

cells in its first row, $c_{34}$, $c_{35}$, $c_{36}$,
cells in its second row,  $c_{43}$, $c_{44}$, $c_{45}$,
cells in its third row,  $c_{52}$, $c_{53}$, $c_{54}$.


What's the difference between a bridge, a mediator and a wrapper? The slides from my course in software architecture hints that these are seperate terms, but I can't seem to find the difference. Aren't all of them just translating interfaces?

It was very common for early patterns research to put a lot of emphasis on the "intended use" of a pattern, over and above any structural differences in the implementation.  Then, people who were at that stage of architectural maturity where they were "doing patterns because patterns is what you do" developed long, often elaborate explanations on why these alleged differences were important.

However, research has shown that the structure is really all that matters, because the semantic distinctions:

have no formal distinctions, even in the mathematical treatment of type theory
are not enforceable without syntactic differences in developing the type relations (compiler needs something to enforce)
therefore change with changing requirements
and should not be forced not to change, as reuse is the point of good architecture

So much of those large discussions on why strategy is different than state have turned out quite labored, unconvincing, ineffectual, and slightly humorous as the years have moved on.

My suggestion is to ignore any "is used for" discussion at all and completely focus on the type relationships.  If you do that, then you will find that (depending on your particular definition of these patterns, but fairly standard here)

Mediator > Bridge > Adapter

where the > relation should be read as "is implemented using".  Adapter is a functional relationship between three or more types around on one abstraction tree.  Bridge and Mediator are functional relationship between four or more types around two abstraction trees, defining an interface between the abstraction trees.  Mediator adds to the type coupling usage relationships between concrete nodes of the abstraction trees.

Typically, Mediator is a bad pattern (antipattern) that doesn't scale well and causes an application to become monolithic.  It is used very frequently because people read what it does and go "oh, I need that" and use a pattern becasue, as above, well, patterns are "what you use".  They may be an intermediate step while decoupling a heavily coupled application during refactoring, but typically if you are making that step, full decouple to Bridge (with a factory) is indicated and just as easy.


Find the minimum amount of swaps in fixed indices to sort an array When given the length of a source array, I want to generate the array of swaps that need to be performed in order to sort the source array. I want to make this array as small as possible. Swaps will be performed only if necessary for sorting, as defined by the following function.

def compare_swap(array, a, b):
    if array[a] < array[b]:
      (array[a], array[b]) = (array[b], array[a])

Example

input: 3
Output: [(0,1), (1,2), (0,1)]

What I mean is something like network sorting.

I want to understand how to calculate the number of such swaps and how to generate such array exactly.

Your question appears to be about sorting networks. Sorting an array in the comparison model requires $\Omega(n\log n)$ comparisons, and so $\Omega(n\log n)$ of your swaps. Ajtai, Komlós and Szemerédi were the first to come up with a matching $O(n\log n)$ sorting network (the AKS sorting network), and their construction was simplified by Patterson. These networks also have the advantage that they can be divided into $O(\log n)$ layers of disjoint swaps. Very recently, Goodrich came up with Zigzag sort, another $O(n\log n)$ sorting network.

Since we know that there exist $O(n\log n)$ sorting networks, we can find an optimal sorting network in time $\binom{n}{2}^{O(n\log n)} = 2^{O(n\log^2 n)}$ (verifying that a network works takes time roughly $2^n$ using the zero-one principle). There is no reason to expect any subexponential algorithm.

You might be interested in Ian Parberry's page on sorting.

This part answers the following question: What is the maximal number of swaps needed to order an array of length $n$?

Suppose that your array contained numbers from $1$ to $n$. Then you can think of it as a permutation $\pi \in S_n$. Swapping two elements in the same as multiplying by a transposition, so the question is how many transpositions we need to multiply to get $\pi$. If the cycle structure of $\pi$ is $a_1,\ldots,a_k$ then this number is $(a_1-1) + \cdots + (a_k-1) = n - k$. Therefore $n-1$ is the most that is needed. An example of a permutation needing $n-1$ swaps is $(234\cdots n1)$, which corresponds to the array $2,3,4,\ldots,n,1$.


Min-max the component-wise sum of two sets When I was trying to prove a problem at hand to be NP-complete, I coined the following problem:

  Given two integer sets $A = \{ a_1, \cdots, a_n \}$ and $B = \{ b_1, \cdots, b_n \}$.
  We know that there are $n!$ bijections between $A$ and $B$.
  For a bijection $f\colon A \to B$, define
  $$\max f = \max_{a \in A} \{ a + f(a) \}.$$
  This problem is to find a bijection which minimizes $\max f$.

I think it is polynomial solvable (which is thus of no use in reduction).
The algorithm is simple: Sort $A$ non-decreasingly and $B$ non-increasingly and map $A$ to $B$ component-wisely.

However, I could not find a proof.

Problem: How to prove (or disprove) this algorithm?

Let $f$ be an optimal solution in which $f(a_1) < f(a_2)$ for some $a_1 < a_2$. Let $g$ be obtained from $f$ by switching the values at $a_1$ and $a_2$:
$$
g(a) = \begin{cases} f(a_2) & a = a_1, \\ f(a_1) & a = a_2, \\ f(a) & \text{otherwise}. \end{cases}
$$
Then
$$
\begin{align*}
a_1 + g(a_1) &= a_1 + f(a_2) < a_2 + f(a_2), \\
a_2 + g(a_2) &= a_2 + f(a_1) < a_2 + f(a_2), \\
a + g(a) &= a + f(a) & \text{otherwise}.
\end{align*}
$$
It follows that $\max g \leq \max f$.

Consider now $f$ as a permutation on $\{1,\ldots,n\}$: the first element is the index of $f(a_n)$, the second element is the index of $f(a_{n-1})$, and so on. It is a classical result that $f$ can be sorted by transposing pairs of numbers in the wrong order, an operation which corresponds to the transformation above (one way is to put $n,n-1,\ldots,2$ in their right place, if needed, in this order). The correctness of your algorithm immediately follows.

Comment: This sort of analysis is very reminiscent of the analysis of greedy algorithms.


Matching each unique pokemon with a unique move Background:

There are 832 unique Pokemon in the Pokemon universe, and
There are 728 fighting moves that the Pokemon can collectively learn.
No Pokemon can learn to do every fighting move, and some Pokemon can only learn one.
The average Pokemon can learn between 10-30 fighting moves , and
Most fighting moves can be learned by multiple Pokemon.

Challenge:

I want to match as many unique Pokemon to one unique move. These are one-to-one matches.

Example with U.S. presidents:

Name: Clinton, Moves: Democratify, Impeachify
Name: Bush, Moves: Republicanify
Name: Obama, Moves: Democratify, Healthcarify
Name: Trump, Moves: Republicanify, Impeachify

Example solution that matches the highest number (in this case, all of them)

Clinton-Democratify
Bush-Republicanify
Obama-Healthcarify
Trump-Impeachify

Summary:
What's an algorithm I could use to get the most potential matches of unique Pokemon to unique move?

Caveat:
I'm just a regular guy, no computer science background, and a fuzzy memory of what I learned in my high school calculus class, and a VERY basic understanding of graph theory... so bonus points if you explain it simply enough for me to understand.

While your description of the problem is not super clear. I can guess that you're looking at a maximum bipartite matching problem. Which by the way, can also be viewed as a degenerate case of maxflow problem. Both problems are classic, you should have no problem finding resources on them. For example, this.


Clarifying the definition of reduction with regards to NP-complete problems In my logic class we started learning about the different complexity classes. In particular, we focused on the NP complexity class. A problem is in NP if it is solvable in polynomial time using a nondeterministic Turing machine. To show that a problem $L$ is NP-compelete, we have to show that: $1)$ $L$ is in NP, and $2)$ if $L$ is solvable in polynomial time, then all problems in NP can be solved in polynomial time.
In regards to $2)$ we can use reduction. So if you already know a NP-complete problem $M$, then it is enough to show that we can use a polynomial time algorithm that we can use for $L$, in order to solve $M$ in polynomial time.
I'm not sure I understand the explanation for the reduction section.

A problem $L$ is $\text{NP}$-complete if $L$ is in $\text{NP}$, and $L$ is $\text{NP}$-hard (that is, $A\leq_p L$ for all $A\in \text{NP}$ ). Consider the following claims.
Claim 1: if $L$ is $\text{NP}$-complete and $L\in \text{P}$, then $\text{NP} \subseteq \text{P}$ (that is, all problems in $\text{NP}$ can be solved in deterministic polynomial time).
Claim 2: If $ A \leq_p B$, then $B\in \text{P} \to A \in \text{P}$.
What you asked about is claim 1. To begin with, its correctness follows from claim 2. Indeed, if $L$ is $\text{NP}$-complete, then for every $A\in \text{NP}$, it holds that $A\leq_p L$. Thus, if we assume that $L\in \text{P}$, then we get by claim 2 that $A\in \text{P}$, and therefore $\text{NP} \subseteq \text{P}$. So what is missing for you is the proof of claim 2, and a sketch of its proof goes as follows. If $M_f$ is a TM that computes a polynomial time reduction $f$ from $A$ to $B$, and $M_B$ is a TM that decides $B$ in polynomial time, then a TM $M_A$ that decides $A$ in polynomial time operates as follows. On input $x$, $M_A$ computes $y = M_f(x)$, then $M_A$ runs $M_B$ on $y$, and answers the same. What is left to show is that $M_A$ decides $A$ in polynomial time, and I leave that to you (use the fact that |y| is polynomial, and the fact that a composition of polynomials is a polynomial).


Why do many developers continue to rely on pseudo-random number generators? Although hardware based “true” random number generators are available, software-based pseudo-random number generators still remain the predominant method for generating random numbers in use today. Why do developers continue to rely on pseudo-random number generators?

Pseudo-random number generators and "true" random number generators serve different purposes, though there are some areas where they can overlap.

Pseudo-random number generators are useful when you need a large sequence of bits that appear to be uniformly distributed (or sometimes distributed other ways) that can be deterministically generated. "Unpredictability" is usually unimportant in these applications. In fact, it's often useful to use quasi-random number generators which are even more predictable. Being deterministic is often a valuable, if not critical, benefit. It means that you can easily repeat a specific sequence which is good for debugging and replication among other things. For example, if I want to replicate a database query that involves (pseudo-)"random" numbers, I can just ship a seed to the replicas and they can replay the transaction rather than requiring that I ship the entire sequence of numbers generated. It's also nice that pseudo-random number generators don't require any special hardware or anything at all beyond the ability to compute.

"True" random number generators are used when you need unpredictability, usually in an adversarial (and particularly security) context. You need some "secret" that you know that no one else knows even if they know everything about how you think and could predict anything you could do if they knew what you were observing.1 Producing entropy is time-consuming though. Most of the time, if a large number of "random" bits are needed, a source of entropy will be stretched using cryptographic pseudo-random number generators. Even doing this, hardware instructions take on the order of hundreds of cycles and are usually slower than optimized (non-cryptographic) pseudo-random number generators. If you don't need bits that are unpredictable by an adversary, there is usually little reason to use "true" random numbers.

1 Bits of "true randomness" are powerful things. Being able to "flip a coin" provides solutions to problems that are otherwise unsolvable.


How to calculate the total error from an arbitrary hidden layer in a neural network back propogation? I'm following the tutorial over at https://mattmazur.com/2015/03/17/a-step-by-step-backpropagation-example/ and so far everything makes sense to me. I am now trying to reason about how these formulas extend to any number of hidden layers. Specifically, how to proceed when you have the partial derivative of total error with respect to a weight. In the above post, $\frac{\partial Etotal}{\partial w1}$ is just the sum of the partials for $Eo1$ and $Eo2$ with respect to $w1$. Let's say that there is an extra layer between the $h$ nodes and the $o$ nodes, with nodes $j1$ and $j2$. Is $\frac{\partial Etotal}{\partial w1} = \frac{\partial Ej1}{\partial w1} + \frac{\partial Ej2}{\partial w1}$ or is it more complicated? Something like: $\frac{\partial Etotal}{\partial w1} = \frac{\partial Eo1}{\partial w1} + \frac{\partial Eo2}{\partial w1} = (\frac{\partial Ej1}{\partial w1} + \frac{\partial Ej2}{\partial w1}) + (\frac{\partial Ej1}{\partial w1} + \frac{\partial Ej2}{\partial w1})$

The short answer is yes, $\frac{\partial E_{total}}{\partial w_1} = \frac{\partial E_{j_1}}{\partial w_1} + \frac{\partial E_{j_2}}{\partial w_1}$.

The long answer. The key formula is the chain rule, as D.W. mentioned:

$\frac{\partial E_{total}}{\partial w_1} = \frac{\partial E_{total}}{\partial out_{h_1}} \cdot \frac{\partial out_{h_1}}{\partial net_{h_1}} \cdot \frac{\partial net_{h_1}}{\partial w_1}$

What's good about it is that all three components on the left are local information. No matter what the next or previous layers are,

$\frac{\partial out_{h_1}}{\partial net_{h_1}} = out_{h_1} (1 - out_{h_1})$

$\frac{\partial net_{h_1}}{\partial w_1} = i_1$

Hence, the calculation is the current node depends only on forward messages from direct neighbors to the left and backward messages from direct neighbors to the right:

$out_{h_1}$ and $i_1$ are known from the forward pass, and $\frac{\partial E_{total}}{\partial out_{h_1}}$ is the total backward message.

In the architecture from the post, the node $h_1$ has two direct neighbors to the right: $o_1$ and $o_2$, and that explains the sum $\frac{\partial E_{total}}{\partial out_{h_1}} = \frac{\partial E_{o_1}}{\partial out_{h_1}} + \frac{\partial E_{o_2}}{\partial out_{h_1}}$. In your example, the neighbors are $j_1$ and $j_2$, so it will be the sum  $\frac{\partial E_{total}}{\partial out_{h_1}} = \frac{\partial E_{j_1}}{\partial out_{h_1}} + \frac{\partial E_{j_2}}{\partial out_{h_1}}$. If $h_1$ has even more connections, all of them will pass the backward message and they will be added up.


Algorithm to find if there are N 1's in a matrix where no two 1's are in same row or column I am trying to find an algorithm to determine whether a $N\times N$ matrix of ones and zeroes could have a sublist of ones,  such that in that sublist we have only one $1$ from each row or column.

This is the perfect matching problem in a bipartite graph: construct a bipartite graph with nodes $1,...,N$ on one side and nodes $-1,...,-N$ on the other side, and with an edge from $i$ to $-j$ if your matrix has a 1 in row $i$, column $j$. Then a perfect matching in this graph corresponds to a subset of ones in the matrix having the property that no two of them are in the same row or column.

Textbook algorithm

The Hopcroft-Karp algorithm solves the problem; it can determine if a perfect matching exists in time $O(\sqrt{N} M)$ where $M$ is the number of ones in your matrix (clearly, $M \le N^2$).

A simpler randomized algorithm

If you are satisfied with a randomized algorithm (with a small probability of error), there is indeed a conceptually simpler algorithm due to László Lovász. Create a new matrix $X$ in which every 1 in the original matrix is replaced by a random integer between 1 and some bound $P>100 \cdot N$; zeros in the original matrix remain zeros in $X$. Compute the determinant of $X$. If $det(X) \neq 0$, then for sure the original matrix has a perfect matching; if $det(X) = 0$, then with probability at least $1-1/100$, the original matrix does not have a perfect matching. (If you want to be sure that the value of the determinant does not overflow, you can do the computations modulo $P$ if you choose $P$ to be prime.) Computing the determinant will take time $O(N^3)$ with standard decomposition methods.

An even simpler (and slower) method

The simplest polynomial-time algorithm I know for bipartite perfect matching is due to Linial, Samorodnitsky and Wigderson and runs in time $O(N^4 \log N)$. Let $c_j$ denote the sum of the elements in column $j$. The algorithm is as follows:

  For $N^2 \log N$ iterations do:
      1. Normalize each column so that it sums to 1
      2. Normalize each row so that it sums to 1
      3. Compute $c_1,\ldots,c_N$
      4. If $\sum_{j=1}^N (c_j-1)^2 < 1/N$ return YES
   Return NO

If $N$ is tiny

If you want something even simpler (?) to implement (but much, much slower if $N$ is large), you could just enumerate all permutations over $N$ elements, and for each of these check if the corresponding set satisfies your property. That is, for each permutation $\pi: \{1,\ldots,N\} \to \{1,\ldots,N\}$, you check if cell $(i, \pi(i))$ of the matrix contains a 1, for each $i=1,\ldots,N$. The standard libraries of some programming languages have support for generating all permutations of a set; for example, itertools.permutations in Python or next_permutation in C++.
However, this approach based on enumeration will take time about $N \cdot N!$, which is more than exponential in $N$. It will probably only be acceptable if $N$ is at most around 10-12.


Does $\mathsf{P} \ne \mathsf{NP}$ imply that $|\mathsf{NP}| > |\mathsf{P}|$? Is it possible that $\mathsf{P} \not = \mathsf{NP}$ and the cardinality of $\mathsf{P}$ is the same as the cardinality of $\mathsf{NP}$?  Or does $\mathsf{P} \not = \mathsf{NP}$ mean that $\mathsf{P}$ and $\mathsf{NP}$ must have different cardinalities?

It is known that P$\subseteq$NP$\subset$R, where R is the set of recursive languages. Since R is countable and P is infinite (e.g. the languages $\{n\}$ for $n \in \mathbb{N}$ are in P), we get that P and NP are both countable.


Is this partitioning problem NP-complete? I have a sequence of points $(x_1, \ldots, x_n)$ and a function $f$ that maps every consecutive subsequence (ie. of the form $(x_i, x_{i+1}, \ldots, x_j)$) to a real number. I want to split this sequence into partitions of consecutive subsequences so that the sum of $f$ on each partition is maximized.

For example, suppose the sequence is $(1, 5, 6)$ and $f$ is defined as:
$f(1) = 1, f(1,5) = 13, f(1,5,6) = 0, f(5) = 2, f(5,6) = 9, f(6) = 6$

Then partitioning the sequence as $\{(1,5), (6)\}$ achieves the maximum possible value of $f(1,5) + f(6) = 19$.

Is this problem NP-hard? I can come up with some greedy algorithms to find an approximate solution, but I don't think they always get the correct answer. But I can't figure out how to prove that it's NP-hard either. Any hints on how to make the reduction?

This problem can be solved in polynomial time with dynamic programming. Let $A[i]$ be the maximum value you can achieve with the points $x_1, \dots, x_i$.

You can compute $A[i]$ by choosing the maximum of $A[k]$ + $f(x_{k+1}, x_{k+2}, \dots, x_i)$ from all $k < i$. Then $A[n]$ contains your answer.


How do you prove a heuristic is admissible? How does one prove that a suggested heuristic is admissible? Is this even possible?

For Example: Let's say I have the game Free Cell.
Rules: https://en.wikipedia.org/wiki/FreeCell

How can I prove that the number of cards not in the foundation plus every out of order card is an admissible heuristic?

Proving a heuristic is admissible usually means proving two things:

it follows the triangular inequality principle
given the same preconditions, the heuristic never overestimates the actual solution


P, NP Problem and Turing Machines My first question here, I think this will be an easy one.

As for definition:

NP:
NP is the set of decision problems solvable in polynomial time by a theoretical non-deterministic Turing machine. (wiki)

P:
P Contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. (wiki)

(a) I thought, that you can convert every Non-deterministic Turing machine into a equivalent deterministic Turing machine ?

I am not sure about that I know it is possible with NFA's to DFA's.

But if (a) is true, wouldn't that mean that P=NP?

Yes, a non-deterministic Turing machine can be converted into an equivalent deterministic Turing machine, but it is not known that if a polynomial time non-deterministic Turing machine can be converted into an equivalent polynomial time deterministic Turing machine.

Note "equivalent" only means they accept the same language, it does not mean they run in the same time.


Question on time hierarchy How can I prove that $\mathsf{DTIME}^{\mathrm{Htm}}(n^2)$ is contained in $\mathsf{DTIME}^{\mathrm{Htm}}(n^3)$?

(sorry about how it is written. I mean the set of languages decided by a deterministic TM with an oracle to $\mathrm{Htm}$ in $n^2$ time and $n^3$ time).

If someone can please write the proof, it will be great.

A language is in $\mathsf{DTIME}(f(n))$ if there is a Turing machine accepting the language and running in time at most $f(n)$ (or, in some definitions, $O(f(n))$). Therefore $f(n) \leq g(n)$ implies that $\mathsf{DTIME}(f(n)) \subseteq \mathsf{DTIME}(g(n))$. The same holds for relativized classes.


What is the difference between finite automata and finite state machines? I have used FSM in Digital sequential Circuit designs. But I am unfamiliar with Finite Automata. Can somebody help me in understanding 'basic' difference between the two ?

As far as I understand, both have "states", and "actions" that make the machine move from one state to another upon an input signal. Thus the conceptual ideas are the same. There is some difference in the details.

In FSM for circuit designs the input signal is mostly assumed to be a bit (binary), whereas in finite state automata one can have a general "abstract" alphabet of input symbols. Second, a FSM also generates an output, associated to the state reached, also binary. In automata terminology this 'extension' is called a Moore machine. Automata however have final (or accepting) states, that signal a favourable input read. Finally, FSM are mostly deterministic, i.e., for each input in a certain state there is one next state. In automata theory one also considers the nondeterministic variant where one might have choice in where to move.


Context sensitive language is context free Problem of determining whether a context sensitive language is context free is undecidable.

How to prove it

This can be done in a similar way to the proof that it is undecidable whether the language of a context-free grammar is regular. A general statement of such undecidability properties is Greibach's theorem observed by  Sheila Greibach in 1968.

  Let $C$ be a family of languages effectively closed under union and
  concatenation with regular sets, and for which equality to $\Sigma^*$ is
  undecidable (for sufficiently large $\Sigma$). Let $P$ be a proper subset of $C$,
  which contains all regular languages, and is closed under single
  letter quotient. Then membership of $P$ is undecidable for $C$.

So, we have to check whether the context-sensitive and context-free languages meet the criteria of Greibach for $C$ and $P$.


weighted-clique to vertex cover reduction WEIGHTED-CLIQUE

  input: a undirected graph G that has weighted edges and 2 natural numbers a, b
  question: does G have a clique of size a with total weight of b?

I want to prove that this is NP-hard (assuming weighted-clique $\in NP$)

So I would have to prove

$VertexCover \leq_P WeightedClique$

Need to show the transformation: $(G, k) \to (G', k', d)$

Which ill do by using the fact that $C$ is a vertex cover in $G = (V, E)$ whenever $\bar{C}$ is a clique in $G = (V, E)$ so $\overline{C} = |V| - C$

Hence we can let $G' = \overline{G}$ and $k' = |V| - k$.

I will draw example graphs to illustrate this:

I put 1's in $G'$ just to show that they're weighted as of right now, they have no purpose since I'm not sure how to integrate them into this problem yet.

So ultimately to prove this I need to show

  If there is a solution to $VERTEXCOVER(G, k)$, then there must be a solution to WEIGHTEDCLIQUE$(\overline{G}, |V | − k, d)$ (1)
  if there is a solution to WEIGHTEDCLIQUE$(\overline{G}, |V | − k, d)$, then there must be a solution to VERTEXCOVER$(G, k)$ (2)

I only know how to do the (2) part since the $d$ number could just be ignored.

(2) Using the fact from above where $C$ is a vertex cover we know that

If $\forall u, v \in V$, if $u, v \in C$, then $(u, v) \in E$

Taking the contrapositive

$\Leftrightarrow \forall u,v \in V$, if $(u, v) \in \overline{E}$, then $(u \in \overline{C} \text{ or } v \in \overline{C})$. Which makes it clear that $\overline{C}$ is a clique. This is also done in polynomial time since we are going over all pairs of vertices in the original graph which is done in polynomial time.

Now for (1) I'm not sure how to use the vertex cover and get some d such that it holds, if even possible.

Any help appreciated

edit: did wrong side by accident, fixed it

Let $G=(V,E)$ be an unweighted graph (think of all the edges as having weight $1$), $n=|V|$, and $\bar{G}$ be the edge-complement of $G$.

Now, $C$ is a vertex cover of $G$ iff $\bar{C} = V \setminus C$ is an independent set of $G$, that is, iff $\bar{C}$ is a clique of $\bar{G}$.

When you combine this with the fact that a clique of size $k$ has $\binom{k}{2} = \frac{k^2-k}{2}$ edges you get: "There is a vertex cover of size $k$ in $G$ iff $\bar{G}$ contains a clique of size $a = n-k$ and weight $b = \binom{n-k}{2}$."

In fact, as far as this reduction is concerned, you can drop either the size or the weight constraint from your clique problem since one implies the other.


Unary notation representation in Turing Machine What can be a good convention to represent positive and negative integers in unary notation on a Turing machine? I want to design a Turing machine which acts as a subtractor.So should I partition the integer range to represent positive and negative integers in unary notation or is there some other way?

A reasonable convention would be to take any enumeration of the integers and use it. For example, this enumeration
$$
0,1,-1,2,-2,3,-3,\ldots
$$
corresponds to this encoding:
$$
\begin{align*}
0 &\to \epsilon \\
1 &\to 1 \\
-1 &\to 11 \\
2 &\to 111 \\
-2 &\to 1111 \\
3 &\to 11111 \\
-3 &\to 111111
\end{align*}
$$


Is there a physical analogy to the Turing Machine? Recently in my CS class I've been introduced to the Turing Machine.

After the class, I spent over 2 hours trying to figure out what is the relationship between a tape and a machine.

I was completely unaware of the existence of computer tapes or how tapes and machines interacted until today. I still can't see why a machine would read tapes but a scanner is perhaps a closer conception to the Turing machine where paper is considered a tape and whatever goes inside of a scanner is whatever a Turing machine would do.

But in any case, isn't the idea of a Turing machine quite archaic? We have so many physical (rather than hypothetical) devices in our office or living room that seems to do what the Turing Machine does.

Can someone provide a better example drawing from reality so that the essential functionalities of this hypothetical conception is captured?

AFAIK the Turing Machine is modeled on the idea of a human with a pen and paper. The human has a certain state in the brain, looks at the paper like the machine looks at the tape, and writes something on the paper or moves to look at a different place, just as the machine does.

TM is archaic as Peano natural number arithmetic. TM is useless for practical computation, and it is of course not intended to be used for that. It is just a simple way to axiomatize computation so we can reason about what's computable and what isn't - just as Peano arithmetic is useful for defining from first principles what natural numbers are, and what are their properties - but it would be ridiculous to try to do arithmetic by manipulating Peano numbers by hand according to the theoretical definitions.

Just think how difficult it would be to prove different theorems from complexity and computability theory (e.g. prove that the Halting Problem is undecidable), if you had to prove them using the semantics of the C++ programming language instead of the Turing Machine. Your proofs would be ridiculous or impossible - as ridiculous as proving associativity of natural number multiplication by using the grade-school method applied to decimal integers as your definition of what multiplication is.


Is n!=O(2^(n lg n))? By Stirling's Approximation $n! = \sqrt{2*\pi*n} * [n/e]^n * e^\alpha$

Therefore $T(n!) = O(n^n)$

$O(n^n) \neq O(2^{n \lg n})$

Is this correct? Is there another way to get this result if it is correct? Thanks.

Remember, big-O is essentially an upper bound so we do have
$$
n! = O(n^n)
$$
in the sense that there is a constant $c$ for which $n!\le c\;n^n$ eventually. [Note, by the way, that there's no function $T(\cdot)$ involved here.]

Now let's see if $n!=O(2^{n\log n})$. We can argue this way (assuming the log is base-2):
$$
2^{n\log n} = 2^{(\log n) n} = \left(2^{\log n}\right)^n = n^n
$$
so we can conclude that the two sets $O(n^n)$ and $O(2^{n\log n})$ are in fact equal.


Where is Program Counter (PC) stored? Where is program counter stored? CPU caches?

Also how big are these counters?

What happens if that memory has been filled up?

I know that it's a value that stores the next instruction for the CPU to process, as well as it increments with the size of the next instruction to cycle for the next instruction for the CPU to process, and the cycle continues, that's as far as I know, right?

Inside a modern high-end CPU, the "program counter" is probably not stored in a single place. Superscalar out-of-order execution requires more than one instruction to be executing at a single time, some of them executing speculatively.

To understand what's going on, you need to consider what the program counter is used for. I'm going to use the Intel Core 2 microarchitecture as an example, mostly because it's the only decent-but-uncluttered diagram that I could find. Most modern high-end CPUs are broadly similar, in that they have a Tomasulo-like pipeline with register renaming. A RISC (e.g. MIPS or ARM) might have fewer decode stages. Also, not all CPUs implement a retirement register file; there are other methods which do the same job.

Nonetheless, let's go with this for the moment.

Instructions are (broadly speaking) streamed from the top to the bottom of the diagram. They start in the cache (and of course may have to be fetched into the cache), go through decoding and being stored in different buffers, until they end up in the reservation station. Here it waits until it is ready to execute.

When everything that an instruction needs becomes available, it goes to an execution unit. In the diagram, the yellow parts are the "normal" execution units (integer, floating point). There are also execution units for memory operations, but we'll ignore those for the purpose of this discussion.

When an instruction has finished execution, the results are posted on the results bus (called the "common data bus" in Tomasulo's original paper). These results may wake up instructions which depend on those results, and the cycle continues.

Now, think for a moment about what the program counter is used for.

First off, let's think about instruction fetch. It needs to know what address to send to the instruction cache for lookup. Most of the time, it's the next address. However, do consider that the cache line width isn't a single instruction; in this example it's 128 bits. So the instruction fetch unit actually increments its "program counter" by 16 bytes, no matter how big each instruction is.

Branch instructions complicate instruction fetch. Unconditional branches are straightforward once you've recognised them, so the instruction fetch unit gets some input from pre-decoded instructions.

Conditional branches are similar, except that the instruction fetch unit needs to decide whether to guess that the branch was taken or not taken to keep instructions flowing.

So the IFU has an idea about what the "program counter" is, but it is granular, working on a cache line at a time.

Now let's think about execution. The CPU would like to execute instructions out of order if it can, however things can happen which complicate that. The most obvious problem is if the IFU incorrectly predicted a conditional branch. However, instructions can also raise exceptions, and also the CPU might need to respond to an external interrupt.

To achieve this, the CPU needs to be able to recreate the CPU state as if it was executing instructions sequentially at the time that the control flow was interrupted. This is the job of the reorder buffer.

The reorder buffer is conceptually a queue of instructions, ordered by the "logical order" (i.e. the order that they would be executed if this was a scalar in-order processor). An instruction enters the queue as it travels down the fetch-and-decode path. Once it is in the ROB, it can execute out-of-order.

When an instruction completes, its entry in the ROB is updated noting that it is now complete. An instruction can leave the queue (it is "retired") if it has completed, and every instruction before it in logical order has completed or retired.

The "result" of many instructions is to write a value into a register. If that value is used by a subsequent instruction which is awaiting execution (i.e. it's in the reservation station), then this is handled by the internal results bus. Either way, the result is also stored in the instruction's entry in the ROB. This arrow is not shown on the diagram, but it happens.

When an instruction retires, any register write that it does is stored into the retirement register file. Because instructions are retired in-order, this register file actually stores the state of the machine registers exactly as they would be if the instructions were executed in-order. This is why it's also called the "program visible state". This is the view of the registers that the program "sees", what is saved and restored on a context switch, and so on.

So the second place where there the "program counter" is stored is here, in the instruction retirement unit. This is the program counter as the program sees it, without any speculation, but it's decoupled from instructions that are being fetched and executed.

As an aside, the ROB is also how faults and exceptions are handled. If a fault occurs, then the ROB for the faulting instruction is updated with information about the fault, and every instruction after it in the ROB is removed, along with a flush of the fetch-and-decode parts of the pipeline. This ensures that instructions after the fault don't "happen" even if they have been executed already: the results of those instructions never make it to the program-visible state. Speculative execution is handled in a similar way.

A third place where the program counter may be stored is in the ROB itself. It may be convenient to store the program counter of each instruction along with the instruction. Note that it may not be necessary to store the whole program counter; it may be sufficient to store enough information to recreate the program counter as needed.

A final place where the program counter may be stored is as a general-purpose register. Exactly what this means is a bit complicated to explain if you don't know how register renaming works, but some instructions might need the value of the program counter (e.g. it might be used for memory addressing in position-independent code), in which case transient copies may be stored in reservation station entries of instructions which use it.

So what I hope you can see here is that the real answer is "it's complicated". The program counter is different from other registers in a modern CPU, and there is no one place where it's really "stored", because more than one instruction is "happening" at any given point in time.


Is my compilers assignment irrational? In our assignment we are given a grammar (called minipython) and we are asked to implement some phases of compilation (parsing, some semantic analysis).
One of the requirements is to be able to check for types in an arithmetic expression (arithmetic expressions are only defined for integers). For example in the below code:
def add(x,y):
   return "hello world"
print add(2,1)+ 2

We are expected to detect such errors. However the language,like python, seems dynamic to me. Meaning that the return type of a function depends on the runtime (for example the function def f(x): return x
When we showed the instructor the code below:
a=0
b=1
if b>2:
    a = 'a'
c = a + b

The instructor told us we are supposed to detect such errors (in the arithmetic expression one type is string, the other is a number). And also he said we should run the code tracking the value of each variable.
Well... i haven't heard of a compiler that runs the program in order to detect errors. I mean that would be impossible if the language is Turing-complete right? (I'm not sure if minipython is though)
One of my classmates is attempting to do this by setting a limit on the times he remains on any loop or setting a max recursion depth. But I don't think this is right , i mean what compiler does this? I don't know what magic people do in static analysis tools but i don't expect that anyone runs the code in order to check type errors... unit tests are for that.
My question: Are my assignment's tasks irrational?? Can this language have a totally inferred type system? I'm really confused and I don't have much experience with compilers. Please correct me at any point if I have said anything that is wrong
I can also provide minipython's BNF if its necessary.

Sorry, in complete generality this is an undecidable problem. Pick your favorite undecidable problem $P$ and an instance $a$, and write e.g.:
def value(a):
     if P(a):
         1
      else:
         "Hello, world!"

print(41 + value(a))

Under the (conservative!) assumption that all execution paths are possible, you see that the above is badly formed (value returns an integer or a string). That restriction is doable, and not too hard either:   Do a postorder traversal of your AST, recording the possible types of each node. If any node could have conflicting types, flag a (possible) error.


Expander Graph - Is the following graph family an expander graph? Consider the family of graphs of degree $6$ with vertex set $V_n=(a, b, c)$ for all  $0\leq a, b, c \leq n-1$ with $(a,b,c)$ being connected to $(a-1, b, c),(a+1, b,c), (a, b-1, c), (a, b+1, c), (a,b,c-1), (a,b, c+1)$, with all operations modulo $n$. Show that this  is not a family of expander graphs.

I've been struggling with this question for over a week.
I tried looking at from the algebraic perspective and show that the spectral gap is getting smaller as n(the number of vertexes) rise. But I got stuck a long the way and now I don't know if I'm on the right track at all.

Given $n$, consider the set of vertices $S = \{ (a,b,c) : c < n/2 \} \subseteq V_n$. Assuming for simplicity that $n$ is even, this set contains exactly half the vertices. An edge connects $x \in S$ to $y \notin S$ iff $x = (a,b,n/2-1)$ and $y = (a,b,n/2)$, for a total of $n^2$ edges. Therefore the expansion of $S$ is $|E(S,\overline{S})|/|S| = n^2/(n^3/2) = 1/n$, which converges to zero.


return all strings contains given string in suffix tree Here is my question:

Given a compressed suffix tree of string S and a substring T.
I need to return all substrings of S that begins with the substring T
sorted by lexicographic order.

My approach:
I can traverse the suffix tree and find the edge / node which last letter of T is written on it.
The subtree of this edge basically should be all the substrings of S beginning with the string T.

Am I right about this one?
And How can I print all this subtree sorted?

Yes, you are right. You need to consume the symbols of $T$ and all occurrences of it shall be in the sub-tree below the position you stopped.

Since the edges are stored in lexicographical order, you can perform a Depth-first to print all the substrings of $S$ starting with $T$ in lexicographical order.

Using this example from Wikipedia

and assuming $T = A$, we would arrive at an internal node. Doing a DFS, we would have: $A\$$, $ANA\$$, $ANANA\$$.


Sharp concentration for selection via random partitioning? The usual simple algorithm for finding the median element in an array $A$ of $n$ numbers is:

Sample $n^{3/4}$ elements from $A$ with replacement into $B$
Sort $B$ and find the rank $|B|\pm \sqrt{n}$ elements $l$ and $r$ of $B$
Check that $l$ and $r$ are on opposite sides of the median of $A$ and that there are at most $C\sqrt{n}$ elements in $A$ between $l$ and $r$ for some appropriate constant $C > 0$.  Fail if this doesn't happen.
Otherwise, find the median by sorting the elements of $A$ between $l$ and $r$

It's not hard to see that this runs in linear time and that it succeeds with high probability. (All the bad events are large deviations away from the expectation of a binomial.)

An alternate algorithm for the same problem, which is more natural to teach to students who have seen quick sort is the one described here: Randomized Selection

It is also easy to see that this one has linear expected running time: say that a "round" is a sequence of recursive calls that ends when one gives a 1/4-3/4 split, and then observe that the expected length of a round is at most 2.  (In the first draw of a round, the probability of getting a good split is 1/2 and then after actually increases, as the algorithm was described so round length is dominated by a  geometric random variable.)

So now the question:

  Is it possible to show that randomized selection runs in linear time with high probability?

We have $O(\log n)$ rounds, and each round has length at least $k$ with probability at most $2^{-k+1}$, so a union bound gives that the running time is $O(n\log\log n)$ with probability $1-1/O(\log n)$.

This is kind of unsatisfying, but is it actually the truth?

It's not true that the algorithm runs in linear time with high probability. Considering only the first round, the running time is at least $\Theta(n)$ times a $G(1/2)$ random variable. Let $p(n) \longrightarrow 0$ be the allowed failure probability. Since $\Pr[G(1/2) \geq \log_2 p(n)^{-1}] = p(n)$, the running time is at least $\Omega(n \log_2 p(n)^{-1}) = \omega(n)$.

(There is some cheating involved, since the length of the first round isn't really $G(1/2)$. More careful analysis might or might not validate this answer.)

Edit: Grübel and Rosler proved that the expected number of comparisons divided by $n$ tends (in some sense) to some limit distribution, which is unbounded. See for example Grübel's paper "Hoare's selection algorithm: a Markov chain approach", which references their original paper.


What is beta and k parameter in Incremental Decision Tree I have read this paper https://arxiv.org/pdf/1803.03674v1.pdf for outlier detection problem with real data (online training)
In this paper, the authors used Incremental Decision Tree to build subspaces (nodes in tree) by 2-mean method. The problem is in the algorithm 2 (build tree in paper), the condition (line 22): if t = beta power k. with t is the round observations (maybe each round we observe one sample) the splitting is performed.
The question is: What is beta and k? I spent a lot of time thinking about this. In the experiment you can see the authors plot chart describe splitting space process. At round 5, 11, 40? These are t (in my understanding) 5 can't be a result of any number power any number.
Thanks you.

It appears that $\beta$ is a constant, and $k$ ranges over the integers.  See paragraph 3 of Section IV.B.
Line 1 of Algorithm 2 tells you that $\beta$ is a parameter: it says "Select parameters $\beta$ and ..."  Based on the body text in Section IV.B, presumably "if $t= \beta^k$" means "if there exists $k \in \mathbb{N}$ such that $t=\beta^k$".


Break an authentication protocol based on a pre-shared symmetric key Consider the following protocol, meant to authenticate $A$ (Alice) to $B$ (Bob) and vice versa.

$$ \begin{align*}
 A \to B: &\quad \text{“I'm Alice”}, R_A \\
 B \to A: &\quad E(R_A, K) \\
 A \to B: &\quad E(\langle R_A+1, P_A\rangle, K) \\
\end{align*} $$

$R$ is a random nonce.
$K$ is a pre-shared symmetric key.
$P$ is some payload.
$E(m, K)$ means $m$ encrypted with $K$.
$\langle m_1, m_2\rangle$ means $m_1$ assembled with $m_2$ in a way that can be decoded unambiguously.
We assume that the cryptographic algorithms are secure and implemented correctly.

An attacker (Trudy) wants to convince Bob to accept her payload $P_T$ as coming from Alice (in lieu of $P_A$). Can Trudy thus impersonate Alice? How?

This is slightly modified from exercise 9.6 in Information Security: Principles and Practice by Mark Stamp. In the book version, there is no $P_A$, the last message is just $E(R_A+1,K)$, and the requirement is for Trudy to “convince Bob that she is Alice”. Mark Stamp asks us to find two attacks, and the two I found allow Trudy to forge $E(R+1,K)$ but not $E(\langle R, P_T\rangle, K)$.

This protocol seems to be insecure due to the fact that Bob sends $E(R_A,K)$. This can be used by Trudy to "generate" encryptions of $E(\langle R_A+1,P_T\rangle , K)$ that will later be used to complete the authentication protocol.

Specifically, consider the following attack:

Trudy picks random $R_1$ and runs the protocol with Bob in the following manner:
$$ \begin{align*}
 T \to B: &\quad \text{“I'm Alice”}, \langle R_1+1,P_T \rangle \\
 B \to T: &\quad \color{blue}{E(\langle R_1+1,P_T \rangle, K)} \\
\end{align*} $$
and then Trudy cuts the protocol in the middle (since she doesn't know how to reply). We assume both Trudy and Bob abort.

Now Trudy starts another instance of the protocol:
$$ \begin{align*}
 T \to B: &\quad \text{“I'm Alice”}, R_1 \\
 B \to T: &\quad E(R_1, K) \\
 T \to B: &\quad \color{blue}{E(\langle R_1+1,P_T \rangle, K) }
\end{align*} $$
How did Trudy complete the protocol this time without knowing $K$? it's easy! Bob actually performed the encryption for her in the first instance.

Lesson learned: in a cryptographic protocol, it's good for each message or separable fragment to contain a unique tag that prevents its reuse as some other message in the protocol. If Bob's reply was $E(\langle 1, R_A\rangle)$ and the third message was $E(\langle 2, R_A+1, P\rangle)$, this attack would not work.


Can a language recognized by a NFA be recognized by a push down or Turing machine? Every single NFA has an equivalent DFA representation so that every language recognized by NFA is recognized by the DFA, but is it also true that the language recognized by NFA is recognized by a push down automata and a Turing machine?

A language is recognized by an NFA iff it is regular. It is recognized by a push-down automaton iff it is context-free. It is recognized by a Turing machine iff it is computable. Every regular language is context-free. Every context-free language is computable.

Even without knowing these facts, it is not difficult to simulate an NFA by a push-down automaton and a DFA by a Turing machine.


Does there exist a language which is PSPACE-complete and regular? Does there exist a language which is PSPACE-complete and regular?  (reduction is polynomial with regard to time).

Correct answer here is "unknown".  I can't prove it. Can you help me?

There exists a PSPACE-complete regular language if and only if P=PSPACE, which is unknown.

In fact, we can say even more: the language $\{1\}$ is PSPACE-complete if and only if P=PSPACE.


Why do we need to convert binary numbers into hexadecimal, octal and decimal? Computer reads binary. Now my question is, what is the use of hexadecimal, octal and decimal? Do Computers understand or can read hexadecimal, octal and decimal? This question remains a mystery for me. Why memory locations use hexadecimal, it should be in binary right? Or is it because it is a binary and by time we read its memory location, the computer converts its memory location from binary into hexadecimal for us to make it readable?

You got it in one. Hex is easier for humans to read but also trivial to convert to and from binary. The computer itself only uses binary, in the sense that every wire is either on or off. But, at the same time, you can look at the pattern of ons and offs on four adjacent wires and call that a hex digit.