texts:
I am going through the following series of lectures on OS development .

http://www.brokenthorn.com/Resources/

In the fourth tutorial , I came across the term " OEM" parameter block that stores the windows MBR and the Boot-record information whose soul purpose is to describe the file system on the disk .

And then  on moving to the following tutorial ,by taking the authors promise to explain about it at a later opportune point , I came across the term "FAT" file system . And I could see that there were few terms in the parameter block  like "bpbNumberofFATS" and "bpbsectorsperFAT" .
"FAT" stands for "File Allocation Table" and it is a again a "filesystem" .

This got me confused as "OEM" parameter block is used to describe the filesystem on a disk . And if "FAT" itself is a file system , then that means and surely there are other file systems ,which could have been on that disk . Why will the "OEM" block predefine the file system in terms of "FAT".

On reading a bit about other file systems , I came across statements like "FAT was written by .." . And it further piqued me to ask , what does it mean to write a filesystem ?

So , basically I am confused about :

What exactly is a filesystem ? (Is it a kind of coordinate system to provide information about the storage of the contents of the file ?)
How is a file system written ?

There are a lots of other file systems , OEM is used to describe the file system on a disk , so why OEM has parameters concerned about FAT's ? And who sets the filesystem of a disk and how ?


texts: Is finding the longest path of a graph NP-complete?

texts: The problem of finding the largest subgraph of a graph that has a Hamiltonian path can be restated as finding the longest path of a graph. Is this NP-complete? Also, is finding the $k$-length path of a graph NP-complete? Is it still NP-complete if we require the path to visit a given vertex?


texts: Highly colored vertices in greedy coloring imply existence of subtrees

texts:
I have a graph $G$ on which I try greedy coloring; i.e. I order the vertices and then start coloring them according to their order and I assign each vertex the smallest possible color available to it. (It is easy to see that this might not be the optimal coloring possible)

So after the coloring, we see that a vertex has color $k$ which is the highest assigned color in the graph (other vertices might have color $k$ but no vertex has color more than $k$). I would like to say that given any tree on $k$ vertices I can find that tree as a sub-graph of $G$.

My ideas : I observed that the $k$ vertex tree can be found in the graph with one vertex being the one colored $k$ (as one might expect). Moreover I think that if someone mentions any $k$ vertex tree and any node, $v$, in that tree we can find the tree in $G$ with the vertex colored $k$ acting as the node $v$. This is what I tried to induct on but couldn't succeed.


texts: Minimizing the iterative sum of pairs of numbers in a list

texts:
Given the tuple (list, value):

$$\left(\left[x_1, x_2, \cdots x_n\right], y\right)$$

You may choose two adjacent values in the list to modify the tuple as:

$$\left(\left[x_1, x_2, \cdots x_{i-1}, (x_i + x_{i+1}), x_{i+2} \cdots x_n\right], y + x_{i} + x_{i+1}\right)$$

Iterate until:

$$\left(\left[\sum_i x_i\right], y + z\right)$$

What is the optimal set of choices that minimizes $z$?

Intuitively, you never want to operate on the largest number in the list.  But the largest number in this list changes as you add values together.  In other words, the optimal solution is not necessarily obtained by an optimal solution of a sub-problem.

A greedy solution would start by taking the smallest number in this list and adding it to the smaller of its adjacent numbers.  This solution, while close, is not equivalent to the value returned by brute force search.  This points to the fact the some locally optimal step is not globally optimal, which could be connected to the fact that the largest element of the list changes as values are added together.


texts: NP-hardness of a special traveling salesman problem

texts:
Consider we have $n$ vertices, $v_1,\ldots,v_n$. We have two positive values $(a_i,b_i)$ associated with each $v_i$. The edge weight $w(v_iv_j)=a_ia_j+b_ib_j$.

Is it NP-hard to solve the traveling salesman problem on this graph?

In the special case where all the $b_i$ are $0$, this is solvable in $O(n\log n)$ time. Because this is the traveling salesman problem on a symmetric product matrix. See section 5.2 in this survey.


texts: What is the fastest algorithm to check whether input table is a group?

texts:
Given an input table with binary operation $\circ$. I want to check whether given input table represents a group or not.

I need to verify the four axioms of a group.

The identity I can find it by just scanning the first row of the given table. -----$\mathcal{O}(|G|)$ running time.
Find the closure operation ie.e for any $x,y \in G$, I need to show that $x \circ y \in G $.------$\mathcal{O}(|G|^2)$
An inverse of an element.----$\mathcal{O}(|G|^2)$ Running time.
Associativity operation. -----$\mathcal{O}(|G|^3)$

Which gives me a $\mathcal{O}(|G|^3)$ running time algorithm to check whether the input table corresponds to some group.

Question : What is the fastest algorithm to check whether the input table is a group?

Model of computation is RAM, which computing $x \circ y$ takes constant time.


texts:
I was solving Stone Game II on LeetCode. I was able to come up with a recursive (TLE) solution, which I optimized using memoization. The recursive solution computes a function $u(i,m)$, depending on an array $A_1,\ldots,A_n$, where:

$i$ is the starting index
$2m$ is the maximum size of the window at $i$

Here is the recurrence:
$$
u(i,m) =
\begin{cases}
\sum\limits_{j=i}^{n} A_j & \text{if } i + 2m-1 > n, \\
\sum\limits_{j=i}^{n} A_j - \min\limits_{\substack{0 \leq k \leq 2m-1 \\ i+k \le n}} u(i+k+1, \max(m,k+1)),
& \text{if } i + 2m-1 \le n.
\end{cases}
$$
(Using $O(n)$ preprocessing, the sums can be computed in $O(1)$.)
I am interested in the value of $u(1,1)$.
However, I am not sure about the time complexity of this solution.
According to me :

There are $m \times n$, where:

$n$ is the number of elements in $A$.
$m$ is the width of window that varies at each step.

Each state is being calculated only once.
$m$ can not be greater than $n$, the size of $A$.

Hence, the time complexity of the solution should be $O(n^2)$.
Is there something that I am missing? Is there a mathematical way to prove this?


texts: Which research languages have a stronger typesystem than Haskell and why?

texts:
Here I read that:

  Haskell definitely does not have the most advanced type system (not
  even close if you count research languages) but out of all languages
  that are actually used in production Haskell is probably at the top.

So I am asking two things:

which research languages have more powerful type systems  than Haskell;
what do they improve.

I am just a programmer, so I don't know many mathematical objects used in type theory, please provide gentle explanations if you can.


texts:
I have an  algorithmic problem.

I have a set of different polygons in the 2D space. Each polygon is represented according to its vertex representation (x and y coordinates) and may contain up to N different vertices.

Assuming I have a set of N polygons, then for a new polygon k, how do I determine whether or not k overlaps with each one of the N polynomials in the set AND what is the overlapping reign percentage?

This is a purely algorithmic question but I plan on writing the algorithm in parallel using the CUDA platform, therefore any highly parallel solution would be preferred.


texts: using mappings in order to reduce k-SUM to k-clique

texts:
In page $4$ of this paper, Lemma 2.1 claims to establish a reduction from $k$-$SUM$ to $k$-$Clique$ problem:

  For any integers $n,c,d,p \geq 1$ such that $p ≥ 3n^{\lceil
> c/d\rceil}$, there is a set of $s = 2^{o(d)}$ mappings
  $f_1,\cdots,f_s:[−n^c, n^c] → [−p/3, p/3]^d$ and $s$ target vectors
  $t_1,\cdots,t_s \in [−p,p]^d$ such that:

  For every $x,y,z \in [−n^c,n^c]$,
  $$x+y+z = 0 \iff \exists i\in[s].f_i(x) + f_i(y) + f_i(z) = t_i$$.

There are two things I do not quite get about this:

How does this establishes the reduction,
And, what is the role of the condition: $p\geq 3n^{\lceil\frac{c}d\rceil}$?

EDIT: It should be noted that the original source for this lemma is: Lemma 3.1 of this paper.


texts: It is decidable whether a pushdown automaton will accept a word?

texts:
I'm asking myself if the problem of decide whether a push down automaton will accept a word is decidable.

I would say that you can simulate a push down automaton with a Turing Machine and, if it doesn't loop forever, accept the word when the automaton accepts, or reject when it does. In this case, the problem of decide if a push down automaton accept a word would be semi-decidable. But I'm not sure if that is correct and also, I can't find a way to prove if it is decidable or not.

Any ideas here?


texts: Convoy effect in priority scheduling and SJF (Non preemptive)

texts:
In books, I have read that FCFS suffers from convoy effect. I think that even SJF and priority(both preemptive and non preemptive) can suffer from convoy effect.

In SJF, if a process with large burst time arrives first then no other process can preempt it causing convoy effect.

In preemptive and non preemptive priority, if all processes arrive at time 0 and if a high priority process has very large burst time, it can lead to convoy effect as no other process can preempt this process because they all have lesser priority.

Am I correct?


texts:
I'm trying to show that the language {(m,n)|m has exactly n divisors} is in NP.

The input (m,n) is in binary.

The non-deterministic Turing machine for the language would be:

1) Guess the prime factors of m.

2) Verify that ∏i(di+1)=n.

The problem is that I can't find a way to factorize in polynomial time (in the input) the number m.

If stage 1 takes m steps then it would be m=2 ^ log(m) and the whole algorithm would run in exponential time.

How can I prove that verifying that m has exactly n divisors is in NP ? Perhaps not via factorization but somehow else. I've run out of ideas.


texts: What is the intuition behind balancing in AVL trees?

texts:
I am not sure that my question is clear from the first sight. But I will try to explain what I mean. For now, I am learning balancing the trees on the example of AVL trees. We know that to balance tree wnen new node is added, we turn the tree either to left or right, e.g if new node in left child's left subtree (left-left) we turn it to right, or in right-right case we turn it to left.

