Find an algorithm that sorts the nodes of a given graph acc. to distance from source node + value of the node's key an unweighted connected graph $G=(V,E)$ all nodes of the graph contain a "serial number" between 1 to V. (V is an integer).

I am trying to come up with an algorithm that sorts all nodes firstly by distance (number of eadges) from source node 's' , secondly- if two nodes have same distance value sort them by value of thier serial number.

complexity required is $O (V+E)$

I tried to solve this via using bfs and then recieve a "bucket" array of distances - for each distance $1,2...$ all nodes within it are in its "bucket".
the problem is, that in order to sort two nodes with same distance according to
their serial number takes at least $O( nlogn)$ of sorting.
 I tried to come up with a use $v-1$ empty arrays and tried to send each "bucket" nodes acc. to their index in the graph and print it - that takes )$V^2$.

This is NOT homework, I really did try my best.
Your comments are appreciated.

Hint:

Use BFS to calculate the distances.
Calculate the scores (sums of distance to source and serial number).
Use counting sort to sort the scores.
Go over the list again and output the vertices in sorted order.


How to prove the structured program theorem? Wikipedia:

The structured program theorem [...] states that [...] any algorithm
can be expressed using only three control structures. They are

Executing one subprogram, and then another subprogram (sequence)
Executing one of two subprograms according to the value of a boolean expression (selection)
Executing a subprogram until a boolean expression is true (iteration)

This theorem is developed in the following papers:

C. Böhm, "On a family of Turing machines and the related programming language", ICC Bull., 3, 185–194, July 1964.
C. Böhm, G. Jacopini, "Flow diagrams, Turing Machines and Languages with only Two Formation Rules", Comm. of the ACM, 9(5): 366–371,1966.

Unfortunately, the first one is practically unavailable, and the second one, in addition to being a bit cryptic (at least for me), refers to the first, so I have problems to understand the proof. Can anyone help me? Is there a modern paper or book which presents the proof? Thanks.

UPDATE
To be exact, I would like to understand the second part of the CACM paper (section 3). The authors write in section 1 the following:

In the second part of the paper (by C. Böhm), some results of a
previous paper are reported [8] and the results of the first part of
this paper are then used to prove that every Turing machine is
reducible into, or in a determined sense is equivalent to, a program
written in a language which admits as formation rules only composition
and iteration.

Here [8] refers to the unavailable ICC Bulletin paper. It is easy to see that the above quote from Wikipedia refers to this second part of the CACM paper (the Turing machine serves as a precise definition of algorithms; "composition" means sequence; an iteration can replace a selection).

The Böhm-Jacopini theorem essentially says that a program based on 'goto' is functionality equivalent to one consisting of 'while' and 'if'.

Sketch of proof based on the following lecture notes:

Say you have a program that consists of a sequence of statements $S_i$; prefix each statement with a label $S_i^{\prime} \gets L_i: S_i$ and update existing goto statements to point to the right locations. Declare a location variable, $l \gets 1$, and wrap the prefixed statements in a while loop that will continue until the last statement is reached, $\textbf{while} (l \neq M) \ \textbf{do} \ S^{\prime}$.

Apply the following rewrite rules to $S^{\prime}$:

Goto rule: Replace $L_i \ \textbf{goto} \ L_j$ with $\textbf{if} \ (l = i) \ \textbf{then} \ l \gets j$
If-goto rule: Replace $L_i : \textbf{if} \ \text{(cond)} \ \textbf{then} \ \textbf{goto} \ L_j$ with $\textbf{if} \ (l = i \land \text{(cond)}) \ \textbf{then} \ l \gets j \ \textbf{else} \ l \gets l + 1$
Otherwise rule: Replace $L_i : S_i$ with $\textbf{if} \ l = i \ \textbf{then} \ S_i,  \quad l \gets l + 1$

The resulting program is then free of goto statements showing the correspondence between the two paradigms.

A more formal proof is provided in your second reference.

Update

After studying the paper in greater detail, this is my interpretation:

Based on the definitions in CACM, let $\mathcal{B}^{\prime} = \mathcal{D}(\alpha, \lbrace \lambda, R \rbrace)$ be the class of Turing machines represented by the language $\mathcal{P}^{\prime}$ that covers flow diagrams. Let $\mathcal{B}^{\prime \prime} = \mathcal{E}(\alpha, \lbrace \lambda, R \rbrace)$ be the class of Turing machines represented by the language $\mathcal{P}^{\prime \prime}$ that covers the transformation covered above.

According to CACM, the author wants to prove that if a Turing machine exists in the family of Turing machines described by $M \in \mathcal{B}^{\prime}$, then there exists a corresponding Turing machine in the family of Turing machines described by $M^{*} \in \mathcal{B}^{\prime \prime}$.

Sketch of the author's proof: He does this by drawing from the derived relationship $M \in \mathcal{B}^{\prime}$ and $M \in \mathcal{E}(\cdots)$ (definition (5)) and then sets up the relationship $M^{*} \in \mathcal{E}^{*}(\cdots)$. For each component of $\mathcal{E}(\cdots)$ he draws a one-to-one mapping with those of $\mathcal{E}^*(\cdots)$. Thus by establishing the bridge between $M$ and $M^{*}$ through $\mathcal{E}(\cdots)$ the author proves $M \in \mathcal{B}^{\prime} \implies M^{*} \in \mathcal{B}^{\prime\prime}$.


Logic, "and" operator between a set of formulas and a formula Consider a set $S$ of formulas $\beta_i$ and a formula $\alpha$, if we have a condition such as $S \land \alpha$ is inconsistent what we have to calculate to check the inconsistency of $S \land \alpha$? In other words, what is the result of $S \land \alpha$?

For example, $S=\{\beta_1, \beta_2, \beta_3\}$

A set $S$ of formulas (propositional logic) is consistent if there is a truth assignment under which all formulas in $S$ are true, in other words if there is a model of $S$. Alternatively, $\{\beta_1, \beta_2, ...,  \beta_n \}$ is consistent, iff $\beta_1 \wedge \beta_2 \wedge ... \wedge \beta_n$ is satisfiable.

You could just find a truth assignment such that $\alpha \wedge \beta_1 \wedge \beta_2 \wedge \beta_3$ is true. If the number of variables is small then you can check it by hand by creating a truth-table, or use Method of analytic tableaux. Also, note that the Satisfiability problem (SAT) is NP complete.

You can also use a resolution procedure to show that a formula is unsatisfiable (inconsistent).


Compute visible vertices of a polygon Given a simple polygon $P$ and a point $p$ within the polygon, I want to compute the vertices of $P$ visible from point $p$. A point $q$ is visible from point $p$, if the line segment $\overline{qp}$ is completely in the polygon $P$.

One can use the accepted answer here to compute visible vertices in $P$ from a point $p$ in $\mathcal{O}(n\log{}n)$.

My question is, does an algorithm exist to do it in $\mathcal{O}(n)$ time?

Yes, there are more algorithms to do so in $\mathcal O(n)$. The first is dated back to ElGindy and Avis in 1981, Lee 1983 and Joe & Simpson in 1985. The visibility algorithms use stack (the first one three stacks, further only one) and process vertices in order they appear at boundary.

The visibility algorithms described in book Art Gallery Theorems and Algorithms by Joseph O'Rourke. The book is out of print, available online.

Also author wrote a paper the vertex-edge visibility graph of polygon with Ileana Streinu in 1996, which with Chazelle's linear time triangulation and slight modification (simply by adding two edges from given point) would solve the problem in linear time.


Machine Learning: if test, validation errors are same, the model with lower train loss is better at generalization? I tuned some hyperparameters and got 2 best models.

These two models are almost the same "test(not train)" and "validation" errors. But model A has lower "train" error than model B.

In this case, the model with lower "train" error (model A), would show good performance on new data? (good generalization)

Or model A is more overfitting to the dataset so it would work worse in new data?

Thanks

Though usually the test error is your primary goal, I can imagine some specific cases when the train error also matters. One possible example: training set has much more 'hard' inputs than the test set.

If you ever visually examined MNIST, you've probably seen that some images are puzzling even for a human, while others are much easier to tell. If one would split the training/test set differently, it's possible to see that training error would be higher than the validation or test error.

However, it's important to say that a situation like that indicates that data is probably poorly collected or split. So in this case it's better not to choose model A vs model B, but to check the data.


How to represent a map data structure mathematically Wondering how to represent a map object such as the following mathematically:

var foo = {
  a: 10,
  b: 'bar',
  c: true
}

You could say that it was a function like this:

foo(x, y, z)

where $x$ is an integer, $y$ is a string, and $z$ is a boolean. But the question then is how to say the names of the keys a, b, c. Something like:

foo(label(x, a), label(y, b), label(z, c))

But then wondering about how type theory deals with this, so I' a bit confused. Wondering how computer science would model this data structure using mathematical notation. Maybe:

$$
\begin{align*}
foo = \left\{
  \begin{array}{r@{}l}
& a = x \\
& b = y \\
& c = z
  \end{array}
  \right\}
\end{align*}
$$

There are multiple ways to represent it.

The simplest way is probably as a mathematical function $f:S \to T$ where $S$ is the type of the keys and $T$ is the type of the values.  In other words, you can represent it as a function/map.  Here we have $f(\mathtt{a}) = 10$, etc. (so this is different from the idea you mentioned in the question).

Here are some more sophisticated ways to encode this in a type system:

If the keys a, b, c, are statically known and never dynamic, and that set is fixed in advance and never changes, this could be represented as simply a tuple or a record type.

If the keys are static but you want to extend them, you could represent this as an extensible row type.  See also In type systems, is there a name for SQL's way of cutting and combining record types into new types? and Is there any difference between extensible records and dependent maps and Encoding row types.

If the keys are fully dynamic (their possible values aren't known at compile time), it needs to be represented as a function (i.e., map type).


How to demonstrate that a language is regular for k? I sort of need an explanation on how can I demonstrate that a language formed by strings that are multiples of k, is a regular language

I really dont know how

Generalizing the other answer, here is a complete classification of regular language of this sort.

  The language $\{ x \in \Sigma^* : |x| \in S \}$ is regular iff there exist $n \geq 0$ and $k \geq 1$ and sets $A \subseteq \{0,\ldots,n-1\}$, $B \subseteq \{0,\ldots,k-1\}$ such that
  $$ S = A \cup \{ n+ mk + r : m \geq 0, r \in B\}.$$

One direction follows from a direct construction (either a DFA or a regular expression), and the other from the pumping lemma (exercise) or Parikh's theorem.


all pairs shortest path using Dijkstra So, I have a list of cities (A, B, C, etc) with weighted edges (two-way, undirected) between them with a list of cities that already have a store.

My task is to place a one new store at either A, B, C, etc so that I minimize the travel distance from any city to a store.

So my head is thinking

Perform Dijkstra's on every non-city vertex
Find the max distance among that node -> all other nodes.
Store that distance associated with the store it originated from.

The problem I encountered was

The easiest example of A, B, and C cities with a store already existing at A, has roads of
AB = 1, BC = 2.

Placing a store at B, would make C have to travel 2 units to the nearest store (at B).
While placing a store at C, would make B have to travel 1 unit (since it can backtrack to A where a store is at).

This "backtracking" to other nodes is causing my mix-ups. Since I'm only iterating from the point of view of either City B or C. B's point of view thinks the max distance to a store is 2, while C does as well. (Even though C should find the max value of 1 unit).

Hint: If you have all-pairs shortest-paths information, and if you are considering placing a store at city X, can you compute the max distance from any city to a store?  You could now enumerate all possibilities for city X.  What's the running time of this algorithm?

An alternative approach:

Hint: If you add a new source vertex and add edges from it to _______, and then use Dijkstra's algorithm to compute single-source shortest-paths starting from that source, does that give you any useful information that will help you?  (You'll have to fill in the blank somehow.)


