How to improve the CPI and Speed up factor in CPU-OS simulator? I am using the CPU-OS simulator by Besim Mustafa(https://www.merlot.org/merlot/viewMaterial.htm?id=476196) and I am studying Pipeline Stages. I have written a simple program and captured the metrics like CPU Clocks, CPI, Instruction Count, Speed Factor.
My question is what changes should I make to improve the CPI and Speed Factor.

To be able to improve CPI and the speed-up factor you need to enable the pipeline. The programmer can help improve CPI but it is best to leave that to an optimising compiler and clever CPU architecture. The simulator's built-in compiler offers some help in reducing the CPI, for example loop unrolling, constant folding, identifying code dependencies, etc. In pipelined architecture, the goal is to reduce/prevent hazards and the above optimisations help do that. In addition, the pipeline has a means of forwarding operands, i.e. prior to previous instructions updating registers in a later stage, that contributes to reducing the CPI. There is also the technique of jump predictions. All these are available in the simulator which you should explore.


Rank of random binary matrix subset I have a problem that smells like it is NP-complete, but at the same time it feels like maybe you can solve it by just keeping track of column-wise Hamming distance or something, or that it's equivalent to some spanning tree-like problem. The problem is as follows.

We have some binary matrix $M \in \mathbb{F}_2^{n\times k}$ with rank $n$. Let $S_i$ be the matrix constructed by sampling the rows of M $i$ times without replacement. I would like to find

the expected rank of $S_i$
a vector $x \in \mathbb{F}_2^k$ such that appending $x$ to $M$ prior
to sampling will maximize the expected rank of $S_i$.

Any ideas on sources that cover similar problems would also be appreciated.

The Whitney rank polynomial, an analog of the well-known Tutte polynomial of graphs, enumerates the number of subsets of a matroid of given size and rank. It can be computed using a deletion-contraction recurrence essentially the same as the recurrence for the Tutte polynomial. You can find the details in Welsh's Matroid Theory, §15.4. From the rank polynomial it is easy to read off the expected rank of $S_i$.

Granted, this algorithm takes exponential time, which is not necessarily better than direct counting. Computing the coefficients of the rank polynomial is #P-hard, which suggests that computing the expectation might be hard as well. You can estimate it to your heart's content by sampling, though.


Efficiently determine relative ordering between two elements in a PO-set What algorithms/heuristics exist for efficiently determining the relative order between two elements in a partially ordered set?

In my case, the PO-set is stored as a directed acyclic graph where an edge is an happened before relation and I am streaming live data into this PO-set. Nodes usually have less than 5 backward edges, with 1 being the most common, and there will be at most 10^6 nodes. The newly inserted nodes usually have edges to the previously most recently inserted nodes.

I am usually doing this query just after I've added a node to the graph, to find the relative ordering between the inserted node and a few select other nodes, so the traversal paths tend to overlap a lot. I am also maintaining a total order of the PO-set as I go, which might be useful for this as well.

My current solution consists of starting at both nodes and moving backwards one step at a time from both simultaneously (or rather, one step for the left node, then one step for the right) until I find a common ancestor node, or run out of edges to traverse. This is not very fast, but I don't have that many elements in the set yet so it works for now.

The main problem is the worst case runtime of O(n) as n will grow in the future. Is there a way to do this faster?

This is the dynamic reachability problem for DAGs, where you only need to handle vertex/edge insertion (but not deletion).  It's sometimes known as incremental reachability or incremental DAG reachability.

There's lots written in the research literature on the subject.  Here are some pointers to get you started:

https://cstheory.stackexchange.com/q/18787/5038
https://cstheory.stackexchange.com/q/14343/5038
https://cstheory.stackexchange.com/q/5176/5038
https://cstheory.stackexchange.com/q/29/5038
https://en.wikipedia.org/wiki/Dynamic_problem_(algorithms)
https://en.wikipedia.org/wiki/Dynamic_connectivity (though this seems to talk about undirected graphs, rather than directed graphs)


Do exponents have higher time complexity than factorials? My professor said exponentials will always have higher time complexity compared to polynomials. My question is, do exponentials also have higher time complexity than factorials?

I plotted a chart in Matlab to check it myself.

When range of x is small, from 1 to 10, I get the following chart,

%Matlab script
x  = [1 : 10];
y1 = factorial(x);
y2 = exp(x);

plot(x', [y1',y2']);
title("N! vs e^N");
legend("O(n!)", "O(e^n)");

Here factorial is clearly beating exponential.

But when I bump the range of x from 1 to 1000, I get the following chart,

x  = [1 : 1000];

Here exponential is clearly beating factorial.

So, can I say conclusively that exponentials will always have higher time complexity than both factorials and polynomials?

-

In fact $e^n$ is $o(n!)$. We could show it using the Stirling approximation by taking limit
$$\lim_{n\rightarrow \infty}{\frac{e^n}{(\sqrt{2\pi n})(\frac{n}{e})^n}} = \lim_{n\rightarrow \infty}{\frac{e^{2n}}{(\sqrt{2\pi n})n^n}} = \lim_{n\rightarrow \infty}{\frac{1}{\sqrt{2\pi n}}\frac{e^{2n}}{n^n}}$$
Since $\lim_{n\rightarrow \infty}{\frac{1}{\sqrt{2\pi n}}} = 0$ we only need to calculate
$$\lim_{n\rightarrow \infty}{\left(\frac{e^2}{n}\right)^n}$$
The function $\frac{e^2}{n}$ decreases faster than any function $c^n$ where $0 < c < 1$ for sufficiently large $n$s (as $n$ goes to infinity), and so $\lim_{n\rightarrow \infty}{\left(\frac{e^2}{n}\right)^n} = 0$.
Regarding Quazi Irfan's comments about Matlab graph
I am not a Matlab user, but these are plots for $e^x$ and Stirling approximations of $n!$ using Wolfram script: plot (1\sqrt(2*pi*x)*(x/e)^x) from 0 to 6, plot(e^x) from 0 to 6

As you see $n!$ overtakes $e^n$ when $n=6$.


Building a context-free grammar for this language I have a hard time creating a context-free grammar for the language

$$L=\{(a^n)^*(b^m)^*y\mid y\in\{a,b\}^*,\ |y|=n+m \}\,.$$

Any help breaking down the problem is appreciated, since I'm getting nowhere with this one...

I'm not sure to have fully understood your notation.

As production rules you could consider:

$S \rightarrow aSa \ |aSb \ | S_1 | \epsilon$

$S_1 \rightarrow bS_1a | \ bS_1b \ | \ \epsilon$

In $S$ for each $a$ you add an $a$ or a $b$ or you can go to $S_1$ and then never come back to $S$ again.

In $S_1$ for each $b$ you add an $a$ or a $b$.


Numerically validate CRC performance Koopman, P., & Chakravarty, T. (2004, June). Cyclic redundancy code (CRC) polynomial selection for embedded networks. In Dependable Systems and Networks, 2004 International Conference on (pp. 145-154). IEEE.

In this paper authors compare performance of different CRC polynomials in terms of minimum Hamming distance of two codes with the same checksum.

The naive method of doing this would require enumerating all codes that have the same checksum. This is computationally intractable for 2048 bit long data words that authors consider - so they must have used some more more efficient technique.

I did not find a mention in the paper on how the authors computed it. But it would be interesting to know the method as it would allow to numerically verify optimality of used CRC polynomials on given data word size.

What algorithm authors used to compute minimum HD for given CRC polynomial on long data words?

There are multiple techniques to compute the minimum Hamming distance for a given CRC polynomial.  I don't know what technique they used, but here are three techniques that seem suitable.

I will assume the problem is as follows:

Given a CRC polynomial $p(x)$, determine whether there exists a $d$-bit error pattern of length $n$ that isn't detected.

This is equivalent to asking whether there exists a word of length $n$ with Hamming weight $d$ whose CRC is zero; or whether there exists a polynomial $q(x)$ of degree $n$ and weight $d$ such that $p(x)$ divides $q(x)$.

Method #1: Exhaustive enumeration

One can enumerate all words of length $n$ and Hamming weight $d$, and check each one to see if that error pattern would be detected.  This involves checking ${n \choose d}$ possibilities, which is feasible if $d$ is small and $n$ is not too large, but rapidly becomes infeasible for larger parameters.

For instance, their Table 1 lists results for $n=48$ and $d=1,2,3,4,5,6$.  These are feasible to compute by exhaustive enumeration.  For instance, for $n=48$ and $d=6$, we have ${48 \choose 6} \approx 2^{37.3}$, and it's feasible to do $2^{37.3}$ computations on a computer in a reasonable amount of time.

As another example, for $n=2048$, it's feasible to compute results for $d=1,2,3$.  We have ${2048 \choose 3} \approx 2^{32.4}$, which isn't too large.  However, ${2048 \choose 4} \approx 2^{44.6}$ which is feasible but uncomfortably large.

Method #2: Meet-in-the-middle

We can speed up method #1 using a trick.  The trick reduces the amount of computation time to something like $\sqrt{{n \choose d}}$, at the cost of requiring much more space (memory).

Note that the CRC is linear.  Suppose there exists a data word $x$ of weight $d$ whose CRC is zero.  We can express $x$ as $x=y \oplus z$ (where $\oplus$ denotes the xor), where $y,z$ each have weight $d/2$.  Then by the linearity of the CRC, the CRC of $x$ is the xor of the CRC of $y$ and the CRC of $z$.  So, if we want to search for an $x$ whose CRC is zero, it suffices to search for $y,z$ whose CRC xors to zero -- i.e., to search for $y,z$ that have the same CRC.

Now the method becomes this.  We enumerate all data words $y$ of length $n$ and weight $d/2$, compute their CRC, and store them in a hashtable (or sorted list) keyed on the CRC.  Next, we enumerate all data words $z$ of length $n$ and weight $d/2$, compute each one's CRC, and look up that CRC in the hashtable to look for matches.  This will require $2 {n \choose d/2}$ CRC computations and ${n \choose d/2}$ space.  Note that ${n \choose d/2}$ is roughly $\sqrt{{n \choose d}}$, so this is a big reduction in the running time.

If $d$ is not even, then we split into $y$ of weight $(d-1)/2$ and $z$ of weight $(d+1)/2$, so the running time is ${n \choose (d+1)/2}$ and ${n \choose (d-1)/2}$ space.

Of course, we can trade off memory for space, so we can find an algorithm with running time ${n \choose d_1}$ and space ${n \choose d_2}$ for any $d_1,d_2$ such that $d_1+d_2=d$.

As an example, for $n=48$ and $d=6$, there is an algorithm with ${48 \choose 3} \approx 2^{16.1}$ running time and ${48 \choose 3} \approx 2^{16.1}$ space -- easily computable on a computer.  As another example, for $n=2048$ and $d=4$, the running time is $2^{21}$ and the space is $2^{21}$ -- again, easily feasible.  For $n=2048$ and $d=5$, the running time is $2^{32.4}$ and $2^{21}$ space, which is again easily feasible.  So this readily explains how one could compute the results in Figures 1-2.

(In fact, it turns out you can speed up this method by a small additional factor, at the price of an exponentially small probability of error.  There are many ways to split $x=y \oplus z$, so in some sense the above method is doing more work than necessary.  An optimization is to require that $y$ be zero in the last $n/2$ bits and $z$ be zero in the first $n/2$ bits, and search for such a split.  This reduces the running time and space to ${n/2 \choose d/2}$ time and space.  However, there is no guarantee that $x$ can be split in this way.  So, instead, we pick a random subset $S \subseteq \{1,2,\dots,n\}$ of $n/2$ positions, and we require $y$ to be zero in all bit positions of $S$ and $z$ to be zero in all bit positions of $\overline{S}$, and we search for any solution.  Then, we repeat this again multiple times with multiple different random choices of $S$.  If there is a solution, then we have about a $1/\sqrt{\pi d/2}$ chance of finding it, so after $O(\sqrt{d})$ repetitions, there is an overwhelming chance that we find it.  This provides a speedup by about a factor of $\Theta(2^{d/2}/\sqrt{d})$, at the cost of some implementation complexity.)

Method #3: Discrete logs in finite fields

Finally, there is one more method, which involves a lot more implementation complexity and requires knowledge of finite fields.  Given $p(x)$, we'll try to determine whether there exists a polynomial $q(x)$ of degree $n$ and weight $d$ such that

$$q(x) \equiv 0 \pmod{p(x)}.$$

We can think of this as working in the finite field $\mathbb{F}_{2^m}$ where $m$ is the degree of $p(x)$.  Note that there are fairly efficient algorithms for computing the discrete log in $\mathbb{F}_{2^m}$ when $m$ is not too large (as is the case for CRC polynomials, where typically $m \le 32$).  We can think of any polynomial as an element in this finite field.  For example, we can think of the degree-1 polynomial $x$ as an element in the finite field.

We'll use a subroutine for computing the discrete log of an arbitrary polynomial $s(x)$, to the base $x$.  In other words, given $s(x),p(x)$, this subroutine returns us a number $k$ such that

$$s(x) \equiv x^k \pmod{p(x)}.$$

Now we'll split $q(x)=r(x)+s(x)$ where $r(x)$ has weight $d-1$ and $s(x)$ has weight $1$.  If $q(x) \equiv 0 \pmod{p(x)}$, it follows that

$$r(x) \equiv s(x) \pmod{p(x)}.$$

Thus we'll enumerate all possible polynomials $r(x)$ of degree $< n$ and weight $d-1$, and for each, we will compute the discrete logarithm of $r(x)$ to the base $x$.  If the resulting discrete log, call it $k$, is less than $n$, we have found a valid $s(x)$ of weight $1$ and thus $q(x) = r(x) +  x^k$ is a multiple of $p(x)$ with degree $<n$ and weight $d$, so we have found a valid solution.  If the resulting discrete log is $\ge n$, we discard this possibility $r(x)$ and continue enumerating other values of $r(x)$.

The running time is ${n \choose d-1}$ computations of a discrete log and $O(1)$ space.  This is unlikely to be better than Method #2 except for very large values of $n$ and small values of $d$, but there are some parameter settings where it might be probably faster than Method #2.


How unallocated memory space is represented? I'm doing C programming stuff, and I'd like to know little bit about memory management - My problem is that I'm not understanding where the computer (or the OS or the programs) stores the information related to allocated space and how the unallocated space information is processed and how it is reported as a runtime error.

I did many searches but didn't find any information about this stuff yet. Can anyone try to explain, or recommend any book or online course?

Each page of RAM is typically a 4k block, with a set of privileges on it such as read, write, or execute. Broadly speaking, the memory manager for the operating system will allocate a bunch of pages for OS related storage, and when a program launches, it will allocate initial RAM, and as more items are allocated, the program will ask the operating system for more RAM.

From the program's point of view, the RAM is all contiguous. However, under the hood, the operating system is mapping the various blocks of system RAM, and each program's RAM.

Physically, the RAM is broken up into blocks, which are essentially unorganized, but the operating system itself has a table mapping what block belongs to each program.


PSPACE languages reducible to other PSPACE languages in polynomial space Intuitively it makes sense that all PSPACE languages are reducible to other PSPACE languages in polynomial space. But how would I go about actually showing this?

The same way that you show that any problem in P is polytime reducible to any other, or that any decidable language is Turing reducible to any other: solve the problem in the reduction.

Note that the claims (yours in the question and mine above) aren't quite true for many-one reductions, since you can't reduce any other language to $\Sigma^*$ or $\emptyset$ using many-one reductions.


Formalizing self-propagating behaviour Since reading Ken Thompson's Reflections on Trusting Trust I am trying to formalize the idea of a program which mutates its own behaviour; specifically, a program that would be self-reproducing except that it would reproduce itself with a mutation. With this definition I wish to differentiate this kind of program from self-reproducing programs and will call them programs with self-propagating behaviour (due to the nature of propagating its own mutations). I am familiar with Hoare Logic, LTL, CTL, and CTL*, but am unsure what to use for the formulation since Hoare Logic requires a concrete implementation of a program and I am trying to represent not a program but a kind of program, and am also unsure if/how I could express this idea in LTL, CTL, or CTL*.

I don't have time for an elaborate answer right now, so here is just a quick braindump: Program logic does not restrict to concrete programs. Given e.g. a pair $(A, B)$ of pre/post-conditions, you can think of this pair as defining a set of programs

$$
\{ P \ |\ P\ \text{is a programs such that}\ \models A[P]B \}
$$

Here are a couple other references that might be useful.

J. Von Neumann, Theory of Self-Reproducing Automata.
F. Cohen, Computer Viruses - Theory and Experiments.
S. Kramer, J. C. Bradfield, A general definition of malware.
G. A. Kavvos, Theories of Computer Viruses: 30 Years Later.
L. M. Adleman, An abstract theory of computer viruses.
G. Jacob, E. Filiol, H. Debar, Formalization of viruses and malware through process algebras.
J. L. England, Statistical physics of self-replication.

As the kind of program you envision is a form of meta-programming, I suggest also to look at this field (which is primarily implementation-driven and lacks substantial theory as of 2017). Here are some references, none of which is likely to be directly relevant, but will eventually lead to research that should be:

M. Berger, L. Tratt, Program Logics for Homogeneous Meta-Programming
S. N. Artemov, L. D. Beklemishev, Provability Logic.
G. Japaridze, D. de Jongh, The logic of provability.
S. Artemov, Explicit Provability And Constructive Semantics.
J. Alt, S. Artemov, Reflective λ-Calculus.


Prove the MinAveCodeLen of a product information source is less than the sum of that of the multiplicand and multiplier source? The product of 2 independent sources $(S_A,P_A)$ and $(S_B,P_B)$ is defined as

$$
(S,P)\text{ s.t. }S = \{s_As_B|s_A\in S_A,s_B\in B\}\text{ and }\ P(s_As_B) = P_A(s_A)\cdot P_B(s_B)\,\forall s_A\in S_A,s_B\in S_B
$$

and the MinAveCodeLen is the minimum average codeword length which is equal to the average codeword length of a Huffman coding.

The problem is to prove

$$
\mathrm{MinAveCodeLen}(P)\leq\mathrm{MinAveCodeLen}(P_A)+\mathrm{MinAveCodeLen}(P_B)
$$

The original problem is quite confusing. I am asked to prove $H(P_A)+H(P_B)=H(P)$ in the previous part, so I was trying to relate the problem with $H$ at first with no progress.

It's so wired that again, I'm answering my own question... I have to admit I am not confident at all when confronted with constructive proof problems.

An encoding scheme for ${P}$ could be described graphically as follows: Suppose $T_A$, $T_B$ are 2 Huffman trees for ${P}_A$ and ${P}_B$ respectively. For each leaf $s_{Ai}$ in $T_A$ replace it with $T_B$, i.e.

Letting $|S_A| = q,|S_B| = q$, the average code word length of this coding scheme is
$$C = \frac{\sum l_{Ai}+l_{Bj}}{pq} = \frac{q\sum l_{Ai}+p\sum l_{Bj}}{pq} = \mathrm{MinAveCodeLen}({P}_A)+\mathrm{MinAveCodeLen}\mathbb{P}_B)$$
where $l_{Ai}$, $l_{Bj}$ are the codeword length of $s_{Ai}$ and $s_{Bj}$ in the Huffman code corresponding to $T_A$, $T_B$. Therefore,
$$\mathrm{MinAveCodeLen}({P})\leq C\leq\mathrm{MinAveCodeLen}({P}_A)+\mathrm{MinAveCodeLen}({P}_B)$$


Why substituting the search part in INSERTION SORT doesnt yield a running time of $\Theta(nlgn)$ $$
\Theta - Tight \ asymptotic \ bound
$$

If we change lines $5-7$ in Insertion sort

With BINARY-SEARCH(A,p,r,v)

Why don't we get a running time of $\Theta(n\lg n)$ as we go through the array $\Theta(n)$ and then do a binary search $\Theta(\lg n)$?

You still need to shift $O(n)$ elements to make room for the newly inserted element even if you find the correct position in $O(\log n)$.


How does TLC check liveness properties? The paper "Model Checking TLA+ Specifications" published in 1999 explained how TLC (Temporal Logic Checker) checks safety properties written in TLA+ developed by Lamport. At that time, TLC did not yet check liveness properties.

Today, TLC is able to check liveness properties. I want to know:

What liveness properties is TLC able to check?
How does TLC check liveness properties?

Any references?

Presumably it can check any "liveness" property that that can be formulated in LTL. A "liveness" property is typically described as a property stating that "something good eventually happens". This is usually contrasted to a "safety" property which states that "nothing bad ever happens". See e.g. Slide 20 of this SPIN tutorial. Basically, a basic safety property will look like $\square P$ which states that it is always the case that $P$ holds, e.g. the temperature is always below boiling. A basic liveness property  might look like $\lozenge Q$ which states that $Q$ eventually happens, e.g. eventually the HALT state is reached.

A seminal paper is An Automata-Theoretic Approach to Automatic Program Verification. The idea is to use a Büchi automaton, which is just a normal finite state automaton with a notion of acceptance that works on infinite words. The key result is that you can turn an LTL formula into a Büchi automaton that accepts exactly the computations that satisfy the LTL formula. A model checker takes your specification and produces a Büchi automaton, then it takes the LTL constraint, negates it, and produces a Büchi automaton for it. Finally, it intersects the two Büchi automata and endeavors to show that the resulting automaton accepts nothing, i.e. describes the empty language. It does this by conceptually (and to a large extent actually) enumerating all the states. In practice, the state space is way too large to be completely enumerated and this is why model checkers are not theorem provers.

So what's the issue with "liveness" properties that would cause them not to be included from the beginning? To check (the failure of) $\square P$ in a model checker is straightforward. You simply check $P$ for each state. If $P$ ever fails to hold, then you've found a counter-example to $\square P$. On the other hand, checking $\lozenge Q$ requires producing a trace that will never hit a state satisfying $Q$. There are two ways this could happen. First, we could reach a final state without ever going through a state satisfying $Q$. This is straightforward to check. Second, we could enter an infinite loop without ever reaching a state satisfying $Q$. To check this, we need to check if we reach a state that this particular trace has been to before without ever passing through a state satisfying $Q$.

It's the "this particular trace" that is problematic. For safety properties, it is enough to visit each state. How you get to a state for the most part doesn't matter. You'll want to keep track of which states have been visited to avoid (potentially infinite) repeated work, but it doesn't matter which trace visited a state. For liveness properties, it is not enough to know that some trace has visited a state. You need to know if this trace has visited that state. The upshot is that checking a safety property just requires enumerating the reachable states, while checking a liveness property requires cycle detection. Of course, there are linear-time algorithms for calculating strongly connected components.  Due to the sheer number of states, transcribing textbook algorithms is often not adequate. You can see an indication of some of the issues here. As far as I can tell from the source code and that page, TLC does just do Tarjan's algorithm, but this interacts poorly with distribution (i.e. liveness checking is not supported in the distributed mode) and with symmetry reduction techniques to reduce the state space. It is also just inherently slower than checking safety properties.


What machine learning techniques work on ASTs? I am interested in experimenting with machine learning on the ASTs of programming langauges (e.g. some Java code). I would like to develop an algorithm that determines if a given AST satisfies some predicate. I have a training set of programs that do and do not satify the predicate.

The machine learning techniques that I am aware of operate on vectors or matricies. Are there techniques that operate on trees?

Your problem can be solved by existing machine learning methods. So, instead of searching for new technique you should choose from existing techniques. The main part of your problem which separates it from general machine learning problems is AST data which will act as input to your algorithm.

There are a lot of feature extraction techniques available which will help you convert AST data into usable format. I would suggest doing tree traversals to generate a feature vector from your AST and then applying machine learning techniques on it.


How to extent primitive recursion from natural numbers to finite strings? Primitive recursion seems to be related to bounded quantification. It is easier to make sense of bounded quantification with respect to natural numbers than to make sense of bounded quantification with respect to finite strings.

A relatively clean way out of this dilemma could be a two sorted language with both natural numbers and finite strings, and some basic functions between the two sorts, like the lengths of a string, or the string where one symbol is repeated n times.
A nicer solution could be to avoid the need for natural numbers, and work with some more native finite string related concepts, like head/tail, substring, ... instead.

I wonder whether there exist a robust computational model (on finite strings) corresponding to primitive recursion, just like Turing machines represents a robust computational model (on finite strings) corresponding to general ($\mu$-) recursion.

You don't really need to do anything. Without loss of generality, let $\Sigma = \{0, \dots, d-1\}$.  A string in $\Sigma^*$ is (almost) just a natural number written in base-$d$. The only problem is that leading zeroes are significant in strings but not natural numbers so we instead associate the string $w_1\dots w_k\in\Sigma^k$ with the base-$d$ natural number that's written $1w_1\dots w_k$. The length function is just a suitably rounded logarithm, which is primitive-recursive anyway.

(The first way you'd try to compute a base-$d$ logarithm would probably be to use a while loop to repeatedly divide by $d$. But you can replace that with a for loop, since we know that $\log_d n\leq n$.)


Unsupervised anomaly detection: assigning the clusters to normal and anomaly Having a unsupervised algorithm done on a dataset (e.g. K-means), how can I determine which cluster is normal and which is anomalous (for 30 clusters, for example)?

If the dataset contains normal traffic much more than anomalies (99%), then the radius of clusters associate to normal traffic is bigger. Is this true? Why?

If so, then we set the clusters with greater radius to normal according to a threshold. The smaller the threshold, the more the detection rate and the more the false alarm rate. Is this true?

Could a labeled dataset help determine the normal clusters? For example, finding the closest point to the centroid of a given cluster and checking whether it is labeled anomaly or not?

[1] uses Cluto software and its mountain visualization graph that I can't understand why its 3D, having feature space of dimension 41.

Reference:
[1] Jose F. Nieves, Data Clustering for Anomaly Detection in Network Intrusion Detection

The radius depends on the number of clusers you choose. The more clusters, the smaller the radius.

If you have labelled data, you could eliminate the outliers/anomalies for determining the threshold radii for your clusters. For example you could take the greatest distance from the cluster center to its members (smaller radius for higher detection rate as stated in your question).

This question is closely related to the question Anomaly/outlier detection using fuzzy clustering. I am reposting my answer:

As far as I know there is no unique definition for what is an outlier/anomaly. Therefore you'll have to decide by yourself what the characteristics of outlying data points in your data set are. This could be for example: distance to the cluster center (threshold), local neighbourhood (a data point that has no/few data points in its neighgbourhood might be an outlier) or statistical characteristics (an outlier doesn't 'fit' to the distribution of a cluster, e.g. Grubbs' method). You can find a survey of outlier detection methods in A Survey of Outlier Detection Methodologies by Hodge and Austin (2004).


Proving Little-Oh notation by definition I need to prove by definition (show that for every $C$ there exists a $n_0$) that: $$5n^2+3n= o(n^3-4n)$$

By trying to simplify the expression I get to the point where I should prove that: $$ \frac{5n^2+3n}{n^3-4n} < C$$.

Now, showing that $\lim\limits_{x\to\infty} \frac{5n^2+3n}{n^3-4n} = 0$ isn't a tough mission, but how do I prove it by definition? How do I point out specific $n_0$ for every $C$ that comes up? I'm asked to provide a tight answer and not let $n_0 = C^C$ so that the $n_0$ for sure will be large enough but to point out $n_0$ that is reasonably small.

Either you do what David suggested, or you do something like this:

Let $c > 0$. Then

\begin{align}
5n^2 +3n &\le c(n^3-4n) &\iff \\
5n+3 &\le cn^2-4c &\iff \\
0 &\le cn^2-5n-(3+4c)
\end{align}

Now solve for $n$ and let $n_0$ be the bigger root of that term.


How do quantum computers find the global minimum? If I understand correctly, quantum computers work by trying multiple methods of solving a problem simultaneously, using quantum superposition. However, if you try to "look" at a superposition-ed atom, you will find either one or the other-1 or 0. What I've heard is that this is random.

So, if you compute all these solutions, how do you know which is the best without "looking" at it? Wouldn't the result just be random, and you can only see the result of one answer? Now, I've heard that this can be solved by quantum annealing, but I don't really understand it. I'd like to know how this works in fairly layman-ish (It's a word) terms.

Nope, that's not how quantum computing works.  That's actually a common misconception.  Sometimes people think that quantum computers work by trying all solutions in parallel and then selecting the best one, but that's not right -- that's not really how quantum computing works.

To learn more about how quantum computing works, I recommend you study Scott Aaronson's book Quantum Computing since Democritus, or his lecture notes on quantum computing.

Don't expect to find a one-sentence summary that is simultaneously enlightening and accurate.  Quantum physics is highly counter-intuitive, so you shouldn't expect your existing intuition to necessarily help you understand how quantum computing works.  Keep in mind that it's a bit unreasonable to expect an explanation in layman terms: quantum physics is tricky stuff, so your intuition from the everyday world doesn't really translate into a useful way of thinking about quantum computing.

You can also look at other questions on this site.  See, e.g., Why and how is a quantum computer faster than a regular computer? and quantum-computing.


Why does packet delivery time only count transmission time once? Why is packet delivery time equal to transmission time + propagation delay, and not equal to 2*(transmission time) + propagation delay?

At the end of packet delivery time, doesn't that mean that those bits haven't been received?

After the transmission time has passed, the last bit of the packet has just been put on the wire. That bit (just like all the others) will take an amount of time equal to the propagation delay to reach the receiver. When the last bit reaches the receiver, all the earlier bits will have reached it. So the total time taken is the transmission time plus the propagation delay.

It might be easier to visualize what's going on if you think about a train instead of a data packet. Imagine that we're standing by the track, some distance apart. We want to know how long it is from when the front of the train passes me (the time at which "I start sending the train to you") until the whole train has passed you (the time at which "you finish receiving the train"). This is equal to the time it takes the whole train to pass me (transmission time), plus the time it takes the back of the train to reach you (propagation delay). Or, if you prefer, it's equal to the time it takes the front of the train to reach you (propagation delay) plus the time it takes the rest of the train to pass you (transmission time).


Textbook for understanding formal grammars I am looking to understand the Chomsky Hierarchy. I've read some textbooks that touch on formal grammars (textbooks on computability, which relate automata to specific sets of formal grammars, notably context-free grammars and regular grammars), but not one that specifically deals with formal grammars as an object.

Is there a good textbook for this?

Probably the most-used textbook today is:

Hopcroft, Motwani, & Ullman, Introduction to Automata Theory, Languages, and Computation (3rd edition).

A couple of other common ones are:

Sipser, Introduction to the Theory of Computation.
Linz, An Introduction to Formal Languages and Automata.

And a couple of older ones:

Michael Harrison, Introduction to Formal Language Theory. Many learned from this 1978 classic. Even though it's older, it has the advantage that you can pick up a very inexpensive used copy from online retailers.
Thomas Sudkamp, Languages and Machines: An Introduction to the Theory of Computer Science. It's up to the 3rd edition now, but the first edition was my textbook when I was an undergraduate. The exercises are excellent, but it's light on examples.


edge coloring a directed acyclic graph I have an edge coloring problem as follows:
Suppose we have a DAG which has a source vertex s and an end vertex e, in addition, all the paths from s to e are of the same length say L. We define L colors from 1 to L. Is there an efficient edge coloring algorithm to color all the edges, such that every path from s to e uses all the L colors and every path must be labeled differently? I attach a picture below for illustration, where vertex 1 is s, vertex 10 is e.

I don't know whether there is a polynomial-time solution.  Since $L$ is fairly small ($L\le 10$), one possible approach is to use a SAT solver.
Suppose $L=10$.  For each vertex $v_5$ at distance 5 from $s$, we'll enforce that all paths $s \leadsto v_5$ have a different color sequence.  Then, we'll do the same for all paths $v_5 \leadsto e$.  This suffices to ensure your property holds.  (In general, replace 5 with $L/2$.)
Here is a plausible way to encode this in SAT.  For each edge $e$ and each color $c$, add a boolean variable $x_{e,c}$, which captures whether edge $e$ is assigned color $c$.  Also, for each pair of edges $e,e'$ at the "same level" (i.e., their start nodes are at the same distance from $s$), and for each pair of edges $e,e'$ that are part of the same path from $s$ to some vertex at distance 5 or some path from a vertex at distance 5 to $e$, add a boolean variable $y_{e,e'}$, which captures whether $e,e'$ receive the same color.  Then add constraints:

Enforce that $y$ are transitive by adding $y_{e,e'} \land y_{e',e''}  \implies y_{e,e''}$.

Enforce that $x,y$ are consistent by adding $y_{e,e'} \land x_{e,c} \implies x_{e',c}$ and $x_{e,c} \land x_{e',c} \implies y_{e,e'}$.

Enforce that the $x$'s are a one-hot encoding by adding the constraints $\bigvee_c x_{e,c}$ and $\neg x_{e,c} \lor \neg x_{e,c'}$ for all $e,c,c'$.

Enforce that each path uses all colors, by requiring $\neg y_{e,e'}$ for all pairs of edges $e,e'$ in the same path.

Enforce that each path uses different colors: for each pair of paths of the form $s \to v_1 \to v_2 \to v_3 \to v_4 \to v_5$, $s \to v'_1 \to v'_2 \to v'_3 \to v'_4 \to v_5$, add the constraint
$$y_{s\to v_1,s\to v'_1} \lor y_{v_1\to v_2,v'_1\to v'_2} \lor \dots \lor y_{v_4 \to v_5,v'_4 \to v_5}.$$
Do the same for each pair of paths of the form $v_5 \leadsto e$.

Then use an off-the-shelf SAT solver to solve this SAT instance.
I think the number of variables and clauses won't grow too large, so maybe there is a hope this instance of SAT might be solvable in a reasonable amount of time.  In particular, for any particular vertex $v_5$, the number of paths of the form $s \leadsto v_5$ will be at most $5!=120$; if there are more, then the graph cannot be colored.  Why?  Well, as j_random_hacker points out, all such paths must use the same set of 5 colors.  So, each such path's color sequence is of the $5!$ permutations of that set.  Also, each such path must have a different color sequence (otherwise we can pick any one path $v_5 \leadsto e$, append it to both, and obtain two paths $s \leadsto e$ with the same color sequence), so there can be at most $5!$ such paths.  This means that the SAT instance will have something like ${120 \choose 2} M + {M \choose 2}$ boolean variables and clauses, where $M$ is the max number of vertices per layer.


Polynomial time verification of Graph Isomorphism problem Using guess and check method, for two given graphs with the same number of nodes, a NTM selects a permutation of the node set and then checks if the edges are preserved.
The nondeterministic selection of a permutation of the nodes is done in polynomial time.
How is the choice of a function done in polynomial time? This is not clear to me.

The choice of function is done in nondeterministic polynomial time which is something you shouldn't try to "make sense of" in the real world.
It is a mathematical model of computing where we assume that the machine can perform many simultaneous operations, kind of in parallel, and if any of these operations "succeed", you get one of those answers out.

The point of this exercise is however that you show that Graph Isomorphism is contained in the complexity class NP by showing that you can solve the problem in nondeterministic polynomial time; by giving a nondeterministic algorithm for the problem.
The algorithm works as follows.  Nondeterministically pick the correct permutation $\pi$, and then in deterministic polynomial time we can verify that $\pi$ is indeed a witness or a certificate for the fact that the two input graphs are isomorphic, by checking that $\pi(v)\pi(u) \in E'$ if and only if $uv \in E$.
If $\pi$ is not a permutation that proves that the graphs are isomorphic, you can therefore conclude that the graphs are indeed not isomorphic.

It is important to stress that this does not give rise to an algorithm you can actually implement  in the real physical world, not without enumerating every permutation, at least, which as you correctly point out, cannot be done in polynomial time.


NP-completeness and reduction of MAX-XOR-SAT and MAX-2-XOR-SAT It is often stated that the MAX-XOR-SAT problem is NP-hard, and that likewise is the MAX-2-XOR-SAT problem. However, I cannot find a reduction from SAT to either of these problems, nor a proof of NP-hardness. Is one published anywhere?

MAX-2-XOR-SAT is a generalization of the more familiar problem MAX-CUT.

To see this, consider a graph $G=(V,E)$. We will have a variable $x_v$ for each $v \in V$, and a constraint $x_u \oplus x_v$ for each edge $(u,v) \in E$. We can identify a cut $S \subseteq V$ with a truth assignment by $S = \{ v \in V : x_v = 1 \}$. You can then check that the number of clauses satisfied is exactly the same as the number of edges cut by $S$.


Is $\{s_0 w s_1 : s_0s_1\in L_1, w\in L_2 \}$ context free if $L_1$ and $L_2$ are? In class, it was alluded to that a language: \begin{equation*}
\{s_0 w s_1 : s_0s_1\in L_1, w\in L_2 \}
\end{equation*} would be context free, if $L_1$ and $L_2$ are context free.

Intuitively, that doesn't make sense to me. I tried doing my own research and attempted a proof using the pumping lemma, but didn't get anywhere. Maybe I misunderstood? If that is correct, how could I prove it (or convince myself).

Class is right.

The pumping Lemma is not very helpful in this setting. It is usually used to show a given language non-context-free.

As for your language, first try to understand the special case, where $L_s = \{A\}$ for a special symbol $A$, that is try to prove that the language $\{ s_1As_2 \mid s_1s_2\in L_1 \}$ is context-free whenever $L_1$ is context-free.

In the comments below, Yuval gives a hint how to perform the construction with a PDA, for the general case. Start an automaton for $L_1$. At any nondeterministic moment (once during the computation) interrupt the $L_1$ computation and push a new bottom-of-stack symbol. Then use that as a marker to simulate a PDA for $L_2$ which stops when we accept by empty stack. Remove the marker, and happily resume the computation on the second part of $L_1$.

A simple construction using CF grammars is given by Yuval in his answer.


How Does Dynamic Heap Storage Have Something to Do with Heap? There are three typical ways to allocate memory for programs: static, stack and dynamic heap. However, when I look at the implementation of dynamic heap memory allocation from wikipedia , what I found is fixed block allocation, etc. So why is dynamic memory allocation called "heap" memory allocation? How does it have something to do with "heap"?

Heap memory and the heap data structure are two different and unrelated things. This really bothered me when I was learning about memory, especially since stack memory was actually a stack. The original use of the word heap in computer science referred to the data structure. However, in the 1970s some authors began to use the word heap to refer to the pool of available memory. This use actually more closely matches the English definition of heap - an untidy collection of things - since heap memory is a messy place to allocate and deallocate memory. The name stuck and now we have multiple meanings for the word heap.


Non-Approximate Dynamic All-Pairs Shortest Path algorithm for Undirected, Unweighted Graphs? I am looking for an algorithm involving adding unweighted edges to an empty, undirected graph (with vertices) and then for each, updating the table of shortest paths.

An example is if we have vertices 1 to 5. We can see that initially, all of the paths are infinite except for the diagonal entries, i.e.:

  1 2 3 4 5
1 0 i i i i
2 i 0 i i i
3 i i 0 i i
4 i i i 0 i
5 i i i i 0

where i means "infinite". But if we add an edge (1, 2) then the 1-2nd and 2-1st entries of the table are updated:

  1 2 3 4 5
1 0 1 i i i
2 1 0 i i i
3 i i 0 i i
4 i i i 0 i
5 i i i i 0

Now, if we add the edge (2, 3), then obviously the 2-3rd and 3-2nd entires are updated, but also are 1-3rd and 3-1st (which has length 2, since the path is 1->2->3 and 3->2->1):

  1 2 3 4 5
1 0 1 2 i i
2 1 0 1 i i
3 2 1 0 i i
4 i i i 0 i
5 i i i i 0

Now, the more edges and vertices we add, the more complex the problem becomes, since we need to update other entries in the matrix if they are connected. The one fact that I know about this kind of graph is that it is symmetric along the diagonal.

I've been looking at this problem for a few hours and I do not think there is a generic algorithm that will solve the problem for a general unweighted, undirected graph. Are there resources on the problem?

The paper A New Approach to
Dynamic All Pairs Shortest Paths by Camil Demetrescu and Giuseppe F. Italiano gives a solution to the directed version of the problem.

It involves saving two priority queues at each position on the matrix and updating and extracting information from these queues as edges are added. The psuedocode for the algorithm is on page 9 of the link.

For undirected graphs like this one, you could add 2 edges for each edge, one in each direction. This will not affect the time complexity of the algorithm.


Is it possible that Co-NP = P but NP != P Suppose there exists an algorithm that takes as input an unsatisfiable SAT formula, and never fails to verify it in polynomial time. However, when the input is a satisfiable formula, it doesn't work (let's say time and memory problems, the algorithm gets lost in the reasoning).

Then Co-NP = P because we can verify unsatisfiable instances in polynomial time. The certificate of unsatisfiability is the formula itself.

But then is it still possible that P != NP?

The answer is no, and the reason is that $\mathrm{P}$ is trivially closed under complement. Just by definition of $\mathrm{co}$, it follows that $\mathrm{coNP} = \mathrm{P}$ is equivalent to $\mathrm{NP} = \mathrm{coP}$, and then we use that $\mathrm{coP} = \mathrm{P}$ to conclude that $\mathrm{coNP} = \mathrm{P}$ iff $\mathrm{NP} = \mathrm{P}$.


Don't understand the merge part of the mergesort I understand how the divide part of the algorithm works and how it is meant to spread efforts.

What I don't understand is how would you merge blocks [7][14] and [3][12] or [9][11] and [2][6]. For the latter part it's easy enough as you just concatenate them ( although how do you know that? )  but  for [7][14] and [3][12] you have to rearrange their indexes for the order to be increasing.
How in software/pseudocode do you implement that step?

The merge subroutine takes two sorted arrays and creates one sorted array out of these two arrays. It does so in linear time.

Say the sorted arrays are A = [1 2 3] and B = [2 3 4]. Since these two are already sorted, the minimum is going to be either the first element in A or the first element in B. So take the minimum among these two values and append it to the output array C. We get C = [1] and the two arrays now look like A = [2 3] and B = [2 3 4] (you don't have to remove 1 from A, you can increment an index to implement this step).

Now iterate this process until both arrays are empty and the final sorted array is C.


BFS Algorithm for Finding Minimum Steps for Knight Eliminating a Moving Pawn BFS Algorithm for Finding Minimum Steps for Knight Eliminating a Moving Pawn.

As the Title suggests, I'm trying to intuitively understand this problem. Suppose we have a Pawn and a Knight taking turns. Both pieces must move on their turn, and both pieces have a starting position, and suppose the board is sufficiently large enough for the Knight to eventually catch up to and eliminate the Pawn, where the Pawn is avoiding being captured. I want to find the minimum amount of moves the Knight takes to eliminate the Pawn.

I know that we can use a BFS algorithm to find the shortest path between the Knight and a stationary spot on the board, but I'm not sure how to do this for a moving target. What if we do a BFS on every square of the column the Pawn is travelling on and then compare the number of moves that takes and check if one of these sequence of moves ends up on the Pawn's location. But this doesn't seem like it will always work, because finding the minimum amount of moves to where the Pawn will eventually be could be less than the actual minimum amount of moves to catch up to the Pawn because the Knight could "stall" a bit until it's in the right position to eliminate the Pawn.

It's very simple.

A pawn has a choice to move one or two positions forward in its first move, in all following moves it moves one position. A knight moves two squares in one direction, and one step orthogonal.

As a result, the colour of a pawn's square changes on every move, except on the first move, where it has a choice to change the square's colour or not. The knight always changes the colour of its square. So in its first move, the pawn moves to the same colour as the knight, and from then on, the knight can never take the pawn.

(You need to specify what should happen if the knight is in the pawn's way so it cannot move though. If the rule is that the pawn just doesn't move, then the knight can block the pawn's path, and two moves later takes the pawn).


Find all sets of nodes that can be connected with a single path **  Edit: I just noticed my current algorithm is incorrect, as it only finds paths starting/ending at the given node. I'm trying to figure out a solution, but I'm a bit stuck.

Say I have an undirected graph. I would like to find all possible combinations of nodes that could be connected with a single path, that include a certain node.

--clarification: That is paths starting and ending at any node. Not just paths starting at the node in question.

Take this graph for example:

A----B
|    |
|    |
D----C

The solution for node A would be:

ABCD; example path A->B->C->D. Alternatively B->A->C->D or many others. As long as we have one, we're good.
ABC; example path C->B->A, etc.
ADC
AB
AD
A; 'path' from itself to itself

I understand this is a -very- hard problem with a lot of results. To make it simpler it is allowed to have some duplicates in the end result, but less would be better(this makes cyclic graphs a bit easier).

My current(naive) solution is as follows:

Start at the node in question
Note current path as possible path.
If no possible connections, return.
For each possible connection, go into recursion via [2].

See the following example. The problem with my algorithm is that a lot of duplicates are generated. Here the bottom two items in the example tree are the same solution.

Just use depth-first search. Each node you encounter in the search tree corresponds to a path from the source vertex.


Conjunctive normal form to simple elementary algebra I'm curious to know the computational complexity class of each step in this method of converting a CNF formula into simple elementary algebra.

An example:
$$\phi=\left(x_1 \vee x_2 \right) \wedge \left(\neg x_1 \vee x_3 \right) \wedge \left(\neg x_2 \vee \neg x_3 \right) \tag{CNF} $$
Let $\neg a = 1-a$

Let $a \vee b= a+b-ab$

Let $a \wedge b = ab$

Then:
$$\phi=\left(x_1 + x_2 -x_1x_2\right) \left(1-x_1+x_1x_3\right) \left(1-x_2x_3 \right) \tag{AFF} $$
I refer to this step as algebraic factor form (AFF) (I am unfamiliar with any canonical terminology)
Then expanding these brackets out gives
$$\phi = x_1-{x_1}^2+x_2 - 2x_1 x_2 +{x_1}^2x_2 + {x_1}^2x_3-{x_2}^2x_3+2x_1{x_2}^2x_3-x_1^2x_2^2x_3-x_1^2x_2x_3^2-x_1x_2^2x_3^2 + x_1^2x_2^2x_3^2 \tag{EAF}$$
Which is in elementary algebra form.

Finally, using ${x_1}^2=x_1, \; \; {x_2}^2=x_2, \; \; {x_3}^2=x_3$ we get
$$\phi = x_1-{x_1}+x_2 - 2x_1 x_2 +{x_1}x_2 + {x_1}x_3-{x_2}x_3+2x_1{x_2}x_3-x_1x_2x_3-x_1x_2x_3-x_1x_2x_3 + x_1x_2x_3$$
Which simplifies to:
$$\phi = x_2 - x_1x_2 + x_1x_3 - x_2x_3 \tag{SEAF}$$
Which I call simple elementary algebra form.

If there are already established names for these formulas please let me know and I will amend asap.

So my question is: What are the computational complexity classes of each transformation in (CNF) $\rightarrow$ (AFF) $\rightarrow$ (EAF) $\rightarrow$ (SEAF)

I'm interested to know which parts are P and which parts are NP

Thanks in advance for any answers, Ben

$\mathsf{P}$ and $\mathsf{NP}$ are classes of decision problems. Essentially, a decision problem is a function $D \subseteq \{0,1\}^\ast \times \{ 0,1 \}$ (although describing $D$ simply by giving the subset $\{ 0,1 \}^\ast \times \{ 1 \}$ is more common). A Turing machine is said to solve $D$ if, given any string $x \in \{ 0,1 \}^\ast$, it produces $D(x)$. If there is a Turing machine which does so in time bounded by a polynomial $p(|x|)$, then $D \in \mathsf{P}$. If there is a nondeterminstic Turing machine capable of doing so in polynomial time, then $D \in \mathsf{NP}$. As you can see, $\mathsf{P}$ and $\mathsf{NP}$ are unrelated to transforming representations of objects into other (equivalent) representations; they are only about saying, for some string $x$, whether $D(x) = 1$ or not.

In your case, what we can do is analyze the time complexity of each transformation.
The step CNF $\to$ AFF simply causes the formula to be longer by a constant factor and can be realized in linear time.
In AFF $\to$ EAF, the formula blows up exponentially; assuming we previously had a maximum of $t$ terms for each of the $c$ clauses, you go over every possible $t^c$ multiplication of said terms, which takes potentially exponential time.
The final EAF $\to$ SEAF step aggregates some terms and may be computed, for instance, in quadratic time (e.g., by looping over each term in the formula).
Note that these time complexities are all relative to the respective input length for each step; for instance, "linear" is supposed to mean bounded by $c |\varphi|$, where $\varphi$ is the respective formula which is given as input to the respective transformation step.

I am not aware of a name for the forms you have given. Nevertheless, considering a Boolean formula $\varphi$ as an arithmetic expression (in particular over larger fields) is usually referred to as an arithmetization of $\varphi$ and is very relevant in complexity theory; see, for instance, this and this.


Correctness of an algorithm difference between recursive and iteraive I know that the general strategy to do the correction of an algorithm is as follow :

  if the algorithm is recursive then prove the correctness using induction
  if the algorithm is iterative (using a for loop for example) then find an invariant

Finding an invariant is sometimes hard while induction is easy. So since every iterative algorithm can be transformed into a recursive one, why do we bother finding clever invariant while we could do :

  find the recursive equivalent algorithm -> use induction

Maybe the part : "transform the iterative program into a recursive one" is hard, but for simple programs it's definitely worth it. I mean sometimes it is (at least for me) very hard to find invariant, but when doing induction everything is "easy".

So I guess I am missunderstanding something ?

Thank you !

A proof using a loop invariant is also a proof by induction – you prove that the invariant is indeed an invariant by induction. The reason that finding the inductive hypothesis is easier for recursive procedures is that we usually state the semantics of the recursive function – what it is supposed to compute – and this is the "loop invariant" we use to prove its correctness.

Let's consider the following two procedures for summing an array $A[1],\ldots,A[n]$:

  Iterative:

  $sum \gets 0$
  $i \gets 1$
  While $i \leq n$:

  $sum \gets sum + A[i]$
  $i \gets i + 1$

  Return $sum$

  Recursive:

  $Sum(A[1],\ldots,A[n])$

  If $n = 0$, Return $0$
  If $n > 0$, Return $Sum(A[1],\ldots,A[n-1]) + A[n]$

The loop invariant for the iterative algorithm is $sum = A[1] + \cdots + A[i-1]$. This is something we have to come up with. We prove that it holds by induction, and conclude that the function returns $A[1] + \cdots + A[n]$.

In contrast, it is clear what $Sum$ is supposed to compute: the sum of its input. We still need to argue inductively that $Sum$ works correctly, but the inductive hypothesis $$Sum(A[1],\ldots,A[i]) = A[1] + \cdots + A[i]$$ corresponds to the semantics of $Sum$.

We often attach a meaning to recursive procedures, but not so often to loops. If we did attach a semantic meaning to the $i$'th iteration, it would become easy to formulate the loop invariant. An example is the Floyd–Warshall algorithm (or rather, some of its implementations), where the $i$'th iteration computes the shortest path of length at most $i$.


Why are there $(2kn+1)^{kn}$ Turing Machines with $k$ symbols and $n$ states? I've seen a few references [1], [2], [3] that say that for a Turing Machine with transition function defined by:

$\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\}$

the number of turing machines with $n$ states and $k$ tape symbols is $(2kn+1)^{kn}$.

However, looking at the definition, shouldn't it be $(2kn)^{kn}$ instead?

Perhaps they are counting the number of Turing machines with at most $n$ states. In any case, it's not a big difference. Usually one is only interested in an upper bound, and from that perspective there is no difference between the two expressions.


Shortest Path with a twist We are given a Graph G where, s ∈ V and t ∈ V. w:E such that w represents the time from u to v.  We have to calculate shortest path between s to t with a twist. The twist is the turbocharger which can be activated at any node u, such that time between u to v becomes (u,v)/3. The turbocharger has to be used just once. Find the minimum distance path between s to t.

My approach - Use BFS to calculate all the paths.
When we find all the paths from s to t, apply brute force to each edge (u,v) and check the minimum result.
This approach takes O(V+E) + O(E) time roughly. (I assume).

I am looking for suggestions and better approach to this problem. Please appreciate my learning phase and help me to do better at algorithms.
 Thank You.

First, your algorithm is not |V|+|E| because each node can be visited more than once. This is because at each stage of your BFS, there is not greedy to always visit the optimal next node. If you are generating all paths, each path visits at most all the nodes once, so the time complexity of your algorithm would actually be O(PN) where P is the total number of paths. In fact, it is likely way larger because each edge can be visited more than once.
However, there is another algorithm that can be applied to this non-negative edge-weight graph: Dijkstra's Algorithm.
To deal with the turbo charger, simply expand the graph such that each each state in your heap stores both the current weight and wether the charger has been used.


Least common multiple of a list of numbers I'm trying to learn computer science by doing some challenges. One is the following.

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Let's generalize the problem from $1$ to $n$.
I thought of a loop between $n$ and $n/2$ as everything above $n/2$ is a multiple of something between $1$ and $n/2$. At each iteration, the result is the least common multiple of the loop variable and the precedent result (at the beginning the result is 1).
If I am correct, the complexity of this should be $\mathcal{O}(n/2)$. Am I right?
Is there any more efficient algorithms to solve this problem? If so witch one and what is their complexity?

Suppose that we are interested in the LCM of all numbers from $1$ to $n$. It is not hard to check that the answer is the product of $p^{k_p}$ for all primes $p \leq n$, where $k_p$ is the largest integer such that $p^{k_p} \leq n$. For example, the primes at most 10 are $2,3,5,7$, and so the answer is
$$
2^3 \cdot 3^2 \cdot 5 \cdot 7 = 2520.
$$
Similarly, the primes at most 20 are $2,3,5,7,11,13,17,19$, and so the answer is
$$
2^4 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19.
$$


Origins of the numerical notation for types in type theory In several papers on type theory it's possible to see some sort of numerical notation for types based on the number of possible constructors for the type. For example, the unit type is usually written as $1$, as there's only one possible constructor for it; similarly, they use $2$ for booleans, $x + y$ for disjoint unions (sum types), $x * y$ for product types, and so on.

This kind of notation seems to be assumed familiar to the reader. Where does it come from? Are there any sources that explicitly explain this notation?

This almost certainly derives from (finite) set theory. The cardinality of a finite set $S$, written $|S|$, is the number of distinct elements it has. For finite sets, we have the following relations: $$\begin{align}
|\emptyset| & = 0 \\
|1| & = 1 \\
|A\times B| & = |A||B| \\
|A\uplus B| & = |A|+|B| \\
|B^A| & = |B|^{|A|}
\end{align}$$
where $A\times B$ is the Cartesian product of $A$ and $B$, $A\uplus B$ is the disjoint union of $A$ and $B$, and $B^A$ is the set of functions from $A$ to $B$. The type theoretic constructions $A\times B$ (product types), $A+B$ (sum types), and $A\to B$ (function types) correspond to these set theoretic constructs. For example, finite sets form a model of the simply typed lambda calculus with products and sums where product, sum, and function types are interpreted as exactly the constructs on finite sets above. This correspondence is not general. There are many other models of the simply typed lambda calculus that will interpret these type constructions differently. Nevertheless, this is the archetypal example.

Category theorists often use similar notation but it is motivated the same way.

Another take on this is that these type operations (ignoring function types though their existence implies distributivity) make types into a commutative semiring up to isomorphism. Equations that you can prove in the theory of commutative semirings give rise to type isomorphisms.


Merge two sorted arrays without using additional memory We have two sorted arrays of integers.
Without using additional memory we need to merge these two arrays such that the smallest numbers are in the 1st array and the remaining numbers are in the second array.

For instance, if your two arrays are $A=[1,3,9,14]$ and $B=[2,4,15]$, the result should be $A=[1,2,3,4], B=[9,14,15]$. Entries are integers, and you can use only $O(1)$ extra memory for auxiliary variables.

Here, great solution, from: http://www.geeksforgeeks.org/merge-two-sorted-arrays-o1-extra-space/

Below is C++ implementation of above algorithm.

// C++ program for implementation of Sieve of Atkin
#include <bits/stdc++.h>
using namespace std;

// Merge ar1[] and ar2[] with O(1) extra space
void merge(int ar1[], int ar2[], int m, int n)
{
    // Iterate through all elements of ar2[] starting from
    // the last element
    for (int i=n-1; i>=0; i--)
    {
        /* Find the smallest element greater than ar2[i]. Move all
           elements one position ahead till the smallest greater
           element is not found */
        int j, last = ar1[m-1];
        for (j=m-1; j >= 0 && ar1[j] > ar2[i]; j--)
            ar1[j+1] = ar1[j];

        // If there was a greater element
        if (j != m-1)
        {
            ar1[j+1] = ar2[i];
            ar2[i] = last;
        }
    }
}


A general picture of formal verification in software I'm trying to piece together a general picture of the state of formal software verification, and I'm having a good bit of trouble. For context, I come from mostly a math background. I'm quite familiar with the state of automated theorem provers and proof assistants with respect to their use to prove well formed mathematical statements (e.g. in Coq, Isabelle, Lean, etc.). What I'm having trouble understanding is what is going on with "formal methods" in practical CS applications.
I've found that companies such as Microsoft and AWS have used TLA+ as a "formal method" in their software development somewhat substantially. But when I started to read Wayne's Practical TLA+ book, I found that he considered a program to be formally checked if we just check say  a sorting algorithm on lists of length $<n$ with entries between 1 and $n$ for some fixed $n$, i.e. we are just checking finitely many cases and saying that therefore the algorithm should work in general. This doesn't seem particularly interesting; just an example of particularly rigorous unit testing. Notably it is not a formal proof of correctness.
On the other hand, I've seen murmurs about Isabelle and Coq being able to prove things about software just like they can prove mathematical theorems. Though when I look into the books which seem to promise this, e.g. Chlipala's Certified Programming with Dependent Types, I see a lot of abstract stuff that seems to vaguely relate to formally verifying programs, but no examples of taking a real program written in a language that has widespread use (e.g. C++, Python, Java, etc.) or even just pseudocode and "verifying it", whatever that means.
Can someone try to clear up my confusion?

A formally proven program is a formally proven program regardless of which language it's in. Just because a program is written in Coq and perhaps extracted to OCaml or Haskell, rather than written in a more “enterprisy” language such as C++ or Java, doesn't make it any less of a program.
Proving programs written in general-purpose programming languages, even “tame” ones like Haskell, is hard because these languages typically include a lot of convenience features, dark corners for performance and to interface with the operating system, and rich and complex libraries. To prove a property of a program, you first need to state this property, and the statement embeds the semantics of the language that the program is written in. When you try to formalize languages that were initially designed without a formal semantics (which is almost all of them), you very quickly hit dark corners which the English description leaves unspecified, or where it's ambiguous, or where it's outright self-contradictory, or where the reference implementation doesn't do what the description says and that's considered a bug in the English rather than in the implementation. The state of the art of proving properties of programs written in a preexisting language is to restrict the programs to a subset of the language.
What goes into that subset is highly variable. Syntactic sugar is not too difficult: the semantics just needs to translate it into simpler constructs. Reflection properties aren't particularly difficult to model, but may make the model a lot more difficult to reason about (for example, it invalidates properties such as “this snippet of code doesn't have any way to reference this variable, therefore it cannot change its value”), so many frameworks rule this out. Interactions with the operating system (typically via libraries) are problematic because they require modeling the operating system, which get be extremely complex. Floating point operations are hard because keeping track of the approximations across successive operations causes a huge blow up.
For C, one of the main large subsets with a formal model is CompCert C, the language of CompCert. CompCert is a formally verified compiler (written in Coq), so if you prove a property of the C program, you can additionally get a proof of the generated machine code. CompCert C is a very large subset of C99, but the formalization excludes most of the standard library and some quirks of the language.
To prove a program that is written in a (suitable subset of a) real-world programming language, the program needs to be structured in such a way as to make the proof tractable. In practice, this means having written and proved the program first in a higher-level language (which has no implementation on real hardware), and using this higher-level language as a specification of the final program. Often there are several levels of successive refinements between the executable program and the specification.
It's fairly common that the final program is not written manually, but extracted mechanically from a higher-level language. For example, writing Coq which is extracted to OCaml, or writing F* which is extracted to C. But the opposite approach is possible as well, for example writing (“tame”) C, annotating it with properties of functions and other code subdivisions, and using Frama-C to prove those properties (and the implied property that the C program has no undefined behavior).
When you have a formal semantics of a programming language and a way to express properties of programs, proving these properties is a mathematical theorem. Typically these theorems don't involve any complex mathematics such as calculus (unless brought in by the application domain, such as tracking the movement of a physical object), but they're difficult to prove because involve very large formulae, and contain arithmetic statements ($x^n+y^n=z^n$ is not a complex equation, but solving it is not elementary!). It's theoretically impossible to write a program that can prove a non-trivial semantic property of all programs, and practically impossible to write a program that can prove many interesting properties of typical programs. Formal verification involves a combination of breaking the problem down into sufficiently small steps (writing small functions and stating enough precise properties of those functions), having a tool automatically prove some of those properties (such as a SAT solver for propositional logic), and having humans write proofs where the computer can't do it (but the computer will check the human's proof). Proof assistants such as Coq and Isabelle come in for this last step.
Formally proving a real-world program is a huge effort, requiring a much larger amount of time and expertise than the typical software project. It's rarely done outside of high-assurance environments, mostly environments with high safety requriements such as transportation (planes, trains, not so much cars), sometimes environments with high costs such as space or (very rarely) with high security requirements such as smart cards.

if we just check say a sorting algorithm on lists of length <n with entries between 1 and n for some fixed n, i.e. we are just checking finitely many cases and saying that therefore the algorithm should work in general.

That would not be a formal proof unless the program had a limit of n items for its input. I don't know this book, but I suspect either you misread something. Formally checking a sorting program would involve proving its correctness for all n.


Push down automata for $\{a^n b^n c^n | n \ge 0\}$ I am learning about context free languages.

I understand how $\{a^n b^n c^n | n \ge 0\}$ can be shown to be not context free using the pumping lemma for CFL's.

Intuitively however it seems that a pushdown automata to recognize $\{a^n b^n c^n | n \ge 0\}$ can be constructed. This PDA would initially push two $a$'s into its stack whenever it sees an $a$ in the input. It would change state when it first encounters a $b$ and pop a single $a$. It would continue to pop $a$'s for every b in the input until it encounters a $c$. It would again change state and pop single $a$'s for every c encountered. If the stack is empty at the end of the input the language is recognized as $\{a^n b^n c^n | n \ge 0\}$.

There must be something I am overlooking whilst constructing the PDA as a language is context free if its has a PDA recognizing it. Please point out my mistake.

Your PDA would also accept strings of the form $a^nb^ic^j$ where $i+j=2n$ and $i,j>0$. For example the string "aaabbbbbc" is accepted. There is no way to tell that there are exactly $n$ $a$'s still remaining on the stack once you've finished reading the $b$'s.


How come identity encodes absurdity From P5 in this paper: https://hal.inria.fr/hal-01094195/file/CIC.pdf

  Using this purely functional part, it is possible to encode many int
  eresting notions. For instance
  ∀
  C
  :
  Prop
  , C
  is a logical proposition (a term of type
  Prop
  ) which encodes absurdity (
  ⊥
  ) : there is
  no closed term of type
  ∀
  C
  :
  Prop
  , C
  (so no proof of
  ⊥
  without hypothesis) and also from a proof
  t
  of
  ∀
  C
  :
  Prop
  , C
  one can build a proof
  t C
  of an arbitrary proposition
  C
  so the natural deduction
  rule for eliminating
  ⊥
  is derivable in the logic.

where

$$
\forall C: Prop, C
$$

looks entirely identity function to me, which can definitely be inhabited by a closed term. Why the author said it encodes absurdity?

If I were to encode absurdity, I would do

$$
\exists P: Prop, P \to \forall Q:Prop, Q
$$

That is, there exists a proposition which derives everything. From category theoretic perspective, it's precisely how the initial object is defined, which can encode absurdity with no doubt.

Did I misread it in a terrible wrong way that the author was actually right? How about my encoding, does it make sense to you?

looks entirely identity function to me, which can definitely be inhabited by a closed term

A proof of $\forall C : Prop, C$ is a function from an arbitrary proposition to its proof. Since a proposition isn't a proof, an identity function is not a function from propositions to proofs.

The identity function (or rather, a function returning the identity function on proofs of $C$) corresponds instead to the proof of $\forall C : Prop, C \to C$. That's even the example on the beginning of page 3!


Construct two functions $f$ and $g$ satisfying $f \ne O(g), g \ne O(f)$ Construct two functions $  f,g:   R^+ → R^+ $ satisfying:

$f, g$ are continuous;
$f, g$ are monotonically increasing;
$f \ne O(g)$ and $g \ne O(f)$.

There are many examples for such functions. Perhaps the easiest way to understand how to get such an example, is by manually constructing it.

Let's start with function over the natural numbers, as they can be continuously completed to the reals.

A good way to ensure that $f\neq O(g)$ and $g\neq O(f)$ is to alternate between their orders of magnitude. For example, we could define

$f(n)=\begin{cases}
n & n \text{ is odd}\\
n^2 & n \text{ is even}\\
\end{cases}$

Then, we could have $g$ behave the opposite on the odds and evens. However, this doesn't work for you, because these functions are not monotonically increasing.

However, the choice of $n,n^2$ was somewhat arbitrary, and we could simply increase the magnitudes so as to have monotonicity. This way, we may come up with:

$f(n)=\begin{cases}
n^{2n} & n \text{ is odd}\\
n^{2n-1} & n \text{ is even}\\
\end{cases}$, and
$g(n)=\begin{cases}
n^{2n-1} & n \text{ is odd}\\
n^{2n} & n \text{ is even}\\
\end{cases}$

Clearly these are monotone functions. Also, $f(n)\neq O(g(n))$, since on the odd integers, $f$ behaves like $n^{2n}$ while $g$ behaves like $n^{2n-1}=n^{2n}/n=o(n^{2n})$, and vice-versa  on the evens.

Now all you need is to complete them to the reals (e.g. by adding linear parts between the integers, but this is really beside the point).

Also, now that you have this idea, you could use the trigonometric functions in order to construct ``closed formulas'' for such functions, since $\sin$ and $\cos$ are oscillating, and peak on alternating points.


Shortest-Path for Weighted Directed Bipartite Graphs I did a research project in which I seek to move a car through zones from origin to destination. This allows for the formulation of a bipartite graph because only adjacent zones can be connected. Each edge has a non-negative weight of time. I look to find the shortest path between source and sink, given the weights and directions of the edges. The structure of the graph is quite simple, all adjacent zones are connected. The bipartite graph looks this this.

My question is what is the best shortest-path algorithm for such a graph?

Merge every zone into one vertex. You now have a linear path, with one or multiple edges between each vertex. Since this graph does not branch, you can simply choose the cheapest edge between every vertex directly.

A small illustration I made:


Is infinitely fast computer fundamentally impossible even theoretically? This may get slightly philosophical, but consider the following program:

bool lampState = false;
TimeSpan timeout = 1;
while (true)
{
    lampState = !lampState;
    Thread.Sleep(timeout);
    timeout = timeout / 2;
}

DotNet Fiddle link for C# code

This is obviously an implementation of Thomsons lamp in C#.

So the question is what is the value of lampState after 2 seconds of execution?

Lets assume that no physical law prevents us from constructing an infinitely fast computer. Static code analysis shows that we will never exit the while loop. Does this mean that we can have an algorithm that is arbitrary fast, but not infinitely fast, not even theoretically (because we run in to a contradiction?

No, it doesn't mean that.

The problem with Thompson's lamp is that a particular state of an abstract machine is not well-defined. This is nothing unusual. E.g., dividing by 0 also yields an undefined value, because any value we could choose would lead to inconsistencies with other definitions that we would like to keep - at any rate, more than the isolated, unimportant definition of 1/0.

Abstract machines can be implemented in real machines, but there are limits; one if them is that you have only finite matter, space and time available. Therefore, infinitely fast machines, just as infinitely big machines, cannot be implemented. This merely means that we cannot check the question by physical experiment.

There are many other machines that are infinitely large that we also can't build, but which at least yield a well-defined prediction (for instance, the machine that never does anything would leave the state at the initial value). Those machines cannot be tested by experiment, but they can be predicted theoretically. This machine cannot even be predicted, because it has been carefully defined to fall into an undefined niche of logics.

But this has nothing to do with the question how fast an algorithm can be. There are many algorithms of which we do not know whether (given enough time) they eventually terminate. Some of these may be testable by running them and waiting long enough, but since we don't know how long "long enough" is, physical experiment can only ever give the answer "yes", but never "definitely no".

Therefore you shouldn't be too worried about the fact that a certain machine can't actually be built. Some problems are better handled via experiment, and some via theory. Those that cannot be handled either way are vexing, but almost always they are far removed from any practical problem that we really need to solve.

Example: if mathematics weren't incomplete, i.e. it it were possible to determine the truth of any propositional formula via a single algorithm, mathematicians would be glad, but everyday life would not be much affected. Even knowing P = NP would do little; it is one thing to know that a prime can be factored in polynomial time, quite another thing to be actually able to do it.


Is $L / R$ context free? I was reviewing the post  If $L$ is context-free and $R$ is regular, then $L / R$ is context-free?

I completely understand why $L/R$ is context free.

I just tried a different approach, which is not that rigorous according to the answers given. It is just based on the basic understanding.

How I tried :

Let $L = a^N b^N a^M b^M$ and $R = \left (a + b \right )^*$.

Then $wx$ belongs to $L$. Suppose I assume $wx = aaabbbab$.

So, now $x = ab$ which belongs to $R$.

So $L/R$ contains $aaabbb$.

Like this, I will get all strings in $L/R = \left \{ a^N b^N | N \geq 1 \right \}$.

This language is nothing but context free.

This approach is not as rigorous as what I saw in the answers.

I just want to confirm: is this approach right?

You can't prove a general theorem by proving one special case. So even if your proof of the special case were correct (and it isn't), all it does is prove that the theorem holds in that specific case.

Your proof is erroneous since $L/R$ is larger than what you indicate. In fact, whenever $\epsilon \in R$, we always have $L/R \supseteq L$. In your case
$$
L/R = \{ a^{n_1} b^{n_2} : n_2 \leq n_1 \} \cup \{ a^n b^n a^{m_1} b^{m_2} : m_2 \leq m_1 \}.
$$


"Breadth course" problem – find maximum independent set given all maximal cliques One of the undergraduate degree requirements at my university is that all Letters and Science students must take a "breadth course" in each of seven categories. If a course has multiple associated categories, you have to pick one; you can't satisfy multiple breadth requirement categories with a single course.

For example, while CHINESE 110A Introduction to Literary Chinese is both an "arts and literature" course and an "international studies" course, you can only use it for one of the two categories. If you then take COMLIT 156 Fiction and Culture of the Americas, which satisfies "arts and literature", you've now got both of the categories taken care of.

I'm trying to write a program that determines the maximum number of categories you can fulfill with a given set of courses. I suspect I can do this by creating an undirected graph as follows:

Each node of the graph represents a particular course applied to a particular category.
The graph has a clique for every category containing all of the nodes with that category, as well as a clique for every course containing all of the nodes with that course.

For the example case, we'd make a graph that looks like this:

Then, the number of requirements fulfilled would be the size of the maximum independent set of the graph.

Where I'm having trouble is in finding that maximum independent set. I'm aware that algorithms exist to find the maximum independent set of any graph in exponential time, but is there a more efficient algorithm I could use to take advantage of the fact that I already know all the maximal cliques?

This is an instance of bipartite matching.   You have one left-vertex for each course, one right-vertex for each category, and an edge between each course and each category it can be used for.  Now you want to find a maximum matching in this bipartite graph.  There exist standard polynomial-time algorithms for finding a maximum matching in a bipartite graph.


E-R diagram and relationships Suppose we have two entities $A$ and $B$ and some relationship between them. If there is an $M:N$ relationship between them (i.e. an $M$ on the line connecting $A$ to the relationship and an $N$ connecting the relationship to $B$), how do we read this? Would it be the following: A single instance of $A$ is related to $N$ of $B$ and a single instance of $B$ is related to $M$ of $A$?

You got it right, I think.

$1 : N$ means: Any $A$ may be connected with any number of $B$, but every $B$ is connected to (exactly) one $A$.

Example: (Biological) Mothers and children.
$M : 1$ means the same, just reversed.
$M : N$ means that any $A$ may be connected with any number of $B$ and vice versa.

Example: Teachers and students.


DFAs are regular languages, but regular languages are closed under concatenation I have course notes which claim the following two facts:
First, DFAs recognize exactly the regular languages.
Second, regular languages are closed under union, concatenation, and *.
Now I have as an exercise constructed a DFA which recognizes strings from {0,1} which have an odd number of 1s.  So the language of strings of any odd number of 1s is a regular language.  However, if you concatenate any two words from the language it contains an even number of 1s and is therefore not closed under concatenation.
I must be misunderstanding something, but what?
I think maybe what I'm doing is saying that the language itself is closed under concatenation, when that's not true.  Maybe the claim is actually that the concatenation of one regular language with another regular language is a third regular language?

The third paragraph is the correct description how to interpret the statement from your notes. This is also easy to prove: Say $L$ and $L'$ are regular languages described by some regular expressions $r$ and $r'$ respectively. Then $rr'$ describes the concatenation $LL'$ of $L$ and $L'$.


Induction on strings (words) Given is an alphabet $\Sigma = \{ 0, 1, 2 \}$ and a function quer to calculate the cross sum of a word.

$quer : \Sigma^*\to \Bbb N$ with:

$$quer(w)=\begin{cases} 0, &\text{when } w=\epsilon\\
quer(v)+x, &\text{when } w=vx, x\in\Sigma
\end{cases}$$

Where $\epsilon$ is the empty string.

Prove by Induction on words that $\forall w\in\Sigma^*$, $quer(w)\le 2*|w|$.

I can prove that the statement holds for $\epsilon$.

Base case: $quer(\epsilon) = 0 \le 2 * |\epsilon| = 0 $

How can I show that the statement holds in the inductive step?

I suppose you are already familiar with the idea behind mathematical induction, but just to recap the general idea, the goal is to use the inductive hypothesis to help us get the desired statement. It is helpful to construct the words in a way that will simplify how you can relate back to the original word.

Suppose it works for all words $v \in \Sigma^*$ such as $\lvert v \rvert = n$ (we can do this because you proved the base case for words of length 0). Now, take $w = vx$ for any $x \in \Sigma$. Note that the length of $w$ is $\lvert v \rvert + 1$ by construction ($\lvert w \rvert = n + 1$).

$$ quer(w) = quer(vx) = quer(v) + x \leq quer(v) + 2 \\
                                    \leq 2\cdot \lvert v \rvert + 2\\
                                    = 2 \cdot (\lvert w \lvert -1) + 2\\
                                    = 2\lvert w \rvert - 2 + 2 \\
                                    = 2 \lvert w \rvert
$$


What is the difference between LRU implemented for a cache and for page replacement? I have read that true LRU page replacement requires significant hardware support, so only approximation of LRU is implemented for page replacement.

So I wanted to contrast LRU that is implemented for cache, and that for page replacement. Like - Is LRU properly implemented for cache?

LRU is most commonly used in 2-way associative caches, where it only requires a single bit that is set or cleared depending on the way accessed. (True LRU requires log2(N!) bits for N ways for each set.)

For four-way and eight-way associativity, binary tree pseudo-LRU is commonly used, though some embedded systems might implement true LRU as such is easier to analyze for worst-case execution time. Binary tree pLRU is relatively simple to implement because an access to a given way will always merely set/clear specific bits.

For associativities higher than eight, FIFO, random, and Not Recently Used have been used. E.g., the Itanium 2 6M used NRU that is similar to the clock page replacement algorithm in that a bit is set when accessed and all the bits are cleared when they have all been set.

An interesting exception is the use of true LRU in the 32-entry fully-associative L1 TLBs for several Itanium implementations. For a fully associative TLB, true LRU is less expensive because there is only one set, so storage and control logic can be bundled together.

It should also be remembered that LRU is really just an estimate of relative reuse distance; approximation of a conceptually-derived heuristic can be roughly as effective as the ideal heuristic. (Even reuse distance may not be ideal for replacement because not all entries have the same cost/benefit.)


Calculate Stages in Non-Pipelined Processor I have tried to attempt a question where I have to find the number of stages for non-pipelined processor(8085) for below program :-

MOV #40, R00
MOV #50, R01
MOV #60, R02
SUB R02, R01
ADD R02, R01
INC R01
SUB R00, R02
HLT

What will be the no. of stages and there list here?

That processor should come with a manual. If yes, you can use the information in the manual. If no, you can google for the manual, like "8085 manual". The number of cycles and states for each instruction are in chapter 3, for example CPI = 7 states. Then you add up the numbers.


Constructing a binary tree with given traversals I have given a post order & in order traversal a BST & I need to construct it. I want to know how to do this.

for eg.

Post Order : DCBGFEA

In Order : BDCAFGE

This is how I am trying to do :

From POST order it is clear that A is root. So in IN order, I consider everything right to A is at it's right sub tree & so for left.

Now, I consider A's left sub tree. It has BDC. Again from POST order, I conclude that B is root.

Now, again consider B's sub tree. It has contents DC & POST order, C has to be at root. So now I get C at root. But where to place C, at B's left or right ? It's where I am getting stuck now.

Same happening with A's right sub tree also. I place E as root of A's right sub tree. Then I conclude element below should be F, but does it come at right or left of E ?

I want to know how to tackle this problem & also is there any better approach for this to do.

You are doing well. From the postorder determine the root, from the inorder determine which letters are in the left and right subtrees.
Once you have done that, you can proceed in the same way for the subtrees.

In the example you start with postorder DCBGFE A
and inorder BDC A FGE.

Using postorder you determine the root as A, and using inorder split the letters into left BDC and FGE.
Thus (1) the left subtree has postorder DCB and inorder BDC
while (2) the right subtree has
postorder GFE and inorder FGE.

Let us look at left subtree (1) which you mention in your question. The root is B, and both DC follow to B in the inorder and thus are right from B.
How to place them. This tiny subtree has postorder DC and inorder DC. Hence its root is C, and D is before C in the inorder, and is in the left subtree of C.


Upper bound of of fib(n+2) I have a homework problem that is perplexing me because the math is beyond what I have done, although we were told that it was unnecessary to solve this mathematically.  Just provide a close upper bound and justify it.

  Let
  $$f(n) = |\{w ∈ \{a, b\}^n : aa \notin w \}|. $$
  Provide an asymptotic upper bound on $f$ as $n\to\infty$.

So far:
$$
\begin{array}{c|c|c}
n & \text{strings} & \text{compared to } 2^n \\\hline
1 & 2 & 2^n - 0 \\
2 & 3 & 2^n - 1 \\
3 & 5 & 2^n - 3 \\
4 & 8 & 2^n - 8 \\
5 & 13 & 2^n - 18 \\
6 & 21 & 2^n - 43 \\
\end{array}
$$

The math that will give me an exact bound is beyond me.  Obviously $O(2^n)$ is an upper bound, though it is not particularly tight.

Any suggestions on what I should try?

So I'm not completely sure, but I think you're asking to count the number of strings of size $n$ (over the alphabet $\{a, b\}$) where the factor/substring $aa$ does not appear right?

In this case, there are a few combinatorial approaches that you can take. Both Yuval and ADG have given simpler and more intuitive arguments, so I definitely suggest checking their answers out! Here's one of my favorites, it's a little strange, but it's a very general (and kind of a fun) approach.

Let's start with a simpler language, that of words which starts and ends with $b$ (also with no substrings of $aa$). We can look at an admissible string (e.g. $bbb\textbf{a}b\textbf{a}bbbb$) as a list of sequences of $b$s separated by singular $a$s. This gives the construction:
$$
w = (b^+a)^*b^+
$$
Now, how do we count sentences that belongs to this language?

Let's imagine that we're expanding these expressions out. What does $e^*$ denote? Well, it's simply
$$
e^* = \epsilon \mid e \mid ee \mid eee \mid eeee \mid \dots
$$
Now, this will make very little sense, but let's imagine that $e$ is a variable over some numerical field. In particular, we'll treat $\epsilon \to 1$, $a \mid b \to a + b$, and $abc \to a \times b \times c$. This then says that
$$
e^* \to 1 + e + ee + eee + \dots
$$
Let's try to see the motivation behind this strange interpretation. This is almost a bijective transformation. In particular, we want to preserve the count of each $e^n$ word, which, as you can readily see, we do. However, there's one crucial difference between the string expressions and numerical expressions: the multiplication (concatenation in strings, $\times$ in numerical expressions) is now commutative! Intuitively, commutativity lets us treat all permutations of the same word as the same; that is, we don't disambiguate between the expression $bbbab$ and $bbabb$; they both represent a string with 4 $b$s and one $a$. Therefore, this transformation allows us to preserve the count of each word of a certain number of $a$s and $b$s, but it now allows us to turn a blind eye on the superfluous details that we don't care about.

If you go back to precalculus, you might recognize this series as $\frac{1}{1 - e}$. I know that it doesn't make any sense to rewrite this regular expression as a numerically-valued function, but just bare with me for a moment.

Similarly, $e^+ = ee^* \to \frac{e}{1 - e}$. Which means that we can translate $w$ into
$$
w \to \frac{1}{1 - (\frac{b}{1 - b} \times a)} \times \frac{b}{1 - b}
$$

In turn, we can simplify this down to
$$
w(a, b) = b \times \frac{1}{1 - (b + ba)}
$$

This tells us that the language $w$ is isomorphic to the language $b(b \mid ab)^*$ (whose direct translation is already $\frac{b}{1 - b - ba}$) without ever having to resort to any language-theoretic tools! This is one of the power of treating these series as closed-form functions: we can perform simplifications on them that are nearly impossible to perform otherwise, hence reducing it down to a simpler problem.

Now, if you still recall any of your calculus course, you'll recall that certain types of functions (being well-behaving enough) admits these series representations known as Taylor expansions. Don't worry, we won't really have to worry about those pesky Calc 1 problem-sets; I'm just merely pointing out that these functions can be represented as the sum
\begin{align*}
w(a, b) &= \sum_{i,j} w_{ij} a^i b^j
\end{align*}
so that $w_{ij}$ gives the number of words that satisfies $w$ such that it has exactly $i$ occurrences of $a$ and $j$ occurrences of $b$. However, we don't particularly care about whether something is an $a$ or a $b$. Rather, we just care about the total number of characters in the string. To turn a "blind eye" between $a$ and $b$, we can just (literally) treat them the same, e.g. let $z = a = b$ and get
$$
w(z) = w(z, z) = \frac{z}{1 - z - z^2} = \sum_k w_k z^k
$$

where $w_k$ counts the number of satisfiable words of length $k$.

Now, all that's left to do is to find $w_k$. The usual combinatorial approach here would be to decompose this rational function into its partial-fraction: that is, given the denominator $1 - z - z^2 = (z - \phi)(z - \psi)$, we can rewrite $\frac{z}{(z - \phi)(z - \psi)} = \frac{A}{z - \phi} + \frac{B}{z - \psi}$ (There's a bit of algebra involved here, but this is a universal property of rational (one polynomial dividing another) functions). To solve this, you can refactor
$$
\frac{A}{z - \phi} + \frac{B}{z - \psi} = \frac{z}{(z - \phi)(z - \psi)}
$$
which generates the constraints $A + B = 1, A\psi + B\phi = 0$. Irregardless of what $A$ and $B$ are, recall that $\frac{1}{1 - x} = 1 + x + x^2 + \dots$, well, we can rearrange
\begin{align*}
w(z) &= \frac{-A}{\phi - z} + \frac{-B}{\psi - z} \\
&= (-A\phi)\frac{1}{1 - \frac{z}{\phi}} + (-B\psi) \frac{1}{1 - \frac{z}{\psi}} \\
&= (-A\phi)\left(1 + \phi^{-1} z + \phi^{-2} z^2 + \dots\right) + (-B\psi)\left(1 + \psi^{-1} z + \psi^{-2} z^2 + \dots\right)
\end{align*}
therefore
$$
w_k = (-A\phi)\phi^{-k} + (-B\psi)\psi^{-k}
$$
Here, $\phi$ is the golden ratio $\frac{1 + \sqrt{5}}{2}$ and $\psi = -\phi^{-1}$ is its conjugate. We then have an easy description of the asymptotic behavior of the $w$ language: it runs in $\Theta(\phi^n)$. In fact, if you expand everything out, you'll find that
$$
w_k = \frac{\phi^{k} - \psi^{k}}{\sqrt{5}} = \left\lceil \frac{\phi^{k}}{\sqrt{5}} \right\rceil
$$
There's also an intricate connection to another common combinatorial class. This is just the Fibonacci numbers!

Now, suppose you have $w_k$, which counts the number of strings of size $k$ that starts and ends with $k$ (and also contains no $aa$ substrings), how can we build a string that can start or end with an $a$? Well, it's simple: an admissible string is either in $w$ (starts and ends with $b$), or it is $a w$ (starts with $a$), or it is $w a$ (ends with $a$), or it is $a w a$ (starts and ends with $a$). Therefore:
$$
f(n) = w_n + w_{n-2} + 2 * w_{n - 1}
$$
Recall that $w_n$ is the fibonacci sequence, so $w_{n-1} + w_{n-2} = w_n$, which means that
\begin{align*}
f(n) &= (w_n + w_{n-1}) + (w_{n-2} + w_{n-1}) \\
&= w_{n+1} + w_{n} \\
&= w_{n+2}
\end{align*}
Therefore, $f(n) = \text{fib}(n + 2) = \left\lceil \frac{\phi^{n+2}}{\sqrt{5}} \right\rceil$

Now you probably don't have to do this analysis, but just by having the insight that this sequence is a shifted Fibonacci sequence ought to give you an idea of some other combinatorial interpretations that you can try.


Proving the language of non-primes is in NP I am learning about NP problems and found this problem in my textbook that I was not sure how to answer, and was looking for some help on how to start the question.
Show the following language is in NP:
Not-Prime = {n ∈ N: n is not a prime number}
So far, I have created an efficient decider for the language with a certificate, but I'm not sure how to prove that the language is actually in NP. Thank you for any advice!

If you created a deterministic polynomial-time algorithm $A$ that can check a "yes"-certificate for Not-Prime (of polynomial length in the size of instance), then you already proved that your problem is in $\mathsf{NP}$.
Say that a polynomial upper bound on the length of the certificate is $p(s)$, where $s$ is the size of the instance. A non-deterministic polynomial-time algorithm for Not-Prime can do the following:

Guess the length $\ell$ of the certificate in $\{0, \dots, p(s)\}$.
For $i=1, \dots, \ell$: guess the $i$-th bit $c_i$ of the certificate.
Run $A$ on the certificate $c_1 c_2 \dots c_\ell$. If $A$ accepts, accept. Otherwise reject.

A certificate for an instance $n$ of Not-Prime is just a non-trivial prime factor of $n$ (which requires at most $\lceil \log n \rceil$ bits to be represented, so you can pick $p(s)=s$).