Finding the upper bound of states in Minimal Deterministic Finite Automata I have a task to determine the upper bound of states in the Minimal Deterministic Finite Automata that recognizes the language: $
L(A_1) \backslash L(A_2) $, where $ A_1 $ is a Deterministic Finite Automata (DFA) with $n$ states and $A_2$ is Non-deterministic Finite Automata (NFA) with $m$ states.

The way I am trying to solve the problem:

$ L(A_1) \setminus L(A_2) = L(A_1) \cap L(\Sigma^* \backslash L(A_2))$, which is language, that is recognised by an automaton $L'$ with $nm$ states.
Determinization of $L'$ which has $(nm)^2$ states and it is the upper bound of states.

Am I right?

This is wrong. Determinization of an NFA with $r$ states could result in a DFA with up to $2^r$ states. Therefore your argument actually gives an upper bound of
$$2^{nm}. $$
This can be improved if you switch the order of operations. If you first convert your NFA to a DFA and only then apply the product construction, then you get the better bound
$$ n2^m. $$

This bound is tight for infinitely many values of $n,m$. Consider the language $L_2$ of all words over $\Sigma^*\{\sigma_1,\ldots,\sigma_2\}$ that do not contain all letters. There is an NFA for $L_2$ (with multiple initial states) using only $m$ states. However, any NFA for $\overline{L_2}$ needs to contain at least $2^m$ states. Since $\overline{L_2} = \Sigma^* \setminus L_2$ and $\Sigma^*$ can be accepted by a single-state DFA, we see that the bound above is optimal.

You can probably show that the bound is tight for (practically) all $n,m$ by slightly modifying the above construction, replacing $\Sigma^*$ with $(\Sigma^n)^*$.


A minimal automaton for a language quotient $w^{-1}L$ if $L$ is regular For a given language $L$ and $w \in X^{\ast}$ denote by $w^{-1} L := \{ u \in X^{\ast} : wu \in L \}$ the (left) quotients of $L$. The left quotients are closely related to the minimal automaton of $L$ in case $L$ is regular, i.e. in that case $(X, Q, \delta, q_0, F)$
with $Q := \{ w^{-1} L : w \in X^{\ast} \}$, $\delta(w^{-1}L, x) := x^{-1}(w^{-1}L)$,$F := \{ w^{-1}L \in Q : \varepsilon \in w^{-1}L \}$ is isomorphic to the minimal complete automaton accepting $L$.

I am interested in the minimal automaton of a given quotient $w^{-1}L$ in case $L$ is regular, is there a way to construct it? Also as the quotients and the states in a minimal automaton correspond to each other, I am somehow interested in the set $\{ u^{-1}(w^{-1}L) : u \in X^{\ast} \}$ for  given quotient $w^{-1}L$.

Note also that the quotients are closely connected to the Nerode (right) congruence, i.e. $u \sim_L v \Leftrightarrow \forall x \in X^{\ast} : ux \in L \leftrightarrow vx \in L \Leftrightarrow u^{-1}L = v^{-1}L$, giving a bijection between them; and also yielding that the minimal automaton of $L$ is an accepting automaton for the nerode classes.

Now that the question is clarified, I transform my comment into an answer and improve the construction. Our goal is to construct a minimal automaton for $w^{-1}L$ given a minimum automaton $A$ for $L$ and $w$.

It is known that $A$ is isomorphic to the automaton where the state correspond to quotients of $L$. This is the minimal automaton that you describe in your question.

Observe that the quotients of $w^{-1}L$ are also quotients of $L$ since $u^{-1}(w^{-1}L) = (wu)^{-1}L$. Thus, intuitively, you have in $A$ all the states that you need for constructing a minimal automaton for $w^{-1}L$.

First, we claim that the automaton $A$ where we change the initial state to be $w^{-1}L$ recognize $w^{-1}L$. Indeed, by reading $v$ from $w^{-1}L$, you end up in the state $v^{-1}w^{-1}L$. We have then $v \in w^{-1}L$ if and only if $\epsilon \in v^{-1}w^{-1}L$ iff $v^{-1}w^{-1}L$ is final.

Now we have two things to do: first, find the state in $A$ that corresponds to $w^{-1}L$: it is easy, it is the state reached by reading $w$ from $q_0$. Second, we have to minimize this automaton. We claim that if we only keep states that are reachable from state $w^{-1}L$ then we will have a minimal automaton for $w^{-1}L$. Indeed, this automaton still recognize $w^{-1}L$ as we only removed dead state. Moreover each remaining state represents a non-empty quotient of $w^{-1}L$ and two states represent two different quotients. Thus, it has the required minimal size.

To summarize the algorithm:

read $w$ in $A$ and reach state $q$
remove states that can't be reached from $q$
set $q_0 := q$.


Optimal Page Replacement Algorithm - If more than one frame will not be used again, which one gets replaced? This may not make a difference in the end, but not knowing is driving me insane. When using the Optimal algorithm for page replacement, if you need to put something new into a frame and you have more than one frame that will not be used again, how does it prioritize which one to replace? In other words, if you have three frames and you enter in 1, 1, 2, 3, and neither 1 or 2 ever appears again, which one gets bumped when you try to put in 4?

Does it go by FIFO and kick out 1, does it go by most used and kick out 2 or does it go by least recently used and kick out 1?

The optimal algorithm uses whatever is optimal (or one of the optimal possibilities, in case there are several), i.e. whatever produces the least page faults. There isn't necessarily any simpler description of its behavior, though there might be. In general, it depends on the problem; for this specific problem, I don't know whether a simple description exists, though there is probably a simple algorithm that finds an optimal sequence.

FIFO, most used and LRU are heuristics that are useful for the online version; it's not necessarily true that they can be used in any shape or form to obtain optimal page replacement sequences (but you might be able to describe rules for obtaining an optimal sequence using them; I just don't know).


Maintaining search indices with binary trees There are some documents to be indexed, that means I need to read the docs and extract the words and index them by storing at which document they appear and at which position.

For each word initially I am creating a separate file. Consider 2 documents:

document 1: “The Problem of Programming Communication with”
document 2: “Programming of Arithmetic Operations”

Here, there are 10 words, 8 unique. So I create 8 files (the, problem, of, programming, communications, with, arithmetic, operations).

In each file, I will store at which document they appear and at what position. The actual structure I am implementing has lot more information but this basic structure will serve the purpose.

file name        file content
the              1 1
problem          1 2
of               1 3 2 2
programming      1 4 2 1
communications   1 5
with             1 6
arithmetic       2 3
operations       2 4

Meaning. the word is located at document 1, position 3 and at document 2, position 2.

After the initial index is done I will concatenate all the files into a single index file and in another file I store the offset where a particular word will be found.

index file: 1 1 1 2 1 3 2 2 1 4 2 1 1 5 1 6 2 3 2 4
offset file: the 1 problem 3 of 5 programming 9 communications 13  with 15 arithmetic 17 operations 19

So if I need the index information for communications, I will go to position 13 of the file and read up to position 15 excluded, in other words the offset of the next word.

This is all fine for static indexing. But if I change a single index the whole file will need to be rewritten. Can I use a binary tree as the index file's structure, so that I can dynamically change the file content and update the offset somehow ?

if I change a single index the whole file will need to be rewritten

So don't change indices. When you add data, remember what words already existed, and store subsequent words afterward. For each word, instead of storing one index in the index file, store several.

There is a lot to optimize on top of that. But I don't think this is a productive use of your time. There are existing programs that can do this (and far more complex use cases, too) very efficiently and without raising a sweat: databases. Use a database engine (Berkeley DB, SQlite, NoSQL, MySQL, TSQL, …).

If you want to understand how to store this kind of data efficiently, read about implementations of database engines. B-trees will be involved at some point.


NPDA for $\{w : w \in \{a,b\}^*,n_a(w)\geq n_b(w)+1 \}$ I believe that the following NPDA accepts the language
$$\{w : w \in \{a,b\}^*,n_a(w)= n_b(w)+1 \}\,,$$
where $n_a(w)$ represents number of symbol $a$'s in string $w$.

Is there a two-state NPDA that accepts the same language?

"Is there a two-state NPDA that accepts the same language?"

Yes, every PDA can be replaced by one that has two states, one accepting and one non-accepting. In general one uses three steps to prove this formally:

Every PDA (with empty stack acceptance) can be transformed into a CFG. The construction is sometimes known as the triplet construction: a single nonterminal of the CFG codes two states and a stack symbol of the PDA.
Every CFG can be transformed into a PDA with a single state and empty stack acceptance. That equivalence is quite straghtforward.
PDA with empty stack acceptance are equivalent to PDA with final state acceptance. But, where the stack-PDA may have a single state, the state-PDA usually uses one more, for acceptance.

Always, when discussing PDA, be explicit on the acceptance mode. (But that might be a silly request when your textbook considers only one of these types.)

PS. By the way, your machine seems to have the basic counting ideas implemented.


When did polynomial-time algorithm become of interest? I would like to understand why and when polynomial algorithms became of interest.

When did people realize the role and importance of efficient versus non-efficient algorithms? Did that happen when the concept of an algorithm was discovered, or the the term algorithm used.

For instance, I've looked at some textbook of Algorithms such as the one by Cover, Leiserson, Rivest, and Stein "Introduction to Algorithms" 3rd ed. they states in the Preface "Before there were computers, there were algorithms. But now that there are computers, there are even more algorithms, and algorithms lie at the heart of computing".

Would it be the case that, before computers were invented, we were more interested in finding new ideas for solving problems, and were not so concerned with the time it took.

So I am interested in knowing when people became conscious of the importance of efficiency,  started to study it more systematically.

Are there some reference papers on the subject, on the history of algorithms and their motivations, and on the concern with efficiency.

[note from the translator]
The topic of the question may seem a bit wide, as I tried to keep the meaning without betraying the author. But it seems a good and useful general question that can be adressed with a few general remarks and some facts and examples

Since this question was reopened and made more explicit, I would like to convert my comment into an answer. Now the OP wants to understand

  why and when polynomial algorithms became of interest.

I especially focus on the sub-question:

  When did people realize the role and importance of efficient versus non-efficient algorithms?

Because algorithms, in its general terms, have existed since ancient times, it is hard to identify the person who is the first to highly praise the polynomial algorithms(, and when and why). However, there is a famous person who has explicitly advocated the polynomial algorithms. It is Jack Edmonds, in the paper Paths, Trees, and Flowers; 1965.

In Introduction, the author claims

  We describe an efficient algorithm for finding in a given graph a matching of maximum cardinality.

Then in the second section titled "Digression", the author

  An explanation is due on the use of the words "efficient algorithm".

Then come the explanations:

  There is an obvious finite algorithm, but that algorithm increases in difficulty exponentially with the size of the graph. It is by no means obvious whether or not there exists an algorithm whose difficulty increases only algebraically with the size of the graph.

  When the measure of problem-size is reasonable and when the sizes assume values
  arbitrarily large, an asymptotic estimate of $\ldots$ the order of difficulty of an algorithm is theoretically important.

  For practical purposes the difference between algebraic and exponential order is often more crucial than the difference between finite and non-finite.

  However, if only to motivate the search for good, practical algorithms, it is important to realize that it is mathematically sensible even to question their existence. For one thing the task can then be described in terms of concrete conjectures.

