texts: Of monotone formulas and same ones satisfying certain properties

texts:
There is the following theoretical computer science, namely:

  For a particular monotone formula $M$ of size $n$, there's an equivalent formula of depth $\text{O}(\text{ln}\,n)$.

(I am reading the original paper in my library, if I have time later I will scan it and add scans of it to this post. My apologies for being unable to find a copy online.)

However, I'm finding myself going from step to step in the proof without really understanding what's going on, lacking intuition, as the paper is quite short and condensing quite a bit of reasoning and motivation, at least I feel. I was wondering if somebody could offer me their explanation of the proof of this result, hopefully with lots of their intuition thrown in so I and others reading can have a greater understanding of a proof?


texts:
I have two questions regarding a paragraph about table-driven agent programs from Modern Approach to Artificial Intelligence 3rd Edition.

"Let $\mathbb{P}$ be the set of possible percepts and let T be the lifetime of the agent (the total number of percepts it will receive). The lookup table will contain $\sum\limits_{t=1}^T |\mathbb{P}|^t$ entries. Consider the automated taxi: the visual input from a single camera comes in at a rate of roughly 27 megabytes per second (30 frames per second, 640 x 480 pixels with 24 bits of color information). This gives a lookup table with over $10^{250,000,000,000}$ entries for an hour's driving."

Can someone please show me the step-by-step derivation of the total number of entries based on the given information to arrive at a value over $10^{250,000,000,000}$? I did my math in the following way, but clearly there is something wrong:

$\mathbb{P} = 2^{640x480x24}$, since per frame there are 24x640x480 bits, and each frame is a percept. (I'm not entirely sure that my claim that a frame is a percept is accurate.)

Then, the total number of entries (S) for an hour is as follows:

S = $\sum\limits_{t=1}^{T=3600x30} (2^{640x480x24})^{t}$.

That series can be converted into the following closed form:

S = $\frac{\mathbb{P}^{T+1} - \mathbb{P}}{\mathbb{P} - 1}$.

If I plug in $2^{640x480x24}$ for $\mathbb{P}$, I end up with essentially $10^{240,000,000,000}$ and NOT over $10^{250,000,000,000}$. What am I doing wrong?

"The daunting size of these tables (the number of atoms in the observable universe is less than $10^{80}$) means that (a)...(d) even if the environment is simple enough to yield a feasible table size, the designer still has no guidance about how to fill in the table entries." I'm not exactly sure what guidance the designer needs. I'm assuming that the agent function already exists. In that case, all the designer needs to do in constructing their table entries is look up the corresponding action with each percept sequence.

I thank everyone in advance for taking the time to read this and help me out =)!


texts: Estimating the range of $1$'s in an array of $0$'s and $1$'s

texts:
I have a large array $A$ that contains something like $[0..1..0..]$. It has a continuous range of $0$'s, followed by a range of $1$'s, and then another range of $0$'s.

This array is large and access is expensive, so I want to use a sampling algorithm to estimate the range $(i, j)$, where $A_i$ is the first $1$ and $A_j$ is the last $1$. Let's say I want to approximate this within an error of $\epsilon n$ where $n$ is the size of $A$, so that I get a range $(i', j')$ where $|i' - i| \leq \epsilon n$ and $|j' - j| \leq \epsilon n$.

What is an algorithm I can use to achieve this?


texts: Is Palindrome subset of a regular language regular?

texts:
Suppose we have $L$ being a regular language with alphabet $\Sigma$, if we define $M=\{ x \in \Sigma^{*}  \mid xx^{R} \in L  \}$, then we know that $M$ contains all half copies of palindrome strings of $L$, now here comes the question, is $M$ regular?

Is it easy to see that when $L$ is finite, then $M$ is clearly also finite hence regular. However, what if $L$ is infinite? I think it will be non-regular and try to pumping lemma but does not work...


texts: How to prove the complexity of this modified version of the minimum dominating set problem?

texts:
I have an optimization problem and I want to show its complexity. The optimization problem is the same as the minimum dominating set problem, but with an additional constraint. The constraint is easy. Consider a defined subset $S$ of nodes in a graph. The additional constraint is to guarantee that at least a given number of nodes in this set are selected. Therefore, I want to find the set $D$ with minimum cardinality that ensures all nodes in the graph are dominated and, the given number of nodes in the $S$ is selected. Actually, my solution is the union of the solution to the minimum dominating set and the additional constraint. As the cost function is minimizing the cardinality of the solution, so the result to the minimum dominating set should have the most common nodes with the set $S$.
I know, the minimum dominating set is a well known NP-Complete problem, and to show the complexity of a problem to an NP-hard or NP-complete I should use polynomial reduction. But, I can't find a well known NP-hard or NP-complete problem to reduce it to my problem.
Therefore, I want to help me with that, is there any way to find the complexity of my problem? I'm thinking of a way other than reduction.
Or, is there any problem to reduce it to my problem to show its complexity.


texts: End-to-end bandwidth allocation to n pairs of nodes

texts:
Suppose there is a weighted graph representing a network with available bandwidth. I want to allocate end-to-end bandwidth between a set of pairs of nodes to transfer data. I want to find a path and allocate bandwidth to these pairs over that path and cover the most number of pairs possible. To solve this, I used shortest-widest path as a greedy algorithm but certainly, there are cases where this would cause problem and we can support more pairs to communicate with each other. I searched for a while but I could not find the exact problem, any suggestion on how I can solve it?

To elaborate, there is a network like in the following figure and there is bandwidth for each link (which is the maximum capacity of that link).

Connected to these switches are the hosts, as the input of the problem we have host pairs and required bandwidth, for instance, [h1, h2, 20Mbps]. The offline version of the problem has all the input data at the beginning and we want to maximize the number of input accepted by the network, by accepting input entry we find a path between those hosts and allocate the required bandwidth, in addition, the used bandwidth on each link can not be used by any other input entry. Shortest-widest path seems to be a good greedy algorithm for this problem, but in some cases it is not giving the best answer.


texts: Genetic programming - tournament selection and elite

texts:
I am writing a thesis about automatic GUI testing. In order to find the fittest strategy I am using GP. I am using tournament selection to select chromosomes for the next generation and elitism to make sure the strongest elite(s) will proceed to the next round.

Basically, I have 2 questions:

a) Many papers use 7 as tournament size because this is the default in one of Koza's papers. From my understanding we are missing the point of Koza. I think 7 might have been a good fit for his research, which may be based on his population. Shouldn't we use the probability and adjust the tournament size accordingly instead? As one may already have noticed, I am making assumptions. Are there papers I may have missed that are writing about choosing the right tournament size? If not, should experiments be conducted to find the right tournament size for a specific research setup?

Eg. Following results in a probability of 7% that a chromosome is part of the tournament.

Population: 100
Elites: 5
Tournament selection: 7

Increasing the tournament size (selection pressure) will result in a higher probability a chromosome will be selected for the tournament.

b) If I have a population of 100, a tournament size of 10 and 5 elites, if I understand correctly, 6 chromosomes will make it to the next generation right?

Please people, enlighten me :)


texts: General notion of memory for a computational model

texts:
I have just started studying Michael Sipser's Theory of Computation, studying various computational models such as FAs, PDAs et cetera.

In the book, the term "memory" was often used,as in the case of FAs, it was taken to be the number of states, or for PDAs, the length of the stack, which is infinite,a hint as to why PDAs also accept Context-Free non-regular languages.

I wonder how this Notion of memory is thought of;how can we effectively decide for any computational model,its corresponding "memory"  (if even there is one?)


texts: construct a TM decides in linear time, if valid bracket

texts:
I want to construct a 2-tape Turing Machine, which decides in linear time if the input string over $\Sigma^* := \{(, [, ], )\}$ is a valid bracket.

I have not constructed too many TM's yet, this is why I need your help.


texts: Finding a subarray of time series data in which all values are less than X for specified time Y?

