texts:
Early note: This is not homework.  I simply regularly create ideas in an attempt to teach myself a language.  For what it's worth I'll be using Javascript for this.

That said, I haven't been able to come up with a solution/algorithm outside of brute force.  I've searched for various puzzle algorithms but any assumptions regarding puzzle shapes don't fit my simpler criteria so become overly complicated quickly.

I'm calling this a rectangle puzzle rather than a jigsaw puzzle since there is no final picture or restrictions on the overall placement of the pieces.

There are only 4 possible piece shapes (row x column) : 1x2, 2x1, 2x2, 4x1
These are the only pieces (ie. they may not be rotated or overlap)
The play area is 8x4
The number of pieces will be undetermined at start
Pieces may exist multiple times or not at all
The play area does not need to be completely filled
The only requirement regarding placement is they must fit in the play area
There is no one solution

End solution: What I would like to output is the various arrangements that exist.  In other words, given a set of pieces I'd like to know in what ways they may populate the game area.  Given the pieces available among other constraints there will be a finite set of solutions.

For the visually minded please see the images.

Play Area

Possible Pieces

Generating a 2D array and fitting the "pieces" via brute force, as said, is possible but I'd prefer to know whether this is already a game of sorts and an algorithm exists.  I'm not a math lover so I'm not familiar with any possible solutions that may exist in that space but wouldn't be against investigating if something makes sense.


texts: Hash table: When is it suitable to use modulo power of 2?

texts:
I am implementing a hash table that may need to grow and shrink as the number of stored keys varies. I have a hashcode function that uniformly hashes keys to positive 32-bit integers. The table itself will use a smaller array of approximate size M.

If I wanted to use the hash function to produce a value between 0 and P-1 (if P is close to M), can I use mod P if P is a power of 2?

What about using mod P, where P is a prime?


texts: Matching vertex values with sum of edge weights on bipartite graph

texts:
Earlier this week I asked this question (please review):

  Imagine StackOverflow started offering a subscription where companies
  could buy X number of impressions per month for a set of tags.

  For example, you might be interested in running an ad with 50000
  impressions on the following tags: javascipt, typescript, react,
  nextjs, nodejs, webpack.

  StackOverflow "promises" you will get 50000 impressions, but they are
  free to distribute them across the above tags however they desire
  (could even be 100% to one tag).

One of the solutions provided suggested using the Hopcroft-Karp algorithm, which I have since been able to successfully implement.

However, I'm having trouble scaling this solution to work for my use case.  The bottle neck is actually in the setup of the graph more-so than the algorithm performance.

The problem is the massive number of edges that must be initialized.  Take the example below:

==Inventory==

Tag          Units

javascipt    2
typescript   4
react        3
nextjs       3

== Subscriptions ==

Account  Units   Tags
Acme     7       javacript, typescript, react, nextjs

Stark    4       javacript, typescript

If we create a vertex to represent every unit, then we would end up with a graph that has 101 edges (7*11 + 4*6)!

The problem I'm working on is orders of magnitude larger, so this quickly becomes unrealistic.

As suggest, I can reduce the number of vertex by scaling the units, but I lose resolution and that's actually somewhat important in this case (I can maybe scale by 100x max).

I was thinking there must be a more efficient way to do this, since I'm essentially duplicating vertex for every unit.  I came up with the following bipartite graph with weighted edges and vertex values:

The goal would be to to adjust the weights of the edges so that:

On the left, the sum of edges is equal the value of the vertex
On the right, the sum of edges is less than or equal to value of the vertex

Below is an example of one of the solutions:

I'm guessing (hoping) this is already a well known problem, for which there is also a well documented solution (ideally one that's not NP-hard)!

Maybe it's even possible to modify the Hopcroft-Karp algorithm to work for this?


texts: What's the name of this sorting(?) algorithm?

texts:
Given the options of:

Red
Orange
Yellow
Green
Blue
Violet

You want to find your favorite color by comparing all pairs to each other, like so:
Red vs...

Red vs Orange = Orange
Red vs Yellow = Red
Red vs Green = Red
Red vs Blue = Red
Red vs Violet = Red

Orange vs...

Orange vs Yellow = Orange
Orange vs Green = Orange
Orange vs Blue = Orange
Orange vs Violet = Orange

Yellow vs...

Yellow vs Green = Green
Yellow vs Blue = Yellow
Yellow vs Violet = Yellow

Green vs...

Green vs Blue = Green
Green vs Violet = Green

Blue vs...

Blue vs Violet = Violet

In the end you'll find your "most preferred". Not sure if you get a full order of preference.
What's the name of this...thing?
Also as D.W. described, I believe it's solved by which color won most often. So in the example above:

Orange = 5
Red = 4
Green = 3
Yellow = 2
Violet = 1
Blue = 0


texts:
I need to find out to what extent two shapes are similar. I mean I've got two vectors of points - and just that, no shadows, color or whatever - simplest case. Two triangles are the perfect example. Of course this has to work regardless of what the angle shift is and regardless of their scale (only aspect ratio matters).

I know there is SIFT method but this seems too complicated for this simple use case. Is there more suitable method?

Updated question

The problem is I don't know the optimal measure too. I mean I have to check if the two shapes are similar not in terms of size or angle but shape. So in terms of those triangles what matters is angle. Of course these shapes not need to be so trivial - they can consist of curves where no angles are present. So far I have found that I can use Procrustes algorithm to eliminate the offset, size and angle but what then? There is Fréchet distance but it seems it won't work for any composite shapes - a square with both diagonals is a good example. I mean this isn't going to work when there are several ways of drawing a figure, is it?

I was also wondering if those shapes can be represented by graphs (so finite number of points) and then I could see what is the length of minimal path going through both points (hamiltonian cycle?) - but I'm not sure if it would work in all scenarios.

While Procrutes algorithm will work with any shape I can think of, Frechet distance is more problematic.

It works well for any shape which can be drawn in one stroke so there are no two ways of doing this. A good example is a triangle

the problem is visible here

as there are more than 1 way of ordering the pixels to get the desired shape. Is there a way to handle this as well with Frechet algorithm? If not, what algorithm should be used?


texts: Is there any simpler way to have for each sequence element the amount of succeeding larger elements than to implement an AVL tree?

texts:
I have a sequence. And now for each element in this sequence I would like to know how many subsequent elements are larger. Or, in other words, I have a sequence $a_1, \ldots, a_n$, and for each $1\leq i\leq n$ I would like to compute $|\lbrace j|j>i\wedge a_j > a_i\rbrace|$.

My idea: Implement an AVL tree, put elements from this sequence to this AVL tree from the last one to the first one. Before putting each element obtain the amount of larger elements the tree already contains. I can implement an AVL tree that would allow such operations.

But alas, I do have to implement such an AVL tree, since unfortunately the standard C++ std::set doesn't allow obtaining the distance between two iterators in logarithmic time.

Now I need this to solve a task from one of the former exams on algorithms and data structures. These exams usually contain two tasks, a "simpler" one and a "harder" one. And this is the "simpler" one. Now I doubt that a "simpler" task would require implementing an AVL tree. A "harder" task might; but a "simpler" one, doubtfully. Therefore, I would say, there should be a less laborious way to solve this task.

Is there any simpler way to compute what I need to compute?


texts: Drawing an implication graph for 2-SAT clauses

texts:
I am trying to convert the following 2-sat clauses to implications and then draw the implication graph.

The clauses are: {¬xvy}, {¬yvz}, {¬zvw} ,{¬wvu},{¬uv¬x},{xvw},{¬wvx}

I converted the boolean literals into implications so I could construct the implication graph:

{¬xvy}: I have x-->y and ¬x -->¬y

{¬yvz} : I have y-->z and ¬y-->¬z

{¬zvw} : I have z-->w and ¬z-->¬w

{¬wvu} : I have w-->u and ¬w--->¬u

{¬uv¬x} : I have u-->¬x and ¬x-->¬u

{xvw} : I have ¬x-->w and ¬w-->x

{¬wvx} : I have w-->x and ¬w-->¬x

Am I doing this right? If so, I have constructed this implication graph to prove it is not satisfiable.

I would argue that these literals are not satisfiable because of the infinite loops you can have from ¬w ¬x ¬y ¬z ¬w and w x y z w. Is this a sufficient enough explanation?

Thanks in advance!


texts:
I recently thought of the following problem:

Given a set $A$ of sets find a minimal set $B$ of pair-wise disjoint sets such that each set in $A$ can be expressed as a union of sets in $B$.

For example, if $A = \{ \{ 1, 2 \}, \{ 1, 2, 3 \}, \{3, 4\}, \{4\} \}$ then $B = \{ \{ 1, 2 \}, \{ 3 \}, \{ 4 \} \}$.

I designed the following algorithm:

Let $B = \emptyset$ initially.
Let $S$ be the set of set(s) of lowest of cardinality in $A$.
Let $I$ be the intersection of the sets in $S$.
If $I = \emptyset$: add the sets in $S$ to $B$, remove the elements in the sets in $S$ from the sets in $A$, and remove $\emptyset$ from $A$.

If $I \neq \emptyset$: add $I$ to $B$, remove the elements in $I$ from the sets in $A$, and remove $\emptyset$ from $A$.
Repeat from step 2 until $A = \emptyset$.

My questions are:

Does this problem have a name?
Is this algorithm correct?
What is the complexity of this algorithm?
Is this algorithm optimal, and if not, what would be a better algorithm?


texts: Is $L = a^{n}b^{n+m}c^{m} | n,m \geq 0$ a context free or a recursive language?

texts: My initial thought is that L can't be context free since I can use the pumping lemma. I also don't think a grammar can be generated since it needs to keep track of the number of c's and a's. However, I'm having a hard time coming up with an algorithm for this language.


texts: Variant of ridge regression loss function

texts:
We can create variants of the loss function, especially of ridge regression by adding more regularizer terms.  One of the variants I saw in a book is given below
$min_{w \in \mathbf{R}^d} \  \  \alpha.||w||^2 + (1-\alpha).||w||^4 + C||y-X^T.w||^2$
where $y \in \mathbf{R^n}, s \in \mathbf{R^d}, X \in \mathbf{R^{dxn}}$ and $C$ a regularization parameter $\in \mathbf{R}$ and $\alpha \in [0,1]$
My question is how does change in $\alpha$ affects our optimization problem? and how does generally adding more regularizers help? why is not one regularizer enough?


texts: Looking for cheat sheet to J.C. Reynolds symbols

texts: Most specifically, his use of small epsilon introduced at the end of section 1 of "Types, Abstraction and Parametric Polymorphism" is throwing me, but in general I would like references to symbols in the Type and Logical Relations literature.


texts: Closest Pair of Points Algorithm - Fortune and Hopcroft

