texts:
I'm writing some notes about functional programming, so I'd want to describe some features of the category theory.

I visited wiki page about Category of Set, and I found this:

"The epimorphisms in Set are the surjective maps, the monomorphisms are the injective maps, and the isomorphisms are the bijective maps".

I'd want to explain Category theory it in term of computer science, so my question is:

It's correct to consider only the category of Set?
It's correct to consider only the category of Set when I explain functional
programming in term of Monoid/Functor/Algebraic Data/Product type and so
on?

I know that Category theory is not only Set, but It's important for me define a boundary where all my examples are correct on assumptions and definitions.

thanks
Mike.


texts: Is $L = \{ a^ib^j : 0 < j < i < 2j\}$ context free? How can it be shown?

texts:
Is $L = \{ a^ib^j : 0 < j < i < 2j\}$ context free?
If so, can there be a pushdown automaton described for it?
If not, does the pumping lemma apply?


texts: Are registers stack, per core or per application based?

texts:
I am doing a study on I found on youtube called OpenSecurityTraining: Introductory Intel x86. From what I understand there are registers like EAX, ECD, EDX, ect... and each have a purpose and hold/move information in memory.

Are these registers per stack/application? Meaning, each application will have it's own EAX, EDX, ect... that it uses to hold or move data in and out of memory?


texts: Results on the difficulty of specific random 3-SAT problems?

texts:
This is a companion question to Results on number of solutions to random 3-SAT?

Let $A$ and $B$ be two problems drawn from random 3-SAT, both with the same number of variables and clauses.  If $A$ has fewer satisfying assignments than $B$, do SAT solvers perform worse when trying to solve $A$ vs. $B$?    Are there any results on this?  (I'm a physicist by training, so a follow-up would be: is this even an interesting CS problem?)

EDIT:
I wrote a quick little DPLL-based program to calculate the number of satisfying assignments for $\alpha = 4$ and $N = 80$.  Here are the # of solutions and time to complete for a few random runs to illustrate the phenomenon that I'm looking for insight into:

368 solutions, 2.2 s
192 solutions, 8.4 s
UNSAT, 3.2 s
50492 solutions, 2.6 s
1212 solutions, 13.9 s

As illustrated above, both the number of solutions and the time to run can fluctuate significantly; is there any relationship between the two?


texts: Standard or Top Text on Applied Graph Theory

texts: I am looking for a reference text on applied graph theory and graph algorithms.  Is there a standard text used in most computer science programs?  If not, what are the most respected texts in the field? I have Cormen et al.


texts: An infinite subsequence of random numbers in Kolmogorov sense

texts:
Is it possible to construct an infinite increasing sequence of random naturals (in Kolmogorov sense) that is a subsequence of another sequence? Ok, in general I suppose not, e.g. for prime numbers. But:

I want to prove that sequence $\{ax+b\}_{x\in\mathbb{N}}$ contains an infinite subsequence of random numbers. (This is, more-or-less, a statement in an exercise).

EDIT: The actual statement is to show that $\limsup\limits_{x\to\infty}\frac{C_U(ax+b)}{\log (ax+b)}=1$.

I believe the existance of infinitely many random numbers in general, stems from the fact that for a given $k$ we have $|\{x\in\{0,1\}^k: C_U(x)< k\}|< 2^k$ because there are less binary strings of length $\leq k-1$ which may represent input to $U$. So no matter how large a binary representation, we can always find a random number with such a representation (in terms of its length). So, assuming longer $x$ means larger number it represents, we have infinitely many random numbers.

But what about here? We'd want those numbers to be of very specific form. Is there a way to do that? Could you give me a hint?


texts:
I am unable to find a clear definition of term "size of the instance" when considering some algorithmic problem. I came accross a definition that said, that "Size of the instance corresponds to the size of the input array of numbers (in case the input is numeric) or size of the representation of the input."

Is the size of the instance simply size of the input? Or is it size of all the structures used in the algorithm (in that case, it would be the space complexity, right?).

Lets explain it on a specific problem:

a) I have an array of n numbers and I have to sort them in non-decreasing order.

So the size of the instance is n (those n numbers I have to sort - using for example BubbleSort). Is the size different for some other sort that uses some additional arrays during the sorting process?

b) Find strong components of a graph with n vertices and m edges.

Is it simply n+m? Or n+2m (if I represent edges by 2*m array)? Or do I have to consider all structures used in my algorithm (in this case it would be Tarjan, I guess).

Thank you for clarification!


texts: Find an asymptotic bound for $T(n)=n^2+T(\frac{n}{2})+T(\frac{n}{4})+T(\frac{n}{8})+...+T(\frac{n}{2^k})$

texts:
Given is the following recurrence relation:

$T(n)=n^2+T(\frac{n}{2})+T(\frac{n}{4})+T(\frac{n}{8})+...+T(\frac{n}{2^k})$

where $k$ is some constant and $n = 2^t$ for some $t\in \mathbb{Z}$.

I'm trying to find an asymptotic bound for $T(n)$.

My work so far:

First, I've tried to guess and prove by induction.
Then, I tried to solve using a recursion tree, but I couldn't find any obvious pattern to follow.


texts:
The following Boolean expression is simplified into its minimal number of literals:
$$x'y' + yz +x'yz' \implies x'+yz.$$
How do you logically conclude this using the Boolean Laws?


texts: How do you prove that the set of decimal representation of the 4 divisble natural numbers is regular?

texts:
This is from an old exam, the last Task no one could solve correctly and I'm curious how it's done :p

Show that the set of decimal representation (without leading zeroes) of the divisible numbers by 4 (natural numbers) is regular.

By this thread How to prove a language is regular? I know that one can make a DFA to Show that a language is regular.

But is that possible at all because we have infinite natural numbers that are divisible by 4..

I cannot even imagine how that DFA would look like :o

Maybe there is another way of showing this, too?

Edit: Removed..


texts: Symbolic formalization of a rooted directed subgraph

texts:
In a directed graph $G(V, E)$; how can I define in symbols the set of subgraphs $G'=(V',E')$ of $G$ such that $G'$ has a root vertex, i.e., a vertex that sends a directed path in $G'$ to every $v\in V'$.

So far, I have the following.  I need to say that

$$\forall v \in V'\, \exists \text{ a directed path $P$ from $r$ to $v$, with all edges in $E'$}\,.$$

This directed path P can be thought as a sequence $(e_1, ..., e_n)$ , where each $e_i$ $\in E'$ and root r is P source. But now I don't know how to continue.


texts: What is the name of this logistic variant of TSP?

texts:
I have a logistic problem that can be seen as a variant of $\text{TSP}$. It is so natural, I'm sure it has been studied in Operations research or something similar. Here's one way of looking at the problem.

I have $P$ warehouses on the Cartesian plane. There's a path from a warehouse to every other warehouse and the distance metric used is the Euclidean distance. In addition, there are $n$ different items. Each item $1 \leq i \leq n$ can be present in any number of warehouses. We have a collector and we are given a starting point $s$ for it, say the origin $(0,0)$. The collector is given an order, so a list of items. Here, we can assume that the list only contains distinct items and only one of each. We must determine the shortest tour starting at $s$ visiting some number of warehouses so that the we pick up every item on the order.

Here's a visualization of a randomly generated instance with $P = 35$. Warehouses are represented with circles. Red ones contain item $1$, blue ones item $2$ and green ones item $3$. Given some starting point $s$ and the order ($1,2,3$), we must pick one red, one blue and one green warehouse so the order can be completed. By accident, there are no multi-colored warehouses in this example so they all contain exactly one item. This particular instance is a case of set-TSP.

I can show that the problem is indeed $\mathcal{NP}$-hard. Consider an instance where each item $i$ is located in a different warehouse $P_i$. The order is such that it contains every item. Now we must visit every warehouse $P_i$ and find the shortest tour doing so. This is equivalent of solving an instance of $\text{TSP}$.

Being so obviously useful at least in the context of logistic, routing and planning, I'm sure this has been studied before. I have two questions:

What is the name of the problem?
How well can one hope to approximate the problem (assuming $\mathcal{P} \neq \mathcal{NP}$)?

I'm quite happy with the name and/or reference(s) to the problem. Maybe the answer to the second point follows easily or I can find out that myself.


texts: Algorithm for detecting a finite limit of time-series numbers

texts:
Is there a well known and proven algorithm to find the TOP (finite) limit of a set of points, which are time based metrics? I'm looking for an existing implementation, in order not to invent the wheel of something which already exists.

This is what I have in mind, but it is a bit hard to configure the right parameters, and requires iterations:

Run over the numeric values of a series

Calculate L which is the top limit, and E (E is configurable), where 2*E is the convergent stripe around L.

Most points, P percentage, except of anomalies/noise, are below the top line of L+E (P is configurable, ranging somewhere at 95-99% range).
A Linear line around the last X points (Linear Regression) has a minor slope of +/-S (X and S are configurable)

The algo uses a stored state of a previous maximum limit - max-L.

In case L which was calculated in (a) is lower than max-L, it is considered a local max which is discarded
If L is greater than max-L then it is considered a new max limit and stored as the new max-L

The question is do you know of an existing algorithm to fulfil this, or add any suggestions to the algorithm I created. Thanks!

NOTE:
Just to be clear, as an input I have a set of data points, each with a real value and a timestamp. There is no function input, just those points. This mean, that the algorithm might detect a limit, which when inspecting all the historical data points would look like a true maximum limit, but then later in time new data points would be higher and yield a new higher limit. meaning that the algorithm I'm looking for would only find "local" limits.


texts: Time efficient way to implement Multi-Armed-Bandits?

texts:
I'm doing a research on Multi-Armed Bandit (MAB) problem with approx. 1 million arms. In contrast, the number of iterations is of course much larger, about 10-20 million.

Most MAB-algorithms require an argmax operator (argmax of the action space) that has to be executed in each iteration in order to select the current arm (which maximizes a given selection criterion). Regardless of the chosen programming language for implementation, this procedure/ this argmax operator over the entire action space (1 million arms) is very time-consuming.

Does anyone have some ideas on how to implement MAB algorithms in a time-efficient way?


texts: Classes of NFAs which allow efficient subset testing or unambiguity conversions

texts:
I'm doing some research regarding NFAs and inclusion problems with them. I know that in general, the inclusion problems, and converting to an unambiguous NFA, are both PSPACE-complete.

I'm wondering, are there any sub-classes of NFA for which these can be decided efficiently? In particular, the NFAs I'm looking at accept finite language where all words have the same Parikh vector.


texts: Turn biased random number generator into uniform

texts:
I'm looking at a problem in the book Introduction to Algorithms by Cormen et al. It says that if we are given a random number generator rand() which satisfies the distribution:

$P(X = 0) = p,\;\;P(X=1)=1-p,\;\;0<p<1$,

then we can use rand() as a subroutine to create a unbiased sampler from the set {0,1}. My idea for this is along the following lines:

Choose some fairly large even integer n.
Create a table "t" containing two integers.
Loop over $i=1,\ldots,n$ sampling $x=rand()$ for each $i$. When $i$ is even increment $t[i]$ and when odd increment $t[1-i]$.
Return $0$ if $t[0]\geq t[1]$ and vice versa.