Resolution when clauses contain more than 1 complementary literals Let's assume that we have clauses $(l_1 \lor l_2 \lor l_3), (\neg l_1 \lor \neg l_2 \lor l_4), (l_1 \lor l_2 \lor l_5), (\neg l_1 \lor \neg l_2 \lor l_6)$, where both $l_1$ and $l_2$ are complementary literals for the clauses.

If we apply the resolution technique for $l_1$ we'll get clauses

$(l_2 \lor \neg l_2 \lor l_3 \lor l_4)$,
$(l_2 \lor \neg l_2 \lor l_3 \lor l_6)$,
$(l_2 \lor \neg l_2 \lor l_5 \lor l_4)$,
$(l_2 \lor \neg l_2 \lor l_5 \lor l_6)$

How to proceed with $l_2$ from here?

Clauses containing both a variable and its negation are not useful, since they're always correct. You can just ignore them.

Furthermore, you CNF is satisfiable - for example, you can set all variables to TRUE. So it's not completely clear what you are trying to accomplish.


Is function application actually a memory manipulation algorithm? I thought about how in lambda calculus (and many implementations of functional programming languages) function (lambda) application and lambda itself, as a construct, are "primitive things", usually somehow implemented by an interpeter. Then I thought, can you "boil-down" these two things to more primitve stuff.
For instance, we have a following expression (apply is usually implicit by the syntax convetions, but whatever)

(apply (\x.\y.x) (a b))

The interpreter:
1. Constructs a new environment, where arguments are bound to lambda's terms, i.e. new_env = this_env.append({"x":a, "y":b, "body":"x"})
2. Performs a rewrite of the whole application term with lambda's body, i.e.
  new_env["body"]

Given only the environment manipualtion "primitives", like: "construct", "append", and "get", doesn't that make whole lambda calculus just a clever trick to hide memory ("tape") mutations? Now I know that turing machine and lambda calculus are equivalent, but is there something more to LC than just what I've described? What have I missed?

That seems reasonable to me, although I've never thought of other that way.  The critical point is that LC essentially involves variables and substitution.  So I wouldn't say it "hides" memory ops, exactly, that's just how LC substitution translates to Turing machinery.  On the other hand, substitution is not primitive - combinatory logic eliminates both variables and substitution.  So you might say LC introduces rather than hides something.


How to enhance my skills as a programmer I want to learn Cryptography and so I am interested to master C-programming.

I know the basic concepts of C-programming  like how to use an array,pointers etc.

I want to develop myself so that I can find the different loopholes in the security of different cryptosystems.

Basically I want to work in Attacking of Cryptosystems apart from developing my skills in theory.

Will someone suggest me some goods or a list of books(say) which are just above the beginner's level and which will establish me as a good programmer?

I will be extremely thankful if someone could help.

You don't need books. You need to write lots of programs. Since you are interested in cryptography, you should practice writing programs that involve mathematics. A good way to do so is to join Project Euler and just go down the list. Good luck!


Fenwick Tree Traversal using Binary value of Index Can someone explain me how do I execute sum query from Index 0 to Index I given the binary value of that Index I. There are some trivial question that I want to know :

Do we have to remove last set bit and all the bits following it.
How many times do I have to access the temporary array made for the data structure i.e Fenwicktree[ ] array.
I have been trying to think about these from the binary index of the Index I.

For eg I have the binary

  001100100100100011

I removed the last set bit. I took 0 as left and 1 as right and traverse it . Whenever I take a right , I access the tree elements and accessing the array finally when I reach the node.So the count comes around  around 6 times.
But when I did the same with

  1000110111011101100

The answer comes out to be 10 but the the number of times I access the array is 12. How do I get to this ? What am I missing out ? Is there a general way to calculate the number of times just looking at the binary value of Index ? Please help me out.

Answering Question 2:

Simply count the number of 1's in the binary value.

This is part of the beauty of Fenwick trees, they're very simple to implement. The whole algorithm for finding the sum up to some index i is:

sum = 0
while i > 0:
    sum = sum + f_tree[i]
    i = i - (last set bit of i) // remove last set bit
return sum

At each step, we remove the last set bit from the index. Intuitively, the total amount of iterations is equal to however many set bits there are. You can find this in $O(\log i)$.

Answering Question 1:

Yes you do need to remove the last set bit. That is implicit on the structure of the tree.

Let's say the last set bit of some index $i$ is bit $r$ (e.g. if $r = 0$ it is the least significant bit). The value in the Fenwick Tree at index $i$ is "responsible" for the sum of all values $[(i - 2^r + 1) \dots i]$.

Now let's say index $i$ has set bits $\{r_0, r_1, \dots r_k\}$, that is, $i = \sum_{j = 0}^k 2^{r_j}$. We can then get the sum up to index $i$ in segments (iterations of the sum algorithm). Let $S_n$ denote the range that the accumulating some covers after the $n$th iteration.

$$\begin{align}
S_0 & = [(i - 2^{r_0} + 1) \dots i]\\
S_1 & = [(i - 2^{r_0} - 2^{r_1} + 1) \dots (i - 2^{r_0})] + [(i - 2^{r_0} + 1) \dots i]\\
& \vdots\\
S_k & = [1 \dots 2^k] + \dots + [(i - 2^{r_0} - 2^{r_1} + 1) \dots (i - 2^{r_0})] + [(i - 2^{r_0} + 1) \dots i] \\
S_k & = [1 \dots i]
\end{align}$$

Example

This may be easier to visualize with an example. Take your first one for instance:

  001100100100100011$_2$ = 51491$_{10}$

I'm not going to go through all the math, I encourage you to do that. This is, in short, how it would work out with a total of 7 iterations.

$$\begin{align}
S_0 & = [51491 \dots 51491]\\
S_1 & = [51489 \dots 51490] + [51491 \dots 51491]\\
& \vdots \\
S_6 & = [1 \dots 32768] + \dots + [51489 \dots 51490] + [51491 \dots 51491]\\
S_6 & = [1 \dots 51491]
\end{align}$$

A lot of this information came from this Topcoder Article on Binary Indexed Trees. I would highly recommend reading it if you have confusion with Fenwick Trees.


Algorithm for ensuring that each element ends up in its specified range when composing a list I am designing a feature recommendation system and I have encountered an algorithmic problem and I am wondering if any of you know if there are known algorithms to solve this type of issue. In our recommendation system the content recommended can have in its metadata information at what range it should be put. To demonstrate:

Items 1-2 can be put in slots 3-5
Items 3-4 can be put in slot 7-9
Item 5 can be put in slot 1
We are composing 9 element list which (based on content performance) may look like this: [5, 6, 2, 8, 1, 7, 3, 4, 9]

Implementation of this problem has a lot of corner cases (like ranges overlapping and content from 1 range takes the position from another range, thus making the whole result invalid). Do any of you know if there are some algorithms to handle this type of issue?

It would be best if the algorithm had time complexity lower than O(n^2)

Thanks a lot!

Here is my guess at your problem.

There are a bunch of items that you need to place in a vector.

Each item has a set of allowed positions in the vector.

You need to find an assignment of items to positions in the vector.

This is an instance of bipartite maximum matching. On one side you have the items, on the other you have the positions in the vector. You add an edge if the item can be put in the position. A maximum matching is one that puts each item in an allowed position, without collisions.


Fast implementation of basic addition algorithm Write code for a modified version of the Grade School addition algorithm that adds the integer one to an m-digit integer. Thus, this modified algorithm does not even need a second number being added. Design the algorithm to be fast, so that it avoids doing excessive work on carries of zero.

I encountered this question looking over last year's final for my algorithms course. I'm not really sure how to answer it, although it seems like it isn't a very challenging question.

In a positional number system, there is one highest digit; every other has a successor in the set of digits. At the (low-significant) end of the sequence of digits (the integer's representation), there is either one of those other digits, or a sequence of that highest one.


Which algorithm suits this problem best? I have an optimization problem and I'm looking to find an algorithm whitch best fits this. The problem is the following:

There are several points of interest (POI), each has a value (for the user), the distance to each other POI is also known.
Now I want to generate the best tour (ordered list of POIs) with the most value for the user given a maximum distance he has to travel.

At first I was thinking about the knapsack problem where the distance would be the weight. The problem is, the order of the POIs is important and the weights vary according to the POIs already selected (more specifically, they depend on the last POI selected). Another idea is using TSP, where I first need to somehow select the subset of nodes which should be visited.

Does anyone have an idea, which known problem is similar to the one described and/or if there is an algorithm solving this. I'm not looking for an ideal solution, a good approximization is fine as well. Also perfomance is not an issue (for now).

I thought of a method to state this problem completely in terms of metric vertex weights, which could be considered a (very non-standard) kind of TSP.

In particular, look at the following subproblem:

  Given a graph $G=(V,E)$, with an initial vertex $v_0\in V$, a distance function $d : E\rightarrow \mathbb{R}^+$ such that the graph is metric, a function $p : V \rightarrow \mathbb{R^+}$ that assigns points to vertices, a maximum distance $D$, a minimum value $P$ and an integer $k$.
  Determine if there exists a (simple) tour on $G$ starting at $v_0$ of exactly $k$ vertices such that the total distance is less than $D$ and the sum of the points $p(v)$ is at least $P$.

So, we want to find a tour of vertices $v_1,\ldots,v_k$ with total distance at most $D$, so $\sum_{i=1}^{k-1} d(v_i,v_{i+1})\leq D$. Additionally, we want to have enough POI points, so $\sum_{i=1}^{k} p(v_i)\geq P$. We will rewrite to the second condition to be similar to the first.

We can replace the second condition by $\sum_{i=1}^{k} -p(v_i)\leq -P$, but now we have negative weights. Since we have fixed $k$, we can solve this by adding the value $p^* =\max_{v\in V}p(v)$ to every individual point: set $p'(v_i):=p^*-p(v_i)$ and $P':=k\cdot p^* - P$, so we get $\sum_{i=1}^{k} p'(v_i)\leq P'$. Now, $p'(v_i) = p^*-p(v_i)$ is non-negative, and we may assume $P'=k\cdot p^*-P$ non-negative, since we know for sure that we cannot get enough points in any tour of $k$ vertices otherwise.

Now, the difference is that points are assigned to vertices in stead of edges. We solve this by defining $p'(v,w):= \frac{1}{2}(p'(v) + p'(w))$ and now we require $\sum_{i=1}^{k-1} p'(v_i,v_{i+1})\leq P'$. This is still equivalent to the previous condition, as we must leave and enter every vertex on a (simple) tour exactly once. Note that $p'(v,w) \leq p'(v,w)+ p'(u) = \frac{1}{2} (p'(v) + p'(w)) +p'(u) = \frac{1}{2}(p'(v)+p'(u)) + \frac{1}{2}(p'(u) +p'(w)) = p'(v,u) + p'(u,w)$ for any $u,v,w\in V$, since $p'(u)$ is positive. So, the distance $p'$ is metric on $G$, as it satisfies the triangle inequality.

Now, there are no more differences between the pairs $(p',P')$ and $(d,D)$. This means that we can phrase our subproblem as follows: determine if there exists a simple tour of exactly $k$ vertices of length at most $P'$ under metric $p'$ AND of length at most $D$ under metric $d$. I call this the $k$-vertex simultaneous TSP.

Note that this problem, if we assume $(p',P')$ arbitrary, could actually be a lot harder than the current problem. $(p',P')$ is extremely 'regular' for a TSP, since the order in which we visit the vertices doesn't matter for this metric. (which should be the case, since it didn't matter in the original formulation either)