ADDED: I have just happened to found a third-party confirmation that it was Jack Edmonds who originally advocated the polynomial algorithms.

The following is quoted from Section 2.18.1 of the book "Applied Combinatorics (second edition)" by Fred Roberts and Barry Tesman.

  A generally accepted principle is that an algorithm is good if it is polynomial. This idea is originally due to Edmonds [1965].


How to define an automata for zig zag concatenation? I have two DFAs one for language A and one for language B.
I'm asked to make an FDA that is the zig-zag concatenation of letters of A and letters of B.
This is described by the following: {w: w = $a_1 b_1$...$a_k b_k$ and $a_1...a_k \in A$ and $b_1 ... b_k \in B$}. With $1 \leq i \leq k$ and $a_i \in \Sigma$ and $b_i \in \Sigma$

This automata should be described as a 5-tuple {Q, $\Sigma$,$\delta$,$q_0$,$F$}.

I simply do not know how I would go about defining the total function $\delta$.

This is what I tried:

$Q = Q_A \cap Q_B$ // We only want the words that contains both a and b

$F = F_A \cap F_B$ // The accepted states should contain both letter from a and from b.

$q_0 = q_A$ //because the word starts with a letter from a.

$\Sigma$ // in this problem we aren't interested in defining the alphabet we just leave the symbol as is in the 5-tuple.

let $Q=Q_A\times Q_B\times \{1,2\}$ (1 means A, 2 means B)

also define $F=F_A\times F_B\times \{2\}$  (we end with B)

and $q_0=(q_A,q_B,1)$ (we start with A)

with the delta function: $\delta ((q_1,q_2, i),\sigma)=
      \begin{cases}
      (\delta(q_1,\sigma),q_2,2) &i=1 \\
      (q_1, \delta(q_2,\sigma),1) &i=2
   \end{cases}$

The idea is to encode both A and B together, with some "index" telling us if we need to check A or B


Is it correct to say that CPU's only compute threads? New to the world of parallel computation. Would it be correct to say that CPU's are actually thread calculators? My understanding currently: a process is composed of multiple threads and a single core on a cpu is capable of executing instructions from 1 thread at a time, sometimes a bit more when taking into account hyper-threading, but essentially it is computing threads. When the CPU, along with  all of its cores, are done calculating all of the threads that belong to a specific process then that process would be considered complete.

So like an analogy would be:

A CPU is like a monkey, with N number of mouths (cores). Each mouth is responsable for eating a long chain of bananas (threads) out of wooden crates (processes). We can increase the rate at which some program is finished/emptied, by hooking up more banana chains from it to an empty and waiting core/mouth. A program is called complete if the wooden crate is emptied of all bananas.

Would this interpretation be correct?

Below is an illustration of my current understanding

also what are some of the practical differences (programming-wise) of what I can/cannot do with spawning new processes vs threads. I always see something along the lines of processes have their own memory while threads share it but what do they really mean by that? Like in python, can I just go like from thread_a import var_something?

Take a step back. In most operating systems, a process is an entity that owns resources, like memory areas, open files, and such. A thread is an entity that can be scheduled (i.e., get a CPU core assigned, has its own contents of registers and local variables). Several threads can exist within the same process, sharing it's resources.

Switching between threads that share memory means that the table pages and cache entries don't have to be flushed, and that is a major cost in current processors (today to access a word in memory can take the same time than hundreds of instructions!).

Note that some systems (like Linux) have a non-standard view of threads, in that you can create a new thread from an existing one and specify in detail exactly what they are to share.

Is using threads or processes a win? No way to answer in full generality. If different threads of execution don't use the same data, it won't matter much (see above), and it can be advantageous for them not to be able to trample on each other's work. Use processes. If they share data intimately, threads are a better match (and will be more efficient). But then again, having several cores accessing the same data gives rise to cache ping-pong and bad performance. Also, taking such a program and rewrite to run on a distributed system (note that current massive machines are NUMA, essentially separate machines connected by an insanely fast network, but still much slower than direct access to memory) will be much harder.


Encoding huge number of tape-symbols of a turing machine in the simulation of the turing-machine using real computer I was going through the classic text "Introduction to Automata Theory, Languages and Computation" by Hopcroft,Ullman,Motwani where I came across the simulation of a turing machine using a real computer. There the author argued that it shall be almost impossible to carryout the above simulation (not considering universal turing machine) if the number of tape symbols are quite huge. In such a situation it might happen that the code of a tape symbol might not fit in the single hard-disk of a computer.

Then the author makes a claim as:

  There would have to be very many tape symbols indeed, since a 30 gigabyte disk, for instance, can represent any of $2^{240000000000}$ symbols.

Now I can't figure out the specific mathematics that the author does...

I assume the usual encoding as we do in digital logic say to encode $8$ symbols we need atleast $3$ bits of code.
Then to represent $n$ symbols if $k$ bits are required then we should have the following relation,

$2^{k} = n$

$\implies$ $k=log_2(n)$

Now,

$30$ $gigabytes$ $= 30 \times 2^{33}$ $bits$ $= \beta (say)$

Now if our disk can hold all the $n$ symbols then we shall have the following relation true:

$Disk$ $size$ $= (Bits$ $required$ $for$ $each$ $symbol$) $\times$ ($number$ $of$ $symbols)$

$\implies$ $\beta = k \times n = (log_2(n)\times n)$

Solving graphically I have:

$n= 7.8 \times 10^{9}$ , which is no where close to the number $2^{240000000000}$

Where am I making the mistake?

You are interpreting this statement backwards - he is not calculating how many symbols can 30 gigabytes represent, he is calculating how many symbols can be represented by using 30 gigabytes to represent a single symbol!  That would be necessary to be able to approximate a calculation where each symbol is an infinitely-precise real number.


Nested Big O-notation Let's say I have a graph $|G|$ with $|E|=O(V^2)$ edges. I want to run BFS on $G$ which has a running time of $O(V+E)$.

It feels natural to write that the running time on this graph would be $O(O(V^2)+V)$ and then simplify to $O(V^2)$.

Are there any pitfalls to using such a "remove-the-nested-O" shortcut (not just in this case, but more generally)?

Let me start of with a recommendation: treat Landau notation just as you (should) treat rounding: round rarely, round late. If you know something more precise than $O(.)$, use it until you are done with all calculations, and Landauify at the end.

As for the question, let's dig through this abuse of notation¹. How would we interpret something like $h \in O(f + O(g))$? We should replace $O$ with its definition from the inside out. So, we get

$\qquad \displaystyle \exists g' \in O(g).\, h \in O(f + g')$

and then

$\qquad \displaystyle \exists g' \in O(g).\,\exists d>0.\, \forall n.\, h(n) \leq d(f(n) + g'(n))$

which is equivalent to

$\qquad \displaystyle \exists c > 0.\,\exists d>0.\, \forall n.\, h(n) \leq d(f(n) + cg(n))$.

As certainly² $d(f(n) + cg(n)) \leq cd(f(n) + g(n))$, we see that this is equivalent to $h \in O(f + g)$; the loss of precision is ignored by $O$ anyway.

What about other combinations, say $h \in O(f + \Omega(g))$? If we try the same here, we get

$\qquad \displaystyle \exists g' \in \Omega(g).\, h \in O(f + g')$.

But this is a tautology: $h$ is certainly bounded above by something arbitrarily large. So, combining upper and lower bounds in this fashion is not meaningful.

$O(.)$ and the other Landau symbols map functions to function classes. Feeding it a function class is not immediately meaningful.
At least if we consider only positive functions, which we can safely assume when talking about runtimes. I'm not sure this works in general.


What is the Name of This Problem? Given two integers $a$ and $b$, determine if $a$ and $b$ are equivalent modulo any $k \, (k: 1 \lt k \lt |a - b|)$.

If $\exists$ an integer $ (k: 1 \lt k \lt |a - b|) \text{ and }a \equiv b \mod k$, then the algorithm would return true, otherwise it would return false.

I thought of this problem today.

Before attempting to solve it, I want to know if there is existing literature on the problem. However, I would need to know the problem to do research on it.

You just need to check if $|a-b|$ is divisible by a some integer $k$. You can reduce it to the integer factorization problem if you are not interested in the trivial divisors 1 and $|a-b|$.


What is the difference between "Decision" and "Verification" in complexity theory? In Michael Sipser's Theory of Computation on page 270 he writes:

  P = the class of languages for which membership can be decided quickly.
  NP = the class of languages for which membership can be verified quickly.

What is the difference between "decided" and "verified"?

The task of deciding membership is: given any input $x$, decide wether $x \in L$, i.e. compute the following function:

$\qquad \displaystyle \chi_L(x) = \begin{cases}1 &x \in L \\ 0 & x\notin L\end{cases}$

On the other hand, the task of verifying membership is: given any input $x$ and a (proposed) proof (or witness) of membership, check quickly wether $x\in L$ by that proof¹.

For example, consider prime factorisation. Given $n \in \mathbb{N}$, compute all prime factors of $n$. On the other hand, given $(n, \{i_1, \dots, i_k\})$, verify that $\prod_{j=1}^k i_j = n$. Which is easier?

Another example: Given a weighted graph $G = (V,E)$, decide wether there is a Hamilton circle (that visits all nodes) with weight at most $k$. On the other hand, given $(G, (v_1, \dots, v_n))$, verify wether the path $v_1 \to \dots \to v_n$ visits all nodes exactly once and has weight at most $k$. Which is harder?

So you will say "no" if $x \in L$ but the proof is wrong. That is fine, though, as we consider nondeterministic machines in this context; it is only important that we can guess the correct proof and verify it (quickly).


Variant of nim game with particular rules Let's say we have the following rule for that particular Nim game: You have multiple heaps, and you have to remove 1,2 or 3 sticks (not more) from a SINGLE choosen heap. The player who pick up the last stick LOSES. (misere game). Is there an algorithm which solves this variant of Nim game ?

Thanks in advance!

The following answer solves your game under normal play when there is a single heap. You can accommodate multiple heaps using Sprague–Grundy theory. Using a very similar approach, you can also handle misère rules.

You can solve combinatorial games by calculating the winning and losing positions recursively, using the following algorithm (for your special case):

for n from 0 to infinity:
   set Win[n] to True if n ≥ 1 and Win[n-1] is False
   set Win[n] to True if n ≥ 2 and Win[n-2] is False
   set Win[n] to True if n ≥ 3 and Win[n-3] is False
   otherwise, set Win[n] to False

Here are some empirical results, starting at $n=0$:

False, True, True, True, False, True, True, True, False, True, True, True

The pattern repeats, so one can conjecture that $Win[n]$ is true iff $n$ is not a multiple of 4. It is not hard to prove this guess by induction. Clearly 0 is a losing position, and 1,2,3 are winning positions since we can remove 1,2,3 (respectively) to get to 0. Now 4 is a losing position, since whatever we remove gets us to one of the winning positions 1,2,3. As before, 5,6,7 are winning positions, since we can get down to 4. And so on.

