texts:
Proposition: The binary search algorithm runs in $O(\log n)$ time for a sorted
sequence with $n$ elements.
When justifying this claim, first we say that with each recursive call the number of candidate entries still to be searched is given by the value
$$ high - low + 1 $$
The middle index, $mid$, is given by
$$ mid = \Biggl\lfloor\frac{high + low}2\Biggr\rfloor $$
We say that the number of remaining candidates is reduced by at least one half with each recursive call. Hence the number of remaining candidates, $n$, when we shift our $high$ index to the $(mid - 1)$ index is given by:
$$ n = (mid - 1) - low + 1 $$
$$ n = \Biggl\lfloor\frac{high + low}2\Biggr\rfloor - 1 - low + 1 $$
$$ n = \Biggl\lfloor\frac{high + low}2\Biggr\rfloor - low  $$
$$ n \le \Biggl\lfloor\frac{high  -low + 1}2\Biggr\rfloor $$
This is the part I don't understand how did we get from the equality equation to the inequality equation?
Again, when we are computing the maximum number of recursive calls performed, $r$, we say that $r$ is the smallest integer such that
$$ \frac{n}{2^r} < 1 $$
So:
$$ r > \log n $$
$$ r = \lfloor \log n \rfloor + 1 $$
Similarly, how did we get from the inequality equation to the equality equation?
Any help will be appreciated to help me understand this proof.


texts: Paper-based algorithm to find longest formula which is common to at least two formulas

texts:
Given a list of logical formulas:

f1: A&B
f2: A&D&C
f3: B&D&E
f4: A&B&C
f5:
fn: ...

In this case I want A&B as the longest formula which is common to at least two formulas.
Is there a simple algorithm to find the longest formula that could be performed on paper?


texts: Is there a super-linear lower bound on the time complexity of all solutions of NP complete problems?

texts:
$P \ne NP$ would imply that any polynomial is a lower bound on the time complexity of any NP complete problem.
Is some non-trivial lower bound known at all?


texts: Minimum Vertex Cover of 2 vertex disjoint odd cycles that have edges between them

texts:
Consider the graph $G$, which is comprised of 2 vertex disjoint odd cycles ($C_1$, $C_2$) where $|C_1|$ and $|C_2| \geq 5$. $G$ is sub-cubic and connected, with edges in between the cycles. Because $G$ is sub-cubic, each node's degree $\leq 3$ but $\geq 2$.
I am interested to know whether the minimum vertex cover of $G$ can be found in polynomial time? Furthermore, I am also interested to know whether we can:

Establish a tight upper bound on the MinVC for such a graph.
Say anything else about this graph that's insightful.

We know that for either cycle $C$, $MinVC = \left\lfloor\frac{|C|+1}{2}\right\rfloor$. Thus, $MinVC(G) \geq \left\lfloor\frac{|C_1|+1}{2}\right\rfloor+\left\lfloor\frac{|C_2|+1}{2}\right\rfloor$
A loose upper bound would be to take all vertices of one cycle and solve optimally for the other. Thus, $MinVC(G) \leq \min(|C_1|,|C_2|) + \left\lfloor\frac{\max(|C_1|, |C_2|)+1}{2}\right\rfloor$.


texts: Why do we need to take the derivative of the activation function in backwards propagation?

texts:
I was reading this article here: https://towardsdatascience.com/how-does-back-propagation-in-artificial-neural-networks-work-c7cad873ea7.

When he gets to the part where he calculates the loss at every node, he says to use the following formula:

"delta_0 = w . delta_1 . f'(z)
where values delta_0, w and f’(z) are those of the same unit’s, while delta_1 is the loss of the unit on the other side of the weighted link."

And $f$ is the activation function.

He then says:

"You can think of it this way, in order to get the loss of a node (e.g. Z0), we multiply the value of its corresponding f’(z) by the loss of the node it is connected to in the next layer (delta_1), by the weight of the link connecting both nodes."

However, he doesn't actually explain why we need the derivative term. Where does that term come from and why do we need it?

My idea so far is this:

The fact that the identity activation function causes the term to disappear is a hint. The node doesn't feed into the next exactly as is, it depends on the activation function. When the activation function is the identity, the loss at that node just passes to the next one based on the weight.
Basically, you just need to factor in the activation function somehow, specifically in a way that doesn't matter when it's the identity, and of course the derivative is a way to do this.

The issue is that this isn't very rigorous, so I'm looking for a slightly more detailed explanation.


texts: What are "state registers" and "code registers"?

texts:
While reading a chapter about FSM, I was stuck on the following slide:

In fact, I have been unable to determine what are "state registers" and "code registers", which were not explained in the course. Therefore, I have used  to search for the definitions on the net, but I haven't yet found any result.


texts: A question about parallel algorithm complexity

texts:
When in a Parallel algorithm we say:

  "This algorithm is done in $O(1)$ time using $O(n\log n)$ work, with $n$-exponential probability, or alternatively, in $O(\log n)$ time using $O(n)$ work, with $n$-exponential probability."

Then Can we Implement this algorithm for a Quad-Core Computer (and just 4 threads) with $n=100,000$?

The other question is what is the "$n$-exponential probability" in this sentence?

Thanks.


texts:
I'm studying about data structures and algorithms in that Time complexity  and calculating time complexity of the programs.

I just wondered that how to calculate time complexity of  non terminating loops such as infinite loops


texts: Graphs which favour BFS over DFS and vice versa

texts: I am trying to figure out what kinds of graphs are better suited to BFS and which are better suited to DFS. However i'm struggling to visualise what kind of graphs favour which search. Could someone give some simple graph examples and explain which search strategy would be more efficient/faster for the given graph?


texts: NOT satisfiable 3SAT instance certificate

texts:
Given a NOT satisfiable 3SAT instance, that we say $S$. Suppose that $M$ is a minimal subset of clauses of $S$ such that $M$ is NOT satisfiable. Say $X$ the subset of variables of $S$ that belong to the clause of $M$. For each Boolean values combination of the variables of $X$, we have a clause of $M$ that is false, because $M$ is NOT satisfiable.
The question is: is $M$ a polynomial certificate that $S$ is NOT satisfiable? I mean: if we have $M$, we can check that, for each possible Boolean value of the variables that are in $X$, there is a false clause in $M$. This means that $M$ is a certificate that $S$ is NOT satisfiable. Because each clause is false for only one Boolean value of the variables that are in the clause and becasue $M$ is minimal, the number of cases, that we have to check to verify that $M$ is NOT satisfiable, is the cardinality of $M$ (i.e. the number of clauses in $M$). Threfore the complexity of the certificate is linear on the number of clauses of $M$ (therefore linear on the number of clauses of $S$).
Here an example.
If $X=\left\{a,b,c\right\}$, $M$ contains all possibile combinations, three by three, of $\left\{a,b,c,\bar{a},\bar{b},\bar{c}\right\}$ ($9$ literals in all), without that a variable and its negation appear in the same clause (it would be a tautology). Therefore the number of clauses of $M$ is exponential on the number of the variables of $X$, but the number of clauses of $M$ is at most the number of clauses of $S$. In other word we have $cardinality(X)=O(\log(numberClauses(S)))$.


texts: Language Classification + AWS ML: what am I doing wrong?

texts:
I'm evaluating Amazon's machine learning platform, and thought that I would give it a "simple" classification problem first.  As a disclaimer, I am quite new to machine learning (hence my interest in an ML platform).

The classification problem is language detection.  Given a list of 20k words, and their language (English, French, or Random), train a model to classify new words.

My data is structured in CSV format, with 2 rows:

dàagzj, random
tunisia, english
craindre, french
voters, english
religions, english
condition, french
...

I imported the data successfully into the platform, and all seems fine.

When I attempt to run train a model (using both the default settings and tweaking them) I get the same result.  English is selected as the language nearly 100% of the time.

I know this problem is possible to get reasonably accurate results with simple neural networks, however I'm not sure what is going wrong?

Do I need to perform any preprocessing operations on the text input, or is the plain string sufficient?  What data can be collected about a single word that may be a more effective input to a machine learning model?


texts: About the first order logic (valid, Unsatisfiable, Syntactically wrong)

texts:
I am in trouble , I searched a lot about how to solve this kind of questions but I did not get any answers.

I understand how can I know when the sentences is valid and Unsatisfiable in propositional logic, but in FOL I can't.

Can someone help me how can I solve this kind of questions? Because it comes always in the past exams in AI.

Let us have the following:

1- ¬(Speed(Processor(MyPC))=Speed(Processor(MyPC)))
2- ¬ ∃ x ( Speed(x) = Speed(MyPC) )
3- Speed(MyPC)=MyPC
4- ∀ y ∃ x (Speed(x) ∧ Speed(y))= Speed(MyPC)

Note :

    MyPC:
    a constant symbols that represents my PC.

    Speed(x):
    a function symbol that refers to speed of x

The answer for 1 is Syntactically wrong
2 is Unsatisfiable
3 is Neither valid nor unsatisfiable
4 is Syntactically wrong


texts: Find longest common substring using a rolling hash

texts:
The longest common substring (LCS) of two input strings $s,t$ is a common substring (in both of them) of maximum length. We can relax the constraints to generalize the problem: find a common substring of length $k$. We can then use binary search to find the maximum $k$. This takes time $\cal O(n \lg n)$ provided that solving the relaxed problem takes linear time.

Finding a $k$-common substring can be solved using a rolling hash:

Compute hash values of all $k$-length substrings of $s$ and $t$.
If a hash of $s$ coincides with a hash of $t$, then we've found a $k$-length common substring.

Step 1 uses a rolling hash to achieve linear time but I can't see how we can perform step 2. in linear time. Any suggestions?


texts: How does TCP manage to discard segment received from a source other than the one with which the connection has been established?

texts:
It is known that TCP is a connection oriented transport layer protocol of the TCP/IP suite. But TCP (and UDP) operate over a connection less network layer protocol, the IP (internet protocol). What this means is that in TCP, if a sender sends data to the receiver, at the network layer, the receiver will accept the packet, without bothering about the source IP address of the packet. The receiver network layer then strips-off the IP-header from the received packet (and the IP address information of the source and the destination get stripped along with it), and passes off the remaining segment to the transport layer.

Now the doubt arises is, since the IP address information has been stripped away from the packet before forwarding it to the transport layer, how does the TCP sitting at the transport layer manage to decide from which IP address the information has come, when the only address details the transport header contains is the source and destination port numbers of the processes running on the respective hosts?


texts: prove that l={w ∈ {0, 1}*: n0(w) ≠ n1(w)} is a non regular language?

texts:
I tried doing this, but kept failing to prove. I know how to prove that the language is nonregular when  n0(w) = n1(w). The following is the proof for n0(w) = n1(w) using pumping lemma:

Assume L is regular. Then, by the Pumping Lemma, there is a natural number m such
that any w ∈ L with |w| ≥ m can be factored as w = xyz with |xy| ≤ m and |y| > 0,
and xyi
z ∈ L, for i = 0, 1...
Pick w = 0^m 1^m.
Then, 0^m 1^m = xyz, where y = 0k, for k > 0.
By the Pumping Lemma, xz ∈ L.
But, n0(xz) does not equal n1(xz).
The assumption that L is regular thus is false.
Hence Proved