texts:
The idea is to find an anomalous value (i.e. it's less than X) in time series data (sorted by time), and check if this behavior continues during specified time (Y=2 hours).

If all values in sub-array (which represents 2 hours period) are ≤  X, the subarray is returned as a result, and we do not continue further.

Else search continues until such sub-array is found or we have no more data.

Is there an algorithm or family of algorithms that are suited for this task?

Example:

X = 10

Y = 2 hours

Data:

(time=00:00, value=4)

(time=01:00, value=4)

(time=02:00, value=11)

(time=03:00, value=4)

(time=04:00, value=3)

(time=05:00, value=3)

Result:

(time=03:00, value=4)

(time=04:00, value=3)

(time=05:00, value=3)

...during these 2 hours all values were consistently ≤ than X=4.

On the other hand, 00:00 - 02:00 range has X=11 at the end, so it isn't included in result.

Update:

There are approx. 1440 data points in the array (1 point per minute x 24 hours).

This shouldn't be a streaming algorithm, all needed data points are already available.

Data points are immutable, values (or time) don't change.

It's important that we use as little memory during the search as possible.

Search is run once a day, so the data is different and does not depend on previous searches.


texts: What does pump down means in this solution?

texts:
Problem text (from Sipser's "Introduction to the Theory of Computation"):

2.42 Let $E = \{1,\#\}$ and $Y = \{ w \mid w = t_1\#t_2\# ...... \#t_k \, \text{for $k \geq 0$, each $t_i \in 1^*$, and $t_i \neq t_j$ whenever $i \neq j$}\}$.
Prove that $Y$ is not context free.

Solution:

Consider  a string $1^p\#1^{p+1}\# ... \#1^{2p-1}\#1^{2p}\#1^{2p+1}\#
> ... \#1^{3p}$ where $p$ is pumping length. While pumping there can be
three possibilities :

If either v or y has a #. If so, then pump string 3 times. Let's say hash is in v s.t. $v = 1^m\#1^n$, then $v^3$ will be
$1^m\#1^n1^m\#1^n1^m\#1^n = 1^m\#1^{n+m}\#1^{n+m}\#1^n$. Otherwise #
will be in y, which can be shown similarly.

If # lies in $x,
>      a$. $v$ lies in $1^j$ such that $j<2p$. if $|v| = 1$then pump up it twice, else if $|v| > 1$ then pump up it once. We must get $t_i$
which will be equal to some $t_j$.  I have considered to pump twice if
$|v| = 1$ because it may happen that $|y| \neq 0$. Think what am I
talking.
b. $y$ lies in $1^j$ such that $j \geq 2p$. if $|y| = 1$ then pump down it twice, else if $|y| > 1$ then pump down it once.
c. If one of the $v$ and $y$ is empty then pump other up or down once depending on where it lies i.e. $1^j$   $j$ is greater than $2p$
or other way.

If both $v$ and $v$ lies in same $1^j$, and $j \leq 2p$ then pump up it once. Else if $j > 2$p then pump down it once.

My Question
I know that in pumping lemma if language $L$ is a CFL, then $w \in L = uvwxy$ and $uv^nwx^ny \in L$ for all $n\geq 0$.
How can I pump down it twice? I think it means $ n = -1$.


texts: When searching graphs breadth-first and depth-first color the graph. Who un-colors the graph when the search is completed?

texts:
The depth-first and breadth-first algorithms for traversing graphs use a flag (or  color) to mark nodes when they are visited. For example some forms of the algorithms use white/grey/black as colors. When the traversal is complete all the nodes in the graph are black.

None of the material I have been reading on these algorithms mentions anything about reverting all the nodes back to white when the traversal is complete.

Are there some extra steps we can add to the algorithms to take care of this? Or must we traverse the graph all over again to reset each node's color? Or perhaps the Graph's data structure is such that changes to the flag/color is temporary and is lost once the traversal is complete?


texts:
I have an $n \times m$ matrix, and fill it with numbers of $1 \dots k$.

If a matrix can be turned into another matrix by exchanging its lines and exchanging its columns, the two matrices are considered to be the same.

I know that I can easily computed the numbers of the different matrices out in $O((n\times m)^k)$ time, but is there any better algorithms for this problems?

Also, I am wondering whether $\texttt{Burnside's lemma}$ or $\texttt{Polya's Theorem}$ work here. I am having no ideas with them.


texts: Can you always prove the asymptotic bound of a recurrence of the form aT(n/b) + f(n) using the substitution method?

texts:
To make my question more concrete, here is an example I am stuck on.

I want to prove that $T(n) = 8T(\frac{n}{2}) + n^3$ is asymptotic bound by $n^3\log(n)$ using the substution method. That is $T(n)$ is $\Theta(n^3\log(n))$, so both $O(n^3\log(n))$ and $\Omega(n^3 \log(n))$.

We know $T(n) = \Theta(n^3 \log(n)) \Leftrightarrow \exists c_1, c_2, n_0 > 0: \forall n > n_0 . c_1 n^3 \log(n) \leq T(n) \leq c_2 n^3 \log(n)$.

Given that I assume the proof should go somewhat as follows:

To show: $\exists c_1, c_2, n_0 > 0: \forall n > n_0 . c_1 n^3 \log(n) \leq T(n) \leq c_2 n^3 \log(n)$

To do this we can use strong induction.

Let $P(n)$ be $c_1 n^3 \log(n) \leq T(n) \leq c_2 n^3 \log(n)$.

Take $n$ to be an arbitrary natural number.

Induction hypothesis: $P(1),P(2),...,P(n-1)$. And notably, $P(\frac{n}{2})$.

It seems fairly straight forward to show the right-hand side of $P(n)$, that is that $\forall n > n_0 . T(n) \leq c_2 n^3 \log(n)$.

It follows that (taking $\log$ to be in base $2$):

$$
\begin{align*}
  P(\frac{n}{2}) &\Leftrightarrow T(\frac{n}{2}) \leq c_2 (\frac{n}{2})^3\log(\frac{n}{2}) \\
  &\Leftrightarrow 8T(\frac{n}{2}) + n^3 \leq 8c_2 (\frac{n}{2})^3 \log(\frac{n}{2}) + n^3 \\
  & \Leftrightarrow T(n) \leq 8c_2\frac{n^3}{8}(\log(n) - log(2)) + n^3 \\
  & \Leftrightarrow T(n) \leq c_2n^3\log(n) + n^3 - c_2n^3log(2) \\
  & \Leftrightarrow T(n) \leq c_2n^3\log(n) + n^3 - c_2n^3 \leq c_2n^3\log(n) \ \text{ (if $c_2 \geq 1$)}
\end{align*}
$$

So we have $P(n)$.

And as such $\exists c_2, n_0 > 0: \forall n > n_0 . T(n) \leq c_2 n^3 \log(n)$.

My problem:

So we have shown that $T(n) = O(n^3 \log (n))$ but not yet that $T(n) = \Omega(n^3 \log (n))$ which is also required to have $T(n) = \Theta(n^3 \log(n))$.

And that is what I am not sure how to go about showing — the left-hand side of $P(n)$, that is that given $P(\frac{n}{2})$, we have $c_2 n^3 \log(n) \leq T(n)$.

Can someone provide some insight into how to approach this?


texts: Increasing the weights of all edges in an undirected graph makes a minimum cut still minimum

texts:
We have an undirected graph, with a weight function and a minimum cut. If you raise the weights of all the edges by one, the minimum cut remains minimal even with the new weights.

I know this is refutation, but I could not find a good example of refutation.
I would be happy if you would help me.


texts: To what extent is an x86 machine equivalent to a Turing Machine?

texts:
To what extent is the abstract model of computation specified by the x86 language Turing complete?
The above question is related to this question: Is C actually Turing-complete?
In theoretical computer science the random-access stored-program (RASP) machine model is an abstract machine used for the purposes of algorithm development and algorithm complexity theory.

The RASP is a random-access machine (RAM) model that, unlike the RAM, has its program in its "registers" together with its input. The
registers are unbounded (infinite in capacity); whether the number of
registers is finite is model-specific. Thus the RASP is to the RAM as
the Universal Turing machine is to the Turing machine. The RASP is an
example of the von Neumann architecture whereas the RAM is an example
of the Harvard architecture.
https://en.wikipedia.org/wiki/Random-access_stored-program_machine


texts: How many tapes would Turing Machine require to find the sum of 2 integers (expressed in base2)?

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

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

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


texts:
I have a band matrix -- a sparse, square, symmetric $N \times N$ matrix whose structure looks like the following:

Here, the area under the blue stripes is the non-zero elements; everything else is zero

Is there an algorithm to invert this kind of matrix that is simple yet more efficient than Gaussian elimination and LU decomposition?


texts: Origin of a story about a computer in the 50's recommending offing Pensioners

texts:
There's a story I've heard a few times in various computer science talks, usually offered as a cautionary tale, that goes something like this:

In the late 50s, the British gov't purchased an early computer, and tried to build a computer model of the gov'ts budget, including every variable and factor they could think of.  They then had it run an analysis to find the best ways to save money.  The surprising result was they should decrease spending on traffic lights and cross-walks.
This confused the researchers, since these items were a very small fraction of the total budget, much less then what the computer claimed could be saved by eliminating them.  Upon further examination, they found that the source of the savings wouldn't be due to the direct cost of traffic lights, but were due to the increase in pensioners being killed trying to cross the street, thus saving the gov't X millons of dollars.

Even if the story is apocraphyl (which I sort of assume is the case) does anyone know what the original source is?


texts: How to prove Shortest Common Superstring is NP-Hard

texts:
After some research and many youtube videos I have learnt that to prove a problem is NP-Hard; you would need to reduce that problem to known NP-Hard problems such as Subset Sum Problem, Halting Problem, Satisfiability Problem or Traveling Salesman Problem. Now my problem is Shortest Common Superstring

Input: A finite set R = {r1, r2, ..., rm} of binary strings (sequences of 0 and 1); positive
integer k.
Question: Is there a binary string w of length at most k such that every string in R
is a substring of w, i.e. for each r in R, w can be decomposed as w = w0rw1 where w0,
w1 are (possibly empty) binary strings?

In this link it states that the problem is NP-Hard(https://www.geeksforgeeks.org/shortest-superstring-problem/), besides I am using the greedy algorithm stated there to solve the problem.

So I need help with choosing which NP-Hard Algorithm to reduce to and a way to reduce it. I do not expect a full solution(even though it would be welcome), just guidance would be enough. I honestly do not have much clue on how to go about it.


texts: NP-Completeness of modified decision problems

texts:
Suppose we have a NP-Complete decision problem like independent set or finding matching in graph theory and we change the greatness or smallness of the condition of that problem i.e. change the direction of the inequality in the problem's definition ($ \ge$ or $\le $).
For example in independent set problem when the condition is $|V'| \ge k$ and I change it into $|V'|\le k $. Are problems modified in this way still NP-complete?


texts: Does a Context-free language have a grammar that has either 3 or 0 nonterminals on the right hand side?

texts:
Is the following true or false? Why?

Let L be a context-free language with $\epsilon\notin$ L. Then there is $\epsilon$-free grammar $G=(V,\Sigma, P,S )$ with $L (G) = L$, so all production rules are of form $A \to BCD$ or $A\to a$ with $A, B, C, D \in V$ and $a\in$ $\Sigma$.

I don't know normal forms for context-free languages. Just the CNF for regular ones. Trying a few small examples don't gives me a generally valid response, if there are really always production rules of this form.


texts:
Let A = $(Q, \Sigma, \delta, S, F)$ be a deterministic finite automaton associated with the language
$L \subseteq \Sigma^*$

$L' = \{y \in \Sigma^*:\exists x\in L. |x| = |y|\}$
$L \subseteq L'$

How do I show that there exist a NDFA associated with L' ?


texts: Why is A implies B true if A is false and B is false?

texts:
It seems to me that the 'implies' in English language does not mean the same thing as the logical operator 'implies', in a similar way how 'OR' word in most cases means 'Exclusive OR' in our everyday language use.

Let's take two examples:

  If today is Monday then tomorrow is Tuesday.

This is true.

But if we say:

  If the sun is green then the grass is green.

This is also considered true. Why? What is the 'logic' in natural English behind this? It blows my mind.


texts: Confusion about data types, compilers, hardware data representation and static vs dynamic typing

texts:
I am trying to understand static vs dynamic typing, but am really struggling to see how everything fits together.

It all starts with data types. As far as I understand, data types are quite abstract notions, which exist 'in' compilers in order to categorise data so that the operations on various types of data can be validated (i.e. in an attempt to stop you adding a string to an integer), and in order to generate the right machine code for the hardware interpretation of the value. I.e. say we have the following:

int myInt = 5;
char myChar = '5';

Console.WriteLine(myInt);
Console.WriteLine(myChar);

Both would ultimately write a five to the console window, but, since the representations in memory of integers and characters are different, the machine code which interprets the value in the memory location bound to the variable myInt, which takes that value and displays it on the console window, would be different to the machine code for myChar. Even though Console.WriteLine() 'does the same job', the different representations of five require different low level code.

So my question is this: if data types 'exist only in the compiler' - i.e. once the program has been compiled into machine code there is no knowledge of what type of data the value in a particular memory cell is (everything is just 1s and 0s) - then how can any type-checking be done at runtime? Surely there is no concept of data types at run time? So surely dynamic typing can't be anything to do with type-checking occurring at run time?

Where is my understanding going wrong, and could somebody please explain static and dynamic typing with respect to the argument given above? What is the big picture of what is going on?

I am trying to understand this for an essay, so references to books or online sources would be useful :) Thank you.


texts: What happens if there is context switch while executing system call?

texts:
Suppose a process does system call, hence it goes to kernel mode, the registers are saved. Now the system call will be running in process' allocated kernel stack.

Can there be a context switch when a system call is processed?
Is really the system call allocated process' kernel stack?
If context switch is possible, this means kernel has set the timer for this. Right?
Are system calls part of job scheduling(separately) or this are include in job scheduling of process?

I am really messed up with this kernel stack.


texts: Loop-invariant code motion with unsafe operations

texts:
There are well-known algorithms LICM, and they work well.
Unfortunately, there are certain cases when these optimizations can cause runtime failures with code that was initially correct.
Consider the following example:

read a
read_array bs
for (b in bs) {
    if (a != 0) {
        c = 5 / a
        print b * c
    }
}

applying loop-invariant code motion we find that c = 5 / a is loop-invariant and therefore can be moved out of loop.
These may cause runtime error when a == 0, though original code works fine.

What to do then?
I am not certain, but I have several ideas.

We can refuse from optimizing potentially unsafe instructions
We can apply loop unswitching before loop-invariant code motion.
But I would not rely on this optimization, since it must be applied
carefully to avoid code bloating.
When moving unsafe instructions out of loop body we add range checks.
However, it again causes code bloating
(but not as great as in the previous case).
Also this approach harder to implement, since we can't put these checks
into single basic block, unless we have a special division instruction
that does not cause runtime error.
Perform range analysis before applying LICM.
If divisor is never equal to zero, don't perform LICM.

Are there best practices to deal with such unsafe operations?
Notice, that I am looking primarily for algorithms appropriate for SSA form.


texts: Find the nearest sum to a given number of two elements in sorted matrix

texts:
Given a sorted  $n\times n$ matrix $A$ of real values. That is $a_{ki}<a_{kj}$ and $a_{it}<a_{jt}$, when $i<j$. Propose and algorithm, finding two elements of this matrix with the sum nearest to a given value $q$. The restriction of memory is $\mathcal{O}(n)$. It is not allowed to change a given matrix.

The naive approach  is $\mathcal{O}(n^4)$  brute force algorithm.

Also I can propose $\mathcal{O}(n^3)$ algorithm. Which use the following idea. Let we have two sorted arrays $c_1\leq c_2\le \cdots \leq c_{k}$ and $d_1\leq d_2\le \cdots \leq d_s$ and we need to find a sum of the form $c_i$ + $d_j$ nearest to a given $q$. We can do this by $\mathcal{O}(k+s)$ algorithm by imaginary merging two arrays:
$$
c_1\leq c_2\leq \cdots \le c_{k}; \ \ q-d_s\leq q-d_{s-1}\leq \cdots\le q-d_{1}
$$
in one array.
So to solve the problem we can iterate the set of row-pairs  of our matrix and to use the above idea. Of course this algorithm will have a complexity $\mathcal{O}(n^3)$.

  My question. How can we do this more effectively?


texts: Size of parity automata and Buchi automata from linear time mu-calculus?

texts:
Given a linear time mu-calculus formula, there are many works on transforming the formula to Buchi or Parity automaton.  Using the best algorithm, what is the size of the resulting Buchi automaton and parity automaton?

Suppose the size of the formula is n which is the number of subformulae, then, how many states and transition rules in Buchi automata and Parity automaton?


texts: The maximum decimal integer that can be stored in memory of 8-bit word processor computer?

texts:
Actually i am preparing for an exam and in the last year exam this que. was been asked. i.e

The maximum decimal integer number that can be stored in memory of 8-bit word processor computer ?

a) (128)10
b) (127)10
c) (129)10
d) (255)10