Now the expected value for $t[0]=t[1]=n/2$, so this should give a value very close to the uniform distribution. The only problem is that the set of outcomes in (4) is biased towards $0$, so for any fixed $n$, we do not get a uniform distribution, although we do get it in the limit. There has to be a way to get $n$ to depend on some random value to balance it out, but I can't figure out how.

Anyone have any other ideas how to approach this? The key in the problem was that we do not know $p$.


texts: What's the running time for the following clique algorithm?

texts:
I sometimes like to puzzle over some NP-complete algorithms (I know how microscopic the chances are to find something new but I find it relaxing) and came up with something that I don't really know how to quantify. My idea is for the clique decision problem. Basically it's made into an adjacency matrix and from the beginning, every combination is checked as far as necessary. So from the first row (A) you check if it has (k-1) connections, then go to the first connected vertex (B), then check if it has at least (k-2) vertices in common with A, go to the first one they have in common (C) and check if they have (k-3) in common et cetera. As soon as they don't have enough in common you can eliminate that vertex from the row before and check the next one. Because you eliminate combinations as soon as they have less adjacent edges in common than necessary, you don't need to check every possible combination to eliminate them. Furthermore you never need to move more than k rows vertically or (n-k) rows horizontally and with each row you get less vertices to check.
I have an example for a graph and the combinations it's have to check here: https://www.dropbox.com/s/bctrdd7fjo8abwv/Bildschirmfoto%202020-06-20%20um%2019.20.58.png?dl=0
As you can see, it's only 12 combinations that need to be checked instead of all 252 possible ones (for n=10 and k=5 -> Does the 10-vertex graph have a 5-clique?).
I hope someone can help me by telling me what the worst-case running time would be. Also I read the fastest (known) clique algorithm is the Bron-Kerbosch-Algorithm, and I'm not sure if the one I made up is more or less the same as that one. I know it's probably a dumb question but still thanks in advance for helping.


texts:
I recently learnt about Quine-McCluskey and Petrick's methods and they are all okay by me using minterms the procedure is as follows :

1- Reduce the prime implicant chart by eliminating the essential prime implicant rows and the corresponding columns.

2- Label the rows of the reduced prime implicant chart $P0,P1,P2,...Pn$

3- Form a logical function $P$ which is true when all the columns are covered. P consists of a product of sums where each sum term has the form $P_{i_0}+P_{i_1}+...+P_{i_n}$ where each $P_{i_j}$ represents a row covering column $i$

4- Reduce $P$ to a minimum sum of products by multiplying out and applying $X+XY=X$

5- Each term in the result represents a solution, that is, a set of rows which covers all of the minterms in the table. To determine the minimum solutions, first find those terms which contain a minimum number of prime implicants.

6- Next, for each of the terms found in step five, count the number of literals in each prime implicant and find the total number of literals.

7- Choose the term or terms composed of the minimum total number of literals, and write out the corresponding sums of prime implicants.

I have a problem I want to apply this same method but with essential prime implicants as Maxterms (POS expressions)
I really need someone to indicate the difference that will occur in each step

Thanks


texts: What is fastest algorithm for factoring out square from number

texts:
I have $n$-digit integer $N=a^2b$, $b$ is square-free. In other words, $a$ is maximal square which divides $N$.

What is fastest known algorithm to find $a$? I can write algorithm of $O(n^2\sqrt{N})$ simply trying all squares that are smaller than $N$ and checking for divisibility.

Is this problem as hard as factoring integer?


texts: Is Huffman encoding for the entire language or the body of text?

texts:
I am using language as a placeholder although I think it can be used in music too. I am unclear if the frequencies are given based on the text or the entire language. The latter would prove to be difficult because if we are to say that 'e' is the most common letter in English, wouldn't this shift over time with some new words being created and some being dropped due to fashion etc?
Say we are trying to encode the first book of Harry Potter, is the encoding basing the frequency of letters of the book only or of the English language at the time? Extending it to music, would the entire domain be all possible sounds the human ear can hear or only of the track being listened to.


texts: Identifying useless vertices in a directed graph

texts:
I have a randomly generated directed graph with 3 types of vertices: input, output, and the rest (I'll call them hidden).

A useless vertex is a hidden vertex which:

can't be reached from an input vertex, OR
can't reach an output vertex.

For example:

input = yellow/green
output = blue
hidden = white
useless = red border

Note that:

cycles and self-loops are allowed
the graph may be disjoint
inputs and output nodes are known (i.e. you can determine what type of node an edge connects to and from)

So what do you call this type of problem? Is there any algorithm for this?

I'm looking for more information about this. I have a python script which seems to work. I'm just not sure if it will work for all cases since I don't fully understand it myself. It was a mix of DFS, trial-and-error, manual hand-checking, and a bunch of if statements.


texts:
We know that the "subset product problem" is NP-complete, as Gary and Johnson mentioned in their book, and the proof is by reduction from X3C.

I wonder if we can prove that this problem, i.e., the subset product problem is NP-complete even where all the given numbers are distinct powers of 2?

It seems to me it has to be NP-complete, but I have challenge with this, as in any reduction- if there is any- we need to create 2 to the power of the numbers that we are given which is not obtained in polynomial time. Does anybody have any idea?


texts: Does precedence matter in constructing parse trees of arithmetic expressions for postfix notation?

texts:
Table 4 in Problem Solving with Algorithms and Data Structures's
 chapter on Infix, Prefix and Postfix Expressions gives the following examples:

Infix Expression: A + B * C + D
Prefix Expression: + + A * B C D
Postfix Expression: A B C * + D +

Why is prefix not:

+ A + * B C D

To show my reason for this question, I'll use lowercase characters combined to represent a completed operation (e.g. + A B becomes ab). Here's my thinking:

+ A + * B C D
+ A + bc D
+ A bcd
abcd

Here's my thinking applied to the answer supplied by the text:

+ + A * B C D
+ + A bc D
+ abc D
abcd

They both work?

I'm making the same mistake with

Infix Expression: A + B + C + D
Prefix Expression: + + + A B C D
Postfix Expression: A B + C + D +

I write postfix as:

A B C D + + +

...which is wrong (but I don't know why).


texts: Fitness functions for low-dimensional parts of cooperative coevolution algorithms

texts:
In cooperative coevolution algorithms, a high dimensional vector is broken into smaller vectors, each of which is optimized separately using EAs for fewer dimensions and then recombined.

What is the fitness function used to optimize those?
It can't be the same benchmark function, as those are for higher dimensions.

I am specifically talking with respect to the algorithm DECC-G ("Large Scale Evolutionary Optimization Using Cooperative Coevolution" by Z. Yang, K. Tang, X. Yao). What is the fitness function used to optimize subpop in SaNSDE and wpop in DE?


texts: Proving $L = \{ w : w \neq w^R \}$ over $\Sigma = \{0,1\}$ is CFL

texts:
I'm trying to prove $L = \{ w : w \neq w^R \}$ over $\Sigma = \{0,1\}$ is CFL.

Define $G = ({S,T}, \Sigma, R, S)$ where $R = S \to 0S0|1S1|0T1|1T0, \; T \to 0T|1T|\varepsilon$.
Now I want to show that $\mathcal{L}(G) = L$.
One direction is fine, where given $w\in \mathcal{L}(G)$, it must've deduced using $S \to 1T0|0T1$, and therefore $w \neq w^R$.

But given $w \in L$, all I know is $w \neq w^R$. How can I prove $w\in \mathcal{L}(G)$?


texts: Travelling Salesman Problem with unknown shortest paths between nodes

texts:
I have a Travelling Salesman Problem, where I want to retrieve the "shortest" (approximate solution) circuit including the nodes n_1..n_n in a graph. The graph, however, includes a second set of nodes, say, o_1..o_n, which CAN but do not NEED to be included in the route (see picture).

i.e., this means, in the graph, I do not know the shortest paths between the nodes n_1..n_n which I want to travel.

Is there a more elegant way to retriev a relativley optimal solution than transforming the original graph into a graph only including the nodes n_1..n_n (e.g. by solving the shortest path problem for each pair of nodes [n_i|n_j]) and then using e.g. an evolutional algorithm to get a solution for the TSP?


texts: What is the most recent comparison of signature files and inverted indices?

texts:
Modern papers on search indices often contain a statement that inverted indexes (posting lists) are categorically superior to signature files (bloom filters). Here are some examples from papers published in 2016:

While this [signature file] technique provides a relatively low computation overhead, studies by Zobel et al. [1998] have shown that inverted files significantly outperform signature files.
Inverted indexes have been benchmarked as the most generalisable, and well performing structure (Zobel et al., 1998)

Every paper seems to cite Zobel et al., Inverted files versus signature files for text indexing.
However, if I'm reading Zobel et al. correctly, the argument they make isn't fundamental (e.g., an asymptotic bound or an information theoretic limit). Rather, the argument seems to be, given signature files implemented with techniques X, Y, and Z compared to inverted indices implemented with techniques A, B, and C, and the current technology of the day (disks with very high seek/access overhead), inverted indices are superior because they require fewer seeks and there are faster.
Is there a more recent comparison that compares these techniques on SSD, NVMe, or RAM, or is there a more recent comparison that looks at "new" techniques that have been invented since 1998?


texts: Randomized algorithm for 2kCNF satisfiability problem

texts:
The problem: Let a formula in $\varphi\in 2kCNF$ where there's an assignment $\alpha$ such that for every clause, $l$ in $\varphi$, $\alpha$ satisfies at least $k$ literals of $l$. Suggest a randomized algorithm for finding a satisfying assignment for such $\varphi$.

So basically I've read about the $WALKSAT$ algoritm which starts with some random assignment, $\alpha_1$ and for every iteration chooses randomly an unsatisfied clause, $l$ of $\varphi(\alpha)$ and a literal of $l$. Then, it flips this literal in $\alpha_1$, getting a new assignment, $\alpha_2$.

We repeat this process within a time bound $t$ or until a satisfying assignment has been found.

I've understood that this algorithm could be suitable here. I need to show that there's a probability of $\frac{1}{2}$ finding a satisfying assignment (probably after amplification)

I think we should look at the hamming distance of $\alpha, \alpha^t$ where $\alpha$ is the assignment as described in the question and $\alpha^t$ is unsatisfying assignment after $t$ iterations.

I'd be glad if you could guide from this point.

Thanks!


texts:
I have read from the following references about Distribution Sort:
https://users.cs.duke.edu/~reif/courses/alglectures/vitter.papers/Vit.IO_survey.pdf (5.1. Sorting by Distribution)
https://en.wikipedia.org/wiki/External_sorting#cite_note-Aggarwal88-6 (Part for External Distributtion sort)
https://en.wikipedia.org/wiki/Cache-oblivious_distribution_sort
and i can't understand
1)What affects the number of split elements in Distribution Sort?
2) What would be the ideal value of count in relation to the number of D disks? (In an external memory model). Why it is sqrt(D), D = number of Disks ; How it calculated ?


texts: The following time complexity is right for the given algorirthm