However, I don't know how to prove it for when number of 0 is not equal to number of 1.


texts: Why isn't the time complexity of constructing a Fenwick tree tighter than $O(n\lg n)$?

texts:
Intuition:

Suppose I have an array of nonzero integer values $A[n]$ and a partially constructed Fenwick tree of this array: $F[k], n>k$. I can see why inserting the next element would be worst case $O(\lg n)$. The number of elements accessed from $F[0:k]$ to calculate $F[k+1]$ is equal to the number of trailing zeroes in $(k+1)_2$ which is at most $\lfloor \lg(n) \rfloor$. There are $n$ elements, so this is $O(n\lg n)$. Wikipedia seems to agree as well.

Thoughts:

NOTE: I am using this algorithm.

Consider the number of positive integers less than or equal to $n$ with exactly $j$ trailing zeroes in their binary representation, $j<{\lfloor \lg(n) \rfloor}$. Since the leftmost ${\lfloor \lg(n) \rfloor}-(j+1)$ digits can be freely assigned so long as the resulting number is less than $n$ ($j+1$ because the $(j+1)th$ digit from the right must be a $1$), there are between $2^{\lfloor \lg(n) \rfloor-j-1}$ and $2^{\lfloor \lg(n) \rfloor-j)}$ such numbers for any $n$.

Let an operation be defined as the summation of two numbers, which is assumed to be a constant time operation. (The other operations, like insertion, are also in constant time and are performed a constant number of times, hence they are ignored) Thus, for $j$ trailing zeroes, $j$ operations must be performed.

As a result, the total number of operations to perform is at most $\sum\limits_{j=0}^{\lfloor \lg(n) \rfloor} j2^{{\lfloor \lg(n) \rfloor}-j}$. It must also be true that $2^{\lfloor \lg(n) \rfloor}≤n<2^{\lfloor \lg(n) \rfloor + 1}$. Note that both maxima occur when $n_2$ is filled with ones. If we take this case, the mean number of operations for any $j$ as $n \rightarrow \infty$ should be:

$\lim_{n\to\infty}\frac{\sum\limits_{j=0}^{\lfloor \lg(n) \rfloor} j2^{{\lfloor \lg(n) \rfloor}-j}}{2^{\lfloor \lg(n) \rfloor +1}-1}
=\lim_{n\to\infty}{\sum\limits_{j=0}^n \frac {j}{2^{j}}}
=1$

Now, if we take the other extreme, where $\lg(n)\in\mathbb{Z}$ ($n_2$ is a one trailed exclusively by zeroes) then there are exactly $\lg(n)+\sum\limits_{j=0}^{\lg(n)-1} j2^{{\lg(n)-1}-j}$ operations to be performed over exactly $2^{\lg(n)}$ numbers, and the limit also approaches $1$. Testing seems to reveal that no other values of $n$ with the same $\lfloor \lg(n) \rfloor$ values have a higher mean number of operations per element than these.

If the amortized cost of inserting each element is indeed constant, shouldn't constructing the tree be $\Theta(n)$ time?

Testing:

I've tested the ranges between admittedly small consecutive powers of two, both by applying the summation and by brute force, and the results seem to agree:

Code using summation: http://pastebin.com/T3EEM7qz

Code using brute force: http://pastebin.com/sxdAkgxn


texts: How can I get 8 bits output from 4 bit CPU?

texts: I am very new to Computer architecture. I am thinking to add one more output register to this 4 bit CPU as shown below. However, I am not sure should I connect the output register to the current CPU. Should I connect it just the same way as the current one and label the 2 output register as output A and output B? But if I connect it the same way, the input data from ALU to output registers will always be only 4 bits, how should I get 8 bits output from the two output registers?


texts: How to model the constraint of a circle placement problem mathematically?

texts:
I have a circle with radius $R$ and $N$ points on a 2D plane with known locations $(x_i,y_i), i=1,2,..N$. I want to place the circle such that it maximizes the number of covered points.

Let $d_i=(x_i-x)^2+(y_i-y)^2$ be the square of the distance between the point $i$ and the potential center of the circle $(x,y)$. To ensure  point $i$ is within the circle, $d_i$ must satisfy $d_i\leq R^2$. This condition can be formulated by introducing a binary variable $u_i$ such that $u_i=1$ if point $i$ is inside the circle and $u_i=0$ otherwise. Then, we have

$u_i((x_i-x)^2+(y_i-y)^2)\leq R^2$

My question, does the constraint above model my problem correctly?.


texts: Oblivious Universal Turing Machine in O(T log(T)) time

texts:
I'm currently reading Computational Complexity: A Modern Approach. In this book, they give a proof of a universal Turing machine $U$ such that if $M(x)$ runs in $T$ steps, then $U(\lfloor M \rfloor, x)$ runs in $CT \log T$ steps where $C$ depends only on $M$'s alphabet size, number of tapes, and number of states. I'll describe $U$ loosely here:

  It has an input tape, output tape, tape for $M$'s states and transition functions, tape for $M$'s current state, and one work tape. We say $M$ has $k$ work tapes and an alphabet of $\Gamma$.

  $U$ uses an alphabet of $\Gamma^k$ to put the letters of all $k$ tapes on one cell and has a clever way of imitating the left and right shifts of different heads.

  Since we only have $T$ steps, we only need to go from $-T$ to $T$. We'll say $L_i$ goes from $2^i$ to $2^{i+1}-1$ and $R_i$ goes from $-2^{i+1}+1$ to $-2^i$. This goes from $i=0$ to $i=\log T+1$. For any $i$, $L_i$ and $R_i$ is full of blank symbols, half-blank half-filled, or completely filled. Furthermore, the total number of blank symbols in both $L_i$ and $R_i$ at one time is $2^i$, meaning half of all of the cells are blank while the other half is information.

  To left shift, find the smallest $i$ so $R_i$ is not empty and thus $L_i$ is not full. Put the leftmost non-blank symbol in position $0$ (i.e. under the head in $M$) and move the other $2^{i-1}-1$ non-blank symbols into the empty $R_0,R_1,...R_{i-1}$. This leaves all of those zones half-empty.

  Push the $2^{i-1}$ leftmost non-blank symbols in $L_{i-1},...,L_1$ into $L_i$ and then reorganize the other non-blank symbols to make $L_{i-1},...,L_1$ all half-full.

  Right shifts look similarly, except switch the roles of the left and right zones.

I want to solve the following exercise:

  Define a TM $M$ to be oblivious if its head movement does not depend on the input but only on the input length. That is, M is oblivious if for every input $x \in \{0, 1\}^∗$ and $i \in N$, the location of each of $M$’s heads at step $i$ of execution on input $x$ is only a function of $\lvert x \rvert$ and $i$. Show that for any time-constructible $T : \Bbb{N} \rightarrow \Bbb{N}$, if $L \in \mathbf{DTIME}(T(n))$, then there is an oblivious TM that decides $L$ in $O(T(n)\log T(n))$ time.

  Hint: Show that $U$ can be tweaked to be oblivious.

Now, my question is, under such a machine, while maintaining $CT\log T$ time, how do we make $U$ oblivious? I see how putting the input down initially and the left/right shifts are simply functions of $\lvert x \rvert$, but when we decide to left/right shift each tape has to decide on $x$ since we're not given that $T$ is oblivious, so how do we time the left and right shifts of $U$ so that they only depend on $\lvert x \rvert$ and not on the actual content of $x$?


texts: Course teaching time complexities in real life systems

texts:
Having mis-read What course in CS deals with the study of RAM, CPU, Storage? I now wonder what course in CS deals with time and space complexities including GPUs, CPU caches in multiple levels, seek times on hard disk vs. SSDs, and bandwidth to disk and RAM.
I was taught the big O-notation but it never took into account that I might have a GPU with 100s of cores, or a limited amount of extremely fast cache, or a harddisk that is has a high bandwidth, but a high seek time.
Which class teaches this extended version of algorithm time complexities, which takes real world limitations into account?


texts:
Assume that we have 10 points. If all those points are on the same plane, they all are coplanar. But some of them might be at a different place. That disrupts the structure of the plane if we were to draw the surface that passes from all the points.

I need a metric that tells me how fine the structure of the plane is preserved. Or how planar is the surface.

What I have thought is, take random 3 points among 10 and derive the plane equation in terms of $ax + by + cz = d$. Then, for each remaining point $p(p_x,p_y,p_z)$, calculate the summation $ap_x + bp_y + cp_z$. Store the results and take the standard deviation.

However this method fails for the following reason:
If there are 9 points on the same plane and only 1 point is far away, and if I pick the point who is far away, then the equation I generate is way too different then the plane defined by remaining 9 points.

Plugging the coordinates of remaining points into the equation of the plane, I'll get too many different results. Therefore, even though the surface is almost planar, standard deviation will be so high, depending on the generated equation.

This problem (I think) can be reduced to line cover problem (covering a set of points in 2D with minimum number of lines), hence, NP-Complete.

Or is it really? Is there a polynomial time algorithm that guarantees to find a value for all types of point sets?

I thought about starting not with 3 but with 4 points, then testing the other points. Does that work?


texts:
I'm trying to prove the following identity:
$$ ({L_A}^*\  L_B)^+ = (L_A \cup L_B)^*L_B $$

which is clearly true as both sides will exactly match "any sequence of A and B ending with B" :

$$ B, AB,AAB, ABBABAB, ... $$

I tried thinking about the set properties and even tried to reasoning about the NFA constructed by the the two sides of the equation but to no avail so far.

Does anyone know how to prove it?


texts: Does it matter for this function if the set we check membership of is finite?

texts:
I have the following problem.

  Let $\Phi$ be an admissible numbering of the single-parameter partially-recursive functions. That is, $\Phi(i, x) = f_i(x)$ with $f_i$ the $i$th partially-recusive function with one parameter. Denote with $f(x)\!\uparrow$ that $f(x)$ is undefined in the sense that its computation does not halt.

  Now let $B$ be a partially computable set (finite or infinite) so that $\Phi(i,i)\!\uparrow$ for all $i \in B$.

  Show that

  $\qquad H_1(x) = \begin{cases}1 \text{ if }
\Phi(x,x)\downarrow \\ 0 \text{ if } x \in B \\ \uparrow \text{
otherwise}\end{cases}$

  is partially recursive.

I know from here that there is even an infinite set. I am preparing for an exam, so just assume that they give an suitable infinite set. How would the program differ if B is a finite set like $B= \{b_1,b_2,\cdots,b_n\}$?

Also a function obtained from composition, recursion is partially computable. So since definition by piecewise is primitive recursive , Could I say $x \in B$ is partially computable if $B$ is finite or would it be better to comeup with a program. I don't know how using just these four instructions, one could say  $x \in B$ or not.

\begin{array} \\
\;\;\;\;\;\;\;\;\;Y \gets 0 \\
\;\;\;\;\;\;\;\;\;\text{IF } X \neq 0 \text{ GOTO } A \\
[E] \;\;\;\text{ GOTO } E \\
[A]\;\;\;\; Y \gets Y+1
\end{array}