It is not hard to notice the pattern, that if left subtree is heavier then we turn it to right and vice versa. For me it is like standing and balancing on the board (that's my intuition).

Then I tried to apply this intuition on left-right (left child's right subtree) and right-left (right child's leftsubtree ) case. But I failed. It looks like:

Here assume that B is root and new node somewhere in right subtree of C, which root is A. Here one rotation is not enough, i.e. we need to turn it first to left, then to right. So the point is in middle rotation the we make, it is like bringing tree to rotatable form. Because if I have tree in following form, I can just rotate the tree to right, that's all.

So it looks like in previous image what we were doing is to bringing the tree to the form of tree as in the last example. Because rotating it directly to right doesn't solve problem, actually we get again unbalanced tree but with right heavy part.

I am familiar with optimization methods, also Pareto efficient points, etc, and somehow feel that there is something like that. If you want to decrease the height of one subtree, then you must increase somewhere, and vice versa. All good people already devised pattern for all cases. But I can't understant what are these properties (maybe how we can mathematically define that properties) of that middle, even stable stage. I feel it, but can not understand these properties. Or maybe I am absolutely wrong. Sorry for long question. But I will be very happy if you answer and clarify this for me.


texts:
Is it possible, in general, to determine whether two regular expressions admit the same set of strings?

Also, in particular, is it possible to determine whether a given regular expression admits the same set of strings as the regular expression ".*" (i.e., accepts anything).


texts: Understanding Return Oriented Programming on Harvard Architecture

texts:
I'm currently reading this paper: Code injection attacks on Harvard-architecture devices (ACM) (pdf)

I understand the basics of what the attack is trying to do, but one thing really bothers me.  If Harvard Architecture is supposed to have a strict separation of code and data, how is the initial buffer overflow allowing the attacker to rewrite return addresses on the stack?  Since the architecture only allows data to be read into instruction memory via the SPM instruction--one that is specially reserved--I just don't get where the ability to rewrite the ret pointers is coming from.  I feel like I'm missing something obvious.


texts: Using persistence on a constant database

texts:
I'm quite new to understanding persistent data structures, so bear with me.

Consider some database with data of the form $(\text{id}, d_1, d_2)$. The last two could e.g. mean production data and sales date, respectively.  The database is constant, i.e. we will not be adding or removing data points.

Let $n$ be the number of items in the database. I want to be able to do the following query:

  Query$(a,b,s)$: Return the number of objects that have $a\leq d_1 \leq b$  and $d_2 \leq s$.

I want to be able to perform the query in $\mathcal O(\log n)$ time, with the best possible space and preprocessing time complexities. My question is how could one construct a persistent data structure that solves this problem?

I think that I need to use timestamps that relate to the $d_1$ and/or $d_2$ in some way. However, I'm not quite sure how.


texts: I need help understanding how to prove partial correctness

texts:
Please help me understand how I would prove the partial correctness of the below pseudocode with respect to the following predicates:

Pre: {n>=0}

Post: {a^2 <= n and n < (a+1)^2)

That is,

{Pre}
begin
   x:= 0;
   y:= 1;
   z:= 1;
   while y <= n do
      x:= x+1;
      z:= z+2;
      y:= y+z;
   a:= x;
end
{Post}

An explanation would be much appreciated. I've read various PPTs and PDFs and still can't fully make sense of how to do this.

From what I can tell, I think that if the code is executed satisfying the precondition, then everything holds true. The problem is that I'm not sure how to formally prove that.

Considering Hoare's logic, would the Composition rule be applied here? Would each line of pseudocode be a consecutive "program" in the Hoare Triple? I guess one of the things confusing me is how to solve for multiple lines of code. Most examples I've come across are more simplified: { x + 1 = 43 } y := x + 1 { y = 43 }


texts: Does MST exclude the edge belongs to the cycle of the graph?

texts:
For any simple, connected, undirected graph $G(V,E,w)$ with each carrying distinct positive edge weights, is it true that MST will contain all the edges which do not lie in any cycle of $G$?

I think MST can take any edge of irrespective of the fact whether it is an edge of cycle (like I simply use Kruskal's), Also I am unable to see Why the above statement should true. Can anyone tell how the statement is true?


texts:
I am trying to prove that following decison variation of MaxSAT is both NP hard and co-NP hard.
$(\phi ,k) \in L$ iff an assignment of $\phi$ satisfies k clauses and no assignment satisfies more than k clauses.

I think we can show that NP hardness by reducing SAT to L by setting k=m (number of clauses). But I can't reduce $\overline{SAT}$ to L. Is that reduction possible?


texts: Infix vs postfix vs prefix - which has the smallest processing time

texts: Infix, prefix (polish notation) and postfix (reverse polish notation) are all forms of arithmetic operations. As I understand it, infix is what we use in maths where the rules of BODMAS (Bracket, Order, Division and Multiplication, Addition and Subtraction) are used to decide what order the operations are used in. I can understand this being more computationally expensive to calculate than pre/post fix as the processor would have to reorder the equation so that it follows BODMAS. However, I do not understand why there is both prefix and postfix as they just change the order of tree traversal, so logically would take the same amount of processing time as each other. Is there any reason for choosing one over the other, and is my belief of infix being slower than post/prefix correct?


texts: What are methods for showing that concurrent objects are not linearizable?

texts:
Linearizability is a well-known correctness condition for concurrent objects.  It provides the illusion that each operation applied by concurrent processes takes effect instantaneously at some point between its invocation and its response. To prove linearizability of an implementation, it is necessary and sufficient to show that all its possible executions are linearizable with respect to some sequential specification. For this purpose, two common methods have been developed, as summarized in the paper "Linearizable Implementations Do Not Suffice for Randomized Distributed Computation [@STOC'2011]".

However, what are typical methods for showing that some implementation is not linearizable? Logically, it is necessary to identify an execution which is not linearizable. But, how to achieve it? Are there some typical examples of demonstrating the non-linearizablity of an implementation in the literature?


texts: Largest parallelization speedup for multiplication of very large numbers

texts:
I have recently come across the following papers:

S. Baktir and E. Savas. Highly-parallel Montgomery multiplication for multi-core general-purpose microprocessors.
In E. Gelenbe and R. Lent, editors, Computer and Information Sciences III, pages 467–476.
Springer London, 2013.
P. Giorgi, L. Imbert, and T. Izard. Parallel modular multiplication on multi-core processors. In Computer
Arithmetic (ARITH), 2013 21st IEEE Symposium on, pages 135–142, April 2013.
B. S. Fagin, "Large integer multiplication on massively parallel processors," [1990 Proceedings] The Third Symposium on the Frontiers of Massively Parallel Computation, College Park, MD, 1990, pp. 38-42.

where they deal with the issue of computing a multiplication between large numbers (in the first two papers, up to approx $2^{14}$ bits, in the last one up to $2^{23}$ bits) using many processors simultaneously.

I was wondering: what happens beyond that? What is the theoretical maximum speedup for a $2^n$ bit multiplication, having an unlimited amount of processors at disposal? Can the wallclock time of the operation be made arbitrarily small? I guess there are communication bottlenecks among the processors?


texts:
Is the following problem NP-complete? (I assume yes).

Input: $k \in \mathbb{N},G=(V,E)$ an undirected graph where the edge set can be decomposed into two edge-disjoint simple cycles (these are not a part of the input).
Question: Is there a simple cycle in $G$ with length greater than $k$?

Obviously the problem is in NP and the maximum degree in $G$ is $\leq 4$, but that doesn't seem to help.


texts: Fastest way to check data against an envelope

texts:
If I have two arrays containing max and min points which make up an envelope. It's quick to test if any point in a given data array goes outside of that envelope using:

 for (int i = 0; i < envMax.size(); i++)
    {
        if ((data[i] < envMin[i]) || (data[i] > envMax[i]))
        {
            return false;
        }
    }
    return true;

However, my data array can be large and I have to load the max and min envelope data from a file for each new data array which needs testing (just the way the system works). So it might be quicker to just use a smaller number of points for the envelope and interpolate. But whats the quickest way of doing this with a  reduced number of points. I can do (sudo code):

for each data point
find min and max envelope point before and after data point
calculate equation of line between two points
put in data "x" value
check resultant y value.

Alternatively I can just generate N max and min envelope points (where N is = length(data)) (same thing really)...

But this seems computational exhausting. I can't believe I am the first person to want to do this so is there an accepted (fastest) method / algorithm type?

EDIT:

The problem is essentially this: Check that the blue line is within the green lines. But doing it when the number of points describing the green lines is much less than the number of points describing the blue line.


texts: Calculating time complexity of two interdependent nested for loops

texts:
Consider the following code segment :

for (int i = 1; i <= n; i++ ) {
    for (int j = 1; j <= n; j = j + i ) {
          printf("Hi");
    }
}

Here, the outer loop will execute $ n $ times, but the execution of inner loop depends upon the value of $ i $.

When $ i = 1 $ inner loop will execute $ n $ times.
When $ i = 2 $ inner loop will execute $ \frac{n}{2} $ times.
When $ i = 3 $ inner loop will execute $ \frac{n}{3} $ times.
$ \vdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \vdots  $
When $ i = n $ inner loop will execute $ 1 $ time

So complexity will be given by
$$
 \begin{align}
  T(n) &= \frac{n}{1} + \frac{n}{2} + \frac{n}{3} + \cdots + \frac{n}{n}\\
\\
       &= n \left( 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} \right) \\\\
       &= n \sum_{k = 1}^{n} { \frac{1}{k} }
 \end {align}
 $$
I am not able to solve $ \sum_{k=1}^{n} \frac{1}{k} $. Upon searching I found that it is the $ n^{th} $ Harmonic number ( $ H_n $), but couldn't find any closed formula for it. How can I proceed further to calculate $ T(n) $?


texts:
My first thought was using the third case of the master theorem, but I am not sure if I can use $\epsilon \rightarrow 0$, so $f(n) \in \Omega(n^{log_2^4+\epsilon})$.

Otherwise, I tried solving the equation by iteration where I got $T(n) \in \Theta(n^2log_2^3n)$ instead of $T(n) \in \Theta(n^2log_2n)$.

Which solution is right and why? Thanks.


texts: What does it mean that a value can only be incremented after it's been loaded into a register?

texts:
Consider the following program:

const int n = 50;
int tally;

void total() {
  int count;
  for (count = 1; count <= n; count++){
    tally++;
  }
}

void main() {
  tally = 0;
  parbegin (total (), total ());
  write (tally);
}

  Determine the proper lower bound and upper bound on the final value of the
  shared variable tally output by this concurrent program.Assume processes can execute
  at any relative speed and that a value can only be incremented after it has
  been loaded into a register by a separate machine instruction.
  Suppose that an arbitrary number of these processes are permitted to execute in
  parallel under the assumptions of part (a).What effect will this modification have
  on the range of final values of tally?

My problem is that I don't understand the question what does this mean ?

  ... and that a value can only be incremented after it has been loaded into a register by a separate machine instruction.

I feel that when two processes execute simultaneously due to this assumption some value of tally will be lost but I don't know how it can happen because I don't know what this assumption means so I can't find lower bound!it is obvious that if 2 or n process execute one after the other tally will be 100 hence 100 = (number of process *50) is upper bound!


texts: Why do we care about random Boolean SAT formula?

texts:
I've been looking for a reference for the above question.

As far as I know the answer is:

If we can make a solver that is efficient for all randomly generated instances, it should be efficient for any instance.

i.e. if we make a solver that doesnt rely on any inherent structure, it will always be efficient.

Is this correct? Either way, does anyone have a reference to a paper I can cite for the answer.


texts:
Let's consider the following MIPS (using pipelined arch.) assembly code:

lw r1,0(r2)
sub r4, r1, r6
and r6, r1, r7
or r8, r1, r9

the r1 value used in the second and third instruction will not be ready to use  until the end of the 4th cycle of the pipeline, while the 2nd and the 3rd instruction need it at the 4th and 5th cycle respectively, i think for the 3rd instruction the problem can be resolved using bypass but for the 2nd instruction i am not sure ??
can anyone tell me how to avoid the RAW data hazard in this case ??


texts:
Suppose I have an NFA with accepting state q1(which is also an accept state) and non-accept state q2, with ε-transition from q1 to q2.

Also, suppose that empty string is inside the language. Then I want to know if the empty string is accepted by the above NFA following the standard definition:

Here, $\mathcal{P}(Q)$ denotes the power set of Q. Let $w = a_1 a_2 \ldots a_m$ be a word over the alphabet $\Sigma_\epsilon$. The automaton $M$ accepts the word $w$ if a sequence of states, $r_0,r_1, \ldots, r_n$ exists in $Q$ with the following conditions with $m >= n$ and $m>=0$:

$r_0 = q_0$

$r_i+1 \in \Delta(r_i, a_i+1)$, for $i = 0, \ldots, n−1$

$r_n \in F$

I know it would be much easier to figure out whether the given string is accepted by NFA by visualizing what's going on in the NFA, but I find the formal definition above rather confusing because it's only checking the existence of one particular branch of computation that satisfies the above three conditions. I know that an empty string is w =  ε or [blank]. By blank, I mean it has no symbols (where m = 0). But if I take w = ε, it would move from q1 to q2 via following ε-transition.But if I take w = [blank], then the sequence of state would be just q0, then it would be accepted. Is this the right way of thinking about it?


texts: Terminology - machine code and byte code

texts:
Do "machine code" and "byte code" terms refer to the available instruction set to the CPU and virtual CPU and their encoding (the language specification) or do they refer to the "encoding" of the current program's instructions after compilation?
The definitions I found in wikipedia seem to lean towards the notion of "instruction set":

https://en.wikipedia.org/wiki/Machine_code
https://en.wikipedia.org/wiki/Bytecode


texts: Is there a name for the "tree" aproach to listing things?

texts:
I've only been studying computer science for a few weeks, so I apologize if this is a silly or naive question.

Suppose we're trying to list all elements of the set $$C(r) = \{(x,y,z) \in \mathbb{N}^3 : \sqrt{x^2+y^2+z^2} \leq r\}.$$

An obvious approach would be this: first, list all integers between $0$ and $r$; these become our $x$-values. Then, for each $x$-value, list all integers between $0$ and $\sqrt{r^2-x^2}.$ These become our $y$ values. Then, for each $(x,y)$ pair, list all integers between $0$ and $\sqrt{r^2-x^2-y^2}$. These become our $z$ values. We can visualize this process as a tree; the branches of the tree are the elements of $C(r)$.

A similar approach can be applied to solve the Knapsack problem a little quicker than brute force. Begin by forgetting the value of each item and just focusing on its weight. Now go through the items from left to right, bifurcating each node into two as you go, so that one edge corresponds to "take the item" and the other corresponds to "don't take the item." If taking the item would send you overweight, you refrain from adjoining the edge that corresponds to taking the item, but you still adjoin the one corresponding to not taking the item. In the end, we get a binary tree whose branches can be viewed as subsets of the set of items, which ultimately means fewer numbers that need comparing.

Well, I can see my computer running out of memory pretty quickly trying to do this - I'm sure there's better approaches out there - but nonetheless, if there's a name for this kind of thing, I'd like to know it.


texts:
I'm currently doing some research on signal processing and I got a dataset which includes the signal in itself and its "translation".

So I want to use a Many-to-Many RNN to translate the first into the second.
After spending a week reading about the different option I have, I ended up learning about RNN and Seq2Seq models. I believe this is the right solution for the problem (correct me if I'm wrong).
Now, as the input and the output are of the same length, I don't need to add padding and thus I tried a simple LSTM layer and TimeDistributed Dense layer (Keras):
model = Sequential([
    LSTM(256, return_sequences=True, input_shape=SHAPE, dropout=0.2),
    TimeDistributed(Dense(units=1, activation="softmax"))
])

model.compile(optimizer='adam', loss='categorical_crossentropy')

But the model seems to learn nothing from the sequence and when I plot the "prediction", it nothing but values between 0 and 1.
As you can see, I'm a beginner and the code I wrote might not make sense to you but I need guidance on few questions:

Does the model make sense for the problem I'm trying to solve ?
Am I'm using the right loss/activation functions ?
And finally, please correct/teach me


texts: When proof by induction on length string is not possible?

texts:
I found out an exercise where you have to prove the correctness of the following CFG:
Let $L=\{ 0^i 1^j|2i \leq j \leq 3i \}\:$ and
$\: G: S\rightarrow 0S11 | 0S111| \epsilon$
claim: Every string $w \in L$ can be generated by $G$.

It says that it's not possible to prove the claim by induction on the length string, and I can't figure out why.


texts:
I recently began working as a tutor with my college, helping younger students struggling in intro classes get their footing.

Many of my students particularly struggle with basic data structures (linked lists, heaps, binary [search] trees, hash tables, etc.); I'll call them DS's for short. I can often explain a DS where they make sense of it how it works (with a little help from Wikipedia). To further help them develop an understanding of these DS's, I'd like to provide simple examples for them to work through (think 3-layer binary search tree with 5-7 nodes), as well as some common applications of these data structures.

This leads me to my question. Do you know of a collection of basic data structure examples I could use for tutoring students? To clarify, I am not searching for implementations of these DS's, but specifically written/diagrammed problems of the common data structures such as the ones your professor might work through in lecture during the first two years in a university program.


texts: Show that every definite language is accepted by a finite automaton

texts: A language $L$ is definite if there is some $k> 0$ such that for any string $w$, whether $w \in L$ depends on the last $k$ symbols of $w$. How can I prove that every definite language is accepted by a finite automaton?


texts: How specifically do I need to describe (in words) the language of a regular expression?

texts:
For the regular expression $(a^*ba^*b)^*a^*$, I want to learn how to describe it in words. I know there are an even number of $b$s but how much do I need to explain it? Do I need to explain it enough that each possible string can be produced from my explanation?
Another example is $(a^*[ba^*c])^*$ where I would describe it as as string over $\{a,b,c\}$ where there are the same number of $a$s and $c$s.


texts: Max nodes whose value exceeds all neighbors

texts:
A node is valid if its value is greater than all of its incident edges.

Task is to maximize the number of valid nodes.

Given $n$ values for nodes and $n-1$ values for edges, how do I assign these values (to nodes and edges) to a given input tree so the number of valid nodes is maximized?


texts:
Say one is given a matrix (assume real and symmetric if necessary) and its $n-$dimensional columns be say $v_1,v_2,..,v_n$. Now is it possible to find a set of $d<n$ lower dimensional vectors ($w_1,..,w_d$) such that they form a $d \times d$ matrix $B$ (assume real and symmetric) with either of these properties,

That the $d$ eigenvalues of $B$ are "close" to the top$-d$ eigenvalues of $A$? (and hence the correspomding eigenvectors are also "close" in some sense?)
That the spectral norm of $B$ is "close" to the spectral norm of $A$.

Will this be called "sketching"?
Does Johnson-Lindenenstrauss lemma help in doing these?


texts: Determining the number of walks between two vertices in a graph

texts:
Given a graph G and a set of vertices $(v_1, v_2)$.

How can you determine whether there is $\textit{one}$ unique walk between $v_1$ and $v_2$?


texts: Can a cellular automata structure simulates another cellular automata structure?

texts:
In Elementary Cellular Automata, rules can show one pattern, but i am wondering if there is something where a cellular automata structure can simulate another structure?

Is there a category for this in Cellular Automata?


texts: Is there an equivalent of van Emde Boas trees for ropes?

texts:
Someone I know is planning on implementing a text editor in the near future, which prompted me to think about what kind of data structures are fast for a text editor. The most used structures are apparently ropes or gap buffers.

Van Emde Boas trees are just about the fastest priority queues around, if you don't mind an upper bound on the number of items you can put into it and a large initialization cost. My question is whether there exists some data structure that is just as fast as the van Emde Boas tree, but supports text editor operations.

We only need to support up to $m$ characters in our data structure (so if $\log m = 32$, then we support up to 4GB worth of ASCII characters). We are allowed $\sqrt{m}$ time to initialize a new data structure. We'd like to support the following operations:

Insert a character at position $i$ in $O(\log \log m)$ (and thereby increasing the position of every subsequent character by 1).
Delete a character at position $i$ in $O(\log \log m)$.
Return the character at position $i$ in $O(\log \log m)$.

So, insert(0,'a') followed by insert(0,'b') results in "ba".

Even better would be this:

Return a 'pointer' to some index $i$ in $O(\log \log m)$.
Given a 'pointer', return the character at this position in $O(1)$.
Given a 'pointer', remove the character at this position in $O(1)$.
Given a 'pointer', add a character at this position in $O(1)$ and return a pointer to the following position.
(optional) Given a 'pointer', return a 'pointer' to the next/previous character in $O(1)$.


texts:
When using monitors for most concurrency problems, you can just put the critical section inside a monitor method and then invoke the method. However, there are some multiplexing problems wherein up to n threads can run their critical sections simultaneously. So we can say that it's useful to know how to use a monitor like the following:

monitor.enter();
runCriticalSection();
monitor.exit();

What can we use inside the monitors so we can go about doing this?

Side question: Are there standard resources tackling this? Most of what I read involve only putting the critical section inside the monitor. For semaphores there is "The Little Book of Semaphores".


texts:
I'm studying The Algorithm Design Manual and the proof exercises of the first chapter are really hard(at least for a first-timer). I asked a question on here about the previous question in the exercises two days ago and I still haven't been able to go through the whole page.
Anyway, I'm trying to inductively prove Euclid's algorithm(I'm think the deductive proof is simpler but I want to familiarize myself with Inductive proofs). No matter how I approach the problem, I just prove the algorithm in a deductive way that doesn't require induction in any way.
I would really appreciate if you could give an inductive proof of Euclid's algorithm or provide me with a resource that does so.Thanks in advance.
The greatest common divisor of positive integers x and y is the largest integer
d such that d divides x and d divides y. Euclid’s algorithm to compute gcd(x, y)
where x > y reduces the task to a smaller problem:

gcd(x, y) = gcd(y, x mod y)

Prove that Euclid’s algorithm is correct.

Edit:
The deductive proof that I know of is as follows:
A. given that a,b,c,y,x are all integers we can prove:
a|b ^ a|c → a|(xb + yc)
B. p,q,r and t = (pr + q) are all integers.we want to prove gcd(pr+q,p)=gcd(p,q)
let m = gcd(pr+q,p) and n = gcd(p,q)
since A, n|p ^ n|q → n|pr + q
n is a common divisor of (pr+q,p) and m is the greatest common divisor of (pr+q,p) therefore, m >= n.
C. P: m|p which we know is true
Q: m|(pr + q) which is also true
R: m|q
we know that m|p ^ m|q → m|pr + q is true, so based on this and P,Q and R we can deduce that R is true.
m is a common divisor of (p,q) and n is the greatest common divisor of (p,q) therefore, n >= m.
B is true
Q is true
B ^ Q → m = n is also true.
therefore, m = n
gcd(pr+q,p) = gcd(p,q)


texts: Algorithms for tabulating/counting/frequency counting?

texts:
It is common in data science to receive two equal length vectors (array of dimension 1), say Categories and Weights.

We aim to find all unique values of Categories and sum up the corresponding Weights. E.g.

Categories = ["abc", "def", "a", "a", "def"]
Weights =    [ 1   ,  2    , 1 ,  10 , 1000]

Let's call our algorithm/function groupsum then we calling it

groupsum(Categories, Weights)

should give a result like

("abc" => 1, "def" => 1002, "a" => 11)

One algorithm is to loop through the Categories and build up a hashtable where the key is the hashed values of Categories, and the value is the cumulative values of the corresponding Weights. This is called an accumulator.

I wonder if there are even cleverer ways that deals with large amount of data e.g. think vectors that are ~2 billion+ elements long may

Or there specialised algorithms for special Categories data type e.g. if Categories are UInt8 then we can skip the hashmap and use an array instead to keep the counter.

Any links to research welcome!


texts:
I use a very simple neural network to make classification between classes. Once my ANN is trained I'm able to present new and unknown data, and get a good classification.

Is there a simple way to reverse the process and create an artificial data, knowing at which class it should belong ?

What would be the method name ?

Thanks a lot !


texts: Do these answers work even when we change the values?

texts:
So I know that these are both true, but if I change the values would they still be true? Do these statements hold for any value?

A) Suppose f is a flow of value 50 from s to t in a flow network G. The capacity of the minimum s-t cut in G is equal to 50.

Suppose we were using 100 or maybe 75 instead of 50. Is this still true?

B) Suppose f is a flow of value 100 from s to t in a flow network G and there is an s-t cut of capacity 100. Then there are no s --> t paths in the residual graph Gf.

If we use 80, 60, 20 and so on is this still true? What about for odd numbers?


texts: Bisimilarity and Trace Equivalence in Labelled Transition Systems

texts:
I'm a bit confused regarding the relation between trace equivalence and bisimilarity. These lecture notes I found and a few others documents I've read state that "if an LTS is deterministic then two states are bisimilar if they are trace equivalent".

When reading around the topic I found this page, which shows the following image:

These LTS' are trace equivalent and deterministic(?), why does the rule not hold that they are then bisimilar?


texts: Difference between regular language and context free language

texts:
What is nature of difference of regular language and context free language?

My guess is

RL - CFL = RL
CFL - RL = CFL

Am I correct with this?


texts: Does music stop for a short interval while listening into it,maybe a milliseconds that we just doesnt sense it cause by interrupts for operating system to run other programs


texts: Constructing a DFA $M$ such that $L(M) = L(A) \bigtriangleup L(B)$ with a kind of log-space TM

texts:
Suppose that $A$ and $B$ are DFAs. We know that there is some DFA $M$ such that $L(M) = L(A) \bigtriangleup L(B)$, the symmetric difference. Also, we can construct this $M$ by some Turing machine $N$. But can we ensure that $N$ has the following form?

$N$ consists of (i) a read-only input tape, (ii) a work tape that is log-space with respect to $|\langle A, B\rangle|$, and (iii) a one-way, write-only, polynomial-time output tape.

This really comes down to showing that this kind of TM can construct DFAs for $L(A) \cup L(B)$ and $L(A) \cap L(B)$. But it's not clear to me how this would work.

Any help is appreciated.


texts: For a collection $S$ of weighted sets $S_i$, find those $k$ elements that maximise the sum of weights of all sets $S_i$ covered by them

texts:
I have a collection $S$ of sets $S_i$. Each $S_i$ has a weight given by how many times this set was observed in some data. I now want to find the $k$ elements that maximize the cumulative weight of all sets that can be covered by those elements (that is, those sets that contain only elements from those $k$ selected).

As an example, let $S$ consist of the following sets and corresponding weights:
$$
\{1\} = 20  \\
\{2\} = 10  \\
\{3\} = 5  \\
\{1,2\} = 10  \\
\{2,3\} = 40  \\
\{1,3\} = 5  \\
\{1,2,3\} = 5\\
$$

In this case, I want my solution for $k = 2$ to be $\{2,3\}$, as $\{1,2\}$ has a cumulative weight of $20+10+10=40$, $\{1,3\}$ has a cumulative weight of $20+5+5=30$ and $\{2,3\}$ has a cumulative weight of $10+5+40=55$.

I have the feeling that my problem resembles a maximum coverage problem, but with a limit on the elements, not the sets, and with the sets having weights instead of the elements.


texts: How can lazy learning systems simultaneously solve multiple problems?

texts:
On the english Wikipedia it says about lazy learning systems:

  Because the target function is approximated locally for each query to the system, lazy learning systems can simultaneously solve multiple problems […]

What does this mean? I can only guess what "approximated locally" is supposed to say but even then I have no idea how one is supposed to follow from the other.


texts: undirected graph without weights and DFS

texts:
following question on undirected graph without weights can be solved by using DFS and in O(|V|+|E|) times.

check that G is bipartite.
check G has one simple cycle.
find number of connected component G
with given two vertex u, v, find a path between u and v with minimum edges

anyone can describe, how the authors of this note claim that all of them can be checked with DFS and in O(|V|+|E|) times?


texts: Changing from Kernel mode to User mode (and vice versa)

texts:
I am reading Operating Systems book by Galvin. Galvin explains, what are kernel & user modes, instruction privileges given for both modes & also about mode-bit. But I am interested to know how mode changes from one to another. Basically I want to solve following question :

  A CPU has 2 modes, privileged and non-privileged. In order to change
  the mode from previledged to non-previledged

  a) A hardware interrupt is needed

  b) A software interrupt is needed.

  c) A privileged instruction is needed.

  d) A non-privileged instruction is need.