In the same way, you can compute the Sprague–Grundy function, which is $g(n) = n \bmod 4$. This allows you to solve the multiple heap version of this game.


Searching in sorted array with $O(\log n)$ Recently been practicing some recent exams, there was a problem I could not comprehend the given answer, the question is as follows:

Suppose array $A[1..n]$ consist of $n$ distinct integers that is
sorted in ascending order, then How many of below problems could be
solved in $O(\log n)$?

and there were three statements;

Find an $i$ index so that $A[i]= i $
Find an $i$ index so that $A \left \lfloor{i}\right \rfloor = 3i +2$
Find an $i$ index so that $A[i]= 4i^{2} + 3i + 5$

The answer sheet stated as one statement is true, Also there was no clue on which statement is true.

What is my issue?
So I think the first and second statements could be true, since the array is sorted then we can use Binary search with $O(\log n)$ to find the element with index $i$, also the first two statements are linear, thus I think that's what the question wants, If it's not then I don't know what the question exactly wants, any explanation would be handful.

You can answer the first question with binary search. Lets consider you're now discussing the interval $[l, r]$, and $m = \frac{(l + r)}{2}$. If $A[m] = m$, you have found an answer and you shall stop the search. If $A[m] < m$, then the answer must be in the interval $[m + 1, r]$, because if $i \le m$, then $A[i] \le A[m] - (m - i) < m - (m - i) = i$ (since the array is sorted in strictly ascending order and the elements are integers), thus no $i \in [l, m]$ can be the answer. Otherwise, if $A[m] > m$, then the answer must be in the interval $[l, m - 1]$, because if $i \ge m$, then $A[i] \ge A[m] + (i - m) > m + (i - m) = i$.
And I don't think you can solve the other tasks in $O(lg(n))$ using binary search. Consider these two examples :
$A = [5, 6, 12, 14, 15]$
$B = [4, 9, 12, 14, 17]$
As we know, binary search initially examines the middle element, in these cases, $12$. $12 \ne 3 \times 3 + 2$, thus the search has to continue. In both cases, decision must be the same, since the middle element is the same, therefore, if the algorithm decides to check the interval $[4, 5]$, the algorithm will respond NO to the array $A$, although $5 = 3 \times 1 + 2$, and if the algorithm decides to search the interval $[1, 2]$, it yields NO to the array $B$, while $17 = 3 \times 5 + 2$.
It is also true about the third task, with examples :
$A = [13, 49, 51, 52, 180]$
$B = [12, 48, 51, 52, 193]$
I hope my answer was helpful.


Validating authenticity of a file Suppose there's an entity which produces files. User A has one of those files and decides to send it to user B.

How can user B validate the authenticity of the file without communicating with the producer? Is it even possible?

It depends on what you call "without communicating". How does B know that A really exists ? Either B speaks to A, or C tells to B that A exists, and B trusts C.

So, if a trusted C exists, C may provide to B a key to authenticate A. If a trusted C doesn't exist, B can't know if A exist, and authenticate its messages makes no sense.


We can control tcp/udp traffic using router. Then why is it in Network layer and not transport layer? Routers make use of the IP address, etc to shape the traffic. So obviously they must reside in at least the Network layer.
However we can also shape the traffic using tcp/udp. Routers usually have the port forwarding feature which allows them to shape the tcp/udp traffic.

The IP header has a field for protocol. However that doesn't show whether the traffic is udp/tcp. This information must be present inside the payload part of the IP packet. Then why is the router able to see that information despite being in the Network Layer?

Because routers are real concrete devices, not theoretical constructs.  They aren't limited by layering diagrams.  Layering is a form of abstraction, which is a convention; there's nothing that prevents a device from inspecting and acting on the rest of the packet.

Separately: layering diagrams are a model, but not a perfect one.  Real devices violate layering from time to time.  The OSI 7-layer model is especially approximate -- don't take it too seriously.  See, e.g., Till which layer does the loopback packet goes? and can network layers communicate between each other?.


Reflection on Concurrency Reflection is a common mechanism for accessing and changing the structure of a program at run-time, found in many dynamic programming languages such as Smalltalk, Ruby and Python, and in impoverished form in Java and (hence) Scala. Functional languages such as LISP and Scheme also support a good reflect framework.

Modern languages support concurrency, either by adding threads on top of the existing language constructs, or by designing from the ground up with concurrency in mind.

My question is:

  What models of reflection for the concurrency aspects in concurrent languages (multi-threaded, actor-based, active-object-based) exist?

The closest I can think of is the MetaKlaim language. Klaim is a process calculus with asynchronous communication via tuple spaces. MetaKlaim is an extension of Klaim that integrates the meta-programming features of MetaML, namely multi-stage programming with types. (You may be more familiar with the syntax of MetaOCaml)

I am not an expert in any of these fields, so I don't really know if multi-stage programming fit in this definition of reflection. (I know this does not capture all aspects of reflection anyway so that's at most a partial answer).


Matching 2 sets of items by price I'm trying to solve the following problem in the most efficient way I can find.

I want to trade my items for someone elses items, every item have a price and a value.

I want to maximize the value of the items I trade, so for example:
My items:

  Banana, P: 10, V: 5
  Pen, P: 3, V: 1
  Paper, P: 1, V: 1

Their Items:

  Phone, P: 10, V: 8
  Key, P: 1, V: 2
  Wallet, P: 30, V: 100

You can see that I can trade my Banana and Paper (with value of 6) with Phone and Key (with value of 10)

I can overpay but can not pay less and the amount I overpay is lost.
Currently my solution is to use generate all the possible combinations of my items and try to match the price with knapsack algorithm and check each result.

This is however very not efficient because I can have over 1000 items (both mine and the other person).

Does anyone have a possible solution to this problem? I need it to be efficient but also give me the best solution (best value)

The items are not infinite and they have a limit.

Assume you have a table of items of quantity Q, price P and Value, V and a computed value ratio P/V for each item.

I would use a Successive Approximation Register approach using the most significant item rated by P/V ratio using a product sum that does not exceed the total or consumes all your inventory of that item then repeat down your ranked list by Price/value ratio. Just as SAR is the fastest for ADC's, this would be my optimum solution.

The trade may not be attractive to the other person, since you have offered items with the least value to you, so a practical solution must consider the V/P ratio of your item to  the other person, which may be unknown.

Tony
EE since 1975.


Is escaping a concept in CS? I understand "escaping data" as making an exception when matching data; for example, if a program can't match data wrapped in some character/s (such as single and/or double quotes) without an exception, than we make an exception when "escaping" such character/s to be matched.
Is escaping a concept in CS?
Is it "part of how any computer would work" or just a technical implementation in human-developed programming languages?

Escaping characters is part of an abstraction, most commonly pertaining to programming languages.  Computer architectures, specifically at the sub-ISA level, don't know anything about it.


Can this grammar be simplified? So, I have a book here, which has an example for context sensitive grammar, and the grammar is the famous $0^n1^n2^n$ , and it has:

$$ \begin{align}
S  &\rightarrow 0BS2 \mid 012 \\
B0 &\rightarrow 0B \\
B1 &\rightarrow 11 \\
\end{align} $$

I agree that the above works, but what is wrong with just saying:
$S\rightarrow 0S12 |\epsilon$

The above also generators the same number of $0$s as $1$s and $2$s.

Your grammar will generate:
$S\rightarrow 0S12\rightarrow 00S1212\rightarrow 001212$ which is not in the required language.


Machine with an oracle for a language that cannot decide another language in polynomial time We usually see examples of languages contained in $P^A$ for some language $A$, or cases where $P^A=P^B$ (or $P^A\subseteq P^B$) for two languages $P^A$ and $P^B$.

However, there is any explicit example of two languages $A$ and $B$ such that $P^A\not\subseteq P^B$ and $P^A\not\supseteq P^B$?

I was thinking in something like $\mbox{HALT}$ and $\mbox{EMPTY}$ but Yuval Filmus made me see that in fact $P^{\mbox{HALT}} \subseteq P^{\mbox{EMPTY}}$, because $\mbox{EMPTY}$ is stronger than $\mbox{HALT}$. Nevertheless is possible to find an explicit language satisfying the desired property? What about $\mbox{FINITE}=\{<M>: L(M) \mbox{ is finite}\}$, it can be compared with $\mbox{HALT}$ in the same way as $\mbox{EMPTY}$?

Let $A,B$ be two incomparable Turing degrees (these can be constructed by diagonalization, known in this context as forcing). If $P^A \subseteq P^B$ then in particular $A \in P^B$, and so $A$ reduces to $B$; since we know this is impossible, we can conclude that $P^A \nsubseteq P^B$. Similarly $P^A \nsupseteq P^B$.


Solving recurrence with logarithm squared $T(n)=2T(n/2) + n \log^2n$ $T(n)=2T(n/2) + n\log^2(n)$.

If I try to substitute $m = \log(n)$ I end up with

$T(2^m)=2 T(2^{m-1}) + 2^m\log^{2}(2^m)$.

Which isn't helpful to me. Any clues?

PS. hope this isn't too localized. I specified that the problem was a squared logarithm which should make it possible to find for others wondering about the same thing.

This is indeed the second case in the Master Theorem. For the standard recursion form $$T(n)=a\;T(n/b)+f(n),$$
you get $a=b=2$, and therefore  $f(n)=\Theta(n^{\log_b a} \log^2 n)=\Theta(n  \log^2 n)$.

Applying the Master theorem yields $T(n)=\Theta(n\log^3 n)$.


Detecting rotational symmetries of spatial structures I have a spatial graph-like structure. The structure consists of vertices in the 3D space and connecting edges. Are there any algorithms available that would identify the rotational symmetries of these structures? In particular, I'm interested in all the rotational axis along which I can rotate the structure to overlap itself, as well as the degree of rotation. For example, an equilateral triangle (3 vertices + 3 edges) would have one rotational axis perpendicular to its plane, with a degree of 3 and 3 others in its plane, with a degree of 2 each.
The closest I could find are molecular packages identifying the symmetry groups of molecular structures. I would prefer not to go that far as I'm only interested in rotational symmetries and not entire group theory description of structures.

Here is one approach  to identify all rotational symmetries of the graph:

Pick any three vertices, $v_1,\dots,v_3$.  Loop over all possible combinations of three vertices $w_1,\dots,w_3$.  For each such combination, find the unique rotation that maps $v_1 \mapsto w_1,\dots,v_3 \mapsto w_3$, then check whether this is a rotational symmetry of the entire graph (by mapping the entire graph and seeing whether the mapped graph coincides with the original graph).

The worst-case running time will be something like $O(n^4)$, where $n$ is the number of vertices in the graph.  In practice I expect it to be typically more like $O(n^3)$, as most candidate rotations can be immediately rejected by testing a few vertices.

To identify the unique rotation that maps $v_1 \mapsto w_1,\dots,v_3 \mapsto w_3$, given $v_1,\dots,v_3,w_1,\dots,w_3$, see https://math.stackexchange.com/q/3341635/14578.