texts:
I am interested in implemented the deterministic ${O(n\log(\log(n)))}$ algorithm for the closest pair of points problem described here by Fortune and Hopcroft: https://ecommons.cornell.edu/bitstream/handle/1813/7460/78-340.pdf
In particular I would like to have a solution to the two-dimensional case.
They say: "The algorithm is based on the following observation: suppose we can find an interval size such that at most one point falls within each interval, and there are two nonempty adjacent intervals. Then to determine the closest pair we need only examine, for each point, the intervals surrounding the point". And for the one dimensional case which they describe in detail, the initial interval size is selected by taking (max(S) - min(S))/n where ${S}$ is the collection of points and ${n}$ is the number of points.
They claim the extension to higher dimensions is "obvious", but it's not at all clear to me how this above line might be generalised.
Does anyone have any suggestions? Many thanks.


texts:
Given an image of a biology diagram, I would like to classify the diagram into these 4 categories:

Plant
Animal
Cell
Anatomy

However, I don't have any training data. I would like to avoid the crowdsourcing for data. Is there anything I can do?


texts: Example of Minimum Test Collection Problem

texts:
I'm studying the Minimum Test Collection problem and I can't find an example of some instance of the problem, given values to the sets. The Garey and Johnson book  only contains the proof of its NP-Completeness.

I hope someone can give me an example in order to understand in a better way the problem.

The problem is defined as follows:

Instance: A finite set A of "possible diagnoses," a collection C of subsets of A, representing binary "tests," and a positive integer J≤|C|.

Question: Is there a subcollection C′⊆ C with |C′|≤ J such that, for every pair $a_{i},a_{j}$ of possible diagnoses from A, there is some test c∈C′ for which |{$a_{i},a_{j}$}|∩ c|=1 (that is, a test c that "distinguishes" between $a_{i}$ and $a_{j}$)?

Thanks.


texts: When we say a problem is NP-hard is that a property of a set of problems or is it a property of a instance of the set of problems?


texts:
There are possibly several min-cuts for the source and target nodes of a graph.
I think I can determine the same min-cut for the same graph by putting the following restriction

"if there are several min-cuts, then I select the min-cut consisting of edges closer to the source atom. By saying close to source atom, I mean you start to travel from the source to the target, then an edge, which is in a min-cut you first encounter"

a,b and c are nodes, A, B and C are edges.
The most left node is the source and the most right node is the target.
Example (1)

a --A--> b --B--> c

two sets: {A} and {B}. we chose {A}.
Example (2)

a --A--> b --B--> c
a --C--> d --D--> c

Four sets: {A, C}, {A,D},{C,B} and {B,D}.  we chose {A, C}.
Example (3)

a --A--> b --B--> c
a --C--> b --D--> c

Two sets: {A,C} and {B,D}, we choose {A,C}.
We can keep trying, but I think all other graphs are combinations of these 3 examples (I may be missing some cases).
(1) So, I want to prove that by doing that way, I alway find a same min-cut for the same graph if I run the algorithm many times.

If I am right, how can I prove (1)?
or I am thinking too much about a very obvious fact? (^&^)


texts: True Postcondition, with true Precondition

texts:
In my exam preparation I stumbled across the follwoing exercise regarding pre and postconditions:

As far as I understood the question, we need to express some condition for p, such that if that condition holds for p, then we have that {true} p {true}.

The conclusion I got to when trying to think about it intuitevely is that p could simply be a skip statement, but I found myself wondering what a {true} postcondition implies. I know a {true} precondition means that there is no restriction on inputs, what does it mean for postcondition? What would be such a suitable condition to express p?

Thanks!


texts:
I want to add a constraint to a convex program, to guarantee some matrix $A$ to be positive semidefinite.
How should I do it?

The library I am working with can cope with linear/ quadratic inequalities only.

By definition, $A$ is positive semidefinite iff $\forall x \in \mathbb C^n : x^T A x \geq 0$, but this is a set of inifinitely many constraints. So, my question is: how can I formulate it using a finitely many set of contraints and using linear/ quadratic inequalities only.

Thanks in advance!


texts: What is meant by superlinear speedup? Is it possible to have superlinear speedup in practice?

texts:
In parallel computing, I know the speed up equation is

$$ \frac{1}{ s + \frac{1-s}{p} } $$

But what is meant by superlinear speed up? Is it something theoritical? Could you explain it with equations?


texts: Coin flipping problem on an $n \times m$ grid

texts:
There are $n \times m$ coins lying on an $n \times m$ grid. Each coin is either facing up or down initially. We can do the following operation repeatedly:

Flipping a row of coins;
Flipping a colomn of coins;
Flipping a diagonal line of coins;
Flipping a counter-diagonal line of coins.

The problem is to check whether we can finally let all coins facing up.

As we can see, there are $3n+3m-2$ kinds of transformations in total ($n$ rows, $m$ colomns, $n+m-1$ diagonals, and $n+m-1$ counter-diagonals). However, these transformations are not independent. For example, flipping all rows and then all colomns except the first colomn is equivalent to flipping the first colomn.

By trying some examples $n,m\ge 3$, I find that there are $3n+3m-9$ kinds of independent transformations in total. Other 7 transformations can be done by combining the $3n+3m-9$ kinds of independent transformations. Using Xor-Gaussian elimination we can check the correctness of the proposition.

If we can prove the above proposition, we can solve the problem in this way:

In the following image, there are $3n+3m-9$ shaded lattices. For any state of coins of these lattices (facing up or facing down), we can always use the above transformations to face up all coins of these shaded lattices (according to the order in the image to face them up). Also, for other unshaded lattices, their state will be uniquely determined. Then we can check whether we can finally let all coins facing up in $O(nm)$ time.

But it seems difficult to prove the independent proposition. Does anybody have some ideas on it? Thank you!


texts: How is average precision related to the precision-recall curve?

texts:
As background, in Information Retrieval, there are many metrics to assess how well search results are retrieving information.

A simple one is precision, where we calculate the fraction of documents returned that are relevant to our query. There is a second (or more general?) metric, precision@K: For a ranked result set, we calculate the fraction of documents at rank $k$ or higher which are relevant. So if the first document is relevant, the second is not, and the third is, then precision@3 is 1/3.

On to average precision. As I understand it (thanks in part to this), for this we get the rank of every relevant document in the result set, and then average the precision@k values at each of those ranks. It's even clearer if you look at my link.

Ok, my question: Both Wikipedia (here) and my IR book give the same explanation I gave, but then they start talking about precision-recall curves. My understanding of precision-recall curves is from machine learning, but I assume the concept is similar: You plot precision and recall against each other (on the x and y axis), showing how a decrease in one leads to an increase in the other.

I don't see how that relates to average precision, which is only a metric of precision and not of recall.

Wikipedia says: Precision and recall are single-value metrics based on the whole list of documents returned by the system. For systems that return a ranked sequence of documents, it is desirable to also consider the order in which the returned documents are presented. By computing a precision and recall at every position in the ranked sequence of documents, one can plot a precision-recall curve, plotting precision p(r) as a function of recall r. Average precision computes the average value of p(r) over the interval from r=0 to r=1.

If I had to guess, it seems like they're describing calculating both average precision and average recall for every rank, or something. But if so it's confusing that they'd put it under Average Precision, and I'm very unsure of my interpretation.

So, how is average precision related to precision-recall graphs? It probably goes without saying that any other tips on understanding that Wikipedia section are also humbly appreciated.


texts: Which closure properties are always valid between regular, context-free and non context-free languages?

texts:
I am making a scheme that respresents some closure properties (union, intersection, complement and concatenation) for regular languages, context-free languages, decidable languages and RE languages. Below you can see my scheme.

I am trying to find all possible internal closure properties of these different languages that will always be valid. E.g., I know that $$\text{Regular language } \cup \text{ CFL } = \text{ CFL } $$
$$\text{Regular language } \cap \text{ CFL } = \text{ CFL } $$
$$\text{Regular language } ^* \text{ CFL } = \text{ CFL } $$
What other internal properties are there between these languages?


texts: Finding simple cycle of minimal weight in directed bipartite complete graph with negative cycles

texts:
Given a weighted complete bipartite directed graph K_{m,n}, is it possible to find a simple cycle (every node is visited at most a single time) with minimal weight in polynomial time (in m*n) when there exist simple cycles with negative weight?

For general graphs this problem is NP-complete (Finding the lowest-weight negative cycle in a weighted digraph). Using Bellman-Ford it is possible to find a cycle with negative weight if such a cycle exists, but this algorithm gives no guarantee that it is the most negative cycle.

In total there are

simple cycles in this graph, so checking all of them would already give a subexponential algorithm. But can this be reduced to a polynomial time algorithm?

Some assumptions I can make:

The absolute value of the weights are bounded by a constant C.
There exists a negative simple cycle and all negative simple cycles visit at least 4 nodes.

Thanks.


texts: Counting letter frequency in array in O(1) with hash function