From what I understand,

from user mode to kernel mode - Hardware Interrupt is needed [like in Disk I/O]. Now, in case user program tires to access an memory which is beyond its permissible range, a trap occurs, which is basically a software interrupt which will be handled by OS. Now, in user mode we cannot execute any privileged instructions. So, a non-privileged instruction such as I/O request can change user to kernel mode. So I think, to change

  from non-privileged(user) to privileged(kernel) - H/W Interrupt, S/W
  Interrupt & non-Privileged instruction will do.

Now coming to, kernel to user mode. The OS can change kernel to user mode. So, it will simply run a privileged instruction to change from kernel to user mode. It does not need to generate either H/w or S/w interrupt. So I conclude, to change

  from previledged to non-previledged - a privileged instruction will
  do.

Am I right ?

Also when executing in kernel mode, all interrupts will be disabled right ? So answer cannot be (a) or (b). Also, since OS is basically a software, it cannot generate H/W interrupts.

Also, since OS itself handles interrupts, it does not make sense to me why has to generate a interrupt (& service it) to change from kernel to user mode.

Please let me know if I am wrong anywhere. Any help regarding this is appreciated.


texts: How to calculate Huffman code length without generating the actual huffman code?

texts:
Given a vector of elements, how can I calculate the length of the Huffman codewords without generating the Huffman code itself?