Answer of this que. as given in the answer key is b) 127. And I have no idea how they arrived at this result.

Acc. to my understanding, we have 8-bits, which is 28 = 256  so 255 should be the maximum integer which we can store.

EDIT - An another very similar que. asked in same exam was

The maximum permissible integer in a computer with n-bit word processor and one  word per integer is equal to

a) 2 n - 1 - 1
b) 2 n - 1
c) 2 n - 1 + 1
d) 2 n + 1

Its ans. is  a) 2 n - 1 - 1 (acc. to official ans. key).

By putting n = 8 from above que. we got the answer 127. But again i am clueless how did they derived this answer too.


texts:
Given an array $A$ of $N$ integers, each element in the array can be increased by a fixed number $b$ with some probability $p[i]$, $0 \leq i < n$. I have to find the expected number of swaps that will take place to sort the array using bubble sort.

I've tried the following:

The probability for an element $A[i] > A[j]$ for $i < j$ can be calculated easily from the given probabilities.
Using the above, I have calculated the expected number of swaps as:

double ans = 0.0;
for ( int i = 0; i < N-1; i++ ){
    for ( int j = i+1; j < N; j++ ) {
        ans += get_prob(A[i], A[j]); // Computes the probability of A[i]>A[j] for i < j.

Basically I came to this idea because the expected number of swaps can be calculated by the number of inversions of the array. So by making use of given probability I am calculating whether a number $A[i]$ will be swapped with a number $A[j]$.

Note that the initial array elements can be in any order, sorted or unsorted. Then each number can change with some probability. After this I have to calculate the expected number of swaps.

I have posted a similar question before but it did not had all the constraints.

I did not get any good hints on whether I am even on the right track or not, so I listed all the constraints here. Please give me some hints if I am thinking of the problem in an incorrect way.


texts: Sample K representative frames within a video

texts:
I have an image-based processing module that takes photos for some computer vision processing. I have many videos, but I need to sample representative frames as its inputs, preferably those frames with higher attention.

What are some good and effective algorithms or approaches to take K sample frames in a video? Interesting feature is that usually camera doesn't move much in successive frames with higher attention. So basically we have more stable scenes when a person is focusing on something important. Is there any ways to take this into account for our sampling?


texts: Understanding a boolean expression in λ-calculus

texts:
(NOTE: This is not a homework question at at all.  Rather, this was something that I thought that I understood (at least on the surface), but now appear to have no clue about, and am not currently finding any resources helpful.  I know that we typically like to see what people have tried, but I am honestly discombobulated enough at this moment that I am truly unsure about where to even begin.  If this turns out to be a duplicate that I haven't found, I would also be perfectly happy.  I just want to understand.)

Anyway, on to the question itself:

So, if $\lambda xy.x$ represents true, and $\lambda xy.y$ represents false, then I have been told that $(\lambda b.b \ \ \lambda xy.y \ \ \lambda xy.x)$ is a not function, because the expression

$(\lambda b.b \ \ \lambda xy.y \ \ \lambda xy.x) \  \lambda xy.x$ results in $\lambda xy.y$,

and the expression

$(\lambda b.b \ \ \lambda xy.y \ \ \lambda xy.x) \  \lambda xy.x$ results in $\lambda xy.x$.

Where I am stuck is that I don't see how to apply $\beta$-reductions here.  There are three expressions inside the parenthesis.  How is one of them chosen by applying the outer expression?


texts: Create a program in Python that works with mathematical operations

texts:
Write a program that takes N numbers as input and prints all 3^(N-1) equations that can be formed by inserting the operators +, -, or * between these numbers (keeping them in the initial order). Also count how many unique answers there are and print that as well.

So far, I have this code

import math

def expressions():

userinput= input("enter some numbers:")

operations= ['+',' -',' *')

thelist=[1::]

head= L[0]

if len(expression)==0 :
    return[]
    else:

What I'm having trouble with understanding, is do I iterate over the operations so they alternate with the input that are numbers?


texts: Where to find practical exercises for algorithm analysis?

texts:
What is a good book or resource to find practical exercises of analysis of the complexity of concrete algorithm implementations (that is, which asymptotic complexity does a particular code have)?

I'm interested not in solving algorithms but in practising finding out their complexity. I have seen a couple of these kind of exercises in my Discrete Mathematics textbook (Rossen), but I haven't been able to find a good resource to find others.


texts:
I am trying to prove partial corectness of following program:

{s = 0 and j = 0}
while j <= n do begin
  { s + j = (j - 1)j/2 and j <= n + 1}
    s := s + j;
  { s = (j-1)j/2 and j <= n + 1}
  { s = j(j+1)/2 and j + 1 <= n + 1}
    j := j + 1;
  { s = (j-1)j/2 and j <= n + 1 }
end;
{ s = (j-1)j/2 and j <= n + 1 and j > n}
{s = n*(n+1)/2}

And I am trying to find invariant.  It seems to me that good candidate is s = (j-1)j/2 and j <= n + 1.
Am I ok ?


texts: How to generate a context-free grammar that defines a regex expression

texts:
As the title says, I have been asked to generate a grammar that defines the language of regular expressions. The symbols are: + . * | ? char
I tried and came up with this but it doesn't work when trying to create a parse tree so it's wrong but I'm so lost on how to even begin to define the different rules. So any help either on the question specifically, on improving/re-writing what I got, or general step-by-step guidance to figuring out how to write a grammar from just being given symbols is appreciated.


texts: Optimal dividing of K people into N groups

texts:
A teacher at a school has to do this on a regular basis. Let's say 12 students should be divided into either 4 groups of 3, or 3 groups og 4.
Each student can pick up to 3 other students that person would most rather be with.

I tried to set this up as an undirected weighted graph, and implement shortest path algorithms, but the shortest path here doesn't ensure that as many students as possible get their top wish.

What algorithm should I look into here, in order to achieve to most optimal solution to a problem like this?

Here is a visualisation of the problem:


texts: Possible to connect arbitrary number of dots without intersections?

texts:
A (now closed) question on SO made me think about the following problem:

  Given an arbirtary number of points (2D), draw a path that consists of
  straight lines between points, visits each point exactly once and does
  not intersect with itself.

I came to the conclusion that this is easy if I can chose starting and ending point:

sort points by their x coordinate
use point with mininmal x coordinate as starting point
connect remaining points in left-to-right order

If there are multiple points with the same x value, start with the point with minimal y value and go bottom-up. This way, no intersections can occur.

Now my question is: is this still possible if start and end point are fixed?
I assume that there are well known algorithms for this problem, but my search didn't reveal any useful results.

As @hyde points out, there is no solution if more than two points are on a straight line and start/end points are not the outermost points.


texts: FA for |w| divisible by 3 or number of zeros divisible by 2

texts:
Working on a question were I should construct a deterministic finite automaton for the language

$L=\{w\in \{0,1\}^* \mid |w| \mod 2 =0 \lor |w|_0 \mod 3 =0 \}$

The DFA for the two sublanguages is clear, and also howto construct a nondeterministic automaton from these. However my DFA look horrible complicated. Is there a better one than this:


texts: Is SAT known to be non-context-free or even non-regular?

texts:
We have seen various languages proven to be outside of REG and CFL by corresponding pumping lemmas.

Has something similar been done for SAT?


texts: Understanding connection between minimum spanning tree, shortest path, breadth first and depth first traversal

texts:
In CLRS, in the later part of breadth first search topic, for unweighted graphs, it says:

  At the beginning of this section, we claimed that breadth-first search finds the distance to each reachable vertex in a graph $G=(V,E)$ from a given source vertex
  $s \in V$ . Define the shortest-path distance $\delta(s,v)$ from $s$ to $v$ as the minimum number of edges in any path from vertex $s$ to vertex $v$; if there is no path from $s$ to $v$, then $\delta(s,v)=\infty$. We call a path of length $\delta(s,v)$ from $s$ to $v$ a shortest path from $s$ to $v$.

So for many months, I was content with the fact that for unweighted path, BFS gives shortest path. But today I came across problem asking whether breadth first search gives minimum spanning tree for unweighted graph. I was like, BFS gives shortest path not the minimum spanning tree. And to my surprise I was wrong. Somehow, stupidly, I assumed what CLRS stated was the only connection among minimum spanning tree, shortest path, depth first search and breadth first search, because I was subconsciously thinking that its not given in CLRS (in any of four sections), then it should not be the case. I did not give any extra thought for evaluating any possible connection. But now I want to know what all are the connection.

I have done quick google and found many links, some of which are:1, 2, 3.

My conclusion is:

  For unweighted graph,

  Breadth first search gives both minimum spanning tree and shortest path tree.
  Depth first search gives only minimum spanning tree but not the shortest path tree.

Now I have further small doubts:

  I know for weighted graph MST and SPT are not same. But are they same for unweighted graph? Somehow I feel no, as otherwise point 2 will be wrong, and DFS would have given both MST and SPT for unweighted graph. However I am not able to come up with the unweighted graph for which MST and SPT are different.
  MSTs given by BFS and DFS on given unweighted graph may be different, its just that the number of edges contained in them will be the same.

Which of above points are correct and which are wrong?


texts:
Consider a datatype whose objects will be sequences of elements that has the following two methods

prepend($x, T$) which will insert an element to x to the beginning of the sequence T

search($T, i$) which returns the ith element in the given sequence

T is a linked list. prepend takes $1$ step. Search takes $i$ steps

Suppose T has exactly one element and a sequence of n operations are performed. You are given that prepend has probability $p$ and search has probability $1-p$ for each operation. The value of $i$ is chosen uniformly from $[1, \dots, T]$

Q) Derive the expected # of steps that are taken to perform all the operations (n operations).

for prepend it takes 1 step and n times would be $n \cdot p$

for search it takes $(1) + (2)  + \cdots + n(1-p)$ where each number means the size [1,...,T].

I think prepend is right but I'm not completely sure about search. If theres 1 element in the sequence it would be n times if it were 2 it could be either 1 or 2 and that takes i (i is somewhere between [1...T]) times and so on for 3 until we are at n(1-p).

hence

$E(X) = n \cdot p + \left((1) + (2)  + \cdots + n(1-p) \right)$

Does this make sense?


texts: Hiring one person out of n -- rank and probablity

texts:
I am studying algorithms from CLRS book. I try to understand the difference between

probability of hiring the $i$th person out of $n$ and
probability of hiring the $i$th person out of $n$ persons based on ranks.

Using the normal probability, we know the answer for the first one is $\frac{1}{n-i}$ and the answer for the second is given as $\frac{1}{i}$ in the CLRS book. I am unable to understand the concept here. How is it $\frac{1}{i}$? Can it also be $\frac{1}{n-i}$ taking in ranks, too?

We have n candidates lined up for an intertiew.Once a candidate is interviewed he is given a rank.If the rank of the next candidate is greater the current greatest rank he is hired and his rank is now the current greatest rank

HireAssistant(n)
   best=0
   for i=1 to n
       interview candidate i
       if candidate i better than candidate best
          best=i
          hire candidate i


texts: Complexity analysis of while loop with two conditions

texts:
I am curious how to do a line by line analysis of this piece of code using the "Big O" notation.

i = 0;
j = 0;

while ( ( i < n ) && ( j < m ) )
{
      //do something
      i++;
      j++;
}

How I should represent number of iterations for the loop? Is good if I will do some assumptions or I should write min(n, m)?

Small extension after @Patrick87's comment to show why I am not sure that min() is a general solution:

i = 0;
j = 0;

while ( ( i < n ) && ( j < m ) )
{
      //do something
      i++;
      j++;
}
if ( i < n )
{
      while ( ( i < n ) )
      {
         //do something
         i++;
      }
}
else
{
      while ( ( j < m ) )
      {
         //do something
         j++;
      }
}

How right now we can connect a number of iterations of the first loop and second one if we don't know which condition broke the condition of the first loop?


texts: Proof that $L=\{a^ncb^n| n \in \mathbb{N}\}$ is not regular

texts:
Prove that $L=\{a^ncb^n| n \in \mathbb{N}\}$ is not regular.

Here is my try, I would really appreciate if someone could tell me if this is a correct proof.
Proof:
Lets assume L is regular. Then we know that L must meet the requirements of the pumping lemma.
So let p the pumping number.
Let $w=a^pcb^p$. $w$ is obviously of the length p and is in L. Therefore it should be possible to split w into three pieces xyz such that $|y|>0,|xy|\leq p,xy^iz$ is in L $\forall i \in N$.
Because $|xy|\leq p$ $y $ can only contain the symbol $a$(If $y$ would contain a symbol different from a it would imply that $|xy|>p$, which is not possible). Therefore $y$ must be in the form $y=a^{p-k},0\leq k<p$. So the word w equals $w=a^ka^{p-k}cb^p$, if we set i=2 we get $a^ka^{2p-2k}=a^{2p-k},k<p$ and because $ a^{2p-k},k<p\neq b^p$ it follows that the pumped $w$ is not  in $L$. Which is a contradiction. Therefore $L$ is not regular.
$\tag*{$\blacksquare$}$


texts: Can Johnson's algorithm for simple cycles be modified in order to find only cycles up to length L (but all of them)?

texts:
I have a question regarding Johnson’s algorithm for finding all simple cycles in a graph.
I was wondering it is possible to modify the algorithm in order to find only cycles up to a given length.
After having read into the algorithm, my approach would the following:
Assume I want only cycles up to length L.
Then, if the stack has reached height L, if the current node on top of the stack is not a neighbor of the starting node, I treat it as having no neighbors left, i.e. I remove it again from the stack.
I am not deep enough into network theory, however, to be sure that this modification still guarantees me finding all simple cycles (up to length L).


texts:
L is as usual the complexity class DSPACE($\log n$), of languages decidable using a deterministic Turing machine using logarithmic workspace.

  Is L closed under linear-time reductions?

It is possible that for some pair of languages Q and R, every linear-time reduction from Q to R requires more than logarithmic space.
Up to linear space could be used while still remaining within linear time.
So it isn't immediately obvious to me that L must be closed under linear-time reductions.

On the other hand, it is not clear what a counterexample would look like.
One wants a language Q that can be linear-time many-one reduced to a language in L (for instance, to undirected graph st-connectivity), yet so that Q is not in L.


texts: Recursive algorithm for finding a common ancestor between two nodes in a tree, if it exists?

texts:
Here's the start and the vernacular I'm using.

# in class Scene
@staticmethod
def common_ancestor(item1, item2):
    if item1 is item2:
        return item1
    com = Scene.common_ancestor(item1.parentItem(), item2)
    if com is None:
        com = Scene.common_ancestor(item1, item2.parentItem())
    return com

Anyway, confusion sets in quickly with this one.  Any ideas how to proceed logically?

Steven's idea in the comments:

# in class Scene
@staticmethod
def is_ancestor_of(anc, item):
    if anc is None:
        return True
    if item is None:
        return False
    if item is anc:
        return True
    return Scene.is_ancestor_of(anc, item.parentItem())

@staticmethod
def common_ancestor(item1, item2):
    if Scene.is_ancestor_of(item1, item2):
        return item1
    if Scene.is_ancestor_of(item2, item1):
        return item2
    return Scene.common_ancestor(item1.parentItem(), item2.parentItem())


texts: How to solve this partial order reduction in $O(n^2)$?

texts:
There are two orderings of numbers from the same set. Number $a$ is "immediately before" $b$ iff $a$ appears before $b$ in both sequences and there is no other number that appears between them in both sequences.

So in this example:

Seq 1: 1 2 3 4 5 6
Seq 2: 6 2 1 3 5 4

1 is not immediately before 2 because they appear in opposite orders.
1 is not immediately before 4 because 3 appears between them in both sequences.
2 is immediately before 3 and 3 is immediately before 4.

The problem is to find all pairs $a$, $b$ such that $a$ is immediately before $b$ in $O(n^2)$ time. How can this be done?

I understand that the naive solution can work in $O(n^3)$: For each pair in the first sequence ($n^2$ pairs) verify it using the second sequence ($O(n)$ time).


texts: Applying Machine learning in biological data

texts:
I am trying to solve the following question: Given a text file containing a bunch of biological information, find out the one gene which is {up/down}regulated. Now, for this I have many such (60K) files and have annotated some (1000) of them as to which gene is {up/down}regulated.
Conditions

Many sentences in the file have some gene name mention and some of them also have neighboring text that can help one decide if this is indeed the gene being modulated.
Some files also have NO gene modulated. But these still have gene mentions.

Given this, I wanted to ask (having absolutely no background in ML), what sequence learning algorithm/tool do I use that can take in my annotated (training) data (after probably converting the text to vectors somehow!) and can build a good model on which I can then test more files?
Example data

Title:    Assessment of Thermotolerance in preshocked hsp70(-/-) and
(+/+) cells
Organism:  Mus musculus
Experiment type:   Expression profiling by array
Summary:   From preliminary experiments, HSP70  deficient MEF cells display moderate thermotolerance to a severe heatshock of 45.5 degrees after a mild preshock at 43 degrees, even in the absence of hsp70 protein. We would like to determine which genes in these cells are being activated to account for this thermotolerance. AQP has also been reported to be important.
Keywords: thermal stress, heat shock response, knockout, cell culture, hsp70
Overall design:    Two cell lines are analyzed - hsp70 knockout and hsp70 rescue cells. 6 microarrays from the (-/-)knockout cells are analyzed (3 Pretreated vs 3 unheated controls). For the (+/+) rescue cells, 4 microarrays are used (2 pretreated and 2 unheated controls). Cells were plated at 3k/well in a 96 well plate, covered with a gas permeable sealer and heat shocked at  43degrees for 30 minutes at the 20 hr time point. The RNA was harvested at 3hrs after heat treatment

Here my main gene is hsp70 and it is down-regulated (deducible from hsp(-/-) or HSP70 deficient). Many other gene names are also there like AQP.
There could be another file with no gene modified at all. In fact, more files have no actual gene modulation than those who do, and all contain gene name mentions.
Any idea would be great!!


texts: Lower bound on space of DFS keeping the running time linear

texts:
$\mathsf{DFS(G, u) \text{}}$, $G = (V,E)$

Input : A Directed graph $G$ and a source vertex $u$.

Find  : Is $v$ reachable from  vertex $u$ for all $v \in V$ ?

Model of computation : Word RAM , one can represent a vector $A[1,\cdots ,n]$ of elements from a finite alphabet $\Sigma$ using $n \lg |\Sigma| + O(\lg^2 n)$ bits, such that any element of vector can be read or written in constant time.

$\mathsf{DFS \text{}}$ (Depth first search) takes $O(m + n)$ time and $O(n\log n)$ bits of space . Other known results for DFS is $O((m + n ) \log n)$ time and space  $O(n)$ bits ( see this paper) (please note that DFS in this paper have defined as two phase process 1) Forward phase 2) Backtack phase )