Initially, I thought this approach would lead to a regular TSP problem, but it seemed more unlikely as I wrote it down. Nevertheless, I think the ideas here can be useful in approaching the problem, at least. I don't see a way to 'combine' the different distances for an exact solution, but it might be possible if we are satisfied with an approximation.


Compute unknown matrices that minimize a sum This problem is about working with smart-phone accelerometers.

To calibrate accelerometer, I need to find three unknown matrices T, K and B that minimize this sum:
$$\sum_{i=0}^N(|g|^2 - |TK(a_i + B)|^2)^2,$$
where $a_i$ is a known 3x1 vector and |$g$| is a known constant and unknown matrices are:
$$T = \begin{bmatrix} 1 & t_1 & t_2 \\ 0 & 1 & t_3 \\ 0 & 0 & 1\end{bmatrix},\ K=\begin{bmatrix} k_1 & 0 & 0 \\ 0 & k_2 & 0 \\ 0 & 0 & k_3\end{bmatrix},\ B=\begin{bmatrix} b_1 \\ b_2 \\ b_3\end{bmatrix}.$$

I have read in an article one can solve such problems by Levenberg-Marquardt
(LM) algorithm. Unfortunately I cannot figure out how. Can anyone suggest a solution to this minimization problem? And I need to implement the algorithm in python so if you know any good python library please  name it.

I've found the answer. You can solve such problems using scipy.optimize.root which includes  Levenberg-Marquardt (LM) algorithm.


Divide N sticks among M boys as homogeneously as possible (ignoring order) There are $N$ sticks. $N$ is an integer greater than zero. I want to divide it among $M$ boys. $M$ is also a positive integer. Partitioning $N$ among $M$ is easy, but doing it as evenly as possible is difficult for me to think through. Can someone suggest an algorithm? Similar questions exist on this site, but I could not find an answer that solves this problem, though it is possible that I overlooked something.

EDIT:

The sticks are all homogeneous, the same in every respect. What I mean by "as evenly as possible" is that if there are 6 sticks and 3 boys, the division algorithm should output 2-2-2. If there are 5 sticks among 3 boys, it should output 1-2-2. The disparity between the minimum stick holder and maximum stick holder should be minimized. Ordering does not matter (e.g. 1-2-2 is the same as 2-1-2).

Give some of the boys $\lfloor N/M \rfloor$ sticks (i.e., divide and round down), and some of them $\lceil N/M \rceil$ sticks (divide and round up).  Once you fix those two numbers, that uniquely determines how many boys get $\lfloor N/M \rfloor$ sticks and how many get $\lceil N/M \rceil$ sticks -- do some simple arithmetic, try a few examples, use the fact that $\lceil N/M \rceil = \lfloor N/M \rfloor + 1$ if $M$ doesn't evenly divide into $N$, and you'll work out the general formula.


Implications of polynomial time reductions I'm reviewing for finals and have a sample problem that I think I understand, but would like someone to bless my understanding or smack me and tell me why I'm wrong.

I'm presented with a problem $\Pi$  of unknown complexity class.  If I can transform $\Pi$ to some problem $X$, where $X  \in {\sf P}$, what does that tell me about $\Pi$?

I think allows me to conclude that $\Pi \in {\sf P}$, right? If I can reduce $\Pi$ to another problem that's deterministically solvable in polynomial time, and the transformation itself can be done "easily" in polynomial time, then I can conclude that $\Pi$ is deterministically solvable in polynomial time, and therefore that $\Pi \in {\sf P}$ correct?

Conversely, given the same input, transforming $X$ to $\Pi$ in polynomial time allows me to conclude nothing meaningful, since nothing is known about  $\Pi$ right?

Right, if you have an algorithm A that reduces $\Pi$ to $x$ in polytime, and you can solve $x$ is polytime using some algorithm B, then you can solve $\Pi$ in polytime by applying first A and then B.

Using polytime reductions on a problem in P however is rather boring, since you can solve the instance during the reduction and map every instance of $x$ to either a trivial yes or a trivial no answer. Normally you restrict yourself to logspace reductions for problems from P.


Quadratic Diophantine equation - Polynomial Time Cases In number theory, solving a Quadratic Diophantine equation (a, b, c constants)
$$
    a*x^2+b*y= c
$$ is an NP-Complete problem. Even for a=1, the problem remains NP-Complete.

The solution (x, y) are positive integers.

Query: What are the conditions on values of constants for which solving the problem is Polynomially feasible? Any link to the references?

You shouldn't expect a complete characterization of all parameters that can be solved in polynomial time, but here are two cases where it can be solved in polynomial time:

If $b$ is prime, you can solve this in polynomial time by letting $x = \sqrt{c/a} \pmod{b}$ and then $y=(c-ax^2)/b$.  You can compute modular square roots in polynomial time by standard methods.

If $b$ has known factorization, similar methods can be used (use the Chinese remainder theorem).

Dealing with the requirements $x\ge 0,y \ge 0$ (which were added to the question after I wrote this answer) is more challenging.  When $b$ is prime, you can enumerate both modular square roots and see if either of them leads to a valid solution.  When $b$ is not prime but has known factorization, in the worst case this might require enumerating exponentially many modular square roots (though you might be able to randomly sample a few square roots and hope that at least one will lead to a positive solution).


Trying to solve the recurrence relation by comparing 3 cases of master theorem I am trying to understand how the master theorem is invoked on the following recurrence relation:

$$ T(n) = \sqrt{6006} T(n/2) + n^{\sqrt{6006}}. $$

So basically, I found the following source where they have Master theorem definition defined.