Using Matlab, I was able to compute the Huffman code and and get the length of the codewords but is it possible to get the lengths alone without computing the codewords?


texts: Let's say we have a pipeline with 20 stages. If the testing for the jump condition is done at stage 14 and we have a wrong prediction, then the instructions processed in those 14 stages, that shouldn't have been processed due to the wrong prediction made the processor lose 14 cycles. We know that the jump instruction entered the pipeline 14 stages back, therefore from this behaviour I deduced that 14 cycles were lost. Am I correct? If no, why?


texts: Why can't we solve the Halting Problem by using Artificial Intelligence?

texts:
Yesterday I was reading about Computability and they mention the Halting Problem. It got stuck in mind all day until I remember that some weeks ago, when learning Java, the IDE (Netbeans) show me a warning saying that my code was going to result in an infinite loop.

My question is, why can't this problem, be solved by using an "Intelligent" program to determine if another program will halt or end in an infinite loop? This hypothetical program could look for repetitive structures, conditions, etc and even predict under which circumstances (possible inputs) will halt, loop infinitely or end. Maybe like looking for the "acceptable range", like the domain of a mathematical function.


texts:
I'm reading through Algorithm Design by Kleinberg and Tardos and was working on Ch1 Q1. The question is about stable matching and their 'proof' is presented by contradiction. I have an alternative argument and want to know if its right. The question paraphrased is:

  Consider a town with n men and n women. Each man as a preference list
  that ranks the women and each women has a similar preference list. Of
  these men and women, k men are bad and k women are bad. So there are
  n-k good women and n-k good men. Each man prefers to match with a good
  women and vice versa. Therefore all preference lists rank the good
  people higher than bad people. Show that in every stable matching
  every good man is married to a good women.

My 'proof':

Assume that there is a pairing where a good man is matched with a bad women. Because there are the same number of good men and women, it means that there is one good woman, currently paired with a bad man, who rejected this good man. If she rejected this good man it means that he must be of lower preference than the bad man she is paired with. But this is a contradiction because a good man cannot be ranked lower than a bad man. It means that the good man is actually bad and there are more bad men than good women and the initial problem statement is false.


texts:
Let's say I have an array of numbers {a,b,c,d,e} and want to calculate the sum of product of all triples abc+abd+...+cde.
I can calculate it very fast without generating all triples using this formula
F(n,k)= k*F(n-1, k-1)+ F(n-1, k) with two loops

       int[] values={a, b, c, d, e...};
       int k = 3;
       int[,] F = new int[values.Count, k];
       ...
        for(int i = 0; i < values.Count; i++)
            for(int j = 0; j < k && j <= i; j++)
                F[i, j] = values[i] * F[i - 1, j - 1] + F[i - 1, j];

Now I have this array of groups {{a1,a2,a3..an}, {b1,b2,b3 ...bn}, {c1,c2...} } and every element of a triple must be in different group.
a1*b2*c1 is a valid triple but a1*a2*b1 is not allowed because a1, a2 are in the same group. It's possible to generalize the above algorithm to find the sum of valid triples (quadruple or n-tuple)?


texts: Is there a name for this tree traversal?

texts:
This came when I was looking at block scoping in compiler design.

{   A   { B }   { C {D} {E} }   }

For the above pseudo code, the order in which the scope varies as we scan left to right is A B A C D C E C A, where A to E represent scopes.

A parse tree can be constructed for the above pseudo code:

  A
 / \
B   C
   / \
  D   E

Is their a term for such a traversal order, which for the above tree is A B A C D C E C A?


texts: Can two deterministic turing-machines avoid each other in a sidewalk?

texts:
Imagine a turn-based game where two robots are placed on opposite sides of a 16x16 board, facing each-other. Each robot, at each turn, can perform one of 2 moves: move (moves forward), turn (turns 90 degree; clockwise for the first robot, anti-clockwise for the second). They can also send messages to each-other, and behave according to arbitrary deterministic computations.

|_|_|_|_|v|_|_|_|_|
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|^|_|_|_|_|

For simplicity, assume the behavior of the robots is determined by a Python function such as:

# just an example, not used
state = {}

# always go forwards
def brain(otherPos, myPos, message):
    return ("move", "hello")

This behavior is, of course, stupid, as it always goes forward and broadcasts the same message, ignoring the position of the other robot and the message sent by it. On this case, the robots would just go forward, until they colide and stop moving forever. But any logic could be implemented and the robots could collaborate in arbitrary ways. An improvement would be:

# just an example, not used
state = {turn: 0}