texts:
Calculate the complexity of the algorithm as follows O (n ^ 2) Would it be correct?
int Smming(int n) {
      int i, j, sum = 0;
      for (i=n; i>0; i=i-1 {
          for (j=1; j<n; j*=2){
               sum+=i+2*j;
           }
       }
       return sum;
    }

And in the code below I calculated it to be O (n^2), would it be correct?
void B (int* vet, int n)
{
 int i, j, pos;
 for (i=0; i<n-1; i++)
 {
    pos = i;
    for (j=i+1; j < n; j++)
       if (vet[pos] > vet[j])
           pos = j;
       if (pos != i) {
           int tmp = vet[pos];
           vet[pos]=vet[i];
           vet[i] = tmp;
          }
   }
}


texts: What happens if you run Kosaraju’s algorithm on a DAG?

texts: What happens if you run Kosaraju’s algorithm for finding strongly connected components of directed graphs on a DAG?


texts:
Is object oriented programming considered to be a declarative programming approach?
On Wikipedia, it is said that OOP tries to extend the imperative programming paradigm to a somewhat declarative programming approach, but what precisely makes OOP imperative or declarative?


texts: What is the most power/energy efficient sorting algorithm?

texts: I am writing a Android phone application that needs to be very power efficient, and I would like to use the most power efficient sorting algorithm. I will implement it in C for extra power efficiency. What algorithm is the most power efficient algorithm for sorting arbitrary text strings?


texts: Church–Turing thesis and infinite Turing machines

texts:
What exactly is the definition of church turing thesis? It's really confusing.
I want to prove the following statement:

A Turing machine with infinitely many states is more powerful than a regular Turing machine, as it can accept all languages.

How does this statement not contradict the Church–Turing thesis?
I don't exactly understand the definition of the Church–Turing thesis, and how it applies in this context.


texts:
Let $\Sigma  = {1,2,3,4}$  . We say that symbol $\sigma $ bonds with
  symbol $\tau$  if $\sigma = \tau$ of $\sigma = \tau +1$ for even
  $\sigma$ and $\sigma = \tau -1$ for odd $\sigma$ . In other words  , 1
  and 2 bond  , and 3 and 4 bond (in addition to every number bonding
  with itself ) .

  The  Pattern bonding problem is defined as follows:

  INPUT :  Text $ T = t_{1}  , ..., t_{n}$  and pattern $ P = p_{1}  ,
 ..., p_{m}$ over alphabet  $\Sigma  $ .

  OUTPUT :  All locations $i$ in the text that bond with the pattern ,
  i.e  , where $t_{i+j-1}$ bonds with $p_{j}$ $j=1,...,m$ .

Can someone supply an algorithm for the pattern bonding problem (the faster the better   complexity can)  ?  , I thought about "Less then matching" .

Edit: (Answer)

Map $ (1,2) \rightarrow \alpha , (3,4)\rightarrow  \beta$ then the text and the pattern is on $\Sigma = {\alpha , \beta}$ and then we know to solve it in $O(n)$ using witness or KMP .


texts: Non-termination of types in Martin-Löf's Type:Type?

texts:
In the pre-history of dependent type theory, Per Martin Löf
introduced a calculus that is in some sense the simplest dependent
type theory and the most general form of impredicative polymorphism.
It is often referred to as Type:Type because the kind Type is
itself of type Type.  Unfortunately, it is inconsistent as a
logic. This was discovered by Girard in his famous dissertation [1],
who managed to express the Burali-Forti paradox in Type:Type.
Various people have analysed, generalised and simplified Girard's
analysis, see e.g. [2, 3]. This analysis seems to involve showing that
non-terminating terms can be typed.

I have a question about non-termination: do we get non-normalisation at
the level of types? By that I mean, is there a type $T$ such that the
reduction relation $\rightarrow$ used, explicitly or implicitly, to
define equality of types, gives rise to an infinite reduction sequence
$$
   T \rightarrow T' \rightarrow T'' \rightarrow \cdots?
$$

[1] J.-Y.. Girard, Une extension de l'interpretation fonctionelle de
Gödel a l'analyse.

[2] T. Coquand, A New Paradox in Type Theory.

[3] A. J. C. Hurkens, A Simplification of Girard's Paradox.


texts:
We've learned in class that CVAL is P-complete. CVAL is the language of all $\langle C,x\rangle$ where $C$ is a formula (a circuit which outputs $0$ or $1$) and $x$ is some input for $C$ such that $C(x) = 1$.

We've done this in the same fashion Michael Sipser does in this paper (accessed Jul 11, 2017).

The reduction itself is pretty much clear. What isn't clear to me is why we can make this reduction in $\mathcal O (\log n)$ space?

It's clear that every cell is dependent on some constant number of cells of the above row (= previous configuration). Yet, one would end up calculating recursively more and more cells, until reaching the very first configuration.

We did learn in class how to evaluate $f_2 (f_1(x))$ effectively, with $\log n$ space - You start with computing $f_2$, and when in need, you "ask" $f_1$ for some symbol. I don't see how to apply it in our case.

I'd be glad for clarificatoins


texts:
I want to prove that unique(reverse(L)) = reverse(unique(L)) where L is a List.

List has the following constructors:
[] : -> List
[e] : Element -> List
cons(e, L) : Element x List -> List

I defined unique and reverse as follows:
unique : List -> List
reverse : List -> List

unique([]) = []
unique([e]) = [e]
unique(cons(e, L)) = cons(e, unique(L)), if member(e, L) = false
unique(cons(e, L)) = unique(L), if member(e, L) = true

reverse([]) = []
reverse([e]) = [e]
reverse(cons(e, L)) = append(reverse(L), [e])

also,
member : Element x List -> {true, false}
member(e, []) = false
member(e, [a]) = (e == a) (true, if a is equal to e; false, if a isn't equal to e)
member(e, cons(a, L)) = (e == a) V member(e, L) (V is logical disjunction)

append : List x List -> List
append([], L) = L
append([e], L) = cons(e, L)
append(cons(e, L1), L2) = cons(e, append(L1, L2))

Both base cases are easy to verify.

Induction hypothesis: I assume unique(reverse(L)) = reverse(unique(L)) is true

Inductive step: I have to prove that unique(reverse(cons(e, L))) = reverse(unique(cons(e, L))) is true

I consider two cases:

member(e, L) = true, then:

unique(reverse(cons(e, L))) = unique(append(reverse(L), [e]))

reverse(unique(cons(e, L))) = reverse(unique(L)) = unique(reverse(L))

Those are obviously true, but I don't know how to formally prove it (I can explain it in words, but that's not the point).
member(e, L) = false, then:

unique(reverse(cons(e, L))) = unique(append(reverse(L, [e])))

reverse(unique(cons(e, L))) = reverse(cons(e, unique(L))) = append(reverse(unique(L)), [e]) = append(unique(reverse(L)), [e])

I'm stucked here.

unique, reverse, append and member don't have to be defined that way, but they have to do the same thing.


texts:
I was reading about binary search trees on it's Wikipedia article. I was a little confused by this image. Why is it that the right branch to the head node does not have a sub-tree? I understand why it can be valid like this but surely the "8" could branch to "13" instead, then "10" and "14" could become the descendants of "13". It seems like this would be far more balanced. So I researched around for more information about binary search tree balancing and I'm still unsure. Why is the diagram in the Wikipedia article was favored? Is my suggestion wrong?

Depth-first in-order traversal still works as I presume the same for all other traversal methods.


texts: Alter Sankoff's Algorithm to give all optimal solutions

texts:
I'm trying to find a way to alter the Sankoff's Algorithm
so it will trace back all the optimal solutions and not only one.
Is it possible?


texts: Regular languages - models of computation

texts:
As far as a I understand, a regular language is a set of words that can be run in a DFA.

$L_1 = \{ x\#y \mid x,y \in \{0,1\}^* \ \text{and} \ |x| = |y| \}$

$L_2 = \{ xy  \mid x,y \in \{0,1\}^* \ \text{and} \ |x| = |y| \}$

$L_1$ is not regular but $L_2$ is, why is that?
Is it possible to create a DFA that accepts $L_2$ (it needs to remember the length of $x$) if so, why is it impossible to do it with $L_1$?


texts:
Problem

Given a range of integers $\{a,a+1,...,b-1,b\}$, find a subset of size $k$ such that the sum is equal to $s$.

Question

This problem came from evaluating some scheduling algorithms that I am interested in optimizing for some small home grown useless embedded system I am playing with. My problem is that I do not know if this problem is NP-Complete like the K-Sum problem. I am guessing it might be but it has been a while since I have dealt with proofs pertaining to NP problems. I remember something with SAT, but looking around did not jog any memories (at least any good ones).

How might I prove it is or is not NP-Complete?


texts: How does Server know window size for TCP Header?

texts: I'm trying to understand TCP right now. In the header there is "Window Size" which to my understand is the maximum amount of data that can be sent at once. My question: How does the server know how much data it can send? If I understand it correctly, the only information the server gets from the client is the ACK number that says "Package Received". Or is there more? Do I miss something?


texts: differences between theoretical research and applied research

texts:
What would be the differences between these two branches of research? For what I know the theoretical research is the one that will not necessarily end up with an application part, but the applied research deals with experimentation.

So it would be safe to say that applied research = experimental research?

Could anybody can bring up some examples to show the difference between these two types of research in the field of Computer Science?

I have been searching for some information about these topics, but I was not able to get a definitive answer.

Thanks


texts: Comparing different implementations of genetic algorithms

texts:
I am looking up some material for my thesis in CS (development of a module to integrate a genetic algorithm in a system developed by other students).

My actual current task is to make a comparative analysis of several libraries for genetic algorithms.
After this comparison I will choose one of these libraries and an algorithm.

I want to know if you can give me any tips or best practice to perform such comparison. Which approach to the task would you recommend?


texts: In the "tall cache assumption" what does $\Omega$ represent?

texts: Within the field of cache-oblivious algorithms the ideal cache model is used for determining the cache complexity of an algorithm.  One of the assumptions of the ideal cache model is that it models a "tall cache".  This is given by the statement $Z = \Omega(L^2)$.  Where $Z$ is the size of the cache and $L$ is the size of the cache line.  What does $\Omega$ represent?


texts: Finding the number of leaves in a imbalanced recursion tree

texts:
I'm going through the MIT Online Course Videos on Intro. to Algorithms at here at around 38:00.

So we have a recursion formula

$\qquad T(n) = T(n/10) + T(9n/10) + O(n)$

If we build a recursion tree it looks like

                   T(n)                     -- Level 1       = c*n
             /               \
       T(n/10)             T(9n/10)         -- Level 2       = c*n
        /   \             /         \
 T(n/100)  T(9n/100) T(9n/100)  T(81n/100)  -- Level 3       = c*n

   /                                  \                      <= c*n
    .                                .
    .                                .
 0(1)                                 0(1)

where $c$ is a constant larger than $0$.

Shortest path from the root to the leaf is $\log_{10}(n)$.

Longest path from the root to the leaf is $\log_{10/9}(n)$

Therefore, the cost could be calculated as Cost = Cost of each level * number of levels.

With the shortest path cost, we get a lower bound of $cn\log_{10}(n)$, and with the  longest path cost an upper bound of  $cn\log_{10/9}(n)$.

And now I have to add the costs of leaf nodes, which leads to my problem. In the video it says the total number of leaves is in $\Theta(n)$. I have trouble figuring out how he got to $\Theta(n)$.

The video further says $T(n)$ is bounded by

$\qquad cn\log_{10}(n) + O(n) \leq T(n) \leq cn\log_{10/9}(n) + O(n)$

Wouldn't it make more sense to say it's

$\qquad cn\log_{10}(n) + O(n^{\log_{10}(2)}) \leq T(n) \leq cn\log_{10/9}(n) + O(n^{\log_{10/9}(2)})$

where $\Theta(n^{log_{10}(2)})$ represents the leaves on the left and $\Theta(n^{\log_{10/9}(2)})$ represents the leaves on the right.

Or is there a way to simplify these terms to $\Theta(n)$?


texts: Can a functional language be homoiconic?

texts:
According to the wikipedia page on homoiconicity:

  In a homoiconic language the primary representation of programs is also a data structure in a primitive type of the language itself.

I was wondering if the lambda calculus was homoiconic (I assume not, because applications are not data (which, for the calculus, would mean variable or abstraction?)), and if not, what it would take to make it homoiconic (wrap all applications in an abstraction with a useless variable, a la \a.b c?).

But the more important question is this: If the only primitive data type in the language is the function, is it possible to achieve homoiconicity? (Does homoiconicity even make sense if all you have are functions?) If not, then is there some formal definition of what data-properties must be present in order to achieve homoiconicity?


texts: Proof of lemma for flow in residual graph

texts:
In CLRS 3'rd edition there is a Lemma 26.2 which states that:

Let $G=(V, E)$ be a flow network, let $f$ be a flow in $G,$ and let $p$ be an augmenting path in $G_{f}$. Define a function $f_{p}\colon V \times V \rightarrow \mathbb{R}$ by
$$f_{p}(u, v)=\left\{\begin{array}{ll}c_{f}(p) & \text { if }(u, v) \text { is on } p \\ 0 & \text { otherwise }\end{array}\right.$$
Then, $f_{p}$ is a flow in $G_{f}$ with value $\left|f_{p}\right|=c_{f}(p)>0$

How would you go about proving this?
As I understand we need to check for flow conservation and capacity constraint. We know that $c_f(p)$ is the minimum of the residual capacities on path $p$ which is smaller than the capacities, hence the capacity constraint is satisfied. But how about the flow conservation constraint and proving that the flow value is in fact $c_f(p) > 0$?


texts:
I am searching for substrings that satisfy a given first order formula in a moderately sized text. The formula is made out of usual $\wedge, \neg, \exists$ and predicates Equals(x, "some string"), Before(x, y) and similar, where variables are pairs indices denoting substrings.

If the text is $n$ symbols long and the formula contains $k$ quantifiers, then the brute search is $O(n^{2k+2})$. This is quite a bit of time. I ask, is there a way to significantly improve on this?

Many ranges are 'obviously' not worth iterating over, but I don't see a good way to sufficiently restrict the search space, without enumerating all the possible substrings.


texts: Minimum number of ways to write a string

texts:
Consider the following question

There are K magical pens (numbered 1 through K). You are given strings P1,P2,…,PK (each of which consists of characters from 'a', 'b', …, 't') ; for each valid i, the i-th pen can only write letters from the string Pi

.

You want to write a word S
of length N. All the characters of S are between 'a' and 't' inclusive. This string must be written from left to right. To write it, you pick up some pen and start writing; after you've written some prefix of S, you can put down that pen, pick up another pen, continue writing S from the point where you put down the previous pen, later pick up another pen (any pen) and continue writing S with that pen, and so on until you write the whole string S
You may pick up each pen any number of times, including zero.
You have to find a way of writing the word S
such that the number of times you change the pen (put down the pen you're currently writing with and pick up another) is the smallest possible. If there are multiple solutions, you may find any one. It is guaranteed that it is possible to write S with the given pens.

I know that to represnt a pen as a number using bitset and solve it ,but how can i solve it
faster.

Link for the question https://www.codechef.com/ICPCIN19/problems/PENS


texts: Find longest path between two disjoint sub-sets of vertices $V_1, V_2 \subset V$ of a Graph

texts:
I have a homework question which I would appreciate some help with:

Let there be a DAG $G=(V,E)$ with positive weights. For every two different vertices $v_1, v_2$ we will define $D(v_1, v_2)$ to be the maximum length between $v_1$ and $v_2$ in the graph.
For every two disjoint sub-sets of vertices $V_1, V_2 \subset V$ we will define "The detour length" between them to be: $w(V_1, V_2) = max\{D(v_1, v_2) \mid v_1\in V_1, v_2 \in V_2\}$
Describe an algorithm which runs at $O(|V|\cdot |E|)$ complexity, that receives as an input $V_1, V_2 \subset V$ and calculates $w(V_1, V_2)$
(Hint: You can add vertices and edges to the graph)

OK so I realize that this is a problem which is connected to finding the longest path in a DAG. I know that I can negate all the weights inside $G$ and run Bellman-Ford to find the longest path, (It will work without issues because this is a DAG). Because Bellman-Ford runs in the wanted complexity, I think this can be solved by doing some modification to B-F, but I can't seem to figure out what I can do to solve it.
Every solution I come up with will run in a higher complexity than needed - I thought about running B-F on every vertex on $V_1$ and then calculating the max, but this isn't efficient, and also doesn't really use the hint. I also though about creating a second graph by connecting the two sub-sets but that also will run at a higher complexity because I need to run over every vertex.
Any help is appreciated, Thx!


texts: Efficient algorithm to find all distances to a specific node in a tree

texts:
I wish to calculate the number of nodes within a certain distance of a particular node in a tree such as the one below:

Let's assume I'm looking for all the distances to node 2. What would be the most efficient (in terms of time complexity) method of computing the distances? Can it be done in linear time?

For this instance the output for the above tree would be:

within one edge length distance: 4
within two edge length distance: 2
over two edge lengths away: 0

What I've done so far:

A simple brute force-ish solution would be to traverse the tree all the way to node 2 starting from all other nodes and counting the edges. I can make it a bit more efficient by storing the distances for all the nodes that are visited during each traverse and using the value if the node is visited again in a traverse that has originated from another node (for example traverses originating from nodes 1 and 3 in this graph will both result in visiting node 5). Is this the most efficient it can get?


texts: What purpose was the Von Neumann machine intended for? And what hardware limitations existed when von Neumann invented it?

texts:
Its namesake invented the Von Neumann architecture (VNA) in a specific computing environment and a specific context. In light of those two:

What kind of limitations was the VNA designed to work with?
What features in the VNA reflect that?
What kind of purpose did Von Neumann intend for the VNA?
How did the design of the VNA accomplish his purpose?


texts:
What is the fastest way to compute the inverse of the matrix, whose entries are from file $\mathbb{R}$ (set of real numbers)?

One way to calculate the inverse is using the gaussian elimination method. In this method append more columns(double the number of columns ) to the input matrix and then we try to make last row zero except the last column entry and second last and so on until we get a identity matrix and then we stop and we have a inverse of input matrix. Consider the cost of one multiplication, division  and addition is constant. Then total $O(n^2)$ many operations is needed.

Is there any algorithm which is faster than the above algorithm? Please give the algorithm or reference to the algorithm


texts:
I'm having a real hard time solving recurrences using the substitution method.

Show that: $T(n) = T(n/2) + 1$ is $O(\lg n)$

I thought this to be relatively easy:

We have to show that $T(n) \leq c \lg n$

Substitution gives me:

$\qquad
  \begin{align}
    T(n) &\leq c \lg(n/2) + 1 \\
         &= c \lg n - c \lg 2 + 1 \\
         &= c \lg n - c + 1 \\
         &\leq  c \lg n
\end{align}$

for every c.

I was under the impression this was it, but when I was looking for an answer, I came around a much more elaborate answer on the web, given  involving subtracting a constant. I don't get why that's needed, I thought I had shown what was needed.

Any help would be greatly appreciate, starting Monday I'm enrolled in an algorithms class and I don't want to get behind!

We are using the CLRS book (surprise) and though I appreciate the amount of information in it, I'd rather have some more resources. I've really enjoyed a datastructures class and I really think I can enjoy this as well, but more resources would be very much appreciated.


texts: Is this language regular or not regular {(a* union b)a } intersection {a*b*} is a regular language

texts: Is {(a* ∪ b)b } intersection {a* b* } a regular language?


texts:
CLRS book has the following algorithm for parallel for matrix vector multiplication

My problem is, can't we use a simple approach like this,

MAT-VEC-MULTIPLY-MAIN(A,x,y,n)
    for i = 2 to n
        spawn MULTIPLY-ROW(A,x,y,n,i)

    MULTIPLY-ROW(A,x,y,n,1)
    sync

MULTIPLY-ROW(A,x,y,,n,row)
    for j = 1 to n
        y[row] = y[row] + a[row]j.xj

Both approaches generate same number of threads (One thread for each row). Is there any performance difference between these two?


texts:
I have a book from my university that claims:

  There is an linear algorithm that can convert BDD to CNF in linear time, and generate CNF in linear length of the BDD size (number of nodes).

Then they wrote an exercise to find one...

Actually I tried to do so, I thought to find the paths that brings me to 0, and then translate them to clause (with the opposite value of the variables), and use Tseytin transformation to create linear length of CNF.

The problem are:

How can I find all the paths to 0? I thought about DFS but it seems to be complex task for DFS because I need the variables value (the naive algorithm is exponential)
The other problem is the variables to add, when should I create a new variable, every move? It can cause an exponential number of variables, which is not good.

So what is the correct algorithm to do that?


texts: Assuming P != NP, what is the cardinality of the set of NP-Hard languages?

texts: If P=NP, then every non-trivial language is NP-Hard, so clearly there are uncountably many NP-Hard languages. However it's less clear to me what the cardinality of this set is assuming P != NP.


texts:
If a school has an IP that's like 10.0.x.x, and a department in that school has it's own site that's an extension of the school's site, does that department's IP just change the last two numbers in the IP?
Does the school have to purchase extra domain space?
Could I have additional addresses established at my IP address, just by changing the last numbers?
Am I completely wrong with my idea of IP numbers?


texts: Why algebraic semantics of programming languages have died out and have not used today?

texts:
Algebraic semantics is one type of semantics that uses algebraic expressions for connecting the formal descriptions of initial and final states of some operation of some operation that is defined in the programming language. I can not imagine more general and more versatile semantics, but yet - it is not used in today research. Why is that?

Traditionally symbolic methods were considered quite expensive, but current mathematical software, proof assistants and other automation of the mathematics and algebraic manipulations - all that provides the automation of the algebraic semantics. But still - algebraic semantics has dropped out of favour.

Why would we need algebraic semantics or semantics of programming languages generally? Answer is simple. This year the program synthesis field started to take off in earnest https://arxiv.org/search/?query=%22program+synthesis%22&searchtype=all&source=header . Apparently - if the search for target program could be done in the semantic domain (e.g. using relational/symbolic reinforcement learning or using inductive logic programming or other neuro-symbolic technique) and if there was the translation procedure from the formal semantics to whatever programming language, then the problem of program synthesis would be solved.


texts: Is Knapsack Feasibility and Knapsack with Unit Values NP-Hard?

texts:
It is well known that the maximization problem of Knapsack if NP-hard. How about just finding a feasible solution i.e. objective is set to zero?

And also if we set the values to all one (not the weights) in the objective of the Knapsack problem is it still NP-hard i.e. $\max v^Tx$ where $v=(1,1,1..,1)$?


texts: Why does the ouput of an NC0 circuit depend on only a constant number of input bits?

texts: I understand that NC0 circuits have a constant depth and bounded gate fan-in of two, but I'm struggling how to understand why the language is in NC0 iff there is a constant c such that for every n, there is a set c variables that determine it's membership.


texts:
This is something I couldn't find - but I always found it interesting that the pumping lemma is just a lemma (especially since it has the same name for regular languages, context free languages, etc...)

What is it a lemma to?


texts: find the minimum number of vertices in a directed graph from which the other vertices are reachable

texts:
In a directed graph i want to call bfs on some of the vertices so that all of the vertices will be met.

(in other words all of the other vertices are reachable from these chosen vertices.)

I want to find the minimum number of such vertices.

Actually this problem arises in social networks when we want to find the minimum number of people to which if we send a message then all of the network members will get that.(suppose that we know when someone gets the message he/she will send that to all of his/her followers.)

Can anyone help?


texts: Don't understand one step for AVL tree height log n proof

texts:
I came across a proof that the an AVL tree has O(log n) height and there's one step which I do not understand.

Let $N_h$ represent minimum number of nodes that can form an AVL tree of height h. Since we're looking for minimum number of nodes, let its children's minimum number of nodes be $N_{h-1}$ and $N_{h-2}$.

Proof:

$$N_h = N_{h-1} + N_{h-2} + 1 \tag{1}$$
$$N_{h-1} = N_{h-2} + N_{h-3} + 1 \tag{2}$$
$$ N_h = (N_{h-2} + N_{h-3} + 1 + ) + N_{h-2} + 1 \tag{3}$$
$$ N_h > 2N_{h-2} \tag{4}$$
$$N_h > 2^{h/2} \tag{5} $$

I do not understand how we went from (4) to (5). If anyone could explain, that'd be great. Thanks!


texts:
I was wondering what factors effect a machine's epsilon value. I was thinking about how modern computers can calculate expressions to higher accuracy then their predecessors, but what hardware and software factors allow for improved accuracy? Is it the implementation of better algorithms for computing various functions (examples welcome), the use of more capable hardware, or another factor I can't think of?

My go to thought is the development of better algorithms, but I can think of any that were developed post 1990.

My second thought was that the increased memory available in modern computers allows arbitrary precision arithmetic to produce more accurate results, however not all applications run with arbitrary precision and you can still run into a software "bottle neck" on the outputted precision.

What factors have the greatest effect on machine precision?


texts:
I have been searching for matching algorithms similar to the Gale Shapley, or stable marriage algorithm, but with no luck.
The question is if there are other algorithms that are similar to the GS and used for the assignation of persons or items based on preferences?


texts: Counterexample for equality in Quantified Boolean Formula

texts:
I'm looking for a counterexample for the following (false) equality. It should exist.

$n$ is an odd integer.

$f(x_1, x_2 .. x_n)$ is a boolean expression in 3 CNF form with boolean variables x.

$A = \exists x_1 \forall x_2 \exists x_3 \forall x_4 ... \forall x_{n-1} \exists x_n: f(x_1..x_n)$

Note that the exists and forall are alternating and that the expression begins and ends with exist.

$B = \forall x_2 \forall x_4 \forall x_6 .. \forall x_{n-1} \exists x_1 \exists x_3 .. \exists x_n : f(x_1..x_n)$

Somehow I have a flawed proof that implies $A=B$. I'm looking for a simple counterexample, a 3 CNF formula with few variables, so I can find the flaw in my proof.


texts: An NP-hard problem reduces to its complement?

texts:
I found this statement in a true/false test section:

Could someone explain in laymans why this is a true statement?

My understanding is that if $X$ is $\mathcal{NP}$-hard, then its complement must be $\operatorname{co-\mathcal{NP}}$-hard. However, here we are assuming that a language that is $\operatorname{co-\mathcal{NP}}$-hard ($\overline X$) is reduceable to an $\mathcal{NP}$-complete language (3SAT). This is where I get lost. I think this means $\mathcal{NP}$-hard = $\mathcal{NP}$, and thus $X$ will reduce to its complement in this world.


texts:
Given a problem $X$, to show it is is $\sf NP$-complete, one usually shows a deterministic reduction from an $\sf NP$-complete problem.

If it is hard to show deterministic reduction, then one shows a randomized reduction.

What does a deterministic reduction give about the hardness of the problem that a randomized reduction does not give?
What is the consequence if there is a randomized reduction from an $\sf NP$-complete to $X$, however one can show there is no deterministic reduction from an $\sf NP$-complete problem to $X$?
If we have only randomized reduction, is $X$ still an $\sf NP$-complete problem or could it have faster algorithms?
What does it mean for problem $X$ if there is a randomized reduction from $\sf NP$-complete problems? (Does it mean $X$ is still $\sf NP$-complete?)


texts: If there is an polynomial time approximation to an NP-complete problem, is P approximately NP?

texts:
Deciding bipartite hypergraph coloring is NP-hard:

  While for bipartite graphs a 2-coloring can be found in linear time, it was shown by Lovasz [10] that the problem to decide whether a given k-uniform hypergraph is bipartite is NP-complete for all k≥3.

Bipartite hypergraphs are colorable in expected (average) polynomial time:

  The purpose of this note is to present an algorithm that colors a hyper-graph chosen uniformly at random from the family of all labeled, 3-uniform, bipartite hypergraphs on n vertices in O(n^5 * log (2n)) expected time.

Does this imply that P is approximately NP?

Source: https://www.math.uni-hamburg.de/home/schacht/abstracts/09eurocomb.pdf


texts: The stable marriage algorithm with asymmetric arrays

texts:
I have a question about the stable marriage algorithm, for what I know it can only be used when I have arrays with the same number of elements for building the preference and the ranking matrices.

For example if we have 10 students that should be assigned to 10 dorms, then I can build the preference and ranking matrix of this data. The question that I have is what to do in the case that I have, for example, only 5 students to assign and for example 10 dorms. Can I still apply the stable marriage algorithm?

Maybe this question is a little bit foolish, but as I said I only saw this algorithm applied to quadratic arrays.


texts:
I am trying to understand the Projection operation (linear tree homomorphism) and Cylindrification operation (inverse tree homomorphism) from the book. Linear Tree homomorphism is defined as follows:

Inverse Homomorphism is defined here as follows:

With these two concepts defined, I try to use it to understand the following operations:

Now, there arent any step by step examples of how to accomplish ith projection/ ith cylindrification in tree automata in the referenced book. I would be grateful if you could point me to other useful references for these operations. That said, there is one example for the first projection, which I am unable to parse:

 How does one come up with the new set of transitions rules, and which symbol is being projected?


texts: How to build/recognise a deadlock-free order of resources

texts:
I have been faced with a problem where three concurrent processes X, Y ,Z execute three different code segments that access and update certain shared variables. Before entering the respective code segments :

Process X executes the P operation on semaphores a,b and c;
Process Y executes the P operation on semaphores b,c and d;
Process Z executes the P operation on semaphores c,d and a.

After completing the execution of its code segment, each process invokes the V operation (i.e, signal) on its three semaphores. All semaphores are binary semaphores initialized to one.

How do I recognise a deadlock-free order of invoking the P operations by the processes ? For illustration, the given examples are the following

X: P(a)P(b)P(c) Y:P(b)P(c)P(d) Z:P(c)P(d)P(a)
X: P(b)P(a)P(c) Y:P(b)P(c)P(d) Z:P(a)P(c)P(d)
X: P(b)P(a)P(c) Y:P(c)P(b)P(d) Z:P(a)P(c)P(d)
X: P(a)P(b)P(c) Y:P(c)P(b)P(d) Z:P(c)P(d)P(a)


texts: channel capacity of a general binary channel

texts:
I have found worked examples for special cases of binary channel such as the binary symmetric channel and the Z-channel. However, I am interested in a more general type of binary channel $X \to Y$ in which I only know that $P(Y=1|X=0)=a$ and $P(Y=1|X=1)=c$, hence one hopes that $0<a<c<1$.

The mutual information is defined to be
$$
I(X,Y):=\sum_{x,y \in \{0,1\}} P(X=x \wedge Y=y)\log_2 \left ( \frac{P(X=x \wedge Y=y)}{P(X=x)P(Y=y)} \right ).
$$

Denoting $t=P(X=1)$, it follows that

$$
I(X,Y)=(1-c)(1-t) \log_2 \left ( \frac{1-a}{1-c} \right )
+ a \frac{1-c}{1-a}(1-t) \log_2 \left ( \frac{a(1-a)}{(c-a)t+a(1-c)} \right )
+ct \log_2 \left (\frac{c(1-a)}{(c-a)t + a(1-c)} \right ).
$$
The channel capacity is defined as the supremum of the mutual information over all possible distributions of $X$, that is, over all $t \in [0,1]$.

Is there, in this case, a formula for the channel capacity as a function of $a$ and $c$ ?

Thank you for your time.


texts: Problems with different complexities on directed and mixed graphs

texts:
Some computational problems have different complexity on different graph classes. For instance, 3-edge coloring is NP-complete on cubic graphs but polynomial on cubic bipartite graphs.

  What are the graph problems that have different complexities on directed and mixed graphs.

A mixed graph can have both directed and undirected edges. A perfect answer would be a survey paper of such problems.


texts: On the definition of Error-Correcting Codes

texts:
Let us start with the following well-known definition:

Definition 1. Let $C\subseteq A^n$ be a code over $A$ and let $t\in \Bbb Z^+$ be a positive integer.  We say that the code $C$ is
$\boldsymbol t$-error correcting if nearest neighbour decoding is
able to correct at most $t$ errors, assuming that if a tie occurs in
the decoding process, a decoding error is reported. That is, if
whenever $x \in C$ and $y\in A^n$ such that $\mathrm{d}(x,y)\leq t$, then $y$ is decoded to $x$
using nearest neighbour decoding.

Now let us make an observation.

Remark.  Recall that when there is no unique nearest codeword to $x\in C$, then
nearest neighbour decoding fails. So, a code $C\subseteq A^n$ is $t$-error correcting if and only if
whenever $y\in A^n$ is a word within distance $t$ of a codeword $x\in
  C$ (that is, $\mathrm{d}(x,y)\leq t$), then $$\mathrm{d}(x,y) <
  \mathrm{d}(z,y), \quad \text{for all } x\neq z \in C.$$

The Remark gives us a more abstract way to state the definition of $t$-error correcting without  mentioning nearest neighbour decoding.
However, I stumbled on another statement of the definition (which I found on some lecture notes on the web):

Definition 2. The code $C$ is $t$-error correcting if there do not exist $x,z \in C$ such that $x\neq z$ and $y\in A^n$ such that
$$\mathrm d(x, y)\leq t, \quad \mathrm d (z, y)\leq t.$$

My question is why the last definition is equivalent to the first one (given with the form of the remark).
Could you please give me a hand?

UPDATE: My attempt: Definition 1 tells us that
$$(\forall x\in C)(\forall z \in C)(\forall y\in A^n)(d(x,y)\leq t)(z\neq x \implies d(x,y)<d(z,y)).$$
Definition 2 tells us that
$$(\forall x\in C)(\forall z \in C)(\forall y\in A^n)(d(x,y)\leq t)(d(z,y)\leq t \implies z=x).$$
Equivalently,
$$(\forall x\in C)(\forall z \in C)(\forall y\in A^n)(d(x,y)\leq t)(z\neq x\implies d(z,y)>t ).$$
Equivalently,
$$(\forall x\in C)(\forall z \in C)(\forall y\in A^n)(d(x,y)\leq t)(z\neq x\implies d(z,y)>t\geq d(x,y)).$$
So the Def2 $\implies$ Def 1. Is that correct? How about $\Longleftarrow$?


texts: What could 'two characters are terminals' mean?

texts:
In the context of this statement, what does 'a & b are terminals' mean?

  Stacks and queues can be used for determining whether a particular
  input string is in the language or not.

  L = {a^nb^m | m,n >= 0, m >= n, and a & b are terminals}

  Sample strings in L : abb, aabb, aabbb

  Sample strings NOT in L : aab, ba


texts: Simple generator of pseudo-random permutations of variable length short sequence

texts:
The problem in front of me is to write a function (from scratch) to permute n elements, where n is an argument. I decided to break it down to applying Knuth's shuffles algorithm, therefore I needed to write a pseudorandom number generator.

So now my task is to write a simple function F(seed,n) that will help me generate indices for the pseudorandom permutations of n elements. However, the function has to be extremely simple: My constraint is that I can only use the following operators: +,-,*,/,%, specifically, no address access, binary encoding, bits selection etc. - only arithmetic on numbers. That is fine, I went for linear congruental generators and implemented a (a*x+c)%m procedure.

As I started testing F(seed,2) it immediately went apparent that the results oscilate between zero and one with a period of two.

My problem is: how can I adjust F to avoid that behavior? Maybe I should generate the n-permutations in a different manner?

In practice, I am only interested in n=<32


texts:
In this table B is foreign key referring to the primary key A with on delete cascade option.What will be the result after deleting (4,3) and how
A:1 4 2 9 3 5
B:3 3 4 2 9 4


texts: What roadblocks are there to HSA becoming standard, similar to floating point units becoming standard?

texts:
I remember when my dad explained to me for the first time how a certain model of computer he had came with a "math coprocessor" which made certain math operations much faster than if they were done on the main CPU without it. That feels a lot like the situation we are in with GPUs today.
If I understand correctly, when Intel introduced the x87 architecture they added instructions to x86 that would shunt the floating point operation to the x87 coprocessor if present, or run some software version of the floating operation if it wasn't. Why isn't GPU compute programming like that? As I understand it, GPU compute is explicit, you have to program for it or for the CPU. You decide as a programmer, it isn't up to the compiler and runtime like Float used to be.
Now that most consumers processors (Ryzen aside) across the board (including smartphone Arm chips and even consoles) are SoCs that include CPUs and GPUs on the same die with shared main memory, what is holding back the industry from adopting some standard form of addressing the GPU compute units built in to their SoCs, much like floating point operation support is now standard in every modern language/compiler?
In short, why can't I write something like the code below and expect a standard compiler to decide if it should compile it linearly for a CPU, with SIMD operations like AVX or NEON, or on the GPU if it is available? (Please forgive the terrible example, I'm no expert on what sort of code would normally go on a GPU matter, hence the question. Feel free to edit the example to be more obvious if you have an idea for better syntax.)
for (int i = 0; i < size; i += PLATFORM_WIDTH)
{
    // + and = are aware of PLATFORM_WIDTH and adds operand2 to PLATFORM_WIDTH
    // number of elements of operand_arr starting at index i.
    // PLATFORM_WIDTH is a number determined by the compiler or maybe
    // at runtime after determining where the code will run.
    result_arr[a] = operand_arr[i] + operand2;
}

I am aware of several ways to program for a GPU, including CUDA and OpenCL, that are aimed at working with dedicated GPUs that use memory separate from the CPU's memory. I'm not talking about that. I can imagine a few challenges with doing what I'm describing there due to the disconnected nature of that sort of GPU that require explicit programming. I'm referring solely to the SoCs with an integrated GPU like I described above.
I also understand that GPU compute is very different than your standard CPU compute (being massively parallel), but floating point calculations are also very different from integer calculations and they were integrated in to the CPU (and GPU...). It just feels natural for certain operations to be pushed to the GPU where possible, like Floats were pushed to the 'Math coprocessor' of yore.
So why hasn't it happened? Lack of standardization? Lack of wide industry interest? Or are SoCs with both CPUs and GPUs still too new and is it just a matter of time? (I am aware of the HSA foundation and their efforts. Are they just too new and haven't caught on yet?)
(To be fair, even SIMD doesn't seem to have reached the level of standard support in languages that Float has, so maybe a better question may be why SIMD in general hasn't reached that level of support yet, GPUs included.)


texts: Compile a programming language with itself

texts:
I'm a computer science student. I want to create my own programming language (A basic language with few instructions).

I know how to do a syntactic analyser, I already did it in Perl. In an article, I read something about the compiler, a compiler is done in itself.

For example the C compiler is written in C. How it's possible?
I can make my own language but I don't know how I could execute it? Any idea?

It's really a good question and I can write a blog the project.


texts: Maxima of diagonals in a column wise and row wise sorted matrix

texts:
Let $\{a_i\}$ and $\{b_i\}$ be non-decreasing sequences of non-negative integers.

How fast can one find
$$c_j=\max_{0 \leq i< j}\{a_i+b_{j-i-1}\}$$
for all $0\leq j\leq n-1$?

Naively, it takes $O(n^2)$ time, but I'm hoping monotonicity can help here.

It's easy to observe $\{c_i\}$ is also non-decreasing. If we consider the matrix $M$ where $M_{i,j} = a_i+b_j$, then it is a matrix sorted in both row and column direction, and we are searching for the maximum element in every diagonal.

However, if it's an arbitrary column wise and row wise sorted matrix, this problem require $\Omega(n^2)$ time.

Proof: Let all the numbers below the main diagonal be $\infty$. The elements in the $k$th diagonal are randomly numbers from $(k,k+1)$. Reading any entry provides no information for any other entry.

Edit: This problem is much harder than I anticipated. We can model this problem as a convolution problem over the semiring $(\min,+)$ (take the dual, search for min instead of max), and it can be solved in $O(\frac{n^2}{\log n})$ time according to a Ryan Williams's answer on mathoverflow. It doesn't use the information that the sequence is non-decreasing though.


texts: Is there an efficient algorithm for solving tiling puzzles?

texts:
As an example of the type of problem, consider Stewart Coffin's Cruiser puzzle:

  Let R be a 48 × 31 rectangle. Let T be a 30°-60°-90° triangle with
  hypotenuse 34.565 (so legs are 17.2825 and 29.934). Let P be a right
  trapezoid with base 20.0982 and altitudes 27.1178 and 15.514. Show how
  to place two copies of T and two copies of P inside R with no overlap.

Solution

The algorithm should be able to solve for any number of polygons of any shape within another polygon of any shape (or conclude that such a solution is not possible).


texts: Difference between data duplication and data redundancy

texts: My Computing teachers talk about data duplication and data redundancy in terms of databases as different things, but I'm struggling to differentiate them. The context is database normalisation, and in particular why the third normal form is important: because it eliminates data duplication and redundancy. But as far as I can see, both of these terms relate to data appearing more than once in a database. Yes, I asked my teachers, but I didn't understand the explanation and it was a group revision session that I didn't want to hold up.


texts: Polynomial reduction from unbounded knapsack problem to general integer programming

texts:
Given an oracle that can solve in polynomial time:

$$a^Tx=b$$
$$x \geq 0$$

So it can solve the feasibility problem with one equality-constraint ($a$ is here a vector and $b$ is a constant, $x$ is required to be integer) and non negativity constraint for the solution. (This problem is also known as unbounded knapsack problem)

With this oracle how can this be solved in polynomial time:
$$Ax=b$$
$$x \geq 0$$

where there are arbitrary many equality-constraints ($A$ is here a Matrix and $b$ an vector, $x$ is required to be integer) and non negativity constraint for the solution.

My thoughts:

Just finding a solution for every constraint is not enough. You need to somehow be able to find a solution which fulfills all constraints. But i don't see a way? But there has to be way, because both problems are NP-complete.


texts: Number of integers in a certain range with certain properties

texts:
How would one (quickly) find the number of integers in the range [1, x] for some x, more than half of its digits being one digit, given that $x$ has at most, say, 19 digits.

Brute force would obviously not work in a reasonable amount of time (where "reasonable" means roughly $10^9$ seconds)


texts:
i'm currently converting this NFA:

into DFA, however it's a bit confusing and my result so far ended with:

However, this doesn't seem right to me, and i would love to hear if im on the right track or not


texts:
Can somebody give intuition how to answer those questions? From one side I can say that most of them are undecidable because we can reduce the halting problem to them (or halting problem can appear because we don't know about given TM anything so it can behave unpredictably, can simply loop on any input), but on another hand in question 2. we don't know much about machine, however I can hardcore all words into my TM as far as given language is finite. Also, for question 1. I'm able to create TM which checks if the output of M is even-length (I would classify this problem as semi-decidable).

What type  of the following decision problems are: decidable, partly decidable, or even undecidable:

Does the language of the given machine M contain only even-length words?
Does the given M machine accept a finite language size of which is less than 2019?
We say that language A is prefixless if no word belonging to A is a prefix of any other word from A. For example, language A = {0, 10, 110, 1110, ...} is prefixless, while language B = {0, 1, 00, 11, 000, 111, ...} does not have this property (for example, because 0 is the prefix 00).
Consider the following language (decision problem): L = {⟨M⟩ | L (M) is prefixless}.
Is the given recursive function a surjection?
Is the given recursive function an injection?
Does the machine M stop at bb?
Does the machine M accept the empty language?


texts: Image properties given by similitude moments

texts:
What image properties are given by similitude moments? These are image moments of the form shown below:

$$\eta_{pq}=\frac{\sum_x\sum_y(x-\mu_x)^p(y-\mu_y)^qI(x,y)}{(\sum_x\sum_yI(x,y))^{\frac{p+q}{2}+1}}$$

Specifically, I'm looking for the properties given by this set of similitude moments:

[$\eta_{02}$, $\eta_{03}$, $\eta_{11}$, $\eta_{12}$, $\eta_{20}$, $\eta_{21}$, $\eta_{30}$]

I wasn't able to find many relevant results on Google. Those that mentioned similitude image moments just said how to calculate it, not what they're used for.


texts: Definition of imperative semantic in a HDL context

texts:
I've been studying from this book the topic of "Synthesis and optimization of digital circuit". In chapter 3 some theory about programming languages is exposed. I was wondering what's the meaning of this paragraph about the meaning of "imperative semantic"

  Languages with an imperative semantics are those where there is an
  underlying dependence between the assignments and the values that
  variables can take.

By surfing the web I've seen that basically these languages are "C/C++" like languages because how the program change its own state during his execution is specified by a sequence of statements in an explicit manner. However the topic of that book is basically how a circuit described using an HDL language is synthesized, and there's no "actual program there", and I can't relate how the "imperative semantic" concept provided is applied in such context. Is there a more rigorous definition of imperative semantic that applies to both context?


texts: Number of compatible trees with an ancestry matrix

texts:
Suppose you are given an ancestry matrix $M$ which means that $M[ij] = 1$ iff node $i$ is an ancestor of node $j$. If $M$ represents no cycles (treated as an adjacency matrix) the corresponding graph is a tree (or a forest). My question is what is the number of trees where their ancestry matrix is $M$.

Is this question any simpler than counting number of directed graphs which are compatible to a general ancestry matrix?


texts: Why are registers name in assembly cryptic

texts:
Why are registers named so short - EAX, EBX,...etc They could have easily made the names more
descriptive rather than encrypted like that.


texts: Find the maximum number of valid cartesian coordinates

texts:
Given a list X containing m number of x coordinates and a list Y containing m number of y coordinates. The coordinate (x, y) is valid if and only if the difference between x and y is less than or equal to d. I need to find out the maximum number of valid coordinates. Here is my algorithm.
sort the list X in non-decreasing order
sort the list Y in non-decreasing order
for x in X:
     for y in Y:
         if abs(x - y) <= d:
             let x match with y
             remove x from X
             remove y from Y

Can this algorithm give me maximum number of valid pairs? If yes, is there any more efficient algorithm? The nested loop means the worst-case time is $O(m^2)$. Is there any log linear time $O(m\log m)$ algorithm for this question?


texts: Types and Programming Languages - proof for theorem about principles of induction of terms

texts:
Types and Programming Languages book introduces a theorem about principles of induction on term (p. 31, theorem 3.3.4):

  Suppose P is a predicate on terms.

  Induction on depth:

  If, for each term s, given P (r) for all r such that depth(r) <
  depth(s)  we can show P(s), then P(s) holds for all s.

Proof of this theorem is left as the exercise for the reader. The solution to the exercise given in the book hints at defining a new predicate Q(n) on natural numbers such as:

  ∀s with depth(s) = n. P(s)

and apply the principle of complete induction on natural number (p. 19, axiom 2.4.2):

  If, for each natural number n, given P(i) for all i < n we can show P(n),
  then P(n) holds for all n.

Since I lack experience in writing mathematical proofs, I'm struggling with applying the hint from the book and proving that theorem.

Given that:

n = i + 1
for all natural numbers i less than i + 1, the predicate Q(i) holds (from the induction axiom)

How do I prove that Q(n) (or Q(i + 1)) is true? Should I use depth function definition introduced previously for the simple arithmetic language?


texts: Complete Problems for $DSPACE(\log(n)^k)$

texts:
We know that the $polyL$-hierarchy doesn't have complete problems, as it would conflict with the space hierarchy theorem. But: Are there complete problems for each level of this hierarchy?

To be precise: Does the class $DSPACE(\log(n)^k)$ have complete problems under $L$-reductions for each $k > 0$?


texts: What is the decision version of integer programming?

texts:
I don't know what is meant by "decision version of integer programming".

I know ILP, but this terminology has me confused.


texts: Calculate expected values of "Craps Game" with the help of Prism Model Checker

texts:
I have modelled the craps game (https://en.wikipedia.org/wiki/Craps#Rules_of_play) as a dtmc with the prism model checker:

dtmc

module craps

    // local state - won = 7, lost = 8
    s : [0..8] init 0;

    // first roll
    [] s=0  -> 1/12: (s'=1)  +  // point 4
        1/12: (s'=2)  +  // point 10
        1/9 : (s'=3)  +  // point 5
        1/9 : (s'=4)  +  // point 9
        5/36: (s'=5)  +  // point 6
        5/36: (s'=6)  +  // point 8
        2/9 : (s'=7)  +  // won - point 7/11
        1/9 : (s'=8);    // craps - point 2/3/12

    // further rolls
    [] s=1  ->   3/4 : (s'=1)  + 1/12 : (s'=7) + 1/6 : (s'=8);
    [] s=2  ->   3/4 : (s'=2)  + 1/12 : (s'=7) + 1/6 : (s'=8);
    [] s=3  -> 13/18 : (s'=3)  +  1/9 : (s'=7) + 1/6 : (s'=8);
    [] s=4  -> 13/18 : (s'=4)  +  1/9 : (s'=7) + 1/6 : (s'=8);
    [] s=5  -> 25/36 : (s'=5)  + 5/36 : (s'=7) + 1/6 : (s'=8);
    [] s=6  -> 25/36 : (s'=6)  + 5/36 : (s'=7) + 1/6 : (s'=8);
    [] s=7  -> (s'=7);
    [] s=8  -> (s'=8);

endmodule

rewards "dice_rolls"
    [] s<7 : 1;
endrewards

Now I need to calculate:

Creating a proper reward structure, calculate the expected number of rolls to win and to lose the game.
Creating a proper reward structure and considering a variant of the game in which at each roll of
the dice a cost of 1 is payed by the player, calculate the expected money payed to reach a state of
winning and the expected money payed to reach a state of loosing.

The reward structure "dice_rolls" should be good to calculate both the requirements, as IMHO they differ only semantically.

In the case of the expected number of rolls to win, a property like R=? [ F (s=7) ] gives as result Infinity , and the manual says "In the case where the probability of reaching a state
satisfying prop is less than 1, the reward is equal to infinity"-
http://www.prismmodelchecker.org/manual/PropertySpecification/Reward-basedProperties
which (also intuitively) seems to confirm that the model is right (otherwise the dice would be not fair as there would be chances to win with P = 1.

Are my calculations right (the requested costs are all infinite), or I need to correct the reward structure and/or the reward property?


texts: Direct edges of undirected graph so that all indegrees are even

texts:
Undirected graph is given which has M edges and N vertices we have to convert every edge from $u-v$ to $u\to v$ or $v\to u$ such that the total indegree of every vertex is even.

For example, consider a graph which has the edges 1-2, 1-3, 2-4, 3-4. We can direct it as 1→2, 1→3, 2←4, 3←4, so indegrees of 1,2,3,4 are respectively 0,2,2,0, which are all even.

Which method or algorithm is suited for least time complexity? M and N are between 1 and 100,000.


texts: Polygon decomposition into minimum star-shaped polygons

texts:
As the title suggests, I'm trying to implement an algorithm to decompose a polygon into the minimum number of star-shaped polygons. I've been searching for quite some time but I can't find any algorithms or even anything theoretical to study on this problem online. The closest I found is decomposition to the minimum number of convex polygons.

Any suggestions as to how I should approach the problem?

I've tried to think about it by myself but the combinations seem too many and I don't want to get into writing an algorithm while my main problem is still unsolved.


texts: Can a Turing machine decide the language $L_\emptyset$ of machines with empty language?

texts:
Let $$L_\emptyset = \{\langle M\rangle \mid M \text{ is a Turing Machine and }L(M)=\emptyset\}.$$
Is there a Turing machine R that decides (I don't mean recognizes) the language $L_\emptyset$?

It seems that the same technique used to show that $\{A \mid A \text{ is a DFA and } L(A)=\emptyset\}$ should work here as well.


texts: Two labelled transition systems feeding each other

texts:
Assume we have two LTSs, say DFA with labels over the transitions (though the question can be generalized to more sophisticated automatons), define the input to each system to be as usual just the input word, and define the output of each system to be the sequence of labels of visited transitions.

Now assume that the two systems are wired directly to each other: every output letter (i.e. non-epsilon transition) in system A becomes instantly an input letter to system B, and output of B becomes input of A.

I'm looking for some analysis of this construction. Maybe anyone happen to be familiar with research topic that discuss such?

EDIT: Special case - if we have labelled pushdown automatons (context free grammars), then is the combined system as powerful as a two-pushdown machine (Turing powerful)? Or is strictly weaker?


texts: Evasiveness of acyclicity of undirected graph

texts:
The lecture note by Jeff Erickson discusses "Evasive Graph Properties":

  We call a graph property evasive if we have to look at all $\binom{n}{2}$ entries in the adjacent matrix to decide whether an (undirected) graph has that property.

As an example, it shows that connectivity is evasive.

I want to know: Is acyclicity evasive? How to prove/disprove it?

My attempt: A rather straightforward adaptation I made from the proof for connectivity does not work for acyclicity.


texts: C++ STL: How does the distance() method work for a set/ multiset (stored internally as a self balancing tree)?

texts:
I'm working on the problem: Count smaller elements on right side using Set in C++ STL
The solution is to add each element to the set and then to count the elements on the left, the distance function is called.
This is the algo:
1. Traverse the array element from i=len-1 to 0 and insert every element in a set.
2. Find the first element that is lower than A[i] using lower_bound function.
3. Find the distance between above found element and the beginning of the set using distance function.
4. Store the distance in another array Lets say CountSmaller.
4. Print that array

I'm having a hard time to visualize or understand how can distance function be used with a set like structure since internally, the set data is stored as a self balanced tree (Red Black Tree). Whats the concept of distance for a self balancing tree and how does calling distance() give us the count of smaller elements on the right side?


texts: What is a Huffman tree for a Block-Code?

texts:
We have the word "w = aabceefgeebdaabbceeffghdcbbeefbbbbghhie ".

I have created a Huffman tree for the string w.

We get the following table:

Now I want to create a Huffman tree for a Block-Code with length of block $4$.

Do we maybe take each consecutive 4 letters, i.e., {aabc, eefg, eebd, aabb, ceef, fghd, cbbe, efbb, bbgh, hie} to make the tree?

But then the last one is of length 3 and not 4.

So, do we choose in an other way the blocks?


texts: Calculating makespan among several machines

texts:
I have a question about makespan calculation. I know that makespan formula is like this:

  Makespan = Time of completion of last job - Starting time of the first
  job

but I can't figure out how we should use it for several machines. I have a load balancing algorithm that helps in processing of several independent jobs on 3 homogeneous machines. A central coordinator gathers the load on each machine (lead = number of tasks on each machine) and if there is an overloaded device, the coordinator will move some of its tasks to a less-loaded machine. By the way jobs are not consisted of small tasks and all the job should be done on a single machine. I want to calculate makespan for this algorithm.

Now in order to calculate makespan, should I calculate makespan for each machine separately

or

I should do this among all machines? I mean should I find the time of earliest job arrived to these machines and also find the time of last job among 3 machines and apply the above formula to them?


texts:
Is the problem to construct a $\mathcal{O}\mbox{*}(1.4^n)$ (or better) time algorithm for subset sum still open? I wanted to check the problem before finishing a paper.

The most recent reference I found to this open problem is on next paper:

  'SETH-Based Lower Bounds for Subset Sum and Bicriteria Path, Amir
  Abboud et al.' 2017
  link

citing:

  'Open problems around exact algorithms, Woeginger' 2008
  link.


texts: What is a "closed set" in context of AI? How is it different from an open set or a frontier?

texts:
I am reading some properties on the A* search algorithm on Wikipedia, specifically:

"If the heuristic function h is admissible, meaning that it never overestimates the actual minimal cost of reaching the goal, then A* is itself admissible (or optimal) if we do not use a closed set. If a closed set is used, then h must also be monotonic (or consistent) for A* to be optimal."

But I am not sure I understand what a "closed set" refers to. Is it different than an open set / frontier? If so, why? And why do we use a "closed set" as opposed to an "open set" for A*? Is a priority queue a closed set?


texts: Do we generally store the degree of each vertex in the linked list implementation? if not, why?

texts:
So generally speaking, when we implement the graph using linked list, do we store the degree of each edge too?

I'm asking this because if a question in my exam stated that we implemented this graph using linked list, do i assume we can access the degree of each edge in o(1) or not? this matters because it effects the time complexity of algorithms like finding if the graph has euler cycle which i should check the degree of each edge

and the exams are SAT type of questions so i can't write down anything i should just choose one of the 4 answers which for example says the time complexity of finding if the graph has euler path in linked list implementation


texts: Vertex coloring with an upper bound on the degree of the nodes

texts: Consider the set of graphs in which the maximum degree of the vertices is a constant number $\Delta$ independent of the number of vertices. Is the vertex coloring problem (that is, color the vertices with minimum number of colors such that no pair of adjacent nodes have the same color) on this set still NP-hard? Why?


texts: Arithmetic code: from interval to code value

texts:
I've not clear how to pass from final interval to code value, for example:

Suppose we have the set of symbols={0,1,2,3} with probability={0.2, 0.5, 0.2 , 0.1} and that we have to encode a source S={2,1,0,0,1,3};

After the encoding process we'll have an interval $[ 0.7426, 0.7428 ) $.

Now the final step is to find the shortest representation to transmit and in the book the chosen value is 0.10111110001 = 0.74267578125.

  How is it possible to calculate the shortest representation and the code value to transmit having the final interval?


texts: I want a fast rank only shuffling algorithm for a full 52 card deck

texts:
My goal is to do some large iteration Monte Carlo simulation of different card games that require on the order of 1 billion random decks to get a reliably accurate answer.  The bulk of the computer time is actually shuffling/preparing the decks, not searching for the "hit" criteria I am looking for.

I am using an string function rich interpreted language.  I have bit functions available that work up to 32 bit at a time.  I am only interested in the ranks of the 52 card deck, not the suits.  So I am looking for a fast algorithm that will give me 4 of each of the 13 ranks for a full 52 card deck.  It doesn't matter which order the suits of a particular rank come in since we are ignoring the suits (other than we are enforcing that there only be 4 of each suit for each rank).

My first attempt was to just generate a normal deck with the ranks and suits "encoded" using cards numbered 1 thru 52 with an array of flags telling which cards were already seen.  Each random number generated, (from 1 to 52), was for determining the next card (if there was no collision).  This algorithm worked but was kinda slow, only producing about 6000 full decks per second on a 3.06 Ghz dual core computer (using only about 50% of the CPU).

My 2nd attempt was just to tweak the first attempt by only picking the first 48 cards (since the "seen" ratio is very high for the last 4 cards and likely many collisions will occur, slowing it down), then choosing a random number from 1 to 24 to handle the permutations of the last 4 "missing" cards which are known from simply scanning the flag array and finding the 4 that are marked "false" meaning they haven't been seen yet.  This was roughly 50% faster as I was able to generate about 9000 full decks per second vs. about 6000 previously.

For my 3rd attempt, I am using a 32 bit random number to place 4 or 8 cards at a time from the unshuffled deck into a built up shuffled deck.

Any help/ideas would be greatly appreciated.


texts: What does it mean for a problem to be solved in polynomial time "relative to" an oracle?

texts:
I came across the following theorem in page 12 of the following pdf :

  There exists an oracle relative to which there is a problem solvable
  in polynomial time (with bounded error probability) on a quantum
  computer, but any probabilistic Turing Machine with bounded error
  probability solving this problem (using the oracle) will require
  exponential time (at least $2^\frac{n}{2}$ steps on infinitely many
  inputs (of length n).

My question is what does it mean to say "There exists an oracle relative to which there is a problem". My take on it is that if we try to solve the problem using a non deterministic T.M. or non deterministic Quantum computer (I don't know if such a thing even makes sense as I just started studying Quantum Computing) the oracle is a black box which tells the machine which path to take in the non deterministic step. Is this the correct interpretation?


texts: How do you find a sub-digraph in a digraph such that the in degree and out degree of each vertex is 1. My professor told in the class that an algorithm can be build for it using bipartite matching but I have not able to do so. I am just looking for hints on how to proceed because I am kind of stuck on where to start.


texts: Confusion about finite automata construction in Knuth–Morris–Pratt algorithm

texts:
There is one point I don't understand in the DFA construction for mismatch cases.

Here is the lecture note I watched, which describes how to handle mismatched characters during the DFA construction process.

Some information about the presentation screen shot:

pat is the pattern, string index starts at 0, dfa is the state transition table, in which the row is indexed by the character(eg, "A","B" or "C"), column by state(1,2,3,...).

My question starts:

In the place in the presentation, where starts with "To compute dfa[c][j]", it says run the simulation using the last j-1 chars.

I am confused:

Why run the simulation using the last j-1 chars, rather the last j chars.

What's the intuition of this design?


texts: Why descriptive power of context-free grammar is greater than regular expression?

texts:
Below is a saying from this article.

  Regular expressions sit just beneath context-free grammars in descriptive power: you could rewrite any regular expression into a grammar that represents the strings matched by the expression. But, the reverse is not true: not every grammar can be converted into an equivalent regular expression.

Can anyone tell me if the saying is correct and why? Per my understanding, they should have same power and the differernce is a context-free grammar has recursive definition.


texts: Average length and entropy of a code from a probabilistic source


texts: Initializations methods for lloyds algorithm (Kmeans++ vs Gonzalez)

texts: I'm learning the initialization methods for Lloyd's algorithm. And I have a hard thing finding examples where Kmeans++ works better than Gonzalez and where the reverse is true so Gonzalez works better than Kmeans++. Does anyone have an example input (Pointset and value k) for these two scenarios?


texts: Is it Polynomial to decide whether any product of input numbers satisfies a boolean expression?

texts:
I have an input number c of n bits and its prime factorization. I want to find a divisor of c with certain fixed bits "f". For example:

INPUT:
c=1100011 (99) (n=7)
prime factorization = 11,11,1011 (3,3,11)
f=0??1?0?

OUTPUT:
o=0001001 (9)

Unfortunately, it's no use to check all divisors, because according to http://en.wikipedia.org/wiki/Divisor there may be up to O(sqrt(2^n)) divisors, which is exponential.


texts: What happens when an alphabet is not listed in a Turing Machine?

texts:
I was given a quick lesson on Turing Machines which I found interesting. However, I came up with a problem which made me think a bit on a problem and since it's not an actual class, the answer was not given. First, let me give you some background info on a Turing Machine:

A Turing machine is a quadruple (K, sigma, small delta, s), where
  K is a finite set of states, not containing the halt stage h;
  sigma is an alphabet, containing the blank symbol #, but not containing symbols L and R;
  s is in K is the initial state;
  small delta is the rate of change.

With that info in mind, I have the following problem:

Consider the Turing machine M = (K, sigma, small delta, s), where
  K = {q0,q1} //only has two states
  sigma = {a,#} //only has a and the blank symbol
  s = q0 //will start at 10

and small delta is given by the following table.
  q      small sigma      small delta(q,small sigma)
  q0      a                 (q1,#)
  q0      #                 (h,#)
  q1      a                 (q0,a)
  q1      #                 (q0,R) //move one cell of the tape to the right

With this info and the following example, we have:

a|a|#

Let's check the first cell, it's a and we are in the initial state. If it's a, change it to #.

#|a|#

We're still on the same cell, but we changed states, q1. The alphabet is #, so let's go back to the initial state and go one cell to the Right.

The next cell has an a as well, so we change it to #. Go to state q1 and check if the alphabet is blank. It is, so we go one cell to the right.

#|#|#<we're in this cell now.

Now we go to the initial state and check if the alphabet is a, it isn't so let's check if it's blank. It is, so we halt the whole thing.

We have

#|#|#

Pretty straightforward, right? Well, I have thought of one thing. What if the tape had something that was not taken into consideration?

Something like

a|b|a|#

Would the Turing machine crash or would it ignore it?

Thank you for your time.


texts: What questions can denotational semantics answer that operational semantics can't?

texts: I am familiar with operational semantics (both small-step and big-step) for defining programming languages. I'm interested in learning denotational semantics as well, but I'm not sure if it will be worth the effort. Will I just be learning the same material from a different point of view, or are there insights I can only gain from understanding denotational semantics?


texts: Computing inverse matrix when an element changes

texts: Given an $n \times n$ matrix $\mathbf{A}$. Let the inverse matrix of $\mathbf{A}$ be $\mathbf{A}^{-1}$ (that is, $\mathbf{A}\mathbf{A}^{-1} = \mathbf{I}$). Assume that one element in $\mathbf{A}$ is changed (let's say $a _{ij}$ to $a' _{ij}$). The objective is to find $\mathbf{A}^{-1}$ after this change. Is there a method to find this objective that is more efficient than re-calculating the inverse matrix from scratch.


texts: How to remove filaments from a planar graph?

texts:
I have a planar graph and I'm trying to implement this algorithm (https://geometrictools.com/Documentation/MinimalCycleBasis.pdf Chapter 4, page 3).
For the filament F0(V4, V3, V2), that has one endpoint (same for filament F2), it's easy to detect and remove in a graph (I think it's sufficient iterate vertices and when I find a vertex x that has just one neighboor (length[Adjustment_list[x] == 1), I remove the entire path (except the source node). But how can I remove the filament F1(V5, V6, V8), that has terminating branch points?
P.S. I'm currently working in Java, feel free to poste code if present.
Thanks in advance!


texts: In Strassen's algorithm, why does padding the matrices with zeros not affect the asymptopic complexity?

texts:
In Strassen's algorithm, why does padding the matrices with zeros, in order to multiply matrices that are not powers of 2, not affect the asymptopic complexity?
Hi, I was reading this question but I do not follow Yuval Filmus's answer completely.
He offers two ways of padding the matrix with zeroes, I am interested in his first suggestion, padding the entire matrix with zeroes at the start such that the new matrix has dimensions $N\times N$ where $N = 2^c$.
He says "$N < 2n$ so this doesn't affect the asymptotic complexity."
Could someone please elaborate as I do not follow, I understand calculating time complexity with the master theorem and $T(n) = aT(n/b) + f(n)$ so if someone could explain how this works in reference to that it would be greatly appreciated.