texts: Can this set of propositions be represented and proved in Haskell?

texts:
I used a set of natural language statements and their formalization  from  Gries and Schneider. I attempted to transform the propositions into Haskell equations. For example, for S0 : $a \land w \Rightarrow p$ the conjunction was split giving $a \Rightarrow p$ and  $w \Rightarrow p$ and then the contrapositive rule was applied giving  $\neg p \Rightarrow \neg a$ and  $\neg p \Rightarrow \neg w$. I then translated those propositions into Haskell conditional equations.

Is the Haskell representation a reasonable transformation?  Is there a relation between the execution of the Haskell expression not e a proof of theorem $\neg e$?

Natural language

If Superman were able and willing to prevent evil, he would do so. If Superman were unable to prevent evil, he would be ineffective; if he were unwilling to prevent evil, he would be malevolent. Superman does not prevent evil. If Superman exists, he is neither ineffective nor malevolent. Therefore Superman does not exist.

Formalize

$a$: Superman is able to prevent evil.

$w$: Superman is willing to prevent evil.

$i$: Superman is ineffective.

$m$: Superman is malevolent.

$p$: Superman prevents evil.

$e$: Superman exists.

S0 : $a \land w \Rightarrow p$

S1 : $(\neg a \Rightarrow i) \land (\neg w \Rightarrow \neg m)$

S2 : $\neg p$

S3 : $e \Rightarrow \neg i \land  \neg m$

module SUPERMAN where
 a::Bool
 w::Bool
 i::Bool
 p::Bool
 e::Bool

 a | (not p) = False  -- S0a
 w | (not p)  = False -- S0b
 i | (not a) = True   -- S1a
 m | (not w) = True   -- S1b
 p = False            -- S2
 e | (i || m) = False -- S3
-- Theorems (not e), (i || m), and (i && a) all hold


texts:
I’m having some troubles with Bellman Ford Algorithm in the following exercise
My guess is that at the end the algorithm should detect the negative cycle BD DF FG GB since B is decreasing at Vth (i.e. 7th) iteration. However changing the distance of the source does not make much sense to me. Is the source to be considered at fixed distance 0 or it can change as well as all the other vertices? Or is it correct to assume, as I did, that the algorithm will detect a negative cycle in the end?
Moreover, assuming to proceed with the computations, it is not clear to me the order I should follow. Being Vertex A not connected, should I go on relaxing from C (I guess not since it is not directly connected to B)? Or should I go on from D, which is the first vertex in alphabetic order directly connected to B?
Thank you


texts: Reducing Exact Cover to Subset Sum in practise!

texts:
The reduction of Exact Cover to Subset Sum has previously been discussed at this forum. What I'm interested in is the practicality of this reduction, which I will discuss in section 2 of this post. For you who are not familiar with these problems I will define them and show the reduction Exact Cover $\leq_p$ Subset Sum in section 1. For the readers who are already familiar with these problems and the reduction can move ahead to section 2.

section 1

The Exact Cover defined as follows:

Given a family $\{S_j\}$ of subsets of a set $\{u_i, i=1,2,\ldots,t\}$ (often called the Universe), find a subfamily $\{T_h\}\subseteq\{S_j\}$ such that the sets $T_h$ are disjoint and $\cup T_h=\cup S_j=\{u_i, i=1,2,\ldots,t\}$.

The Subset Sum is defined as follows:

Given a set of positive integers $A=\{a_1,a_2,\ldots,a_r\}$ and another positive integer $b$ find a subset $A'\subseteq A$ such that $\sum_{i\in A'}a_i=b$.

For the reduction Exact Cover $\leq_p$ Subset Sum I have followed the one given by Karp R.M. (1972) Reducibility among Combinatorial Problems

Let $d=|\{S_j\}|+1$, and let
$$
\epsilon_{ji}=\begin{cases}1 & \text{if} & u_i\in S_j, \\ 0 & \text{if} & u_i \notin S_j,\end{cases}
$$
then
$$
a_j=\sum_{i=1}^{t}\epsilon_{ji}d^{i-1}, \tag{1}
$$
and
$$
b = \frac{d^t-1}{d-1}. \tag{2}
$$

section 2

In practise (meaning for real world problems) the size of the Universe for the Exact Cover problem can be very large, e.g. $t=100$. This would mean that if you would reduce the Exact Cover problem to the Subsets sum problem the numbers $a_j$ contained in the set $A$ for the Subset Sum could be extremely large, and gap between the $\min\{A\}$ and $\max\{A\}$ can therefore be huge.

For example, say $t=100$ and $d=10$, then its possible to have an $a_j\propto 10^{100}$ and another $a_i\propto 10$. Implementing this on a computer can be very difficult since adding large numbers with small numbers basically ignores the small number, $10^{16} + 1 - 10^{16} = 0$. You can probably see why this could be a problem.

  Is it therefore possible to reduce the Exact Cover to Subset Sum in a more practical way, that avoids the large numbers, and have that the integers in $A$ are of a more reasonable size?

I know that it is possible to multiply both $A$ and $b$ by an arbitrary factor $c$ to rescale the problem, but the fact still remains that gap between possible smallest and largest integer in $A$ is astronomical.

Thanks in advance!


texts: Turing machine for which it is impossible to decide if it halts?

texts:
Assuming someone tries to approximate a function which decides if a turing machine halts or not. It uses only a finite amount of time. The function returns $0$ (=the turing machine halts), $1$ (=the turing machine never halts) or $2$ (=the algorithm could not decide if the turing machine ever halts). If it returns $0$ or $1$ the answer must be correct.

Of course there are (countable) infinite many calculatable functions which could be used for this. All those functions could be called $f_n(t_i)$ where $t_i$ is a turing machine.

For every $f_n$ there must be some $t_i$ for which the function is not able to decide if the turing machine halts or not.
\begin{align}
\forall n\in\mathbb{N}:\exists i\in\mathbb{N}:f_n(t_i)=2
\end{align}

One could then define a new $f_m$ which tries all previous defined $f_n$ and if one of the previous $f_n$ was able to decide if a turing machine halts it has the final answer. But of course this also does not work perfect, beause there are still some turing machines for which it is not possible to decide if they halt (otherwise the halting problem would be solved).

Then it is possible to say that a turing machine (or infinite many...) $t_i$ must exist for which all halting problem solver approximations $f_n$ must return $2$.

In words: A turing machine must exist for which it is not possible to decide if it ever halts or not. Is such a turing machine known? If not: why not? Or isn't it possible to find such a turing machine?

Thank you very much


texts:
In "Introduction to the Theory of Computation" by Sipser, Savitch's theorem is explained as an improvement to a naive storage scheme for simulating non-deterministic Turing machines (NTM). I am going to quote the text verbatim, because quite frankly I don't fully understand it (which is why I was unable to really ask my question in enough detail):

  We need to simulate an $f(n)$ space NTM deterministically. A naive
  approach is to proceed by trying all the branches of the NTM’s
  computation, one by one. The simulation needs to keep track of which
  branch it is currently trying so that it is able to go on to the next
  one. But a branch that uses $f(n)$ space may run for $2^{O(f(n))}$
  steps and each step may be a nondeterministic choice. Exploring the
  branches sequentially would require recording all the choices used on
  a particular branch in order to be able to find the next branch.
  Therefore, this approach may use $2^{O(f(n))}$ space, exceeding our
  goal of $O(f^2(n))$ space. (Sipser, "Introduction to the Theory of Computation" 334)

He goes on to describe Savitch's use of a subroutine called $CANYIELD$, a TM that decides whether some configuration $c_2$ is reachable from some other configuration $c_1$ in $t$ steps. It is recursively defined, so that $CANYIELD(c_1, c_n, t)$ results in two recursive calls $CANYIELD(c_1, c_m, t/2)$ and $CANYIELD(c_m, c_n, t/2)$, and so on until the "distance" between configurations is $0$ or $1$, or it is deemed unreachable. I think this can also be described as $STCON$ on a configuration graph of the TM in question.

So, there are two questions I have.

I understand how the size of each level and the depth of $CANYIELD$ results in no more than $O(f^2(n))$ use of space, but I don't understand how the intermediate configuration $c_m$ is found. Is this just not important given that all we care about is space? How do we know that the space used to obtain $c_m$ is negligible?
I don't understand why we need $2^{O(f(n))}$ space in the naive approach. Why can't we "forget" about branches we've executed, so that we are still using at most the space required to go all the way down one branch?


texts: What does the term "top-most" mean in the context of formal grammars?

texts:
I was learning about disambiguating grammars. In particular I was learning about enforcing right associativity on the sum language here:

$$ \mathit{Sum} ::= 0 \mid 1 \mid \mathit{Sum} + \mathit{Sum} \mid ( \mathit{Sum} )$$

I think I understand the intuition that in a string like:

$$ 0+1+0 $$

we want the 1 to be an argument to the left plus, so we put some sort of wall so that the symbol + cannot be right next to the 1. So something like this:

\begin{align}
\mathit{Sum} &::= \mathit{Ntp} \mid \mathit{Ntp} + \mathit{Sum}\\
\mathit{Ntp} &::= 0 \mid 1 \mid ( \mathit{Sum} )\end{align}