It is a open question that $\mathsf{DFS \text{}}$ can be done in $O(m + n)$ time and $O(n)$ bits of space. (see this paper)

How to prove the lower bound that for $\mathsf{DFS \text{}}$ if we want to keep the runtime $O(m + n)$, we cannot do better than $O(n)$ in terms of space ?

Thanks in advance.


texts: Regex for strings with even number of 1's and number of 0's divisible by 5

texts:
I was trying to build up this regex but I am having huge expressions but nothing generates the given regex. I tried to break up the regex as

$0$ multiple of five times and odd $1$'s
$0$ multiple of five times and even $1$'s

Bu this doesn't help me.
The regex  I Found was  $(00)^*1(00)^*1(00)^*1(00)^*1(00)^*$. But in this way two $1$'s and five $0$'s cannot be generated.
Again $(11)^*0(11)^*0(11)^*0(11)^*0(11)^*$ does not generate $5n$ times $0$'s for $n\ge 2$.
There are other possibilities and that too do not meet the regex.
Any help would be appreciated.
P.s: I am at the very beginning in regex. So I am currently trying to avoid the method of conversion from finite automata to regular expressions.


texts: Convert a non-deterministic Turing machine into a deterministic Turing machine

texts: How can we systematically convert a non-deterministic Turing machine into a deterministic Turing machine that recognizes the same language?