# always go forwards
def brain(otherPos, myPos, message):
    if state.turn === 0:
        return ("turn", "I'm turning")
    elif state.turn === 1:
        return ("move", "I'm moving horizontally")
    elif state.turn <= 4:
        return ("turn", "I'm turning again")
    else:
        return ("move", "Now I'm going forward, forever!")

This one would cause both robots to turn 90 degrees, move, then turn 3 times, and then move forward forever. They'd still collide and get stuck on the same column, though, because, as one turns clockwise, the other one turns anti-clockwise.

My question is: is it possible to program a brain function in such a way that, after N turns, each robot ends up on the other side?


texts: Does a deep feedforward neural net approximate a (single or multivariate)polynomial?

texts: Does composition of several linear transformation plus non-linear activation function in each layer and different layers (as they are in feedforward neural net) represent or approximate a multivariable polynomial? Here is what I am wondering about. Removing the affine linear transformation part of the neuron does chaining multiple non-linear function together approximate a polynomial? For example if we chain bunch of tang or sigmoid or even ReLU would they approximate a polynomial? for example $$tanh(W_2 * tanh(W_1 X+b_1) + b_2)$$


texts: Decidability of language of TMs which accept only their Gödel number

texts:
I am trying to prove that $L = \{\langle M \rangle  \mid L(M) = \{\langle M \rangle \}\}$ is undecidable, where $\langle M \rangle$ is the code of the TM $M$, and $L(M)$ the language recognized by $M$.

I think I can't use Rice's theorem, so I tried to find a reduction. The halting problem for example does not help me in this case. Do you have any idea how to prove it?


texts:
By Stirling's Approximation $n! = \sqrt{2*\pi*n} * [n/e]^n * e^\alpha$

Therefore $T(n!) = O(n^n)$

$O(n^n) \neq O(2^{n \lg n})$

Is this correct? Is there another way to get this result if it is correct? Thanks.


texts: How to correctly contract an edge in a network?

texts:
Assuming an adjacency list as data structure of a directed Graph, it is not completely clear to me how "contraction of an edge" is defined.

Let me cite the definition I do have at hand:

Source: JAMES B. ORLIN - A FASTER STRONGLY POLYNOMIAL MINIMUM COST
FLOW ALGORITHM, Section 4.1. Contraction

  [...] any edge, say $(k, \ell)$, can be contracted into a single node $p$. The contraction operation consists of: letting $b(p) = b(k) + b(\ell)$ and $e(p) = e(k) + e(\ell)$; replacing each
  edge $(i, k)$ or $(i, \ell)$ by the edge $(i, p)$; replacing each edge $(k, i)$ or $(\ell, i)$ by the edge $(p, i)$; and letting the cost of an edge in the contracted network equal that of the edge it replaces.[...]

$b$ and $p$ are functions defining values for certain properties of a node; their meaning is unimportant for understanding contraction.

Consider the following graph described in "adjacency speak", where e.g. node 0 has an edge to the nodes 1, 2 and 5; node 5 has no outgoing edges; node 3 has an edge to node 4 and so on...

0 -> 1, 2, 5
1 -> 2, 3
2 -> 1
3 -> 4
4 -> 5
5

Now I want to contract the edge $(1,2)$. Note that there is an edge $(2,1)$, too. Should the application of the contraction operation yield the following directed graph, where the newly introduced node $p$ has the id $6$?

0 -> 6, 5
3 -> 4
4 -> 5
5
6 -> 3, 3, 5, 6 # Note that we got two edges from node 6 to node 3.
                # Note that we also have an edge from 6 to 6, i.e. a loop.

Thanks a lot!


texts: Looking for a contex-free grammar for the following language

texts:
I want to derive a context free grammar for the following language on alphabet $\Sigma=\{a,b\}$:

$\qquad\displaystyle \{ xax'yby'z \mid x,y,z\in\Sigma ^*, |x|=|x'|, |y|=|y'|, |z|=|x|+|y|\}$

I am convinced that this language is context-free because this is part of my proof to a theorem given in textbook, but haven't yet seen a context-free grammar for it.


texts: How much does regularization prevent overfitting?

texts:
I've been curious why machine learning algorithms with high VC dimension, such as XGBoost and deep learning, do well in practice.  The answer appears to be regularization significantly restricting the parameter space, but the only justifications I've seen are references to Occam's razor.

Is there quantitative/theoretical understanding of how much regularization can prevent overfitting in a model?

Background:
I've taken a course in machine learning and covered the theory behind regularization and a couple techniques, such as lasso and ridge regression.  I understand the principle that regularization can reduce the VC dimension by minimizing or zeroing weights in the model.

But, that principle does not clarify in my mind whether regularization is adequate to counteract the high VC dimension in models used by XGBoost and deep learning.

I am asking for some sort of quantitative theory that provides justification that even with high VC dimension regularization can reduce the dimensionality enough to provide a decent guarantee of generalization.

Alternatively, providing a method I can use to figure this out myself is also acceptable.


texts: How to prove intersection between languages L1 (belongs to NP) and L2 (belongs to P) actually belongs to NP?

texts:
I have to prove that if L <=p L1 intersection L2, where L1 and L2 are described as above, L belongs to NP.

I thought about the definitions of P and NP and built a DTM D that decides L2 and a NTM N that decides L1. Then I tried to build a NTM NN that accepts when both D and N accept on some input w.

Now,did I really prove that intersection between L1 and L2 is in NP by constructing NTM NN? Thx in advance


texts: Why is the counting variant of a hard decision problem not automatically hard?

texts:
It is well-known that 2-SAT is in P. However, it seems quite interesting that counting the number of solutions to a given 2-SAT formula, i.e., #2-SAT is #P-hard. That is, we have an example of a problem for which decision is easy, but counting is hard.

But consider an arbitrary NP-complete problem (say 3-COL). Can we immediately say something about the hardness of its counting variant?

Really what I'm asking is: why do we need another proof to show a counting variant of a hard decision problem is also #P-hard? (Sometimes you see parsimonious reductions that preserve the number of solutions, and so on). I mean really, if the counting problem was easy, you could automatically solve the decision problem as well! So how could it not be hard? (OK, maybe it is hard, but I'm not sure for what definition of hard).


texts: Find most stable combination of a vector with itself at different periods

texts:
I receive a vector of varying length such as [0, 1, 2, 3, 2]. The value corresponds to the yield and its position to a time slot. Hence, at the first time slot the yield is zero, at the second period it is 1, etc.

I need a procedure that can combine this vector with itself at varying periods in order to ensure that the sum of the yields are the "most possibly" stable. Ideally it will be completely but I doubt that it is always possible.

I also need to make sure that it is indeed a periodic solution.

Below 2 examples that I solved by hand and a list of other example I don't know how to solve:

First one:

     [0, 1, 2, 3, 2]   [0, 1, 2, 3, 2]
           [0, 1, 2, 3, 2]   [0, 1, 2, 3, 2]
                 [0, 1, 2, 3, 2]   [0, 1, 2, 3, 2]
sum = 0  1  2  4  4  4  4  4  4  4  4  4...
In this example after an initialization period of length 3, we get a stable
pattern with a yield of 4

Second one:

     [0, 0, 0, 1, 0, 1, 0, 1]            [0, 0, 0, 1, 0, 1, 0, 1]
        [0, 0, 0, 1, 0, 1, 0, 1]            [0, 0, 0, 1, 0, 1, 0, 1]
                       [0, 0, 0, 1, 0, 1, 0, 1]            [0, 0, 0, 1, 0, 1, 0, 1]
                          [0, 0, 0, 1, 0, 1, 0, 1]            [0, 0, 0, 1, 0, 1, 0, 1]
sum = 0  0  0  1  1  1  1  1  1  1  1  1  1  1  1  1  1...
In this example after an initialization period of length 3, we get a stable
pattern with a yield of 1

However I could not find a pattern for the following vectors and I am searching for an algorithm that could identify the best pattern for any such one:

[0, 0, 2, 3, 2]
[0, 0, 2, 0, 3, 0, 4, 0, 2]

Precision 1: The vector will always start with at least a zero, but there can be many more, and it will always finish with a value above zero.

Precision 2: The solution should be the shortest periodic design that allows a stable sum of yield.

Retry at the problem specification: We have a production mean 'A' to grow plants. Each plant has specs as to how it grows, represented by a given vector as presented above. For a given 'A', once a plant production cycle is over, you can start a new one. We want to model a stable plant production with as few 'A' as possible.


texts: 2-Dimensional interval scheduling problem

texts:
I have a problem that is similar to the conventional interval scheduling algorithm but it is two dimensional, so I have another metric to take into account. My dataset format:
Cars with the start and end time of parking, along with their length in meters.
Total street length in meters.
Number of cars.
Opening hours of street parking.
Start and end times are in whole hours and length in whole meters.
I was thinking of splitting the street up into short 1 meter segments, but that wouldn't ensure a best solution as I wouldn't be able to optimize the locations based on later segments.
Objective:
The goal is to fit all cars in the street parking (Assumed possible). Output will be the location of the car during the given time period.


texts: What are the (efficient) algorithms to cluster squares into groups using a threshold such that the closest squares form groups?

texts:
I have a set of rectangles that needed to be grouped based on their locations.
(All the rectangles follow the same orientation.) Two rectangles would be in the same group if the distance between them is less than a certain (constant) threshold.

The obvious algorithm will find all groups in ${O(n^2)}$ time. What I am looking for is an efficient algorithm that can perform better.


texts: Most stable algorithm to solve a system of linear equations?