I found the similar solution (See the Link #1 in the comment below) where they are trying to solve the same problem (Problem #c). I

In the solution, they have mentioned the following :

We have :

n0.5logb(a)  =  nlogb(6006)1/2

=  n0.5log2(6006)1/2

and so on and so forth. I am not able to understand how they compared the results with the given equation.

You determine $a$, $b$, and $f$ using pattern matching.

The Master theorem applies for recurrences of the form

$\qquad\displaystyle T(n) = a T(n/b) + f(n)$;

you have

$\qquad\displaystyle T(n) = \sqrt{6006} \cdot T(n/2) + n^{\sqrt{6006}}$.

Just by comparing the two formulae, you determine that

$\qquad\begin{align*}
  a &= \sqrt{6006},\\
  b &= 2, \quad\text{and} \\
  f &= n \mapsto n^{\sqrt{6006}}.
\end{align*}$

Now you go through the three cases and check which applies (if any). See also here.


On maximum independent set of line graphs Are there any special algorithms for maximum independent set of line graphs? Could this special case be in $\mathsf{P}$?

Finding a maximum independent set in $L(G)$ is equivalent to finding a maximum matching in $G$. For more, and a fast polynomial-time algorithm that work for e.g., line graphs, see [1].

[1] Lozin, V.V. and Milanič, M., 2008. On finding augmenting graphs. Discrete Applied Mathematics, 156(13), pp.2517-2529.


Define a finite automaton accepting the language below $\{ w∈(a,b)^\ast | w $ does not contain '$ab$' as a subword $\}$.

About questions like this, I always want to construct the regular expression for it, then convert the regular expression to a finite automata. Is there an easier way? Actually, I dont know the regular expression of it either.

It helps to think of finite automata in terms of their states. That is, think of what should each state represent for designing a finite automaton. In fact, it helps to "be the automaton". For this problem, you could start like, Initially, we are at the "start" state, say S1. Now we see an "a", what do we do? We have matched part of the ab substring, so we now need to check if we get a "b" next in line. So this state "waiting for a "b"" is a new state, say S2. Now at S1, we get a "b". This doesn't change anything, we still haven't got an "a" so we continue to remain in S1, waiting for an "a" to match and move to S2. At S2 if we get a "b", we have an "ab" now, so I move to a new "matched ab" state, say S3. At S2, if we get an "a", then we are still in the "matched a" state, and continue to wait for B. Try to think this way, and you shall probably find it easier to design automata, I found this intuition helpful.


Deterministic linear time algorithm to check if one array is a sorted version of the other Consider the following problem:

Input: two arrays $A$ and $B$ of length $n$, where $B$ is in sorted order.

Query: do $A$ and $B$ contain the same items (with their multiplicity)?

What is the fastest deterministic algorithm for this problem?
Can it be solved faster than sorting them?
Can this problem be solved in deterministic linear time?

You haven't specified your computation model, so I will assume the comparison model.

Consider the special case in which the array $B$ is taken from the list
$$
\{1,2\} \times \{3,4\} \times \cdots \times \{2n-1,2n\}.
$$
In words, the $i$th element is either $2i-1$ or $2i$.

I claim that if the algorithm concludes that $A$ and $B$ contain the same elements, that the algorithm has compared each element in $B$ to its counterpart in $A$. Indeed, suppose that the algorithm concludes that $A$ and $B$ contain the same elements, but never compares the first element of $B$ to its counterpart in $A$. If we switch the first element then the algorithm would proceed in exactly the same way, even though the answer is different. This shows that the algorithm must compare the first element (and any other element) to its counterpart in $A$.

This means that if $A$ and $B$ contain the same elements, then after verifying this the algorithm knows the sorted order of $A$. Hence it must have at least $n!$ different leaves, and so it takes time $\Omega(n\log n)$.


Converge to unknown number with oracle I'm playing a game where I'm trying to estimate an unknown real number $x$.

An oracle exists that will answer the question of "Is a number $y$ greater than or equal to $x$?", to which the oracle will reply either yes or no. The question may be asked an $t$ number of times.

For example, with an unknown $x=9.5$, the oracle will reply yes to $15$ and no to $9$.

What's the best approach to estimate $x$? It's okay to assume my first guess $y_1$ will always be answered with yes (so I always have some "best" guess available), but now I'm tasked with getting even closer to $x$ with my second guess $y_2$, third guess $y_3$, ..., and last guess $y_t$.

I'm not necessarily looking for a solution to this problem, but at least the established name for it so I may do some research. Concepts like optimization, numerical analysis, and machine learning come to mind, but they are large, deep fields, and I'm not quite sure where to turn.

My use case for this algorithm is to discover the optimal frequency to send requests to a service which is frequency-capped by an unknown amount. When I send too fast, I get error responses (oracle says no), and when I'm below the cap, I get success responses (oracle says yes). To keep things focused on the important concept, assume the network has no delay.

For the game you describe, take a look at binary search.  It will find the answer in logarithmically many queries: the logarithm of the search space.  In some cases interpolation search can perform even better.

For the application you mention at the end, take a look at TCP's congestion avoidance algorithm (additive increase, multiplicative decrease), as David Richerby suggests.


How a swapper manipulates entire processes in the operating system? The below-given lines are written in the book of the operating system (Page -307), details of the book are as follows:
OPERATING SYSTEM PRINCIPLES, 7TH ED., Abraham Silberschatz, Peter Baer Galvin, Greg Gagne. Wiley India Pvt. Limited, Nov 27, 2006
"A lazy swapper never swaps a page into memory unless that page will be needed. In the context of a demand-paging system, the use of the term swapper is technically incorrect. A swapper manipulates entire processes, whereas a pager is concerned with the individual pages of a process. We thus use pager, rather than swapper, in connection with demand paging."
Can you please kindly explain how a swapper manipulates entire processes?

One processor can only execute one process at a time. Today processors have several cores/threads in the same chip. Even if you have one core in your processor, the OS needs to swap the entire execution context (the entire process) in order to execute something else and it needs to do it efficiently to prevent latency in rendering.
What is called a swapper here is the part of the OS which does this execution context swap.
For example, on Linux the task_struct is a structure containing the process information. When Linux calls schedule(), the function will determine what process should run next and on what core based on priority. This priority is probably stored in the task_struct.
Paging swapping and process swapping is quite different. Every process has its own page tables.
For example, on x86-32 systems (32 bits systems) you are going to have 2 levels of page table: PDT (page directory table) and PT (page table). The CR3 register contains the address of the bottom of the PDT and the PDT contains addresses of the PTs. Since on most systems pages are 4KB, one PDT, which has itself a size of 4KB, can map up to 4MB. If your PDT is full, it will thus map the whole address space available (4GB) (https://wiki.osdev.org/Paging). A virtual address is separated in chunks representing the offset in respective tables. For virtual address 0xABCDEF12, on x86-32 you have 0xF12 as the offset in the physical page, ten bits as the offset in the PT and the most significant 10 bits as the offset in PDT.
When a process swap occurs, all page tables are kept in memory (RAM) and the actual physical pages are kept where they are. The only thing which changes is the CR3 register which will point to a new address. At this address is another PDT for the new process taking place. The TLB (page cache) needs to be flushed as well.
Page swapping is completely different. It involves taking pages that are on a swap partition on the hard-disk and loading it to RAM. Linux for example works with interrupts to manage page swapping. The CPU was made to throw an exception (or interrupt) and launch a certain interrupt handler when a page fault occurs (when the CPU tried to execute or read data that isn't in RAM). For x86-32, the interrupt number of a page fault is 0xE (https://wiki.osdev.org/Exceptions). When a page fault occurs, the CPU will look in its IDT for the address of the handler (code present in RAM that will run to manage the page fault). The address of the IDT is stored in a special register called the LIDT.
A page fault can occur when the PT contains a page which has the present bit not set. This means that the page is mapped but not present in RAM at the moment. The page fault handler registered by the OS will thus take the page on the hard-disk and load the page to memory and return.
With virtual addressing, each process is considered to have a full 4GB of virtual address space. One core has only one process running and this process has access to the whole 4GB of virtual address space. The same virtual address can point to 2 different addresses in physical RAM. The OS uses this to map the process space to different positions in RAM so that processes don't interlace each other. If physical RAM is full (which is rare nowadays), the OS will place some pages not currently in use onto the hard-disk. I often installed Linux on computers without swap space. I simply considered that RAM would never be full and thus I would not need it.
As an example, Linux uses ELF files as executable files. Very often, the ELF file's code will be mapped to virtual address 0x400000. Every process' code is mapped to the same virtual address. Thus the OS needs to setup its page tables accordingly and needs to determine what process is going to get what part of the available RAM. It is done so that all processes don't interfere with each other or the kernel.
Processes are swapped according to a timer which raises an interrupt after some time. The timer is programmed to a certain time, counts down to 0, then raises a certain interrupt number. The OS will register a handler to that interrupt number which will call a scheduler which will determine what process goes next and reschedule the timer etc. When processes are swapped all registers are stored onto the process' stack and a pointer to the stack is kept in a structure somewhere (https://en.wikipedia.org/wiki/Context_switch).


Counting all $x,y,z$ such that $a[x] > a[y] + a[z]$ Given an array $a$, I want to count all triplets of indices $x,y,z$ such that $a[x] > a[y] + a[z]$.

I can think of two solutions:

Go over all triplets of indices $x,y,z$ directly. This takes time $O(n^3)$ and constant space.
Compute a new array consisting of all sums $a[y]+a[z]$, sort it, and then go over all $x$ and use binary search. This takes time $O(n^2\log n)$ and space $O(n^2)$.

Is it possible to improve on these solutions?

Let me try to sketch a method that counts the triplets by directly counting. Let me first assume that $a$ is sorted. I will also keep $x$ constant for this exposition (and iterate over $x$). For simplicity take $a[x]=0$, so the task is to count $(y,z)$ such that $a[y]+a[z]<0$. We can count the pairs, but not by going over all $n^2$ of them, but by following the "boundary" between negative and positive pairs. This is like counting the number of negative elements in a two dimensional array that is increasing in both dimensions. This seems to be possible in linear time? (for fixed $x$)

As an example we consider the following virtual two-dimensional array; i.e., it is not explicitly constructed, element $(y,z)$ just is $a[y]+a[z]$. We can count the elements $a[y]+a[z]>9$ by "walking" along the "boundary".

$\begin{array}{c|ccccc}
a & 1 & 3 & 4 & 7 & 8 \\\hline
1 & 2 & 4 & 5 & 8 & 9 \\
3 & 4 & 6 & 7 & \color{green}{10}& \color{green}{11}\\
4 & 5 & 7 & 8 & \color{green}{11}& \color{green}{12}\\
7 & 8 & \color{green}{10}& \color{green}{11}& \color{green}{14}& \color{green}{15}\\
8 & 9 & \color{green}{11}& \color{green}{12}& \color{green}{15}& \color{green}{16}
\end{array}$


Give a grammar for words whose number of $a$'s modulo 2 is larger than whose number of $b$'s modulo 2 Given is an alphabet $\Sigma = \{ a, b, c \}$, and a language $A4 =\{ w \mid w \in \Sigma^* \wedge |w|_a \operatorname{mod} 2 \ge |w|_b \operatorname{mod} 2 \}$

whereas $|w|_a$ is the number $a$'s in the word $w$ and $|w|_b$ is the number of $b$'s in $w$.

We should give a grammar (of any type) for $A4$.

I know that the only words that do not belong in $A4$ are the words where the number of $b$'s is odd and the number of $a$'s is even.

I can't seem to be able to give a comprehensive grammar for this without breaking that rule. Any tip would be greatly appreciated.

I know that the only words that do not belong in $A4$ are the words where the number of $b$'s is odd and the number of $a$'s is even.

This characterization of words not in $A4$ is nice. However, what we want is to produce words in $A$. Let us classify the words in $A4$ as the disjoint union of the following 3 pieces.

the words where the number of $a$'s is even and the number of $b$'s is even.
the words where the number of $a$'s is odd and the number of $b$'s is even.
the words where the number of $a$'s is odd and the number of $b$'s is odd.

Now use a distinct nonterminal to represent each piece.

The above hint should be enough to set you moving.

Once you have got your own solution, or you run into another bottleneck, you could mouseover the following to reveal the spoiler.

   To facilitate writing the grammar, we will add a non-terminal to represent the 4-th piece.

 $\quad$4. the words where the number of $a$'s is even and the number of $b$'s is odd.

 Here is the grammar, where non-terminal $S_{i,j}$ represents the words whose number of $a$'s is $i$ modulo 2 and whose number of $b$'s is $j$ modulo 2.

 $S\to S_{0,0}\mid S_{1,0}\mid S_{1,1}$
 $S_{0,0}\to cS_{0,0}\mid aS_{1,0}\mid bS_{0,1}\mid\epsilon $
 $S_{0,1}\to cS_{0,1}\mid aS_{1,1}\mid bS_{0,0}$
 $S_{1,0}\to cS_{1,0}\mid aS_{0,0}\mid bS_{1,1}$
 $S_{1,1}\to cS_{1,1}\mid aS_{0,1}\mid bS_{1,0}$


Restrictions that set binary variable to 1 when integer variable equals x, 0 otherwise I have this problem: I'm building an integer linear program, which I'm going to give to an ILP solver.  I have a binary variable Y which can be either 1 or 0 and an integer variable MONTH which takes integer values 1-12.

I have to give restrictions such that Y = 1 if MONTH = 1, and Y = 0 otherwise.

I don't know how to do this. I can think of a way to make Y = 1 when MONTH = 1, like Y + MONTH > 2, but I can't think of a restriction to make Y = 0 otherwise.

In this case (where the possible sets of values are finite) a graphical approach can work nicely for determining a suitable set of constraints. Draw the points in the set $\{1,\dots,12\}\times\{0,1\}$ in the plane, using $+$ for allowed and $-$ for disallowed combinations:

$\begin{array} & & + & - & - & - & - & - & - & - & - & - & - & - \\
 & - & + & + & + & + & + & + & + & + & + & + & +\end{array}$

Can you find a set of lines separating the $+$s from the $-$s? Note that $Y+MONTH\ge 2$ already take care of the $-$ in the bottom left corner.


string matching vs integer matching How different are string matching and integer matching in terms of time complexity?

I'm asking this especially in relation to Rabin Karp algorithm. Why is it faster to compute hash code for every substring and check for equality of hashcode with the hashcode of the given string than the naive method of just checking if amy of the substrings match with the given string?

Checking whether two 32-bit integers are equal can be done in a single machine instruction.

Checking whether two strings are equal can take a lot longer.  If my two strings are each 100 characters long, then checking whether those two strings are equal might require the equivalent of about 100 machine instructions: I have to check them, character by character.

In asymptotic complexity terms: checking equality of (fixed-precision) integers takes $O(1)$ time, checking equality of strings takes $O(n)$, where $n$ denotes the length of each string.


Converting a function with single parameter to a function with multiple parameters I have been solving some algorithm questions recently and a pattern I have observed in some problems is as follows:

Given a string or a list, do an aggregation operation on each of its elements. Here in each of these elements we apply some recurrence to solve it.

An example of one such problem is below.

Problem: Given n integers return the total number of binary search trees that can be formed using the n integers

To solve this problem, I define a recurrence relation as follows:

f(n) = 1 // if n = 0
f(n) = ∑ f(i) * f(n-i-1) where 0 <= i <= n-1

This works and I get the correct answer however I want to modify the function a bit.

Instead of expressing the function in terms of f(n) I want to express it in terms of f(n, i) so I can remove the summation. However I am unable to do it correctly.

Code

My code to solve the problem by defining the recurrence in terms of f(n) is as follows: (I am aware it can be optimized by DP but that is not what I am trying to do here)

public int f(int n) {
    if(n == 0)
        return 1;

    int result = 0;
    for(int i = 0; i< n; i++)
        result += f(i) * f(n-i-1);
    return result;
}

I want to remove that for loop and instead express the function in terms of f(n,i) instead of f(n).

Question

How to convert the recurrence shown above from f(n) to f(n,i) and remove the summation?

Here 'n' is the size of the list of element and 'i' is the ith element in the list that we choose to be the root of the tree.

You could do it by making the second parameter of your function function like the index of the summation, and recursively increment this parameter as long as $0 \leq i < n$.

$$f(n, i) = \begin{cases}
    1 & \text{if } n =0\\
    f(i, 0)\cdot f(n-i-1,0) + f(n, i+1) & \text{if } 0 \leq i < n\\
    0 & \text{otherwise}\\
\end{cases}$$

Then $f(n, 0)$ gives you the answer you want.


Complexity of membership testing for finite-regular languages A language $L \subseteq \Sigma^*$ is finite-regular if there exists $C$ such that for all $n$, $L \cap \Sigma^n$ is accepted by some DFA with at most $C$ final states.

Given a finite-regular language $A_L$, am I guaranteed that there exists a polynomial-time algorithm $A_L$ that recognizes $L$?  In other words, I want an algorithm such that on input $x$ it returns true or false according to whether $x \in L$ or not, and the running time is polynomial in the length of $x$.  Is this guaranteed?

Note that the number of states of the complete DFA accepting such $L$ may be $O(|\Sigma|^n)$ so any trivial algorithm actually constructing the full DFA would not be polynomial time. However the number of accepting final states is $O(1)$, which leads me to believe there is some shortcut available here.

Thanks to Yuval Filmus for formalizing this language class, and explaining its closure properties.

Finite-regular languages need not even be decidable. Indeed, if $L$ is any language such that $|L \cap \Sigma^n| \leq C$ for some $C$ independent of $n$, then $L$ is finite-regular (you can show this by considering the case $C=1$). In particular, the language $\{ 1^n : \text{ the $n$th Turing machine halts on the empty input} \}$ is finite-regular but not decidable.


Processor Scheduling (SJF / FCFS) So I know that scheduling has been covered in other articles, but because my provided values are different and decimals are used, I am having difficulty wrapping my head around it. I have reviewed all of the other posts already but would like clarification on my specific values if possible.

What is the average turnaround time for these processes with the FCFS scheduling algorithm?
What is the average turnaround time for these processes with the nonpreemptive SJF scheduling algorithm?
The SJF algorithm is supposed to improve performance, but notice that we chose to run process $P_1$ at time 0 because we did not know that two shorter processes would arrive soon. Compute what the average turnaround time will be if the CPU is left idle for the first 2 units and then nonpreemptive SJF scheduling is used. Remember that processes $P_1$ and $P_2$ are waiting during this idle time, so their waiting time may increase.
What is the average turnaround time for these processes with the preemptive SJF scheduling algorithm?

The values (including a make-shift Gantt chart) are as follows:

1. FCFS

\begin{array} {|r|r|}
\hline
P_1 &P_2 &P_3 \\
\hline
0-5 &5-8 &8-9 \\
\hline
\end{array}

Completion times:
$P_1=5, P_2=8,P_3=9$
Turnaround Time = 5.866667

2. Non-PreEmptive SJF

\begin{array} {|r|r|}
\hline
P_1 &P_3 &P_2 \\
\hline
0-5 &5-6 &6-9 \\
\hline
\end{array}

Completion times:
$P_1=5, P_2=9, P_3=6$
Tunaround Time = 5.2

3. Future-Knowledge (Non-PreEmptive SJF with Idle time)

\begin{array} {|r|r|}
\hline
- &P_2 &P_3 &P_1 \\
\hline
0-2 &2-5 &5-6 &6-11 \\
\hline
\end{array}

Completion times:
$P_1=11,P_2=5,P_3=6$
Turnaround Time = 6.2

4. PreEmptive SJF (SRTF)

\begin{array} {|r|r|}
\hline
P_1 &P_2 &P_2 &P_3 &P_1 \\
\hline
0-0.4 &0.4-3 &3-3.4 &3.4-4.4 &4.4-9 \\
\hline
\end{array}

Completion times:
$P_1=9,P_2=4.4,P_3=3.4$
Turnaround Time = 4.133333333

Hopefully these values are correct. If they are not, could you please explain the process so that I can understand how to properly calculate it myself? Thank you in advance for any assistance!

1. FCFS

Turnaround Time T T = 5.866 is correct.

2. Non-PreEmptive SJF

T T = 5.2 is correct.

3. Future-Knowledge (Non-PreEmptive SJF with Idle time)

T T = 6.2, I'm not sure about this.

We never get a future knowledge of how big the next process will be.

4. PreEmptive SJF (SRTF)

Here, your scheduling is wrong.

$P_2$ arrives at time 1.4, how can you schedule it at time 0.4?

Refer below scheduling:

\begin{array} {|r|r|}
\hline
P_1 &P_2 &P_3 &P_2 &P_1 \\
\hline
0-1.4 &1.4-3 &3-4 &4-5.4 &5.4-9 \\
\hline
\end{array}

T T ($P_1$) = 9 - 0=9
T T ($P_1$) = 5.4 - 1.4=4
T T ($P_1$) = 4 - 3 =1
Avg T T = 4.6

Dont you see the improved TT of one over other.

FCFS = 5.8 > NON-PRE SJF = 5.2 > PRE SJF =4.6


Dynamic programming and multiple optimal solutions I have tried researching how I can handle multiple optimal solutions based using dynamic programming. The answer is found from this question is simply that you have to backtrack. What if this is not possible and one of my solutions can't be found this way?

From this YouTube video we are given the problem of finding the optimal rod cuttings for maximizing profit.

The rod has a length of $n=5$, and the possible ways to cut with its respective values in parenthesis are $1(2)$, $2(5)$, $3(7)$ and $4(8)$. By setting up a matrix as in the video we end up finding that the optimal solution is $12$. By backtracking this we are only able to find one of the solutions $1,2,2$ and not the other solution consisting of $2,3$.

My question is, how can I combine dynamic programming with some sort of best sequence sum algorithm so that I am able to backtrack both solutions? The algorithm he proposes uses the max of the previous subproblem, however, that might not be the only solution as a combination of the current subproblem might also be feasible.

The matrix proposed in the video looks like this (rows are the possible cuts and columns are the rod length):
$$
\begin{bmatrix}
    0 & 2 & 4 & 6 & 8 & 10 \\
    0 & 2 & 5 & 7 & 10 & 12 \\
    0 & 2 & 5 & 7 & 10 & 12 \\
    0 & 2 & 5 & 7 & 10 & 12 \\
\end{bmatrix}
$$

Assume you already computed the dynamic programming table DP[SIZE][LENGTH] where DP[s][l] stands for maximum profit that can be obtained by using cuts up to size s on a rod of length l. You want to find all decomposition to get the value DP[SIZE][LENGTH], to do this notice that at every step DP[s][l] we have two options, use the cut of size s or don't use it (possibly using both values we get optimal answer). The pseudo code will look like this:

PROFIT[s] = value of using a cut of size `s`.

def find_answers(s, l, partial_answer):
    """ Populate in `partial_answer` possible ways to
        partition a rod of length `l` using cuts of
        size up to `s` and report them.

        `partial_answer` is a multiset that will contain all cuts
        done so far.
    """

    # Base case when length is `0`.
    if l == 0:
        report partial_answer

    best = DP[s][l]

    # If not using the cut of size `s` gets a profit as good
    # as best expected profit, find solutions.
    if DP[s - 1][l] == best:
        find_answers(s - 1, l, partial_answer)

    # Try to find an answer that uses current cut size if `s` is
    # less than current length, and profit using this cut is as good
    # as best expected profit.
    if s <= l and DP[s][l - s] + PROFIT[s] == best:
        find_answers(s, l - s, partial_answer + {s})

Call this function like find_answers(SIZE, LENGTH, {}) with an empty multi-set as partial_answer. Since it is doing backtracking it is possible to get to the same state (s, l) several times with different partial_answers. This function will call report partial_answer exactly once per valid decomposition, also notice that the number of optimal decomposition can be exponentially large.


Recognizing primitive recursion I am trying to write a program to recognize if a given lambda calculus expression is primitive recursive. I believe that a general algorithm to do this does not exist, but I am interested in the most general algorithm. This is a subset of the primitive recursive functions in the LC.

Primitive recursion is built up from the following rules: "http://safalra.com/lambda-calculus/partial-recursive-functions"

To outline some of these rules

(λfx. x) is zero
(λnfx. f (n f x)) is successor
etc...

Now in my program I can just recognize these axioms directly. My confusion is what happens when I get to things derived from them. Take the number 5 for example encoded as (λs.(λz.(s (s (s (s (s z))))))). This is the result of applying the the successor function to zero 5 times. But the above expression is not one of the axioms. I believe that the rule set says that the result of primitive recursive functions are also primitive recursive, but I do not see how given one of these results the result can be shown primitive recursive.

What I mean is that given just the encoding of the number 5 how can I show that it is primitive recursive? That is without brute force search building up from the axioms. Also is my method of representing the primitive recursion axioms correct (for suc and zero) or are the axioms not that literal? Thanks!

I found this post on stack exchanges CS theory section:

https://cstheory.stackexchange.com/questions/20364/how-to-make-the-lambda-calculus-strong-normalizing-without-a-type-system

It is very similar to what I was looking for.


Dynamic Programming formulation for hotel problem There are n hotels given at a0, a1, ..., an such that 0 < a0 < a1 < ... < an. The only places you are allowed to stop are at these hotels, but you can choose which of the hotels you stop at. You must stop at the final hotel (at distance an), which is your destination. Moreover, you are required to complete your journey in exactly d days (i.e have to make d-1 stops in between). If you travel x miles during a day, the cost for that day is x^2. You want to plan your trip so as to minimize the total cost - that is, the sum, over all travel days, of the daily cost. Find the optimal sequence of hotels at which to stop.

I came up with this dp solution:

Let dp(i) be the minimum cost such that the last stop is hotel i.
Base case: dp(0)=0.

To compute dp(i), I consider all possible places 0<=k<i, that we might have stopped before. Thus, the recurrence relation becomes:

for i=1;i<=n;i++
  dp(i)=inf
  prev(i)=undefined
  for k=0;k<i;k++
    if (dp(i)>dp(k)+(ai-ak)^2)
      dp(i) = dp(k)+(ai-ak)^2)
      prev(i) = k

How do we make sure that this algorithm takes exactly d stops?

Start with yinnosanders algorithm, then try to get faster than $O (n^3)$ in typical cases:

With your cost model, travelling a total distance of x miles in d days costs at least $x^2 / d$. If you could stop anywhere you like, you would travel $a_n / d$ miles every day.

First find a reasonably good set of stops: On each day, when there are d' days left, you pick the hotel whose distance is closest to the remaining distance, divided by d'. This gives you an upper limit L for the cost of the optimal journey.

Now jinnosanders suggests that you calculate dp(i,j). But first we calculate a lower limit for the cost of any journey that involves stopping at hotel i on day j: The cost would be lowest if you drove the same distance on each of the first j days, and the same distance on the remaining last days. The cost is at least $a_i^2 \space/\space j\space+\space(a_n - a_i)^2/(d-j)$. If this cost is higher than the upper limit L for the best solution that we found earlier, then there is no need to calculate dp (i, j) and we set dp (i, j) = infinity instead.

We will have dp (j-1, j-1) ≥ dp (j, j-1) ≥ dp (j+1, j-1) ... so when we calculate dp (i, j), we stop when dp (i-n, j-1) = infinity. This should work considerably faster than O (n^3) in typical cases if the hotels are reasonably close to equidistant.


Is data received after transmission immediately stored and can that be recovered? When I send a message from one device to another, during the process during which the other device is receiving the data, is that data stored temporarily on some place on the device or is it immediately stored on the hard-drive of the device. and while using TCP when you receive an ACK does this mean that that data has been stored on the hard drive or is it stored when everything is received. For example, I am sending an essay to a server which makes a download link for another person and then send that link back to me, for sharing. Now during the process of sending that essay on the server I cancel halfway, so can I determine whether the essay was stored on its main drive or not (just an example).

Briefly, communication between two hosts/peers on a network occurs by means of network sockets. Roughly a socket is pair (IP,PORT) of numbers which uniquely identifies a host on a network. So, when a host A sends data to another host B on the network, B listens to a corresponding port for incoming data. Data (payload) comes byte-by-byte and when one byte of data riches destination B gets notification. At this point it is up to the application what to do with data: to store it on the hard drive or in memory. Nothing is stored in HDD or on some other device by default.

As for "sending an essay to a server" your are talking about file transfer protocols, in particular file uploads. Whether your file was stored on the server depends on the underlying protocol. For example recently people have started talking about resumable file upload protocol.

Your questions say that you should start learning from basic TCP/IP and HTTP protocols, and move towards more advanced and specific protocols depending on your tasks.


Prove that an $n$-length string has $2^n$ i18n-style abbreviations An i18n-style abbreviation is one in which multiple letters are shortened to that number of letters. E.g., "internationalization" -> "i18n" ("nternationalizatio" is substituted with its length 18). Other abbreviations include "in17n", "i17on", "in16on", etc. I see a pattern in which words with at least 3 characters have $2^{n-2}-1$ different abbreviations. E.g.,

hat - h1t (1 possible abbreviation)
code - co1e, c1de, c2e (3 abbreviations)
words - wor1s, wo1ds, wo2s, w1rds, w1r1s, w2ds, w3s (7 abbreviations)
active - acti1e, act1ve, act2e, ac1ive, ac1i1e, ac2ve, ac3e, a1tive, a1ti1e, a1t1ve, a1t2e, a2ive, a2i1e, a3ve, a4e (15 abbreviations)

The pattern is apparent, but how do I prove that this is the case?

The proof should be easy once you've modeled the problem sufficiently precisely. Your examples demonstrate some assumptions about possible abbreviations that you don't describe in the accompanying text.

The first and last letter are always kept unchanged. For example, hat can only be abbreviated h1t (or left unabbreviated).
If successive letters are abbreviated, then they must all be included in the same number. An equivalent way to state this is that you cannot have consecutive numbers in an abbreviation. For example, code cannot be abbreviated as c11e: if both the o and the d are abbreviated then the number 2 must be used to replace them both together.
You seem to waver as to whether the original word counts as a (trivial) abbreviation. I'll include it as an abbreviation in my answer.

Under these rules, an abbreviation is uniquely determined by the set of letters to abbreviate. A letter that can be abbreviated is determined by its position, which is an index between $2$ and $n-1$ where $n$ is the number of letters in the word. Therefore, for a word of length $n \ge 2$, the set of possible abbreviations is uniquely determined by the set of indices in the range $[2,n-1]$ to abbreviate. In mathematical terms, there is a bijection between abbreviations of a given word of length $n$ and the set of all subsets of $[2,n-1]$.

The set of integers $[2,n-1]$ has $n-2$ elements. The set of its subsets $\mathscr{P}([2,n-1])$ has $2^{n-2}$ elements. Given the bijection above, the number of abbreviations is also $2^{n-2}$.

Follow-up exercise (significantly harder): some of these abbreviations are useless, in that they are no shorter than the original. There is one trivial abbreviation where all the letters are kept, but there are also abbreviations which involve the replacement of a single letter by 1, such as h1t (no shorter than hat) or a2i1e (no shorter than a2ive). How many abbreviations actually shorten the word?


Algorithm to check that one sum is less than another Suppose that we have two sums:
a1+a2+...+an,
b1+b2+...+bm
We can perform only two binary operations on operands of these sums:

lt (less than)
eq (equal)

These operations can return 3 possible results: true, false, unknown. Other operations like summation, subtraction and etc. are not allowed.
The question is how to implement algorithm for function lt(a1+a2+...+an, b1+b2+...+bm), that also returns true, false or unknown? But unknown can be returned only if there is no enough information to return true or false.
For example if we know that (n=m=3 && a1 < b3 && a2 = b2 && a3 < b1) the algorithm have to return true.
Or if we know that (n=3 && m=2 && a1 < b1 && a2 < b1 && a3 < b2 && b1 < b2) the algorithm have to return unknown.

I will assume your variables can take on arbitrarily real numbers.  Build a weighted directed graph that represents all known inequalities, with one vertex per element (i.e., $n+m$ vertices in total).  In particular, apply 'eq' and 'lt' to all ${n+m \choose 2}$ pairs of elements.  Then:

If $x < y$ (i.e., $\textsf{lt}(x,y)$ returns true), where $x,y$ are two elements, add a directed edge $x \to y$ with length $-1$.

If $x \le y$ (i.e., $\textsf{lt}(y,x)$ returns false), add a directed edge $x \to y$ with length 0.

If $x=y$ (i.e., $\textsf{eq}(x,y)$ returns true), then add directed edges $x \to y$ and $y \to x$ with length 0.

If $x\ne y$ (i.e., $\textsf{eq}(x,y)$ returns false), do nothing and add no edges.

Let $d(x,y)$ be the length of the shortest path from $x$ to $y$ in this graph.  If $d(x,y)=c$, then we will be guaranteed that $x \le y + c$, and this is the optimal $c$ for which this is true (i.e., it is the smallest $c$ for which this is true).
Compute a new bipartite graph $G$  with an edge $a_i\to b_j$ of length $d(a_i,b_j)$ for each $a_i,b_j$.  This can be computed with the Floyd-Warshall algorithm, for example.
Find the minimum-weight perfect matching in this bipartite graph.  This is an instance of the assignment problem, and hence can be solved in polynomial time with standard algorithms.  If the total weight of the matching is $w$, then we can conclude that
$$a_1+\dots+a_n \le b_1+\dots+b_m + w.$$
Consequently, if $w \le 0$, then we can conclude that $a_1+\dots+a_n \le b_1+\dots+b_m$ and we can return "true" to the original question.
Solve another assignment problem for the bipartite graph with edges $b_j \to a_i$ of length $d(a_i,b_j)$ for each $a_i,b_j$.  In this way, we obtain $w'$ such that
$$b_1+\dots+b_m \le a_1+\dots+a_n + w'.$$
If $w' \le 0$, return "false" to the original question.
Otherwise, return "unknown".
This takes $O(nm)$ calls to the binary operations and $O((nm)^{2.5} \log n)$ running time.
This works for this very specific problem.  A more general approach is to use linear programming: if you want to check whether $(I_1 \land \cdots \land I_k) \implies J$, where the $I$'s and $J$ are linear inequalities, then check whether the system of inequalities $I_1 \land \cdots \land I_k \land \neg J$ is satisfiable using linear programming.  This will let you support more general mathematical expressions and more general relationships between the variables, as long as they are all linear functions/inequalities of the variables.  In your problem, after you call 'lt' and 'eq' on all pairs of elements, each operation that returns something other than "unknown" gives you an inequality or equality $I_i$ on two variables.  Here $J$ is the inequality $a_1+\dots+a_n \le b_1+\dots+b_m$.  So, you could apply linear programming directly to your problem.  This approach also supports more general operations, as long as they are all linear.
My answer above essentially solved the linear programming problem for the special case where $I_1,\dots,I_k$ are all inequalities with a difference of two variables, and $J$ has the form $a_1+\dots+a_n \le b_1+\dots+b_m$.  I used a standard data structure for representing differences of two variables (the graph), and then combined it with an algorithm for the assignment problem to capture the one additional inequality with multiple variables.


Questions on Sipser's NP implying verifiability? I've revisited trying to understand the proof to why NTM exists iff there is a verifier. I think I'm finally understanding the proof but I want to make sure and thus have some questions as follow up along with to check if I'm understanding.

For the forward implication (there exists a verifier $V$ and we want to show this implies the existence of an NTM $N$), we can, according to Sipser, "Nondeterministically select string $c$ of length at most $n^k$. Then we run $V$ on input $(w,c)$ and accept if $V$ accepts, otherwise reject." I'm wondering if $V$ would be run as part of the algorithm on each branch of $N$. In other words, for any node in the computation tree of $N$, the verifier will be run on the that current string, and the branch will produce a YES answer only if the verifier accepts that string. Am I understanding this correctly? So it would run concurrently, and since the verifier runs in $O(n^k)$ and the NTM runs in $O(n^q)$, then this still runs in polynomial time if the verifier is run at every step in the computation.
For the backward implication, we assume $A$ is decided by a polynomial time NTM and construct a polynomial time verifier $V$. When we say that $A$ "is decided by" $N$, does this mean that $N$ is correctly able to determine if any given branch of computation results in accept or reject? This feels a bit cyclic to me, since we are trying to construct the verifier $V$ given $N$. I don't see how $N$ could decide $A$ without $N$ having a verifier constructed already. In other words, without a verifier, how would the NTM know if it should accept/reject on any of its given branches?

Essentially, yes. Though I usually find it easier to think of nondeterministic machines as guessing what to do. So, as the machine runs, it starts by repeatedly doing the following: either it guesses that the current string is good, and verifies it, or it guesses what the next character should be, and it repeats. Thus, if there's some string that the verifier will accept, some sequence of guesses will lead to the machine producing that exact string and then deciding to verify it, so the machine will accept. (Also, the machine needs to keep track of how long the string is, so it can stop if it gets too long.)

We have a nondeterministic Turing machine $N$ and the guesses it makes lead it down some path of the tree of possible computations. If that path ends in an accepting state, the machine is defined to accept its input; if no path ends in an accepting state, it is defined to reject. There's no circularity: that's just the definition of what it means for a nondeterministic machine to accept or reject.
From this machine, we build a verifier. The input to the verifier is a description of a computation path, and the verifier checks that each action taken on that path is a thing that $N$ could do in that state, and that the path ends in an accepting state. If those conditions are met, the verifier has verified that $N$ really would accept the given input.


How to Construct a Lattice from Program Statements In order to optimize a program, I am trying to figure out how the idea of a lattice applies to data-flow graphs, as introduced by this presentation (first diagram below). The lattice seems to take a program, order its inputs and outputs, and allow for easily determining flow of variables and state, so you can perform verification and optimization. But I am not sure how to construct the lattice from the program statements.

In this question I would like to know how to construct the lattice from the program.

Specifically, given a program such as this:

var x = 10
var y = 20
var z = 0
var i = z
while (i < x) {
  y = y + x * i
  i = i + 1
  z = y + i
}

We can construct a Control-Flow Graph (CFG) where each node is a program statement such as var x = 10. From that we can construct a Data-Flow Graph (DFG) where we are keeping track of how a variable is used. This creates an def-use ordering, along the lines of:

x, y, i at the same time
z comes after i
...

That's where I start getting lost. But once we have a partial ordering, somehow a lattice is created. Finally from the lattice, we can do things such as doing pointer analysis (Figure 2) and computing fix-points (Figure 3). That will help in optimization and verification of the program.

I'm wondering only the first part, how to construct the lattice from the example program above. Wondering what is needed to construct the lattice at a high-level. I understand the upper and lower bounds of a lattice, which seems to correspond to CFG inputs and outputs being joined, but I don't quite see how to actually do the join (meet), what the nodes/vertices are in the lattice (not sure if it's a single program statement, a variable, or what), and what the edges are in the lattice. Once that is defined, then doing the rest of the stuff should be straightforward. Thank you for your help.

^- Figure (1).

^- Figure (2).

^- Figure (3).

There is no such thing as a "DataFlow Graph lattice".  Those are two separate things.  A data flow graph is a graph that represents how data flows in a program, which can be helpful in data flow analysis.  A lattice is a mathematical object that can be helpful for data flow analysis.

Data flow analysis is a broad subject.  There are many techniques for data flow analysis (many use lattices, but it's not a hard requirement).  They don't all use lattices in the same way.  So, there's no one way to do the conversion you are referring to.

To learn more about the subject, I suggest reading a good textbook on program analysis.


Does every computational problem have a decision version? Is the following claim correct?:

  Every computational problem has a decision version of roughly equal computational difficulty.

If the above claim is correct, please give a reference for it.

(I find this pdf from Prof. E. Demaine, but he doesn't provide any references.)

Here is a "counterexample": sorting. The natural decision version of sorting is deciding whether a given array is sorted. Another natural decision version is given an array and a permutation, decide whether the permutation correctly records the sorted order of the array. In both cases, the "decision versions" can be solved in linear time, while sorting itself (in most models) requires loglinear time.

Here is another "counterexample": consensus. This is a classical problem in distributed computing. I'm not sure it has a "decision version".

The claim you are stating is not a mathematical claim; it's just a comment whose goal is to explain why in introductory classes we only consider decision problems. There are three reasons: First, decision problems can be used to analyze many other types of computational problems (though not all of them). Second, it has become conventional to consider only decision problems (for example P and NP are classes of decision problems). Third, introductory classes are introductory, and so their scope is limited.

In order to make the claim a mathematical claim (and so, potentially, right or wrong), you will need to define all the concepts involved; there might be several ways of doing it, resulting in different interpretations of the claim. Some interpretations will result in valid statements: for example, optimization problems have canonical decision problems, and to some extent the two kinds of problems are equivalent in complexity. Other interpretations might be more problematic, for example if they encompass my first counterexample. Another source of difficulty is computational problems like my second counterexample to which this entire paradigm seems inapplicable.

Lecturers often make such comments, and these are supposed to be helpful for you as a student. If you find one of these comments confusing, I think it's best to just ignore it. If you have access to the professor, you can discuss the matter with them, but otherwise just drop the matter.


A question about the definition of PRFs Let $\mathcal{F} = \{ f_{s} \}_{s \in \{\, 0,1 \,\}^{*}}$ be a family of computable functions, where $f_{s} \colon \{\, 0,1 \,\}^{|s|} \rightarrow \{\, 0,1 \,\}^{|s|}$.

We define a family of functions $\mathcal{H} = \{ h_{s} \}_{s \in \{\, 0,1 \,\}^{*}}$, where $h_{s} \colon \{\, 0,1 \,\}^{|s|} \rightarrow \{\, 0,1 \,\}^{|s|}$ and $h_{s}\left( \cdot \right) = f_{s}\left( f_{s} \left( \cdot \right) \right)$.

Let $F_{n}$ ($H_{n}$) be the distribution of functions $f_{s}$ ($h_{s}$), where $s$ is uniformly distributed over $\{\, 0,1 \,\}^{n}$. And let $R_{n}$ denote the uniform distribution over the set of all functions from $\{\, 0,1 \,\}^{n}$ to $\{\, 0,1 \,\}^{n}$.

We know that for any PPT adversary $A$, if for all $n$,
$$\left\vert \Pr\left[ A^{F_{n}}\left( 1^n \right) = 1 \right] - \Pr\left[ A^{R_{n}}\left( 1^n \right) = 1 \right] \right\vert \leq \epsilon (n)$$
then $\mathcal{F}$ is a family of PRFs. And if $\mathcal{F}$ is a family of PRFs, then $\mathcal{H}$ is also a family of PRFs.

How about $A$ can only can query the oracle of a function sampled only one time? In other words, if
$$\left\vert \Pr\left[ A\left( F_{n} \right) = 1 \right] - \Pr\left[ A\left( R_{n} \right) = 1 \right] \right\vert \leq \epsilon (n)$$
holds true, can we get that
$$\left\vert \Pr\left[ A^{F_{n}}\left( 1^n \right) = 1 \right] - \Pr\left[ A^{R_{n}}\left( 1^n \right) = 1 \right] \right\vert \leq \epsilon (n)$$

PS: The title may not clear enough, but I don't know how to make it better :(. Thanks for anyone helping me to make it better :).

Let $F_n$ be a random involution induced by a random perfect matching on $\{0,1\}^n$. For any input $x$, the distributions of $F_n(x)$ and $R_n(x)$ are almost identical (in fact, $F_n(x)$ has the same distribution as $R_n(x)$ conditioned on the event $R_n(x) \neq x$, which occurs with probability $1-2^{-n}$), so they are statistically indistinguishable. However, $H_n$ is the identity function, so it is easy to distinguish from a random function.

With some more work, it might be possible to extend this from one query to any fixed polynomial number of queries.


Question is about a paper "A Block-sorting Lossless Data Compression Algorithm" by M. Burrows and D.J. Wheeler In the paper A Block-sorting Lossless Data Compression Algorithm by M. Burrows and D.J. Wheeler Link.
On page number 5. please describe this line

  If the original string $S$ is of the form $Z^p$ for some substring $Z$ and some $p > 1$, then the sequence $T^i[I]$ for $i = 0,...., N - 1$ will also be of the form $Z'^p$ for some subsequence $Z'$.

F.e. string "abc" becomes "bca" after BWT. This means that "abcabc" will transform into "bbccaa", i.e. "external repetition" of entire string will lead to "internal repetition" of each char in transformed string.


Data structure for or-lookups over bit-field associations maps For a mapping between a bit-arrays and values I want cheap lookups using bitwise-or instead of equality.

Slightly more formally, I have a set of associations $k_i \mapsto v_i$ where $k_i \in \mathcal{P}(\mathbb{N})$ is a set of naturals and $v_i$ can be of any type $T$. A query on $q \in \mathcal{P}(\mathbb{N})$ matches pairs $(k_j,v_j) \in \mathcal{P}(\mathbb{N}) \times T$ such that $k$ overlaps with $q$ (ie $q \cap k \neq \varnothing$). Also the maximum element $M$ encountered in any $k_i$ is bounded, typically not larger than 5k and each $k_i$ is small $|k_i| \ll M$, ie the bitfield corresponding to the set $k_i$ would be sparse.

I imagine it could be a tree or a heap with (bitfield,a) values at the leaves and at each node a bitfield that is the bitwise-or combination of all bitfields in it's subtree? I failed to find any literature on the subject. Any pointers?

Preprocessing: For each $(k_i, v_i)$ pair, and for each $x \in k_i$, add $(x, (k_i, v_i))$ to a map data structure (e.g., a hashtable) with $x$ as the key.
To process a query $q$, for each $y \in q$ look up all values in the map, append all of them to a list, and finally remove duplicates (or instead add them directly to a data structure that can collapse duplicates immediately, like a hashtable).


Is the langauge of (descriptions of) DFAs that accept $\Sigma^*$ decidable? Is $L = \{\langle A\rangle\mid A\text{ is a DFA and }L(A) = \Sigma^*\}$ decidable?

I know that $L'=\{\langle A,w\rangle \mid A\text{ is a DFA and }w\in L(A)\}$ is decidable, but I'm not sure if this is related.

It's decidable. Think about what an DFA's accepting states must look like if it accepts every possible string. That property is very easy to check.


Understanding the algorithm behind day of week calculation I came across this algorithm recently to calculate day of the week for any year.

int y0 = year - (14 - month) / 12;
int x = y0 + y0/4 - y0/100 + y0/400;
int m0 = month + 12*((14 - month)/12) - 2;
int d0 = (date + x + (31*m0)/12)%7;
switch (d0) {
    case 1: return "Monday";
    case 2: return "Tuesday";
    case 3: return "Wednesday";
    case 4: return "Thursday";
    case 5: return "Friday";
    case 6: return "Saturday";
    case 0: return "Sunday";
}

How does this algorithm work? I see a lot of magic numbers in calculations above, but its difficult to understand the intuition behind this algorithm

As mentioned in a comment, this program is a variant on Zeller's congruence.

Here are the steps:

It's good to know that the Gregorian calendar (which is what we are using) repeats every 400 years. In the 400 year cycle, every fourth year is a leap year except for the centuries other than the one at the start of the cycle. In other words, in the 400-year cycle starting 2000 and ending 2399, there are 97 leap years: all the years divisible by 4 except 2100, 2200 and 2300.

There are 365 days in a normal year, which is 52 weeks and one day. A leap year has an extra day. So the 400-year cycle, which has 303 normal years and 97 leap years, is 52*400 weeks plus (303 + 97*2 = 497) days. 497 days is exactly 71 weeks, so the cycle is an exact number of weeks, which means the weekday for a given date is the same for the "same date" in every cycle. (The same date meaning the same day, month and year mod 400.)

Since we're only interested in which weekday a date is, and not the total number of days since some determined starting point, we can do all computations mod 7. So if we know the weekday for some particular date, we can find the weekday for the same day/month in another year by adding the number of years and then the number of intervening leap days.

int x = y0 + y0/4 - y0/100 + y0/400;

y0 is explained below; if you think of it as the number of years from the beginning of (some) 400 year-cycle, then x is just the number of years plus the number of leap years: y0/4 (every fourth year) - y0/100 (except for centuries) + y0/400 (other than the centuries which start a cycle). If we had computed y0 as years into the current cycle, we could have avoided the y0/400 term.
The fact that a leap day falls into the middle of a year complicates that computation. To make it simpler, we start the cycle at March 1 instead of January 1, effectively moving January and February to the previous year. That puts the leap day at the end of the year, so we can evaluate the number of leap days by counting the number of leap years, as above. As we'll see below, this also has the advantage of making the alternation of month lengths more regular; aside from February, months more or less alternate between 31 and 30 days.

int y0 = year - (14 - month) / 12;
int m0 = month + 12*((14 - month)/12) - 2;

Those lines are trying to way too hard to be clever, and end up being terrible because of the slowness of division (even though division by 12 can be performed with multiplies, and even though the compiler can figure out that it's only necessary to do it once. The code would be clearer and faster if it were written in the obvious way:

int y0 = year, m0 = month - 2;
if (m0 < 1) { ++y0; m0 += 12; }

Essentially, we now have a weekday offset of March 1 in the specified year from the March 1 which starts the cycle. Now we just need to figure out the adjustment for the months between March and the specified month. Each of these months will move the weekday by either two (30 mod 7) or three (31 mod 7) days. Months mostly alternate between 31 and 30 days, except although sometimes there are two 31-day months in a row. (As mentioned above, we can ignore February here because we're only counting months which come before the specified date, and with February shifted to the end of the year, it is never before any date in the year.)

int d0 = (date + x + (31*m0)/12)%7;

(31 * m0) / 12 for m0 in the range [1, 12] produces the sequence {2, 5, 7, 10, 12, 15, 18, 20, 23, 25, 28, 31}. The adjacent differences in that sequence are {3, 2, 3, 2, 3, 3, 2, 3, 2, 3, 3} which happen to correspond to the lengths of the months (mod 7) starting at March. (The pairs of consecutive 3s correspond to July/August and December/January.) So adding this to the year adjustment x and the date in the month date and then reducing the sum mod 7 gives us the day in the week with the week starting three days before March 1 of (every) cycle. (Three days before because (1) the magic formula (31 * m0) / 12 starts with 2, not 0, and (2) the day of the month starts with 1, not 0. So the formula is off by 3.)

This is not the only way of performing this calculation. As it happens, exactly the same sequence is produced with (13 * m0 - 1) / 5. Either way, the cleverness is not justified by efficiency; division is a lot slower than a simple table lookup:

/* Not optimal but it corresponds to the above computation */
static const char month_adjust[] = {
    2, 5, 7, 10, 12, 15, 18, 20, 23, 25, 28, 31
};
int d0 = (date + x + month_adjust[m0]) % 7;

The above table could be reduced to three bits per month, since only the value mod 7 is important. That means that the lookup table could be replaced with a magic integer constant and a bit-shift, but the potential gain is probably insignificant. I'll leave the details as an exercise for would-be code golfers.
March 1 of every cycle is a Wednesday, and that needs to correspond to the value 3 of that computation. The mapping between modulo and day of the week is provided by the switch statement:

switch (d0) {
    case 1: return "Monday";
    case 2: return "Tuesday";
    case 3: return "Wednesday";
    case 4: return "Thursday";
    case 5: return "Friday";
    case 6: return "Saturday";
    case 0: return "Sunday";
}

I would have used a lookup table instead of a switch, which leads to more direct code:

static const char* weekdays = {
    "Sunday", "Monday", "Tuesday",
    "Wednesday", "Thursday",
    "Friday", "Saturday"
};
return weekdays[d0];


Difference between decision tree and rule based reasoner I am new to this topic, and in some scientific papers I've been reading about prediction in sports I encountered the term rule based reasoner. Is it this term the same as a semantic reasoner( where the two main directions are forward and backwards chaining?). If yes, can you point out the difference between a decision tree and this? Because for me, it seems pretty much the same.

Decision tree classifiers could be easily converted to rule based classifiers in data mining and vice Versa. please have a look at "Introduction to Data Mining", chapters 4 and 5.

Usually it depends on the data characteristics, how to choose between these two methods and which of the mentioned methods give you smaller classification errors.


Find path from s to t that goes through another node w If you have directed and unweighted graph G how could you find a path from node s to node t that also goes through another node w? This could be a non-simple path.

If you don't care about simplicity, a path from $s$ to $t$ that goes through $w$ is just a path from $s$ to $w$ concatenated with a path from $w$ to $t$.


Two-color hitting set Let $n,m$ be a positive integer with $m\ge 2n$. In the set $M=\{1,2,\dots,m\}$, some elements are black and others are white. Given $2n$ nonempty subsets of $M$, the task is to determine whether there exists a subset $T\subseteq M$ consisting of $n$ black and $n$ white elements such that each of the $2n$ subsets has a nonempty intersection with $T$. Can this be done in polynomial time?
Without the color constraint, this is very similar to the hitting set problem. Choosing a subset $T$ of size $2n$ without the color constraint is easy, by choosing one representative from each of the $2n$ subsets and, if the union of these representatives has size less than $2n$, fill in with arbitrary remaining elements of $M$. But having $n$ black and $n$ white elements is not always possible, for instance if there are not enough elements of one color.

Can this be done in polynomial time?

No, it cannot (unless P equals NP, of course).
Consider the case where all the $2n$ sets only contain elements that are colored (say) black. Finding a "white-black hitting set" with $n$ pairs is now exactly the same as finding a regular hitting set with n elements.
A reduction from Hitting Set

Find a set of at most $k$ elements that hits all sets in the collection $\mathcal{C}$, where $\mathcal{C} = r$

to your specific scenario

Find a set of $n$ pairs of white and black elements that hits all sets in the collection $\mathcal{C}$, where $|\mathcal{C}| = 2n$

follows easily. The only extra thing to take care of is if $2k < r$ (just add $r-2k$ black elements to $M$ and make each one a singleton set, now $n = r-k$), or if $2k > r$ (just take some arbitrary set $C\in \mathcal{C}$, add $2k-r$ extra elements to $M$ and, for each one make a set containing the union of it and $C$).


Making a finite automata How can I make a finite automaton which does not end in string ab.

With the alphabet a,b

I made 3 states. For the first one it is accepting states and thus accept the empty string.

So here is a table I made. State 1 is initial state

        input   goes to state input goes to state

State 1

         b       1             a      2

state 2

          b       3             a       2

state 3

            b       3              a      3

But will it work?

Here is your suggested automaton, if I understand your transitions correctly (initial state is 1)

This automaton will only accept $\epsilon$, and words consisting of a number of $b$'s

Hints to make one that accepts your language:

Make sure that it accepts $\epsilon, a, b$ and make sure that you "move away" from accepting states when seeing a $b$ after an $a$ (keep in mind that $aabb$ is also a string in the language, i.e the second $b$ should make the machine go to an accepting state).


Hamiltonian circuit for a family of graphs For $\Sigma = \{a,b\}$, let $S_n = \{w\mid w \in \Sigma^{*} \land |w| = n\}$.

Let $C_n \subset \Sigma^{*}$ be the language of circular strings that contain as substrings all elements of $S_n$.
For instance,  $bbaaaababaabbbba \in C_4$

I have formulated the problem of finding the subset of $C_n$, formed by the circular strings with the smallest size ($=2^n$), as the problem of finding all hamiltonian circuits on the graph that has the elements of $S_n$ as vertices, and edges connecting all pairs of vertices $s_i$ and $s_j$ such that $s_i = xw$ and $s_j = wy$, with $w \in \Sigma^{n-1}$ and $x,y \in \Sigma$.

For the example above, the graph could look like this:

My question:

  Would there be a polynomial-time solution for the hamilton circuit problem restricted to this family of graphs?

This graph is known as a de Bruijn graph, and its Hamiltonian circuits are known as de Bruijn sequences. Both are well understood (for example, we know exactly how many of these exist).


Performance differences between Go-Back-N and Selective Repeat ARQ protocols? This is what I know:

GBN weakness is the fact that when the window size is too large, the number of packets in the pipeline grows and one packet error causes the retransmition of many packets unnecessarily.
Selective Repeat solves this by acknowleding just the suspicious packets, which sightly makes performance better, but if a wrong window size is chosen, then the reciever doesn't know if a packet is being retransmitted or another packet is being sent by first time.

So, back to the question, what other important performance differences exists between these protocols?

If GBN is used in tandem with AIMD for congestion avoidance, the network link will experience a large amount of latency when a packet is lost. This is because the AIMD CA mechanism will typically wait for a timeout before declaring the packet that hasn't been received as being dropped. Also, the timeout wait-time will occur every time because of the nature of GBN to send cumulative acknowledgments. Worse still, the pipeline will decrease drastically every time this occurs, causing the network to incorrectly gauge congestion.

Once you contrast the above scenario with the SR instead of GBN, it becomes apparent that the window size is no longer really an issue when compared to the latency due to the lost packets in the pipeline. However, SR handles the scenario well since it acknowledges every packet. Thus, the pipeline grows at a favorable rate (as dictated by the AIMD CA) without having unnecessary decreases in the length of the pipeline.

More differences come to light when a congestion avoidance / prevention mechanism is presented.


L1 and Ln cache: when are they written? I have been following the "High Performance Computer Architecture" course from Georgia Tech (also on YouTube), and unless I've missed something, I cannot see where the following has been explained:

If I have a multilevel cache, L1/L2/L3/Ln:

1) what decides what level of this hierarchy a block fetched from memory initially gets put in?

2) If I evict a block from L1, does that mean it gets moved to L2 (replacing a block from L2 depending on the replacement policy), and so forth for L2 to L3, and L3 to Ln, until the block evicted from the last level cache gets written to memory?

PS And yes, I have searched for this, so don't downvote assuming I haven't :)

Update

After the answer given below, I went back to the video course and found this.  It seems to suggest that data is initially fetched into the L2 cache, then "fed" to the L1 cache.  This also shows how, without the inclusion bit set, L1 and L2 can become "out of sync".

3) Is this generally what happens in all caches?  IE if I have a 7 layer cache, will the block be fetched into L7, then fed L7->L6, L6->L5 ... and finally L2->L1?  This seems like a lot of work...

4) Except in the situation shown in the linked video (if the caches get "out of sync" then certain data will only be available in one cache even though it started out in both caches), it seems that having the same data in multiple levels of the cache all the time (i.e. when the inclusion bit is set) is a waste; we have to copy it amongst all the levels.  This can't be the case though, so what am I missing?

1) Usually any accessed data are saved into L1, independent whether they were previously available in L1, L2... or memory only.

For exclusive cache, data are stored ONLY in L1, for inclusive one, in the entire hierarchy. There are also mixed strategies. Also, some CPUs have "victim cache", which is extra cache level which gets ONLY data moved out of LLC (last level cache).

2) Yes, for write-back exclusive cache.