texts:
Given this definitions about Types and Type systems :
Types are described by means of a language of type expressions:

Basic or primitive types: Bool, Char, Int, ...

Type variables: a, b, c, ...

Type constructors: → (function), × (tuple), [ ] (list), ...

Rules to build type expressions:
τ ::= Bool | Char | Int | ··· | t | τ → τ | τ × τ | [ τ ] | ···

Types whose type expression contains no type variable are called monomorphic types or just monotypes.

Types whose type expression contains variables are called polytypes or polymorphic types (parametric polymorphism)

A polymorphic type represents an infinite number of monotypes

I'm trying to understand the last definition but i can't.
A polymorphic type represents a infinite number of monoytpes, because in his type expression has a type variable ?


texts: Can weighted problem have polynomial complexity if non-weighted problem is NP-complete: hitting set

texts:
I am confronted with task to find polynomial time complexity solution for weighted hitting set problem. I have found that usual hitting set problem is NP-complete and therefore the task seems to be contradictory.

But there are several other reformulations of this problem. E.g. d-Hitting set problem can be solved in polynomial time (when each class or set contains no more than d elements).

Maybe the weighted case has completely different algorithms and complexity estimation? Apparently the non-weighted problem is the special case of weighted one and therefore there should not be different complexity estimation, isn't so?


texts: How to solve the bin packing problem with conflicts?

texts:
I'm trying to devise an algorithm to solve the bin packing problem with conflicts (sometimes referred to as BPPC, or BPC).

The problem is defined as follows: consider a set $V$ of $n$ items, where each item $i$ has an associated positive weight $w_i$, and $n$ identical bins of capacity $C$. In addition, there is an undirected graph $G=(V,E)$ representing the conflicts between items. The problem is to assign all items to the minimum number of bins without exceeding $C$ and in such a way that no bin contains conflicting items.

Now I understand that this problem is a combination of the graph coloring problem, and the normal bin packing problem, but I can't quite figure out how to merge algorithms designed for one or the other into a single algorithm suitable for solving this problem.


texts: Other than correlation of events, what is the halting problem about?

texts:
Object B can be in two state 1(stopped), and 2(running) at an arbitrary time t in the future. Object A can be in two states x, and y at t0. However, if A is in state x, B must be in state 2 at t, and if A is in state y, B must be in state 1 at time t.
Thus, you can't have Object A in state x at t0 and B in state 1 at time t. (In other words, the predictor A can't correctly predict that the thing B will have stopped because predicting so will cause the thing B to be running.) This is merely about some correlation and mutual exclusion of events, I don't see this problem as any significant?


texts: Maximize Possible Subset Sums of A Multiset

texts:
The following problem is a problem I faced in one of my coding competitions.

Given two positive integers $N$, $M$. You can have $M$ distinct types of stones, for which different types of stones must have different weights. Find the maximum of $k$ such that any weight in $\{1, 2, ..., k\}$ can be formed as a total weight with at most N stones, given that you can choose the weights of those $M$ types of stones. (Assume that any type of stones have infinitely many, but each time you could only choose N stones among all stones in all types.)

For example, when $(N, M)=(2, 2)$, if we choose the stones to have weights $\{1, 2\}$, we can form 3 with 1 and 2 and we can form 4 with 2 and 2, so we'll have 4.
When $(N, M)=(3, 2)$, $k_{max}=7$. Since we can choose the weights $\{1, 3\}$, and form 4 with 1 and 3, 5 with 1 and 1 and 3, 6 with 3 and 3, and 7 with 3 and 3 and 1. It's also given that when $(N, M)=(5, 4)$, $k_{max}=71$.
This problem seems familiar to me at first, but even till now I haven't solved it. The problem states that $1\leq N\leq8$ and $1\leq M\leq6$. Does that mean there might not be a good polynomial solution? Is this problem related to efficient backtracking?
I appreciate any kind of help! Thanks a lot!


texts: Finding all possible paths in a directed, (possibly) cyclic graph

texts:
I need to find all possible paths in a directed graph, that may have loops. The graph has a defined start and one or multiple defined endings. Basically im trying to find all possible scenarios in a Use Case Description. Since loops may occur, the user may define how many times a loop/alternative flow may be repeated.

For this example and a cycle depth of 1 the possible scenarios should be:

S1: $1 \to 2 \to 3 \to 5$

S2: $1 \to 2 \to 4$

S3: $1 \to 2 \to 3 \to 2 \to 3 \to 5$

S4: $1 \to 2 \to 3 \to 2 \to 4$

So far i tried saving which edges I've visited but then i might get stuck in the middle of the graph when a loop occurs. Anyone got an idea how to solve my problem?


texts: Why is the complexity of the following code $O(n^4)$?

texts:
for i = 1 to n
    s = 0

    for j = 1 to i - 1
        s = s + j * (i - j + 1)

    r = s * s

I calculated the time complexity of this code to be of order $O(n^2)$, but my professor says it is actually $O(n^4)$ because of the statement $r = s * s$, as $s$ is dependent upon $j$ and $i$ which in turn are dependent on $n$. But don't we consider arithmetic operations to be $O(1)$?

Complexity calculation is a new concept to me, and it confuses me a lot. I would appreciate if someone posts a detailed answer which clears my confusion.


texts: How to cluster N sets into N subsets ,so that we can determine which set a point is from by checking its nearest neighbor in aforementioned subsets?

texts:
Question 1:

Given N sets of points $S_1$ ... $S_n$ (no intersection between $S_i$ and $S_j$ when i != j),

I want to find subsets of $S_1$ ... $S_n$ (call them $T_1$ ... $T_n$ respectively)

So that for any point in $S_k$ ,the nearest neighbor to it in $\bigcup_{i=1}^{n} T_{i}$ is in $T_k$,

Obviously $T_k$ = $S_k$ (k= 1 ,...,n) could suffice .

Now how to find the subsets $T_1$ ... $T_n$  so that | $\bigcup_{i=1}^{n} T_{i}$ | is minimum ?

Question 2:

Given N sets of points $S_1$ ... $S_n$ (no intersection between $S_i$ and $S_j$ when i != j),

I want to find point sets $T_1$ ... $T_n$ (no intersection between $T_i$ and $T_j$ when i != j, $T_k$ may or may not be subset of $S_k$ )

So that for any point in $S_k$ ,the nearest neighbor to it in $\bigcup_{i=1}^{n} T_{i}$ is in $T_k$,

Obviously $T_k$ = $S_k$ (k= 1 ,...,n) could suffice .

Now how to find the subsets $T_1$ ... $T_n$  so that | $\bigcup_{i=1}^{n} T_{i}$ | is minimum ?

(Distance can be any kind of Minkowski distance ,like Manhattan distance , Euclidean distance, or Chebyshev distance)


texts: Does Assembly Language depend on an Assembler or the family of processor?

texts:
From what I understand, the x86 family of processors understands the same instruction set and x86-32, x86-16 machine code can be executed by an x-86-64 processor because of backwards compatibility.

Now since Machine Code is usually produced from Assembly Language and we use an assembler for that purpose, does that mean that the family of processors doesn't define an Assembly Language but it is rather the Assembler that we use since it actually parses the code?

Let's say I have an Assembly Code like this which is assembled by MASM for an 80386 processor:

MOV AX, 5
ADD AX, 10

Now assume that this another Assembly Code which is assembled by another hypothetical assembler (lets say HASM) for the same 80386 processor:

MOV 5
ADD 10

Q1: So for the same processor we can have two different Assembly Code which when assembled using the right assembler can produce the same Machince Code?

Q2: So let's say I have a PC running another family of processor (ARM) and write an Assembly Code and assemble it by MASM which produces machine code compatible for the 80386 processor. Now, without executing, it I copy the machine code over to another PC with the 80386 processor, would the code run Okay?

Q3: If I have two PCs with 80386 processors, one running Windows & the other linux. If I use MASM to assemble a source code on Windows for the 80386 processor, why then, when I copy the machine code over to Linux, it won't execute? Both PCs are running the same processor and machine code is the same! How does OS come into play here? (Please assume no OS specific API function has been used)


texts: 1-to-1 cryptographically secure bit shuffling

texts:
Given an input item (N bytes), I'm looking for a function that will map this to an output (still N bytes).  The function should have the following qualities:

It should be 1-to-1 so that all inputs map to some output and so that no two inputs map to the same output.
Given an output element it should be difficult to guess the input that lead to that output, even when the mapping is completely known.

Does such a function exist? Where can I learn more?


texts: I'm aware of some techniques to compress a string of characters such as Huffman coding. I need to know whether there is any technique to compress a long string of arbitrary bits? (ideally with high compression ratio).


texts:
I was calculating the time complexity of one of the phases of my proposed algorithm, but unfortunately, I faced a problem about solving that and providing an understandable running-time. This phase of the algorithm indeed iterates a task $t$ times where $t$ is that iteration in which the algorithm achieves the desire result (optimal value). Each iteration $i$, where $0\leq i\leq t$, runs in $O\big((Y-iy)(\log(Y-iy)+D-id)\big)$ such that $y$ is the expected amount by which $Y$ decreases and $d$ is also the expected amount by which $D$ decrease at each iteration $i$. Therefore the total time complexity of this phase is as follows:

$$\sum_{i=0}^t O\big((Y-iy)(\log(Y-iy)+D-id)\big)\,.$$

Now I would like to find a nice solution for that. Can you help me approximate this in order to obtain a better solution?
Any help will be appreciated. Thank you in advance.


texts: How to solve a recurrence when the master theorem fails?

texts:
How do solve the following recurrence?

  $$ T(n) = \frac{1}{2} T\left(\frac{n}{2}\right) + \frac{1}{n}. $$

Master's theorem cannot be applied as $a$ is equal to 0.5 which is less than 1. Hence the theorem fails. How do I solve a recurrence when the theorem fails?


texts: What does a recursive min s,t-cut optimize?

texts:
Consider the following algorithm sketch:
Given an edge-weighted directed acyclic graph $G = (V, E, w : E \to \mathbb{N})$, adjoin a temporary source $s$ and sink $t$ to get $G' = (V', E', w')$. $G'$ should have edges pointing from $s$ to all nodes in $G$ that have an empty set of in-neighbors, and edges pointing from all nodes in $G$ that have an empty set of out-neighbors to $t$. Edges should not be added between completely disconnected nodes (ones with no out- or in-neighbors) and $s$ or $t$. These edges should have weight $1 + \sum_{e \in E} w(e)$ (or any number much greater than the existing weights, the specific number doesn't matter much). Then, run any minimum s,t-cut algorithm on $G'$ to produce two sets $X, Y \subseteq V$ where $s \in X$ and $t \in Y$. Return $(X', Y') = (X - \{s\}, Y - \{t\})$.
Now given any edge-weighted DAG and a stopping condition, we can run this algorithm recursively, e.g.: by calling this on the subgraph induced by $X'$ and the subgraph induced by $Y'$. The stopping condition decides whether a set is worth continuing to split. The result of this recursive algorithm is a set of sets of nodes.
There's some ambiguity in this description since it's unspecified which side of the partition the minimum s,t-cut should put the completely disconnected nodes in. Feel free to make whatever assumptions you want about this behavior.
Suppose that our stopping condition is "each subgraph should contain no edges". This results in a set of anticliques in $G$. Is this set the answer to some optimization problem? Is this algorithm a greedy approximation of any optimization problem?