What is practical difference between NP and PSPACE-complete? Here's something that has puzzled me lately, and perhaps someone can explain what I'm missing.

Problems in NP are those that can be solved on a NDTM in polynomial time. Now assuming P$\,\neq\,$NP, PSPACE$\,\neq\,$NP etc. this means that there are NP-complete problems that cannot be solved in polynomial time on a DTM. Which means that either they have some complexity that lies between polynomial and exponential (which I am not sure what that might be) or they must take exponential time on a DTM (and no more than polynomial space). If its the latter, then consider the PSPACE-complete problems. A problem is in PSPACE if it can be solved using a polynomial amount of space. Since NP$\,\subseteq\,$PSPACE$\,\subseteq\,$EXPTIME, PSPACE-complete problems must also take exponential time on a DTM. Then what is the practical difference between NP-complete and PSPACE-complete problems?

I think it depends on what you're interested in. If you're looking for an exact solution to a problem and you hear that it's either NP-hard or PSPACE-hard, then in either case you won't be able to find an algorithm for that problem that is simultaneously worst-case efficient, deterministic, and always correct unless P = NP or P = PSPACE. Therefore, if you're just looking for whether the problem is efficiently solvable in all cases, both NP-hardness and PSPACE-hardness probably means that you're out of luck.

However, if that's not the lens you're looking through, then (based on the suspicion that NP ≠ PSPACE) there's a difference between NP-completeness and PSPACE-completeness. If a problem is NP-complete, then even if you can't solve the problem efficiently, you can still check "yes" answers efficiently. On the other hand, if NP ≠ PSPACE and you have an instance of a PSPACE-complete problem you're convinced has a "yes" answer, there might not be any efficient way to convince someone else of this.

Hope this helps!


Transforming an NFA into an NFA of similar size but without $\epsilon$-transitions I'm learning for the exam and have problems with this task:

  Describe an algorithm that transforms a given NFA $A = (Q, \Sigma, \delta, q_0, F)$ (which may have $\epsilon$-transitions) into an equivalent NFA without $\epsilon$-transitions with the same condition number. And then determine the maturity of the algorithm. The algorithm should have a running time $O(|Q| · |\delta|)$ where
  $$|\delta| := \sum_{\substack{q\in Q\\ a\in\Sigma\cup\{\epsilon\}}} |\delta(q,a)|$$

The obvious answer is: the powerset construction gets rid of $\varepsilon$-transitions, so you can use it. It blows up the automaton exponentially in the worst case, though, so it is not directly applicable. However, you can use the part that deals with $\varepsilon$-transitions and keep nondeterminism.

   That is, if a state $q$ has an $\varepsilon$-transition to $q'$, add all outgoing transitions of $q'$ to $q$ and remove the $\varepsilon$-transition.
 You have to iterate this process for every state because there may be chains of $\varepsilon$-transitions. In the worst case, you reach all transitions (for every state), causing the required runtime bound (to be sharp).

Note that formally, this does not change the number of states. It might lead to isolated states, though, that can safely be dropped.


Maximize AND on a sequence of XORs Problem
We are given 2 arrays a and b both of length n. We build a third array c by rearranging the values in b. The goal is to find the optimal c that maximizes
result = (a[0] ^ c[0]) & (a[1] ^ c[1]) & ... & (a[n - 1] ^ c[n - 1])

where ^ is XOR and & is AND.
Is it possible to do this efficiently? It's straightforward to iterate through all possible permutations of b, but this is infeasible for large n.
More details

The order of the values in a is fixed.
The order of the values in b may be rearranged to form c. That is, starting with b = [1, 2, 3], it may be that the maximum result is obtained when the values are rearranged to c = [2, 1, 3].
b may be rearranged in-place if needed.
Since the optimal c is not necessarily unique, any optimal c may be returned.
Assume all values are 32-bit unsigned integers.
1 <= n <= 10,000.

Test cases
Input:
a = [3, 4, 5]
b = [6, 7, 8]
Output:
c = [8, 7, 6] (result = 3)

Input:
a = [1, 11, 7, 4, 10, 11]
b = [6, 20, 8, 9, 10, 7]
Output:
c = [8, 6, 10, 9, 7, 20] (result = 9)

Input:
a = [0, 1, 2, 4, 8, 16]
b = [512, 256, 128, 64, 32, 16]
Output:
c = [16, 32, 64, 128, 256, 512] (result = 0)

For bit #k to be set in the output, you need to arrange the numbers so that bit #k is either set in a[i] and cleared in c[i] or the other way round. Therefore bit #k must be set in exactly n of your 2n inputs. If that is not the case then bit #k cannot be set in the output. So first you determine all k such that bit #k is set in exactly n of the 2n inputs, and ignore all other ks.
Let k be the highest of these bit positions. Split the elements of b into those where bit #k is set and those where it is cleared, and pick c[i] from the correct one of these sets. That's always possible.
Let j be the second highest of these bit positions. Split the elements of b into four sets, where bit #k and #j are both set, bit #k is set and bit #j is cleared, etc. Depending on which bits in a[i] are set, you know from which subset of b you need to pick c[i]. This only works if the sets have the right sizes! If it doesn't work, ignore bit j and take the next highest bit. If it works you can set bit #k and #j in the result and proceed with the next higher bit.


Do poly-time algorithms exist whose time complexity is unprovable? If not, is there a decision procedure that successfully classifies any
polynomial time algorithm as poly-time within a time polynomially bounded
by the length of the input algorithm?

Here is an example. Suppose that you're working within axiom system A, say ZFC. Gödel showed that if A is consistent then A can't prove that A is consistent. Consider the following program:

  On input $x$, go over all strings of length $\log |x|$, and check if one of them is a proof of the consistency of A. If so, loop for $2^{|x|}$ iterations. Otherwise, halt.

This is polynomial time if and only if A is consistent. If A could prove that this algorithm terminates in polynomial time then A has just proved that A is consistent, which is impossible if A is indeed consistent. Yet if we believe that A is consistent, then the machine does run polynomial time; but A unfortunately isn't strong enough to prove it.

Your second question asks whether there is an algorithm that, given a Turing machine $T$, answers in polynomial time whether $T$ is a polynomial time Turing machine. Unfortunately, this is undecidable. Suppose that we only consider Turing machines which don't depend on their input (say the first thing they do is erase their input). Such a machine $T$ runs is polynomial time if and only if it halts on the empty tape. Deciding whether a Turing machine halts is impossible.


Does a given e-NFA accepts all the Strings? Given an e-NFA. It is easy to find a string that is accepted by it. But, how do we find if the given e-NFA accepts "All" the strings over the alphabet. Or if there is a string that is not accepted by it.

Of course the usual way is to construct a DFA, or complement the e-NFA but since we are talking about the whole language, I was wondering if there is a much more efficent method in the worst case.

A classical result, attributed to Meyer and Stockmeyer, is that checking whether an NFA accepts all strings is PSPACE-complete. Nevertheless, there are some non-trivial heuristic algorithms. See for example Antichains: A New Algorithm for Checking Universality of Finite Automata by De Wulf, Doyen, Henzinger and Raskin.


Using a context free grammar to generate sample utterances for Amazon Alexa/Google Assistant? I would like to get some opinions about using a context free grammar to generate sample utterances for Amazon Alexa/Google Assistant skills.

When developing these skills one has to provide a large number of sample utterances, i.e. sentences with which a user could try to invoke a particular feature of the skill. So when the skill is about ordering chocolate I would have to provide sentences like...

i would like to buy chocolate
i would like to order chocolate
we would like to buy chocolate
we would like to order chocolate

...and so on. the number of these sentences tends to grow almost exponentially, yet even with hundreds of them they still often become the bottleneck of the entire skill because users tend to come up with new formulations that weren't anticipated.

There are some tools available that can generate these sentences from simple patterns, i.e. this

{i|we} would like to {buy|order} chocolate

would produce the four variations given above. The drawback of this approach is that usually not all permutations of the pattern are valid (in most cases it is only a small subset of them) and one would thus need another "grammar" on top of these patterns to tell which are. The patterns are also not standardized and thus tied to one particular tool.

So I was looking for a better way to generate these sample utterances, and came across an approach that generates sentences from a context free grammar. This looks very promising to me, and in a small test script I was able to generate a large number of sentences from a very small grammar, with limitations on the sentences structure that I would have been able to include in the patterns of the existing tools.

I am however not a exactly an expert in Theoretical Computer Science and would like to ask a few questions before exploring this further:

My understanding is that a CFG is basically a "pattern" in the form of a tree. It would thus work similar to the patterns described above, but with the additional benefit of having the rules about which permutations of variables are legal embedded in the pattern itself. Is that correct?
If the CFG really is just a more complex pattern that would also mean that this approach (generating sentences from a CFG) can not produce grammatical variations of the generated sentences, e.g. it would not be able to generate pluralized forms like i would like to see _my_ shopping cart -> we would like to see _our_ shopping cart. Is that right?
More generally: From the hierarchy of formal languages, is a CFG really the best solution to this problem, our should I experiment with other types of grammars?

As I've said, it is entirely possible that I am misunderstanding some fundamental things about CFGs here, I am really just looking for some external feedback on this idea before investing more time in it. Thanks!

I don't think that will be effective.  I don't recommend this approach.  I think there's a significant risk that the machine learning will just learn to handle those specific synthetic variants, but not get any better at handling real speech.  It might even get worse, if you cause the ML to overfit to your synthetic variants.

The problem is that real speech has a lot of variety in how people express things.  Your synthetic examples are not going to capture that variety.  Training machine learning on synthetic examples that aren't representative of what it will see during deployment is not likely to be effective.  I suggest you try to obtain more realistic data, even if it can't be easily programmatically generated.


How a 10GB network can copy 1TB data in 2 hours? In the slides of a university lecture, the following phrase got my attention.

Assuming 10GB network, it takes 2 hours to copy 1TB.

My calculation was as follows.

10GB network = 10 gigabits per second network = 10 x 10^9 bits per
second ------> (1)
1TB = 10^3 x 10^9 x 8 bits --------------> (2)
Then the time to copy 1TB data = (2) / (1) = 8 x (10^12) / (10^10) =
800s = 13.33 minutes

I'm not getting 2 hours as the result of the above calculation, seems like I have got something wrong.
Can someone please educate me on this? Thanks in advance.

You have just done the calculation with the raw data to be transferred and not taken into account of the overhead of transferring data using networking protocols across any particular  network. Almost no networking technology transfers data without an overhead because there is the need for addressing the data, routing the data, dealing with the reliability of the network and so forth.
If we assume a layered packet-switching protocol network, such as the internet, we have many layers, each with its own overhead. Each overhead adds more bytes to the data to be transferred.
Physical Layer Overhead
 Datalink Layer Overhead
 Network Layer Overhead (IP)
 Transport Layer Overhead (TCP)
 Application Layer Overhead
 The file
 The data

Getting a large amount of data from one place to another reliabily on a packet-switching network has quite a large overhead.


Use subset of training data as prediction data At our company, we've started using Amazon Machine Learning to predict the likelihood of a certain segment of our customers cancelling their subscription.

We only have 500 customers in that segment so we uploaded training data of all our customers who