From my understanding this always enforces to put a parenthesis on the left side of any sum. Thus, putting a wall literally using the symbol (.

However, what I don't understand is that the 2nd rule is supposed to mean:

  Not top-most plus.

But I don't understand what "top-most" is supposed to mean. What does that mean?

Also, can someone give me a clearer argument to why the above grammar is indeed left associative? I feel my argument is a little to hand wavy or unclear to really be convincing.

Cross posted:

https://www.quora.com/unanswered/What-does-the-term-top-most-mean-in-the-context-of-formal-grammars


texts: Prove or disprove - graph doesn't exists

texts:
So, we have a directed graph G whose basis graph is connective.
I was asked to prove or disprove If its possible that for every DFS run on G, the output will be two trees containing all G vertices .
The only thing I could think of Is that graph like this cannon have a root (otherwise we could use DFS on the root and the output will be just one tree containing all G vertices).

Any Ideas?

thanks.


texts: Problem with determining the shape and direction of the Huffman Diagram

texts:
I have the phrase "abracadabra" and I want to encode it through the Huffman method. I first took the frequencies of each letters;
$$a=5$$
$$b=3$$
$$c=1$$
$$d=2$$
$$r=2$$
But I'm not sure as to how the diagram should look like. I made a few and some of them are correct. Also what determines the direction the branches take? Is there any fixed criteria for it?


texts: What is "Containment order"? Could I get a friendly explanation?

texts: Reading the Wikipedia page was a little dense for me. Can anyone offer a friendly explanation of what this means? It sounds like it saying that if you have two ordered collections, if they are "ordered by containment" then they will be in roughly the same order with each other?


texts: Does godel's incompleteness theorem still hold if we have a TM that can do an infinity amount of computations?

texts:
I have heard whisperings that if we have a turing machine that is allowed to compute infinitely many steps in finite time, then we can solve the halting problem.

This made me wonder, if we have such a TM, do Godel's incompleteness theorems then not hold anymore?

My intuition is: If the TM can make an infinite amount of computations, it can simply check the truth-value of any formula, by checking all natural numbers. e.g. if we have a formula $\forall x \phi (x)$, the infinite-TM can simply check for every natural number $n$ whether $\phi(n)$ holds.


texts: How is the complexity of algorithms to solve 3CNF (decision problem) specified?

texts:
For k inputs, the complexity of naive algorithm is O(2^k). I understood this one.

What is meant by "the size of the instance to be solved should be polynomial in k". Is it equivalent to the statement "The number of clauses in CNF of the boolean expression is polynomial in k"?

What should be complexity of a hypothetical efficient algorithm to solve decision version of 3CNF? Can it be called efficient if it is polynomial in the number of inputs and number of clauses?


texts: Transitive Closure vs Reachability in Graphs

texts:
I am facing the most curious situation with [my current information of] transitive closure algorithms. Specifically, is what follows not an algorithm for finding the transitive closure of a graph G(V, E) and is the time complexity not O(|V|+|E|):

Use Kosaraju's to compute SCCs (strongly connected components) -- O(|V| + |E|)
Create a DAG from the SCCs as (super)nodes -- O(|V| + |E|)
In a single supernode, reachability of all nodes is the same and equal to the union of the nodes in the containing supernode plus the reachable supernodes in the DAG -- O(|V| + |E|) to compute reachability in the DAG and O(|V| * |V|) total to compute reachability sets for all nodes

These reachability sets do constitute the transitive closure of the graph wholly, right?
But there aren't any O(|V| + |E|) transitive closure algorithms around.
What am I missing?


texts: Doing induction on recurrences correctly

texts:
I have $$T(n)=T(n-1)+n^{2}$$
And I know, by drawing the recursion tree that this is $\Theta (n^{3})$
However, if I try claiming that it's $O(n^{2})$ through induction:
$$T(n)\le c(n-1)^{2}+n^{2}\le cn^{2}$$
which evaluates to
$$c\ge \frac{n^2}{2n-1}$$
Which makes $c>0$ for all $n>1$ and concludes that the recurrence is $O(n^{2})$ which is not correct.
So what am I missing?


texts:
By definition, a parameterized problem $(Q, \kappa)$ is in $W[1]$ if it can be transformed into a combinatorial circuit $\varphi$ in polynomial time, such that the weft of $\varphi$ is 1.

On the other hand, $(Q, \kappa) \in A[1]$, if it can be transformed into a parameterized model checking problem $p$ -$MC(\Sigma_1)$.

Finally, $(Q, \kappa) \in W[1] \Leftrightarrow (Q, \kappa) \in A[1]$ holds.
However, I did not see why a parameterized model checking problem has to have weft 1. It occurs to me as if $W[1] \subseteq A[1]$.

Why are they the same class?


texts: Demonstrating that for every monotonic grammar there is an equivalent context-sensitive grammar

texts:
I'm trying to understand the equivalence in expressive power of formal grammars whose rules take the form:

$$ \alpha \rightarrow \beta $$ where $ |\alpha| \leq |\beta| $ (called a monotonic grammar), and grammars whose rules take the form:

$$ \alpha B \gamma \rightarrow \alpha C \gamma  $$

where $\alpha $ and $\gamma$ are strings of terminals & non-terminals or possibly empty, and $B$ and $C$ are single non-terminals. I understand that grammars of the second kind are already, by definition, grammars of the first kind, but I'd like to understand how to derive a grammar of the second kind, given one of the first kind (a monotonic grammar). Can anyone suggest a good reference for this? Many thanks in advance.


texts: In Paxos, what prevents multiple values from being chosen?

texts:
Say we have two proposers (P1, P2), one acceptor (A), and two learners (L1, L2).

What would prevent this sequence of events from occurring?

P1 initiates a round numbered 1. A agrees to participate, and reports that is has not voted on any proposals.
P2 initiates a round numbered 2. A agrees to participate, and reports that is has not voted on any proposals.
P1 asks A to vote for some value v1 in round 1.
A accepts v1 and tries to notify learners. L1 receives the message and declares that v1 is chosen.
P2 asks A to vote for some value v2 in round 2.
A accepts v2 and tries to notify learners. L2 receives the message and declares that v2 is chosen.


texts:
Imagine that I need to install my server in a remote location, so my algorithm can do something fancy (collocation of server at a financial exchange is how I thought of this question, but it applies more generally).

Imagine also I don't trust the people I am working with. They will have access to my server and I cannot be there to stop them from opening up the box and copying the disks.

Is there any way for me to hide the business logic of my algorithm from them, while maintaining that algorithm's functionality? In other words, can I encrypt my software and yet have it operate at the same time?

My feeling is no, since the software needs to speak in machine language, using the instruction set architecture, which is pretty standard. But CS is full of surprises so I thought I'd ask.

If the answer is yes, how do I do it? If the answer is no, are there any safeguards I can implement?


texts: How to use version vectors to decide which value to keep?

texts:
I am trying to understand how to build an eventually consistent KV store. It's just a learning experiment. Let's only consider one value which stores a fruits list.

We have 2 servers, 2 clients, N=2, W=1, R=1.

We start with an empty value and a zero version vector on both servers.

Server 1 and 2: ('', {'Client-A': 0, 'Client-B': 0})

Right from the beginning the updates do not reach all the servers like they should. Client A adds 'apple' and bumps the version vector, but the update only reaches Server 1. Client B adds 'banana' and bumps the version vector, but the update only reaches Server 2.

Server 1: ('apple', {'Client-A': 1, 'Client-B': 0})
Server 2: ('banana', {'Client-A': 0, 'Client-B': 1})

Now Client A reads from Server 2, adds 'mango' and bumps the version vector, but unfortunately the update only reaches Server 1. There are 2 candidates values and version vectors for Server 1.

('apple', {'Client-A': 1, 'Client-B': 0}) (existing value)
('banana, mango', {'Client-A': 1, 'Client-B': 1}) (proposed value)

According to the version vectors the proposed value is a descendant of the existing one, so there is no conflict and we take the proposed value.

Server 1: ('banana, mango', {'Client-A': 1, 'Client-B': 1})

We lost an apple. What am I missing?


texts: Why is DTIME(n) not equal to NP, and consequently, DSPACE(n) not equal to NP?

texts: Intuitively it would seem like these equalities are false since DTIME(n) and DSPACE(N) are in terms of deterministic Turing machines and NP is non-deterministic, but I'm struggling to come up with a convicing argument as to why this is. I'm assuming that both the Time and Space Hierarchy Thoerems must be used but I'm just not quite sure how. I'm hoping someone can lead me in the right direction.


texts: Can't Understand this Subset Construction Proof

texts:
This proof is from Introduction to Automata Theory Languages and Computation by Hopcroft & Ullman and is regarding a 'bad case' for subset construction.

The NFA which is being converted is as follows:

The argument for this then goes as follows:

  Consider the NFA N of Fig. 2.15. $L(N)$ is the set of all strings of
  $0's$ and $1's$ such that the nth symbol from the end is $1$.

  Intuitively, a DFA D that accepts this language must remember the last
  $n$ symbols it has read. Since any of $2^n$ subsets of the last $n$
  symbols could have been $1$, if D has fewer than $2^n$ states, then
  there would be some state $q$ such that D can be in state $q$ after
  reading two different sequences of $n$ bits, say $a_1a_2…a_n$ and
  $b_1b_2…b_n$.

  Since the sequences are different, they must differ in some position,
  say $a_i \neq b_i$. Suppose (by symmetry) that $a_i = 1$ and $b_i = 0$.
  If $i = 1$, then q must be both an accepting state and a
  nonaccepting state, since $a_1a_2…a_n$ is accepted (the $n^{th}$
  symbol from the end is 1) and $b_1b_2…b_n$ is not.

  If $i > 1$, then consider the state $p$ that D enters after reading $i - 1$
  $0$'s. Then p must be both accepting and nonaccepting, since $a_ia_{i+1}…a_n00…0$ is accepted and $b_ib_{i+1}…b_n00…0$ is not.

What's confusing me are these two lines,

  Since any of $2^n$ subsets of the last $n$ symbols could have been
  $1$, ...

and

  If $i > 1$, then consider the state $p$ that D enters after reading $i - 1$
  $0$'s. Then p must be both accepting and nonaccepting, since $a_ia_{i+1}…a_n00…0$ is accepted and $b_ib_{i+1}…b_n00…0$ is not.

I understand the case where $i = 1$, but I don't understand how the $i \gt 1$ works, and what they mean by any of the $2^n$ subsets being $1$. How can the subsets be $1$?


texts: Why Johnson’s algorithm for all pairs shortest paths may create negative cycle?

texts:
There is a contradiction in the Johnson’s algorithm presented in CLRS edition 3 page 700 that I can't understand.

Johnson’s algorithm uses the technique of reweighting, which works as follows: for each edge $(u,v)$ that may has a negative weight, a new weight is assigned which is as follow:

  Given a weighted, directed graph $G=(V,E)$ with weight function $w:E \rightarrow \mathbb R$, let $h:V \rightarrow \mathbb R$ be any function mapping vertices to real numbers. For each edge $(u, v) \in E$, define
  $\hat w(u,v) = w(u,v) + h(u) - h(v)$

The book in page 702 proves that $G$ has a negative-weight cycle using weight function $w$ if and only if $G$ has a negative-weight cycle using weight function $\hat w$.

On the other hand in page 702 it shows that for each $(u,v) \in E, \hat w(u,v) \geq 0$ .

Here is a my problem, how a negative-weight cycle of $G$ using $w$ weight function produces a negative-weight cycle using $\hat w$ weight function when it already has been proved that $\hat w(u,v) \geq 0$ for every edge $(u,v)$?


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

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

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


texts:
A few years ago, MapReduce was hailed as revolution of distributed programming. There have also been critics but by and large there was an enthusiastic hype. It even got patented! [1]

The name is reminiscent of map and reduce in functional programming, but when I read (Wikipedia)

  Map step: The master node takes the input, divides it into smaller sub-problems, and distributes them to worker nodes. A worker node may do this again in turn, leading to a multi-level tree structure. The worker node processes the smaller problem, and passes the answer back to its master node.

  Reduce step: The master node then collects the answers to all the sub-problems and combines them in some way to form the output – the answer to the problem it was originally trying to solve.

or [2]

  Internals of MAP: [...] MAP splits up the input value into words. [...] MAP is meant to associate each given key/value pair of the input with potentially many intermediate key/value pairs.

  Internals of REDUCE: [...] [REDUCE] performs imperative aggregation (say, reduction): take many values, and reduce them to a single value.

I can not help but think: this is divide & conquer (in the sense of Mergesort), plain and simple! So, is there (conceptual) novelty in MapReduce somewhere, or is it just a new implementation of old ideas useful in certain scenarios?

 US Patent 7,650,331: "System and method for efficient large-scale data processing " (2010)
Google’s MapReduce programming model — Revisited by R. Lämmel (2007)


texts:
Although I seriously code with computer languages in general since 2010 and as an amateur programmer with programming languages in particular since 2015 (primarily Bash and JavaScript imperative scripts) and codes I wrote are scattered through my Stack Exchange accounts, as in my Code Review SE account,
I think I still misunderstand what a Callback is;
I feel that the term itself might be misleading, as I understand that callback functions doesn't "call back" anything, but rather "called back" as a reaction to a condition (event).
I understand the alternative term Callafter as significantly controversial between programmers, so I stay with "Callback" or its semantic siblings;
Any Stack Exchange session I read about "Callback" contained answers that I either recognized as contradicting or controversial by other programmers commenting in comments.

My question

Because the particular examples I read of this concept in Bash and JavaScript are not remembered to me as clear, I ask:

  Does the callback concept of programming have any basis in computer
  science?

That is to ask; is there, as part of a computer science theory, some logical formula that can simulate all possible "callback functions" (similarly to as a Turing machine can simulate all possible functions of a computer) that might help understanding the purpose of this concept?
An answer might help me understand what is the common denominator (if there is one) between different "callback" terms in programming.


texts: Find an upper bound for a Linear Recurrence

texts:
Im having a hard time trying to figure out how to find an upper bound to the following recurrence:

$T(N)=T(N-1)+\mathcal{O}(n)$

where i know initially $N=\lfloor\tfrac{n}{logn}\rfloor$

I believe it can be solved as a linear recurrence, but i don't know how to put $n$ in terms of $N$.


texts:
I once asked why does computer data bits are usually organized on binary (base 2) sets, rather than on unary (base 1) sets, aiming to also understand why its not also ternary (base 3), heptary (base 7), ennary (base 9) or even decimal (base 10).
One programmer commented that Turing machines are always binary because the tape includes at least one stage to go to and at least one stage to go back to (or something of that sort; translating from Hebrew without knowing the professional terminology in English).
Must a Turing machine tape be binary? --- Can't it be unary in any situation?
Was there an attempt to create a "similar" model which is unary just for the sake of research (putting efficiency aside)?


texts: Algorithm to determine a set given the size of its intersection with sets you choose

texts:
I am competing in a programming contest where the submission phase can be stated abstractly as follows : There is a known universe set, $U$, and a hidden target $T \subset U$.  I submit $S \subset U$, and for feedback I am given $|S \cap T|$.

What is a good/optimal strategy for finding $T$ in as few submissions as possible given no assumptions on the distribution of $T$?  What are the complexity bounds in terms of $|U|$ and $|T|$?  In my application, $|U|$ is in the tens of millions and $|T|$ has a known size of around 5000.


texts: Convex hull partition of a set of points

texts:
Given a set $S$ of $n$ points in $\mathbb R^2$, denote by $\mathrm{convb}(S)$ the boundary of the convex hull of $S$. Let
\begin{align*}
S_1 &= \mathrm{convb}(S)\\
S_{i+1} &= \mathrm{convb}\left(S \setminus \bigcup_{j=1}^i S_j\right).
\end{align*}

Now $S_1,\ldots$ forms a partition of $S$. Is there an $O(n\log n)$ time algorithm for computing this partition?


texts: Showing if $A\in DSPACE(n^c) \text{ or } DTIME(n^c)$ then $EXP^A \neq EXP$ and $EXP^A= EXP$

texts:
If a language $A\in DSPACE(n^c)$, then $EXP^A\neq EXP$
  If a language $A\in DTIME(n^c)$, then $EXP^A= EXP$

What I tried:

Since it's impossible to show that $EXP \subseteq EXP^A$ because:

We know that $DSPACE(n^c)\subseteq  DTIME(2^{n^c})$
exponential functions aren't closed to composition
so from the above two, suppose we have a TM $M\in EXP$, such that M will simulate $A$ to compensate for not having a an oracle for A, this will yield a $O(2^{2^{n^c}})$ runtime.

It's true since simulating $A$ even an exponential amount will still be exponential since polynomials are closed to composition.


texts: Why can we write almost any nonzero 2-adic integer in the same form?

texts:
The title was difficult to formulate (I am open to suggestions). Two things bug me about this:

"is almost any" is imprecise, which goes against Volume 1's statement on definiteness.
When he writes, "in other words", this means Prof. Knuth explained it to me in two ways and I still do not understand it.

What is going on here in Plain English?

  If $x$ is almost any nonzero 2-adic integer, we can write its bits in
  the form  $$x = (\alpha01^a10^b)_2 $$

  in other words, $x$ consists of some arbitrary (but infinite) binary
  string of $\alpha$, followed by a $0$, which is followed by $a+1$
  ones, and followed by $b$ zeros, for some $a \geq 0$ and $b \geq 0$.
  (The exceptions occur when $x = -2^b$; then $a = \infty $)

  Consequently

  $$ \bar{x} = (\bar\alpha10^a01^b)_2 $$

  $$ x-1 = (\alpha01^a01^b)_2 $$

  $$ -x = (\bar\alpha10^a10^b)_2 $$

  and we can see that $\bar{x} +1 = -x = \overline{x-1}$, ...

  With two operations we can therefore compute relatives of $x$ in
  several useful ways:

  $x \mathbin{\&} (x-1) = (\alpha01^a00^b)_2$
  $x\mathbin{\&} -x = (0^\infty00^a10^b)_2$
  $x \mathbin{|} -x = (1^\infty11^a10^b)_2$
  $x \oplus -x = (1^\infty11^a00^b)_2$
  $x \mathbin{|} (x-1) = (\alpha 01^a11^b)_2$
  $x \oplus (x-1) = (0^\infty00^a11^b)_2$
  $\bar{x} \mathbin{\&} (x-1) = (0^\infty00^a01^b)_2$
  ...
  $((x|(x-1))+1) \mathbin{\&} x = (\alpha 00^a00^b)_2$

Knuth, Donald. The Art of Computer Programming. Volume 4, Fascicle 1. p. 8.


texts: When computing Monotone Polygon Triangulation, how do I store the formed diagonals in the DCEL?

texts:
It's my understanding that a DCEL have the following structs
public class Vertex{
  public Point Coordinate;
  public Edge IncidentEdge;
}

public class Edge{
  public Vertex Origin;
  public Edge Twin;
  public Face IncidentFace;
  public Edge Next;
  public Edge Prev;
}

public class Face{
  public Edge IncidentEdge;
  public List<Edge> edges;
}

If I go about determining the diagonals based on the type of vertex I'm at, how would I store the diagonal that was formed. Vertices can only store one incident edge. If I create a diagonal, any given vertex will have an additional incident edge. Do I just ignore this and just fix the half-edge pointers?
edit: The solution is to create new edges from the existing incident edges and create a new face for the new subdivision.


texts:
I got an amount of numbers, they are shuffled and represent the individuals.
For example (3,1,3,2,5,22,5) is one individual or (22,3,1,3,5,5,2).

Mutation is done quite easy by permutation within an individual.

The problem is to find a crossover method between 2 individuals, in which the quantity of the values stay the same(for the above example 2 times 3, 2 times 5, 1 time 22 and so on). I searched a lot on it but only found crossover methods for either unordered / ordered lists. Those for ordered lists seemed promising but they require that every value only occur ones.

Do you know a method to solve this problem or got an idea for altering an crossover for ordered list method like PMX?


texts:
I will state the complete question now, since it did not fit in the title.
Is the statement given below correct?

A necessary condition for a relation to be in 2NF but not in 3NF is that some non-prime attribute must be determined by a non-prime attribute or a set containing a non-prime attribute.

This is how I view the above statement:

Breaking the statement into parts:

A necessary condition for a relation to be in 2NF is that some non-prime attribute must be determined by a non-prime attribute or a set containing a non-prime attribute.
A necessary condition for a relation to not be in 3NF is that some non-prime attribute must be determined by a non-prime attribute or a set containing a non-prime attribute.

I will conclude that the statement is correct if and only if both the parts of the statement are individually correct.

Is my view of the statement correct?
If it is correct, then

Part two of the statement fails 3NF test, therefore making part two true.
Part one of the statement does not necessarily mean that the relation is in 2NF, therefore making part one false, because every non-prime attribute $A$ in $R$ may not be fully functionally dependent on every key of R.
So the statement should be false.

What I understand about necessary and what I understand about sufficient condition is this

A necessary condition is a condition that must be present for an event to occur. A sufficient condition is a condition or set of conditions that will produce the event. A necessary condition must be there, but it alone does not provide sufficient cause for the occurrence of the event. Only the sufficient grounds can do this. In other words, all of the necessary elements must be there.


texts: Are there programs that never halt and have no non-termination proof?

texts: Like black holes in computer science. We can only know they exist but when we have one of them we will never know it's one of them.


texts: How to prove that the Church encoding, forall r. (F r -> r) -> r, gives an initial algebra of the functor F?

texts:
The well-known Church encoding of natural numbers can be generalized to use an arbitrary (covariant) functor F. The result is the type, call it C, defined by
  data C = Cfix { run :: forall r. (F r -> r) -> r }

Here and below, for simplicity, we will assume that F is a fixed, already defined functor.
It is widely known and stated that the type C is a fixpoint of the functor F, and also that C is an initial F-algebra. For example, if the functor F a is defined by
 data F a b = Empty | Cons a b

then a fixpoint of F a is [a] (the list of values of type a). Also, [a] is the initial algebra. The Church encoding of lists is well known. But I could not find a rigorous proof of either of these statements (C is a fixpoint, and C is the initial algebra).
The question is, how to prove rigorously one of the two statements:

The type C is a fixpoint of the type isomorphism F C ≅ C. In other words, we need to prove that there exist two functions, fix :: F C -> C and unfix :: C -> F C such that fix . unfix = id and unfix . fix = id.
The type C is the initial algebra of the functor F; that is, the initial object in the category of F-algebras. In other words, for any type A such that a function p :: F A -> A is given (that is, A is an F-algebra), we can find a unique function q :: C -> A which is an F-algebra morphism. This means, q must be such that the law q . fix = p . fmap q holds. We need to prove that, given A and p, such q exists and is unique.

These two statements are not equivalent; but proving (2) implies (1). (Lambek's theorem says that an initial algebra is an isomorphism.)
The code of the functions fix and unfix can be written relatively easily:
 fix :: F C -> C
 fix fc  = Cfix (forall r. \g -> g . fmap (\h -> h g) fc )
 unfix :: C -> F C
 unfix c = (run c) (fmap fix)

Given a function p :: F A -> A, the code of the function q is written as
 q :: C -> A
 q c = (run c) p

However, it seems difficult to prove directly that the functions fix, unfix, q satisfy the required properties. I was not able to find a complete proof.
Is it easier to prove that C is an initial algebra, i.e., that q is unique, than to prove that fix . unfix = id?
In the rest of this question, I will show some steps that I was able to make towards the proof that fix . unfix = id.
It is not possible to prove either (1) or (2) simply by using the given code of the functions. We need additional assumptions. Similarly to the Yoneda identity,
 forall r. (A -> r) -> F r   ≅   F A   ,

we need to assume that the functions' code is fully parametric (no side effects, no specially chosen values or fixed types) so that the parametricity theorem can be applied. So, we need to assume that the type C contains only functions of type forall r. (F r -> r) -> r that satisfy the appropriate naturality law (known as "free theorem" after P. Wadler's paper "Theorems for free").
The parametricity theorem gives the following naturality law ("free theorem") for this type signature:
For any types A and B, and for any functions p :: F B -> A and f :: A -> B, the function c :: forall r. (F r -> r) -> r must satisfy the equation
  c (f . p) = f . c (p . fmap f)

Using this naturality law with appropriately chosen p and f, one can show that the composition fix . unfix is a certain function of type C -> C that must be equal to \c -> (run c) fix.
However, further progress in the proof does not seem to be possible; it is not clear why this function must be equal to id.
Let us temporarily define the function m:
 m :: (F C -> C) -> C -> C
 m t c = (run c) t

Then the result I have is written as
fix . unfix  = m fix

One can also show that unfix . fix = fmap (m fix).
It remains to prove that m fix = id. Once that is proved, we will have proved that F C ≅ C.
The same naturality law of c with different choice of p and f gives the strange identity
 m fix . m (m fix . fix) = m (m fix . fix)

But I do not know how to derive from this identity that m fix = id.


texts: Until quantifier of Computation Tree Logic

texts:
It's quite a short question: Refering to this Wikipedia article p U q means, that p has to hold at least until at some point q holds.

So, does it mean:

On each path starting from the current state p has to hold in each state until a state is reached in which q holds.
On each path starting from the current state p has to hold in any state before a state is reached in which q holds.

Example: Suppose p holds in s3 and q holds in s5. Let s0 be the starting state and the set of edges given by { (s0,s1),(s1,s2),(s2,s3),(s3,s4),(s4,s5) }. Let's assume p and q don't hold in all the other states. Is p U q satisfied, starting from s0?


texts: Can dynamic programming have n OPTimal subproblems?

texts:
I want to develop an algorithm which finds the optimal sequence of multiplications to multiply n matrices. For example, if we have:

M1 x M2 x M3 x M4 x M5 x Mn

The algorithm should place the optimal parenthesis to reduce overall number of scalar multiplications. For example, a possible output may be:

(M1 x M2) x (M3 x M4 x (M5 x Mn))

I realize we can place the parenthesis after finding an order for all of the multiplication (x) operators to operate in.

There is certainly a cost associated with each multiplication:

Cost (M1,M2) = rows(M1) x columns(M1) or rows(M2) x columns(M2)

At each step, if we find the subproblem associated with each (x) operator. For example, at the first step, we have:

OPT(do M1 x M2 first)
OPT(do M2 x M3 first)
OPT(do M3 x M4 first)
OPT(do M4 x M5 first)
OPT(do M5 x Mn first)

The problem is, that the number of OPTimal subproblems is not a fixed number. Normally, in a dynamic programming algorithm, we have a fixed number of OPT operations of which we take min or max of.

Is it valid to take n (variable number of) OPT operations in a dynamic programming algorithm?

P.S. I realize another feature of dynamic programming algorithms is the ability to memoize. We can certainly memoize since we will have repeated subproblems through different paths. For example, the following set of parenthesis can be approached through two different paths:

(M1 x M2) x (M3 x M4) x M5 x Mn

Do M1 x M2 first then do M3 x M4
Do M3 x M4 first then do M1 x M2


texts:
I have to construct PDA for ${ \{0^m1^n0^{2n} | n>0\}}$

So my idea is to (informally) not pushing anything into the stack while having 0s at first, then when automata start accepting 1s it should push X onto the stack twice on every 1 and then when start accepting 0s it should pop X once every time until stack will be empty.

Is my understanding correct? If not, how should I proceed?


texts: Proving that the clique cover problem is in NPC by reducing from k-coloring

texts:
Provided that we have to compare it against the graph coloring problem which is NPC. So far,
I can only think of connecting edges from a vertex in a provided graph to all the other edges it is not connected to then I separate the new graph g2, then I connect all the vertices that are not connected in the g2. And then I count the number of subsets. However it doesnt seem to work with a graph that requires four colors?


texts: Minimum spanning tree of a connected induced subgraph

texts:
I'm doing an online course in which I'm struggling with the following multiple-choice question:

Suppose $ T $ is a minimum spanning tree of the connected graph $ G $.
Let $ H $ be a connected induced subgraph of $ G $. (I.e., $ H $ is
obtained from $ G $ by taking some subset $ S \subseteq V $ of
vertices, and taking all edges of $ E $ that have both endpoints in $
> S $. Also, assume $ H $ is connected.) Which of the following is true
about the edges of $ T $ that lie in $ H $? You can assume that edge
costs are distinct, if you wish. [Choose the strongest true
statement.]

For every $ G $ and $ H $, these edges form a minimum spanning tree of $ H $
For every $ G $ and $ H $, these edges are contained in some minimum spanning tree of $ H $
For every $ G $ and $ H $ and spanning tree $ T_H $ of $ H $, at least one of these edges is missing from $ T_H $
For every $ G $ and $ H $, these edges form a spanning tree (but not necessary minimum-cost) of $ H $

I don't understand why option 4 is not correct; the hint given is as follows:

Suppose G is a triangle and H is an edge.

Suppose that G is a triangle with nodes 1, 2, and 3, all connected, and we choose the subgraph H from nodes 1 and 2, thus including only the edge (1,2). That edge then forms a minimum spanning tree of those two nodes, no?
Incidentally, the answer

For every G and H, these edges for a minimum spanning tree of H

is also incorrect.


texts: For a Turing Machine $M_1$, how is the set of machines $M_2$ which are "shorter" than $M_1$ and which accept the same language decidable?

texts:
I wonder how come that the following language is in $\mathrm R$.

$L_{M_1}=\Bigl\{\langle M_2\rangle \;\Big|\;\; M_2 \text{ is a TM, and } L(M_1)=L(M_2), \text{ and } |\langle M_1\rangle| > | \langle M_2 \rangle| \Bigr\} $

(I know that it's in $\mathrm R$ since there's an answer for this multi-choice question, but without explanation).

I immediately thought that the $L_{M_1} \notin \textrm{co-RE} \cup \textrm{RE}$  since we know that checking if two machines accept the same language is really not decidable, I came to think: is it immediate "False", but it can't be since there's a lot of Turing machines who accepts the same answer and have different codings.

Thanks!


texts: how to compute order statistic for union of sorted arrays?

texts:
I'm not sure why this solution holds:

http://www.zrzahid.com/kth-smallest-element-in-two-sorted-arrays/

  For example, $A=[1, 1, 2, 3, 10, 15]$ and $B=[-1, 2, 3, 4, 6, 7]$ then *k=8*th smallest element would be 4 as it appears in 8th position of the merged sorted array=$[-1, 1, 1, 2, 2, 3, 3, 4, 6, 7, 10, 15]$.

  A trivial solution would be to do a merge operation as we do in merge phase of the merge sort while increasing a counter whenever we chose an element in the merge phase (i.e. when we increase one of the marker index). This guarantees $O(k)$ time solution. Can we do better?

  As both the arrays are sorted so in best case scenario when both arrays are identical then kth element in the merged array would be k/2 the element in one of the arrays. If they are not identical then kth element will reside in one of the 2 partitions of one of the sorted arrays. This signals us that we could discard searching in some partitions. How? Of course we can try binary search over two sorted arrays.

    We can try to find two mid point index i and j in the two arrays respectively such that A[i] falls in between B[j-1] and B[j] i.e.
    $B[j-1] < A[i] < B[j]$. Notice that this guarantees that A[i] is
    that (i+j+1) th smallest element because there is exactly j elements
    in B less than A[i] (because $A[i] > B[j-1]$) and there are exactly
    i elements in A less than $A[i]$. So, if we want to find kth smallest element then we need to find middle element $A[i]$ and $B[j]$
     maintaining the invariant that $i+j+1 = k$.

    $i + j = k – 1$

    Also note that if we have $A[i] > B[j]$ then we know that kth smallest can't be in $A[i+1..]$ or in $B[..j]$. So we can discard
    these two halves. This guarantees logarithm search time. Also, note
    that if $A[i] > B[j]$ then we are already discarding elements in $B[..j]$
    which are smaller than kth smallest. So, we arrive the following
    conclusions -

      $A[i] > B[j]$ left partition of B are smaller and right partition of A are greater than kth smallest.
       Discard $A[i+1..r1]$ and $B[p2..j]$
       Update $k = k-(j-p2+1)$ as we are discarding smaller elements in $B[p2..j]$
       Otherwise left partition of A are smaller
         and right partition of B are greater than kth smallest.
       Discard $A[p1..i]$ and $B[j+1..r2]$
       Update $k = k-(i-p1+1)$ as we are discarding smaller elements in $A[p1..i]$

I understand 99% of this. To find the $k$th smallest element, just try to find an $A[i]$ such that $B[j-1]<A[i]<B[j]$ such that $i+j=k-1$.

So from here on out, let $i+j=k-1$ be the constraint.

What I DON'T understand is why, if $A[i]>B[j]$, then we keep $A[i]$ as a possible candidate for the $k$th largest element. In the algorithm from the link, he says to keep $A[0,...,i]$ and $B[j+1,...]$.

I don't know why we don't keep $A[0,...,(i-1)]$ instead of $A[0,...,i]$. If $A[i]>B[j]$, then $A[i]$ is greater than or equal to $j+1$ elements in $B$ along with $i$ from $A$, thus it won't be the $k$th smallest element since $(i+j+2)>k$.

And I tried to implement this algorithm, my implementation only works when I keep $A[0,...,i]$ and not $A[0,...,(i-1)]$. I simply don't understand why we keep $A[i]$ when it clearly cannot be the $k$th smallest element when $A[i]>B[j]$.

Any thoughts? I don't see where I'm wrong here.


texts: Does consensus require a turing machine?

texts: Can we achieve consensus (paxos, zab, etc.) without using a turing machine? What's the least powerful machine we can use to achieve consensus?


texts:
A surprising number of problems have fairly natural reductions to linear programming (LP). See Chapter 7 of [1] for examples such as network flows, bipartite matching, zero-sum games, shortest paths, a form of linear regression, and even circuit evaluation!

Since circuit evaluation reduces to linear programming, any problem in $P$ must have a linear programming formulation. Therefore, we have a "new" sorting algorithm, via reduction to a linear program. So, my questions are

What is the linear program that will sort an array of $n$ real numbers?
What is the running time of the reduce-to-LP-and-solve sorting algorithm?

Algorithms by S. Dasgupta, C. Papadimitriou and U. Vazirani (2006)


texts: The optimal way to find leaves in a weighted full binary tree

texts:
Let T be a full binary weighted tree. For a node v in T, the cost of going right is a i.e w(v, v.right) = a while w(v, v.left) = b

How do I find optimal paths to all leaves from the root. I don't think classical graph traversals are helpful in this context as I don't need to visit all nodes.


texts: Intuition for PH notation in Arora-Barak's Computational Complexity

texts:
For the definition of polynomial hierarchy:

$x \in L \Leftrightarrow \exists u_1 \in \{0, 1\}^{q(|x|)}\forall u_2 \in \{0, 1\}^{q(|x|)} \cdots Q_i u_i \in \{0, 1\}^{q(|x|)} M(x, u_1, \ldots, u_i) = 1$

What does the notation of $M(x, u_1, \ldots, u_i)$ mean? The definition used for $\mathcal{NP}$ is $M(x, \alpha)$ where $\alpha$ is the certificate. What is the intuition for what the $u_i$ signify in terms of the TM $M$?


texts: Are there algorithms with proven upper bounds but no proven lower bound (above constant time)?

texts:
One of my professors mentioned such algorithms exist but could not think of any offhand. Obviously any algorithm will be at least $\mathcal{O(1)}$, but are there algorithms not yet proven to have a lower bound greater than this, which do have a proven upper bound?

I'm interested in both problems and algorithms, but in either case practical examples (if they exist) as opposed to artificial ones.


texts: Find out an algorithm that finds out if an undirected graph contains even length cycle or not using BFS?

texts: I know how to find odd length cycles(a bipartite graph cannot have odd cycles) but I cannot manage to make an algorithm when considering even length cycles.


texts: Why CFG can specify structure of sentence but Regular grammar cannot?

texts: CFG can specify structure of sentences but Regular grammar can only specify strings sequentially. Is it because DFA has only one bit memory?


texts: Need Help Understanding Proof by Contradiction for Halting Problem

texts:
I understand what the halting problem describes, but I do not understand how the proof by contradiction associated with it proves that it is impossible to solve.

The proof by contradiction can be defined as having a function Halt() which could determine whether a program will halt. One could then call this function in a program called Program and halt if the program halts or otherwise loop forever.

Program (String x)

If Halt(x, x) then
 Loop Forever
Else Halt.

END

What I don't understand is why if Halt() returns true that it has to Loop forever. Why can't the Program return 0 or 1?

Thanks


texts: Polynomially many times launch $NL$ machine - is it in $NL$? On example of ACYCLIC

texts:
Lets consider $$ACYCLIC = \{\langle G \rangle | G \text{ is acyclic}\}$$
We are going to prove that $ACYCLIC\in NL$. I know that the easiest approach for this task is to use the fact that $coNL=NL$. However, I wonder if correct answer is following approach:

The idea is to check each existence of each length of cycle. Let $n$ will be number of cycles.

    for l = 1..n
       is_cycle = non-deterministally check if there exists cycle of length l
       if (is_cycle == "yes")
          then return "no"
    return "yes"// graph is acyclic because there is no cycle of length 1..n

Is it correct approach in $NL$?


texts: What are the pros and cons of RANSAC versus Hough Transform?

texts:
A friend needs to find the pool balls in an image of a pool table. Would a Hough transform be a good idea? Why/why not? Would RANSAC be better?

The question comes from this study guide (http://www.cc.gatech.edu/~afb/classes/CS4495-Spring2015-OMS/), is not homework, and I am not currently taking this class.

What I know: RANSAC is least-squares plus a system with voting. We pick the least squares solution that has the least outliers. Hough transform is about finding parametric shapes. You can transform something into Hough space. For a circle you might want to know the radius. If you know more information about your circle (the pool ball) you'll not have as much space to search.

I think it makes sense to use Hough transforms in the case of finding pool balls so I am wondering how and why you'd even use RANSAC.

Edit: I think you could use RANSAC if you had another image to match to that you knew had pool balls in it. The images would be matched against each other, and the features that came out would be the pool balls. But again, it seems like RANSAC isn't a good idea because it could only fit one model to the whole image.


texts: Besides practical computing applications, is there a reason polynomial is "good" and exponential is "bad"?

texts:
The overarching theme of computer science seems to be that polynomial time or space or what-have-you for an algorithm is a success, and exponential is a failure. The definitions of P and NP revolve around this. This seems to be the case in OMBL (online mistake-bound learning) as well.

On the other hand I heard from a respected machine learning expert that in big data processing, O(n) algorithms (such as k-grams) really are the only that work, because n is very huge for modern, real industrial corpuses in high tech, finance, etc.

Are there fundamental theoretical reasons for the divide between polynomial and exponential, or is it motivated entirely by what can run on a real computer in a normal amount of time?


texts: rendezvous vs normal synchronous send and receive

texts: From what I understand, rendezvous is a message-passing technique where both the sender and receiver are blocking (synchronous) and the receiver acknowledge the send in a binary handshake between them. What I fail to understand is the difference between the regular synchronous mechanisms and the rendezvous. Can someone help me understand this point?


texts:
I'd like to know if there is a function $f$ from n-bit numbers to n-bit numbers that has the following characteristics:

$f$ should be bijective
Both $f$ and $f^{-1}$ should be calculable pretty fast
$f$ should return a number that has no significant correlation to its input.

The rationale is this:

I want to write a  program that operates on data. Some information of the data is stored in a binary search tree where the search key is a symbol of an alphabet. With time, I add further symbols to the alphabet. New symbols simply get the next free number available. Hence, the tree will always have a small bias to smaller keys which causes more rebalancing than I think should be needed.

My idea is to mangle the symbol numbers with $f$ such that they are widely spread over the whole range of $[0,2^{64}-1]$. Since the symbol numbers only matter during input and output which happens only once, applying such a function should not be too expensive.

I thought about one iteration of the Xorshift random number generator, but I don't really know a way to undo it, although it should theoretically be possible.

Does anybody know such a function?
Is this a good idea?


texts: Algorithm to cut a sphere in half with a plane and maximize the number of points on the sphere surface on one side of the plane

texts:
Consider a sphere with a coordinate system like the earth. There are $N$ points on its surface at random positions. For all the infinite planes that cuts the sphere exactly in half (i.e. the sphere's center is on the plane), given the set of $(latitude, longitude)$ of the points, find the global maximum number of points that might exist on one side of the plane.
Things I've tried:

Calculate the sum of all vectors from sphere center to the points, then use the plane perpendicular to the sum vector as the target plane; I think exceptions exist
use the plane's equation $ax+by+cz+d=0$, the constraint that the sphere center is on the plane, and another inequation to do a linear programming; I haven't figured what the inequation should be, my first thought is that we maximize the algebra sum of distances between the points and the plane but this seems to have added some sort of weight to different points while in the final result all points are equal
Select all pairs of points $\{p1, p2\}$ from the point set and form a plane with the sphere center, then calculate how much points are on each side and add 2 to the larger side; this should be a doable way but it is $O(n^3)$

Is there a better method to solve it efficiently?
Edit: one exception for method 1
For sphere $s$ and a plane $p$, draw a line $l$ perpendicular to $p$ and goes through the sphere center $C$, assume $l$ meets the sphere surface at point $A$ and $B$. Put 3 points close enough to $A$ and centrosymmetric to $l$. Put another 2 points on the $B$ side of the plane close enough to the plane and centrosymmetric to $l$. In this case, the sum vector will be $3\vec{CA}$ so $p$ is what we are looking for which is obviously not correct. If we tilt $p$ by a little, one of the points on the $B$ side can be included.


texts:
What is the name of the tree data structure where node weight equals the sum of all descendant nodes' weights?

Example:

      15
    /    \
   10     5
  /  \   / \
 2    8 1   4


texts: Decision version of the traveling salesman problem and NP-hardness

texts:
Wikipedia says:

  The problem has been shown to be NP-hard

and

  the decision problem version ("given the costs and a number x, decide
  whether there is a round-trip route cheaper than x") is NP-complete.

How can the "non-decision problem" version be NP-hard? Doesn't this class contain decision problems, by definition? Is this some sort of abuse of notation? Are they just being overly flexible with the definition of NP-hard?


texts: Determine whether removing a node on a graph will disconnect the graph

texts: I have an undirected unweighted graph with a single component. I want to know if removing a given node will disconnect the graph. I know that I can remove the edges to the node and then use DFS to get the number of components, however this seems rather inefficient as I need to check all vertices in the graph for this. Is there a faster way to do this?


texts: Total number of bits of storage for direct mapped cache

texts:
I have a homework assignment dealing with caches. We are asked to compute the total number of bits of storage required for the cache, including tags and valid bits. Then compute the overhead for the cache incurred by the tags and valid bits.

Info given: Consider a direct-mapped cache with 16KBytes of storage and a block size of 16 bytes. Assume that the address size is 32 bits.

So I've done the calculation and get a total number of 32 bits required. We were given the following formula:

(bits/tag) + (bits/index) + (bits/block offset) = total number of bits

I am unsure about my number of sets.
I did this by:

16 byte blocks is 2^4, so 4 bits for block offset
2^32 / 16 bytes per frame gives us 2^28 blocks
2^28 blocks / 65536 sets gives us 2^12 blocks/set, so we need 2^12 unique tags
Add them together: 12 (bits/tag) + 16 (bits/index) + 4 (bits/block offset), which gives us 32 bits

I got my number of sets from 2^size, which is 2^16.

The second issue I'm running into is now calculating the overhead, given those numbers.

We were provided the formula

(Address size - bit offset - bit block offset) * number of frames = kbits of tags

When doing this, I get the following:

(32 - 16 - 4) * 65536 = 12 * 65536 = 786432bits
= 786432bits / 1024 = 768 KBits
= 768 * 0.125 = 96 Kbytes
= (96KBytes / 16KBytes)
= 600% overhead

Which obviously does not make sense.

I believe my issue is the number of sets, but from what I can gather from online and our lecture notes, the number of sets (in a direct-mapped cache) is equal to the size of the cache, so that would be 2^16, so 65536.

We have lecture notes that describe how to do this, but they were with 8byte blocks and we were told the number of sets (in the case of the notes, the size was 256, which is 2^8, which I can only presume is 2^block size).

Any insight will be of help!


texts: Multi-threading : N cores = N times one core?

texts:
This question is about modern CPU architectures and multi-threading. I'm mainly interested in personal computers or servers having 2, 4, 8, 16... cores like for example an Intel core i7. I mean not a NASA supercomputer or GPU vector processing.

You have N cores.

You write an algorithm in a low level language such as C, C++, Java, C#... using essentially arithmetic (+/x/and/or...), basic for loops, floating point and arrays. It is mono threaded and your algorithm takes say 1 minute to complete.

Now you start N threads, and run the same algorithm on each of these threads INDEPENDENTLY : no lock (semaphores) or write access to common objects. Does each thread take 1 minute to complete, so that the total running time is 1 minute ?

What prevents this from being as good as it ? I know for example that if the threads write on the same parts of the memory (even without needing locks), the CPU caches of each processor need to refresh and the whole thing can be slowed down a lot.

Do you know some of the classical cases where the situation might be significantly different from "each thread one minute" and explain what about the architecture causes this ?

Note : Intel (for example) often uses hyperthreading so that 4 cores appear to be 8 logical processors. I don't want to focus on hyperthreading and I would like to simplify my question as if hyperthreading didn't exist. Imagine that each core can process the instructions of a single thread at a time.

I'm of course interested by things I might not be aware of in modern CPU architecture.


texts: Given an array of size n, create a sub array with given conditions using dynamic programming

texts:
We are given an array of integers of size n, which is not necessarily sorted, and we want to create a sub array. We are allowed to do one of 3 tasks below in each level:
1. skip the number in original array and go to the next
2. insert the number in the start of the sub array
3. insert the number in the end of the sub array.
And at last we want the sub array to be the longest one that can be created with the conditions above and sorted.
For example we have A={10,3,13}
now we can insert 10 in the beginning, then 3 at the beginning and finally insert 13 in the end.
so the size of sub array is 3.

I know that I must solve this using dynamic programming but I do not know how to do it exactly.


texts: Representation of 8-Puzzle for (A*) Search Algorithm in C

texts:
I am trying to complete CS50's hacker edition pset3, where you have to make a program that will solve the game of eight or fifteen from its current state, this must be written in C.
https://en.wikipedia.org/wiki/15_puzzle

I first tried an approach of straight going for the step that get's you closest to the goal, but found it got caught in a loop. So I added a condition of not repeating the last move which just led to a longer loop!

I am going to need a search algorithm, and have researched and now understand some of the main ones. I think breadth or depth first would be too computationally expensive on larger boards and so, as the specification recommends I am going to try A* search. Manhattan distance works easily for the heuristic as it is admissible and no. of moves from initial state for g(state).

However I am struggling mainly with the open and closed sets. So these must have the cost amount, but what representation of the game moves for that state? The whole board? But then how do you keep track of moves to get to that board for the final solution? I thought about having a massive array of like 200 to store the moves list, but for so many nodes this would be crazy. So how is the best way to represent the system and process of the game in a way that I can implement the search algorithm?

Many thanks


texts: Calculating the probability of data loss of a RAID 1+0 system

texts:
I have a task where a RAID 1+0 system (A RAID 0 connects two RAID 1's with two disks each = makes 4 disks in total) is given with no further details. Then let p be the probability that one disk shows signs of failure. The variable p is not further defined.

Now I've received the task to calculate the probability that there will be a data loss in this RAID 1+0 system and I have literally no idea how solve this. I know that RAID 1+0 systems can cope with failure of the 1st and 3rd disk without having any data loss.

Please enlighten me, thanks!


texts:
When dealing with caches, the address is split in three parts - offset, index and tag. Question is: if we are given a word address, do we first have to shift left by 2 bits by adding 00 at the end of address?

Suppose cache block size is 4 . block offset is 2 LSBs of the address. If we were to add 00 at end of every memory address, then block offset would always be 00. That means, we could never have access to any other byte rather than one at position 00 in our block?


texts: Scheduling distributed computational graph

texts:
I work in computational fluid dynamics. And I spend most of my time waiting for simulation to complete.

The common way to improve simulation performance is to use a suitable distributed linear algebra library, a big computer with Infiniband, tweek some parameters and hope for the best.

Most of my simulations can be seen as many iterations of a single big "computational graph" of mul/div/add, without a single branch. It seems that finding a optimal scheduling for this computation could be seen as a optimization problem.

The absence of branch, the complete knowledge of the architecture (Memory hierarchy, number of functional units, communication interface...) and the fact that the same graph will be used many time make me think that some very aggressive optimization could be done ahead of time.

As some work been done in computer science to find a optimal scheduling for a "computational graph" and a given architecture?


texts: Number of submatrices, of a base matrix derived from an array, with a particular sum

texts:
Given an N sized array A of unsorted integers and an integer K, derive a square matrix M of order N where $ M_{ij} = A_i * A_j $, and return the number of sub matrices of M where the sum of all of its elements is K.

Example:

$A = \begin{Bmatrix}1&-1\end{Bmatrix}$
$K = 0$

Thus:
$M = \begin{Bmatrix}1 & -1\\-1 & 1\\\end{Bmatrix}$

So, there are 5 submatrices where the sum of its elements is 0:
$ M_{00}...M_{01} = 1 + (-1) = 0$
$ M_{10}...M_{11} = (-1) + 1 = 0$
$ M_{00}...M_{10} = 1 + (-1) = 0$
$ M_{01}...M_{11} = (-1) + 1 = 0$
$ M_{00}...M_{11} = (-1) + 1 + (-1) + 1 = 0$

Brute force is obvious and it costs $O(n^4)$, but I'm looking for a less naive solution. The first thing that comes to mind (at least mine) is two pointer algorithm, but it works only when there are no negative members, which is not the case. If it were it would make this question a duplicate of this one.

I believe there is a smarter way to solve this because of the correlation between M and A, but I can't figure out how.


texts:
I am reading about the Maximum Flow Problem here. I could not understand the intuition behind the Residual Graph. Why are we considering back edges while calculating the flow?

Can anyone help me understand the concept of Residual Graph?

How does the Algorithm change in Undirected Graphs?


texts: What is the signature of a formal language?

texts:
I will briefly state the context where my doubts arise.
I know the following definitions.

A formal language is a set of well-formed formulas. It's a tuple constituited by an alphabet and a formal grammar.

An alphabet of a formal  language is a set of symbols. It's usually consituited by letters (symbols whose interpretation depends on the specific context) and signs(symbols whose interpretation doesn't depend on the context and whose aim is to structure the language).

A vocabulary of a formal language is the set of all letters of the alphabet.

A formal grammar of a formal language is a set of rules specifying how to form a well-formed formula from symbols in the alphabet.

I often find the notion of a signature but it's not intuitive to me. Is that the set of signs of a formal language? If not, what is it?


texts:
I have taken one basic class in complexity and understand the fundamentals. E.g. P, NP, NP-hardness. But I can't understand how to interpret $BPP^{NP}$.  I believe it means "BPP with an NP oracle" but how should I interpret that?

Does this mean that members of this class are problems for which there exist randomized algorithms that run in polynomial time but which can call another algorithm that can solve any problem in NP in constant time?  If so, how is this different from just having an algorithm that can solve any problem in NP in constant time?


texts: One $O(n^k)$ algorithm requiring only one $O(2^n)$ computation (for all n instances) is P or NP

texts:
Let $a$ one decision problem and $A$ one algorithm solving it in $O(n^k)$.

But, to construct $A_n$ we need to compute certain thing (strategy path, magic numbers, ...), we can compute that using certain general algorithm $R$ in $O(2^n)$.

Obiously, $A$ is polynomial (then, all $A_n$ are in P) and $R$ is exponential.

We can not solve big instances because $R$ is not practical.

But, in practice, we will can solve big instances after a big effort computing $A_n = R(n)$.

My question is twofold:

How are such problems considered in theory?
Have they been studied explicitly? Is there a particular case? some literature to read?
How are such problems solved in practice?
Have they been studied in general? Is there is a particular case? some literature to read?


texts: Is the Weighted Maximum Coverage Problem with frequency weights NP-hard?

texts:
I want to prove the following case of Weighted Maximum Coverage problem with special weights is NP-hard. But I have no idea. So I am here seeking for help.

The Weighted Maximum Coverage problem is formulated as follows (known to be NP-hard):

Given a set I of m elements with each element ej has a weight w(ej), a collection of subsets S=S1,S2,...Sn with each set covers some elements, and an integer k, the object is to find k subsets to maximize the sum weights of covered elements.

Now, my concern is as follows:

When the weight for each element is the number of subsets that cover this element, is the problem still NP-hard? How to prove it?

For example, given I={a,b,c,d}, S=S1,S2,S3, and S1={a,b,c} S2={b,c} S3={c,d}, then the weight of element b is 2, since there are two subset, S1 and S2, covers b.


texts: What is the runtime of the 'Risch Algorithm'?

texts:
I have been trying to find the upper bound on the runtime of the 'Risch algorithm' used for finding the integral of mathematical functions, but have been unable to do so.

https://en.wikipedia.org/wiki/Risch_algorithm

Does anyone know where I would be able to find the runtime of the 'Risch Algorithm'?


texts: Finding the smallest positive missing number in array of integers contains negative and duplicates number

texts:
I found this solution but I don't understand it. Can anyone explain the idea behind it ?

the solution:

  A O(n) time and O(1) extra space solution:
  The idea is similar to this post. We use array elements as index. To mark presence of an element x, we change the value at the index x to negative. But this approach doesn’t work if there are non-positive (-ve and 0) numbers. So we segregate positive from negative numbers as first step and then apply the approach.

  Following is the two step algorithm.

  Segregate positive numbers from others i.e., move all non-positive numbers to left side. In the following code, segregate() function does this part.
  Now we can ignore non-positive elements and consider only the part of array which contains all positive elements. We traverse the array containing all positive numbers and to mark presence of an element x, we change the sign of value at index x to negative. We traverse the array again and print the first index which has positive value.


texts: Linear programming restricted to rational coefficients

texts:
I'm reading the appendix A of Williamson's "the design of approximation algorithms" about linear programming. In the definition of a linear programming it restricted the coefficients of cost function and conditions to be rational numbers. I guess that this restriction is because of time analysis consideration in terms of input length. Am I correct? Are there other reasons?

EDIT: And do we know that if there is a solution to the LP, then there is a rational solution to it?

EDIT 2: If the answer to the previous question is yes, is there a guarantee for the length of resulting rational numbers to be polynomially bounded as a function of input size?


texts: TAPL: Explanation and example(s) for satisfied

texts:
This question arises from my reading of "Types and Programming Languages" (WorldCat) by Benjamin C. Pierce.

On page 36 is the definition for satisfied

  A rule is satisfied by a relation if, for each instance of the rule,
  either the conclusion is in the relation or one of the premises is
  not.

On page 36 is the definition for instance

  An instance of an inference rule is obtained by consistently replacing
  each metavariable by the same term in the rule's conclusion and all its
  premises (if any).

  For example

  if true then true else (if false then false else false) -> true

  is an instance of E-IFTRUE, where both occurrences of $t_2$ have been
  replaced by true and $t_3$ has been replaced by if false then false else
  false.

On page 15 is the definition for relataion

  An n-place relation on a collection of sets $S_1, S_2,..., S_n$ is a
  set $R\subseteq  S_1\times\;S_2\;\times\;...\;\times\;S_n$ of tuples
  of elements from $S_1$ through $S_n$. We say that the elements $s_1\in
> S_1$ thorugh $s_n\in S_n$ are related by $R$ if $(s_1,...,s_n)$ is an
  element or $R$.

On page 36 is the definition for one-step evaluation relation ($\rightarrow $)

  The one-step evaluation relation $\rightarrow $ is the smallest
  binary relation on terms satisfying the three rules of Figure 3-1.
  When the pair $(t,t')$ is in the evaluation relation,  we say that "the
  evaluation statement (or judgment) $t \rightarrow t'$ is derivable."

On page 34 are the three rules from Figure 3-1

E-IFTRUE

  \begin{equation}if\;true\;then\;t_2\;else\;t_3\;\rightarrow\;t_2\end{equation}

E-IFFALSE

  \begin{equation}if\;false\;then\;t_2\;else\;t_3\;\rightarrow\;t_2\end{equation}

E-IF

  \begin{equation}\frac{t_1\rightarrow\;t_1'}{if\;t_1\;then\;t_2\;else\;t_3\;\rightarrow\;if\;t_1'\;then\;t_2\;else\;t_3}\end{equation}

Can someone explain this definition and give an example for parts of the defintion.
1. The conclusion is in the relation.
2. One of the premises is not.

Note: I am aware that there is a forum dedicated to questions for the book here.

Note: You can use Google Scholar to see more of the details to this question in context.

EDIT

To connect some of the dots about my comment regarding unification and term rewriting.

When I saw

$$(A\rightarrow B)\equiv (\neg A \vee B)$$

it reminded me of Horn claues from Prolog, that along with the example then connected with my understanding of term rewriting. Having the book "Term Rewriting and All That" (WorldCat) by Franz Baader and Tobias Nipkow, I quickly looked up satisfiability and found satisfiable on page 58. This is actually the start of whole chapter on Equational Problems; but it also covers unification. At that point I realized that the definition was dealing with Satisfiability and from there is was a topic I was already familiar. What threw me was the way Benjamin defined it. He used a very precise definition right up front in a manner I didn't associate with my knowledge.

If you work through the code as I am and understand logic programming, then the definition makes perfect sense.


texts: We have languages $A= \{a\}$ and $B = \{b\}$. If we consider $(A\cup B)^*$, where ${}^*$ means Kleene star, we have a set of words like $\{\lambda, a,b,aa,ab,aaa,\dots\}$, where $\lambda$ is the empty word. Another example we do is $A^*(BA^*)^*$. If we concatenate two languages, $\lambda$ will not be in the set, but the Kleene star adds the $\lambda$. Question is, is this set same as the set with union so $\{\lambda,a,b,aa,ab,aaa,\dots\}$ or is the set for the second example $\{a,b,aa,ab,aaa,\dots\}$, in which case the langauages would not be equal. My opinion is that concatenation is the last operation so sets are not equal but I'm not sure.


texts: The runtime of a neural net with given numbers of observations, features, and neurons

texts:
If I have $n$ training observations, $m$ number of features per observation, and my neural network has $x$ neurons in the 1st layer, $y$ neurons in the 2nd layer, and 1 output neuron, what is the runtime of finding the parameters for my neural network? Using backpropagation? Using the best algorithm out there to do so?

I've looked over a lot of places on the Internet and can't seem to find anyone who's done a derivation of this. I'm very certain it's lower bounded by $O(mf)$ but I don't know how to incorporate $x$ or $y$. I'm asking this because I have a dataset of a certain size I want to try to apply neural nets to, and I'm trying to find a sense of if my dataset is too big for it.


texts: Any reason to use the least-constrained variable heuristic when searching the solution of a CSP?

texts:
Is there any (kind of) (well-known) problem which can be expressed as a CSP in which the least constrained variable heuristic seems to give the best results, when employing backtracking with constraint propagation as the search method?

I am aware of the most constrained variable heuristic, and the intuition behind it, but I was wondering when one would prefer to use the opposite approach.


texts: Algorithm for designing a binary code with predefined distance

texts:
Suppose I have a matrix $A$ with its entry $A_{ij}$ denoting some kind of distance between class $i$ and $j$, is there a feasible algorithm for computing a binary coding for all the classes, such that the Hamming distance between code word for $i$ and $j$ is (roughly) proportional to $A_{ij}$?

A related question is that given a set of points, design a binary code where the Hamming distance is (roughly) proportional to the Euclidean distance.


texts: NLP: in practice, what should I choose as Start and End symbol?

texts:
I'm writing a small program that implements a trigram HMM model and apply it by using Viterbi Algorithm. It's very standardized. However, I have never written anything like this before, and I get confused of what I should use as the START (*) and STOP symbols.

I tried to search for the answer online but apparently people who know the answer don't need to ask online, and people who don't know the answer don't need to know.

I primarily use Scala as my choice of implementation language. Scala has a program called ScalaNLP, but it's nowhere being mature, and it does not have HMM implementation as far as I can tell. So I decide to include a statistic package of Scala and write one by myself.

I recently watched Michael Collins' NLP class on Coursera and I thought he explained HMM model very well and I could possibly try to implement that by myself.

The "apply-part" of program itself on the outmost surface (structure) should look like the Viterbi Algorithm described in Collins' video. I do need to explain. HMM has two parts: training and applying. Training part is implemented to get emission variable: $e - e(x^i|y^i)$ and the parameter $q(v|w, u)$. The applying part is to take in a sentence: x1x2...xn and add two start symbols ** to the beginning of the sentence and a STOP symbol at the end.

I don't know if I am truly capable of doing such, but these great professors never mentioned any real implementation because people will just go and use a library created by someone else.


texts: Are functions in O(n) that are nor in o(n) all in Θ(n)?

texts:
One of my lectures makes the following statement:

$$( f(n)=O(n) \land f(n)\neq o(n) )\implies f(n)=\Theta(n)$$

Maybe I'm missing something in the definitions, but for example bubble sort is $O(n^2)$ and not $o(n^2)$ but it's also not $\theta(n^2)$ since it's best case run time $\Omega(n)$.

What am I missing here?


texts: Backpropagation in multiple output neural networks

texts:
I want to understand how the backpropagation algorithm would work on a neural network with multiple outputs.

More specifically, I have a network with 21 binary (0/1) outputs and I want to minimize the number of outputs that I get correctly; in other words, I want to minimize the hamming distance between the output vector and the desired vector.

How does the loss function work here? How do I backpropagate the error and update the weights?
I know this might be long to explain so I'm also happy with links to some good references that I could read on the matter.


texts: Prove: If $T'$ is not a MST one of its edges may be replaced by a lighter edge in order to get a lighter spanning tree

texts:
Prove: If $T'=(V,F')$ is a spanning tree, but not a MST of $G=(V,E)$, then there are edges $e' \in F'$ and $e \in $ $E$ \ $F'$ such that $w(e)<w(e')$ and $T'$ \ $\{e'\} \cup \{e\}$ is a spanning tree.
My idea:
Let $T=(V,F)$ be a MST of $G$
for all $e \in T$, try to insert it into $T'$ and see if there is an edge in the cycle created that is heavier than $e$. If we found such $e$ we are done.
If not, define $G'=(V,F \cup F')$
This graph obviously has a MST, because $F \subset F' \cup F$
We didn't find a suitable $e$ in the previous part so all edges in $F$ may be colored in red in the generic algorithm for finding a MST in the graph $G'$.
That means there is a MST $T''=(V,F'')$ such that $F'' \subseteq F'$ but that is impossible because $T'$ is not a MST of $G'$, because $T$ is lighter (by definition $w(T)<W(T')$)
Does that seem correct?