I am using the Davis book of Computability where this is mentioned in page 70 of second edition.


texts: How Computer backend works when we play with GUI or CLI

texts: I’ve a question how do computer works in backend when we do anything on CLI or GUI ( i.e. making folders, running exe files, copy/paste etc), I mean how processor and ram works and how do they play with low-level language to show our desired result?


texts: Is Observational Equality better than intensional equality?

texts:
The Observational Equality from Epigram 2 seems to be intensional equality (like Coq and Agda have), but it also supports function extensionality. In that sense it seems that Observational Equality is better in every way than intensional equality in a type theory.
Is it true that it's always better to have Observational Equality instead of just intensional equality, or are there other trade-offs involved?


texts: Clarifications about CPU working: as the functions to get the operands are physically generated?

texts:
I ask patience to help me to have clarity because I tend to equivocate between formal rappresentation like

like operator is a token
bit
it is determined which operation is to be performed and how to get the   operands, according to a function whose domain consists...

and what is physically-electronic-logic rappresentation CPU elements operation like

CPU configuration signal
Registers
pulses

about some with respect to certain specific technical processes.
The cause is related to mixing high bit, operator, operand when it working like functions.

I don't what mean for 'value' - what is this 'value' ? A logic state, adressing mode? i don't understand why operands may as a constant value

Often, one group of bits (that is, a "field") within the instruction, called the opcode, indicates which operation is to be performed, while the remaining fields usually provide supplemental information required for the operation, such as the operands. Those operands may be pecified as a constant value

What it mean 'pulses' ? I don't understand well the connection of bit like rappresentation and its physical state version. This pulses are generated about what electronic component ?

the control unit produces the sequence of pulses on each control signal line required to implement that instruction

I really don't understand if this functions are math or logic states about operand assembly (decode).

Operand Assembly: once the word has been taken from memory, it is determined which operation is to be performed and how to get the operands, according to a function whose domain consists of the operating codes (typically the high order bits of the word) and the co-domain consists of the microprogram to be executed

But..as these functions are generated to get the addresses from which electronic element ? Registers ? Addressing Mode ? I don't understand if it refers about instruction sets, a part of the architecture or if one process?

I don't understand well this electronic logic passage. Hardwired ? Multiple clock pulses ? Is there some link to understand better this ?

In some CPU designs the instruction decoder is implemented as a hardwired, unchangeable circuit. In others, a microprogram is used to translate instructions into sets of CPU configuration signals that are applied sequentially over multiple clock pulses. In some cases the memory that stores the microprogram is rewritable, making it possible to change the way in which the CPU decodes instructions.

what is configuration signals physically-logic ?

is used to translate instructions into sets of CPU configuration signals

But it is done by the ALU or not?

I don't understand Microcode

The microcode is a layer of hardware-level instructions that implement higher-level machine code instructions or internal state machine sequencing in many digital processing elements

Operand: numerical data on which the product is an arithmetic or logic

I understand mean of high-order bit and high word
http://www.gamedev.net/topic/414290-please-explain-high-and-low-order-bitword-terminology/

I understand what is word
http://whatis.techtarget.com/definition/word

and is ok also operand definition (wiki) but I don't understand WHAT THEY ARE like LOGIC_PHYSICALLY ?
How they are made to logical-physical level?

I don't understand why defined bit length of a word is equivalent to the width of the computer's data bus so that a word can be moved in a single operation from storage to a processor register.


texts: Divide $n$ gifts among three people so as to minimize the difference in the total cost of gifts between the most lucky and the most unlucky people

texts:
Divide $n$ gifts of different values among three people so as to minimize the difference in the total cost of the gifts for the most lucky and the most unlucky persons.

The total value of $n$ gifts is $W$. The most fair division will be to give all of them gifts of the total value $W/3$.

Suppose $W_1, W_2, W_3$ are the total values of the gifts of the first, second and third person.

We want to minimize: $\max(W_1, W_2, W_3) - \min(W_1, W_2, W_3)$.

Using the knapsack problem. Assign to the first knapsack the "weight" $W/3$ and the same for the second knapsack $W/3$. Use double knapsack algorithm and get the for each knapsack the gifts that maximizes the total value but obeys the $W_{i \in {1,2}} \le W/3$ property. Then the remaining gifts give to the third person.

The question is if such kind of algorithm is correct? If so why? If no can you provide your own solution to the problem?


texts: Comparative study between Deep neural nets and Bayesian Networks

texts:
Is there any comparative study that showcases the powers of Bayesian Networks and Deep learning in their respective favorable setup and how they compare?

I tried to go through blogs but couldn't find out any experimental study where the respective models where described based on a example?

Rationale in putting this question: I am planning to work on Bayesian networks and I know they are great for inference and answering complex queries. But I couldn't find any convincing experimental results where they seemed to be more favorable as compared to other sophisticated machine learning tools like deep neural nets or conventional deep neural nets.


texts:
Say you have an array of integers like [1, 2, 3, 4, 5, 6], the problem is to find the smallest way to break up the array into sub-arrays where each sub-array satisfies the following requirement:

sub-array.first_integer and sub-array.last_integer must have a common divisor that is not 1.

So for [7, 2, 3, 4, 5, 6] the answer would be 2, because you can break it up like [7] and [2, 3, 4, 5, 6], where 2 and 6 have a common divisor of 2 (which is > 1 so it meets the requirement).
You can assume the array can be huge but the numbers are not too big. Is there a way to do this in n or n*log(n) time? I think with dp and caching n^2 is possible but not sure how to do it faster.
Here is my current attempt with a BFS, but it's still N^2:
https://onlinegdb.com/ryZwkYnA8
Edit: OK I think I found an improvement which is a polynomial times the square root of a pseudo-polynomial: n * sqrt(magnitude of the values). Seems much faster, it basically builds an adjacency list; and can be done BFS, DP, and caching all the same. Although I wonder if anything better is available?
https://onlinegdb.com/SJpl4930L


texts: Would using the mean as pivot speed up quicksort?

texts:
Somehow I thought about quicksort last night and was reading about it on Wikipedia. The interesting part for me was:
'If we could consistently choose a pivot from the middle 50 percent, we would only have to split the list at most $\log_{4/3} n$.
The choice of the pivot seems to be one possible problem of quicksort that can lead to $O(n^2)$ behavior.

My idea was: If in each step one would use the mean of the partition as pivot, this could increase the speed significantly.
Especially after a few steps, when outliers are in their own division of the list, the mean and median should be very close to each other (once again, looking at large lists).
The additional time during each step to calculate the mean should be $n$. Therefore:

Quicksort estimated time: $nA\log_{4/3} n$

Quicksort_mean estimated time: $2nA\log_{5/3} n$

(5/3 is most likely a conservative estimation by me, could as well be closer to 2, as subsets should quickly be without outliers).
So, starting at around 10,000 entries Quicksort_mean would be (on average) faster than Quicksort. Furthermore, it would never risk to be $O(n^2)$, as it is bound to not take the minimal or maximal element of the stack.

My main question is: Did I miss anything? I have to admit, I never implemented quicksort myself, so I might miss out on other parts of the whole thing (storage, etc.)


texts:
I have a set of observations of real data, and a set of Random Variables I produce my self. The goal is to generated Random Variables with the same Distribution as the real data. To investigate the simliarity the two distributions, I use the Kullback-Leibler Divergence. Now with the genetic algorithm of Matlab, I try to find the best parameters for my generator, the thing only is that genetic algorithm is stochastic and so I have no consistent results for the Kullback Leibler Divergence. One idea would be though to run my generator say a thousand times then chosse the minimum Kullback-Leibler Divergence and reproduce the result with this: http://www.mathworks.ch/ch/help/gads/reproducing-your-results-1.html
Would that work? The idea would be to get a continuous fitness function...


texts:
I'm currently reading The Algorithm Design Manual by Steven S. Skiena as my first book to algorithms.
Something in the asymptotic part is kinda of confusing to me.
Proving the Theta
The analysis above gives a quadratic-time upper bound on the running time of
this simple pattern matching algorithm. To prove the theta, we must show an
example where it actually does take Ω(mn) time.
Consider what happens when the text t = “aaaa . . . aaaa” is a string of n
a’s, and the pattern p = “aaaa . . . aaab” is a string of m − 1 a’s followed by a b.
Wherever the pattern is positioned on the text, the while loop will successfully
match the first m − 1 characters before failing on the last one. There are
n − m + 1 possible positions where p can sit on t without overhanging the end,
so the running time is:
(n − m + 1)(m) = mn − m 2 + m = Ω(mn)
This example is clearly meant to be the worst possible running time of the algorithm, however, instead of O(mn), Ω(mn) has been used.
Isn't Ω the lower bound of the algorithm, meaning for big enough n(s) the algorithm cannot perform better than this?
If it is then why is Ω used to show the worst performance, shouldn't Big Oh be used instead?
Any help would be much appreciated.


texts: Operating Systems - SJN/Round Robin - turn around time + waiting time

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

SJN (Shortest Job Next).

Round Robin with a quantum of 10.

Answer -
https://imgur.com/sLN8Vwr

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

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

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


texts: Graph partition that maximize the number of triangles within its parts