are on a subscription or
were on a subscription but cancelled

Amazon tells us there's an AUC score 0.70 which is just ok from what I read.

I'm new to Machine Learning so my question is the following:

Out of the 500 customers that are in the training set, can I load the ones that haven't cancelled into the prediction set to predict the likelihood of them cancelling their subscription in the future? Or can I only use the model for new customers that are not included in the training data?

The most important thing is to avoid "testing on the training set".  If you trained a model on a set of 500 users and then evaluate how well it performs by testing it on some of those same users, you're committing the "testing on the training set" sin.  The consequences of doing that is that your evaluation results will be misleading: they will over-estimate the effectiveness of your model.

There are various standard methods to avoid this problem.  One method is to use a holdout set: you set aside, say, 67% of your data for training and the other 33% for testing.  You train a model on the first 70% (the training set), and then evaluate how well your model performs on the other 30% (the testing set).  This will then give you a reasonable, unbiased estimate of the performance of your machine learning model.  In practice, a test+train division is often not enough; for various reasons, you'll often want three sets, a training set, a validation set, and a testing set.  You can read more about that in standard resources.

Another reasonable method is to use cross-validation to estimate the effectiveness of your scheme.  Basically, this involves repeatedly dividing up the data, learning a model on one portion of the data and evaluating on another portion, and then averaging the results.  This is a reasonable alternative to dividing the data into train+validate+test sets, when you don't have a lot of labelled data -- as in your case.

These comments are all about how to build the model, select parameters for your model, and evaluate the model's performance (predict how effective it will be in practice).  Once you've done all that and settled on a model, then you can simply apply the model to new customers to predict their likelihood of cancelling their subscription.

Finally, one last comment: your approach assumes uniformity over time: i.e., that the factors that influence behavior in the past will continue to hold in the same way in the future.  This may or may not be realistic.  For instance, maybe today some people are more likely to cancel cable subscriptions because of the availability of Netflix/Hulu/etc. whereas ten years ago that wasn't as much of a factor.  In many areas, things can change over time.  Read about concept drift to learn more about that particular challenge.

If this didn't answer your question, edit the question to clarify in more detail what you are asking about.


Value returned by recursive function (pseudocode)

f(x,y,z)
{
    if (x < y)
    {
        return 1 + f(x + 1, y, z)
    }
    else if (y < z)
    {
        return 2 + f(x, y + 1, z)
    }
    else
    {
        return z
    }
}

The function call f(12,14,20) returns $40$. Why is this the case? As the final statement is return z, should it not simply return $20$, which would be the value of $z$ at which the recursion stops - $(20,20,20)$?

How does one go about analysing such a function?

Here's what goes on; there are three different cases:

If $x<y$, you pass from $(x,y,z)$ to $(x+1, y, z)$ and add 1 to the eventually returned result.
If $x\ge y$ and $y<z$, you pass from $(x,y,z)$ to $(x,y+1, z)$ and add 2 to the result.
If $x\ge y$ and $y\ge z$ you return z (plus all the additions you made in cases (1) and (2).

Suppose, for simplicity's sake, we start with $(2,4,6)$. First, we're in case (1), so we pass from $(2,4,6)$ to $(3,4,6)$ and add 1. We then pass to $(4,4,6)$, adding another 1 and pass to case (2). In general, we'll add $1\cdot(y-x)$ in this case.

Now we alternate between case (2) and case (1). In this example, we'll go from $(4,4,6)$ to $(4, 5,6)$ (case 2) and add 2 and then from $(4,5,6)$ (case 1), add 1, and go to $(5,5,6)$, so we've gone from $(4,4,6)$ to $(5,5,6)$ and added 3. Another case (2), case (1) will get us to $(6,6,6)$ In general, we'll add $3\cdot(z-y)$ in this case.

Finally, we arrive at $(6,6,6)$ and find ourselves in case (3) where we return 6 plus the adds we made earlier, namely 2 to get from $(2,4,6)$ to $(4,4,6)$, 6 more to get from $(4,4,6)$ to $(6,6,6)$ for a grand total of $f(2,4,6)=2+6+6=14$.

In general, when $x\le y\le z$ we'll have
$$
f(x,y,z)=1\cdot(y-x)+3\cdot(z-y)+z=4z-2y-x
$$

It's not hard to establish similar results in the cases where $x,y,z$ aren't sorted in increasing order.

[By the way, $f(12,14,20)=4\cdot20-2\cdot14-12=80-28-12=40$.]


Why aren't recognizable languages and co-recognizable languages not reducible to each other? While learning to prove undecidability of problems, I came across a statement that you can't reduce a recognizable language to a co-recognizable language and vice-versa to prove undecidability. Why is it so?

Eg: Halting problem of TMs can't be reduced to Emptiness problem of TM

$\qquad$ $H_{TM}$ = {$\langle M,x \rangle$|$M$ is a TM and $M$ halts on input $x$}

$\qquad$ $E_{TM}$ = {$\langle M \rangle$|$M$ is a TM and $L(M)= \emptyset$}

Suppose that $L_1$ is recognizable, $L_2$ is co-recognizable, and there is a computable reduction from $L_1$ from $L_2$. The computable reduction shows that $L_1$ is also co-recognizable, and so decidable.

We conclude that if $L_1$ is recognizable but not decidable, then it cannot be reduced to any co-recognizable language.


Is there an algorithm to find all the shortest paths between two nodes? Given a directed graph, Dijkstra or Bellman-Ford can tell you the shortest path between two nodes.

What if there are two (or n) paths that are shortest, is there an algorithm that will tell you all such paths?

Edit:

I have just thought up a possible solution. Could you just do a Bellman-Ford but when relaxing edges, if (distance[u] + w == distance[v]) then add u to the set of predecessors of v? Does this work?

For the $k$ shortest paths, there are algorithms; see for instance here.

Enumerating all shortest paths is, however, an inherently costly thing; there may be superexponentially many such paths.


What defines the interaction between CPU, Memory and I/O parts? From Wikipedia:

  In computer engineering, microarchitecture, also called computer organization and sometimes abbreviated as µarch or uarch, is the way a given instruction set architecture (ISA), is implemented in a particular processor.

  Computer architecture is the combination of microarchitecture and instruction set.

I kept reading some Q&A like this. Definition says that computer microarchitecture is how ISA is implemented in a processor, but tells nothing about how CPU, memory and I/O interact with each other. Does architecture defines this interaction? For example, which term defines this picture?

A microarchitecture is a high-level description (in contrast to a hardware-description or circuit-level) of an implementation of an ISA. This includes how instruction bytes get fetched, how many decorders there are and what instructions each can decode, how many functional units there are and for which instructions, the cache hierarchy, how all of these units are connected to each other, and it may also include the number of cores or hardware threads and how they interact with each other and what resources are shared between them.

Main memory and I/O devices are not part of the microarchitecture, but the microarchitecture description includes how it interfaces with components of the system. The term architecture is used to either refer to only an ISA or to both an ISA and a microarchitecture that implements it, depending on the context. Therefore, it also specifies how to communicate with memory and I/O devices, but only in terms of instructions and addresses. You can use the term computer or computer system to refer to the image you've attached. The term CPU may refer to either a single core, a multi-core processor design, or a physical processor package (which may include the DMA and interrupt controllers shown in the image).


Is there a name for the class of algorithms that are the most efficient for a particular task? This would be analogous to the Kolmogorov complexity of a string, except that in this case, I'm interested in the algorithm that solves a given problem using the least number of steps.

We would therefore have to be able to show that any other algorithm is at best of the same order of complexity as the algorithm in question.

I'm asking because I'm working on a paper that makes use of this concept, and I was surprised when I realized that I'm not aware of any name for this concept, though I'll concede I'm risking embarrassment if there is such a name that I'm simply unaware of.

You can say that an algorithm is asymptotically optimal in such a case.

In general, people might also say that an algorithm is optimal in some other sense, like assuming some particular complexity-theoretic conjecture like (S)ETH.


Operating Systems - SJN/Round Robin - turn around time + waiting time 2.(10 pts) a) You are given 4 processes in a batch system that all arrive at time 0 with the following CPU burst times:
        P1 : 35,  P2: 25,  P3: 13, P4: 22.  Assuming there is no context switch overhead, draw a time line chart
       (Gantt chart) showing when each process executes under each of the following scheduling algorithms:

SJN (Shortest Job Next).

Round Robin with a quantum of 10.

Answer -
https://imgur.com/sLN8Vwr

I don't fully understand how to get the turning or waiting time.

Waiting time I'm assuming is (95+90+88+63)/4

Turn around time is P1 = 95 - 0 = 95 or 95 - 25 or 95 - 10?
same goes for P2, P3, P4

Turn Around time= Completion time - Arrival Time

and

Waiting time= Turn Around time - Burst time


Explanation of the knowledge representation hypothesis (Brian Smith) In 1982 Brian Smith proposed his Knowledge Representation Hypothesis:

  Any mechanically embodied intelligent process will be comprised of
  structural ingredients that

  we as external observers naturally take to represent a propositional account of the knowledge that the overall process
  exhibits, and
  independent of such external semantic attribution, play a formal but causal and essential role in engendering the behavior that
  manifests that knowledge.

Can someone simplify this statement or add some explanations to it?

In particular I don't understand what is meant by "propositional account" and "formal but causal role".

Thanks!

This is a philosophical statement which uses sophisticated language per convention. Here is another version (according to this page):

Any process capable of reasoning intelligently about the world must consist in part of a field of structures, of a roughly linguistic sort, which in some fashion represent whatever knowledge and beliefs the process may be said to possess.

You can visit the page I linked from some critique of both statements. For another critique, here is an example taken from these lecture notes. Consider the following two procedures for translating the colors red and blue into French:
function translate1(color):
  if color is "red" return "rouge"
  if color is "blue" return "bleu"

function translate2(color):
  dictionary = [ "red" -> "rouge", "blue" -> "bleu" ]
  return dictionary[color]

According to the lecture notes, only the second function translate2 conforms to the hypothesis.

Now for some positive example. Consider an automated translation service such as Google translate. As a vast simplification, Google has a dictionary that it uses to translate words from (say) English to French. This dictionary is a "propositional account" of the knowledge of the process. Here by "propositional account", Smith means a set of logical statements, for example:

The translation of red is rouge.
The translation of blue is bleu.

(Technically, he means first-order logic, so you would put these statements in concise logical form, or as Prolog statements.)
The translation program uses its dictionary in its efforts. Thus the dictionary plays a "causal ... role" in the "behavior" of the system. That is, since rouge is the counterpart of red, if you give the program red it outputs rouge. We don't claim any 'real' intelligence for the program, so this role is only "formal", and moreover our understanding of the dictionary as a list of matching words in two different languages is only an "external semantic attribution" that is irrelevant for explaining the behavior of the program. After all, the program doesn't really 'speak' English or French, it only gives the impression of being able to.

Let me try to put the hypothesis in simpler words:

Programs use databases that represent knowledge.