texts: How can I find minimum number required to add to sequence such that their xor becomes zero

texts:
Given a sequence of natural numbers, you can add any natural number to any number in the sequence such that their xor becomes zero. My goal is to minimize the sum of added numbers.

Consider the following examples :

For $1, 3$ the answer is $2$;  adding $2$ to $1$ we get $3 \oplus 3=0$.
For $10, 4, 5, 1$ the answer is $6$;  adding $3$ to $10$ and $3$ to $5$ we get $13 \oplus 4 \oplus 8 \oplus 1 = 0$.
For $4, 4$ the answer is $0$, since $4 \oplus 4 = 0$.

I tried working on binary representations of sequence number but it got so complex. I want to know if there is any simple and efficient way to solve this problem.


texts: How to show that $L=\{ wa^kw | w \in \{ a,b,c \}^* ,k \geq 0 \}$ is not regular using the pumping lemma for regular languages?

texts: I'm trying to show that the language in the title is not regular but I don't know how to chose a decomposition $x = abc$ to express the word in the language because the $w \in \{a,b,c\}^*$ is kinda tricky for me, I know it means $ \{ a,b,c\} \cup\{ a,b,c\}^2 \cup ... \cup \{ a,b,c\}^k $ but I don't know how to chose the decompositons for a word in the language and proove that is not in the language by pumping lemma. Any tips ?