texts:
I am doing some image processing involving solving a system of linear equations. I am getting some errors and bits of the image looks corrupted. I would like to know what is the most stable way to solve these systems (I don't care how much cpu it takes to compute). It should try to avoid roundoff, catastrophic cancellation, etc.

What would be the most robust algorithm for this?


texts: What is the complement of the language with all ucv with u ≠ v?

texts:
If $L = \{w_1cw_2: w_1,w_2 \in \{a,b\}^* , w_1 \neq w_2\}$ what is the complement of language L? one of my friend said that it is $\overline{L} = \{w_1cw_2: w_1,w_2 \in \{a,b\}^* , w_1 = w_2\}$ and he said that we can ignore $c$ and it's not in $\Sigma$ of language $L$. but I think $c$ should be in $\Sigma$ of language $L$ and the complement mentioned above is wrong based on definition of complement that is $\{a,b,c\}^* \backslash L$. which answer is right?

Based on transition relation of pushdown automata where is maping from $(Q\times (\Sigma \cup \{\lambda \}) \times \Gamma) $ to $(Q \times \Gamma^*)$ so if we construct a pushdown automata for string $aabcabb$ for example here $c$ should be in $\Sigma \cup \{\lambda \}$.


texts: Is $\{w~|~\forall x \in T(M_v):|w|>|x|~\}$ decidable?

texts:
I want to ask if $\{w|\forall x\in T(M_v):|w|>|x|\}$ is decidable if v is a Index of a random but fixed Turing Machine with $|T(M_v)|<\infty$.
My idea:
It is co-semi-decidable since as soon as i find an $x\in T(M_v)$ with $|x|\geq |w|$ I have shown that this sepcific w is not in the set. I think it aint semi-decidable, since there can always be an $x\in T(M_v)$ which is longer than w. Therefor i also think the problem ist undecidable.
Do i oversee something ?


texts: How can I develop a pseudo-polynomial time algorithm for a non-integer problem?

texts:
I have an scheduling probelm with a set of jobs $J$, with a ''non-integer'' parameter $\beta_j$, i.e. the parameter is a real number and $\beta_j \leqslant 0.5,  \exists j \in J$.

Since the problem will be trivial if $\beta_j > 0.5, \forall j \in J$, I can not assume that we may transform an instance to an integer one. By the way, I am looking for the computational complexity of the problem.

So my question is: How can I develop a pseudo-polynomial time algorithm for the problem (to indicate that it is at most NP-hard in the ordinary sense), although the problem is not integer-value?


texts: Subset Sum: reduce special to general case

texts:
Wikipedia states the subset sum problem as finding a subset of a given multiset of integers, whose sum is zero. Further it states that  it is equivalent to finding a subset with sum $s$ for any given $s$.

So I believe as they are equivalent, there must be a reduction in either side. The one from $s$ to zero is trivial by setting $s = 0$. But I had no luck finding a reduction from zero to $s$, i.e. given a set of integers $A$, construct a set of integers $B$ containing a subset with sum $s$ (for any $s$), if and only if there is as subset of $A$ with sum zero.

Can you give me some pointers?


texts: Determine if a vertex is a part of a cycle in O(m+n) complexity

texts:
I am trying to apply BFS to the following problem, but I'm not sure how to do it

Input: directed graph $G$ defined by the array of adjacency lists with n vertices and m edges, and a vertex $v$ in $G$
Output: $true$, if $v$ is a part of a cycle, $false$ otherwise

Can someone explain in pseudocode or in words how to do this?


texts: Is there any correspondence between SUM type in type theory and arithmetical summation?

texts:
Is there any correspondence between the coproduct(sum) type in type theory and arithmetical summation?

For example what does 3+4 or x+6 mean in type theory?


texts:
I often read in Complexity literature that NP∩coNP is unlikely to have any complete problems. Is that unlikelihood "proved" ?

By proved, I mean that there would be a theorem that would relate the existence of such a problem to, by instance, the collapse of PH, or any other equality that is strongly believed not to hold (and that at least would be a major breakthrough).


texts: Selecting k rows and k columns from a matrix to maximize the sum of the k^2 elements

texts:
Suppose $A$ is an $n \times n$ matrix, and $k \ge 1$ is an integer.  We want to find $k$ distinct indices from $\{1, 2, \ldots, n\}$, denoted as $i_1, \ldots, i_k$, such that

$\sum_{p, q = 1}^k A_{i_p, i_q}$

is maximized. In words, we seek $k$ rows and the corresponding $k$ columns, such that the intersected $k^2$ elements of $A$ have the largest sum.

This problem can be formulated as a quadratic assignment problem, which is NP-hard and admits no polynomial time algorithm with constant approximation bound. I'm just wondering if for this specific problem (as a special case of quadratic assignment), there exists a poly-time algorithm with constant approximation bound. Thank you.


texts: How to decide if a propositional formula is a well formed?

texts:
So, I have the following propositional formula:
(((P → Q) ∨ S) ↔ T)
How do I decide if it's well formed?


texts: 3-SAT wher each literal appears at most once

texts:
I'm currently following a course and we have to prove that a restricted version of the 3-SAT decision problem where each literal appears at most once is solveable in polynomial time.

I think such a problem is always satisfiable since we can just assign any sub-expression the needed truth value without it interfering with the rest of the expression. My reasoning is that if we have any literal $p$ we can freely assign any truth value without interfering at all with any other part of the expression since $p$ is guarantied to not occur in any other part of the expression.

I don't think that is what my professor meant so I am wondering whether my reasoning is correct or what I am doing wrong.


texts: How can I efficiently plot the inside of an ellipse?

texts:
I am given the the coefficients for an ellipse in the form:
$$Ax^2 + Bxy + Cy^2 + Dx + Ey + F=0.$$

I have a 2 dimensional array of point objects (in Python) called "pixels", and I need to give each point a "count" if they lie inside the ellipse.

I initially tried iterating through every point with a loop like:

for row in pixels:
    for pixel in rows:
        x=point.get(pixel)[0]
        z=point.get(pixel)[1]
        if a*(x)**2 + b*(x*z) + c*(z)**2 + d*(x) + e*(z) + f >0:
            pixel.addpcount()

But this is taking way too long because I have several thousand ellipses I need to do this for. Is there a way I can efficiently do this?

(If this is not the right place to ask this question, I apologize.)

Edit:
(I don't have enough reputation to comment).
The Python is mostly irrelevant to my question at hand. I just want a better algorithm instead of iterating through every point.

In order to determine whether something is inside an ellipse, I am actually using this test https://math.stackexchange.com/questions/817130/how-to-determine-if-arbitrary-point-lies-inside-or-outside-a-conic.

The user Evil suggested using Axis Aligned Bounding Box. Does this mean finding the box which bounds an ellipse, and then testing only those points inside the box? That would seem a lot more efficient.

Greybeard, I am not sure what the Bresenham algorithm is, but I will take a look.


texts: Algorithm to find k elements following the median in sorted order

texts:
I have the following problem:

Given an unsorted array A of size n, print the first k elements in A larger than its median.

Here's my approach to the problem:

     1. Create a minHeap and a maxHeap
     2. Iterate over elements in A // O(n)
        - if maxHeap.count < minHeap.count
             insert current element to maxHeap // O(log(n))
          else:
             insert current element to minHeap // O(log(n))
     3. if maxHeap.count < minHeap.count:
              median = minHeap.extractMin()
     4.  output k elements from minHeap  // O(klog(n))

This maintains a maxHeap of elements less than the median and a minHeap of elements greater than or equal to the median. But from my analysis, this seems to take O(nlogn + k(log(n)) which is no better than sorting A first and grabbing A[n/2:n/2+k] in just O(nlog(n) + k).

Now I have 2 questions:

Is my analysis tight? I am doubtful since the heaps have at most i elements in the ith iteration, not n.
Is there a better algorithm? Maybe something like O(n+klog(k))?


texts: Space efficient representation of Regular graphs

texts:
Let $G$ be a $k$-regular graph (each vertex have a degreee $k$). It is trivial to store the graph in $O(\log n)$ space or words such that $j$th neighbour of any vertex can be found in $O(\log n)$ time. Assume that neighbours of each vertex are ordered.

Note that $k=O(\log n)$

Is there an representation of graph $G$ that takes $o(nk)$ space in words such that query can be solved in $O(1)$


texts: Why should one not use a 2^p size hash table when using the division method as a hash function?

texts:
I don't understand what is meant by:

"m should not be a power of 2, since if m = 2^p, then h(k) is just the p lowest-order bits of k." (pg. 231 of CLRS)

Terms defined:

m: size of hash table
h(k): hash function = k mod m
k: key

I don't understand what the p lowest-order bits of k means. Any clarification would be very helpful.


texts: Why does this greedy algorithm fail to accurately determine whether a graph is a perfect matching?

texts:
I came across this problem in Tim Roughgarden's course on Coursera:

  In this problem you are given as input a graph $T=(V,E)$ that is a
  tree (that is, $T$ is undirected, connected, and acyclic). A perfect
  matching of $T$ is a subset $F \subseteq E$ of edges such that every
  vertex $v \in V$ is the endpoint of exactly one edge of $F$.
  Equivalently, $F$ matches each vertex of $T$ with exactly one other
  vertex of $T$. For example, a path graph has a perfect matching if and
  only if it has an even number of vertices.

  Consider the following two algorithms that attempt to decide whether
  or not a given tree has a perfect matching. The degree of a vertex in
  a graph is the number of edges incident to it. (The two algorithms
  differ only in the choice of $v$ in line 5.)

Algorithm A:

While T has at least one vertex:
  If T has no edges:
    halt and output "T has no perfect matching."
  Else:
    Let v be a vertex of T with maximum degree.
    Choose an arbitrary edge e incident to v.
    Delete e and its two endpoints from T.
[end of while loop]
Halt and output "T has a perfect matching."

Algorithm B:

While T has at least one vertex:
  If T has no edges:
    halt and output "T has no perfect matching."
  Else:
    Let v be a vertex of T with minimum non-zero degree.
    Choose an arbitrary edge e incident to v.
    Delete e and its two endpoints from T.
[end of while loop]
Halt and output "T has a perfect matching."

Now, the answer key says:

  Algorithm $A$ can fail, for example, on a three-hop path. Correctness of
  algorithm $B$ can be proved by induction on the number of vertices in $T$.
  Note that the tree property is used to argue that there must be a
  vertex with degree $1$; if there is a perfect matching, it must include
  the edge incident to this vertex.

However, I think I found a counter-example which shows that Algorithm B may not be correct. Am I missing something?  Consider the following graph (say $T$):

If we follow B:

Step 1: Let $v=3$ (all vertices have the same degree) and $e=(2,3)$. Remove $e$ along with vertices $3$ and $2$.

Step 2: Let $v=1$ and $e=(0,1)$. Remove $e$ along with vertices $0$ and $1$.

Step 3: No vertices are left. Hence we get the output: "T has a perfect matching."

But clearly, our original graph was not a perfect matching as all the nodes were of degree $3$.

Note: I assumed that ties are meant to be broken arbitrarily by the algorithm.


texts: Why $P$ cannot have NULL string in Arden's Theorem?

texts: Arden's Theorem says that in the equation $R=Q+RP$, the $P$ cannot have NULL string. In this respect,the theorem will not be valid for the expression $R=Q+R(NULL+01)$. Am I correct? If so, then what will be the justification?


texts: How do the bits of a certain emoji code for all the colors?

texts:
I am watching an introductory course on computer science. At one part, it starts talking about unicode and how the bits 11111011000000010. He states that that codes for a laughing/crying face emoji.

However, he later on talks about how the pixels are each created through a number of bytes.He says the bytes 72, 73 and 33 make light red, light green and light blue.

My question is, if there are so many bytes which make up all those pixels in an emoji, how do the bits 11111011000000010 represent all those pixels of colour?


texts: What is the specific name for basic data types?

texts: What is the specific name for data types such as integer, string, real (the basic ones)?


texts: Merging of two convex polygon chains in O(log n)

texts:
Assume I have a polygon chain implementation which is backed by a key-value store which stores the position of a point inside the chain as key and the point itself as value. So a polygon chain of the points $p_1\rightarrow p_2\rightarrow p_3$ is stored as $\{0\Rightarrow p_1,1\Rightarrow p_2,2\Rightarrow p_3\}$. The key-value store is implemented with a data structure which allows the operations split and join in $O(\log n)$ time.

I want to join the chain $P = p_1\rightarrow p_2\rightarrow p_3$ and the chain $Q = q_1->q_2->q_3$ to a chain $p_1\rightarrow p_2\rightarrow p_3\rightarrow q_1\rightarrow q_2\rightarrow q_3$.

Is there a way to join two polygon chains in logarithmic time without updating the keys? If I do a simple join, I get a problem with duplicated keys, so the keys of $Q$ have to be updated before the join, but this destroys my logarithmic time approach as I need linear time for updating the keys.

Am I wrong here already?

If not, is there a way to keep the logarithmic time?


texts: Why using Hyper-threading can lead to performance degradation

texts:
I have read it at various places like this, that Hyper-threading leads to performance degradation.
I am unable to get why or how hyper-threading leads to degradation.
Why it is so that even when Hyper-threading allows the OS to utilize free resources does the degradation happens.
Though benchmarks does indicate hyper-threading as the culprit but can someone explain me the reason for this.
Thanks


texts: Show $\{1^n0^m |\space n \neq 2^m\}$ not regular using pumping lemma

texts:
Showing that the language $L$ with  $\{1^n0^m |\space n \neq 2^m\}$ is not regular using Myhill-Nerode is easy: Let $i, j\in \mathbb{N}.i\neq j.$ It follows $1^{2^i}\nsim 1^{2^j}$ because $1^{2^i}0^{i}\notin L$ but $1^{2^j}0^{i}\in L$. Therefore $L$ has an infinite amount of Myhill-Nerode equivalence classes and is not regular.
But how do I show this using the general version of the pumping lemma for regular languages? https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#General_version_of_pumping_lemma_for_regular_languages


texts: Stateless pseudorandom/hash algorithm for ℤⁿ → [0,1)

texts:
There's a problem which I had on a number of unrelated occasions which I usually work around in some way or another. Deep inside, though, it bothers me that I haven't ever found a “proper” solution to this:

  Given an n-tuple of integers, how do I derive a stateless pseudorandom number / hash value in the half-open interval [0,1)?

The usual “solution” people use in this situation is to multiply the parameters by some large primes, or bit-shift them, or do any other complex calculation which produces a result that is “random enough” for the given purpose.  I guess these algorithms have been cargo-culted over a long time, maybe from a PRNG implementation.

Instead of copying one of the circulating code snippets, I'd like to really understand what's going on here.  Is there an algorithm or a set of algorithms which should typically be used in this kind of situation, and if so, what's the proper way to choose the constants?


texts: Backpropagation Through Time Recursive Algorithm

texts:
Would it be plausible to write a recursive version of backpropagation through time for recurrent neural network training? I've only found the iterative version:

http://en.wikipedia.org/wiki/Backpropagation_through_time


texts: What is wrong with the following $P$ problem?

texts:
Our teacher gave us the following statement and we were wondering what is wrong with it.

  Consider an array $A$ of $n$ distinct numbers. Since there are $n!$ permutations of $A$,
  we cannot check for each permutation whether it is sorted, in a total time which is polynomial in $n$.
  Therefore, sorting $A$ cannot be in $P$.

Obviously this is wrong.
My friend thought it should just be: therefore sorting $A$ cannot be in $NP$.
Is this correct or are we thinking about it to easily?


texts:
I have these 4 symbols with their probabilities:

 x   P(x)
 --------
 1   0.3
 2   0.3
 3   0.2
 4   0.2

I built the Huffman tree in this way:

and I obtainded:

 x   P(x)   C(x)
 ----------------
 1   0.3     0
 2   0.3     10
 3   0.2     110
 4   0.2     111

it's correct? Because according to the solution the results should be:

 x   P(x)   C(x)
 ----------------
 1   0.3     00
 2   0.3     01
 3   0.2     10
 4   0.2     11

Why?
Yet I followed the steps shown here.


texts: Nearest Insertion Traveling Salesman Heuristic: is it faster to insert nearest nodes first?

texts:
I am trying to implement the nearest insertion TSP heuristic. However, I am wondering if it matters which node I insert into the subgraph first.

For example, should I start with one node; calculate the distance between this node and the other nodes; and sort the other nodes by this distance? Then, I will insert the closest node (to the first node) first. Will this be faster than randomly choosing nodes to insert?


texts: Example on Referential transparency (wikipedia)

texts:
I have a rather foolish question on an example
explaining the idea behind Referential transparency
Here is given an example i not understand:

Consider a function that returns the input from some source.
In pseudocode, a call to this function might be GetInput(Source)
where Source might identify a particular disk file,
the keyboard, etc. Even with identical values of Source,
the successive return values will be different.
Therefore, function GetInput() is neither deterministic nor
referentially transparent.

I'm confused about the claim that
even with identical values of (variable) Source,
the successive return values will be different.
Eg if I tap an 'a' on my keyboard and apply GetInput(Source),
it gives my 'a' as output. Then I tap again an 'a',
which of course is identical to my previuos input.
Next application of GetInput(Source) gives me again 'a'.
Therefore I not understand how is it possible that
GetInput(Source1) and GetInput(Source2) might give
different values if the two imputs Source1 and Source2
are identical. Sorry, if it's too dumb, but I not understand
this quoted example.


texts: Trying to remove ϵ rules from a formal grammar resulted in L(G) ≠ L(G')

texts:
I am trying to remove ϵ rules from the following grammar (after applying the remove redundant symbols algorithm): $G = (\{S,A,B,C\},\{0,1\},P,S)$, where the productions are
\begin{align}
&S \to AB \mid C \\
& A \to 0A1 \mid \epsilon \\
&B \to 0B \mid 0 \\
&C \to 0C0 \mid B
\end{align}
The result of applying the remove ϵ rules algorithm is:
\begin{align}
&S \to B \mid C \mid AB \\
&A \to 0A1 \\
&B \to 0B \mid 0 \\
&C \to 0C0 \mid B
\end{align}
but then, when I re-apply the remove redundant symbols algorithm (as I should do) I get:
\begin{align}
&S\to B \mid C \\
&B \to 0B \mid 0 \\
&C \to 0C0 \mid B
\end{align}
(as $A \Rightarrow^*$ will never result in a terminal word)
The problem is, that $010$ is generated by the original grammar but not by the latter grammar.
in fact, not a single word that contains 1 in it belongs to the latter grammar, as 1 could only have been achieved via $A$!
What have I done wrong? Why are the two grammars producing different languages? They are supposed to be the same.


texts:
When I was explaining the Baker-Gill-Solovay proof that there exists an oracle with which we can have, $\mathsf{P} = \mathsf{NP}$, and an oracle with which we can have $\mathsf{P} \neq \mathsf{NP}$ to a friend, a question came up as to why such techniques are ill-suited for proving the $\mathsf{P} \neq \mathsf{NP}$ problem, and I couldn't give a satisfactory answer.

To put it more concretely, if I have an approach to prove $\mathsf{P} \neq \mathsf{NP}$ and if I could construct oracles to make a situation like above happen, why does it make my method invalid?

Any exposition/thoughts on this topic?


texts: On complexity of the sieve, start crossing at the square of p - Part II

texts:
Ok, this is a follow up question to this, about the Erathostenes Sieve.

If we look at this paper (page 3, footnotes), the author says:

  If we start crossing off at $p^2$ rather than $p$, the number of
  composites we cross off is $\frac{n}{p}−p+1$, but it makes no significant
  difference to our sum, because it only subtracts an irrelevant
  $O(n/ \log n)$ factor

The total cost counting crossings is:

$$\sum_{p\leq n}\bigl(\frac{n}{p}-p+1\bigr)=n\sum_{p\leq n}\frac{1}{p}-\sum_{p\leq n}p+\sum_{p\leq n}1$$

The first sum would give us the known $O(n\log\log n)$. But I don't see the second sum to be an "irrelevant $O(n/\log n)$", so how is that?

According to this post in math overflow an upper bound for the sum of the primes up to $n$ is:
$$\frac{n^2}{2\log n} + O\left(\frac{n^2}{\log^2 n}\right).$$


texts: Is building this tournament fixture an NP-Hard / NP-Complete problem?

texts:
I'm curious to know if this problem is NP-Hard / NP-Complete, which I believe would mean I'm unlikely to find a polynomial-time algorithm to solve it.

I have written a program which randomly generates a tournament fixture, and I call it many times to try to pack the matches into the smallest number of rounds.

When it comes to complexity theory I am still a novice, so laymen's terms would be appreciated.

Inputs:

a set of countries, each of which may enter one or more entrants to the tournament (e.g. Australia might enter two entrants, UK might enter three entrants, and South Africa might enter one entrant)

Constraints:

each match consists of two entrants playing against each other
during a round, an entrant can only play in a single match
no entrant wants to compete in a match against another entrant from the same country
no entrant wants to compete against another entrant more than once in the tournament
each entrant must play the exact same number of matches overall
the number of matches each entrant must play is determined by MIN(for each entrant, total number of possible matches that satisfy the other constraints)

For example, say we have the following entrants:

AU #1 and #2
UK #1, #2 and #3
SA #1

The possible matches in this (artificially small) case are:

AU1 v. UK1   AU1 v. UK2   AU1 v. UK3   AU1 v. SA
AU2 v. UK1   AU2 v. UK2   AU2 v. UK3   AU2 v. SA
UK1 v. SA    UK2 v. SA    UK3 v. SA

Since we want each entrant to play the exact same number of games, the maximum number of games per entrant is three (this can be derived from the total number of entrants (6) less the number of entrants from the largest country (3)).

Since there are six entrants in total, and there are two entrants to each match, the maximum number of courts we can utilise in a round is 3.

A sample fixture is:

          Court 1      Court 2      Court 3
Round 1   AU1 v. UK1   AU2 v. UK2   UK3 v. SA
Round 2   AU1 v. UK2   AU2 v. UK3   UK1 v. SA
Round 3   AU1 v. UK3   AU2 v. UK1   UK2 v. SA

This is a nice example because it's easy to find a solution where each entrant has played exactly 3 games each, and they all pack perfectly into 3 rounds across 3 courts. Two of the possible 11 matches have not been played, but we don't care. We sum the results from each entrant's 3 games to determine an overall ranking, which is then used to generate the finals matches.

I have other scenarios where there are more entrants and I have been unable to pack them so neatly, but by running my program many times it almost always finds a near-optimal packing where the number of rounds and unused courts is minimised.

Output

The first problem is if there is a polynomial-time algorithm to generate an optimal fixture.

The optimal fixture is defined by:

minimum number of unused courts (which implies minimising the number of rounds)

The second problem is, given a fixture "A", how to determine if it is an optimal solution, i.e. is it possible to prove that there can exist no better packings for a given set of entrants. If "A" involves no unused courts in any round, then the answer for that one is clearly "Yes" - but if there are any unused courts in any round, the answer is, I think, difficult to derive.


texts:
i, sq ← 1, 1
while sq < n
    for j ← 1 to sq
        k ← 1
        while k ≤ j
            k ← 2 ∗ k
    i ← i + 1
    sq ← i ∗ i

I have Expressed the running time of the for loop as a sum in this way :
$$\sum_{j=1}^{i^2} log(j)$$
In a similar way, how can I express the running time of outer while loop with sigma in terms of i ?
I have tried the following:
$$\sum_{i=1}^\sqrt{n} i^2log(i)$$


texts: Can one get Turing-completeness without nontermination?

texts:
As I'm reading the movfuscator paper by Stephen Dolan, I encounter this claim:

  In order to have Turing-completeness, we must allow for nontermination.

This seems like a reasonable statement. But I'm also aware of this work by Wouter Swierstra which aims to prove quite the opposite (as I see it): that one can simulate a Turing-complete machine in a total language such as Agda.

From a purely theoretic point of view: I'm somewhat confused. Total languages permit only total functions, and total functions always terminate. Yet there exists a total interpreter of a Turing-complete language. Can somebody help reconcile this confusion?

Is nontermination necessary for Turing-completeness? Is this a valid question at all?


texts: Finding a lower bound for the expression $\ln^k(n)$

texts:
Problem:
Assume that $k \geq 1$ and $\epsilon \geq 0$, is $\ln^k(n) \in$ $\Omega( n^\epsilon)$?
Answer:
In the special case of $\epsilon = 0$, I claim the answer is no. I suspect the person who wrote this
problem meant to write: assuming $\epsilon > 0$.
I claim that if we differentiate $\log^k(n)$, k times then we get an expression with $n^{-k}$ in it. If
we differentiate $n^{e}$  k times then we get an expression with $n^{\epsilon- 2}$ in it. Let me illustrate
this with an example. Suppose I pick $k = 2$. Then if I differentiate the first expression twice, I get:
$$ \frac{ 2 - 2 \ln(x) }{x^2} $$
When I differentiate the second expression twice, I get:
$$ \epsilon ( \epsilon - 1 ) n ^ { \epsilon - 2 } $$
Hence, I claim the answer is no. Do I have this right?


texts: What's wrong with my beta reduction of pred c_0 on Church numerals?

texts:
I'm trying to calculate $\text{pred}\, c_0$, where $\text{pred}$ is the previous church encoded number and $c_0$ is the number $0$ ($\lambda s. \lambda z. z$).

The formula for $\text{pred}$ is $\lambda n. \lambda s. \lambda z. n (\lambda g. \lambda h. h (g s))(\lambda u.z)(\lambda v.v)$

My $\beta$ reduction looks like this so far (I've underlined the function and the applied parameter)

$$
\text{pred}\, c_0 \to \lambda s. \lambda z. c_0 \underline{(\lambda g. \lambda h. h (g s))}\text{ }\underline{(\lambda u.z)}(\lambda v.v) \to $$

$$\lambda s. \lambda z. c_0 (\lambda h. h (\underline{(\lambda u.z)}\text{ } \underline{s}))(\lambda v.v) \to$$

$$\lambda s. \lambda z. c_0 \underline{(\lambda h. h z)}\text{ }\underline{(\lambda v.v)} \to$$

$$\lambda s. \lambda z. \underline{c_0}\text{ } \underline{z} \to$$

$$\lambda s. \lambda z. (???)$$


texts: Choice of machine learning algorithms frequency of parts of speech

texts:
I'm new to machine learning. I have text, and I tag the text according to their parts of speech tag ie walk is tagged as verb, etc. I tag entire sentences, and then convert them into a vector based on their frequency like so:

Dan, walk the dog - > noun,verb, definite-article, noun -><2,1,1> (2x nouns, 1 verb, 1x DA).

The sentences each belong to one of two classes. I've performed a Kolmogorov–Smirnov test on each tag and picked the ones with the lowest P-value to use. I've used a couple of the models provided by scikit but each time I'm only getting around 55-56% accuracy. The models I've tried are: Gaussian Naive Bayes, K-Nearest Neighbours, SVM, Decision Tree, Random Forest Classifier, Quadratic Discriminant Analysis...

I'm asking if anyone has any comments or pointers about these methods? Should I be using different machine learning methods? Am I going about this problem completely wrong? I would really appreciate any input.


texts: What is the average runtime of appending items to arrays?

texts:
It is the time of the year again in colleges for final exams and I am preparing mine as of now and I am finding myself in hot water when it comes to understanding the running times of appending items to arrays in C.

Basically, I know there are different ways of appending items to an array, but please consider this method of appending and it's average runtime. I have managed to find its other runtimes, but not it's average.

This method to append items was introduced to me in class, and the trick is to double the size of the array when it is full, while keeping track of the next free element.

From my analysis (I hope I am right here..)  we see that the price to append something is O(n) when the array is maxed out because a new array of size x2 needs to be made, and the values in the old array has to be photocopied over. However, if our array isn't maxed out then we can just append an item to the end and we get O(1) runtime.

Can someone explain to me what the average case is and what it would be in Big O notation? I am looking for a simple explanation that I can use when exam comes because it is a short answer / multiple choice exam.


texts: What are the advantages of x86 CPUs over ARM?

texts:
Now that Apple is switching the MacOS platform to ARM chips, much has been said about the benefits of ARM processors (they save energy, are passively cooled, and the Apple M1 seems to be faster than even an Intel Core i9 processor).
I'd like to know what advantages of the x86 platform are left. Are there any specific circumstances where the x86 CPUs still have the edge? AFAIK they have an much bigger instruction set than the ARM chips. Under what circumstances is the bigger instruction set an advantage, and why?
Note that I'm not asking about a specific software ecosystem like Windows. I know that Windows has many software titles (e.g. games) that don't run (yet) on any ARM platform. That's not the answer I want to hear. An ecosystem advantage like that of Windows is more or less baggage from previous years. It does not necessarily mean that the CPU platform is in any way better, today.


texts: Computational Considerations on least squares problems

texts:
I am reading Elements of Statistical Learning and read the following claim from the text (page 93, Chapter 3.7):

Least squares fitting is usually done via the Cholesky decomposition of the matrix $\mathbf{X}^T\mathbf{X}$ or a QR Decomposition of $\mathbf{X}$. With $N$ obserations and $p$ features, the Cholesky decomposition requires $p^3 + Np^2/2$ operations, while the QR decomposition requires $Np^2$ operations.

I understand Cholesky and QR decompositions individually, but I do not understand where this claim came from. Please help.


texts:
I am implementing a Merkle tree and am considering using either of the two options.
The first one is sorting only by leaves. This one makes sense to me since you would like to have the same input every time you are constructing a tree from the data, that might not arrive sorted by default.
       CAB
      /    \
     CA     \
   /    \    \
  C     A     B
/  \  /  \  /  \
1  2  3  4  5  6

The second one is sorting by leaves and pairs, which means that after sorting the leaves, you also sort all the pairs after hashing them, however I'm not entirely sure about the benefits of this implementation (if any).
       ACB
      /    \
     AC     \
   /    \    \
  C     A     B
/  \  /  \  /  \
1  2  3  4  5  6

I have seen these implementations of Merkle trees in the past but am not sure about their benefits. So why choose one over the other?


texts: lambda calculus reduction: (((lambda f (lambda x (f x))) (lambda y (* y y))) 12)

texts:
given the input

  (((lambda f (lambda x (f x))) (lambda y (* y y))) 12)

what does this step evaluate to: lambda x (f x)

I am trying to evaluate this and I have the following tree so far:

how do I evaluate this ? looking for guidance on what I might be doing wrong or how to proceed with this.


texts:
How can I prove algorithm correctness ?
when i face a problem and come up with a solution the only way to know if this a valid solution or not is by trying some test cases. if they pass through the algorithm and produce the expected output then my algorithm most properly true.
but obviously this is not hold all the time because i may forget some corner cases or it is hard to figure out all the test cases.
So how can I prove mathematically if my algorithm produce the expected output or not ?

For example, consider the program below.

You’re given a read only array of $n$ integers.
Find out if any integer occurs more than $n/3$ times in the array in linear time and constant additional space.

Algorithm:
We will use an array of size 3 to count occurrence of numbers let it be count adding numbers to our count array with its proper count. If we reach the size of count array we decrement one from count of each number. If number count becomes zero it can be safely eliminated from the count array.

Here is an example:

Input: 4 3 3 7 2 3 4 5
count arr (4,1) 4 as first element and 1 is its count till now
count arr (4,1)(3,1)
count arr (4,1)(3,2)
count arr (4,1)(3,2)(7,1). Here we reach the max allowed size for count then we need to decrement count by one and if it reaches zero its item will be removed from our count array so count arr becomes
count arr (3,1). We will proceed with next element in the array which is 2.
count arr (3,1)(2,1)
count arr (3,2)(2,1)
and so on. At the end count arr will be (3,1)(5,1).

We will make another loop to the input array to count occurrence of 3 and 5 and if any one exceeds $n/3$ it will be printed out.


texts: Adding an ordered into a relationship without violating the functional dependencies

texts:
Assuming that we have the relationship $R(A,B,C,D)$, the tuple $(W,X,Y,NULL)$ and the following functional dependencies:

$$A \to C$$
$$A \to B,D$$

is it possible to insert a tuple with $NULL$ values, without violating the functional dependencies? I understand the definition of functional dependencies but I've never actually thought about what would happen for $NULL$ values. On the one hand, if you consider $NULL$ as a value then yes but if you say that it's the absence of value, then you can't. But in the case of the possibility of adding the tuple, mentioned above, without violating the functional dependencies, what could you do?


texts: Is the question of whether the language of a DFA/CFG is equal to a particular set of string decidable?

texts:
Suppose I have a set of strings $S$ that is generated from the alphabet. Suppose I have a DFA $D$ and a CFG $G$, are the questions of

$\{D\mid D\text{ is a DFA and }L(D) = S\}$ and
$\{G\mid G\text{ is a CFG and }L(G) = S\}$

decidable?

I know that the easier question of whether $D$ or $G$ generates a particular string $w$ or whether the language is the empty-language is decidable, but how can I decide on a particular set of strings?

I am thinking for the case of DFA I can do something like set-difference and check if $L(D/S)$ is empty.

For the case of CFG since it is not closed under complement is this question undecideable?


texts:
For a boolean function $f:\{0,1\}^n\longrightarrow\{0,1\}$, $H_{avg}(f)$ is a function from $\mathbb{N}\longrightarrow \mathbb{N}$, termed as the average case hardness, if $\forall$ circuit $C_n$ of size $H_{avg}(f)(n)$, $Pr_{x\in U_n}[C_n(x)=f(x)]<1/2+\epsilon$, $\epsilon >0$.
Similarly, for a boolean function $f:\{0,1\}^n\longrightarrow\{0,1\}$, $H_{wrs}(f)$ is a function from $\mathbb{N}\longrightarrow \mathbb{N}$, termed as the worst case hardness, if $\forall$ circuit $C_n$ of size $H_{wrs}(f)(n)$, $Pr_{x\in U_n}[C_n(x)=f(x)]<1$.
This I know from the definition of average and worst case hardness. My question is what is the motivation behind these definitions. Can anyone  help?


texts:
Can we use the term "black box" to speak about an algorithm which has a polynomial complexity but for which we don't know exactly how are made the calculations?

In fact I would like to explain that we assume that an algorithm cannot be executed incrementally, i.e., having a part of the input, for instance the first 50%, we cannot progress the computations of this algorithm.

Can the term "black box" be understood in this sense?

Thank you very much.


texts: Does PromiseBPTIME have a time hierarchy theorem?

texts: This is a follow-up to this question. Even though BPTIME does not have a time hierarchy theorem, the reasons that prevent it from having one are essentially bypassed by PromiseBPTIME. Thus, does PromiseBPTIME have a hierarchy theorem? If so, how does it look like and how to prove it?