texts: Avoiding overflows while computing $e^x$ by Taylor series

texts:
I'm coding a program to calculate the value of $e^x$ by using the Taylor expansion, that is:

$$ e^x =\sum_{k=0}^\infty \frac{x^k}{k!} $$

from math import factorial
def e_x(x, n):
    return sum(pow(x, k)/factorial(k) for k in range(n))

Edit: Python seems to handle large integers pretty well so I'm more interested in the algorithm itself.

I want to avoid overflows during the calculation of the $k!$, so my intuition is that by looking at the $k$th-term and trying to do intermediary divisions an overflow might be avoided.

My naive solution was to just do $\frac{x}{k} \cdot \frac{x}{k-1} \cdot \ldots \cdot \frac{x}{1} \cdot \frac{x}{1}$, but the error became unbearable after some few iterations. I'm not using any high (arbitrary) accuracy floating point library (although I'm interested in knowing how would this be implemented in those).


texts: how do you define functions with denotational semantics?

texts:
Denotational semantics are abstract functions that give meaning to statements of a programming language. They accept an expression and return a value.

But how do you define denotational semantics for languages that define, for example, functions (and later use these functions), or global variables, and change some global state of the program?

I think the simplest way to do it would be to define the semantics function so that it returns a pair of values and a "global state" instead of just a value.

But is there a place I can read about it some more? I am sure someone have done something like that. For example, is there denotational semantics for languages like Java or C?

It would be nice to find a book that focuses on denotational semantics for programming languages which are not necessarily purely functional (though I think functional languages, like LISP, can also change a global state).


texts: Algorithm to separate single contour of glyph into several strokes?

texts:
A glyph contour contains points set {p}, a point contains tuple (x,y,on_curve).
Now, think about this need, converting contour of glyph X, for example, into to two contour parts or two strokes, point set of each stroke is similar with contour of glyph \ and /, topologically? Forgive my mouthful description.
Other examples (symbols at right of -> are shapes how these parts look like):

A -> / \ -
B -> | 3 or | ) )
C -> C
D -> | )
E -> |---
F -> |--
G -> C-|

PS: I don't know whether there any algorithm exists for this need.
I use python and hope to make it with Python programming.


texts: Algorithm to minimize distance variance between 2D coordinates

texts:
I've been looking around for an algorithm that would optimize the distance between 2 list of coordinates and choose which coordinate should go together.

Say I have List 1:

205|200
220|210
200|220
200|180

List 2:

210|200
207|190
230|200
234|190

Calculated Distance between Coords:

205|200 to 210|200 == 5.00
205|200 to 207|190 == 10.20
205|200 to 230|200 == 25.00
205|200 to 234|190 == 30.68

220|210 to 210|200 == 14.14
220|210 to 207|190 == 23.85
220|210 to 230|200 == 14.14
220|210 to 234|190 == 24.41

200|220 to 210|200 == 22.36
200|220 to 207|190 == 30.81
200|220 to 230|200 == 36.06
200|220 to 234|190 == 45.34

200|180 to 210|200 == 22.36
200|180 to 207|190 == 12.21
200|180 to 230|200 == 36.06
200|180 to 234|190 == 35.44

This Algorithm would pick:

205|200 to 230|200 == 25.00
220|210 to 207|190 == 23.85
200|220 to 210|200 == 22.36
200|180 to 234|190 == 35.44

The Algorithm would pick these numbers as they would be the group that would have the littlest variance between the distance.
Conditions:

A Coordinate may only be used ones from each list
If List 1 or List2 is larger than it still only uses each coordinate once, but it tries to get the smallest distance variance and does nothing with the unused coordinates.

If you need more clarification please ask.

P.S. I've looked at the Hungarian algorithm and it seems like it will sort of do the job, but not exactly how I was expecting. The Hungarian algorithm will only try and make the least distance from all the coordinates, which can mean the smallest variance, but not every time as variance is more important here then least distance optimization.

Additional Information

I will have an array of List1, List2, and then the distances:

Distance[List1_item_0][List2_item_0] = 5;
Distance[List1_item_0][List2_item_1] = 10.20;
Distance[List1_item_0][List2_item_2] = 25.00;
Distance[List1_item_0][List2_item_3] = 30.68;

Distance[List1_item_1][List2_item_0] = 14.14;
Distance[List1_item_1][List2_item_1] = 23.85;
Distance[List1_item_1][List2_item_2] = 14.14;
Distance[List1_item_1][List2_item_3] = 24.41;

Distance[List1_item_2][List2_item_0] = 22.36;
Distance[List1_item_2][List2_item_1] = 30.81;
Distance[List1_item_2][List2_item_2] = 36.06;
Distance[List1_item_2][List2_item_3] = 45.34;

Distance[List1_item_3][List2_item_0] = 22.36;
Distance[List1_item_3][List2_item_1] = 12.21;
Distance[List1_item_3][List2_item_2] = 36.06;
Distance[List1_item_3][List2_item_3] = 35.44;