texts: Doubt regarding cache hit ratios and access time

texts:
Question 1: What is the average access time for a 3-level memory system with access time $T_1$, $2T_1$ and $3T_1$? (Hit ratio $h_1$ = $h_2$ = 0.9)

The solution given is: $0.9[T_1] + 0.1(0.9[2*T_1] + 0.1[3*T_1]) = 1.11[T_1]$  (Method 1)

Here, they have considered the page won't be copied to the lower level. Otherwise, it would have been like the following

If a page is not there in cache, it would be copied from main memory to cache and then accessed. $T_1 + 2T_1$

If a page is not there even in main memory, it would be brought to main memory, then cache and then accessed. $T_1 + 2T_1 + 3T_1$

$0.9[T_1] + 0.1(0.9[T_1+2*T_1] + 0.1[T_1 + 2*T_2 + 3*T_1]) = 1.23[T_1]$  (Method 2)

I went through another similar problem.

Question 2

Cache Access Time = 20ns
Memory Access Time = 120ns
Hit Ratio = 0.8
Some other useless information below...
Cache Block size = 16 words
Set size = 2 blocks
Number of sets = 128
Size of main memory address = 21bits
What is the hit ratio if the average access time is increased by 40ns?
(A) Remains same      (B) 0.921     (C) 0.467      (D) 0.592