3) You misunderstood his explanation. He said that data are fetched and placed to both caches. Inclusion, btw, isn't the "bit set", but entire cache policy. The policy is built right into the hardware.

4) Exclusive cache better use precious space, but each time you have to bring new block into L1, you have to displace some block to L2, then some one to L3... and finally some one to memory. This means a lot of work. With inclusive cache, you just drop data from L1 cache, or replace older copy in L2 with newer copy displaced from L1.

As result, exclusive strategy is more optimal when adjacent cache levels has closer sizes (f.e. <=4x) and inclusive is better when sizes are very different.

More info at en.wikipedia.org/wiki/Cache_inclusion_policy


Prove that the language $L_1 = \{a^ib^{2i}c^j \;|\; i,j ≥ 0\}$ is context-free Prove that the language $L_1 = \{a^ib^{2i}c^j \;|\; i,j ≥ 0\}$ is context-free.

I have a grammar like this but there are some strings that are not be able to be generated

$$\begin{align}
S &\to aSbb \;|\; C \\
C &\to cC \;|\; \epsilon
\end{align}$$

One example is the string $abbc$ cannot be generated.

You've almost got it. Consider that $L_1$ is simply the concatenation of $L_a$ and $L_c$, where $L_a = \{a^ib^{2i} \;|\; i ≥ 0\}$ and $L_c = \{c^j \;|\; j ≥ 0\}$, since the two parts of each sentence are independent of each other.

That should suggest a grammar which starts with the production $L\to AC$, and which then proceeds to define $A$ and $C$ in the obvious way.