(See Surely you're joking, Mr Feynman!, page 281.)
Now we can come up with many more examples. JPEG compression programs use knowledge about the human visual system in the form of the quantization matrix, which explains which Fourier coefficients are more important for image representation. Recommendation systems use a database of products that can be recommended, and another database that keeps track of what other users liked. OCR systems use implicit representations of symbols (letters, digits, and punctuation) in the form of a machine learning recognizer for them.
Does modern machine learning conform to the hypothesis? Considering the last example, optical character recognition, the "catalog of characters" isn't stored as such, but only implicitly as (say) a set of weights in some neural network. This is certainly not a "field of structures, of a roughly linguistic sort", as per the other version of the hypothesis.
Modern artificial intelligence has largely moved away from the naive and romantic view of classical artificial intelligence, as exemplified by the KR hypothesis. Instead, now we often use statistical methods of machine learning which are much more successful in practice but much less satisfying from a human perspective.
Are knowledge representation techniques used in the real world? This is a question left for the experts to answer.


Terminology: Difference between decision variables, features and attributes? Could there be a difference between the words "feature", "attribute", and "decision variable" when used in the same paper? The one I am specifically thinking about is about an optimization method for clustering, but I am also wondering if there generally are any scenarios for which it could be.

I can't manage to google up an answer that either confirms or denies that these are the same thing, and I have no formal training in data science.

EDIT:

I left the article out at first to not omit a more general answer, but this is the link: ncbi.nlm.nih.gov/pmc/articles/PMC4532808

Some quotes:

"Mutation is a probabilistic operator that randomly modifies a decision variable of a candidate solution."
"Suppose [...] POPi(s) is the sth decision variable of POPi  (i.e.  C r t, t = 1,2,…, d  and  r = 1,2,…, q)."
"[...] max(h i(SIV)),  min(h i(SIV)) are the upper and lower bounds for each decision variable [...]"
"A SIV is a feature of the solution and can be imagined like a gene
in GA."

Feature and attribute have both the same meaning.

Decision variable is the variable which is used to make a split in a decision tree in tree based algorithms, i.e. the variable on which the decision is made.


How to compute number of possible paths in directed Traveling Salesman problem? If we have directed modification of TSP, so that some routes are possible in one direction, given directed graph, could you compute number of possible tours?

What if we have supercomputer, does it make dTSP more feasible?

edit:The number of different Hamiltonian paths in undirected graph is (n−1)!/2 in fully directed version it is (n−1)!, exact number could be computed from adjacency matrix

yes but if i delete city or two from connection like this example will not be fully and this is my case:

1 to 2,3

2 to 3

3 to 1,2,4,5

4 to 2,5,1

5 to 1

so i convert dTSP to simple graph my problem is to know how many paths can i create by my edited dTSP graph so
if i have

1 to 2,3

2 to 1,3

3 to 1,2

i will have number 3!= 6 paths
but if i edit it to be like that

1 to 2,3

2 to 3

3 to 1

i will have 3 paths only

i found that if one city is delete from connections can cut paths maybe by double as i try and error with small numbers of cities so i want to know if i possibly can calculate number of paths that created by this given connections

The way you have written your question makes it very difficult to understand, but let me try to answer one of your points as simply as I can.

Using a "super computer" (however you might define that) will not help us to make significant progress on the travelling salesman problem. The reason is that the time taken to solve a travelling salesman problem increases exponentially with the number of cities.

So suppose we can solve problems with up to 50 cities in a reasonable time on an "ordinary" computer (I have made this number up as an illustration). But let's also suppose that the running time of our most efficient algorithm is $O(2^n)$ - in other words, every time we add a city the time needed to find a solution doubles.

If we had a super computer that was a thousand times faster than an ordinary computer then it could solve problems with $60$ cities in the same time as an ordinary computer took for $50$ cities. This is because adding $10$ cities increases the problem difficulty by a factor of $2^{10} \approx 1000$.

So the super computer gives us a small improvement. But to solve  problems with $100$ cities in a reasonable time we would need a computer that was a million million ($10^{12}$) times faster again.


Prove that we can change probability in definition of PP class According to Wikipedia, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. If the answer is YES, the algorithm will answer YES with probability more than 1/2. If the answer is NO, the algorithm will answer YES with probability less than or equal to 1/2.

So, the problem is to prove that if in definition we change probability from 1/2 to any rational number (0,1) we obtain the same class of problems.

Lets say a separation using $p\in\mathbb{Q}$ exists for $L\subseteq\Sigma^*$ if there exists a polynomial probabilistic Turing machine $M$ such that:

$x\in L \Rightarrow \Pr\left[\text{M accepts x}\right]> p$

$x\notin L \Rightarrow \Pr\left[\text{M accepts x}\right]< p$

$L\in PP$ iff there exists a separation for $L$ using $\frac{1}{2}$ (we can use a strong inequality in both cases). We proceed to show that $\forall p,q\in (0,1)\cap \mathbb{Q}$, if there exists a separation for $L$ using $p$, then there exists a separation using $q$.

We shall use the fact that a probabilistic Turing machine with access to unbiased random coins, is able to simulate an $\alpha$-biased coin for any rational (this can be strengthened) $\alpha\in [0,1]$, in $O(1)$ expected time. See lemma 7.14 in Arora and Barak's book for a proof.

Now, given a machine $M_p$ with separation $p$ for $L$, lets consider a machine $M_q$, which starts by tossing an $\alpha$-biased coin. If the outcome is $1$ then it accepts, otherwise it simulates $M_p$ on the input and returns it's answer.

Since we want $M_q$ to be polynomial in the worst case, we restrict the simulation of the $\alpha$-biased coin to a certain number of iterations, such that the simulation halts with probability $1-\epsilon$ (this can be done for any $\epsilon>0$, simply use the fact that the simulation runs in expected constant time, and apply Markov's inequality). If the simulation didn't halt, $M_q$ accepts. In this case we have:

$\Pr\left[\text{$M_q$ accepts x}\right]=\epsilon+(1-\epsilon)\left(\alpha+(1-\alpha)\Pr\left[\text{$M_p$ accepts x}\right]\right)$, so:

$x\in L \Rightarrow \Pr\left[\text{$M_q$ accepts x}\right]>
\epsilon+(1-\epsilon)\left(\alpha+(1-\alpha)p\right)
$

$x\notin L \Rightarrow \Pr\left[\text{$M_q$ accepts x}\right]<
\epsilon+(1-\epsilon)\left(\alpha+(1-\alpha)p\right)
$

This means it is enough to require $q=\epsilon+(1-\epsilon)\left(\alpha+(1-\alpha)p\right)$. Equivalently,

$\alpha=\frac{q-p-\epsilon(1-p)}{1-\epsilon}$.

Since $p,q\in (0,1)\cap \mathbb{Q}$, if $q>p$ we can find a small rational $\epsilon$ and rational $\alpha\in (0,1)$ to satisfy this. If $p>q$ you can change $M_q$ to reject when the outcome of the $\alpha$-biased coin is 1. When this equality holds, $M_q$ achieves $q$ separation for $L$ and we are done.


Can an (extended) regular grammar have multiple nonterminals in its RHS? Standard (right) regular grammars have three kinds of rules:

A <- ""
A <- "a"
A <- "a" B

This is OK for a theoretical point of view, but a big inconvenience to be usable in practice. A practical regular grammar should allow us to use commodity operators (|,*,+,?,.,(,)), character sets and group multiple rules in a single one. For example, the following regular grammar describes fractional numbers:

start <- digit+ dot digit* | digit* dot digit+
digit <- [0-9]
dot   <- '.'

The question is, what restrictions must be applied to RHS non-terminals to keep this grammars regular (if it is possible at all)?

NOTE

Q - Why regular grammars instead of regular expressions?

A - Regular expressions are OK for simple languages, but they are write-only for more complex ones. On the other hand, well written extended regular grammars are allot more readable and maintainable and allows us to extend them with captures and rule actions easily.

Right regular grammars are very similar to NFAs. In fact, if we modify them slightly by forbidding productions of the form $A \to a$ but allowing ones of the form $A \to \epsilon$, they are completely equivalent to NFAs. As such, it's natural to allow rules of the form $A \to r B$, where $r$ is an arbitrary regular expression.

If we want to stay within the realm of grammars, we can allow instead (or additionally) rules of the form $A \to S'B$, where $S'$ is the starting symbol of a (nonterminal-)disjoint regular grammar (more generally, the regular grammars involved must form a DAG).


Is there a term for the distribution of numbers-of-digits of a bounded uniform distribution Let $X$ be an integer sampled uniformly from the (integer) range $\{ 0...2^k - 1 \}$ .

Now, consider the distribution of

$\#\text{bits}(X) = \begin{cases} 1 & X = 0 \\\\ 1 + \lfloor \log_2(X) \rfloor & \text{otherwise}
\end{cases}$

and

$\#\text{bytes}(X) = \begin{cases} 1 & X = 0 \\\\ 1 + \lfloor \log_{256}(X) \rfloor & \text{otherwise}
\end{cases}$

which are the numbers of bits and of bytes respectively necessary to hold $X$.

My question: Is there some commonly-used term for the one of the distributions of $\#\text{bits}(X)$ or $\#\text{bytes}(X)$ ? Or for a distribution which is very similar to them?

As @YuvalFilmus suggests, these distributions are very close to being geometric. They aren't geometric, since they're bounded, which is what threw me off, but think about it this way:

A geometric distribution corresponds to the number of Bernouli trials up to and including a first success (in some formulations: not including the first success). The distribution parameter p is the probability of succeeding in each individual experiment. Now,

Our first "experiment" involves sampling the most significant bit (or byte): Will it be 0, or something else? A 0 is a success, something else is a failure.
Our second "experiment" is the same, but for the second-most-significant bit (or byte).
and so on.

In a geometric distribution proper, experiments never cease until the first success. In our case, $k$ experiments are conducted, and if you've failed them all then you're simply at 0, with probability $2^{-k}$.


Regular expression for all binary strings avoiding 0110 Consider the language
$$ L = \{ w : w \in {0,1}^* \text{ and } w \text{ doesn't contain } 0110 \text{ as a substring.} \} $$
What is a regular expression for this language?
I thought of $1(1)^*0(0)^*$.
But this seemed to not contain any strings starting with $0$. If I do $1(1)^*0(0)^* | 0(0)^*1(1)^*$ then it can contain $0110$. How can I improve my answer to this question?

A string avoids $0110$ regardless of any initial or final $1$-runs, so we it suffices to consider strings starting and ending with $0$. We can write every such string as follows:
$$
0^{a_1} 1^{b_1} 0^{a_2} 1^{b_2} \cdots 0^{a_\ell},
$$
where $a_1,b_1,a_2,b_2,\ldots,a_\ell \geq 1$. This string avoids $0110$ if $b_i \neq 2$ for all $i$.
The following infinite regular expression corresponds to the above:
$$
\epsilon + 0^+ + 0^+(1+111^+)0^+ + 0^+(1+111^+)0^+(1+111^+)0^+ + \cdots
$$
Here the first summand corresponds to the edge case $\ell = 0$. We can describe all of these cases using a single regular expression as follows:
$$ \epsilon + (0^+(1+111^+))^*0^+ $$
Bringing back the initial and final $1$-runs, this gives the following regular expression for your language:
$$ 1^* + 1^*(0^+(1+111^+))^*0^+1^* $$
Using some case analysis, we can simplify this into
$$ 1^*(0^+(1+111^+))^*0^*1^* $$


Deciding between two algorithms with similar runtime in two parameters Let's say I have a problem which depends on two variables, $m$ and $n$.  I also have two algorithms for solving the problem.  How do I decide which algorithm to use?

For example, say I have an array of unique numbers $A$, not necessarily sorted, and a second sorted array $B$.  I want to create a third array $C$ which contains how many times each number in $A$ appears in $B$.

Algorithm 1 runs in time $O(m \lg n)$ and algorithm 2 in $O(m \lg m + n)$.

It seems to me I would need to divide into three cases:

$n=\Theta(m)$
$n\gg m$
$m \gg n$

How would I generally proceed from here?

A better comparison is $n$ versus $m\log m$. When $n = \Theta(m\log m)$, both algorithms have running times $\Theta(m\log m)$. When $n \gg m\log m$ (or rather $n = \omega(m\log m)$, the second algorithm has running time $\Theta(n)$ and the first one has running time $\Theta(m\log n) = o(n)$ since $m = o(n/\log n)$. When $n \ll m\log m$ (or rather $n = o(m\log m)$) the second algorithm has running time $\Theta(m\log m)$ and the first one has running time $\Theta(m\log n) = o(m\log m)$.


For given set of integers, find and count the pairs with maximum value of bitwise or Let's say we have given set of integers $A = \{x_1, x_2, x_3, x_4, \dots, x_n\}$, consisting of exactly $n$ values, all of them positive integers. Now the problem is to find the maximum value of bitwise or operation of all possible pairs $(x_i, x_j)$

We define bitwise or as bitwise operation that returns true if atleast one of the bits is turned on, in most programming languages it is declared as "|".

Edit: We assume that the numbers in the set can be written with at most 17 bits, or they are smaller than $2^{17}$.

For example, we have: $n=4, A = \{12, 3, 4, 11\}$ the maximum value of bitwise or will be $15$, because $12|3=15, 11|4=15, 12|11=15$ so the result is $15$ and we have exactly $3$ pairs that give this result.

My thinking

Obviously we can take each pair and see what is their bitwise or, but this leads us to solution in $O(N^2)$, and I think that there is much faster solution, I think that we don't need to calculate the bitwise or of all numbers, and we can only calculate it for some numbers.

If the numbers have width $c\log n$ then there is a randomized $O(n^{2-1/O(\log c)})$ algorithm that finds the maximum OR correctly with high probability. The idea is to find the maximum OR bit by bit, MSB to LSB. We can do this using $c\log n$ queries of the following form: "Is there an OR whose $k$ most significant bits are $b_1\ldots b_k$?". Each such query is equivalent (up to bitwise operations) to the query (applied to a different list): "Is there an OR in which all bits are 1?". Abboud, Williams, and Yu gave a randomized $O(n^{2-1/O(\log c)})$ time algorithm for this problem (which they call Boolean orthogonal detection, flipping 0s and 1s).

If the numbers have unbounded width then (depending on the exact model of computation), there is no $O(n^{2-\epsilon})$ time algorithm (assuming SETH). Indeed, deciding whether the maximum OR is all 1s is the same as Boolean orthogonal detection, for which the aforementioned hardness is known (see for example these lecture notes of Russel Impagliazzo).

Finally, if the numbers have bounded width then there is a simple $O(n)$ algorithm. The algorithm computes the set of numbers appearing in the input, and looks up the answer at a (rather large) table.


Master theorem and constants independent of $n$ I applied the Master theorem to a recurrence for a running time I encountered (this is a simplified version):

$$T(n)=4T(n/2)+O(r)$$

$r$ is independent of $n$. Case 1 of the Master theorem applies and tells us that $T(n)=O(n^2)$.

However, this hides a constant dependent on $r$ in the big-oh notation: our recurrence has depth $O(\log_2 n)$ so at the final level we have $O(4^{\log_2 n})=O(n^2)$ subproblems, each of which takes $O(r)$ time to be handled. This means the actual running time is $O(n^2 r)$ (or worse: this analysis only talks about the lowest level).

This is my actual recursion:

$$T(n)=r^2T(n/r)+O(nr^2)$$

Is there a method similar to the Master theorem for these kinds of recursions?

Use a recursion tree (otherwise known as the proof of the Master Theorem).  I'll assume here that $r>1$, since otherwise the recurrence never bottoms out.

The root of the recursion tree for $T(n)$ has value $nr^2$.
The root has $r^2$ children, each with value $(n/r)r^2 = nr$.  Thus, the total value of all children is $nr^3$.
Each child has $r^2$ children of its own, each with value $(n/r^2)r^2 = n$.  Thus, the total value of all grandchildren of the root is $nr^4$.
An easy induction argument implies that for any integer $\ell\ge 0$, the root has $r^{2\ell}$ descendants at level $\ell$, each with value $(n/r^\ell)r^2 = nr^{2-\ell}$.  Thus, the total value of all nodes at level $\ell$ is $r^{2\ell} \cdot nr^{2-\ell} = nr^{2+\ell}$.
The level sums $T(n) = nr^2 + nr^3 + \cdots + nr^{2+\ell} + \cdots$ form an increasing geometric series, so (for big-Oh purposes) only the deepest level matters.
The recursion reaches its base case when $n/r^\ell = 1$, or equivalently, when $\ell = \log_r n$.
The total value of all nodes at that level is $nr^{2+\ell} = nr^{2+\log_r n} = n^2r^2$.
We conclude that $T(n) = O(r^2 n^2)$.

These notes describe the recursion tree method in more detail, with lots of examples.

Equivalently, define $S(n) = T(n)/r^2$, so that $S(n) = r^2 T(n/r) + n$, and then use the Master theorem to solve for $S(n)$.  But that would require remembering the Master theorem, which I don't.


Entropy based progress bar Would it be possible to build a progress bar that estimates progress using entropy?

Consider a web browser that is downloading a large file (for instance), which displays a progress bar indicating the amount of progress in the download.  Let $X$ denote the value of the complete file; it is not known until the download completes.  At time $t$, we have downloaded part of the time, so let $Y_t$ denote the information/data received by time $t$.  Initially, at $t=0$, we do not know $X$ (there is some prior distribution on $X$).  The observed data narrows down the set of possible values of $X$.  The more we observe, the less uncertainty there is about $X$; once we've finished downloading the entire thing, the value of $X$ is known and there is no more uncertainty.

Could we use the entropy $H(X | Y_t)$, or something like that, to estimate progress so far and build the progress bar?  Would this work theoretically?  Would it work in practice?  Would it be useful?

Would something similar work for software installation or other uses of progress bars?

For downloading a file, yes, this would work.

For a file download, there is a much simpler method: let $n$ be the total number of bytes of the file to be downloaded, and $k$ the number of bytes we have downloaded so far; then $k/n$ is a good estimate of our progress (the fraction of the file we've downloaded so far).

This turns out to be equivalent to your entropy-based notion, if we assume that the file contents are iid bits (i.e., uniform distribution over all possible files of that length).

So why count bytes instead of use entropy?  Well, if they're equivalent, they are just two different ways of describing the same thing.  However, it's much simpler to just count bytes.  Also, counting bytes has the advantage of being something that can be implemented.  Calculating the entropy of the file requires some way to measure entropy, which requires a formula -- and in this case, the formula is to count bytes, so we reduce back to the standard metric.

A progress bar for a software update isn't nearly as easy, because it often involves multiple different kinds of operations, which progress at different speeds.  Also, there is often no uncertainty: the installer knows exactly what files it is writing.  The purpose of the installation is to have a side effect.  We want to measure how long it will take until that side effect is completed.  It's not clear that this will fit into the entropy framework, because an entropy framework doesn't take into account how long it will take for those side effects to complete.  For instance, how long will it take to write one 100MB file and 1000 1KB files?  Hard to say, but I can tell you it's not simply proportional to the number of bits in the files, or the number of bits of entropy -- short files may require a seek, so the time to write a file is not proportional to the length of the file.


On lowness of $\oplus P$ $\oplus P$ is low for itself ($\oplus P^{\oplus P}=\oplus P$).

Are there other complexity classes $\mathcal D$ that satisfy $\mathcal D^{\oplus P}=\oplus P$?
Are there complexity classes $\mathcal C$ that satisfy $\mathcal C^{\oplus P}=\mathcal C$?

Weak complexity classes will satisfy $\mathcal{D}^{\oplus P} = \oplus P$. For example, $P^{\oplus P} = \oplus P$.

Strong complexity classes will satisfy $\mathcal{C}^{\oplus P} = \mathcal{C}$. For example, $\mathsf{PSPACE}^{\oplus P} = \mathsf{PSPACE}$.


Find Index In Sorted Array Such That A[i] = C1 * i + C2 I'm already know that there is an algorithm that can solve A[i]=i in O(log(n)) in a sorted array.
But I want to know if there is any kind of algorithm that also can solve A[i] = C1 * i + C2 (witch C1 and C2 are constant values) in O(log(n)) or not

Finding i such that A[i] = i, where A is a sorted array, needs to check every single array element in the worst case. Choose an array where A[i] = i-1 for every i except that A[k] = k for one single k. If you looked at any number of array elements other than A[k], every single one of the remaining elements could be the one you are looking for.
Now replace every array element with A[i] * C1 + C2, and unless C1 = 0, you have exactly the same problem.
Of course you can be optimistic, and often you will find i a lot quicker. Let's say you have array elements a[1] to a[1000], and you find that a[500] = 770. You now know that 1 <= i <= 499 or 770 <= i <= 1000. You just significantly reduced the number of choices. Of course my first example would have a[500] = 499, which tells you nothing apart from i ≠ 500.


Where to start on SJF Cpu schedualing homework problem? So the question is;

For the following three jobs:
P1: 10 (3,2,5); P2: 4 (2,2); P3: 16 (2,3,5,6)
Execute the three jobs using Exp Ave Alpha =0.6, default=2

I know the formula to get the exponential average for a process is

Pn+1 = (alpha) * Tn + (1-alpha * Pn)

I am basically confused at where to start. Obviously, the value .6 gets plugged in for the alpha, but where does the 2 go in the formula? And with each iteration is N increased? Where do the first time quantum for each process (3, 2, 2) go into the equation?

I have searched all over the web for an explanation, but every video I see on SJF has a gant chart and is given arrival time and looks nothing like this problem.

Alright, so after reviewing with the professor, this is how this actually works.

The default of 2 means they all have an equal priority and just get run in order; process P1, P2, and P3.

Now, once we see P1 run for 3 quantums after the first burst, then we calculate its new prediction.

(0.6) * 2 [original default] + (0.4) * 3 [last run] = 1.2 + 1.2 = Prediction of 2.4

Same thing with P2 & P3 (both have a first burst of 2 quantums.)

(0.6) * 2 [original default] + (0.4)* 2 [last run] = 1.2 + 0.8 = Prediction of 2.0

So for the next quantums' order, it would be P2, P3, THEN P1.

Then after that run you would just do;

(0.6) * [2nd to last burst] + (0.4) * [last burst] = new prediction to figure out which proces would run next.

So the actual order would be;

Quantum: Process

Q3: P1:3

Q5: P2:2

Q7: P3:2

Q8: P2:2 (FINISHES)

Q12: P3:3

Q14: P1:2

Q19: P3:5

Q24: P1:5 (FINISHES)

Q30: P3:6 (FINISHES)


Why is it true that the relation R and its negation are not semi decidable? An example given for a relation R where its negation and itself are not semi-decidable was:

$R(x,y)$ holds iff $y = 0$ then $R_{HALT}(x)$ holds, otherwise $y = 1$ and $R_{HALT}(x)$ does not hold.

It's stated with the assumption that the proof is trivial (which for most it probably is), but I am struggling to see why it is the case. Can anyone run me through why it is true?

If the relation $R$ was semi-decidable, then the halting problem would be decidable: if you want to know whether program $x$ terminates, just enumerate the elements of $R$ until you find either $(x,0)$ or $(x,1)$. In the first case, output "$x$ halts"; in the second, "$x$ does not halt." One of these is guaranteed to happen, so you have a decider for the halting problem, contradicting the undecidability of that problem.

The argument for the complement of $R$ is nearly identical: observe that $\overline{R} = \{(x,1-y)\mid (x,y)\in R\}$.


What are the minimum memory requirments a microprocessors must have to perform any calculation? Please excuse my ignorance in low level things. A lot of the written below might be very wrong.

As far as I understand (and I might be very wrong), there are two types of memory locations a microprocessor can have: registers and stacks.

My question is what is the most basic set of memory locatiins a microprocessor must have to perform an arithmetic calculation of unlimited complexity, such as : 12 / (11 / (4 - 7) * 31) + 8.

For example one register is obviously not enough. What about three registers? Or one stack? Or a stack and a register? Given e.g. one stack and a register, can the CPU perform any calculation?

The CPU should be able to perform any calculation like in the example shown above.

unlimited complexity?

That requires unlimited memory, after all - the numbers must be stored somewhere, and the place to store them is always in memory.

So you need 1 memory 'cell' for each number, and another for each operation. You also need a counter to keep track of the next number or operation. Add to that a register to perform the calculation (only 1 is needed as you can use it to store the results in-place. In reality you'll use another register to notify you of errors such as overflow or division by zero).

Or to put it another way: you need sufficient RAM, an accumulator and a program counter. You can get away without the counter if the memory are streamed in sequentially on a specialist computing machine (eg on tape as per Euphoric's comment).


Algorithm to find all connected objects I'm creating a webapplication in which I render multiple objects using Three.js. These objects are saved in a list and can be connected to each other (but don't have to be), and when they are, they are rendered next to each other.
The user can select an object in this list using the UI that I made.
An example of how the objects can be positioned is in the image below.
When I select the most left object I want the whole chain to be rendered, but not the 'singular' objects that are in the same list.

I hope this is clear enough, if not I will gladly elaborate.
Now the problem that I'm having:
The (simplified) list can look like this:
  {
    id: 1,
    connectedObjects: [{ id: 2 }, { id: 5 }],
  },
  {
    id: 2,
    connectedObjects: [{ id: 1 }, { id: 3 }],
  },
  {
    id: 3,
    connectedObjects: [{ id: 2 }, { id: 4 }],
  },
  {
    id: 4,
    connectedObjects: [{ id: 3 }],
  },
  {
    id: 5,
    connectedObjects: [{ id: 1 }],
  },
  {
    id: 6,
    connectedObjects: [],
  },
  {
    id: 7,
    connectedObjects: [],
  },
  {
    id: 8,
    connectedObjects: [],
  },
];

Now I want to write an algorithm that checks which objects are all in the same 'group' as the selected object. So the last three (6, 7, 8) will not be rendered.
This is in JavaScript but if someone points me in the right direction with some pseudocode or a general idea that would be great!

Thanks for your answers!
I looked into both connected components in an undirected graph and the Disjoint set and went for the latter.
After researching this dataset I found a few packages that provided an implementation, but I used this one:

https://github.com/nawatts/disjoint

I'm a junior developer and haven't really come in contact with this kind of problems so your points in the right direction are very much appreciated.


Halting problem under spatial restrictions Let $A(n, B, d)$, $B(n, d)$ be a {Turing machine, random-access machine, C program} with finite tape (which I'm going to denote "Turing machine*" and "random-access machine*" respectively), $n \in \mathbb{N}$. $A$ and $B$ are the same type of machine. For any $N \in \mathbb{N}$, statements where $n \leq N$, don't matter.

$n + |d|$ is the number of spatial units on $B$'s tape if $B$ is a Turing machine* or random-access machine*. If it is a C program, $n$ is the number of Bytes in $B$'s read-write memory (registers are neglected, see last sentence of previous pragraph). The memory $d$ takes up is read-only and not accounted for. All spatial units regarded are capable of holding the same amount of information.

$d$ is the argument data. You may assume $n$ to be included in $d$.

If $A$ is a Turing machine* or random-access machine*, it may access $2 \cdot (n + |d|) + c$ spatial units where $c$ is constant.

If $A$ is a C program, it may access $n + c$ Byte of read-write memory. The memory $d$ takes up is read-only and not accounted for. It may have a function which for any $p, k \in \mathbb{N}, B \in \{\text{C program}\}, d$ returns the $k$th Byte of $B(n, d)$'s memory after $p$ steps.

For any of the situations $B \in \{\text{Turing machine*}, \text{random-access machine*}, \text{C program}\}$: Is there an $A$ which decides whether $B(n, d)$ will halt?

I care about the reasons as to why this is the case. Unfortunately, I forgot a lot of what I learned about computability. I'm sorry if this is super trivial or unknown.

Yes (for Turing machines)

$A(n,B,d)$ can decide whether $B(n,d)$ will halt.

Note the fact that $B$'s writable memory is limited to $n$ units. This means that the number of possible states of $B$ is just $2^n$ (each possible memory configuration that $B$ may assume). Note also that $B$ halts iff it never goes back to a previously visited state, otherwise it would loop. This means that, if $B$ halts, it cannot do more than $2^n-1$ state transitions (as each state is visited only once).

Thus we can exploit the $2 \cdot n + c$ writable memory units of $A$ to build a machine which simulates B and counts the number of states it visits. We can do that by keeping the memory of $B$ in the first $n$ units, and a state counter $\gamma$ in some other $n+1$ units. We increment $\gamma$ at each state transition of $B$.

If $B$ halts, sooner or later the simulation of $B$ will reach a "HALT" instruction, and then we know $B$ halts. If $B$ does not halt, $\gamma$ will increase forever: as soon as $\gamma = 2^n$, we know that $B$ does not halt.


Why is FACTOR in Co-NP? I'm having trouble wrapping my head around the problems PRIME, COMPOSITE, FACTOR and how they're related in terms of complexity. I understand that PRIME has been shown to be in $P$ by the AKS primality test, and I believe this works for COMPOSITE as well.

As for FACTOR,

$$FACTOR = \{(m,r) :\;\; \exists s \text{ such that} 1<s<r \text{ and } s \text{ divides } m\} $$

from what I have read it seems that it is in $NP \cap Co-NP$. I see that it is in $NP$ since a certificate would consist of a prime divisor of $m$ less than $r$. But what kind of certificate can establish that there is no such prime divisor (in polynomial time)?

A certificate for there being no non-trivial divisor of $m$ smaller than $r$ is the factorization of $m$. We can check in polynomial time that all factors are indeed prime (since primality is in P by AKS primality test), that their product is $m$, and that all of them are at least $r$.


Finding reachable vertices I'm trying to solve a graph problem ( it's not for homework, just to practise my skills ).

A dag $G(V,E)$ is given, where $V$ is the set of vertices and $E$ the edges. The graph is represented as an adjacency list, so $A_i$ is a set containing all the connections of $i$.

My task is to find which vertices are reachable from each vertex $v\in V$.

The solution I use has a complexity of  $O(V^3)$, with transitive closure, but i read that in a blog it can be faster, although it didn't reveal how. Could anyone tell me an other way ( with better complexity ) to solve the transitive closure problem in a dag? Thanks in advance.

Here is an $O(VE)$ algorithm, which is substantially better than $O(V^3)$ if the graph is sparse. First do a topological sort, in time $O(V+E)$. Now work your way backwards, storing which vertices are reachable. At a vertex of outdegree $d$, this requires $O(dV)$ work, so in total you get $O(VE)$.


Coming up with loop invariants involving k? void min(arr[], n){
for(i = 0;i < n; ++i)
{
   // Change < to > if you want to find the smallest element
   if(arr[i] > arr[i+1])
       arr[i] = arr[i+1];
}

To avoid wording about a "just check my work" question. I will try to explain what I do not understand about this topic of loop invaraints. I have been having the hardest time coming up with the beginning loop variant with respect to the variables and the what they mean in relation to the arrays. So, my question about this code loop invariant is that this program finds the smallest element in the array. My loop invaraiant is At the start of the iteration when i = k, the item at index k is the smallest item in the range from zero to k. Can you tell me both if I have the correct loop invariant and also am I understanding the concept correctly. I believe that I need to relate such variables such as i, and j in loops with the varaible k in relation to what the program is doing. Thank you.

There is a very simple way to determine whether you have the correct loop invariant:

Can you prove that it holds when entering the loop?
Can you prove that the loop maintains it?
Can you deduce correctness of the algorithm using the invariant?

I trust that you can do all these checks yourself.


Compute how much memory is needed for a two level page table Im studying operating systems and i found an exercise that i cant solve. It asks to compute the memory space needed for a two level page table.
The logical addresses are 32 bit,
Page size is 4KB
and the page entry size is 4 bytes.
from the page size i found out that the offset is 12bits from the 32 of the memory address and that every page has 1024 entries. So the 32 bit memory address is like this: 10 bits | 10 bits | 12 bits for outer table, inner table and offset. How can i calculate the memory size i need? (assume that all inner tables are used)

This is a textbook exercise, maybe answering that exerise is part of your homework, so read your lessons, think about a possible answser, take a sheet of paper and draw rectangles and arrows representing memory, page tables, pointers...

First, an historical note, this arrangement 10 | 10 | 12 is the one used in 32bits x86 CPUs, which were fairly popular!

   4GB memory is divided into 1Million 4kB pages ( binary million = 2^20). Each "Page Table Entry" occupies 4 bytes. Total = 4MB. These entries are arranged in 1024 tables of 1024 entries. The indexes for the 1024 tables, "Page Directory Entries" each take 4 bytes (on x86, this is usually the same size as PTEs), so 4KB. Total size is therefore 4MB+4kB = 4100kB

A few remarks :

This size is only needed for mapping the whole 4GB address space. If there is less memory installed, the page tables can be smaller with "invalid" or "unmapped" entries in the first level page table.
A multitasking OS need to manage different memory maps for the different running applications, so there can be several copies of the page tables.