I simply calculated it using Method 1 as follows

Effective access time = 0.8*20 + 0.2*(120) = 40ns
Increase by 40ns, so new time = 80ns
80 = h*20 + (1-h)*120
Hit ratio = 0.4

But this is not in the options

But when I calculated it using Method 2

Effective access time = 0.8*20 + 0.2*(20 + 120) = 44ns
Increase by 40ns, so new time = 84ns
84 = h*20 + (1-h)*120
Hit ratio = 0.467

That is option (C)

Here, the answer is coming using Method 2 but in the above question they are using Method 1.

How do I know which method to take while solving such problems? Whether would the missed page be brought into the lower memory (cache) or not?


texts: Average Case Analysis for finding max in array with duplicated element

texts:
I've read some posts about counting the number of assignment inside code of finding the maximum value in array like this:

FindMax(L):
   n = len(L)
   max = L[1]
   for i = 2..n:
      if (max < L[i])
          max = L[i] (**)
   return max

According to this post and post, it's about the array that elements are strictly distinguish. So if the array contains values may be duplicated (for example, elements are integer in range [1, m], m = 3, with any length of array), how could we calculate the number of (**) will be executed in average case?


texts: Potential Example of an algorithm failure

texts:
I was looking an algorithm to solve a problem of finding whether and array contains a quadruple with sum = k,(k is input) mentioned at GeeksforGeeks.
In one solution the approach mentioned is below,which i think i not correct:

Store all possible two elements pairs of array in some another auxiliary array and also store i,j indices of the elements.There will be $C(n,2)$ pairs.
Sort the auxiliary array.
Take two pointers,left=0 and right=n-1 to auxiliary array.

3.1. If auxiliary[left]+auxiliary[right]==k and there is no common index in elements represented by left and right, we return true.
3.2  else If auxiliary[left]+auxiliary[right]<k, we do left++
3.3  else we do right--
3.4 And this goes in continues loop until left < size and right>=0 or we get element at 3.1
Now my doubt is that in case sum of left and right elements=k and  there is some common element between left and right,then this algo will do right--.
I want to understand that why we do right-- here and no left++ and the other way.I think there must be some example where this scenario will make algorithm fail but i am not able to produce that.Can some tell that whether it will indeed fail or prove that it is always correct?


texts: Regular language concatenation with superset

texts:
Let $A$ be some alphabet.

$A$ itself is a regular language.

$E = A^*$ is regular language over $A$. $E$ is a superset of all languages over $A$, regular or otherwise, i.e $E$ contains every possible string from symbols of $A$.

Now let $L$ be some regular language over $A$.

What is $\tilde{L} = L \cdot E$ ? More specifically, how $\tilde{L}$ and $E$ relate to each other? Are they equal? Is one subset of the other? Something else?