texts:
I want to calculate the frequency of each character in an array. (e.g ['a', 'b', 'o', 'p']
There are several ways to do this:

A Simple brute-force over the array would need $O(n^2)$ time and $O(n)$ space

Sorting the array first and serial counting the characters is a better solution with $O(n \log n)$ time and $O(n)$ space

But the optimal solution is... using hash tables with $O(1)$ access time. The thing is, I do not quite understand why the complexity is supposed to be $O(1)$ and not $O(n)$. After all, we still have to iterate over the array. For example
def fCount(A):

  frequencies = new hashTable()

  for character in A: // This is O(n) !!!
      frequencies(character) += 1

Yes, the access time is $O(1)$ but in order to create the hash table, you still need $O(n)$ time and space.
So why is this supposedly $O(1)$ time and $O(1)$ space?


texts: Prove the upper bound on $T\left(n\right)=T\left(\log_{2}n\right)+O\left(\sqrt{n}\right)$

texts:
I need some help with the following recursion:

$T\left(n\right)=T\left(\log_{2}n\right)+O\left(\sqrt{n}\right)$

More specifically I wish to find and prove the upper bound on it.

I have a hunch it is $O\left(\sqrt{n}\right)$ but have gotten stuck proving it really is this.

Any help is appreciated

Thank you!


texts:
Having difficulty grasping the concept of how a language and a regular expression are related. For example:

(In all cases, the alphabet is $\{0,1\}$)

The language $L = \{100,10,011\}$ ------> Regular expression.

So far, I have:

$(0+1)$ since you can have either $0$ or $1$ in the first part...but...I'm not sure what would follow after that...I've tried making a DFA for it but I feel like I'm overcomplicating it. Any help would be great since I'm fairly confused. Thanks!


texts:
I am looking for fast procedures for polygon matching, i.e. checking polygon similarity under different transforms

translation only,
translation + rotation,
translation + scaling,
translation + rotation + scaling (= similarity).

The matching can be partial, meaning that there can be a good match on a significant fraction of the outline (say > 70%), and complete mismatch elsewhere.

The number of vertices is reasonable (say N<50).

In a variant of the problem, you need to compare two polygons. In another variant, you compare one polygon to a series of polygons, with preprocessing of the single polygon allowed. In a third variant, preprocessing is allowed on all polygons.

Are you aware of solutions to this problem ?


texts: Is there a more efficient algorithm than backtracking/dynamic programming?

texts:
Consider the following game:

One day a castle is attacked at sunrise (by surprise) by n soldiers.

Each soldier carries a canon and a rifle.

The castle has strength s.

On the first day each soldier shoots his canon at the castle costing the castle n strength points (i.e. the castle ends the first day with s=s-n strength points).
After all the soldiers have fired, the castle sends dpw defenders to battle them.

In the ensuing days the castle and the soldiers battle it out following these rules:

All the soldiers fire first. A soldier can fire his canon at the
castle or his rifle at one of the defenders (but not both and each
soldier can only shoot once). One shot at a defender kills him. One
shot at the castle decreases its strength by 1.
Then each of the d defenders shoots at one soldier (and only
one) killing him.
If the castle still has strength points (i.e. s>0) it sends a
new batch of dpw defenders at this point. The total number of defenders in the next round will be d=d+dpw.
Repeat 1 through 3 on each new day.
If all soldiers are killed by the defenders, the castle wins.
If there are zero defenders after the soldiers shoot and the
castle strength is zero, the soldiers win.

We would like to know the minimum number of rounds the soldiers need to win the game (or if not possible the minimum number of rounds for the castle to win the game).

We would also like to know the number of soldiers, defenders and castle strength at the beginning of each round for the minimum number of rounds solution.

An easy way to solve this problem seems to me to be by recursive backtracking/depth first search or dynamic programming.

The problem however seems simple enough that a better/faster solution seems likely to exist (one that doesnt involve a large search or maybe even a search at all).

Is it obvious what that better strategy/algorithm might be?


texts: Category Set language using simply typed lambda calculus

texts:
I am currently self learning Category Theory and Simply typed lambda calculus (STLC).  For learning purposes, I have implemented an STLC interpreter as given in  Types and Programming Languages book of Benjamin Pierce. Now i am wondering if I can extend this interpreter with category of sets (category Set ). i.e. interpret expressions to construct sets, pushouts, pullbacks etc.
Unable to find any directions on how to do this. Can someone please provide any helpful suggestions on this?


texts:
Is ```sii``sii the smallest Unlambda program that doesn't halt?

In other words, what is the smallest non-terminating combinator term in SKI augmented with $C$ (call/cc) and $D$ (delay)? Is it $SII(SII)$?


texts: Why multiple return values is not a common thing?

texts:
I would like to ask a question about multiple return values, why this construct is not preferrable in programming languages (conceptual and/or technical difficulties). I've heard something about stack frames and how they reserve memory for return value and variable return values could make this problematic, but if someone could explain this better, this would be much appreciated.

In conctanetative languages (like FORTH), having multiple return values from a function is a common and very useful thing, and I imagine something like this in java/c-like languages would be useful too (a very basic example):

x, y = multRet(5);
multret(int x) {
    return x+1;
    return x+2;
    exit;
}

To clarify: I am not asking how to return multiple values (this is a known question with known answers), but I want to get a clarification about why this practice is not common in programming languages.


texts: Understanding non-faulting and faulting software prefetches

texts: What is the difference between a faulting and non-faulting software prefetch. I have read some material in Google but can't understand it deeply. How do we know if a software prefetch is faulting or non-faulting in practice?


texts: Really confused about the chord algorithm

texts:
I'm looking at the pseudocode for chord algorithm here:
// create a new Chord ring.
n.create()
    predecessor := nil
    successor := n

// join a Chord ring containing node n'.
n.join(n')
    predecessor := nil
    successor := n'.find_successor(n)

// called periodically. n asks the successor
// about its predecessor, verifies if n's immediate
// successor is consistent, and tells the successor about n
n.stabilize()
    x = successor.predecessor
    if x ∈ (n, successor) then
        successor := x
    successor.notify(n)

// n' thinks it might be our predecessor.
n.notify(n')
    if predecessor is nil or n'∈(predecessor, n) then
        predecessor := n'

// called periodically. refreshes finger table entries.
// next stores the index of the finger to fix
n.fix_fingers()
    next := next + 1
    if next > m then
        next := 1
    finger[next] := find_successor(n+{\displaystyle 2^{next-1}}2^{next-1});

// called periodically. checks whether predecessor has failed.
n.check_predecessor()
    if predecessor has failed then
        predecessor := nil

I'm struggling to make sense of it. My question specifically is: when exactly will the predecessor field EVER be non-null?
Consider a case where a node id 1 joins. Its successor is 1, the predecessor is nil.
Now say node with 10 joins. Its successor is 1, predecessor is nil.
The stabilization routine depends on the predecessor being non-nil, which in this case it isn't both nodes.
So how does the algorithm proceed at this point?


texts:
When we talk about operators in descriptive complexity, are they something like this: for example, if transitive closure operator $TR$ is available, we can use variable $y$ that we define as $TR(x)$ where $x$ is input? or is it something else?

Also, when we say $FO(t(n))$, what does quantifier block being iterated $t(n)$ times mean?


texts:
I have some experiences with Convolutional Neural Networks before. I have a question regarding the Bilinear Sampler used in "Unsupervised Monocular Depth Estimation With Left-Right Consistency" (the link to it is provided here: https://arxiv.org/pdf/1609.03677.pdf and https://www.youtube.com/watch?v=jI1Qf7zMeIs)

I understand that the author had made the convolutional neural network predict the disparity map of the left image, then uses the disparity map to transform the right image back into the predicted left image.

However, I don't understand how the transformation is done (shown in 5:35 in the youtube video, and "Our network generates the predicted image with backward
mapping using a bilinear sampler, resulting in a fully differentiable
image formation model").

I understand that the system needs to be fully differentiable so that backpropagation can be used, and I understand that Spatial Transformer Networks can map images from a transformed grid, but I cannot understand how the bilinear sampler in the spatial transformer network is used to transform the right view image into a left view image given the left disparity map. In particular, in spatial transformer networks, the sampling stage requires a set of sampling points (which is a 2x3 matrix) and an image so that it can sample a new image from the old one. However, in the depth estimation paper, I can't understand how they extract the set of sampling points (the 2x3 matrix) from the disparity map.   How does that work?


texts: I am using a Hidden Markov Model with Gaussian mixture emissions to cluster a sequential data (I am using hmmlearn in python 3). Initially, I used the log likelihood to find the number of clusters and gaussian mixtures, however, this value kept increasing as the complexity of the model grew (the number of states and mixtures increased); AIC did the same (decreased, at the same parameters). So I decided to use SSE (sum of squared errors, or the squared distance of each sample to the centroid of the state), which had the least value for 13 states, 3 mixtures. However, when I checked this model, there were empty states,i.e., none of my training samples was classified in those states. These empty states seemed to have the same parameters as other non empty states (same values in the transition matrix). Should I just discard the empty states and modify the transition matrix by adding the probabilities of equivalent states?


texts: Computation of iterated logarithm function

texts:
I recently came across the iterated algorithm function denoted as $\lg^* n$.

But I am having a hard time understanding this statement:

$\lg^* n = \min \{i \ge 0: \lg^{(i)} n ≤ 1\}$

I could not understand what $\min$ set is used to signify.
Also, could someone please provide an example of how this works.
I also came across examples like:

$\lg^* 4= 2$

But could not understand the computation, specifically how did they take up the values of i?

Thank you.


texts: Showing that the language L={⟨M,w⟩ | M moves its head in every step while computing w} is decidable or undecidable

texts:
How would you go about showing that the language L={⟨M,w⟩ | M moves its head in every step while computing w} is decidable or undecidable?
Intuitively speaking I think it is indeed undecidable because there seems to be no limit to the possible configurations, however I am not sure.
Thanks a lot in advance!


texts: Is my decomposition of R into 3NF is lossless and preserving all dependencies?

texts:
I have a schema R = {A,B,C,D,E} and the set F of FDs:

F = {A --> BCDE, CD --> E, EC --> B}.

Candidate key = A
Non - Prime Attributes = BCDE
Prime Attributes = A

According to me, there is no partial dependency because no non-prime attribute is dependent on part of CK.

E and B are transitively dependent on A so the schema Ris not in 3NF.

Decomposing R into 3NF, I have three relations and three set of FDs :

R1(A,B,C,D)                         F1={A --> B,A --> C,A --> D}
R2(C,D,E)                           F2={CD --> E}
R3(E,C,B)                           F3={EC --> B}

My question is, Is my decomposition of R into 3NF is lossless and preserving all dependencies or not? And if not how can I decompose it into 3NF losslessly while preserving all dependencies.


texts: How to find a lambda term to complete a function?

texts:
I tried to complete this exercise but i stopped...
Defining a $ \lambda $-term M such that:
$$(<M,u>)<M,v> \: \simeq_{\beta} \: <M,u>$$

I chose $M=\lambda m \lambda a \lambda b \lambda p \,((p)m)b \:$ then i have to find a representation T of a function using M that value true if the sequence is empty and false if it's not. A sequence is defined as:
$$[]=\lambda x_0\lambda x_1 \lambda z z \\
[b]=\lambda x_0 \lambda x_1 \lambda z (z) x_b\\ [b_1 b_2]=\lambda x_0 \lambda x_1 \lambda z ((z)x_{b_1})x_{b_2} \\
.\\.
\\ .
\\ [b_1 .. b_n]= \lambda x_0 \lambda x_1 \lambda z (...((z) x_{b_1})x_{b_2}...)x_{b_n} $$
so the sequence of exercise is :
$$[01101]= \lambda x_0 \lambda x_1 \lambda z (((((z)x_0)x_1)x_1)x_0)x_1 $$
For example T need to be:
$(T)[01101] \simeq_{\beta}$ false while $ (T) []\simeq_{\beta}$ true.
I really find that difficult. How i can do that?

edit.

$true=λxλyx$
and $false=λxλyy$


texts: Reducing "multiple satisfiability" to normal SAT

texts:
I have to prove the NP-completeness of the following set:
QUADRUPLE-SAT:={F is Formula in CNF|F has at least 4 satisfying interpretations}

My idea so far has been to reduce the problem to the normal SAT by constructing a new formula, copying the original formula 4 times and using a new set of literals in every copy, then adding clauses to ensure that the 4 sets of literals are pairwise differently interpreted (there is at least 1 literal which is flipped). Such a formula is easy to find, I'm unable to get it to CNF though.

I might also be on the completely wrong track on this one, if you know another NP-complete problem this could be reduced to more easily, that would be great as well.


texts: Lazy evaluation on slow Boolean functions (optimization)

texts:
Short-circuit evaluation is a straight forward subject for lazy evaluation on Boolean expressions, I noted that two factors could be useful in ordering Boolean functions to improve run-time. But this is applicable in a very particular hypothesis:

Knowing a percentage of positive (hence negative) result of a function. This is followed by a very illustrative example.
Knowing execution run-time of the function on data (knowing size of data can be a hint).

My case is easy to understand. Here is a description:

Let's say F is a Boolean function that scores sentiment and returns -1 or 1. I've been doing some improvements to predict sentiment scores on big arrays of text, and I can calculate How much is likely a function will return 1 (probability withing a tolerated error range) lets call it P(f) = Pf (probability of being positive)

We have also an estimation of execution time since data to be analysed is measurable. lets call it T(f) = Tf
We define positiveness speed as follows:

PS (f) =  Pf  / Tf

Let Lazy be a function which takes a Boolean expression, and gives the best ordering of functions for run-time based on PS scores.

Lazy (&, f1, f2, …, fn) = and_Order (f1, f2, …, fn)

Where and_Order is an ascending order of positiveness speed.

Lazy (or, f1, f2, …, fn) = or_Order(f1, f2, …, fn)

Where or_Order is a descending order if positiveness speed.

Obviously this is a high level optimization and not a compiler task. Is this an established study? How is this practical in cases other than sentiment analysis? Is the PS(F) even correctly representing what it should be representing?


texts: maximum Hamilton cycle and NP-completeness

texts: we know max tsp (maximal Hamilton cycle) is NP-Hard. is there any decision version for this problem to conclude this is NP-Complete?


texts:
I'm trying to build an agent-based model to study facebook usage. One important part is determining, at each step, whether a given user is online/active or not.

I am looking for a distribution of time spent online by percentage of users. I read in [this study][1] that this distribution is exponential, which is expected, but the study didn't provide any details of the function.

Just to be clear, I'm not looking for demographic breakdowns or anything. I'm looking for a function or dataset from which I can say "the top 5% of users spent 10 hours per day, the next 5% spent 6 hours", etc.

Not asking anyone to do my Googling for me, but I haven't found anything and I'd appreciate advise on where to look.

[1]:An Agent-Based Model of Message Propagation in the Facebook Electronic Social Network by Hamid Reza Nasrinpour, Marcia R. Friesen, and Robert D. McLeod, Member, IEEE. Published 2016, Accessed July 8 2017.


texts: We are solving a system of equations $f(x)=0$, including non-linear equations and piecewise linear equations. The space is subdivided to polyhedral pieces (cells), in every of them the equations from the second group are simply linear and there is $C^0$-continuous connection of the equations between the cells. From the structure of the problem we can prove that in most of the cells Jacobian of the system $\det J>0$. There are also some cells where $\det J=0$, due to linear dependence of equations in the second group. Solution of the system does not necessary belong to $\det J=0$ cell, but the path of the solver can intersect such cell, leading to divergency. We use Newton’s method with backtracking line search for solution. Is there any modification of the method to overcome this problem?


texts:
The number of comparisons in the following algorithm is supposed to be $3n/2 - 3/2$ if $S$ is odd. I understand that the for loop is $3n/2$ comparisons, but I fail to see where the $-3/2$ comes from.
if (n % 2 == 0):
    if (S[0] > S[1]):
        Largest = S[0]
        Smallest = S[1]
    else:
        Smallest = S[0]
        Largest = S[1]
    I = 3
else:
    Smallest = Largest = S[0]
    I = 2

for (i=I; i<=n-1; i+=2):
   if S[i] < S[i+1]:
     if S[i] < Smallest:
      Smallest = S[i]
     if S[i + 1] > Largest:
      Largest = S[i + 1]
   else:
     if S[i + 1] < Smallest:
      Smallest = S[i + 1]
     if S[i] > Largest:
      Largest = S[i]


texts: Correctness of Karger's min-cut Algorithm

texts:
tl;dr in the analysis for Karger's min-cut, the probability of an edge being in the min-cut in the $j$th iteration, $\frac{k}{0.5k(n-j)}$, neglects the fact that all the edges between the two corresponding supernodes are contracted. What's wrong?

Karger's algorithm for finding the global min-cut in a graph G(V, E), works by recursively choosing an edge randomly and contracting its two endpoints.
The analysis, starts assuming there is a min-cut of size K; thus the minimum degree of nodes is K -- and this goes for all subsequent recursions, where there can be multiple edges between the nodes, and nodes are actually supernodes containing those nodes which have been grouped together thus far.
The analysis continues by upperbounding the probability of an edge from the min-cut being chosen at each iteration j, by $\frac{k}{0.5k(n-j)}$, where $0.5k(n-j)$, is the minimum number of edges in the (multi-)graph at iteration j.
Now here's the problem, choosing an edge in the multi-graph past the first iteration and contracting its two endpoints, means contracting all the edges between those two endpoints, hence we cannot upperbound the probability of "it" being in the min-cut by the aforementioned value.
I realize that this is conditioned on the event that no edges in the min-cut have been contracted upto this point, however, the point is, that the suggested probability for "the" edge being in the min-cut does not apply anymore, i.e it also has to be conditioned on the fact that the no edge in the min-cut has been cut yet, and more importantly, that its endpoints are in the same partitions in the min-cut, as the other nodes in their corresponding supernodes. This value can be very roughly upperbounded considering that all the edges between the supernodes are not in the min-cut.
I believe that the fault, or rather that there is a fault, can also be readily discerned when considering the expression $\frac{k}{0.5k(n-j)}$ -- the multiplicity of edges is considered when counting the lower bound for edges (the denominator), but then it is completely ignored, when all those edges are contracted, by only considering a single one.

Please enlighten me as to what/if it/there is I am missing.


texts:
I've seen scattered references to typed assembly in high assurance literature, but I don't really understand the advantage.

If the compiler/runtime are capable of passing the types down to the CPU, then aren't they are capable of emitting equivalent checks in assembly?  Bloating an instruction set with high-level primitives increases the complexity of the assembler and slows down execution time because the assembler is busy doing the compiler's job.

It sounds like this would make a compiler writer's job easier but expands the TCB without any real gains in speed or safety.


texts:
I've defined the identity function in Agda as follows:

idd : (∀ {ℓ} {A: Set ℓ}) → A → A
idd a = a

I want to ask you if the following reasonings are correct:

The type of this function is A -> A.
idd is a polymorphic function, where (∀ {ℓ} {A: Set ℓ}) matches any type.
Because is a polymorphic function, I can say idd is of dependent type.


texts:
Currently I am developing a piece of software that solves the vehicle routing problem.

The task is the following:

I have several vehicles along the town
I have lots of destination points along the town
Vehicles have delievering product on board, and the product is uniform (it doesn't matter if you receive it from vehicle A versus vehicle B)
Let assume that vehicles can not run out of products
The number of destination points is greater than the number of available vehicles
I need to calculate optimal routes through multiple points for every vehicle to minimize the average transportation time

My naive approach is the following:

find nearest points for each vehicle using k-means clustering with the raw euclidean distance between map points (LngLat points)
for each vehicle for each destination point from the set of vehicle's nearest destination points calculate optimal routes using other destination points as intermediate points and find routes with smallest avarage transportation time (optimal route from point A to point B crossing several intermediate points can be received from Google Maps API so it is not necessary to use TSP algorithm for it).

It seems that this approach may give results which are not optimal.

Is there better approach which provides better accuracy and/or smaller amount of API requests?


texts:
Popular view tells us that any kind of information is just a collection of bits, that is zeroes and ones placed in a particular order. I was thus having this thought.

Suppose that I have some kind of file such as a text document, a PDF or anything else and that I also have a memory so perfect that I can remember the file exactly in its binary format, i.e. the number and place of zeroes and ones. But nothing else.

My question would then be if, in practice, it would be possible to reconstruct my initial file (without imposing any assumptions on what format it takes) from just this binary format.

Please be advised that I am not an expert in computer science and I do have only some very basic understanding. I do hope though this question fits here.


texts: Is there a context free, non-regular language $L$, for which $L^*$ is regular?

texts:
I know that there are non-regular languages, so that $L^*$ is regular, but all examples I can find are context-sensitive but not context free.

In case there are none how do you prove it?


texts:
I am trying to design an algorithm to compute the solution to this problem.

Given a list of n tournaments with a name, start_date, end_date, latitude and longitude, find the list of p tournaments in chronological order with the least total travel distance when a person has to travel from one tournament to the next to the next.

A valid list of tournaments (called a tour) is where there are no overlaps in dates. The sports person travels from one tournament to the next along the straight line between the 2 coordinates.

I have a working solution but it uses too much memory.

I start by building a graph where nodes are tournaments and edges are the straight line distances between the coordinates of a node and a child_node. Each node has child nodes representing only tournaments which occur after it.

I then define a tour as a list of these nodes.

I start with a previous_tours list (containing tours of length i) and a current_tours list (containing tours of length i + 1). The previous_tours list is initialised with tours of length 1, which is just n tours each with one of the nodes.

Then to calculate the current_tours list, I loop through the previous_tours list and for each tour (current_tour) I get the last_node in the tour. Then for each child_node in last_node, I copy the current_tour and append the child_node to the end of the tour and add each copy to the current_tours list. This calculates all possible tours of length 2 as nodes only have child nodes occuring after it. The distance between the last_node coordinates and the child_node coordinates is added to the tours total travel distance. I then set previous_tours to current_tours.

I repeat this until I have all possible tours of length p. Then I loop through this list to find the one with the least total travel distance.

This is giving me the correct answer, but I am giving it a list of 120 tournaments and trying to calculate the best tour of length 4 and it uses around 5GB of memory when I implemented it in C++

I was thinking of just adding in a heuristic at each iteration to cut down the number of possible tours.

Does anyone know a more efficient way of getting this result without using a heuristic in that way?


texts: What does "Every CFL is decidable" exactly mean?

texts:
I am trying to prove the fact that every CFL is decidable, however I can't come to terms with what the statement exactly means.

I know that generation of a particular string by a given CFG is a decidable problem. This means that we can design a TM that will definitely halt and tell us whether the given string is generated by a CFG.

But coming to this problem, what does it mean? I am making the interpretation that this means - The problem of determining whether a given arbitrary language is a CFL is decidable.

Am I right or does it mean something else?


texts: Understanding a few intricacies related to two naive algorithms to compute the convex hull of a set of points

texts:
I already understood how the well-known algorithms like Graham's scan, Quickhull, etc. work, but I have difficulties in understanding 2 naive algorithms to compute the convex hull:

  Let $S= \{p_1, \dots , p_n \}$ a set of points and $CH(S)$ the convex hull of $S$.

The first problem and corresponding algorithm are as follows.

  Find the smallest subset $R \subset S$ for $CH(R) = CH(S)$. Since there are $2^n$ subsets, the complexity is $\mathcal{O}(2^n)$.

Pseudocode version:

foreach (s in S.subsets)
    if (CH(R) == CH(S))
        return R

Since we don't know $CH(S)$, and indeed it's our goal to compute $CH(S)$, how can we check if $CH(R) = CH(S)$?

The second problem is as follows.

  Let $p,q,r,s \in S$. $s \in CH(S)$, if $s \not\in triangle(p,q,r)$

And here is the algorithm:

Shouldn't the first part of the sentence (of the problem) be

  Let $p,q,r \in CH(S)$ and $s \in S$.

?

However, even in this case, we don't know what $CH(S)$ is.

My counterexample why this algorithm wouldn't work:

At the start, we check the $triangle(1, 2, 3)$, and see that $4$ is not in the triangle, and mark $4$ as not an element of the convex hull, but $4$ should be part of the CH!


texts: Are $\log_{10}(x)$ and $\log_2(x)$ in the same big-O class of functions?

texts: Are $\log_{10}(x)$ and $\log_{2}(x)$ in the same big-O class of functions? In other words, can one say that $\log_{10}(x)=O(\log x)$ and $\log_{2}(x)=O(\log x)$?


texts: Doing beta reduction while constructing the boolean expression in lambda calculus

texts:
I am going through beta reduction in lambda calculus . And beta reduction to my understanding is an act of  substitution  like in the following :

$ (\lambda x.P) M $ is said to be beta reduced to : $ [M/x]P $

So then my course was led to encoding the Booleans in lambda calculus . And the following two expressions were used to encode the true and false boolean expressions :

$ \lambda xy.x$ for true denoted by T

and $ \lambda xy.y$ for false denoted by F

The basic idea behind constructing these expressions is to find expressions that
 analogically mimic the "and" operation if the "application" is the couterpart of "and"

So , for the above two expressions the book says $TT = T $ ,$ FF = F $, $TF= F $ , $FT=F $.

I tried to  do the beta reduction for ($ \lambda xy.x$ )($ \lambda xy.x$ ), which means [ $ \lambda xy.x$ /$x$]$ \lambda xy.x$ .

I could break $ \lambda xy.x$  as $\lambda x . \lambda y.xy  $ but I am unable to find how to use this to advantage to get  the final reduction .

How to carry on the reduction from here so as to prove that ($ \lambda xy.x$ )($ \lambda xy.x$ ) = $ \lambda xy.x$  ?


texts: Running time of greedy scheduling algorithm

texts:
Here is an algorithm to output a subset of activities S such that no activities in S overlap and profit(S) is maximum.

Define $p[i]$ to be the largest index $j$ such that $a_j$ does not overlap $a_i$.

$\#$ Return maximum possible profit from $a_1,...,a_n$

def rec_opt(n):
    if n == 0:
        return 0
    else:
        return max(rec_opt(n-1), w_n + rec_opt(p[n]))

It doesn't mention what $w_n$ is in the slide, but I think it is the profit of the activity $a_n$.

  Consider a set of $n$ activities where there is no overlap at all. Then $T(n) = 2T(n − 1) + c$. This recurrence has an exponential closed-form, $O(2^n)$.

"return max(rec_opt(n-1), w_n + rec_opt(p[n]))": I think this line takes time $2T(n-1)$.
"if n == 0": this line takes time $c$.

Am I correct?

One more question, how can we get $O(2^n)$ from $T(n) = 2T(n − 1) + c$?


texts:
Suppose that we are given an undirected graph, and we know that the maximum edges covered by $k$ vertices is $n$. If we let the greedy algorithm choose these $k$ vertices for us, I am told that it is capable of covering at least $n/2$ edges. Is there a way to prove this? If so, how should it be done?

Since the greedy algorithm removes the vertex with the maximum degree still left in the original graph (along with its incident edges) in each iteration, is it possible to find a connection between the minimal number of edges removed each time by the greedy algorithm to the optimal solution $n$?

I am truly clueless about how such a problem should be solved.

Hints or references are both welcome. Many thanks.


texts: Metaheuristic for NP-complete problem without exact algorithms other than brute-force

texts:
Computing Pure Nash Equilibria (PNE) is a Game Theory related problem.
Deciding if there exists PNE in a given game has been shown to be NP-Complete (Gottlob et al.).

I want to design a metaheuristic algorithm that spits out a strategy that is either a PNE or an approximation of such. A metaheuristic algorithm would not guarantee a global optimal solution but might produce a sufficiently good solution. i.e. I want to view the problem as an optimization problem.

To the best of my efforts, I couldn't find any exact algorithms that solves the decision problem other than iterating over all possible strategies (brute-force).

I've tried implementing some basic metaheuristics (evolutionary algorithm, GSAT-like algorithm, ...) and find 'good' solutions in a 'timely' fashion. I put quotation marks because I can't prove if the algorithm is in fact good and/or fast (it uses metaheuristics). Hence the following question:

Is it useful to design metaheuristic algorithms for a problem like this when its performance can not be shown by comparing it to other (exact) algorithms?


texts: How advanced is the study of mathematically determining computational power comsumption?

texts:
I was thinking about how effective it would be to calculate the number of CPU instructions a section of code would have and then trying to estimate the energy cost for a program.

But I was curious if there were more elegant ways of going about this?


texts: Using cross-products with relational algebra

texts:
I have some questions about something that I'm working on in an assignment for my database class.

Here is the schema for the questions I'm working on, so that you know what to refer to:

Category(class, function, country, num_guns, max_altitude, max_fuel)
Planes(pname, class, year)
DogFights(dname, date)
Outcomes(pname, dname, result)

The first few questions I worked on I was able to get just fine since they were just using the projection and select operations, but I'm getting a little confused with the next few.  I'm guessing that I will likely have to use the cross-product somewhere, but I just don't quite know how I would use it.

The questions are the following:
What are the names of the planes that carried the least amount of fuel in the Battle over Pearl Harbor?

What are the names of planes that can carry more fuel than the Memphis Belle?

What are the names of all the planes that participated in a dog fight in which Hard Luck also participated?

Today in our clas, we did go over Cartesian products a little more in relation to relational algebra, and I have got a little bit of an understanding now. In the question just before the ones I posted here, it's asking what class of plane can fly the highest, and I figured it out using an example we did in class today. For that question I figured out the following:

`Category * c(Category)

PA <- ∏class(category.max_altitude < c.max_altitude(Category * c(Category))

∏class(category) - PA`

So for those questions I posted, would I just do something like this in conjunction with the projection and select operations?


texts: Find largest and second largest elements of the array

texts:
So here is a HW problem I have been working. On I was wondering if anybody could give me a hint of what I am doing wrong. I don't want to be given the answer just hints and advice on how to solve it.

I am given this simple algorithm that finds the greatest value and the second greatest value in a array.

  If A[1] < A[2],
        largest = A[2], Second = A[1]
    else
        largest = A[1], Second = A[2];
    For i in range 3 to n {
        If A[i] > largest {
         second = largest;
        largest = A[i];
        }
        else
            if A[i] > second
                second = A[i]
    }

My first task was to find the number of comparisons it makes not in big-oh terms. So I said 2n-3 because it has one in the beginning and worst case
the largest element is in the first two elements of the array A so from
index 3 to n it has two comparisons. So 1 + 2(n-2) = 2n - 3 comparisons.

My second task was to develop an algorithm that would use less comparisons. So I broke it down with divide and conquer and said this.

 // start is the first index inclusive
        // finish is the last index inclusive
        // A is an array of elements
        function getGreatestAndSecondGreatestValue(A, start, finish) {
            T[] // T is an array of size 2
            if(finish - start == 1) {
                if(A[start] > A[finish]) {
                    T[0] = A[start]
                    T[1] = A[finish]
                } else {
                    T[0] = A[finish]
                    T[1] = A[start]
                }
                return T
            }

            Array1 = getGreatestAndSecondGreatestValue(A,start, start + floor((last-first)/2))
            Array2 = getGreatestAndSecondGreatestValue(A, start + ceil((last-first)/2), finish)
            return merge(Array1, Array2);
            // The greast value will be in the 0th index of the array returned and the second
            // greatest value will be in the 1 index of the array.
        }

        // this merges two arrays keeping the greatest value on the left side of the new array and
        // keeping the second greatest value on the right side of the array
        function merge(Array1, Array2) {
            MergedArray[] // array that will hold the merged results
            if(Array1[0] > Array2[0]) {
                MergedArray[0] = Array1[0]
                MergedArray[1] = max(Array[1], Array2[0])
            } else {
                MergedArray[0] = Array2[0]
                MergedArray[1] = max(Array1[0], Array2[1])
            }
            return MergedArray
        }

For example this say we had the array

[1,4,5,2,7,9,10,19]

then is divides it

[1, 4, 5, 2] [7, 9, 10, 19]

then when it reaches a length 2 is places the highest value in index 0 for arrays the size 2

[4, 1] [5, 2] [9, 7] [19, 10]

I would then proceed to merge these

[5, 4] [19, 10]

[19, 10]

Then the greatest value is 19 and the second greatest was 10.

I then proceeded to find the number of comparisons with recurrences.

T(n) = 2T(n) + 2

There are n leaf nodes because $ 2^{log_{2}(n)} = n $ where $ log_{2}(n) $
is the height of the tree. There are then n - 1 internal nodes so n + n - 1 is 2n - 1. 2 is added to every node so then it would be 4n - 2.

For some reason after using a divide and conquer algorithm I am getting a higher number of comparisons and I am not sure why. Could somebody give me some advice on why this didn't work?


texts:
So it seems that you can get pretty far with just type definitions as a formal model of a system. The typed properties verify that the properties will have that type, typed function arguments verify the functions will get the appropriate input and output types, etc.

But now I am wondering about algorithms. In an ideal world an algorithm would just be a typed object as well and the algorithm's correctness would be inherent in the type definitions. I can't see how that would be possible, so I resort back to my brief readings of proving algorithms. Essentially you want to have an assertion before and after any loop, to establish a loop invariant. This way you can reason through induction that every step of the algorithm works as expected.

I am just not sure what I want to prove in the first place. I would like to have my code be:

Robust.
Fault tolerant.
Fast.
Bug-free.
Scalable.
All the things you would typically want.

So I define a specification for the algorithm:

The algorithm should return a type x object (types handle it automatically).
The algorithm should ~~ chug through the elements one at a time and compute a sum (lets say) ~~. That's where it starts to get fuzzy. Wondering if this is where the "loop invariant" comes in.
If there are no loops or branching in the algorithm (but maybe if-statements), then I want to prove (or "validate") that the value falls within some set of acceptable values.
etc.

So it seems that the quality of the application is dependent on how well-specified the behavior is. If you miss edge-cases, there will be bugs. If you don't specify the acceptable output values of the function, then you may get XSS. Wondering if that is a correct assessment, that everything revolves around the specification. Without that, there is nothing to prove.

Then it seems that you need to do testing first, in order to even comprehend the types of things you want to prove to be correct. It's like you start with some unit tests, and slowly evolve it to proofs. Wondering if that is a correct assessment. Once you know all the inputs and outputs of the algorithm through some thorough testing, then you can write some sort of proof that the algorithm is correct and avoids the error cases. This just seems like a really good unit test.

To summarize, it seems like what you want to prove with algorithms is that they are correct with regards to a specification. And the specification is a living document that you can start out with by writing unit tests which slowly evolve into proofs (somehow).

Just looking for some pointers on if I am on the right track, and how to know what to prove in an algorithm.


texts:
I'm trying to understand/show that DNF VALID is coNP-hard. I have given an algorithm for the complement of DNF VALID and shown that this is in NP (since the complement of a language in NP is in coNP), but I'm really struggling to show that DNF VALID is coNP-hard.

  The complement of DNF VALID = {ϕ | ϕ is not in DNF OR ϕ is falsifiable}

A simple algorithm for the complement of DNF VALID:

On a non-deterministic TM M: "on input ϕ (boolean formula):
 1. Scan through ϕ and check whether ϕ is on DNF.
      If it is, accept,
      if not, continue to step 2.
 2. Non-deterministically choose a valuation for ϕ
 3. If ϕ is falsifiable accept, if not, reject

To show that DNF VALID is coNP-hard I think that I need to show that a language that is NP-complete can be reduced in polynomial time to the complement of DNF VALID, but I'm not sure with which language to choose, and I could really use some help on how to go forth with the reduction.


texts: What are some real world applications of graphs?

texts:
Can you give some real world examples of what graphs algorithms people are actually using in applications?

Given a complicated graphs, say social networks, what properties/quantity people want to know about them?

—-

It would be great if you can give some references. Thanks.


texts:
Would be possible to encode dependent types as regular expressions? if so, ¿is there some work about?

It's common to represent restrictions for elements in a traversable data structure with them, like clojure.spec do for sequences. But
i tried to find some references about using them to represent restrictions at type level with no luck.

Some examples in seudo haskell syntax:

unboundInts :: Int *
-- accepted by typechecker
unboundInts = [] | [1] | [1..] | ["whatever",1,1.2]
-- rejected
unboundInts = ["whatever"]

threeIntsAndChars :: ^ Int {3} Char + $
-- accepted
threeIntsAndChars = [1,2,3,'a'] | [4,5,6,'a'..'z']
-- rejected
threeIntsAndChars = [] | ["whatever",1,2,3,'a'] | [1,2,3,'a',"whatever"] | [1,2,3] | [1,2,'a'] | ...

-- accepted
data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
threeIntsAndChars = Node (Node (Leaf 1) 2 (leaf 3)) 'a' (Leaf 'b')


texts: Lower Bound for Comparison-based sorting algorithms

texts:
We know that the lower bound for comparison-based sorting algorithms is Ω(nlogn), where logn being the binary logarithm of n. But what about for the best-case scenario of the bubble sort, which takes O(n) time? Of course, n is faster than nlogn. Why is that?

However, I don't know if this bound only applies for the worst-case scenario. I haven't ever learned the lower bound for the best- or average-case scenario. Is it different from the other?

(This question comes from the http://cstheory.stackexchange.com)


texts: Perceptron and non linearly seprable data

texts:
I was asked in an interview question, can a perceptron classifier ever reach 100% accuracy on some kind of non linearly seprabale training data in 2D.
I said that no it can't because the data is not linearly seprabale.
We then proceed to the next question, but maybe its just me, but from the look of the interviewr, I'm
not sure that was the right answer.
Am I missing something or just paranoid? Can the perceptron reach 100% accuracy on any training data?
Thanks!


texts: Is there a known way to make an efficient, compact, and fully persistent stack or queue?

texts:
In the world of mutable/ephemeral data structures and imperative programming languages, one of the classic ways to implement a stack or queue is to use array doubling: use mutation to fill up or empty an array, doubling or halving to expand/contract. Such stacks/queues have several nice properties:

They use at most twice as much memory as strictly necessary.
They involve minimal indirection.
They use cache efficiently.
They have amortized $O(1)$ insertion and deletion operations.

In a purely functional system, this approach falls down quite flat, because "mutate the array to fill/empty" becomes very expensive: the array has to be copied each time. I was wondering if there might be some reasonable compromise approach, making something more compact than classical approaches (a la Okasaki) but still with constant amortized time operations. Stacks are simpler, so I started thinking about those. My first attempt (in Haskell notation) was
data Stack a
  = Shallow !(Array a)
  | Deep !(Array a) (Stack a)

with the rule that the array at depth $n$ must have either $0$ or $2^n$ elements. Unfortunately, this doesn't look like it's nearly good enough. It appears that insertions impose an $O(\log n)$ amortized cost, since flipping from a 1 digit to a 0 digit gets more expensive the deeper it happens in the tree. My next attempt was the same, but using skew binary numbers instead of binary numbers (I didn't actually work this one out in full, so it might not even make sense). Same deal. Is there some trick I'm missing, or am I asking to have my cake and eat it too?


texts: Appropiate data structure storing a tree

texts:
So I have an input of the type:

Node parent

but the problem is that the nodes and parent aren't given in a specific order starting from root, and I want to build a Trie but I can't because of this aspect, I thought about using a queue with Trie nodes, and when their parent appear I will pop them from the queue, but there is a problem since what if their parents are already in the queue? And I don't know how to solve this problem.. or to solve it efficiently

sample input:
1 0
0 -1
2 1
3 0
4 3

-1 as a parent means it is the root node, observe the order is random.


texts:
What is a Context? Is it like a scope in C? Does it have a start and an end? Can contexts contain other contexts?

I see Contexts being used in lambda calculi type system rules, but I don't understand concretely what they are and why they are necessary. If they are too abstract, then is there some visual or metaphorical description?

Update: I am referring to "contexts" as what is to the left of ⊢ in typing calculi.


texts:
I am trying to find the running time of the given recurrence by the Master Theorem: $T(n)=16T(\frac{n}{2})+n^3\log^4 n$

I get $a=16$, $b=2$ and $f(n)=n^3\log^4n$, It seems that it's Case 1 of the master theorem. because $f(n)=O(n^{4-\epsilon})$ for some $\epsilon >0$ (?)

but I can't find this epsilon, and I am doubting if I can truly use the Master Theorem in this case.

What's I am missing?


texts:
Let G be a directed graph such that every two vertices are connected by a single edge.
How do I proof that such G has an hamiltonian path?


texts: Efficient algorithm for graph canonization for directed acyclic graphs?

texts:
I'm interesting in generating directed acyclic graphs (see here, for example). As part of this search, I'm curious if there are any efficient algorithms for determining a canonization of a directed acyclic graph. Or, are there any tricks that allow the canonization of a dag to be computed more efficiently than a general graph?

Determining the canonical form in general is GI-complete, but there are many specialized graphs for which it can be calculated in polynomial time.  I didn't have any luck determining whether acyclic digraphs were among those specialized types, however.


texts: Associativity vs blocks per set in fixed size caches

texts:
I am trying to understand the following claim:

  For a fixed size cache, each increase by a factor of two
  in associativity doubles the number of blocks per set
  (i.e., the number or ways) and halves the number of
  sets – decreases the size of the index by 1 bit and
  increases the size of the tag by 1 bit.

I am just wondering if someone can clear this up for me. For example, if there is a cache with 16 cachelines and it's 2-associative the number of blocks per set is 8, but if we increase by a factor of two associativity then the number of blocks per set decreases to 4.


texts: How is an Assembly Language Processed by a CPU's Circuitry?

texts:
I'd like to have a bit more understanding of how, on a circuitry/hardware level, an assembler program works.

I think I have a very broad-brush understanding of how a CPU would process machine code on a hardware level. Please bear with me for this very generalised, hypothetical example:

If you took 00101110 in machine code, with the first part 0010 as an opcode and the second part 1110 as location address...

I think I understand, broadly, how those 8 bits of data would be fed along 8 wires to an instruction register, and how from there, the opcode 0010 gets fed along 4 wires into a variety of checking circuits to check the opcode, and a checking circuit would output true if if the opcode corresponded to the configuration of that circuit. Like this (yes I've been watching crash course computer science):

And i think I understand how, in broad terms, the location address 0111 would be sent along 4 wires that feed into multiplexors attached to four latch matrices, causing address location 0111 to be accessed in each of those matrices, each of which then feeds back whether its data bit at the location was a 1 or 0 / on or off.

What I'm saying is that I think I can begin to see, or at least imagine, how a processor 'processes' a binary number, on the level of hardware/circuitry, without it seeming like magic.

My question is, can someone explain to me on this level how a CPU, as part of an assembler, would translate assembly code?

For example, how would the circuitry take MOV EAX [EBX] and act on that as an instruction? I know that it would parse it, etc., but HOW does it parse it, on the level of wiring? Like how does it take a 'MOV' and translate that into the correct configuration of on/off wires?

On a related note, obviously the 'MOV' isn't stored as 'MOV' in the computer's memory - it's stored in binary. So if it's already stored in binary, why do we need to bother to translate it to a different binary configuration using an assembler?


texts: Prolog: Deletion of all appearances of an element in a list

texts:
I am trying to create a predicate in Prolog which allows me to delete all occurrences of X in a list L. I have the following code:
my_delete(X, L, R):- [] = L, [] = R
my_delete(X, L, R):- [Y|K] = L, [Y|M] = R, my_delete(X, K, M), (Y \= X)
my_delete(X, L, R):- [X|K] = L, [Y|M] = R, my_delete(X, K, R), (Y \= X)

And now, upon querying this following line, I receive no result, implying that no list R could be constructed so that it followed my requirements.
?:- my_delete(baz, [foo, bar, baz], X)

The construction works fine when the list I want to delete from didn't contain an occurrence of X in the first place, but not if it did.
Why is my set of predicates insufficient? What needs to be changed?


texts: Coding for data compression with large target's symbol set (where the target symbol set is larger than the source symbol set)

texts:
For data compression, every codding that I've seen is binary. It means we convert a language with $N$ symbol size to a language with $M=2$ symbol size. For example, in Huffman coding, the goal is to find a binary coding ($M=2$) for English language ($N=26$).

If $M$ is not equal to $2$ and have a value larger than $N$, is there any method to find good coding (or optimal coding) for compression? Is there any research for this type of problem?
Is it a right assumption that when the target symbol size is larger, the goal is to find a map from a subset of source symbols to one target symbol?


texts: How is switching among user-level threads realised in the user space?

texts:
This is with respect to user-level threads where the kernel only knows about the process as a whole, and threads are created and maintained in the user space. Each thread has its PC, registers, stack and thread control block. To my knowledge, updating PC (or any system register) or access of the code segment can only be done in the kernel mode (since it has to be protected from outside access). If this is true, how can user-level threads maintain (or update) their state information (PC, other registers, thread control block, etc.) at the user level instead of the kernel level?

To put it in short, could anyone please explain what actually happens under the hood, and how thread-level context switches are realised at the user level?


texts:
I'm searching a data structure that supports O(1) concurrent insertions (thread number is known in advance) and iteration over its elements (insertion order doesn't need to be preserved).
While one thread is iterating over the elements there won't be any insertions.
So basically I'm looking for a concurrent dynamic array...
Currently I'm using a std::vector and a mutex, but I have the feeling there might be something faster.

Thanks in advance!


texts:
I am reading Long-term Temporal Convolutions for Action Recognition and under the Section 3.1, I read this:

To investigate the impact of long-term temporal convolutions, we here study network inputs with different temporal extents.....

and then

As illustrated in Figure 2, the temporal resolution in our 60f network corresponds to 60, 30, 15, 7 and 3 frames for each of the five convolutional layers. In comparison, the temporal resolution of the 16f network is reduced more drastically to 16, 8, 4, 2 and 1 frame at each convolutional layer. We believe that preserving the temporal resolution at higher convolutional layers should enable learning more complex temporal patterns. The space-time resolution for the outputs of the fifth convolutional layers is $3 \times 3 \times 1$ and $1 \times 1 \times 3$ for the 16f and 60f networks respectively. The two networks have a similar number of parameters in the fc6 layer and the same number of parameters in all other layers. For a systematic study of networks with different input resolutions we also evaluate the effect of increased temporal resolution $t \in \{20, 40, 60, 80, 100\}$ and varying spatial resolution of $\{58 \times 58, 71 \times 71\}$ pixels.

How can we reduce temporal resolution of a ConvNet at each convolutional layer.
What does preserving the temporal resolutional mean and what does complex temporal resolution mean?
I've taken courses on Convolutional Neural Network and never heard of anything such as "temporal extent" or "temporal resolutions". Searching about them gives links to other research paper, which still use the term without describing its meaning.
Anyone, kindly put some light on it.


texts: Where can i find a list of problems reducible to max flow and matching problems. I need such examples to learn and practice .


texts: Algorithmic complexity of Sub-array with sum = target algorithm

texts:
Question:  Given an array of positive integers and a target total of X, find if there exists a contiguous subarray with sum = X

E.g:  If array is [1, 3, 5, 18] and X = 8 Output: True, if X = 10, output is FALSE.

Approach I can think of is to expand sub-array window, until you hit an index such that sum of sub-array == target or > target.  If > target, decrease sub-array by moving first element to the right.

It appears that in worst-case complexity is O(N) since I am moving either start or end index of sub-arrays, so int worst case I will just spend 2*N iterations. Is that correct analysis?

BOOL checkIfArrHasSum(long *arr, size_t size; long target)
{
  long currSum = [arr[0] longValue];
  long startInd = 0;
  long nextIndToCheck = 1;

  while (nextIndToCheck < size)
  {
    if(currSum == target) return YES;

    if (currSum + arr[nextIndToCheck] == target)
      return YES;
    else if(currSum + arr[nextIndToCheck] < target)
    {
      currSum = currSum + arr[nextIndToCheck];
      nextIndToCheck++;
    }
    else
    {
      currSum = currSum - arr[startInd];
      startInd++;
    }
    if(startInd == nextIndToCheck)
    {
        nextIndToCheck = startInd+1;
        currSum = arr[nextIndToCheck];
    }
  }

  return NO;
}


texts:
I have a graph with V vertices and E edges. Each edge is a road that takes fuel F to travel. I have a gas tank of capacity K, and want to find the fewest number of refills needed to go from any vertex to any other vertex. If I choose to refuel, I can fill the tank completely.

My thought is to modify the Floyd - Warshall Algorithm to keep track of both number of refills, and amount of gas left. However, I am not sure how to proceed.

Note: This is NOT a HW question. I was reading To Fill or not to Fill: The Gas Station Problem and began to wonder.


texts: Difference between the logic and the type system of a proof assistant?

texts:
In Comparing Mathematical Provers (section 4.1), Wiedijk classifies logics and type systems of different proof assistants? I do not see what he means by type system of the assistant. He only says:

A system is only considered typed when the types are first class objects that occur in variable declarations and quantifiers.

I can only think of types in goals. For instance, in Isabelle if you write a goal using variables (I don't think you "declare" variables", you can check the type of these variables. But this type is certainly a type in the logic I'm using.
It would be interesting to clarify this and apply this example in the cases of Isabelle, Coq and Metamath (which is untyped and apparently based on proof trees, which could give a hint).


texts: Is the capacity achieving input of a discrete memoryless channel unique?

texts:
Consider a classical discrete memoryless channel (DMC). Let $p$ be an input probability distribution and $Q$ be the channel's transition matrix. $q = Qp$ is a valid output probability distribution. The components of $p$ and $q$ are given as $p_i$ and $q_i$ respectively.

The capacity of this channel is given by maximizing the mutual information.

$$I = \max_{p}\left[\sum_ip_i\left(\sum_{j}Q_{ij}\log(Q_{ij})\right) - \sum_{j}q_j\log q_j\right]$$

But, we know (Theorem 2.7.4 in Cover and Thomas, 2006) that $I(p)$ is concave in $p$.

If $I(p)$ is not simply a linear function (i.e. $q = Qp$ is not a trivial relationship) and is differentiable everywhere (seems like a reasonable assumption), does this not imply that the capacity achieving $p$ is unique?


texts: Efficient algorithm to simulate dealing cards from a large deck of cards?

texts:
In shedding-type card games, the dealer starts by dealing a shuffled deck of cards to the players (if there are N players, card i goes to player i mod N). If the number of each type of card is known, is there a way to simulate dealing the cards and get a count of each type of card each player has?

For example, if there are N=3 players, and there are 5 card types and the count of each card is [3000000000, 3000000000, 3000000000, 3000000000, 2], one possible output is [1000000000, 1000000000, 1000000000, 1000000000, 1], [1000000000, 1000000000, 1000000000, 1000000000, 1], [1000000000, 1000000000, 1000000000, 1000000000, 0], which represents the number of cards of each type that each player has.

A naive algorithm is to create a large array of all of the cards, do the Fisher–Yates shuffle on it, and then go through each element and increment the count of the card for the current player and set the current player to the next player. For the example above, this creates an array of size 12000000002 and requires that many iterations, but there are only 5 card types and 3 players (output is size 15).

Is there a more efficient algorithm? It would have to generate the output with the same probability that the naive algorithm would.


texts: Why do intuitionists accept the nonconstructive proof that the halting problem is undecidable?

texts:
On the intuitionism page at Stanford Encyclopedia of Philosophy (SEP), it's said in Section 3.3 that

  Because of the finiteness of a natural number in contrast to, for example, a real number, many arithmetical statements of a finite nature that are true in classical mathematics are so in intuitionism as well. For example, in intuitionism every natural number has a prime factorization; there exist computably enumerable sets that are not computable...

This uncomputability result must necessarily use the halting problem, whose uncomputability is proved unconstructively, as it relies on the law of the excluded middle: TM $M$ of input $\langle M\rangle$ either halts or not. This is not constructive because it might be impossible to know whether the TM runs forever. If you can prove for every case that the TM runs forever when it indeed does, then the collection of such proofs results in an algorithm that decides haltingness. So this proof is not constructive. But SEP says that intuitionists accept it! Isn't intuitionism a constructive theory? Or are there other constructive proofs of the halting problem that I don't know?


texts: Sorting criteria for Kruskal's algorithm

texts:
I am studying Kruskal's algorithm. Is the only acceptable sorting criteria to sort edges from lowest weighted edge to greatest weighted edge? I ask this because I assume that if the algorithm used an alternative sorting criteria say, greatest to lowest, then it would not produce a MST. My reasoning is that edges with larger weights would be added first.
Any help with this concept would be greatly appreciated.


texts: Decomposition of the set of computable functions into base functions

texts:
Say I have some computation model/programming language $M$ (e.g. Turing machine or equivalent), and let $C_M$ be the set of all partial or total functions $f : \mathbb{N} \to \mathbb{N}$ computable by that model. Also, assume that $C_M$ is countable.

Now let $B = \{ B_1, B_2, ... , B_n \}$ a finite set of computable base functions and $\cdot : C_M \times C_M \to C_M$ an binary operator, which serves as a combination function. Thus, $(B,\cdot)$ is a magma.

I can now choose $B$ and $\cdot$ in such a way that I can decompose each computable function $f \in C_M$ into a finite product from $(B,\cdot)$, i.e. $\forall f \in C_M : \exists b_1, b_2, ..., b_k \in B : f = b_1 \cdot b_2 \cdot ... \cdot b_k$.

To show that, I consider that my programming language consists of a set of instructions $I$ and programs are words over $I$. Then, I choose exaclty one base function $b_{i,m}$ for each instruction $i_m$. Because each computable function $f$ has at least one program computing it, I can just pick one of those $f$-computing programs $P_f \in I^*$ and define
$b_{i,a} \cdot b_{i,b} \cdot b_{i,c} ...  = f$ when the program is the word $P_f = i_a i_b i_c ...$.

This decomposition is obviously not very useful, because it makes the base vectors arbitrary and the definition of $\cdot$ an infinite list of special cases. To consider it useful, the operator $\cdot$ should have some form of structure/finite definition, or in other words, be computable. My interest would be an element-wise function, so that given two values $f(x)$ and $g(x)$, it should be possible to compute $(f\cdot g)(x)$.

My question: Assuming $M$ is turing-complete, is it possible to choose $(B,\cdot)$ in such a way that $\cdot$ is elementwise computable, i.e.

$\exists h \in C_M : \forall f,g \in C_M : \forall x \in \mathbb{N} : (f\cdot g)(x) = h(f(x), g(x))$

and still have each computable function being decomposable into a finite product from $(B,\cdot)$?


texts: How to find LCA in a directed acyclic graph?

texts:
Firstly, I am trying to understand the meaning of LCA in DAG. I read a definition somewhere-"Define the height of a vertex v in a DAG to be the length of the longest path from root to v. Among the vertices that are ancestors of both v and w, the one with the greatest height is an LCA of v and w."

In a graph like this 1->3 1->4 2->3 2->4, 3 and 4 will have multiple LCA's because the height of 1 and 2 would be same.

So, How can I proceed to implement this? I am thinking of applying the same approach that we used to find LCA in a binary tree by starting from root node (In this case, nodes having in_degree=0) but due to cross edges between the nodes this approach wouldn't work.eg. 1->2 1->3 3->2.

So, Is there some better way to find the LCA in DAG's?


texts:
Suppose we're receiving numbers in a stream. After each number is received, a weighted sum of the last $N$ numbers needs to be calculated, where the weights are always the same, but arbitrary.

How efficiently can this done if we are allowed to keep a data structure to help with the computation? Can we do any better than $\Theta(N)$, i.e. recomputing the sum each time a number is received?

For example:
Suppose the weights are $W= \langle w_1, w_2, w_3, w_4\rangle$. At one point we have the list of last $N$ numbers $L_1= \langle a, b, c, d \rangle>$, and the weighted sum $S_1=w_1*a+w_2*b+w_3*c+w_4*d$.

When another number, $e$, is received, we update the list to get $L_2= \langle b,c,d,e\rangle$ and we need to compute $S_2=w_1*b+w_2*c+w_3*d+w_4*e$.

Consideration using FFT
A special case of this problem appears to be solvable efficiently by employing the Fast Fourier Transform. Here, we compute the weighed sums $S$ in multiples of $N$. In other words, we receive $N$ numbers and only then can we compute the corresponding $N$ weighed sums. To do this, we need $N-1$ past numbers (for which sums have already been computed), and $N$ new numbers, in total $2N-1$ numbers.

If this vector of input numbers and the weight vector $W$ define the coefficients of the polynomials $P(x)$ and $Q(x)$, with coefficients in $Q$ reversed, we see that the product $P(x)\times Q(x)$ is a polynomial whose coefficients in front of $x^{N-1}$ up to $x^{2N-2}$ are exactly the weighted sums we seek. These can be computed using FFT in $\Theta(N*\log (N))$ time, which gives us an average of $Θ(\log (N))$ time per input number.

This is however not a solution the the problem as stated, because it is required that the weighted sum is computed efficiently each time a new number is received - we cannot delay the computation.


texts: 5-state DFA that recognizes only the string 00001111

texts:
I'm having trouble coming up with a 5-state DFA that, on all inputs of length 8, recognizes the string 00001111 and no other string (of length 8). The DFA must have an exiting transition for every symbol in the alphabet (namely {0, 1}). The behavior on input of other lengths does not matter. A 6-state solution is pretty simple, but reducing down to 5 states requires more sophistication.
Any help would be appreciated!


texts:
I am currently working through Tiernan's paper, "An efficient search algorithm to find the elementary circuits of a graph" (published 1970), and I am stuck on point 3 of the following excerpt:

  The algorithm is named EC for "elementary circuit." The function blocks of EC are denoted EC1, EC2, etc. EC requires that there be assigned to the vertices, in any order, the integer designators 1, 2, .-., N. The algorithm utilizes two principal arrays in addition to that describing the graph. The first is a one-dimensional array, P, containing the vertices of an elementary path. The second is a two-dimensional array, H, and is initially zeroed. Elementary path building in P is the basic process of EC. The first path is started as vertex 1. A path is extended from its end, one arc at a time, with three conditions
  checked before a tentative extension is performed:

  The extension vertex cannot be in P.
  The extension vertex value must be larger than that of
  the first vertex of P.
  The extension vertex cannot be  closed  to the last vertex in P. H contains the list of vertices closed to each vertex.

What does Tiernan mean by point 3? I've tried googling the term "closed to [some vertex]", but the results were not entirely helpful.


texts: The role of depth of a circuit in its hardware implementation

texts:
The depth of a circuit is the maximal length of a path from an input gate to the output gate of the circuit [Reference]

Question: What is the relation between the depth of a circuit and hardware implementation of the circuit. In fact, I want to ask this question, why the low depth of a circuit  results in the circuit has a suitable  hardware implementation?

Thanks for all suggestions


texts: Which of the common sorting algorithms can be parallelized?

texts:
I want to know that whether which of the following algorithm can be parallelized?

Bubble Sort,
Insertion Sort,
Selection Sort,
Shell Sort,
Quick Sort,
Merge Sort,
Radix Sort.

Those which can't be, please explain me briefly that how? Or please try to tell me in simple words that what is parallelism in sorting algorithms.


texts:
Dancing Links: wikipedia article, research paper is an implementation of algorithm X for exact cover problem.

In the Knuth's research papaer, linked above it is shown how Polymino problem (that is covering a given shape with given sets of Polymino) is translated to exact cover problem, so that dancing links can be used to solve it.

Exact Cover problem goes like this:

  Given a matrix of 0s and 1s, find a subset of rows with exactly one 1 in each column.

For example the matrix

is solved by choosing rows 1, 4 and 5.

Knuth explains in the paper, how the Polymino problem can be translated into exact cover problem on example of the famous case of Polymino problem where we are trying to cover chess board (8x8) with 12 pentominoes. The 12 pentominoes occupy 60 squares in total, so 4 spaces on the 64 squares chessboard are left unaccounted.

Here is Knuth's explanation, of how the problems are translated into each other:

  Imagine a matrix that has 72 columns, one for each of the 12 pentominoes and one for each of the 60 cells of the chessboard-minus-its-center. Construct all possible rows representing a way to place a pentomino on the board; each row contains a 1 in the column identifying the piece, and five 1s in the columns identifying its positions. (There are exactly 1568 such rows.)

If this is not very clear please refer to the original paper for further details.

This makes sense. Latter in the paper Knuth uses a 2x2 tetromino to account for the 4 squares mentioned earlier. This also makes sense.

Now imagine that you have a different shape of the board. This is easy. You still translate each square into a matrix column as explained above.

What I'm having problems though is when I need to find solution for "inexact" cover, or cover with gaps.

In the chessboard problem above, imagine, that you do not want to settle for nicely defined 2x2 tetromino in the centre, like Knuth does. Instead you want to find all solutions no matter where the four "missing" squares go onto the board.

My initial idea was model this with 4 separate "monomino" one square each. Unfortunately this does not work so well. There are over 6 millions combinations of how 4 squares can be selected from 64 square keyboard.

If we assume that for a particular solution the monominoes occupy square A, B, C and D, then there are 4! of indentical solutions that the algorithm need to wade through, where monomino 1 goes to square A, monomino 2 goes to square B, etc or monomino 1, goes to square B , monomino 2 goes to square A, etc and all other possible combinations of fitting these 4 pieces into these 4 squares.

If we have a problem when we have more than 4 gaps, this becomes even worse. We are getting more and more identical solutions where only placement of monomino order is different, and the squares they occupy are the same.

This makes the algorithm orders of magnitudes slower, since in needs to enumerate all these identical solutions.

I cannot figure out how to efficiently model the problem of covering a shape with polymino pieces when there are many gaps as explained above.

Are there better ways to model it?


texts: Can we prove that a time machine is impossible using the Halting Problem?

texts:
Let us take a hypothetical machine i which halts on the ith day of the month if it rains on the ith day of the month. Basically it describes the present.

If we put this machine in a Halting Machine it should say whether the machine would halt. i.e. whether it would rain on the ith day of the month.

Since the Halting Machine is not possible, a time machine is not possible.

Is there any fault in my reasoning?


texts: What does it mean the norm symbol applied to a concept?

texts:
I'm reading this paper:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.150.14
or
http://www.jmlr.org/papers/volume10/kontorovich09a/kontorovich09a.pdf

On page 1101 are introduced 2 functions without a precise definition.
It is said that they are functions of the type
$\textrm{f}:\mathbb{A}  \rightarrow \mathbb{N}$
where $\mathbb{A}$  is a set.
For example $\mathbb{A}$ can be a concept or an instance. For regular languages an instance can be a string on the alphabet and the concept a specific DFA (between all DFA on that alphabet) (alternately the concept can be defined as a subset of the set of sets made of all subsets on all the possible instances (namely a subset of $2^X$ where $X$ is the instance space namely all the possible instances). The instances on the subset are the $accepted$ instances, the others are $rejected$ ).

(http://openscholarship.wustl.edu/cgi/viewcontent.cgi?article=1655&context=cse_research   for precise definitions of instance and concept, look at definitions)

The 2 functions are : $\vert \bullet \vert$ that works on a instance (for example a string). Does mean this function? Can be the length of that instance?

The other function is : $\lVert \bullet \rVert$ and works on a concept (namely yours input is a concept). But I'm not able to imagine what this function means in this context and in the paper isn't explicated.


texts: Reducing Kleene's predecessor for Church numerals

texts:
I am trying to "reinvent" Kleene's predecessor myself. The following code snippet should be self-explanatory. The idea is to make a 2-tuple and count up from zero, i.e. lambda f: lambda x: x, as described in this article:

#!/usr/bin/env python3

NULL = lambda x: x
ZERO = lambda f: lambda x: x

TRUE = lambda T: lambda F: T(NULL)
FALSE = lambda T: lambda F: F(NULL)
IF_ELSE = lambda cond: lambda T: lambda F: cond(T)(F)
IS_ZERO = lambda n: n(lambda _: FALSE)(TRUE)

ADD1 = lambda n: lambda f: lambda x: f(n(f)(x))

MakePair = lambda first: lambda second: lambda cond: IF_ELSE(cond)(lambda x: first)(lambda x: second)
First = lambda pair: pair(TRUE)
Second = lambda pair: pair(FALSE)
Trans = lambda pair: lambda cond: IF_ELSE(cond)(lambda x: Second(pair))(lambda x: ADD1(Second(pair)))
SUB1 = lambda n: First(n(Trans)(MakePair(ZERO)(ZERO)))

THREE = ADD1(ADD1(ADD1(ZERO)))
FIVE = ADD1(ADD1(ADD1(ADD1(ADD1(ZERO)))))

if __name__ == '__main__':
    print(SUB1(THREE)(lambda x: x + 1)(0))
    print(SUB1(FIVE)(lambda x: x + 1)(0))

In the end, the linked article notes that

  It is then straightforward but tedious to expand all of the short-hand expressions above, and reduce the resulting expression to normal form. This results in the standard magical encoding of predecessor.

I assume the normal form of Kleene's predecessor looks like this:

pred = lambda n: lambda f: lambda x: n (lambda g: lambda h: h (g (f))) (lambda y: x) (lambda x: x)

However, after applying a series of expansion and $\beta$-reduction, I ended up with this:

SUB1 = lambda n: n(lambda pair: lambda cond: cond(lambda x: pair(lambda T: lambda F: F(NULL)))(lambda x: lambda f: lambda x: f((pair(lambda T: lambda F: F(NULL)))(f)(x))))(lambda _: lambda f: lambda x: x)(lambda T: lambda F: T(lambda x: x))

Question:

How do I reduce my SUB1 function to pred? I don't think we can go further with only $\beta$-reduction, and there must be some advanced reduction techniques unknown to me.

A step-by-step solution would be greatly appreciated. Note that this is not a homework problem though; I am doing the exercise just for fun.


texts: What is the quickest way to allocate a set of points to a fixed number groups based on Euclidean distances from a point in each group?

texts: Example, if i have certain geographic points in an array A=[a,b,c,d...n] and have 10 points distributed in the solution space B= [1,2,3...10], how can I allocate each member of A to the nearest point in B in the quickest way.