texts:
Given a graph $G = (V,E)$, how to partition $V$ into $k$ parts $P_1, P_2, \ldots P_k$ of at most $M$ vertices, such that the number of triangles (3-cliques) contained in the parts is maximal?
This seems NP-complete. Was this problem studied before? (I couldn't find anything after searching clique graph partition). Furthermore, I would appreciate a heuristic approach to solve it.


texts: The language of machines that accepts all palindromes is not Turing recognizable

texts:
I have this question:

  $L = \{\langle M \rangle | M$ is TM that accepts every palindrome over
  its alphabet $\}$

  Proof that $L$ is not Turing-recognizable by showing reduction from other non Turing-recognizable language.

What I have tried to do is to show reduction from $A_{TM}$ (Accept problem) to $\bar L$, and I didn't succeed to show one. I tried to create a new machine that will reject some palindrome(s) if $M$ accepted $w$ when $\langle M,w\rangle$ is the input of $A_{TM}$. But if $M$ will not halt on $w$, then the palindrome(s) will reject also by mistake.

So how can I show reduction from $A_{TM}$ to $\bar L$ (or $\bar {A_{TM}}$ to $L$)?


texts: I am trying to implement a simple web search engine mechanism with using HITS algorithm. I understand how the algorithm work and produce hubs and authority values for each page. But how can I use this hubs and authorities values to sort web pages? Let's say I have 100 page, their urls, their contents and their hub and authority values. How can I use these to rank pages? I know that there must be tons of way to do that but I mean is there a well-known way to use it like if there is a standard way of doing this?


texts: Computing coefficients of $p(x)^n$ in time $O(n \log n)$

texts:
For homework I've to give an algorithm that computes the coefficients of the polynomial $p(x)^n$ in time $O(n\log n)$, where $p(x)$ is a polynomial of degree 7.
As an hint I'm told to consider first the case where $n$ is a power of 2.
My guess is that I should use FFT and somehow manipulate it with modulo operations (maybe using the fact that for even powers the unity roots of power $n$ are the same as for $n/2$, only twice) but I'm pretty clueless about this one.


texts: Find sequence, given partial information about all pairs

texts:
Let $\Sigma$ be a small, finite alphabet.  Suppose we are given ${n\choose 2}$ sets $S_{i,j}$, where $S_{i,j} \subseteq \Sigma \times\Sigma$.  I'd like to determine whether there exists a sequence $x_1,x_2,\dots,x_n \in \Sigma$ such that $(x_i,x_j) \in S_{i,j}$ for all $i,j$, and if so, find an example of such a sequence.

Are there any good algorithms for this problem?

Also: Suppose I model each set $S_{i,j}$ as a randomly chosen subset of $\Sigma \times \Sigma$ where each of the possible elements is included in $S_{i,j}$ with probability $p$ (independently of everything else).  Thus, the expected size of each $S_{i,j}$ is $p \cdot |\Sigma|^2$.  Is there any characterization of the range of values of $p$ for which this problem should be efficiently solvable?

(In my application, $|\Sigma|=10$, if that helps.)

This looks like some sort of 2-CSP (constraint satisfaction problem, where each constraint is on exactly 2 variables), but I don't know what more we might be able to say.


texts:
This question wask asked in a homework of Computer Theory in Rome, Italy.

  How to simplify the DPLL algorithm in order to solve HORNSAT?

My Approach:

I know that an  Horn clause is an OR of literals where it contains at most one pure literal and any number of negative literals.

I would start with the following algorithm:

FUNCTION $Dpll(S)$:

IF $S = \emptyset $ RET SAT
WHILE $\exists$ one unit clause $(p)$ or $\exists$ one literal $p$ that appears pure in $S$
IF ( $p \in S \wedge \neg p \in S) $ RET UNSAT
ELSE $S = Unit-propagate(S,p)$
ENDIF ENDWHILE
IF $S = \emptyset $ RET SAT
choose one literal $p$ in one clause in $S$
IF $(DPLL(Unit-propagate(S,p) == SAT)$ RET SAT
ELSE RET $DPLL(Unit-propagate(S,\neg p)$

FUNCTION $Unit-propagate(S,p)$

Delete every clause in $s$ that contains $p$
Delete every occurence of $\neg p$
RET $S$


texts: FPTAS for knapsack with private valuations

texts: The Knapsack problem has a well-known FPTAS based on rounding and then using the pseudopolynomial dynamic programming algorithm. When the valuations $v_i$ are private, we also need the assignment rule to be monotonic (i.e., if a player gets included in the knapsack, then if he increases his bid/valuation, he should still be in the knapsack.) However, the well-known FPTAS does not seem to satisfy this because of rounding. Is there a way to fix it?


texts:
I'm being asked the following

  Find a language $L$, such that $L \notin \mathbf{P}$, but $L^* \in \mathbf{P}$

For the $L \notin \mathbf{P}$-part I have to show that there is no polynomial Turing Machine that could accept $L$.

I've been struggling with this problem for quite a while, so I would appreciate any help with it.

My attempt:

Let

$$L = \{0, 1\} \cup \{0^i| M_i\text{ does not accept }\langle M_i \rangle\}$$

Then $L^* = \{0, 1\}^*$. Since this language is regular, we can defined a TM that works on the word $w$ in just a single pass $\implies$ TM runs in $O(|w|) = O(n) \implies L^* \in \mathbf{P}$.

I take this $L$ as example because it seems to me easier to show that $L \notin \mathbf{P}$ by proving that indeed there is no MT that accepts $L$ than showing that it is not accepted by any polynomial MT. To prove the former I was thinking about applying a diagolization argument on $L$.

Am I on the right track? It seems to me that I'm trying to prove something stronger than what I'm asked, so maybe there is a more straightforward way.

Thanks!


texts:
I want to calculate the order of this function, I calculated but I'm not sure if this right.

This is the function

int fct (int Y){
        int y = 0 ;
        for ( int i =0; i<Y;++ i ){
            for ( int j=i ; j >=0;--j ){
                y++;
                }
            }
            return y ;
    }

And this is my calculus:

For Inner Loop

\1+1+sum_{j=i}^{n-1}(1+1+1)=3n-1

For First loop

\1+1+sum_{i=o}^{n}(3n-1+1)=3n^{2}+2

Finally 3n^{2}+1+2=3n^{2}+3= O(n^{2})

Its right this solution?

Thanks


texts: Machine Learning Algorithm Recommendation For Sensor Data

texts:
I would like to classify data coming from a sensor. In the literature Hidden Markov Model and SVM are used, but I would like to improve results with another methods.The picture how data and classes are as follows;

x is time axis and y is sensor outputs axis.
The yellow is how signal looks like and it randomly changes in the range of red dashes.
Green vertical lines are the boundaries for specific classes written in Red color.

The algorithm should make the classification online, I mean while data is coming to the algorithm, it should classify them immediately.

Could you please recommend possible machine learning algorithms for this type of classification?


texts: Should all internal node keys in B+ tree also be in the leaves?

texts:
I was reading about B+ tree insertion.
The algorithm takes following form:

Insert the new node as the leaf node.

If the leaf node overflows, split the node and copy the middle element to the parent index node.

If the index node overflows, split that node and move the middle element to the parent index node.

However, adding the new index value in the parent node may cause it, in turn, to split. In fact, all the nodes on the path from a leaf to the root may split when a new value is added to a leaf node. If the root node splits, the tree grows by one level.

Now the book asks to insert 33 in following tree of order 4:

I was guessing how those [10,20,30] occur to be the root node. Before performing first split while forming above tree, these [10.20,30] should be in some leaf and in any case they should be present in some leaf.
In other words I feel that all internal node keys should also be present in the leaves. However thats not the case with [10,20,30]. This is also inline with the fact that in B+ tree all data is present in the leaves, so all keys should be present in the leaves.
Another example on youtube also have 13 and 30 in the root node but not in any leaf.
Am I wrong with the fact that all internal node keys should also be in the leaves?


texts: What is the difference between ∀ and Π in the Calculus of Constructions?

texts:
As I've learned, the Calculus of Constructions has only two binders - $\lambda$ and $\Pi$. Morte, for example, has $\forall$ as a mere alias of $\Pi$. Yet, on the paper Self Types for Dependently Typed Lambda Encodings, there are types such as:

$$\begin{gather}
  \mathrm{Nat} := \forall X. (X \rightarrow X) \rightarrow X \rightarrow X \\
  \mathrm{It} : \forall X. \Pi x : \mathrm{Nat}. (X \rightarrow X) \rightarrow X \rightarrow X \\
  \mathrm{Ind} : \forall P : \mathrm{Nat} \rightarrow \mathord{\ast}. \; \Pi x:\mathrm{Nat}. \; (\Pi y:\mathrm{Nat}. (P \, y \rightarrow P (S \, y))) \rightarrow P \, \bar 0 \rightarrow P \, x
\end{gather}$$

Notice that the paper uses both $\forall$ and $\Pi$. Moreover, $\forall$ is used both with the syntax $\forall a : b \rightarrow c$ and $\forall a . b$. I can't parse those expressions. What is the difference between $\forall$ and $\Pi$, and how would you express those types on Morte?


texts:
There is a directed social network with large number of nodes and arcs and there are many instances of the network (nodes are same but arcs change in each instance). You can think of it as a stochastic network with probabilities on the arcs, so that in each scenario you end up a different instance of the network (in terms of arcs).

For each node in the network and for each instance we run BFS to determine the successor set. As you may realize we need to run the BFS ($n \cdot k$) times where $n$ is the number of nodes and $k$ is the number of instances. However for a given instance, there may be a much efficient way of doing the BFS. For instance during the steps of BFS if we meet a node whose successor set is already calculated, we directly add that whole set and do not continue further in that direction. This improves the performance when we consider all the nodes, however it still takes too much time for large networks.

So the challenge is: Is there an efficient all-nodes BFS algorithm that computes the BFS sets of all nodes, that is faster than the above method? (Similar to the comparison of Dijkstra and Floyd-Warshall for shortest paths)


texts: Converting a regular expression to a context-free grammar

texts:
Does this conversion look right? I am learning conversion from RE to CFG.
RE:
$$(a \cup b)^* \cup ab(a \cup b)^*$$
CFG:
Terminals:
$$ S_1 \to a \\ S_2 \to b $$
This is for the first $(a + b)^*$:
\begin{align}
&S_3 \to S_1 \mid S_2 && (a \cup b) \\
&S_4 \to S_3S_4 \mid \epsilon && (a \cup b)^*
\end{align}
This is for the $ab$ in the middle:
$$ S_5 \to a \\ S_6 \to b $$
This is for the second $(a \cup b)$ and $(ab)$ in the middle:
\begin{align}
&S_7 \to S_1 \mid S_2 && (a \cup b) \\
&S_8 \to S_7S_8 \mid \epsilon && (a \cup b)^* \\
&S_9 \to S_5 S_6 && (ab)
\end{align}
Concatenated $ab$ with the second $(a \cup b)^*$:
\begin{align}
&S_{10} \to S_8 S_9 && (ab(a \cup b)^*)
\end{align}
This the final CFG:
\begin{align}
&S_{11} \to S_4 \mid S_{10} && (a \cup b)^* \cup ab(a \cup b)^*
\end{align}


texts: Does the k-clique problem became easier on sparse graphs?

texts:
Some definitions, just to not create confusion:

A sparse graph is a graph that contains a number of edges less or equal than the number of vertices.
In $k$-clique problem we are given a graph and an integer $k$, and the task is to decide whether the graph contains a $k$-clique.

I think that even if we have a sparse graph, nothing changes for the $k$-clique problem (it always has complexity $O(n^k)$ if $k$ is less than number of vertices and it has complexity $O(n^n)$ if $k$ is equal to the number of vertices), but I'm not so sure about this.

Is a $k$-clique easier to find if the graph is sparse?


texts: What is the probability of friendship conditioned on the number of mutual friends

texts:
Let Alice and Bob be two users chosen uniformly at random from a social network (e.g. Facebook). What is the probability that they are friends assuming that they share $k$ mutual friends?

I am interested both in the experimental values (or estimates) from currently existing social networks (e.g. Facebook) and values predicted by random graph models for these social networks.


texts: Understanding connection between length of codeword and hamming distance in Hamming code

texts:
I came across following in Huffman coding:

  Minimum Hamming distance to correct up to s errors is $2s + 1$ because that way the legal codewords are so far apart that even with $s$ changes the original codeword is still closer than any other codeword.

Then I came across following:

  Consider dataword length of $m$ bits, codeword length of $n$ bits. So redundant check bits will be $n-m = r$. Each of the $2^m$ legal messages has $n$ illegal codewords at a distance of $1$ from it. These are formed by systematically inverting each of the $n$ bits in the $n$-bit codeword formed from it. Thus, each of the $2^m$ legal messages requires $n+1$ bit patterns dedicated to it. Since the total number of bit patterns is $2^n$, we must have $(n+1) 2^m ≤ 2^n$.

Using this information, I took $m=4$ and found that to meet above equation, $n \ge 7$. So with $n = 7$, I prepared Huffman code for $m = 4$ as shown in the image ($d$ are data bits, $c$ are check bits):

The code has hamming distance of 3 which confirms with $2(1)+1 = 3$ as required to correct 1 bit errors.

Q1. But then, how satisfying $(n+1) 2^m ≤ 2^n$ also ensures hamming distance is 3?

Q2. Also what will be equation if I want to correct $k$ bit errors? Will it be $(\binom{n}{k}+1)2^m\leq 2^n$?


texts: Select the maximum number of links to satisfy the constraint on each link. How to prove is NP-hard?

texts:
Instance: $n$ non-negative real numbers $P_1,\ldots,P_n$, a positive number $k\le n$, and a positive number $\epsilon$.

Question: Is there a subset $S$ of $\{1,\ldots,n\}$ of cardinality $|S|\geq k$ such that

$$\dfrac{P_i}{\epsilon-P_i+\sum_{j\in S}P_j}\geq 1,\text{ for all } i \in S.$$

Can you see a simple, direct reduction from an NP-hard problem?

Note.  This problem is studied in wireless communication where the set represents links in a wireless network, the $P_i$ represents the powers and the constraint represent a quality of service guarantee.

I believe a more general problem is proven NP-hard, see for example here, but the reduction is very hard for me.


texts: While number can be checked for primality in O(n^0.5) then why was it considered to be not in P until AKS test?

texts: While a basic algorithm to check for primality of a number 'n' [checking if a divides n for all a less than n] would take O(n), AKS test was the breakthrough after which it was placed in P complexity class.


texts: Are arc consistency algorithms such as AC-3 inevitable for CSP to be solved more efficiently through pruning of inconsistent values? Can't we use the constraints that we have and predict arc inconsistencies by way of logical inference? Arc consistency algorithms feel quite primitive...There must be a more sophisticated way.


texts: All possible Red Black Trees with this set {1,2,3,4,5}


texts: Seek to infer "correct" route from sequence of stops

texts:
Let us consider school buses. Let a 'Bus Route' be a sequence of bus stops travelled by a single school bus (day after day). Let a 'Bus Stop' be a combination of Latitude (Lat), Longitude (Lon) and Time-of-Day (ToD). That is, a bus may stop at the same Lat/Lon to pick up kids in the morning and again in the afternoon to drop them off. Furthermore, a bus may stop at a certain Lat/Lon at 7am to pick up high school kids, drop them at school, and then visit the same Lat/Lon at 7:30am to pick up middle school kids, and again at 8am to pick up elementary school kids.

Suppose that a bus sends its Lat/Lon/ToD every time it activates its stop-arm (which it does when it stops to let kids on/off the bus). Suppose we have the Lat/Lon/ToD information for a particular bus for 20 consecutive days.

In a perfect world the bus would make every stop at approximately the same time every day. In the imperfect world in which we live these things happen:

When there are no kids waiting at a bus stop in the morning the driver does not stop (so no Lat/Lon/Tod get sent). On any given day there may or may not be kids at any given bus stop.

When no kid are waiting to get off the bus a given stop the bus will not stop (so no Lat/Lon/Tod gets sent).

So, if there are "in fact" 30 stops, on some days the bus will make 30 stops, on other days it may make 20 stops, etc.

Let's assume that algorithms are already in place to analyze the Lat/Lon/ToD tuples for the 20 days worth of data and correctly identify a set of Bus Stops.

Placing the Bus Stops into the correct order would be a simple matter except that:

On some days the bus may visit stops in one order and some days in a different order. So, if Bus Stops are labelled with letters, on one day the path might be:
A C D F H I J L N

and on the next day the order might be:

A B C D H F J L M N

(Notice there is a sequence "D F H" in the first and "D H F" in the second) This can happen for several reason, including:

a) different drivers have different ideas about what is the best route.
b) the driver made a mistake, missed a stop, and has to go back.

ASSUME: there is nobody to ask, "What is the correct route (sequence of stops)?"

PROBLEM: using only the collected data, how can we construct the sequence "most likely" to be correct?

To be clear, this is not an optimization problem; I do not seed to find the "best" route. Rather, if, for example, the bus made exactly the same sequence of stops on 19 of 20 days and on the one odd day the order of two stops was reversed (compared to the other 19) then the "correct" route would be the sequence traveled on the 19 days. What I seek to do is to infer what is most likely the intended route by analyzing when and where the bus actually stops given that drivers skip some stops on some days and sometimes visit some days in different sequence on different days

Thanks for any help you can offer.

Regards, Matt


texts: Is the capacity of a hash table a constant value?

texts:
In this paper, page 4, it is said:

"...there is always a constant expected number of elements that map to the same slot"

Assume we have a set $S$ of $n$ values, and we want to insert them into a hash table. Let's fix some parameters: let $d$ be the hash table's bin/slot capacity, i.e. the bin will get more than $d$ elements only with a negligible probability. Then, we set the hash table length, $h$.

Question 1: is it correct that the capacity of each bin is constant?

Moreover, assume we want to perform an operation on only one bin of the hash table.

Question 2: Is it correct to say the complexity of the operation is constant? because it performs the operation on a constant elements of the set $S$?

Update: Please note that the updated is inserted after the answer is given by provided by @D.W.

I am using a simple static hash table. Assume that the number of elements $n$ is known in advance. Also, for some reasons we want a bin capacity be $d$ with a high probability (e.g. $2^{40}$). Moreover, we use the equation in theorem 1, in here to calculate the number of bins (or hash table length) required. Furthermore, we want to perform a polynomial factorization, whose complexity is $O(d^{2})$, in one bin.


texts:
Consider an unweighted, undirected, simple graph $G=(V,E)$. We have some subset $S \subseteq V$, and we want to determine the shortest distance from any vertex $v\in V$ to some vertex $s\in S$.

To be clear, each $v\in V$ has a distance $d_1, d_2,\dots , d_{|S|}$ to each $s\in S$, and we want to find the smallest value of all $d_1, d_2,\dots , d_{|S|}$, and do this for every $v\in V$. So every $s\in S$, for example, would have a distance of $0$.

The algorithm should run in $O(|V|+|E|)$ time. Note that this is independent of $|S|$. I was thinking of running simultaneous BFS's on each $s\in S$ and only assign a vertex a distance if it doesnt already have a distance estimate (i.e. no other node in $s$ reached to $v$ earlier). I'm not really sure how to make the runtime work out though, since we would have to cut off the BFS at some point to prevent a factor of $|S|$ in the runtime.

Also, this is not a homework problem, it's a question from a midterm from a class a few years ago that I am using to study for my final coming up, and the solutions are not available. Thanks for the help!


texts: Operations without common elements can not be generated using a finite state automata

texts:
I heard that some operations involving regexes that do not have common elements can NOT be generated using a finite automata. I do not remember what it was, where it was from, can anyone tell me what that could possibly be?
Edit : I finally managed to find the exact statement. Here it is, below :
A language (like $(00)^n (11)^n$) can not be generated by an FSM since there is no common character in "00" and "11". We need to keep count of both which is not possible with a finite automata as the count can be infinite.


texts: How can a user process even try to access a memory location its not allowed to when it doesn't have access to page table?

texts:
So is it even possible for a user process to even try to access a physical memory location that does not belong to it and therefore getting an error by operating system?

because for example with a 32 bit cpu the user process has an illusion of having a 32 bit memory all for it self (correct me if I'm wrong) and each page of this virtual memory has a corresponding entry in the page table that says whether this page exists in the real memory or not

but considering user process does not have access to the page table to modify it, how can a process even try to access a memory location in physical memory that doesn't belong to it considering the page table won't let that happen?

does this scenario ever happen? (because i remember reading something about operating systems using exceptions when a process tries to access something that does not belong to it but I'm not sure)


texts: Is it possible to have a zero knowledge proof with a P Prover?

texts:
In the literature, when reading about zero knowledge proofs, the prover (prover/verifier) is always given an unlimited computational power or just capacity to solve NP.
Is it necessary for the prover to have higher computational power than the verifier?
If it is, is there any variant that does not need this property?
If any of the answers is yes can you give me references?


texts:
Suppose $\varphi: X \rightarrow Y$ is a function between feature spaces that I want to model. I want to produce two easily computable functions $\phi_X: X \rightarrow \mathbb{R}^m$ and $\phi_Y: Y \rightarrow \mathbb{R}^n$ so the distance $|\phi_X(x) - \phi_X(x')|$ for $x, x'$ in $X$ is correlated as well as possible with $|\phi_Y(\varphi(x)) - \phi_Y(\varphi(x'))|$.

My question is simple: is there any research going on about questions like this? The problem seems awkwardly stuck between a clustering problem and a classification problem. I don't need an ironclad way of approaching the problem (there almost certainly isn't one), but I was wondering if the problem had any better classification than as a kinda-regression.

EDIT: As per D.W.'s comment, my condition is poorly stated as it stands. A condition that better expresses what I meant is to find a method that, given a point $x \in X$, a finite set of points $y_i \in Y$, and an assurance that $\varphi(x) = y_i$ for some $i$, to determine the most likely $y_i$ that fits this bill. But this is straight machine-ranking, solving the question.


texts: Understanding the union of an undecidable language with a finite or decidable language

texts:
I'm trying to prove that the language $L \cup A$ is undecidable, when the language $L$ is undecidable and the language $A$ is finite or decidable.
This is confusing me because if $L$ were to be a semi-decidable language, then this would be easy to prove (with either pseudocode or TMs), but as I understand not all undecidable languages are semi-decidable, and I don't know what to do with those ones.


texts: Concise example of exponential cost of ML type inference


texts: Randomized Rounding of Solutions to Linear Programs

texts:
Integer linear programming (ILP) is an incredibly powerful tool in combinatorial optimization. If we can formulate some problem as an instance of an ILP then solvers are guaranteed to find the global optimum. However, enforcing integral solutions has runtime that is exponential in the worst case. To cope with this barrier, several approximation methods related to ILPs can be used,

Primal-Dual Schema
Randomized Rounding

The Primal-Dual Schema is a versatile method that gives us a "packaged" way to come up with a greedy algorithm and prove its approximation bounds using the relaxed dual LP. Resulting combinatorial algorithms tend to be very fast and perform quite well in practice. However its relation to linear programming is closer tied to the analysis. Further because of this analysis, we can easily show that constraints are not violated.

Randomized rounding takes a different approach and solves the relaxed LP (using interior-point or ellipsoid methods) and rounds variables according to some probability distribution. If approximation bounds can be proven this method, like the Primal-Dual schema, is quite useful. However, one portion is not quite clear to me:

  How do randomized rounding schemes show that constraints are not violated?

It would appear that naively flipping a coin, while resulting in a 0-1 solution, could violate constraints! Any help illuminating this issue would be appreciated. Thank you.


texts: Language that fulfills pumping lemma but is not in RE

texts: I am supposed to find a language $$L\subseteq \Sigma ^*, \Sigma \subseteq \mathbb{N}$$ that fullfills the pumping lemma and is not in RE and not in coRE. I've never constructed a language with a given constraint, I've only shown that a certain language satisfies a given one. Not wanting to waste a bunch of time guessing some languages and prooving that they meet my criteria, I am looking for a hint on how to start.


texts: Generate the context free grammar for the following language: $\left \{ a^{3n}b^{m}c^{n}|n>0, m>0\right \}$

texts:
Given the following language, I am tasked with giving a context-free grammar that generates it.
$\left \{ a^{3n}b^{m}c^{n}|n>0, m>0\right \}$
Would this be correct?
$A \rightarrow aaaA$
$B\rightarrow Bb | b$
$C\rightarrow Cc|c$
$S\rightarrow ASBSCS|\epsilon $


texts: A way to convert a binary tree into a grid

texts:
Wondering if there is a way to convert a binary tree into a grid such as this:

                    a
                  /   \
                 b     c
                / \   / \
               d   e f   g

                    or

                 d--b--e
                    |
                    a
                    |
                 f--c--g

                    to

                 d--b--e
                 |  |  |
                 y--a--x
                 |  |  |
                 f--c--g

An arbitrary sized binary tree. I'm not super familiar with binary tree properties so I am not sure if this would even be possible or if edge cases would prevent it from being possible.


texts:
I am to find the time complexity of my algorithm and I found one method here.
However I am really not sure about it correctness thus I would like to check it.
There is my algorithm (N is a set (len(N) is constant) and C is a number):

def f(N, C, k = 0):
    if C < 0:
        return 0
    if C == 0:
        return 1
    if not N:
        return 0
    i = 0
    for l in N:
        if l >= k:
            i += f(N, C - liczba, liczba)
    return i

And to my mind time complexity is equal to:
a+b+c+d+len(N)*C where a, b, c, d are constants.


texts: Fast search of local positive quadruples on the sphere

texts:
[redirected from math.stackexchange.com]

Let $U = \{u_{1}, u_{2}, \ldots, u_{n}\} \subset \mathbb{R}^{3}$ be the finite set of points on the unit sphere in $\mathbb{R}^{3}$: $||u_{i}||_{2} = 1$

Definition: Quadruple of points $(u_{i}, u_{j}, u_{k}, u_{l})$ is said to be positive if
$$
\exists \alpha_{i j} > 0, \alpha_{i k} > 0, \alpha_{i l} > 0: u_{i} = \alpha_{i j} u_{j} + \alpha_{i k} u_{k} + \alpha_{i l} u_{l}
$$

Definition: Positive quadruple $(u_{i}, u_{j}, u_{k}, u_{l})$ is said to be local relatively to the set U if $\nexists u_{s} \in U$ such that $(u_{s}, u_{j}, u_{k}, u_{l})$ is positive.

Question: Is there any fast algorithm to find all local positive quadruples in the given set $U$?

EDIT:
Of course, in worst case the complexity of the algorithm should be $\Theta(n^3)$, since there is an example when there are $\Theta(n^3)$ local positive quadruples.

But suppose that $u_{i}$ are taken from some real-world example, and they are distributed on the sphere somehow uniformly (~close to uniform).


texts:
Given language $L$, why is it not necessarily true that the number of equivalence classes of $L$ is equal to the number of equivalence classes of $L^R$?
And for the private case that $L$ is regular, is that true?


texts: Is there an accurate way to convert frequencies of the Stupid Backoff language model to probabilities?

texts:
We introduce a similar but simpler scheme, named Stupid Backoff, that does not generate normalized probabilities. The main difference is that we don't apply any discounting and instead directly use the relative frequencies (S is used instead of P to emphasize that these are not probabilities but scores)

That's a quote from the paper that introduces the Stupid Backoff language model. https://www.aclweb.org/anthology/D07-1090.pdf
I'm curious, is there an acceptable/accurate way to convert those frequencies into probabilities?
Frequencies are acceptable for prediction and ranking predictions by their likelihood, but it's not acceptable if you want to generate text with accurate probability distributions.
Is there an attribute of the algorithm that makes it such that normalizing the frequencies into probabilities isn't an accurate reflection of the probability dist


texts:
Given an undirected Graph. I want to find a hamiltonian path with no restriction to starting or ending vertices. I know there are some smart algorithms for solving that.
Now let's make things interesting: sometimes, when I arrive at a vertex, the edges connected to that vertex change. I.e. some will be removed, others appear. It is only depending on the edge I used before which egdes will change.
That means, if I go from vertex $v_1$ to $v_x$, edges connected to $v_x$ will change in the way $b_{1,x}$. if I arrived $v_x$ via $v_2$, edges will change in the way $b_{2,x}$ and so on.

I am looking for a efficient algorithm telling me if there is a hamiltonian path and output that if so. Has anybody ideas on how to approach that? Or has anyone an idea if this can be transformed into another better known problem?


texts: Comparison of two line segments along a ray

texts:
I have a point $q$, a ray $L$ (halfline which is cast from $q$) and two non-intersecting (intersection is only possible at endpoints) line segments $s_1, s_2$. I want to efficiently compute which of the two line segments along the ray $L$ is visible ("comes first").

I found the following description of a possible solution:

Why are at most five orientation predicates sufficient? I tried it on a few examples but can't convince myself fully.


texts: Can we find k shortest paths between all pairs faster than solving the pairwise problem repeatedly?

texts:
I want to produce $k$ shortest path ($k$ would be less than 10) between all pairs in a graph. The graph is (actually a subway map):

positively weighted
undirected
sparse
with about 100 nodes

My current plan is to apply $k$ shortest path routing to each pair; I am now looking for a more efficient alternative (possibly with dynamic programming).


texts: What do time complexity reductions prove?

texts:
I may have missed something in my classes - but with $A\leq_{P}B$... Does this show that, if $A\in \textbf{NP-Complete}$, that $B\in \textbf{NP}$ or $B\in \textbf{NP-Complete}$?

Or maybe I got things backwards. If $A$ is polynomial-time-reducable to $B$, and $B$ is $\textbf{NP}$-complete, does that make $A$ $\textbf{NP}$ or $\textbf{NP}$-complete?


texts: Tree search returning parents and children

texts:
I've a flat structure where a node references its parent instead of children

class Node(int Id, Node Parent, string Data);

Given a list of all nodes, and a search condition, I want to return the matches plus all ancestors and descendants

This what I'm trying to implement https://hshn.github.io/angular-ui-tree-search/

What would be a reasonably efficient algorithm to achieve this? I was aiming to build a tree as described here https://stackoverflow.com/questions/444296/how-to-efficiently-build-a-tree-from-a-flat-structure, and replicate the algorithm from the angular library above but it went over my head with all that OOP'ness


texts: I'm studying for my Computing languages test and there's one idea I'm having problems wrapping my head around, as far as I know for any Context Free Grammar (CFG), we can design a 2-state Pushdown Automaton (PDA). I am however a little bit confused that why this is possible.


texts:
I am looking for some sort of temporal logic for expressing invariants in interfaces. Since interfaces do not specify data representation, the invariants must rely solely on the publicly available functions of the interface.

For example, suppose we have a simple interface (Java style) Sum:

interface Sum {
    public void add (int a);
    public int getSum();
}

I want to express in an invariant that getSum returns the summation of a in all calls to add(a), without using any data representation of this sum.

The only way I can think of doing this is by using some form of temporal logic. Is there any literature on this subject available I can read? Any pointers would be much appreciated.


texts: What are the prerequisites for instruction pipelining to work?

texts: When can it be applied? When can it not be used? I get the general idea but not what it takes to make it work.


texts:
What is supposed to be the right result of an SCC algorithm running on a DAG.
should it return "no components" or "there are V components of size 1"?

I suspect it will return the latter (since it will start with the last sink, and then go back and mark each single sized vertex as a component, since each DFS will be of a single node before it can continue)

But is this a convention? E.g. if a treat SCC as a "great way to find if a graph has cycles" then I would expect it to return an empty result if there are none. e.g. components of size 1, who don't have a self-loop, don't really "go from A to A". is there a SCC variant that is more explicitly "find all groups that has cycles in them"? (e.g. is there a named variation)

Or what I'm looking for is basically "run SCC, then remove all components of size 1, and you got yourself a cycle detector, e.g. if after you do that you end up with no components, then your graph is a DAG"

Is there a name for that special SCC case? (assuming my understanding in the beginning of the question is correct)


texts:
For this question, I thought function F called twice but it called three times. Are those three functions were called? F(N), F(K) and F(N-1)?

How many times in this pseudo-code is the function F called?

Main
    Declare K as Integer
    K = 3
    Set Result = F(K)
    Write Result
End Program

Function F(N) as Integer
        If N == 1 Then
Set F = 1
    Else
        Set F = N * F(N - 1)
        Set N = N - 1
    End If
End Function


texts: How does the hardness of Subset Sum instances depend on their density?

texts:
The density of a Subset Sum instance $S = \{ s_1, \dots, s_n \}$ of size $n$ is defined as

$\qquad\displaystyle d(S) = \frac{|S|}{\log_2(\max_{s \in S} |s|)}$.

Why is the hardness of Subset-Sum dependent on its density?


texts: $\omega$-string avoiding a set of substrings

texts:
Given a set of strings $S$ over $\{a,b\}$. How to determine whether there is an infinite sequence consisting of ${a, b}$ (i.e., a $\omega$-string), which doesn't have any string in $S$ as a substring?
The total length of all substrings in $S$ is at most $20000$.


texts:
I was reading single pass in memory indexing and had few doubts.

Why is the time complexity of SPIMI O(T) where T are the token.
We know that before writing blocks to Disk, we have to sort dictionary terms. So, why don't we consider log(T) factor of it?

Also, if there is some data in memory then while performing sorting can we sort it in log(n) time if all of the main memory is exhausted?


texts:
So the question is : Is it theoretically possible to feed a neural network with some random values to expect an output since randomness is a lack of knowledge in most case.

For this question, I've got some examples.

First case, not a real problem?

We just throw a coin and get the result and we do that a whole bunch of times. For each throw, we get the initial condition (air pressure, force, etc.). Now we put all this data into the neural network for it to process.

My guess : The result is not really random since it only depends on the initial conditions so it's possible and the neural network will do a great job. So I guess that example is not a real problem since the "randomness degree" is weak.

Second case, questioning

Now, we generate a random list of number and sentences that correspond to each other so we have something like :

'zefvkbdl' -> 1613841.009
'nfeovhlzm' -> 963478.29
'jhgcjbklnsczl' -> 1.535953
'ergz' -> 9138630.26
etc ...

In a way that everything was randomdly generated (still, the list of sentences and number were not generated seperatly but each number was generated after a sentence and correspond to that sentence). In that case, is it possible to give a neural network the half of the list (the list can be forever long) and expect it to predict the other half with a great precision ?

My guess : It depends on the generation algorithm but let's pretend that a letter is just a particular index in an array and that the index was randomly generated. Since most of the time, numbers are randomly generated thanks to the digits of time (the last decimals that are changing extremely fast) I'm not sure of that - I guess it might be possible with an extremly powerful neural network to theoretically do that job.

Third case

Let's now be even more theoretical and consider it is possible to store somehow the global state of the universe at each moment of time. The only thing that is truly random at my knowledge is quantum mechanics so let's try it out.
At each point of time, we store the whole universe state and the outcome of measuring a quantum particle state (like the spin of an electron). Is it possible, after the biggest neural network training, to "predict" the outcome of measuring a quantum particle state knowing the state of the universe ?

Since I'm just a curious student, I don't have a lot of knowledge in neural network or quantum mechanics so I probably said a lot of wrong things and I'm sorry for that. I thank you for reading all of this and I hope someone is able to help me anwser or correct me.

Now, the real question I'm asking is : Do randomness truly exist ?


texts:
In decidability theory, I understand that if a problem is labeled "decidable", then we can construct a Turing Machine that definitively tells us whether an input is valid or invalid. My question is what does "undecidable" mean ? I read the "undecidable" applies to problems that have Turing Machines but cannot definitively tell us whether an input is valid or not(i.e. it outputs "yes" for valid inputs, and keep going for others indefinitely such that we will not know when, if ever, it will output anything). Then does "undecidable" applies to problems that can not be represented by Turing Machines at all, also? What is the difference between unsolvable and undecidable ?

EDIT:
I was reading my textbook(Introduction to Automata Theory, Hopcroft) and I ran into this: "Remember that showing there is no Turing machine at all for a language is showing something stronger than that the language is undecidable(i.e., that it has no algorithm, or TM that always halts"(pg 388). This seems to imply undecidable problems do not include ones without any TMs. Am I interpreting this correctly ?


texts: What is meant by an oracle separation between classes $\mathsf{BPP}$ and $\mathsf{BQP}$?

texts:
In these notes about quantum computation by Scott Aronson, he explains that the computation classes $\mathsf{BPP}$ is contained in $\mathsf{BQP}$, but that they are not equal, and

  So, the bottom line is that we get a problem -- Simon's problem -- that quantum computers can provably solve exponentially faster than classical computers. Admittedly, this problem is rather contrived, relying as it does on a mythical "black box" for computing a function f with a certain global symmetry. Because of its black-box formulation, Simon's problem certainly doesn't prove that $\mathsf{BPP} \neq \mathsf{BQP}$. What it does prove that there exists an oracle relative to which $\mathsf{BPP} \neq \mathsf{BQP}$. This is what I meant by formal evidence that quantum computers are more powerful than classical ones.

What does he mean by an oracle separation?

My understanding of an oracle for a Turing machine is one that solves the halting problem. Surely that can't be the case here?


texts: Expressing definite clauses (Horn rules, logic programming) in lambda terms?

texts:
There is paper which expresses lambda terms in the terms of logic programming http://www.cse.unt.edu/~tarau/teaching/PL/docs/dbx.pdf Is there conversion in the other direction - expressing definite clauses / Horn rules / logic programming sentences using the lambda terms and type calculus?

This question has the following context: definite clause grammars express its rules as definite clauses inside the logic programming formalism, but categorial grammars/type logical grammars use lambda calculus for their expression. Definite clause grammars have nice learnability (grammar induction) properties and algorithms - so - it would be nice to bring them to the culture of (abstract) categorial grammars/type logical grammars.


texts: Closest point in embedded simplicial complex

texts:
Suppose I have a simplicial $k$-complex $\mathcal S$ whose vertices are embedded in Euclidean space $\mathbb R^n$, for roughly $k< n\leq 6$. Examples include triangle mesh surfaces ($k=2$) embedded in $\mathbb R^3$ ($n=3$) and one-dimensional chains of line segments ($k=1$) in $\mathbb R^n$.
Given many points $\{x_i\}_{i=1}^M\subset \mathbb R^n$, is there a data structure/algorithm for efficiently answering closest point queries of the form $\min_{y\in\mathcal S} \|x_i-y\|_2$?
I'm looking for a generalization of methods that handle, e.g., closest point on a triangle mesh.  Pointers to existing implementations are also much appreciated!


texts:
Suppose there are sets $S\subseteq Q, T\subseteq Q$ such that $T=\epsilon (T),S=\epsilon (S)$.

  Prove $\epsilon(S\cap T)\subseteq S \cap T$

Definition of $\epsilon$- closure for epsilon NFA is:

  $\epsilon : 2^Q \rightarrow 2^Q $

  a) $S \subseteq \epsilon (S)$ Base case

  b) If $q \in \epsilon (S)$ then $\delta(q,\epsilon )\subseteq \epsilon (S)$ Recursive case

  c) and nothing else is in $\epsilon (S)$

  And also, S is a set of all states in epsilon-NFA.

My proof:

Is this a correct reasoning?


texts:
s = n
while (s > 4)
  s = s / 2
else
  s = s - 1

Let $T(n) = \Theta(S(n))$ where $S(n)$ is number of while-loop runs.

$S(n)=1 + S(n/2)$ if $n$ is even

$S(n)=1 + S(n-1)$ if $n$ is odd

$S(n)=0$ if $n \leq 4$

By converting n to a binary number, and I think

if $n < 2^k$, then $S(n) \leq k - 1$

I have come to this relationship, yet can't figure out how to approach to $\Theta $ bound.

Any help or guidance is appreciated.


texts: Proof that the following algorithm constructs a Minimum Spanning Forest (MFS)

texts:
I have this algorithm pseudocode:
Build-MSF-By-Add-And-Fix (G, w)
1  F = {} // empty set
2  for each edge e ∈ E, taken in arbitrary order
3      F = F ∪ {e}
4      if F has a cycle c
5          let e' be a maximum weight edge on c
6          F = F − {e'}
7  return F

I'm still trying to complete the proof for this but I'm not managing to connect all the dots.
Starting with a counterpart of the safe edge theorem, this is what I have:
Safe edge removal theorem: Given a graph with a single cycle, removing the edge with the maximum weight on that cycle results in a forest with the smallest total weight.
Proof: Since there is only one cycle, to create a forest, we need to remove only one edge from the cycle. Removing any edge that is not the largest from the cycle will result in a forest with a larger total weight. Q.E.D.
Claim: When Build-MSF-By-Add-And-Fix terminates, it will produce a Minimum Spanning Forest.
Proof: By induction on the number of edges inspected of this proposition:
Proposition P(k): “After k edges have been inspected (after k iterations), the graph F is a minimum spanning forest (MSF) of the graph G that contains only the edges inspected in line 2”.
Base k=1:
Induction P(k) => P(k+1)    (Assume P(k) is true and prove P(k+1) is true. There will be two cases to consider):
Case 1:
Case 2:
Conclusion: Use the above to conclude that F is correct when the loop terminates and the algorithm returns F:
I think I'm on the right track but I'm stuck trying to figure the remainder out.


texts: Flip-based algorithm for Delaunay triangulation in expected or average-case O(nlogn)

texts:
Focusing on the 2D plane:

Lawson's Flip Algorithm works in worst-case $O(n^2)$ flips. I have seen it mentioned that (other?) flip-based algorithms work in expected $O(nlogn)$ time for two dimensions. What is a simple example of an algorithm like this (perhaps with proof of complexity)? How would this be found?

Edit: If there are none in expected $O(nlogn)$, are there average-case $O(nlogn)$ flip-based algorithms?


texts: Best introductory "algorithms"/"more than just coding" comp sci book?

texts:
I've been programming in languages (C/C++/Ruby/Java/HTML) for some time now and am currently entering my senior year of high school. I'm taking AP Comp Sci, which uses Java, but want to have a better grasp of some of the more "math-y" concepts in computer science, like hashes/algorithms/etc. For someone who has done basic object oriented programming but doesn't know any of the algorithmic aspects of computer science (And wants to know them before he goes off to college), what books would you recommend that cover algorithms and the more mathematical stuff in a way that's easy for your rudimentary programmer to understand?

Some examples I've heard given are "Introduction to Algorithms" and "Structure and Interpretation of Computer Programs"; I was going to go with Introduction to Algorithms but it's around 80 dollars new, and I'm not sure if SICP has any of the algorithmic math I want to pursue. Haha, I guess all I'm asking for is personal opinions from people that have studied algorithm books and can give honest personal opinions.

Any and all feedback is appreciated; Thank you!

-Neil


texts: Human computing power: Can humans decide the halting problem on Turing Machines?

texts:
We know the halting problem (on Turing Machines) is undecidable for Turing Machines. Is there some research into how well the human mind can deal with this problem, possibly aided by Turing Machines or general purpose computers?

Note: Obviously, in the strictest sense, you can always say no, because there are Turing Machines so large they couldn't even be read in the life span of a single human. But this is a nonsensical restriction that doesn't contribute to the actual question. So to make things even, we'd have to assume humans with an arbitrary life span.

So we could ask: Given a Turing Machine T represented in any suitable fashion, an arbitrarily long-lived human H and an arbitrary amount of buffer (i.e. paper + pens), can H decide whether T halts on the empty word?

Corollary: If the answer is yes, wouldn't this also settle if any computer has a chance of passing the turing-test?


texts: Time Complexity of inserting a vector to a vector of vectors in C++

texts:
I was solving a question on LeetCode, where I had to generate all possible subsets of a given set of numbers.
Although, the solution makes sense to me, I am unable to understand the derivation of time complexity for those solutions.
A solution I found there was:
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> subs = {{}};
        for (int num : nums) {
            int n = subs.size();
            for (int i = 0; i < n; i++) {
                subs.push_back(subs[i]);  <---- LINE X
                subs.back().push_back(num); <---- LINE Y
            }
        }
        return subs;
    }
};

It is an iterative solution to solve the problem.
What I don't understand is the time complexity of the given solution and more importantly, the complexities of Line X and Line Y.
Does copying subs[i] take O(n) time and then pushing back take another O(n) time, or is it an O(1) step?


texts:
I am trying to understand this program and the respective forest. This is from the book Logic,Programming and Prolog by Ulf Nilsson.

Question:

In the main tree, why from ←off_gound(a) can you derive ⧠ ?
In the main tree, why was chosed on(b,a) first instead of on(c,b)?

Could someone please explain this?

Thank you so much in advance.


texts: Fine-grained versioning of entities in programming languages

texts:
I have a question related to design, implementation of programming languages. I hope it fits here and apologize if it doesn't.
All or most programming languages version modules (aka packages, libraries, crates). All the entities in a module (types, functions, variables and other information) share the same version with the module. However usually only some parts of a module change between a version and the next.
When two different modules use different versions of the same third module, this creates an incompatibility.

Some programming languages (for instance C and C++) ignore the problem altogether. They don't care about the version but only about the name and signature of entities. They accept programs that may crash or misbehave when executed, if different pieces of such programs expected different versions of a same entity that changed.

Other programming languages (for instance Rust or Node.js) trait different versions of the same entity as two completely different entities. This avoid crashes, but introduces unnecessary incompatibilities between entities that did not change.

This can be a big problem for modules that define many different entities and that lots of other modules depend on, for instance the standard library of a programming language. Most programming languages use special tricks for their standard libraries: for instance they tie the standard library's version to the compiler version and require to recompile everything when the compiler version changes.
A better solution to this problem could be versioning every entity independently instead of whole modules. The GNU implementation of the standard library of C and C++ do this. I have seen some Rust crates do this too by importing their previous version and re-exposing all the symbols that didn't change. But these processes are very tedious and easy to get wrong, hence very few pieces of software adopt similar practices.
Do we know of any good way to version entities in a fine-grained way?
Has there been any research on this problem?
A practical example
If the problem I described isn't clear, let me explain it with a practical example.
A module "time 1.0.0" defines loads of entities related to time. Among many others, it defines these two types:
type UnixTime   = uint32_t; # seconds from 1970 Jan 1
type UnixTimeNS = uint32_t; # nanoseconds from 1970 Jan 1

After "time 1.0.0" is out, we realize that UnixTimeNS is too small: it needs to be an uint64_t. We change that type and release "time 2.0.0" since we did an incompatible API change. Nothing else changed in the whole "time" module besides that UnixTimeNS type.
Two other modules "logger" and "totp" depend on "time". The former was developed on "time 1.0.0", while the latter uses "time 2.0.0". They both only use time::UnixTime and nothing else. This type did not change between the two version. But the compiler can't know that and treats time_1.0.0::UnixTime and time_2.0.0::UnixTime as different, incompatible types. It's now very hard to use both "logger" and "totp".
Imagine if they make a similar change to the standard library of any existing language: it could result in a tremendous split between new and existing modules, something as catastrophic as the switch from Python 2 to Python 3. All for a very minor change that affects 0.1% of the existing code.
I developed a rust crate (https://github.com/BlueNebulaDev/rust-version-test) and a Node.js package (https://github.com/BlueNebulaDev/node-version-test/) to show this problem in action. The names used in these projects differ from the ones in the example described here, but the meaning is the same.


texts:
First, I learned this based on these facts:

Turing machine (TM) will be define with 7-tuple Notation, $M=\langle Q,G,b,S,d,q_0,F\rangle$.
Any computation rules that can use to simulate any possible TM is called Turing-Complete.
Universal TM (UTM) is TM that is Turing-Complete.

Then, the question begins:

If we have 7-tuple Notation of any U that is UTM, Is there an algorithm to find initial tape content P that U to simulate any TM T with any I input(s)? If it exists, Does it based on each U or pattern of U? If it does, give me some example(s)? If it does, explain the algorithm?
Since all possible computations can be done with TM, Is there an algorithm to make TM simulate any algorithm P written in any language? If it exists, give me some example(s)?
If both questions above exist the algorithm, Why don't we just make a single UTM U and use it to program itself then do every possible computation?


texts: Decidability of $\lbrace \langle D \rangle \mid \text{$D$ accepts $a^kb^k$ for some $k > 0$}\rbrace$

texts:
I'm trying to understand decidable languages. In particular, I would like to show that
$$B = \lbrace \langle D \rangle \mid \exists k \geq 0 \,.\,\text{DFA $D$ accepts $a^k b^k$}\rangle.$$
I don't quite understand the process of proving these. I know that $a^kb^k$ is not regular, so then no DFA accepts it. I also know that $A_{DFA}$ (acceptance DFA) is decidable, I also know several other decidable languages like $E_{DFA}$ and $EQ_{DFA}$. How can I use these to prove that $B$ is decidable?

If no DFA accepts $a^kb^k$, doesn't that mean that $A_{DFA}$ will reject? So if $A_{DFA}$ rejects then shouldn't the decider for $B$ accept?


texts: How does IEEE 754 decimal encoding work?

texts: This may be a silly question, but if a computer works in binary how can you encript numbers using decimal?


texts:
I got an ILP Model where $c_i$ represents the starting time for a visit$_i$.
$c_i$ is already constraint by a number of constraints, one is $c_i > 0$.

I have now outside of my model 0 or multiple desired intervals for the visit$_i$, lets call them $dStart_{ik}$ and $dEnd_{ik}$ where k represents the k-th desired interval. i started by adding two variables per k: $desiredStart_{ik}$ and $desiredEnd_{ik}$.

I added the constraints

$desiredStart_{ik} >= dStart_{ik}$

$desiredStart_{ik} >= c_{i}$

$desiredEnd_{ik} <= dEnd_{ik}$

$desiredEnd_{ik} <= c_{i+1}$

$desiredDuration_{ik} <= desiredEnd_{ik} - desiredStart_{ik}$

with the last constraint, i get the problem if the intervals do not overlap, the $desiredDuration_{ik}$ gets negative. So I added a "helper" Variable $desiredHelper_{ik}$ to it so it looks like this:

$desiredDuration_{ik} <= desiredEnd_{ik} - desiredStart_{ik} + desiredHelper_{ik}$

The general problem of my model is a minimsationProblem, so I added these two terms to the target function:

$+100000 \sum_{i=0}^N \sum_{k=0}^N desiredHelper_{ik} -\sum_{i=0}^N \sum_{k=0}^N desiredDuration_{ik} $

With this formulation I see a problem, it favours solutions where the desired interval is closer by the actual solution.
Is there a better formulation? how could I avoid the $desiredHelper_{ik}$ variable?


texts: Greedy strategy for computing the minimum number of rays that hit all balloons

texts:
The minimum zap problem below is Exercise 11 in Jeff Erickson's lecture on "Greedy Algorithm".

  The minimum zap problem can be stated more formally as follows. Given a set $C$ of $n$ circles in the plane, each specified by its radius and the $(x, y)$ coordinates of its center, compute the minimum number of rays from the origin that intersect every circle in $C$. Your goal is to find an efficient algorithm for this problem. (See a "9-balloons-with-4-rays" example in the figure below)

  Question: Suppose it is possible to shoot a ray that does not intersect any balloons. Describe and analyze a greedy algorithm that solves the minimum zap problem in this special case.

I'm having trouble approaching this problem. I thought a greedy approach would be to use the ray that intersects the most circles and recurse, but I was told this was wrong. Why is this?

And what is the point of the fact that there is a ray that does not intersect any balloons? Am I supposed to prove that some optimal solution uses this fact?

Any help would be appreciated! I just recently started learning algorithms :)

Algorithm based off of hengxin's answer: https://cs.stackexchange.com/a/52293/42816

Proof by mathematical induction

Note: Did not use O( n log n) implementation

Now we will prove the correctness of this algorithm using mathematical induction. We will show that our greedy algorithm cannot do worse than the optimal solution.

Let $S'$ be the set of rays shot by our greedy algorithm. Let $S$ be the set of rays shot by another optimal solution.

Our base case is when $n = 1$. There is only one object to destroy, and our greedy algorithm uses 1 ray, which also happens to be optimal. So this checks out.

Now for our induction hypothesis, we will assume that our greedy algorithm is optimal for up to $n$ objects.

We now claim that the first ray from $\alpha$ of $S'$ cannot do worse than that of $S$.

Now let's consider an $n+1$ object situation. Then, we sort $S'$ and $S$ according to $\alpha$, clockwise. Now let's examine the first ray that occurs from $\alpha$ clockwise. In $S'$, this first ray, call it $R'$, cannot possibly do worse than that of $S$, call it $R$, because our greedy algorithm says that this ray will intersect the most objects, including the first one from $\alpha$. Therefore, $R$ either intersects just as much or fewer objects than $R'$. Thus, we can replace $R$ with $R'$ in the optimal solution $S$.

Now, we have to figure out if the rest of $S'$ is optimal, cutting out $R'$, which we'll call $T'$. However, since there are now at most $n$ objects, our induction hypothesis says that our greedy algorithm finds an optimal solution to $T'$. As such, the $R' + T'$ problem has an optimal solution from our greedy algorithm. Q.E.D.


texts: Compression algorithm using key value mapping

texts:
Would it be possible to do better than standard compression if you fed a bunch of zipped files through a machine learning algorithm that kept track of the most common bit sequences and produced a lookup map, with a heuristic for giving the longest / most commonly used sequences the shortest key values?
The compression algorithm would then go through a zip file and replace sequences from the map with their lookup key.  If the map was big enough (both compress / decompress parties would have access to it) could you reliably get a smaller file than the original?
Some doubts I have about this method:

Files your learning algorithm had never seen before wouldn't contain
many sequences that had been seen before
The keys would have to be smaller than the sequence of bits it
replaces in order to save space, maybe it quickly runs out of keys
smaller than common sequences
Zip files don't repeat bit sequences very often so we wouldn't be
able to find large pieces to replace


texts: Obtaining a set of $O(log n)$ classifiers using multiplicative weights algorithms

texts:
I'm trying to find an algorithm that uses the multiplicative weights algorithm to obtain a set of $O(logn)$ classifiers that classify a set $X=\{x_1, x_2, ...,x_n\}$ where the set of labels is $l \in\{0,1\}.$
The original question goes as follows:

Suppose we have a set $X=\{x_1,...,x_n\}$, each with a label $l_i\in \{0,1\}$, an hypothesis class $H$
and a learning algorithm $A$ that for every distribution $D$ on $X$ outputs a classifier $h\in H$, such that $P_{i\sim D}[h(x_i)=l_i]\geq 0.51$. Show an algorithm that produces a set of $T= O(log (n))$ classifiers $h^{(1)},h^{(2)},...,h^{(T)}$,  such
that the majority vote among these $T$ classifiers yields the correct label for all $1 ≤ i ≤ n$.

My idea was to use multiplicative weights where each example $x_1,...,x_n$ is an expert and the initial weight for each one is $w_i^{(1)}=1$, and $p_i^{(1)}=\frac{1}{\Phi^{(1)}}=\frac{1}{n}$, where $\Phi^{(t)} = \sum_{i=1}^n w_{i}^{(t)}$. In each iteration of the algorithm we run the learning algorithm $A$ and use the output $h$ to determine $\sum_{i=1}^n {p_i^{(t)}h(x_i)}$ and act accordingly just like in the classic multiplicative weights algorithm. We update the distribution of our experts $p_{i}^{(t+1)}=\frac{w_i^{(t+1)}}{\Phi^(t+1)}$ and their weight: $w_i^{(t+1)} = w_i^{(t)}e^{\epsilon l_i*h(x_i)}$ which means giving more weight to examples the classifier made an error on, and leaving the weights of correctly classified examples unchanged, thus increasing the probability of falsely classified examples to the point where their accumulated mass is at least $0.51\Phi$ and then we feed that new distribution $\bar{p}$ to the algorithm $A$ in the next iteration and the classifier we get will certainly be right on some of them. What I'm still struggling with is how do I know that at some point there's a majority among the classifiers produced so far that classify each example correctly?
Thanks in advance.


texts: Computational complexity of Bell numbers

texts:
I've been recently dealing with a problem which, when worst case is considered, results in exploration of $B_{n}$ options, where $B_{n}$ is th $n^{th}$ Bell number. I am trying to rigorously prove, that dealing with $B_{n}$ possible solutions results in exponential (or worse?) computational complexity (in terms of $n$). If possible, I would also like to prove this in the context of NP-hardness.

As I am new to this, any hints would be greatly appreciated.

So to summarize, given an algorithm, prove that it will take exponential (or worse) time in terms of $n$, when $n$ corresponds to $B_{n}$.

Thank you very much.