Source of the confusion is the following reasoning: closure under concatenation says that $\tilde{L}$ is a regular language and therefore $\tilde{L} \subseteq E$  (according to the above). On the other hand $\tilde{L}$ seems to contain strings $E$ does not, i.e. those that are formed by concatenating non-empty string from both languages.

Obviously this is wrong. What is going on here?


texts: Transitive reduction of rectangle containment hierarchy DAG

texts:
I am looking for a $O(|V| + |E|)$ algorithm for finding transitive reduction of a rectangle containment hierarchy DAG, i.e. a directed edge exists from one rectangle to another if the first rectangle contains the second.

That is, remove as many edges as possible so that if you could reach v from u, for arbitrary v and u, you can still reach it after removal of edges.

Assume that rectangles are unique, so we are dealing with a DAG.

This is useful, for example, with quantitative association rule mining from Srikant/Agrawal 1996. There, we are interested in close ancestors for hyperrectangles s.t. ancestors contain us. Determining close ancestor is similar to determining close descendant, which is related to transitive reduction with rectangle containment. This kind of rule mining is related to APRIORI algorithm for standard (i.e. "Boolean") association rule mining from Agrawal/Srikant 1994.

A similar problem is transitive reduction of standard DAG, which is here:
Transitive reduction of DAG