From the Distance['List1_item_#] I would need to pick a distance. Once that distance is picked the [List2_item_#] CANNOT be picked by a different [List1_item_#]. The distances picked for each [List1_item_#] element would need to be picked in a way that the variance between them all is minimal. So distance for each [List1_item_#] should be as close as possible to each other without reusing a [List2_item_#] more than once.


texts: Maximum possible file size in the filesystem

texts:
A file system with 300GByte disk uses a file descriptor with 8 direct block address ,1 indirect block address and 1 doubly indirect block address. The size of each disk block is 128 Bytes and the size of each disk block address is 8 Bytes.What is the maximum possible file size in this filesystem?
This is previous year question I could not get the idea and couldn't solve it...plz help


texts: Why is there more frequent overflow in normalised Floating Point

texts:
I read that overflow is more frequent when we work with normalised mantissas. Why is this?  Is it because when we adopt a normalised representation, our range is smaller than in a unnormalised representation?

Source: I read this in: Hwang, K. Computer arithmetic. John Wiley & sons, 1979. Chapter 10 "Advanced topics on floating-point arithmetic (page 323)"
It says this:

  The operands are not required to be normalized, overflow may be expected to occur less frequently in unnormalized arithmetic.


texts: Minimum sum of two numbers formed from digits of two arrays

texts:
Given two arrays of digits, both of size $n$, $2 \le n \le 9$, form two separate numbers $n_1$ and $n_2$, so the difference $n_1 - n_2$ is positive and minimal, if multiple solutions are possible the one with the smallest $n_1$ is chosen.

Restrictions:

Time: 0.1 s (brute force ain't gonna do it)

Memory: 2 MB


texts: Why is the module of the second function in double hashing a prime number?

texts:
When using double hashing, the second hash function is defined as $$h_2(x)=A-x\mod A,$$ where $A$ is a prime number less than the capacity of the hash table. But why must $A$ be a prime number?

(This differs from Why is it best to use a prime number as a mod in a hashing function? because the prime number in question is the constant of the second hash function in a double hashing table, whereas the prime number in the other question is the mod of the hash table. In addition, it seems not that significant to avoid collisions because the second hash function in double hashing is used to determine the "jump size".)


texts: Why are mapping reductions from incomputable Languages OK?

texts:
For example, many reductions from $A_{TM}$ will often have the lines:

Simulate M on w:
    if M accepts
       ...
    else

But: a reduction is a computable function, right? So why are we allowed to say "if M accepts"?
Also, I can take the same logic and reduce $A_{TM}$ to a deciable language:
Let L be the empty language. Clearly L is decidable.

Given $(M,w)$:

 Output output:
      If M accepts w
            output = '0'
      else
            output = $\emptyset$

Obviously I'm wrong here. But why?
Thanks in advance.


texts: Algorithm: Finding shortest path through a dungeon in a game

texts:
Background

I was playing the PC-Game "Darkest Dungeon" recently. In the game, you have to explore dungeons, which consist of connected rooms as shown in the picture below.

Here are the rules:

You start in fixed room (Entrance). You cannot choose where to start.
The goal is to visit every room at least once
The distance between adjacent rooms is the same for all rooms.
You can visit rooms and walk paths as often as you'd like

Question

What is the shortest path from the entrance that visits every room at least once?

Subquestions:

What algorithm(s) could be used to solve this problem?
Are there implementations that are free (and fairly simple) to use for someone like me?

What I tried

I have found other questions such as this or this without finding an answer. I am familiar with the (basic) TSP and are able to code and solve simple TSPs. Hamiltonian paths didn't solve my problem, because it doesn't allow for multiple visits. The Chinese postman problem does also not apply here in its basic form because I don't have to visit every edge.

Update

As I have stated in the comments, I'm not a computer scientist and am not interested in proving a mathematical statements (maybe I'll post this question on stackoverflow at a later stage). Also, I'm not a programmer and the chances that I'm able to code a solution myself are pretty slim. But I suspect I'm not the first one dealing with a problem of that nature.

According to @Shreesh and @Dib, the following procedure could be applied:

Create a pairwise distance matrix with all rooms thus adding edges between all rooms.
Solve TSP using a standard solver (e.g. concorde)
Starting from the Entrance, visit all rooms according to the solution. For non-adjacent rooms, substitute the shortest distance between those rooms.

Will this procedure provide the answer to the problem?


texts: How to show that a function is not computable?

texts: I know that there exist a Turing Machine, if a function is computable. Then how to show that the function is not computable or there aren't any Turing Machine for that. Is there anything like a Pumping lemma?


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

  What is 47 to the nearest 10?

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

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


texts: $\ell_1$ Minimization of Probability Distribution and KL-Divergence

texts: Suppose through $\ell_1$ minimization I obtained two sparse probability distributions $P, Q$ which may contain many zero terms. Then I would like to compute the KL-Divergence of them $D(P || Q) = \sum_i {p_i\log(\frac{p_i}{q_i})}$.  However, since the probability distribution is sparse, it might occur that $p_i \not= 0$ and $q_i = 0$. In that case, KL-Divergence is not well defined.  One solution is to incorporate Dirichlet Prior. However, I am afraid by doing so the sparsity of the probability distributions is violated.  Is there any other way to compute the KL-Divergence of the two probability distributions?


texts: Checking correctness of grammar for $L = \{w \in \{a, b\}^* \text{ }| \text{ } w \text{ has } n_a(w) = 2n_b(w)\} $

texts:
I have written a CFG that supposedly generates $L$ below.
$$L = \{w \in \{a, b\}^* \text{ }| \text{ } w \text{ has } n_a(w) = 2n_b(w)\}$$
Where $n_a(w)$ is the number of $a$'s in $w$ and similarly for $n_b(w)$.
My reasoning is that for every $b$ in $w \in L$, we will be able to pair it up with two distinct $a's$ in $w$. There are $3$ distinct orders in which this triple can occur in $w$, namely: $(a, a, b)$, $(a, b, a)$ and $(b, a, a)$. Thus my grammar is as follows.
$$S \rightarrow SaSaSbS \text{ }|\text{ } SaSbSaS \text{ }|\text{ } SbSaSaS \text{ }| \text{ } \epsilon$$
By placing the variable $S$ in between, I am attempting not to make any assumptions about the position of the triple in $w$, only the relative position amongst the triple's elements.
From other questions discussing this $L$, I can see that my grammar is much uglier, but as far as I can tell it seems correct. Are there any strings in $L$ that it cannot generate?


texts:
Given two vectors $a$ and $b$ I need to find $k$ such that $\sum_i|a_i - kb_i|$ is minimal.  In other words, my goal is to find $k$ that minimizes the $l_1$ norm distance between $a$ and $kb$.

How should I approach such problem? The $l_1$ norm has weird derivative. Is there some analytical solution, or should I use something like ternary search?


texts: Obtain all possible Turing Machines from a Universal Turing Machine

texts:
Knowing how a Universal Turing Machines works and its capabilities, is it possible to obtain the collection M = {M0 , M1 , M2 , M3, … } of all possible Turing Machines?

If so, can we prove that a language L = {wj |wj not accepted by Mj } is not accepted by the Universal Turing Machine?


texts: Is there any efficient way of calculating the n-th fibonacci number modulo another number?

texts: With efficient I mean of a big O of polynomial time in the number of digits each number has.


texts:
I have come across the following problem but am unable to understand the solution for it. Hence I would like to know if it has a formal name then, I can search for it and read about it in more detail. Also it will help me ask better questions about it in such forums.

Problem Statement:
Given $n$ objects and two lists $V_n = \{v_1,v_2,\dots,v_n\}$ and $W_n=\{w_1,w_2,\dots,w_n\}$, where $V_n$ denotes the value for a particular item and $W_n$ denotes the weight for a particular item.

Pick $k$ items so that the following ratio is maximized:

$$\frac{\sum_{j=1}^{k}{v_{i_j}}}{\sum_{j=1}^{k}{w_{i_j}}} $$

I have seen the solutions but I am unable to fully understand them correctly. I have head that this problem was invented in 2005.

So does have some sort of a formal name ?


texts: Combinatorial Optimization: Shortest distance given sets of drivers and riders

texts:
Problem:

I have 2 sets, one of drivers and one of riders. All my participants need to reach one common destination. I wish to calculate the shortest combined distance in order for all participant to reach said destination. Although the goal is not to reduce the number of cars, drivers can be considered as passengers if the resulting distance is smaller.

Constraints:

Riders and drivers have distinct starting locations
All participants must reach the destination (common to all)
The riders need to be picked up by a driver
The drivers' cars have limited capacity and the capacity is individual to each car

I'm failing to understand what type of problem I'm facing, and I'm seeking some help.

Vehicle Routing Problem

I've thought of solving it as the Vehicle Routing Problem. A Capacitated Open Vehicle Routing Problem (COVRP) to be more exact. Drivers would act as the vehicle fleet and riders as the customers. A capacitated version because cars have limited seats, and an open version because drivers depart from unique positions and don't return to the "depot" but instead end on the destination.

Problem: In the VRP, not all vehicles of the fleet are used, and the remaining ones are left in their respective "depots". For my problem, I would need all participants to reach the final destination, so I need for existing vehicles to be considered as possible pick-ups for other vehicles.

I could just send the remaining drivers straight to the destination. But that wouldn't really provide a minimum distance solution to my problem, as better ones could be accomplished if the drivers could serve as customers.

Minimum Spanning Tree

As an MST problem, I could use the destination as the root and my participants (drivers and riders) as nodes. Each sub-graph originating from the root would be a cluster to be picked up by a driver.

Problem: The sub-graphs aren't guaranteed to have a driver's node in one end (to be used as a starting point and prevent doubling back on edges), and the sub-graphs may have paths with more nodes than available seats.

The capacitated MST variant introduces capacity to the solution, but it is a fixed capacity. Driver's cars have different capacities, so the MST sub-graphs would need to have individual sizes and each sub-graph would need to encompass the driver of the corresponding capacity.

Am I wrongfully categorizing my scenario as a combinatorial optimization problem?
I appreciate any help to fix the above-mentioned problems or to correctly categorize my computational problem.

Edit: If I managed to group the riders with drivers (with the use of some heuristic), then the remaining set would be drivers and their assigned passengers, or basically a list of clusters of 1+ participants.

I could then apply a capacitated MST solution to this collection. With the destination as root, the sub-graphs would be groupings of the previous clusters.
Ideally, each sub-graph would have different capacities in accordance with the seats of the containing cars.

I'm not sure that's possible, so I thought about doing a loop:

What're the most available seats in a single car?
Run the capacitated MST with that seat capacity
Get the sub-graph containing the car of the corresponding capacity
Remove all the clusters of that sub-graph from future computations
Repeat with the remaining cluster, until no more computations are possible

The problem I see arising is if the selected pivot car is in the middle of the sub-graph, meaning that it would need to double-back on edges because it wasn't a terminal node.

Still doesn't feel like a proper solution...

Thanks for the help!


texts:
I don't know how to solve this. The main thing I do know how buffers work but I don't know about display locations and lookup tables.

A color frame buffer has 3 bits per display location and 6 bits per entry in three lookup tables. What is total number of colors in the palette from which this frame buffer has to choose?


texts: How do I show that whether a PDA accepts some string $\{ w!w \mid w \in \{ 0, 1 \}^*\}$ is undecidable?

texts:
How do I show that the problem of deciding whether a PDA accepts some string of the form $\{ w!w \mid w \in \{ 0, 1 \}^*\}$ is undecidable?

I have tried to reduce this problem to another undecidable one such as whether two context-free grammars accept the same language. However, I'm not sure how to use it as a subroutine.


texts: If L is a regular language, how to show that cut(L) is not necessarily regular?

texts:
Given that L is a regular language. How do I show that cut(L) = {ac | abc ∈ L and |a| = |b| = |c|} is not necessarily regular?

My thought process is that this problem can be re-written as:

cut(L) = {aⁿcⁿ | aⁿbⁿcⁿ ∈ L where n ≥ 0}

I can then convert this to aᵖbᵖcᵖ, and have y consist entirely of 'a's as |xy| ≤ p
I can then pump y up or down, which will cause aᵖ⁺ᵐbᵖcᵖ, where m ≠ 0, making it no longer part of the language, thus being not regular.

However, I am confused as to whether I should be pumping aⁿcⁿ or aⁿbⁿcⁿ or if it even matters which one I do (both should give same result, but I'm not sure which one is the 'correct' one to actually pump)

I am also a bit unsure if my conversion of cut(L) = {ac | abc ∈ L and |a| = |b| = |c|} to cut(L) = {aⁿcⁿ | aⁿbⁿcⁿ ∈ L where n ≥ 0} is allowed either.


texts: DFA for the language L = { $ \omega = xy \in (a,b)^*\mid |x|_a = |y|_b $ }

texts:
I need to find a DFA for this language:
 L = { $ \omega = xy \in (a,b)^*\mid |x|_a = |y|_b $ }


texts: Could neural networks be considered metaheuristics?

texts:
A metaheuristic is defined as

  a metaheuristic is a higher-level procedure or heuristic designed to find, generate, or select a heuristic (partial search algorithm) that may provide a sufficiently good solution to an optimization problem

So my question is if a neural net could be consider in that definition


texts:
Last year, I was reading a fantastic paper on “Quantum Mechanics for Kindergarden”. It was not easy paper.

Now, I wonder how to explain quicksort in the simplest words possible. How can I prove (or at least handwave) that the average complexity is $O(n \log n)$, and what the best and the worst cases are, to a kindergarden class? Or at least in primary school?


texts: Reference asking : High Performance Computer Architecture

texts:
Topics

Pipelining: Basic concepts, instruction and arithmetic pipeline, data hazards, control
hazards, and structural hazards, techniques for handling hazards. Exception handling.
Pipeline optimization techniques. Compiler techniques for improving performance.
Hierarchical memory technology: Inclusion, Locality properties; Cache memory
organizations,Techniques for reducing cache misses; Virtual memory organization, Mapping and
management techniques, Memory replacement policies.
Instruction-level parallelism: Basic Concepts, Techniques for increasing ILP, Dynamic
scheduling (Tomasulo's Algorithm), Reorder buffer and instruction commit, Branch
prediction and advanced instruction delivery, Speculative execution. Superscalar, Superpipelined and VLIW processor architectures.Array and vector processors.
Multiprocessor architecture: Taxonomy of parallel architectures. Centralized shared-memory
Architecture. Synchronization, Memory consistency, Interconnection networks.
Distributed shared memory architecture. Model of memory consistency, Cache coherency,
Multiprocessing snooping protocol, Multiprocessing directory protocol. Cluster computers.
These are the topics I have to learn.
It will be great help if I am suggested any video resources or books regarding this.
Although I am going through Computer Architecture: A Quantitative
Approach by John L. Hennessy and David A. Patterson . But I need more resources.


texts:
Say there are two queues (1 and 2) in series.

The latency will be $t_1 + t_2$ without overlapping of their service times ($t_1$ and $t_2$ respectively).

If there is a overlapping, the latency will be $t_1 + t_2 - T_o$ where $T_o$ is the overlapped time. (Specifically $T_o = \min(t_1,t_2)$ in my case)

To my best understanding, queueing model is not suitable for modeling the overlapped service times. However, there would be some works for extension cause this overlapping is very common behavior, I believe.

How can I model overlapping service times in queueing model?


texts: Recursive algorithm for counting pairs of ancestor and child, where sum =n

texts:
Hey, this is a question from my handouts, but how would I go about writing a recursive program that would return the number of pairs of an ancestor and a child, whose sum equals to n, given that the program takes inputs of (tree t, sum a)

for example given this tree and 13, it will return 5 in the end, 13+0, 15-2, 6+7, 24-11, 12+1 (only ancestor and child, not siblings)

btw the tree itself is expressed in the following way: black indicates a child whereas red indicates a sibling.


texts: What Happens if I swap the forget gate and update gate in LSTM model?

texts:
Consider the following eqautions used in LSTM ( taken from Andrew ng's course on Sequential model)
In an LSTM model, LSTM Cell has three inputs at any time step t

Input($X_t , a^{(t-1)}, C^{(t-1)})$,
Here $X_t$ is the input vector, $a^{(t-1)}$ is the previous hidden state and $ C^{(t-1)}$ is the previous cell state

Now the new cell state $c^t$ is given by the following formula :
$C^t = $  forget_gate * $C^{(t-1)} + $ update_gate* $\overline{C^t}$

Question:
If I swap the places of forget_gate and update_gate, I still get a valid $C^t$, So why are we multilyting the previous cell state with forget gate only and the current cell state with update gate only, what if Imultiply previous cell state with update gate ?
Edit :  After swapping, the formula would look like this,
$C^t = $  update_gate * $C^{(t-1)} + $ forget_gate* $\overline{C^t}$


texts:
You are given $N$ $(1 \le N \le 10^6)$ positive integers $a_1, a_2, \ldots, a_N (1 \le a_i \le 10^6)$
and two positive integers $D$ $(1 \le D \le 10^6)$ and $M$ $(1 \le M \le 10^6)$

Find the longest contiguous subsequence such that

its sum $(a_i + a_{i+1} + \cdots + a_j)$ is divisible by $D$, and
$(a_i + a_{i+1} + \cdots + a_j) \le D\cdot M$.

I can find the longest contiguous subsequence such that its sum is divisible by $D$, but I don't know how to include the second condition. Can anyone help me to solve this problem? I think it should work in something like $O(N)$ or $O(N \cdot \log N)$.

To find the longest contiguous subsequence such that its sum is divisible by $D$, I use the fact that $(a_i + a_{i+1} + \cdots + a_j)$ is divisible by $D$ if and only if $(a_1 + a_2 + \cdots + a_{i-1}) \mod D = (a_1 + a_2 + \cdots + a_j) \mod D$. So, I calculate prefix sum and for every possible remainder I remember when it first occured.


texts: Valid-invalid bit in a process page table

texts:
Valid-invalid bit is used to indicate whether a page in a process’s page table is valid or not. Why is it needed?

Does that mean that each page table has a certain minimum size, i.e. it can accommodate minimum of n references to pages and if the number of pages being referenced by the process is less than n, then this bit is required to tell that only few entries are valid in the page table?

If the page table is built and populated dynamically, then the page table will only have as many entries as needed by process and there will no need for this bit, as all entries will be valid.

Other tags are page-table, valid-invalid bit


texts: Probability of Success in Slotted Medium Access

texts:
Suppose you have a network which uses time division multiplexing (i.e. Slotted Aloha). There are $N$ nodes each transmitting in a given slot with probability $p$.

I understand that the probability a node is successful in a slot is $p(1 - p)^{N-1}$. This is just a geometric distribution. But our book then says that the probability there is success in a slot (i.e. no collisions) is $Np(1-p)^{N-1}$.

I don't understand:

What the difference between the two probabilities (how is the probability that a node is successful in a slot different from the probability of success in a slot).
Why you need to multiply the probability by the number of nodes $N$ since $p(1 -p)^{N-1}$ gives you the probability that one node transmits and all other nodes don't transmit. Could it be because this is the probability that node might transmit given that all other nodes don't transmit, which isn't guaranteed. But we want to find the probability that any of the nodes transmit when all other nodes don't transmit - hence the multiplication by $N$?


texts:
I have a collection of subsets $\{S_1,\ldots,S_m\}$ where each $S_i\subset \{1,\ldots,n\}$. I would like to cover the maximum number of elements from $\{1,\ldots,n\}$ by choosing a single element from each $S_i$. What is the optimal way to do this?

For example, say I have $S_1=\{1\}$ and $S_2=\{2,3\}$ and $S_3=\{3\}$ and $n=3$. If my algorithm picks randomly (or the maximum number say) a number from each $S_i$, then I could obtain a solution that covers only $\{1,3\}$ but there is a solution that covers all elements.


texts: Leftist heap - determining time complexity

texts:
The time complexity of merge (union) operation is said to be $O(\lg (n_1 + n_2))$, where $n_1$ and $n_2$ are the numbers of elements in the merged heaps, respectively. I do not understand this - the algorithm has to go through all the elements of both rightmost paths of the original heaps - lengths of these paths are bound by $O(\lg n_1)$ and $O(\lg n_2)$. That makes $O(\lg n_1 + \lg n_2)$ in total, which is $O(\lg (n_1 n_2))$. Where am I making a mistake in my assumptions?

Arbitrary delete operation - the complexity should be $O(\lg n)$, where $n$ is the size of the heap. But after the deletion, the algorithm has to go through all the nodes from the parent of the deleted node to the root and correct the Leftist property, and the lenght of this path is bound by $O(n)$. Again, where am I wrong?


texts: Does writing more data to disk consume more energy than writing less?

texts:
As the title says, I am wondering if writing more data (i.e. larger files) to disk (e.g. Tablet SSDs) will consume more energy than smaller files.
My expected answer is "yes, because larger files take longer to write, hence need more energy". However, I am not sure if that is true.
If someone could shed some light (better with a link with more info from a reputable source), I'd really appreciate it.


texts: Why using finite automata in implementing lexical analyzers

texts:
I studied the subject of building a lexical analyzer using finite automata, through the classical way: Regular Expression -> NDA -> DFA. And I found it elegant, and a more solid approach for building a lexer.
Now my question is, what are other benifits from building a lexer this way, rather than the "ad hoc" way?


texts: How to prove certain parts of one regular language restricted by another regular language is also regular?

texts:
I’ve encountered the following difficult question that I don’t know how to solve.

$L_1$ and $L_2$ are regular languages over the same $\Sigma$. $$\begin{align}L^\wedge=&\{σ_1σ_2...σ_n\mid n\ge1, \sigma_1, \sigma_2, \cdots, \sigma_n\in \Sigma, \\
&\exists \mu_1, \mu_2,\cdots,\mu_n,\zeta_1,\zeta_2,\cdots\, \zeta_n
\in\Sigma, \\
&\mu_1\mu_2\cdots\mu_n\in L_2,\sigma_1\mu_1\zeta_1\sigma_2\mu_2\zeta_2...\sigma_n\mu_n\zeta_n\in L_1\}\\
&\cup\{a\mid a\in L_1, a\in L_2, a=\epsilon\}\end{align}$$
where the second set on the right hand side just says that $\epsilon\in L^\wedge\Leftrightarrow \epsilon\in L_1\land \epsilon \in L_2$.

How can we prove $L^\wedge$ is regular using closure properties or a product automaton?

What i tried to do is:

Since $n \geq 0$, we can build $\Sigma^* = \{ \sigma^* | \sigma \in \Sigma \} $ $(\Sigma \cup \Sigma) \to \Sigma^*$, then for some function h we can assign $h(\sigma)=\sigma$ (also $h(\sigma')=\sigma$), so because of homomorphism $h^{-1}(L_1 \cup L_2) = \{ \sigma_1...\sigma_n |\forall 1 \leq i \leq n \to \sigma_i \in \{ \mu_i,\mu_i' \}, \mu_1...\mu_n \in L_1 \cup L_2 \} $,

So if $(L_1 \cup L_2)' = h^{-1}(L_1 \cup L_2) \cap ( \sigma'\Sigma \Sigma')*=\{ \sigma_1'\sigma_2\sigma_3'...\sigma_{n-2}'\sigma_{n-1}\sigma{n}' | \sigma_1... \sigma_n \in (L_1 \cup L_2)$ is also regular

So if for some function $f$, $f(\sigma)=\sigma$ and $f(\sigma')=\epsilon$ $(f|f:(\Sigma' \cup \Sigma) \to \Sigma^*)$

Then $f(L_1' \cup L_2') = \{ \mu_1...\mu_n | σ_1μ_1ξ_1...σ_nμ_nξ_n∈L_1 \cup L_2 = L^∧$ and if regular because of regular languages closure to homomorphism

I know it’s complicated and would appreciate help with it, seeing how to do it correctly (pretty sure I've made some mistakes along the way).


texts: Can a new company make a processor compatible with Windows and current software?

texts: Would anyone apart from Intel and AMD ever be able to make a processor that can be used on a personal computer, or is it impossible? I believe it is due to them owning the x86 instruction set, which means that a company doesn't have the right to produce a processor which could run a personal computer. But what if the processor used a different instruction set, but in between it translated the x86 architecture to its own? Would that also be breaching the ownership?


texts: Expected number of vertices with degree 2

texts:
A simple graph with $n$ vertices is constructed by randomly and independently placing an edge between every two vertices with probability $p$. What is the expected number of nodes with degree two?

I was only able to find the probability of any vertex having degree 2. Let me explain what I tried. For any vertex we can have n-1 edges connecting it(since its a simple graph), so for it to have degree = 2, two of these n-1 edges should be there, and rest not.

This gives: $\binom{n−2}{2}p^2(1−p)^{n−3}$.


texts: How can a 16-bit or more processor store a byte in a byte-addressed memory

texts:
I am confused as to how a 16-bit (or 32, 64) processor can store multiple adjacent bytes at once without supplying multiple addresses

For example say we have (16-bit processor) 0xABCD starting at address 0x0000. For loading, the processor would just supply 0x0000 on the address bus and the way the bytes are laid out physically would produce 0xABCD on the data bus, then the processor would just do some neat bit-shifting to get the correct byte of the word

But for storing a byte, lets say 0xCD at address 0x01, what would the processor do about the other byte? (i.e. what would it do about location 0x00)

Thanks

EDIT: I am asking about big-endian architecures


texts: Can you multiply complex 2x2 matrices in fewer than 21 real multiplies?

texts: It is well known that 2x2 matrices can be multiplied using just 7 (instead of the obvious 8) multiplications in the ground field (Strassen-Winograd, etc.). It is also well known that complex numbers can be multiplied using just 3 real multiplications, using what is basically Karatsuba polynomial multiplication. You can obviously combine these tricks, either way round, to multiply two complex 2x2 matrices using 21 real multiplies (and some additions etc.). Is it known whether you can do better? Is there any way to do the whole computation in 20 or fewer multiplications?


texts: Optimize an underdetermined system with quartic constraints

texts:
I encountered an optimization problem which does not belong to any well-known category of optimization.

The system has $M$ (typically $M=120$) real variables and $N$ (typically $N=100$) constraints (all of them are equations), where $M>N$. Thus, all constraints can be satisfied.

The objective function is linear (weighted sum).

Some constraints are quartic equations (all terms are degree 4). Other constraints are quadratic equations (all terms are degree 2).

How to solve such optimization problem? I imagine there are two (possible) general approaches:

mathematical programming approach, e.g. nonlinear programming.
However, I find no specific program which fits the configurations
above.
meta-heuristics, e.g., hill-climbing or simulated annealing. I do not
prefer this approach because it does not address the nature of
under-determined system.


texts:
Can anyone explain me what (problem-)kernels are and what's the use of them? My slides say:

The kernel of a parameterized problem $L$ is a transformation $(x,k) \mapsto (x',k')$ such that:

$(x,k) \in L \Leftrightarrow  (x',k') \in L$
$|x'| \leq f(k)$ for some function $f$
$k' \leq g(k)$ for some function $g$
transformation must be computed in polynomial time.

My questions are:

How is this connected with a problem being fixed parameter tractable?
What makes kernels useful?
Where does this definition come from.

The example on my slides is for vertex cover, but I don't really get it, cause the slides are kind of short.


texts: Cuttings sticks in congruent equal sharing

texts:
You have $n$ congruent sticks (they have the same length). You want to divide them equaly among $m$ friends. To avoid envy, each friend should receive congruent parts, that is, the set of cutted sticks of one friend is exactly the same of any other friend.

Questions: Which is the minimal number of cuts in terms of $n$ and $m$? Is there an algorithm to decide where to cut?

Without the congruence restriction on the received cutted sticks, the problem was solved here.