References

Agrawal, Srikant - Fast algorithms for mining association rules (1994)
Srikant, Agrawal - Mining quantitative association rules in large relational tables (1996)


texts: Best practices for normalizing up training, validation, and test sets

texts:
I was reading up on how to normalize my training, validation, and test sets for a neural network, when I read this snippet:

  An important point to make about the preprocessing is that any
  preprocessing statistics (e.g. the data mean) must only be computed on
  the training data, and then applied to the validation / test data.
  E.g. computing the mean and subtracting it from every image across the
  entire dataset and then splitting the data into train/val/test splits
  would be a mistake. Instead, the mean must be computed only over the
  training data and then subtracted equally from all splits
  (train/val/test).

(source: http://cs231n.github.io/neural-networks-2/)

Does this mean the following?

Split my training set T into training set T1 & validation set V1
Find the mean/var of T1, mean_T1, var_T1
Normalize T1, V1, and my testing set with mean_T1, var_T1.
Train & test accordingly...

Thanks...


texts: Is my implementation of genetic algorithm correct?

texts:
In genetic algorithms, we have a function called "mutation".  Before we call this function, we choose parents.
In my version of the algorithm, when i mutate the child, i don't change the bits which are the same as the given input.
By that, I mean :
Imagine we want to reach the string "ABCDE".
The algorithm first generates 5 strings randomly :
"ADDDE", "ABDIO", "MSDKO" , "POIUU" , "QWERT"
The fitness function says that the first two strings, have better quality to survive. So, we select them.
So we have "ADDDE","ABDIO" as parents.
Then we choose a random number between 0 & 4. Assume that 1 is chosen.
We take "AD" from the first string and "DIO" from the second one.
The child we made is : "ADDIO"

Now, The part which makes me confused :
When i mutate this child, I say "A" is in the same place of "ADDIO" as "ABCDE". So, I don't change "A". I mutate the other characters . For example i make "AQWERT","ARTYUI" , ...

Is this correct? Any idea? Any improvement ?


texts: Questions about Randomized Median algorithm?

texts:
In textbook by Mitzenmacher and Upfal here, they write in page 62, the following:

  By repeating Algorithm 3.1 until it succeeds in finding the median, we can obtain an iterative algorithm that never fails but has a random running time.

Note that that the algorithm has linear running time. Now, if we repeat this algorithm for k times, then the running time would be O(kn). Now, how they say that "By repeating algorithm until it succeeds in finding the median, we can obtain an iterative algorithm"?
I do not understand how they get an iterative algorithm. In order to get an iterative algorithm, then the algorithm must call itself and must have a logarithmic running time.

Another question: What does they mean by "it has a random running time"?

About iterated algorithm, please look here.
To see the algorithm, look at the book in page 59.


texts: MAX-CUT: are there any algorithms or codes for classical computers, that cater to this specific case?

texts:
A paper was published recently in Science where the authors minimized the following function:

$$E_{\text{Ising}}(s) = -\dfrac{1}{2} \Sigma_{i=1}^{N} \Sigma_{j=1}^{N} J_{i,j} s_i s_j,$$
where $s_i$ denotes the $i$th Ising spin, which takes a value of 1 or -1, $s = (s_1 s_2 \cdots s_N)$ is the vector representation of a spin configuration, and $J_{i,j}(=J_{j,i})$ is the coupling coefficient between the $i$th and $j$ spins ($J_{i,i}=0$). The problem is to find a spin configuration minimizing the Ising energy. This problem is mathematically equivalent to a famous combinatorial optimization problem named MAX-CUT (5, 17, 18, 39): divide the nodes of a weighted graph into two groups maximizing the total weight (called "cut value") of the edges cut by the division. By setting the coupling coefficient as $J_{i,j} = - w_{i,j}$ ($w_{i,j} = w_{j,i}$ is the weight between $i$th and $j$th nodes), we can solve MAX-CUT using Ising machines.

In particular, it appears that they are solving instances of weighted MAX-CUT where the input graph is the complete graph on 2000 vertices with edge weights assigned from $\{-1,1\}$ independently and uniformly at random.
They say they found solutions in 0.5 ms and the other specifics such as the criteria for calling something a "solution" are also given.
They say in the abstract that 0.5ms is 10 times faster than the Coherent Ising Machine (a type of quantum calculator), but I would like it to instead be compared to state-of-the-art for conventional algorithms on classical computers.
It should be possible to generate the same type of random instances of MAX-CUT as the authors, and solve the problem with a conventional algorithm for classical computing (e.g. CPUs, GPUs, FPGAs), and compare the performance to what is claimed in the paper, when using the same criteria for what is considered a good enough solution. Are there any algorithms or codes apart from just general SAT/CSP solvers, that could be applied to this specific problem?


texts: Why is simulation by non deterministic Turing machine faster than a deterministic one?

texts:
A deterministic universal Turing machine $U_D$ can simulate a deterministic turing machine $M_D$ in $O(T(n)log(T(n)))$ where $M_D$ runs in $O(T(n))$. But I came across an exercise in Sanjeev Arora and Boaz Barak that a non-deterministic universal Turing machine $U_{ND}$ can simulate a non deterministic Turing machine $M_{ND}$ in $O(T(n))$ where $M_{ND}$ runs in $O(T(n))$.
The hint to the exercise is that $U_{ND}$ first non deterministically guesses tape contents of $M_{ND}$ and verifies then later. But how does this help as any branch of $U_{ND}$ can simulate a branch of $M_{ND}$ in $O(T(n)log(T(n)))$, similar to the deterministic case. Am I missing something ?


texts: How does the asterisk (*) work in the wildcard matching problem?

texts:
This is a wildcard matching problem. Given a pattern P containing letters and character * that can match an arbitrary string of characters (including an empty string), my task is to write a polynomial-time algorithm to determine whether such a pattern P occurs in a given text T. So here is my answer for the problem.

We can use dynamic programming to solve this problem. Let us have a 2D boolean array dp[i][j]. dp[i][j] returns true if there is a match between the pattern and the string.

Initialize dp[i][j] = false

-dp[0][0] = true since an empty string matches an empty pattern.

-dp[0][j] = dp[0][j-1] (= true) if P[j] = * for 1<= j <=m since an empty string matches ‘*’ as long as previous characters match. In other words, once P[j-1] != “*”, dp[0][j] will be false afterwards.

-If P[j] = ‘*’, we have dp[i][j] = dp[i-1][j] || dp[i][j-1]

For dp[i-1][j], ‘*’ acts as an empty string. E.g. ab and ab*

For dp[i]p[j-1], ‘*’ acts as any sequences. E.g. abcd and ab*

In other words, if P[j] = ‘*’ and (dp[i-1][j] || dp[i][j-1]) = true, dp[i][j] = true

-If P[j] = T[i], it boils down to match T(i-1) and P(j-1). dp[i][j] = dp[i-1][j-1]

For other cases, dp[i][j] is false.

Pseudocode:

tLen = T.length

pLen = P.length

Initialize dp[tLen+1][pLen+1] = false

Dp[0][0] = true

For j = 1 to pLen

          If P[j] = ‘*’

                   dp[i][j] = dp[0][j-1]

for i =1 to tLen

          for j=1 to pLen

                   if P[j] = ‘*’

                             dp[i][j] = dp[i][j-1] or dp[i-1][j]

                   else if P[j] = T[i]

                             dp[i][j] = dp[i-1][j-1]

                    else

 dp[i][j] = false

Return dp[tLen][pLen]

The algorithm fills a tLen x pLen table, so the running time is O(nm)

During a discussion in class, my professor said my answer is vague. He asked me if I had considered  * can appear in the middle of the pattern and it can appear several times in the pattern. In particular, consider pattern

abcccdeeef

and string

abcdcccccdefefeefeeef

How does this algorithm determine, which c in the pattern should match with
which c in the text? How does it with e?

My understanding towards this problem is that what matters is the final result of dp[tLen][pLen] and we use a table to compare substrings with each other.The character * would probably match any character it encounters. We just derive our answers from previous steps to fill out the whole table so that we can get the final result of dp[tLen][pLen]. However, for his specific question (that is, How does this algorithm determine, which c in the pattern should match with
which c in the text? How does it with e?), I can't think of a reasonable way to answer. Any help with the explanation would be appreciated.


texts: Proof that a subtree of a red-black tree has no more than $\frac{3n}{4}$ nodes

texts: I have a red-black tree with $n$ nodes, rooted at $x$. How can I prove or disprove that the number of nodes in any subtree of $x$ (including the root of the subtree) will never be greater than $\frac{3n}{4}$?


texts: What is the basic idea behind the usage of TLBs?

texts:
I know how Translation Lookaside Buffers work, and i also know we use them to improve the performance of data/program access by storing the recent page numbers - frame numbers in a memory cache.
The problem is that i can't understand why frequent memory locations are acccessed in a period of time? And what was the starting point of this idea:

  "Since the same memory locations are accessed frequently, We can create a place to hold the frequent translations so that make everything happen faster."

Can someone please share the knowledge behind this concept? Thanks.