texts: Can we prove mathematical induction statements in Lisp?

texts:
My previous question Can we prove that $1 + 2 + \dots + n = \frac{n(n+1)}{2}$ using a computer program? has a problem that it tries to cover too much ground.  Here is a related question motivated by the comments.

In Lisp and certain other languages code and data are put on equal footing.  Lisp  is certainly strong enough to define abstractions, lazy evaluation and define types.  I wonder if it is strong enough to prove simple statements about itself.

Important here... I only intend to prove specific theorems.  It is quite clear we can't prove all theorems using any programming language.

Let's try:  $1 + 2 + 3 + 4 + \dots + n = \frac{n(n+1)}{2}$.  Then we statement:

$$ P(1): 1 = \frac{1(1+1)}{2} \text{ and }P(n):1 + 2 + 3 + 4 + \dots + n = \tfrac{n(n+1)}{2} $$

We need to show that $\boxed{P(n) \to P(n+1)}$ this type of statement seems simple enough that we could try to verify it within Lisp itself.  I could be wrong.

This couldn't be so hard.  We have two functions:

$F_1(n) = 1 + 2 + 3 + \dots + n$ and $F_2(n) = \frac{n(n+1)}{2}$
In both cases there is some type of recursion $F(n+1) = (n+1) + F(n)$
Then we could show the implication $F_1(n) = F_2(n) \to F_1(n+1) = F_2(n+1)$

The induction step should be expressible as a recursion.  If the program itself can't prove induction statements, perhaps it can just summarize them in some kind of way.

In Haskell, the strong type means that once it compiles you have proven the types agree.  This may not be as strong as proving other types of theorems.

I am not an expert in proof-checkers so excuse me if I get the basic concepts wrong.


texts: Computability of an expression of a function rather than a function itself?

texts:
Let's assume we're talking about real functions purely for clarity purposes, but my question is more general.

We say that a function $f$ is computable, if for a given $x$, a turing machine can output $y$ such that $f(x)=y$.

However, I'm wondering whether there is some concept of "computability for the expresssion of a function". For example, let's say I have some implicitly defined function $f$, and let's say that this function is equivalent to $g(x)=\sin(x)$, but we don't know this yet. Then what we would want is to compute the fact that $f(x)=\sin (x)$, but we don't necessarily need to compute that $f(0.45)=0.434965534...$

Is there a concept that rigorously captures this idea of the expression of a function being computable, rather than the function itself being computable? In other words, it may be that a function is incomputible, but that there is at least a finite number of computations we can do to derive that it has a certain closed form expression.


texts: Calculating the average waiting time of tasks

texts:
I have proposed a load balancing algorithm for a group of homogeneous processing devices and now I want to measure the average waiting time to see if my algorithm is successful in decreasing the waiting time. I have considered number of tasks on each device as the load of that device.

Imagine at first there are 54 tasks that is distributed like this between devices:

  device1 = 32

  device2 = 20

  device3 = 2

And after load balancing 15 tasks are transferred from device1 to device3 and these values change to:

  device1 = 17

  device2 = 20

  device3 = 17

Now I want to calculate and compare average waiting time before and after the load balancing, but I'm confused about which tasks to consider.

Should I consider all 54 tasks and measure the waiting time of all these 54 tasks

Or

should I only consider 15 tasks that were transferred and calculate the waiting time of these 15 tasks before and after load balancing?


texts: Find the upper bound of the recurrence T(n) = T(n - 4) + n with n is odd

texts:
I am trying to solve this recurrence assuming n is odd:
$T(n) = T(n - 4) + \Theta n$

What I did so far was:

First, $T(n - 4) = T(n - 8) + (n - 4) $, thus we get $T(n) = T(n - 8) + (n - 4) + n$

Next, $T(n - 8) = T(n - 12) + (n - 8)$, thus we get $T(n) = T(n - 12) + (n - 8) + (n - 4) + n$

Next, $T(n - 12) = T(n - 16) + (n - 12)$, thus we get $T(n) = T(n - 16) + (n - 12) + (n - 8) + (n - 4) + n$

So know I am seeing that where this is going, I wrote the general form:

$T(n) = T(n - 4k) + [n - 4(k - 1)] + [n - 4(k - 2)] + ... + (n - 4) + n$

As mentioned, we have n is odd so I write it as $n = 2k + 1$, in which we get $k = \frac{n - 1}{2}$. So I will plug that in to get:

$T(n) = T(-n + 2) + (-n + 6) + (-n + 10) + ... + (n - 4) + n$

This is where I am stuck. I suspect that the $(n - 4) + n$ must have gone wrong - but I am not too sure but I decided to ask you guys.

Thank you so much!


texts: If my algorithm has complexity O(n!*n), can I just write O(n!), or do I have to keep it like O(n!*n)?

texts: Just as I asked in the title: if my algorithm has complexity $O(n!\times n)$, can I just write $O(n!)$, or I have to keep it like $O(n!\times n)$?


texts: Prominent applications not suited for distributed computing

texts:
In the www I can find a lot of application examples suited for and benefitting a lot from distributed computing.

Question: Are there applications which are not suited for distributed computing? If yes (which I assume) which promiment examples are out there?

Thanks a lot for pointing me into some useful direction.


texts: How do I implement fixed block storage file system in database from typical file-level file system?

texts:
I've a typical parent ID based file system in database and files are physically stored on disks. What I want is to store files in blocks (4096K) of fixed size.

Chunking can be used I found, but how does a fixed size block storage file system may look like at high level in database?

Suppose I also want to update the specific blocks as per new changes inside files which is located remotely. How do I sync both the files? I found Rabin fingerprint and fixed blocks revision can be used. But, how would I implement the revision inside database that adjusts with my existing file system in database?


texts:
Let there be a dictionary of M words with average length N. We want to compute an M×M matrix of edit distances between all word pairs.

Since there are M² word pairs, and the pairwise edit distance has O(N²) average time complexity, the upper bound on the average time complexity for our problem is O(M²N²).

Is there an upper bound tighter than O(M²N²) on the time complexity for our problem?


texts: Efficient immutable data structure for small multi-sets of integer ranges?

texts:
Background

I'm currently writing some Elixir algorithms that are quite computationally expensive. The most-used datastructure is a multi-set of (finite) integer ranges. Modifying this data structure takes up around 80% of the execution time in insert and remove, so it's time to see if there's something better out there. I'm spending around 1400 clock cycles per insert or remove, so there should be some margin for improvement.

Current implementation

The current model, called Domain, is a fully persistent immutable ordered linked-list of [low, high) pairs, normalized so that for any time two ranges overlap, the first one is the longest. Touching ranges are also joined. Most domains consist of less than 100 ranges, but some consist of up to 10k ranges. The current data structure is chosen because it was easy to work with, avoiding premature optimization.

The Domain datastructure represents a multiset of integers. Internally representing ranges as [low, high) pairs is just an optimization. Since some domains cover many million of numbers, I don't think a multiset would be fast enough to be viable.

A range is a set of b-a unique integers x, a <= x < b, distinct from every previously defined range, with b-a as large as possible.

The operations

The operations supported right now are

insert(a,b) union of two domains, keeping duplicates
remove(a,b) a minus b
intersection(a,b)
ncov(a,n) a with n-1 copies of each present integer removed.
after(a,n) domain of everything in a equal to or greater than n
before(a,n) domain of everything in a equal to or smaller than n
minlen(a,l) domain of all ranges in a with a cardinality of at least l.
trunc_start(a,l) a with the l smallest integers removed from each range.
trunc_end(a,l) a with the l largest integers removed from each range.

Queries:

contains?(a,p) does the domain a contain a specified integer p?
covers?(a,b) is domain b a subset of domain a?
lowest(a) what's the lowest integer in the domain?
highest(a) what's the highest integer in the domain?

Behaviour

The most common use-case is to modify the structure a small bit at a time, from smallest value to biggest. Since inserts might modify the whole structure, the lists are almost always rebuilt completely right now. Changing the access pattern to bulk inserts and deletions is not feasible.

The second most common use-case is intersection between multiple (3+) domains, currently implemented as repeatedly calling the binary intersection function.

Questions

Is there a standard name of this data structure?
Is there a more efficient format? If so, which one(s)?
Would a tree be faster than a linked-list? With or without rebalancing?


texts: who can help me explain the concepts of  "Semantic Web", "Semantic Network", "Semantic Search", "Knowledge graph"(not Google's Knowledge Graph) and "knowledge base" and the relations among them?


texts: Find minimum number 1's so the matrix consist of 1 connected region of 1's

texts:
Let $M$ be a $(0, 1)$ matrix. We say two entries are neighbors if they are adjacent horizontal or vertically, and both entries are $1$'s. One wants to find minimum number of $1$'s to add, so every $1$ can reach another one through a sequence of neighbors.

Example:

100
000
001

Here we need 3 $1$'s:

100
100
111

How can we efficiently find the minimum number of $1$'s to add, and where?


texts: Polynomial Time Reduction - Does 0 calls to the black box still imply a reduction?

texts:
Using the following definition:

  Reduction: There is a polynomial-time reduction from problem $X$ to
  problem $Y$ if arbitrary instances of problem $X$ can be solved using:

  Polynomial number of standard computational steps, plus
  Polynomial number of calls to oracle that solves problem $Y$.

  Notation $X \leq_{P} Y$

Say we had the case where $X$ can be solved in polynomial time using $O(n\log n)$ of computational steps, with zero calls to the oracle / black box used to solve instances of $Y$.

Can we still say $X \leq_{P} Y$? As 0 still classifies as a polynomial number of calls to the oracle that solves problem $Y$, and a polynomial number of standard computation steps were used to solve $X$.


texts: Meaning of polynomially larger, / smaller and meaning of polynomial larger / polynomial smaller

texts:
Hi I have spent the last two hours trying to find a general definition for both of these terms, but it seems like in computer science, people do not really agree on definitions. And I haven't even been able to find it in my slides my lecture notes or in the current book I am using.

Could anyone please give me some general definitions for these terms with some concrete examples? And if you are able to give me some general definitions could you cite where you got it from?


texts: I've been doing research on precollege summer programs, and one ongoing project that has come up is "Improving Label Noise Robustness with data Augmentation and Semi Supervised Learning". So, could someone break this down for me? What is a label, what is label noise, and why is it such a large issue?


texts: How do I apply a single iteration of Floyd's algorithm to an adjacency matrix?

texts:
I have the following adjacency matrix for a graph with nodes {a,b,c,d}:

\begin{bmatrix}
 &  &  a&  b&  c& d\\
 &  &  &  &  & \\
 a&  &  0&  1&  100& 10\\
 b&  &  13&  0&  2& 100\\
 c&  &  100&  12&  0& 3\\
 d&  &  4&  100&  11& 0
\end{bmatrix}
I want to apply the Warshall-Floyd algorithm. I can do this since I know it computes the shortest paths between each pair of nodes. By manually calculating each individual entry, I get the final matrix:

\begin{bmatrix}
 &  &  a&  b&  c& d\\
 &  &  &  &  & \\
 a&  &  0&  1&  3& 6\\
 b&  &  9&  0&  2& 5\\
 c&  &  7&  8&  0& 3\\
 d&  &  4&  5&  7& 0
\end{bmatrix}

My question is this: how can I draw the matrix after each 'iteration' of the algorithm? What qualifies as a single iteration and what does the matrix look like after iteration 1?


texts:
There is a complete binary tree with its leaves as components of some system

The values from one node to another gives propagation time for a signal to propagate from one junction to another
For the signal to arrive at the leaves at exact same time starting from the root we must add delays to some wires.
The cost of adding delays into the system is given by the total amount of extra delay added to all the edges.

For example, one way to remove
clock skew from the tree to the right
would be to increase each edge so that it
has delay 6. This has cost 44.

Second way is to raise the costs
of all edges in the bottom layer to 6, all
edges in the middle layer to 5, and all
edges in the top layer to 4. This has cost
36.

One another way is calculate max delay and modify the bottom layer such that it has delay equal to maximum delay from the root

Is there any other way to get the best solution for minmizing cost to add delay??


texts: How is Hypergraph Isomorphism (HI) reduced to Graph Isomorphism (GI) in polynomial time?

texts: This question states that the problem of Hyper-graph Isomorphism is equivalent to Graph isomorphism. I have not been able to find a description of the reduction so I am wondering how that might work and what is its complexity. If I understand the post in the link correctly, the reduction has to be polynomial in order for the Hyper-graph isomorphism solution to inherit the same complexity as the Graph-isomorphism problem. Is the reduction only valid for a special case of the Hypergraph isomorphism problem or in general?


texts: Matching odd-degree nodes in an undirected graph

texts:
The Chinese Postman problem (A.K.A Route Inspection Problem)

I'm trying to match pairs of odd-degree nodes in a grid-graph representing an indoor map to ensure the graph is Eulerian (consists only of nodes with even degrees).  My plan is to form a matching between the odd-degree nodes and consider Euler paths of the graph augmented by this matching. Matchings of different weights will lead to augmented graphs whose Euler paths have different lengths.

Obviously, if the number of nodes is large, the complexity of matching using brute-force grows in a non-polynomial manner. Hence, I first thought about grouping closest (based on Euclidean distance NOT shortest-path) pairs together using  the recursive divide and conquer approach resulting in a time complexity of $O(n\log n)$. I understand that this would not result in a graph with the optimal Euler path. Do you think there are other problems other than the optimality of the generated Euler Circuit ?
I understand that Edmonds' matching algorithm guarantees an optimal pairing of odd nodes. However, I can't find a decent source that describes the algorithm in a simple manner. Could you kindly provide me with any source other than Edmonds' paper?


texts: How can I avoid re-computation of Dijkstra algorithm if I add or remove one edge from a graph?

texts: I have a nested graph filtration and each step I have to find the shortest path between two nodes. At each step I just add one edge to the graph so the re-computation of the Dijkstra algorithm is extremely redundant. Is there any algorithm to circumvent this?


texts: How to (Efficiently) Sort a List of Items with Parent/Child Relationship

texts:
I have a list of items that have a parent/child/grandchild/etc. type of relationship. Each item has a list of descendants, and an _.isDescendentOf(other) member function that returns true when a node is a descendant of another node (they have a list of immediate parents, and can sweep upwards to find grandparents). Some of the items may not have a relationship with one another. I need to sort these items such that no item comes before an item it is a descendant of.
Consider items of the format (a, [b, c]) which indicates that a has descendants b and c. If we had the unsorted list (with an invalid ordering): [(c, []), (a, [b, c]), (b, [c]), (d, [])]
Valid orderings would be: [(a, [b, c]), (b, [c]), (c, []), (d, [])] or [(d, []), (a, [b, c]), (b, [c]), (c, [])]
(Note, (d, []) can technically be placed anywhere since it does not have a relationship with the others.)
(Note, a, b, etc. are randomly-assigned placeholder names and, though they are alphabetically ordered here, in reality they are random.)
I am quite unsure how to achieve this in an efficient way. My (current) solution involves maintaining a list of "placed" and "unplaced" items (the former is empty at the beginning, and the latter initialized with a copy of the unsorted list), and then greedily moving "unplaced" items to the "placed" list when they do not have any ancestors in the "unplaced" list (until the "unplaced" list is empty). That being said... I am curious whether there is a more efficient way to achieve these results. Thanks in advance!


texts: Minimal size of a context-free grammar which defines $L_n=\{a^k\mid 1\le k\le n\}$

texts:
I am looking for the minimal size of a context-free grammar which defines the finite language $$L_n=\{a^k\mid 1\le k\le n\}.$$
The size of a grammar is defined as the total length of all right-hand sides of the rules.
For example a grammar with
$$S\to A_1A_1\\A_1\to A_2A_2\\A_2\to A_3A_3\\A_3\to A_4A_4\\A_4\to aa$$
has size $5\cdot 2=10$.
It is well-known that the minimal context-free grammar which defines the language only accepting the word $a^k$ has size $\Theta(\log k)$ (see the example above for the construction of the word $a^{32}$).
Now, I am interested in the size of a grammar constructing all strings $a^k$ ($1\le k\le n$) for a given $n$. By the information above it is easy to create a grammar for $L_n$ of size $$\Theta(n+\sum_{k=1}^{n}\log k)=\Theta(\log n!)=\Theta(n\log n)$$
since we can create all words by a grammar of size $\Theta(\log k)$ and connect those grammars with a start rule of size $n$ (one symbol for each word). But since the final grammar is allowed to share nonterminals this construction is clearly not optimal. Maybe the smallest grammar has asymptotically the same size, but i don't know. Any help?


texts: Why does this graph show the tightness of MST heuristic's 2-approximation bound?

texts:
This is a homework problem I've been given and I've been raking my brain for hours (so I'm satisfied with some pointers). I know already that the approximation ratio cannot be worse than $2$. I have a wheel graph, where each edge has cost $1$ and the distance between all nodes which are not connected by edges is $2$. The wheel graph $W_6$ is this one:

I have marked in blue what I believe to be the output of an MST heuristic algorithm. But I also think this is the optimal solution, since all nodes can only be visited once. So the cost of the tour would be $7$ for both optimal and MST.

I do not see how this type of graph shows that the $2$-approximation bound of MST heuristic is tight (not necessarily this instance, but the graphs $W_n$ in general). Can someone enlighten me?


texts: Does "standard" Dijkstra's algorithm work with bi-directional edges and zero cost edges?

texts:
I have been reading about Dijkstra's algorithm and I think I understand it. I followed the algorithm in pseudo-code from Wikipedia, and now I wonder:

If my graph is bi-directional and I add each edge to my graph twice (once "forwards", once "backwards"), will the "standard" Dijkstra's algorithm work?
Is it ok that some of my edges are zero cost? (the rest are all positive - none are negative)

And finally, what is a Dijkstra "heap" algorithm? Is it the same as Dijkstra's algorithm using a PriorityQueue?


texts: What's elementary operation in Computer science?

texts: What do Computer Science mean when they use the Term Elementary Operations?


texts: How binary search works in real world scenario?

texts:
In binary search, we need an array of integers for it to search for an element. Also, many other sorting algorithm sorts array of integers.

But in real world, we may search for a name of an employee in a database, title of a post etc. So how does binary search actually works in such cases? Is the data converted and stored in some numeric format? Then how does it point to the original record?

Please explain in detail with a small example if possible.


texts:
I have just used a function 'rand()' in my algorithm. In fact, it was arc4random() that I used. However, it got me thinking, how is randomness created in a computer system?
Can anything ever truly be random when it is produced by a computer?


texts: What is the maximum number of classes resulting from partitioning by DFA as function of number of states?

texts:
I was wondering whether it is possible (and if so, then how) to tell what is the maximum number of equivalence classes generated by a DFA as per Myhill-Nerode theorem (assuming it has no redundant transitions) as a function of number of accepting and rejecting states and cardinality of its alphabet.

My guess is that it should be something like $\log(n) \cdot |{\Sigma}|$, where $n$ is the number of states, since one could see this as tree of derivations created by something like left-regular grammar equivalent to the same automata, and classes would be the leafs of this tree.  But this is just a guess.


texts: Minimize cost and maximize quality of function in four variables

texts:
Problem: Find optimal values for four parameters which are used to tune an algorithm under the constraints of accuracy, time and memory.

I have an indexing scheme used to search for the K-nearest neighbors of a point in many dimensions. This indexing scheme has four adjustable parameters. For each given fixed problem size (total number of points, number of nearest neighbors to find, number of dimensions, desired accuracy) I plan to run a solver to find the optimal values for these four parameters. Here are the constraints:

1) If the accuracy is below desired accuracy (say 95%), prefer parameter values that maximize the accuracy.

2) Once the accuracy equals or exceeds the desired accuracy, prefer parameters that minimize the execution time.

3) Do not exhaust all system memory.

I handle #3 by restricting the one parameter that is directly proportional to memory usage based on numerous manual tests.

One of the parameters is discrete: it may only take on integer values. (This is the one that affects memory size).

Three of the parameters always move in the same direction as accuracy: as they increase, accuracy always remains the same or increases, up to a maximum of 100%. Each of these three parameters also moves in the same direction as cost: as they increase, the cost always increases (without bound).

The fourth parameter has the smallest (and least predictable) influence on cost. The accuracy will always decrease as you move farther away from the optimal value, either up or down.

Because of the 100% accuracy cutoff, the function has places with no derivative (is not smooth).

I have hundreds of combinations to optimize, varying # of dimensions versus # of points. My current approach runs all night without completing all the cases and produces erratic results (poor solver algorithm that gravitates toward high accuracy and horrible time cost). Given the nature of the constraints I have described and the number of parameters, which class of algorithms should I investigate? I understand the gradient method, but worry that it will perform poorly (too many steps) or not work with the non-smoothness of the function.

It might be possible to seed each successively larger case with the best results from the next smaller case; the parameter values should vary smoothly as the case sizes increase. the cost of evaluating the execution time and accuracy increases with the number of points and with the number of dimensions.

Current algorithm:

1) Start with seed values for each parameter, as determined after days of manual testing.

2) Holding all parameters fixed but one and varying that one, find its best value. Test values in increasing order, stopping when the accuracy is acceptable.

3) Repeat for all parameters.

4) Make five passes over all parameters. At each pass, use a finer grid for the search.

My approach is basically using an inefficient gradient search in one dimension at a time. It is slow and produces good results for the smaller cases but soon yields poor results for the medium sized cases.

The Four adjustable parameters

In thinking about them, I have decided that three of the parameters can be represented as discrete integer values, and only one is continuous.

a) Perms = Number of permutations of the index to create. Each index takes up  memory. This parameter has the dominant influence on memory usage. This ranges from 3 to 20. Depending on the number of points indexed, somewhere between 20 and 32 indices will use up all memory.

b) Margin = Number of points to select in each index probe. If K is the number of neighbors sought, Margin typically varies from 3*K to 20*K.

c) Box-Points = Number of random  faces of a hypercube surrounding the search point to probe. This ranges from 1 to 2*dimensions.

d) Box-Size = A fraction to multiply by the characteristic hypercube size to define the volume of hyperspace to search. Typically ranges from 0.3 to 1.5.


texts: Does a DFA accept an empty string if $q_0$ is the accept state?

texts: Suppose $q_0$ is the start state, does this mean that if it's the accept state, then the machine must accept the empty string since it cannot have a transition with the empty string?


texts:
In long-multiplication, you shift and add, once for each $1$ bit in the lower number.

Let $r = p \otimes q$ be an operation similar to multiplication, but slightly simpler: when expressed via long-multiplication, the addition does not carry. Essentially you bitwise-xor the shifted numbers.

Like so:

$$
  \left[\begin{matrix}
    &&p_n & ... & p_i & ... & p_2 & p_1 \\
    &&q_n & ... & q_i & ... & q_2 & q_1 & \otimes\\
    \hline\\
    &&q_1 \cdot p_n & ... & q_1 \cdot p_i
      & ... & q_1 \cdot p_2 & q_1 \cdot p_1\\
    &q_2 \cdot p_n & ... & q_2 \cdot p_i
      & ... & q_2 \cdot p_2 & q_2 \cdot p_1\\
    &&&&&&&...\\
    q_i \cdot p_n & ... & q_i \cdot p_i
      & ... & q_i \cdot p_2 & q_i \cdot p_1 & \stackrel{i}{\leftarrow}
      &&{\Huge{\oplus}} \\
    \hline \\
    \\r_{2n}& ... & r_i
      & ... &r_4& r_3 & r_2 &r_1 & =
  \end{matrix}
  \right]
$$

Using the long-multiplication-style formulation, this takes $\mathcal O\left(\max\left(\left|p\right|,\left|q\right|\right)^2\right)=\mathcal O\left(\left|r\right|^2\right)$ time. Can we do better? Perhaps we can reuse some existing multiplication algorithms, or even better.

Followup: Shift-and-or multiplication operation


texts: What would happen in this priority-based round-robin CPU scheduling algorithm case?

texts:
I've been implementing some kind of CPU Scheduling Algorithms in Python. And I am really confused with one of the cases what'd be implemented in this case.
Let us assume that the time quantum is 10.
If the first come process which came at 0 has a burst time of 7 (simply denoting that it is less than the time quantum). And let us say at 5 another process with a higher priority comes. In this case, would there be a context switching to the one that came later?


texts: What is the time complexity of enqueue and dequeue of a queue implemented with a singly linked list?

texts:
I’m trying to understand the time complexity of a queue implemented with a linked list data structure. My book says that we can the implement a queue in O(1) time by:

enqueueing at the back
dequeueing at the head

and it also says

  Note that although adding an element to the tail is constant time,
  removing an element from the tail is O(n) as we have to find the new
  tail

I know that adding a new node to my queue at the head (enqueue) takes O(1) since I have the head pointer. Similarly, removing a node at the head (dequeue) will take O(1) as well. But I don’t understand why adding an element at the back (enqueue) takes O(1), while removing it (dequeue) takes O(n). It would make more sense to me if enqueueing at the back took O(n) rather than O(1), since in both cases (adding/removing at the back) would need to find the tail pointer and therefore it would need to traverse the entire list.


texts: Enumerate all non-isomorphic graphs of a certain size

texts:
I'd like to enumerate all undirected graphs of size $n$, but I only need one instance of each isomorphism class.  In other words, I want to enumerate all non-isomorphic (undirected) graphs on $n$ vertices.  How can I do this?

More precisely, I want an algorithm that will generate a sequence of undirected graphs $G_1,G_2,\dots,G_k$, with the following property: for every undirected graph $G$ on $n$ vertices, there exists an index $i$ such that $G$ is isomorphic to $G_i$.  I would like the algorithm to be as efficient as possible; in other words, the metric I care about is the running time to generate and iterate through this list of graphs.  A secondary goal is that it would be nice if the algorithm is not too complex to implement.

Notice that I need to have at least one graph from each isomorphism class, but it's OK if the algorithm produces more than one instance.  In particular, it's OK if the output sequence includes two isomorphic graphs, if this helps make it easier to find such an algorithm or enables more efficient algorithms, as long as it covers all possible graphs.

My application is as follows: I have a program that I want to test on all graphs of size $n$.  I know that if two graphs are isomorphic, my program will behave the same on both (it will either be correct on both, or incorrect on both), so it suffices to enumerate at least one representative from each isomorphism class, and then test the program on those inputs.  In my application, $n$ is fairly small.

Some candidate algorithms I have considered:

I could enumerate all possible adjacency matrices, i.e., all symmetric $n\times n$ 0-or-1 matrices that have all 0's on the diagonals.  However, this requires enumerating $2^{n(n-1)/2}$ matrices.  Many of those matrices will represent isomorphic graphs, so this seems like it is wasting a lot of effort.
I could enumerate all possible adjacency matrices, and for each, test whether it is isomorphic to any of the graphs I've previously output; if it is not isomorphic to anything output before, output it.  This would greatly shorten the output list, but it still requires at least $2^{n(n-1)/2}$ steps of computation (even if we assume the graph isomorphism check is super-fast), so it's not much better by my metric.
It's possible to enumerate a subset of adjacency matrices.  In particular, if $G$ is a graph on $n$ vertices $V=\{v_1,\dots,v_n\}$, without loss of generality I can assume that the vertices are arranged so that $\deg v_1 \le \deg v_2 \le \cdots \le \deg v_n$.  In other words, every graph is isomorphic to one where the vertices are arranged in order of non-decreasing degree.  So, it suffices to enumerate only the adjacency matrices that have this property.  I don't know exactly how many such adjacency matrices there are, but it is many fewer than $2^{n(n-1)/2}$, and they can be enumerated with much fewer than $2^{n(n-1)/2}$ steps of computation.  However, this still leaves a lot of redundancy: many isomorphism classes will still be covered many times, so I doubt this is optimal.

Can we do better?  If I understand correctly, there are approximately $2^{n(n-1)/2}/n!$ equivalence classes of non-isomorphic graphs.  Can we find an algorithm whose running time is better than the above algorithms?  How close can we get to the $\sim 2^{n(n-1)/2}/n!$ lower bound?  I care primarily about tractability for small $n$ (say, $n=5$ or $n=8$ or so; small enough that one could plausibly run such an algorithm to completion), not so much about the asymptotics for large $n$.

Related: Constructing inequivalent binary matrices (though unfortunately that one does not seem to have received a valid answer).


texts: Prove that the complements of pumping-style languages are context-free

texts:
Define $L = L(u,v,x,y,z) = \{uv^ixy^iz : i \geq 0\}$, with $u,v,x,y,z \in \Sigma^*$.  Prove that $\overline{L}$ is a CFL for all $u, v, x, y, z$

Clearly, $L$ is a CFL, as it is generated by the grammar:

$S \longrightarrow uAz$

$A \longrightarrow vAy$

$A \longrightarrow x$

I am struggling with this problem, because I don't see how I'd go about constructing a PDA or CFG for $\overline{L}$.  The fact that L "looks like" the main condition of the pumping lemma for CFLs must somehow relate, but I am not seeing the connection.  Maybe I could do something with morphisms?


texts: What is the best algorithm for image comparison in terms of speed?

texts:
Problem domain - I'm implementing a home monitoring system using smart phones. At regular intervals rear camera of the phone takes images and compare them for a change detection. This change detection is done inside the android app itself. Only after a change is detected, image is sent to server.

I want to know a fast algorithm to compare two images and detect whether a significant change is occurred. I want to avoid changes due to light effects and negligible changes. So far I have come up with multiple options
 1. Feature matching using SIFT
 2. Comparing histograms
 3. Template matching

But I'm not sure which one is more appropriate to my problem domain or whether there are better options.


texts: Unique decipherability of infinite regular language

texts:
Can we design an algorithm to test if a infinite regular language is a code?
We have the S-P algorithm to determinate if a finite language is a code. But how about the infinite part of regular languages?
If we have a regex which describes our set of words, then is it possible to modify the S-P algorithm to work on an infinite set without creating Pattern Matching Machines? If it helps, let the regex use only '* | ()' as special symbols.
I thought about making an algorithm which would work based on a PMM, but it isn't as trivial as the S-P algorithm for finite sets, checking the suffixes of strings with matching prefix. The algorithm would be creating a PMM from the regex and traversing it for the search of suffixes etc. like in the S-P algorithm.


texts: Language involving irrational number is not a CFL

texts:
I am working through a hard exercise in a textbook, and I just can't figure out how to proceed. Here is the problem. Suppose we have the language $L = \{a^ib^j: i \leq j \gamma, i\geq 0, j\geq 1\}$ where $\gamma$ is some irrational number. How would I prove that $L$ is not a context-free language?

In the case when $\gamma$ is rational, it's pretty easy to construct a grammar that accepts the language. But because $\gamma$ is irrational, I don't really know what to do. It doesn't look like any of the pumping lemmas would work here. Maybe Parikh's theorem would work here, since it would intuitively seem like this language doesn't have an accompanying semilinear Parikh image.

This exercise is from "A Second Course in Formal Languages and Automata Theory" by Jeffrey Shallit, Exercise 25 of Chapter 4.

I would really appreciate any help, or nudges in the right direction. Thank you!


texts: Identifying/equating constants in a term rewrite system

texts:
Suppose we have a term rewrite system $\mathcal{R} = (R, \Sigma)$ with basic rewrite rules $R$ over a signature $\Sigma$. Suppose also that this rewrite system $\mathcal{R}$ is confluent and terminating, and that each constant symbol of $\Sigma$ is a normal form with respect to $\mathcal{R}$.

Now suppose that we want to identify/equate some of the constants of $\Sigma$. For example, if we have two constants $c, d$ in the signature $\Sigma$, then we may want to 'merge' $c$ and $d$ into a single constant $e$ (thereby obtaining a new signature $\Sigma'$ that is the same as $\Sigma$ except that $c$ and $d$ have been replaced by $e$), and then modify the basic rewrite rules in $R$ accordingly (by replacing all occurrences of $c$ and $d$ by $e$).

If we identify/equate some constants of $\Sigma$ in this way, and then modify the rules in $R$ accordingly, so that we obtain a slightly modified term rewrite system $\mathcal{R}' = (R', \Sigma')$, is there any way to prove that $\mathcal{R}'$ will still be confluent and terminating?

Obviously, if $R$ has a rule like $c \to d$ and we merge $c$ and $d$ into the single constant $e$, then this rule will become the rule $e \to e$, and so the resulting system will not be terminating. But this is why I assumed that each constant of $\Sigma$ is a normal form with respect to $\mathcal{R}$ (so that $R$ will not have rules like $c \to d$).


texts: What is the computer science interpretation of a qubit?

texts:
I am a CS major trying to decipher quantum computing. I have done some elementary study on qubits and I always seem to get lost at the "infinitely many" states that the qubit can have. And I really want to understand what it actually means. My understanding is as follows and please correct me if I am wrong,
A classical bit has two states 0 and 1, which means n bits can represent 2^n different states, though each state is individually expressed. A Qubit could have "infinitely many" states between 0 and 1. This means that n qubits can represent m^n states, Where 'm' is the base and m > 2. This would mean we can represent larger numbers using fewer qubits when compared to the classical bit. If this is so, how does this lead to an increase in computation speeds?
If I am completely off track, what is the actual interpretation of a qubit?


texts: Applications of Lamport's Distributed Mutual Exclusion algorithm

texts:
I'm trying to understand the relevance of the Lamport distributed mutual exclusion algorithm (or any of its variants), where a group of processes cooperate to gain exclusive access to a resource without relying on a centralized coordinator.

How can this be useful in practice?  For instance, if the resource is something like a printer, or a shared file system, it can enforce mutual exclusion on its own, so there is no need for a distributed algorithm. I can't think of an example where this wouldn't be the case.  What am I missing?


texts: What is the relation between Universality and simulations of Cellular Automata structures?

texts:
Elementary Cellular Automata and Conway's Game of Life show interesting Cellular structures, suppose we have a computational model {a Cellular Auotmaton} that can simulate both CA types (ECA & Conway's Game of life) from one input.

Meaning that, if we had a system with an input of (x), (x) can show a structure to an ECA rule {like rule 90} and that system by somehow can transform the input (x) when specified, to show similar patterns like in Conway's Game of life, how this would be related to universality in terms of simulations?

What about complexity, can be related also?


texts: 2D version of LeetCode house robber problem

texts:
The house robber problem of leetcode can be described as followed :

  A robber enters a colony of houses numbered from 1 to n.  Every house has a number printed on the top of it.  That number is the amount of money inside that house. However, there is one constraint. If the robber robs the i-th house, he can't rob house no i-1 and house no i+1. How can the robber maximise his robbery?

Apparently, this is a classical problem in dynamic programming, which can be solved in linear complexity: See here and here.

My question : what about the 2D version ? if the houses are not on a line, but on a 2D grid ? Like for the 1D version, if you rob one house, you cannot rob the adjacent ones (see the following pattern) :

x x x
x o x
x x x

Can DP be used to solve that ? Is it even linearly solvable ?


texts: Find all disconnected directed (cyclic) subgraphs and transform them into stars

texts:
I have a graph $G=(V,E)$ that consists of many disconnected directed subgraphs, some of them may be cyclic. (Basically a "forest" consisting of directed trees and some directed disconnected cyclic graphs added into it).

I want to find all of these disconnected subgraphs and turn them into stars given by the key of the node.

I've built a directed graph (using Python's networkx library) and now I am kinda stuck how to find those disconnected subgraphs, because some of those subgraphs will have source and some of those wont.

How to proceed? Thanks!


texts: Autocorrect algorithm - How to implement a decent "apostrophe & elision" feature?

texts:
shorter version of the original question (as requests in comments)

What is the algorithm to handle missing apostrophe as it is done in auto-correct feature of Android virtual keyboard?

(If it helps / makes sense, feel free to give info about how such feature handles the detection and 2 words being written without any space between them?)

I need this in French where this happens much more than in English.

Example

Jai -> J'ai ('I have' in French)

Regex could be part of the solution?

Here are some regex to recognize the beginning of some (french) words, but these do generate way too many false positive candidates

\b(c)(h?[aeiou])
\b(j)(h?[aeiou])
\b(n)(h?[aeiou])
\b(m)(h?[aeiou])
\b(t)(h?[aeiou])
\b(s)(h?[aeiou])
\b(l)(h?[aeiou])
\b(d)(h?[aeiou])
\b(qu)(h?[aeiou])

Note:
For sake of completeness, I alreay have the 2 remaining simple cases already covered in the dictionary xml file

<word src="sil">s'il</word>
<word src="sils">s'ils</word>

Keeping original question for reference purposes:

Context

Using the opensource AnyosftKeyboard keayboard provider app, I would like to add an "elision/apostrophe" feature to make it aware of missing apostrophe in typed word and add it in the frame of its autocorrect feature.

A word about apostrophe & elision

"The apostrophe in French is used to replace a final vowel which is not pronounced because the next word also start with a vowel or silent “h”. The removing of a final silent vowel is called the ELISION.

In written French, elision takes place only with the following words : ce, je, ne, me, te, se, le, la, de, que, and si (only with “il” and “ils”)."

Source, where you can read more for some examples: https://frenchforenglishhindispeakers.wordpress.com/2012/09/25/lapostrophe/

Example

He is my friend -> Ce est mon ami (incorrect)
'Ce' is followed by 'est' -> elision (deletion) of the 'e' of 'Ce')
                -> C'est mon ami (correct)

Goal

Given the former example, I would like to implement a feature that would detect

Cest

and replace it by

C'est

That would allow the user to type faster by just ignoring apostrophe.
This behavior is already implemented in default Android keyboard

Questions

1 - What would be a proper algorithm to implement this "apostrophe & elison" feature?
 2 - How is this feature implemented in Android keyboard(s)?

PS

I am not sure if this is the right place to ask such question. If not, please let me know where I should ask it. Thanks.


texts: What is the current status of parallel or concurrent programs in the Curry-Howard isomorphism?

texts:
In Girard's Proofs and Types we can read :

  From an algorithmic viewpoint, the sequent calculus has no
  Curry-Howard isomorphism, because of the multitude of ways of writing
  the same proof. This prevents us from using it as a typed $\lambda$-calculus,
  although we glimpse some deep structure of this kind, probably linked
  with parallelism.

  Proofs and Types, J.Y Girard (Page 28)

But we can also read (about Linear Logic) that

  From the viewpoint of computer science, it gives a new approach to
  questions of laziness, side effects and memory allocation [GirLaf,
  Laf87, Laf88] with promising applications to parallelism.

  Proofs and Types, J.Y Girard (Page 149, written by Yves Lafont)

How are parallel programs linked to the Curry-Howard isomorphism ? What are the current thoughts about that ?


texts:
Does Huffman algorithm generate a minimal weight of a tree?

I noticed that by trying to make two different trees with the same frequencies of letters, I get different weights of the trees.

We defined the weight of the tree as $\displaystyle\sum_{c\in C}f(c)d(c)$ where $C$ is all the letters, $f()$ is the frequency of the letter, $d()$ is the depth in the tree of that letter.


texts: Is there a O(log n) algorithm for matrix exponentiation?

texts:
Is there an algorithm to raise a matrix to the $n$th power in $O(\log n)$ time?

I have been searching online, but have been unsuccessful thus far.


texts: Can all decision problems reduce to undecidable?

texts:
If one could build a machine that for any input will never accept, but always loop forever, then will all problems reduce to this?

Or did I just misunderstood the idea of reduction?


texts: Decision Problem vs. Optimization Problem

texts:
Is the following statement correct?

If a decision problem is NP-complete, the corresponding optimization problem can not be solved in polynomial time.


texts: Do multiple transitions over the input give finite state machines more power?

texts:
In the common model of FSA, the automaton reads the input string once, moving from one state to another after reading each letter in the input string. Epsilon transitions allow moving from one state to another without reading a character. However, the movement over the input string is still unidirectional.

Is there a formal model of a FSA that reads the input string K times, and only then reaches its final state? is this model more powerful than FSA, e.g., can it recognize context-free languages that are not regular?

I think the option of adding an epsilon transition for every transition edge in the FSA means the models are equivalent in power (since we can model K iteration over the input by epsilon transitions from the last state back to the first -- although I am not sure), but if this is so, are there any results regarding the number of states needed in a regular FSA and a FSA with K transitions?


texts: Does Warnsdorff’s algorithm for Knight’s tour problem always gives complete tour

texts:
I have implemented the basic algorithm. easily available but I am not getting the complete tour.
The visited square never equals N * N;


texts:
Suppose a person states the following: $n^2 = (n * n), \forall n > 0$. One can check such equality by saying, via proof by induction, that:

for $n := 0:\ 0^2 = (0 * 0)$;
for $n := 1:\ 1^2 = (1 * 1)$;
and for $n := n + 1:$

$\ (n + 1)^2 = ((n + 1) * (n + 1))$

$n^2 + 2n + 1 = n^2 + 2n + 1$

As far as I understand, this states that:

$P(n)$ is valid for some $n$ within a range, say integers greater than 0;
$P(n)$ must be valid for the successor of any $n$ within the previous range;

Of course, it is not commonly necessary to prove such things as $n^2 = (n * n)$. And, proving it seems rather like considering that, eventually, there could be a mysterious value for $n$ that would make $n^2 \neq (n * n)$.

First question: is this interpretation correct?

Now, if one could prove $P(n): n^2 = (n * n)$ via the base and the induction cases:

$P(n)$ is valid for $n := 0$;
$P(n)$ is valid for $n := n + 1$;

One should also be allowed to prove it by saying that:

$P(n)$ is valid for $n := 0$;
$P(n)$ is valid for $n := n + 2$;
and via $P(n)$ is valid for $n := n + 3$;
and via $P(n)$ is valid for $n := n + 4$;
and, in fact, via $P(n)$ is valid for $n := n + m,\ \forall m > 0$.

Second question: is this inference correct?

So, if we are fine thus far, it should be the case that, eventually, a mysterious value $m$ could make proof by induction fail. And here comes the final question.

Third Question: how to prove the correctness of proof by induction?


texts: Optimal way to find maximal sum (with constraints) of array elements

texts:
Problem: Find the maximum sum of the elements in an array, with the following constraints:

all the elements of the array are non-negative integers
each element can either be left out completely from the sum (skipped), can be added, or can be subtracted from the sum
when reading the array left to right (i.e. from index 0 to index size - 1), the sequence of operations must be subtract, add, subtract, add, ... etc, with optional skips in between (e.g. subtract, skip, skip, add, subtract, skip, add)
in other words: the first element included in the sum must be subtracted, the next element included into the sum must be added, the next subtracted, etc... (i.e. we always start with subtraction).

Example: Suppose we have the following array: [1, 2, 3, 4, 5].

Then the sums following is valid:

-1 + 2 -3 +4 -5

-1 + 0 + 3 -4 +5

-1 + 0 + 0 + 0 + 0

0 -2 + 0 + 0 + 5

0 + 0 + 0 + 0 -5

0 + 0 + 0 + 0 + 0

Some invalid sums:

+1 -2 +3 -4 +5  // We did not start with subtraction (+1)

-1 -2 +3 -4 +5  // Two consecutive subtractions (-1 -2)

-1 +2 +0 +4 -5  // Two consecutive additions (+2 +4).

My solution: There are 2^N possible valid sums (where N is the size of the array), since if we read the array left to right, each element can either be included into the sum or not.
For each of these cases, let's calculate the sum that we get, and choose the minimum of those sums.

Pseudo code of my solution:

func findMax(a []) {
    max := 0;
    for (i := 0; i < 2 ^ a.size; ++i) {
        code := i;       // binary representation of the next possibility
                        // 0: we do nothing
                        // 1: we add or remove the next element
        sum := 0;
        sign := -1;
        for (j := 0; j < a.size; ++j) {
            if (code[j] == 1) {    // jth digit of code
                sum := sum + sign * a[j];
                // if (sum < 0) { goto end } // (1) would this help?
                sign := -sign;
            }
        }
        if (sum > max) {
            max = sum;
        }
end:
    }
    return max;
}

Optimization This solution has exponential run-time complexity in the size of the array, therefore I was asking myself how to optimize it. The only idea I have is to backtrack (i.e., don't continue the calculation for a given case), whenever the partial sum becomes negative (see commented out line (1) in the pseudo code). However, I'm not sure that a.) this could not weed out in some way the maximum we are looking for (although I can't think of any counter examples) and b.) that there other, even more efficient ways to backtrack.

Questions

1.) Is there an example, where back-tracking upon encountering a negative partial sum (i.e. the solution suggested at line (1)) would prevent us from finding the real maximum sum?

2.) Is there some even better way to back-track?

3.) What other approaches exist for this problem?


texts: How does Rabin fingerprint finds breakpoints (chunk boundary)?

texts:
I was reading up on chunking and found Rabin fingerprinting is also used to break files into chunks. After reading about this algorithm, I understood how rolling hash is computed using Rabin fingerprint. This is explained almost everywhere. What I don't get is how in Rabin fingerprinting, we know to end one chunk here and start another? And how does insertion doesn't affect original chunks? Some sources mention the following, which I didn't get. (Although it's given with reference to LBFS, I think for de-duplication also chunking will be done in similar way.)

When the low 13 bits of the fingerprint are zero LBFS calls those 48 bytes a breakpoint and ends the current block and begins a new one. Since the output of Rabin fingerprints are pseudo-random the probability of any given 48 bytes being a breakpoint is 2^{-13}. This has the effect of shift-resistant variable size blocks.

We are checking if low 13 bits are 0 or not, because fingerprint is basically a remainder, after dividing by an irreducible polynomial? But even then, how does inserting something in chunk-1, still makes sure chunking will be shift-resistant?

Thanks in advance for the help!

Edit : I am talking about application of Rabin fingerprinting in breaking files into chunks for de-duplication. (Not for string search, I understood that one)


texts: Persistent data structure with double and subtract operations

texts:
I am seeking a data structure that maintains an array of N numbers and supports the following two operations:

Double the first i numbers
Subtract the first i numbers of a previous version from the current version.

It always starts with an array filled with 1s, and we only need to know the final array (after all operations have been applied).  The algorithm doesn't have to be online.  Assume overflow won't happen.

Is it possible to solve this in close to linear running time (e.g., Q log N or Q sqrt N where Q is the number of operations)?  I invented this problem for a programming contest and I'm wondering how efficiently this can be done.

Here is an example:

We start with the array [1,1,1,1] (version 1)

Double the first 3 numbers to get [2,2,2,1] (version 2)

Double the first 1 numbers to get [4,2,2,1] (version 3)

Subtract the first 3 numbers of version 1 to get [3,1,1,1] (version 4)

Subtract the first 1 numbers of version 2 to get [2,1,1,1] (version 5)

Then the program would output the final version: [2,1,1,1]


texts:
A sorted array $A[1..n]$ is given. Each element of $A[i]\in \mathbb{N}$, and for each $A[i],A[j]$ we have $A[i]+A[j]\leq n$. Find two elements $A[i], A[j]$ such that $(A[i]-i)+(A[j]-j)=0$. Give a deterministic $O(n)$ time algorithm for this problem.
I tackle with this problem as follow :
Calculate each $A[i]-i$ , and insert it into hash table $T$ that take $O(n)$ , then one time traverse $A$ such that to find and element that $A[i]-i=T[i]$. Each search take $O(1)$ in expected, but we must give a deterministic in $O(n)$.


texts: Any notions of operations in basic postulates of lambda calculus

texts:
I am learning Lambda Calculus from the book by Hindley and Seldin . They start the formal postulation of lambda calculus as follow :

(a) all variables and atomic constants are λ-terms (called atoms);

(b) if M and N are any λ-terms, then (MN) is a λ-term (called an application);

(c) if M is any λ-term and x is any variable, then (λx.M) is aλ-term (called an abstraction).

In the second postulate $MN$ has been termed as a $\lambda$ term . How to define $MN$ , what does it mean ? Is it an operation?
Is there any scope of defining operations in lambda calculus which are associative and/or distributive  ?


texts: How to show that a partial function is recursive?

texts:
I try to prove that this function is recursive:
$$f(x_1,x_2)= \begin{cases}
2x_1-x_2  & \text{if $x_1 \geqslant \sqrt{x_2}$} \newline
\bot & \text{otherwise}
\end{cases}$$

I think that I need to use minimization operator but I don't know how to do that. $\qquad $ $\qquad $ $\qquad$  Maybe i have to prove that
$$\mu y(|x_1-\sqrt{x_2}| = 0)$$ ?


texts: What datastructure does google use to store its search engine indexes?

texts:
To the best of my knowledge search engines such as Google index the web using MapReduce amongst many other tools. With my limited experience this would make hash tables the most practical option for storing the MapReduce output which by default is in the form of an inverted index.

Are hash tables in fact used by Google for storing search engine indexes or does Google use other datastructures such as binary search trees?

As a follow up question if Google uses another datastructure over hashtables what advantages does it provide?


texts:
I have to show a property P is trivial.

This problem has to do with Rice's Theorem, which I do not completely understand. Can someone explain the difference between trivial and non-trivial properties?


texts: Can the complement of a context-free language be regular?

texts:
I know that the context-free language is not closed under the complement ,
and the result could be context-free language or non-context free language
but my question is :

is it possible of the complement of context-free language = regular language ?


texts: Finding the spots furthest away from bad data

texts:
The real-world problem I'm trying to solve is to create an algorithm which finds the ideal channels where I can transmit radio traffic, inside a radio frequency band that could contain various disturbances. These n ideal channels are those who are furthest away from any of the disturbances, but also the furthest away from each other. Where n is a constant picked by me, depending on how many channels the radio can support.

In abstract terms, I have a chunk of generic data where each item could either be labelled "good" or "bad". It can be considered to be an array of booleans, or illustrated as a series of 1=good and 0=bad, for example 0010111100.

In this data, consecutive sequences of good data form good segments:

0010111100   data size=10
  ^ ^
  | +------- good segment 2, size 4
  +--------- good segment 1, size 1

In the best case, there only exists one good segment covering all of the data:

1111111111   data size=10, 1 good segment with size 10

No matter the nature of the data, I need to find the n "best places" that are furthest away from any bad data, but also from each other. It is considered equally bad to be near a "bad" item as it is to be near another "best place".

The ideal solution is where the minimum distance between all "best places" and bad data/other best places is as long as possible, for all best places.

For example, in the case of 1111111111 where n=3 places, they could be located as follows (simply divide the data size by 3):

1111111111   data size=10, n=3
  ^  ^  ^

Or in case of 0110111110 n=3, the following would be fine:

0110111110   data size=10, n=3
 ^   ^ ^

or

0110111110   data size=10, n=3
  ^  ^ ^

In case there is too much bad data, the problem has no solution. The sum of all good segment sizes must be at least n or there exists no solution.
Example:

0000010001   data size=10, n=3, no solution possible.

I suppose one solution is to find the n best segments out of all the good segments - then simply find the n best places at the center of those segments.

But one problem then is that there aren't necessarily n good segments. In that case, the best places have to be divided across what good segments there are.

Are there any similar existing algorithms that could be used or modified to suit the above scenario?

I'm also wondering if there is a particular data structure that would beneficial to use in this case, other than a raw array? A heap binary tree consisting of good segments?


texts: Word- or byte-addressable? Correct terminology

texts:
Seemingly, a byte has established itself to be 8bit (is that correct?). RAM and NOR-flash can be normally accessed on a quite granular level, but it is up to the system architecture to determine if the smallest addressable unit is 8bit, 16bit or any other power of two bit number. Would the correct terminology be to call this word-addressable? Or asked differently, is a word the size of smallest addressable unit? Or is there some other term to describe this?

Are mabye nibble, byte, word, double word all variable in bit-length and only defined by the architecture? And it is therefore only coincidence that a byte is always 8 bit? E.g. someone could design some new CPU and memory type and define her byte to be 16bit?

Main question: What is the precise term for the smallest addressable memory block?

Side question: What is the antonym to this word I'm looking for (e.g. used in NAND-flash)? Page-addressable, block-addressable? Are both correct or is one inprecise?


texts: How to improve convergence to an equilibrium value, & damp oscillation?

texts:
I am developing a program which seeks strategies for the players A, B in any of a family of simple 2-player gambling-games. The program iterates, using a genetic algorithm to determine, from the current iteration's results, the strategies which are to play one another in the next iteration.

Below I give an overview of my algorithm. Although I've used pseudocode, I am not asking about how to code an algorithm; rather, I would like to learn what the algorithm should contain.

main
{
    Strategy A[], B[];
    input nIters, nStrats, maxTweak, gameRules;

    A := nStrats random strategies;
    B := nStrats random strategies;
    for(t=1..nIters)
    {
        make each A play each B;
        for each A and each B
            its total score := sum of its scores in its individual games;
        sort the A's by total score;
        sort the B's by total score;
        v := the game's bias in favour of the best A;
        write v;
        evolveStrategies(A, nStrats, maxTweak);
        evolveStrategies(B, nStrats, maxTweak);
    }
}

evolveStrategies(X, nStrats, maxTweak)
{
    keep the best few Xs where they are;
    for(each of the others X[i])
    {
        j := index of one of the best Xs;
        X[i] := X[j];
        tweak the value of each parameter of X[i] by no more than maxTweak;
    }
}

The nature of the game is that there is (with best play by A and B) a bias (positive or negative) in favour of A. Its value $V$ is what it is when A's and B's strategies are those at a Nash equilibrium. Let $v$ be my program's estimate of $V$. Ideally my iterations' successive values of $v$ would converge to $V$. For some games in the relevant family, I happen to know what $V$ is; for others, I don't.

The trouble I find is that even if maxTweak is very small, the succession of $v$-values written shows oscillation with an amplitude much larger than maxTweak. Choosing a suitably large number of iterations shows that the oscillation, after an initial large rise and fall, is hardly damped if at all. For example on a simple game, maxTweak=$4\times10^{-6}$ gives an initial large rise and fall, then oscillation with amplitude, peak to peak, $\approx 0.2$ and period $\approx 500000$ iterations.

One solution is to reduce maxTweak. But this entails using many more iterations, and thus more CPU time. A more radical change to my approach is needed.

Given that, a priori, the program does not know the oscillation's period or the limit value, how can my program detect the oscillation and deal with it (e.g. damp it)?

If $v$ varied as undamped simple harmonic motion, plus a constant, then $\frac{dv}{dt}$ varies as undamped simple harmonic motion about 0, so $\frac{d^3 v}{dt^3} \propto -\frac{dv}{dt}$. Since the tweaking is random, there will be small-scale oscillations due to that, as well as the larger-scale oscillation. So it seems that attempts to find higher-order derivatives of $v$ as a function of $t$ will fail.

I tried estimating the first and second derivatives $\frac{dv}{dt}$ and $\frac{d^2 v}{dt^2}$ by maintaining exponentially-weighted averages of $v$ and my estimate of $\frac{dv}{dt}$. Based on the sign of my estimate of $\frac{d^2 v}{dt^2}$ I evolved just A or B. This increased the number of iterations during $v$'s initial large rise and fall, but the following oscillation was as large and undamped as before.

One idea is to start maxTweak at a value which is not small, and adaptively reduce it. But in deciding (at each iteration) whether to reduce it or not, what should I be looking for?


texts: Adding $\Theta$ notations in a recursive setting

texts:
I know the fact that if we have two functions $f$ and $g$ it is valid to say that:
$$ \Theta( f(n) + g(n)) = \Theta( \max\{f(n), g(n)\})$$
My question is if this is valid when $g$ is not a separate function, but also some kind of $f$?
For example, if we have:
$$f(n) = f(n-1)+f(n/3)+ f(n/9)+\dots+ f(n/3^{\log_3(n)})$$
Is it ok to say that:
$$\Theta( f(n))= \Theta(f(n-1))+\Theta(f(n/3) + f(n/9)+\dots)$$
(Note that we take theta of the first + theta of the rest)
I know adding $\Theta$s sounds weird but even some textbooks say we use this informally because this is more convenient (so disregard this non-formal writing).


texts: What are the differences and similarities between CYC and IBM Watson?

texts: From what I gathered from Wikipedia, CYC is based on set membership logic. So it would take symbols and create set membership predicates. But how is this different from IBM Watson?


texts: What is a partially computable function?

texts:
In the book Computability, Complexity, and Languages, Martin Davis writes in chapter two:

  A partial function is said to be partially computable  if it is computed by some program.

and also

  A function is said to be computable if it is both partially computable and total.

From the first definition, a partially computable function must be a partial function, but from the second definition a computable function must be partially computable and total which is a contradiction, because a function is partially computable if it is partial and a partial function can not be total at the same time!


texts: Is there any way to get "around" the halting problem?

texts:
As I understand it, one proof of the Halting Theorem is done by contradiction; we assume we have program X which can determine if any program terminates. We input program X into program X (with some modifications at the output), and we arrive at a contradiction. However, is it possible for a program Y to exist, where program Y can determine if any program (except variants of Y itself, or most loosely any finite set exceptions) halts?

If the set of exceptions must be infinite, can we have at least the set of permissible inputs be infinite itself?

Please try to keep the answers at a lower level, I know a little bit of mathematics but I am a complete layman in computer science.


texts: Proof language A= { 0^i 1^j where j>(i mod 3), j ≥0 , i≥0} is regular language

texts:
$A = \{0^i1^j \text{ where }j>(i \text{ mod }3), i \geqslant 0, j \geqslant 0\} $

I know that A is a regular language, since we can construct the DFA or the NFA, but i dont know how to construct it, Can somebody help me please? Thank you


texts: Decide whether the Language is regular {a^i b^j c^k|i ≥ 0, j ≥ 0, k ≥ 0}

texts:
how would you  prove if this language is regular/irregular?

question given:

Decide for each of the following languages whether it is regular. If so, design a DFA/NFA for recognizing it, and if not, give a formal proof(based on the Pumping Lemma).

i) {a^i b^j c^k|i ≥ 0, j ≥ 0, k ≥ 0 are three integers};

I have constructed a DFA which I believe proves the language is regular however, using the pumping lemma i.e. where the pumping length (p) = 4:
aaaabbbbcccc, and say this is split into xyz where x = aa, y = aa and z = bbbbcccc
then x(y^i)z where i = 2 -> aaaaaabbbbcccc

satisfy the conditions of the pumping lemma:

for each i >= 0, x(y^i)z ∈ A
|y| > 0
|xy| <= p

so:

when i = 2, x = aa, y = aa, z = bbbbcccc then A = aa aaaa bbbbcccc is satisfied
|y| = aa so |y| = 2 which satisfies the condition
x = aa + y = aa so |xy| = 4 which satisfies the condition

meaning the language is regular BUT if:

x = aaa, y = ab, z = bbbcccc

when i = 2, x = aaa, y = ab, z = bbbccc then A = aaa abab bbbccc which doesn't satisfy the condition as they're not in order (a then b then c) anymore.
|y| = ab so |y| = 2 which satisfies the condition.
x = aaa + y = ab so |xy| = 5 which doesn't satisfy the condition.

I could be using the Pumping Lemma completely wrong I'm confused as initially (and from my DFA) I assumed this language is regular as the number of a's doesn't depend on the number of b's and the number of c's doesn't depend on the number of b's or a's etc.

basically: I think I have proven that the language is regular with a DFA but irregular with the pumping lemma and don't know how to give a definitive answer.


texts: Pumping a Language does not imply regular

texts:
I am currently studying the pumping lemma for regular languages and I am trying to come up with an example where even if the language can be pumped it is not regular.
Which condition of the lemma should be broken such that I can find a language like that?


texts:
I'm reading Computer Organization and Design MIPS Edition 5th Edition The Hardware/Software Interface on how memory cache works. I came across the following paragraph on page 393;

The other key aspect of writes is what occurs on a write miss. We
first fetch the words of the block from memory. After the block is
fetched and placed into the cache, we can overwrite the word that
caused the miss into the cache block. We also write the word to main
memory using the full address.

I understand what a cache read miss is i.e. when the required word isn't present in the cache, but I'm having trouble understanding what a write miss is(how can we miss to write data?) and hence the subsequent paragraphs.


texts: Matching/finding mathematical plot images

texts:
I'm trying to come up with a method to match a given mathematical plot against a database of other plots. To make it more specific: plots are generated in R as PNG and might have different dimensions. The latter means that simple pixel-by-pixel matching won't work, even when resized, because text, plotting symbol, margins etc. between two versions of the same old are non-linear transformations of each other.

There's a number of good image matching algorithms available online but those assume any area in the picture is relevant, whereas with mathematical plots it's predominantly about the artifacts representing data that's being plotted.

I'm looking for pointers: is there an algorithm, paper etc. related to this task? Or maybe someone heard of a specialized DNN (which could help in identifying those most important artifacts)?

Appreciate any suggestions.


texts: Determining a minimal-state regular language $A$ such that $A \cap B = C$ given regular languages $B$ and $C$

texts:
Suppose I have a regular language $B$ and a regular language $C$ such that $C \subseteq B$.

How do I find a regular language $A$ such that $A \cap B = C$, where $A$ is represented by a DFA with as few states as possible?

I don't really know where to start looking for research on this, so even pointers to some work in this area would be appreciated.

The motivating case for this general question is building state machines to recognize certain regular expressions within UTF-8 streams, where I can rely on the UTF-8 stream being well-formed. (Or rather, my engine need not return correct values for malformed UTF-8 streams)


texts: Why exactly are Regular Languages decidable?

texts:
I am trying to revise for my exams and going through my lecture slides and recordings, my lecturer didn't really give a clear example of why Regular languages are decidable.

She mentioned that it was because Regular Languages can be represented in Finite Automata, and can be classified as a subset of regular languages. As finite automata are special kinds of Turing Machines with bounded tapes in which you don't write anything, and just gave the definition of what decidable is, which in her words are "a Language L is Turing-decidable if there exists a TM that can decides it".

I sort of what she is getting at, but it seems extremely vague and over generalised that I don't fully understand what she is saying.


texts: Prove the following language is regular?

texts:
Assume $L_1$ is a regular language, and define:
$$L = \{wcv ∈ \{a, b, c\}^* \mid |w|_a + 2|v|_b ≡ 3 \bmod 5, w, v ∈ L_1\}.$$
Show that $L$ is regular.

I first tried to prove by showing that the pumping lemma holds true, then learned that it was not a double implication and can only be used to prove languages are not regular.
Then I tried to draw an NFA, but didn't make any progress.
What's a good way to prove that a language like this is regular?


texts: Enumerate all maximal subset of a weighted knapsack

texts:
Given a knapsack $A$ composed of $(u_i, v_i)$-item where $u_i$ is the item identifier and $v_i$ is the weight of the item.

I call a maximal subset when you consider a subset $S$ of $A$ where the sum $R(S)$ over $v_i$ in this subset is less or equal than $P_{max}$ and if you try adding any item $(u_j, v_j) \in A \setminus S$ (if that's not empty) in $S$, then it'll exceed the $P_{max}$ limit, that is: $\forall (u_j, v_j) \in A \setminus S, R(S \cup \{ u_j, v_j \}) > P_{max}$.

I wrote this Python algorithm to compute such an enumeration:

def determine_available(bag, Pmax):
    return [(u, p) for (u, p) in bag if p <= Pmax]

def enumeration(bag, Pmax):
    if Pmax == 0:
        return []

    cur = []
    for v, p in determine_available(bag, Pmax):
        r = Pmax - p

        if not determine_available(bag, r):
            cur.append([v])
        else:
            for pos in enumeration(bag, r):
                cur.append([v] + pos)

    return cur

print(enumeration([(4, 20), (2, 2)], 100)) # for example.

Pseudo-code:

enumeration (bag: set of available items, Pmax)
     if Pmax = 0
     then return empty list

     current_subsets <- empty list
     for all available and usable item of identifier v, weight p
     do
          r = Pmax - p
          if enumerate(bag, r) is empty
          then add the singleton [v] as a subset in current_subsets
          else
               for all subset of enumerate(bag, r)
                  add in current_subsets: [v] + subset
     done
     return current_subsets

Unfortunately, I would like to compute only distinct solutions without removing duplicates after the enumeration. Is there any way to do this?

Bonus question: how to enumerate them in an iterative way?


texts: Unable to have an equivalent of A(FG p) and AG(EF p)

texts:
It states in my lecture notes that there is no CTL formula that is equivalent to A(FG p) in LTL and likewise, there is no LTL formula that is equivalent to CTL formula AG(EF p).

I am just starting to pick up LTL & CTL and cannot figure out why it is not possible. Could someone shed some light?

A(FG p): I would read it as 'All path will eventually globally satisfy p.

AG(EF p): For all computational states, globally, there exists a path the will eventually satisfy p.

Am I interpreting it wrongly?


texts: Question on the "Tutorial implementation of dependently typed lambda calculus"

texts:
I have a slight technical struggle with this marvelous tutorial. On page 5 the tutorial talks about typing rules for Simply Typed Lambdas and presents following judgement as derivable via rules on figure 3.
I was unable to prove neither id nor const by the same reason. Take for instance the id example.

Say I am looking on type checking rule CHK. It says that in order to check types I should first perform inference and then compare result with what I expect.
To do the inference on application, I have to use the APP rule that immediately forces me to infer the type of the left hand side of the application, namely (id :: α -> α)
To do that I am using the ANN rule that forces me to check that α -> α is a type (and I can prove it no problem). Then I got this naked id symbol and have to prove it's type to be α -> α.
Finally, here is a problem. In order to do that I will have to use var rule, which requires the type of id to be set in the context Gamma explicitly, but it is not done, therefore the proof is falling apart.


texts: Generating general term of union of two countably infinite sets

texts:
I have two sets whose general terms are given as:
$$
\begin{align*}
A &= \{2⋅n \mid n ∊ ℤ\} \\
B &= \{2⋅n + 1 \mid n ∊ ℤ\}
\end{align*}
$$
I want to find the union of these two sets and return the common term of the set, something like $\{n \mid n ∊ ℤ\}$.

I have the following questions:

Given that I can't store the entire sets, what are some efficient ways of merging these two sets?
How can I find the common term of any given sequence?
What would be some other approaches to solve this problem?

I would really appreciate if someone can share some
relevant literature or an algorithm for this question.

Note that the members of the sets need not be integers – they can be rationals too.


texts: Are there any context-free languages that are not known to be in $\mathrm{DTIME}(O(n))$?

texts:
The problem of determining, given a string $x$ and a context-free grammar $G$, whether $x \in L(G)$ is conjectured to take more than linear time in the length of $x$. Currently the best known algorithm is Valiant's which takes $\Theta(|G||x|^\omega)$.

On the other hand, for a fixed $G$ there may be a specialized recognition algorithm which is faster, and indeed linear-time algorithms have been developed for many grammars and classes of grammars of interest. In fact, I can't think of any example of a language which doesn't have a linear-time recognition algorithm.

Is there any example of a context-free language that is not known to be recognizable in linear time?


texts: Optimising buffer allocation in a shared buffer (with total max capacity)

texts:
My intention is to optimise buffer allocation in a shared buffer (with total max capacity) where each incoming and outgoing  packet  belongs to a category (we have a finite number of categories < total buffer size), and the packets are inserted and removed so that each category has a different and independent input and output rate following FIFO scheme. Also we want to minimise packet drops.

For further clarification, suppose that my total buffer size is 100, and I have categories {A, B, C}, each packet belongs to any one of these categories, and each category packet has a variable insertion and removal rate from the buffer. I want to dynamically assign an upper-limit on each category packets that the buffer can hold so throughput is maximised and packet drop is minimised. Here we cannot change the insertion rate, for removal if there exists no packet for a category A then removal request for A will do nothing but a remove(A) polling will still take place on the buffer regardless of it having a packet or not.

It would be sufficient even if I get a hint of what approach I should follow. I may not have explained my problem clearly, please comment for any further clarifications.


texts: Why can't we round results of linear programming to get integer programming?

texts:
If linear programming suggests that we need $2.5$ trucks to deliver goods, why can't we round up and say $3$ trucks are needed?
If linear programming suggests we can afford only $3.7$ workers, then why can't we just round down to $3$ workers?

When can we not use this rounding technique?


texts: Proving the given language isn't context free using Pumping Lemma

texts:
i want to prove that the following Language isn't CF

$L=\{a^kba^kba^k|k\in \mathbb{N}\}$

Let $z=a^nba^nba^n$ be a String from $L$

$n$ is the pumping length and
$|z|=3n+2 > n$

and $z=uvwxy$ with $|vx|\geqslant 1$, $|vwx|\leqslant n$

but i'm not sure how to determine the correct substrings, how should i consider  them ? I tried the ones below are thy correct ?

Case 1 :
$u=a^n,\ uwx=ba^n,\ y=ba^n$

Case 2 :
$u=a^{n-l},\ uwx=a^lb,\ y=a^nba^n$

Case 3 :
$u=a^nb,\ uwx=a^nb,\ y=a^n$

Case 4 :
$u=a^nba^{n-l},\ uwx=a^{l-k},\ y=a^kba^n$

Case 5 :
$u=a^nb,\ uwx=a^n,\ y=ba^n$


texts:
Is Merge Sort the best sorting technique to sort a linked list? Also, which sorting technique is worst for a linked list?

Merge sort uses a divide and conquer method. What makes merge sort efficient for sorting a linked list?


texts: Turing degree incomparable with any countable-ordinal jump of another Turing degree?

texts:
Among the Turing degrees are degrees of the form $0^n$, e.g. $0$, $0'$, $0''$, etc.

I'll just prove this quick for completeness' sake.  Hopefully nobody has any qualms with this short proof:

Lemma: Any countable set of sets of natural numbers can be encoded as a single set of natural numbers, such that each original set can be decoded by a Turing machine.

Proof: Let $S$ be our set of sets, so that each $S_n \in S$ is a set of natural numbers.  Define $O = \{k \cdot 2^{n+1} - 2^n | k \in S_n \}$.

Thus, $S_n = \{ k | k \cdot 2^{n+1} - 2^n \in O \}$.  Clearly, for each $S_n$ there is a Turing machine that computes $S_n$ given an oracle for $O$.

Minor Theorem: Any countable set of Turing degrees has an upper bound.

Proof: Let $D$ be our countable set of degrees.  Thus, each $D_n \in D$ is a countable set of sets of natural numbers.  Let $E_n$ be a set of natural numbers that encodes the elements of $D_n$, and let $E$ be a set of natural numbers that encodes all $E_n$.

Any set in any degree $D_n$ can be computed by decoding $E$ twice in succession, so as Turing degrees, $D_n \leq [E]$.  Therefore $[E]$ is an upper bound of $D$.

Let $0^\omega$ be the upper bound of $\{0, 0', 0'', ... \}$ as described just above.  Of course, we can take the Turing jump of $0^\omega$ to obtain $(0^\omega)'$ which we will write $0^{\omega + 1}$, and so on to obtain the countable set of Turing degrees, $0^{\omega + n}$.  Taking the upper bound of these, we obtain $0^{2 \omega}$, and of course, furthermore taking the upper bound of $\{ 0, 0^{\omega}, 0^{2 \omega}, ... \}$ we obtain the Turing degree $0^{\omega^\omega}$.  Generally for any countable ordinal $\beta$, we can define a degree $0^\beta$.

It is known that for every nonzero Turing degree $a$, there is a Turing degree $b$ with which it is incomparable.  However, for any Turing degree $a$ (and I'm particularly interested in $0'$), is there a Turing degree $b$ that is incomparable with $a^\beta$ for all countable ordinals $\beta$?


texts:
It is mentioned in Sipser's text that the complement of SAT is in $IP$, before $IP$ is formally introduced. After looking at the definition and some of the results, I still don't see why this is the case.

Is this supposed to be seen directly? Or is it easier to show that it is in $NPSPACE$, which would prove the claim since $IP = PSPACE = NPSPACE$?


texts: Creating a single layer perceptron for the OR problem

texts:
I am working on the following problem

Find the linear least squares unit weights for the `OR' problem, ie.
$v_1^T = (0,0), v_2^T = (1,0), v_3^T = (0,1), v_4^T = (1,1)$ and $u_1 = 0, u_2 = u_3 = u_4 = 1$.

Here $v$ represent inputs and $u$ outputs. For problems like this I usually find a matrix $W$ (the weights) such that $$u_i=Wv_i \quad i=1,2,3,4$$ but I think it is obvious a matrix doesn't exist. my reasoning being that the problem is equivalent to finding the matrix $W = \begin{pmatrix} x_1 & x_2 \end{pmatrix} $ such that $$\begin{pmatrix} 0 & 1 & 1 & 1 \end{pmatrix} = \begin{pmatrix} x_1 & x_2 \end{pmatrix} \begin{pmatrix} 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \end{pmatrix}$$ And looking at the two middle columns of the left vector and right matrix we must have $x_1=x_2 =1$ but then we get $1 + 1 = 1$, a contradiction.

In a unit perceptron a function may be applied to the output, and a step function $$f(x) \begin{cases}
0 & x \leq 0 \\
1 & x > 0
\end{cases}$$ would work here.

My question here is, is this correct? I wasn't quite sure if I am answering the right question. I am pretty sure $u_i = f(Wv_i)$ but I am not too familiar with what is meant by "linear least squares unit weights" in this context?


texts:
Assume that for each building in a city there is a known subset of the city's buildings that can be seen from that building (being in a building counts as "seeing a building" as well so for every building you can see at least one building, the building you are in).

Develop an efficient algorithm for visiting the minimum number of buildings given a list of buildings you want to see.

More specifically assume you have a list of all buildings in a city with a list of all buildings you can see from each building:

{ 1: [1, 2], 2: [2], 3: [3, 1] }

And you then want to implement a function like:

seeBuildings([1,2]) -> [1] (list of buildings to visit)

How can this be efficiently implemented when the number of buildings is large (~10,000) and the number of buildings visible from a given building can vary from between 1 (only see self) and 30?

Is there some data structure that can be precomputed then saved so searches are cheap thereafter?


texts: Is summing over all possible $k$-combinations NP-hard?

texts:
Say we have a set of numbers $A=\{a_1, a_2, \dots, a_n\}$, and we wish to sum over all possible combinations of $k$ terms to compute

$$
\sum_{\substack{C \subseteq \{1,2,\dots,n\} \\ |C|=k}} \prod_{c \in C} a_c
$$

Naively this requires $O(k\binom{n}{k})$ operations.

This is different from from computing the permanent where there are permutations.

Is this problem known to be NP-hard when $n=2k$ or other conditions such as $n=\Theta(k^2)$?


texts: Describe a turing machine that accepts Language L = {www| w is {a,b}*}

texts: I know that for the language ww, the TM can zig zag across the tape and match symbols to see if the strings are equivalent by first finding the midpoint of the string. However I am lost on how the TM can find out where in www the repeated strings start and stop. I can find midpoint but how do I get one third or two thirds of the string. Any tips to get me started?


texts: Question about a semi-decidable property of languages

texts:
Consider the following property of recursively enumberable (RE) languages

$$ L = \{ J \in \text{RE} \mid J \cap L_{uni} \ne \emptyset \}$$

where $L_{uni}$ is the language of the Universal Turing machine.

I am wondering if $L$ is semi-decidable. That is (by definition) if the set $$ S = \{ \langle T \rangle \mid L(T) \in L\}$$ is recursively enumerable.

If I am not mistaken then this should be true because one can always construct a Turing machine $M$ that accepts a code $\langle T \rangle$ and  (using non-determinism) generates the "right" input for $T$ and $T_{uni}$, verifies that both accept the generated word (simulating the machines) and if so accepts the supplied string.

Can someone verify this claim?


texts: Is there an online/offline tool that can perform K-means/median, given an initial centroid from the user?

texts:
The types of problems I am trying to solve are as follows:
Given a set of co-ordinates such as: (1,2), (3,3), (6,2), (7,1), a value of k such as k=3 and an initial set of centroids such as c1=(2,2) and c2=(5,4), perform the k-means/median algorithm.
Now, with samples that small, I can easily work it out on paper. However, if I have 200 co-ordinates to start with and 10 centroids, it starts to get a lot more tricky.
I have already found this calculator: https://scistatcalc.blogspot.com/2014/01/k-means-clustering-calculator.html and several others which serve a similar function. I have also found python code doing similar operations. However, all these tools initialize centroids randomly or using k-means++. I, on the other hand, want to initialize the centroids manually.
Is there an online/offline tool/code/platform that can achieve this?


texts: Minimizing the length a Boolean Algebra Expression in disjunctive normal form

texts:
I'm looking to minimize the length of an expression in boolean algebra that has been given in disjunctive normal form and is free from redundancy. To remove redundancy from the original expression I have applied the Espresso Hueristic Logic Minimizer as implemented through the PyEDA library. Now, I would like to express this formula in such a way that the expression length is minimal.
The way I had thought to do this is to divide the expression into subexpressions and convert these subexpressions into either conjunctive or disjunctive normal form based on some heuristic (e.g. a greedy algorithm which selects the minimum length subexpression at each check). However, it appears to me that checking each subexpression will lead to exponential time complexity.
Are there any ideas as to how I might approach this? I believe that the problem is suited to the application of reinforcement learning.


texts:
Consider 3COL (three colourability), Travelling Salesman, 3SAT and 2SAT. Which of these problems can be solved in polynomial time if we happen to live in world 3 (Pessiland).

My Thinking - We know that 2SAT is a P problem and so we can solve it in polynomial time even though we are in Pessiland however I am unsure on what the implications are for 3COL, travelling salesman and 3sat!

5 Worlds I refer to - http://blog.computationalcomplexity.org/2004/06/impagliazzos-five-worlds.html


texts: Are there lambda-calculus functions which always output booleans, but are not constant functions?

texts:
In labmda calculus, true = $\lambda x,y.x$ and false = $\lambda x,y.y$.

Is there a term $f$ such that for any other term $x$, $f x$ normalizes to true or false BUT $f$ does not have the same output for all inputs?


texts: Alternative to Bloom filter for extreme parameters

texts:
A Bloom filter is a space-efficient probabilistic data structure to perform membership-tests on a set (see Wikipedia's page for a definition; I use the same notations below).

I am interested in a special application where the number of bits per element $m/n$ is very low, with typically $m<n$ (this results in a very compact set, but of course the price to pay is a lot of false positives).

An issue I run into is that the optimal number of hash functions $k$ is set to be $k^* = \frac m n \log 2$, which is clearly $<1$ when $m<n$. So there is no choice but to use a single hash function, which results in a suboptimal false positive rate of:
$$\tilde{p} = 1 - e^{-n/m},$$
instead of the more typical
$$p = e^{-m/n (\log 2)^2}.$$

This is suboptimal because the false positive rate is "higher than normal", and it has the effect of predominantly filling the bit vector with ones.

My question is the following: since bloom filters were evidently not designed to be used with such parameters (although technically they still work OK), is there an alternative that would be more efficient ?

Note that I am OK with other limitations of bloom filters (e.g. no deletion possible, false positives, etc.) and that $m/n$ is typically less than $1$ in my case.

Edit: So I came up with some sort of solution, although I still feel there must be something better.

The idea is to have a bloom filter with $k^* = 1$ for a part of the input, and then just output "yes" for any other input. Let's say that you want $m = c n$ with some small $c < 1$.

In the bloom filter (which takes the whole memory space $m$), we have $n_{\text{bf}} = m \log 2 = c n \log 2$, and a probability of false positive of $1/2$ (this is $p = e^{-m/n (\log 2)^2}$ from above instantiated to $k^* = 1$). Indeed, the resulting vector will be on average half ones, half zeroes.

For the rest of the input, that is $n_{\text{rest}} = n - n_{\text{bf}} = n (1 - c \log 2)$, we have a probability of false positive of $1$.

So on average, we have an aggregate
$$p_{\text{partial bf}} = c \log(2)/2 + (1-c \log 2) = 1 - c\log(2)/2.$$

This looks better than $\tilde p$ but worse than $p$ (obviously) on (a part of) the area of interest. Here is a graphical comparison.

The rationale behind choosing $k^* = 1$ is that we choose the bloom filter to be as "dense" as we can afford, if that makes sense. A different choice for $k$ leads to worse results (at least for $0 < m < n$).


texts: Could a modification of Krom's proof system be used to solve 3-SAT in polynomial time?

texts:
A literal is a nonzero integer, and we define $\sim x = -x$.
A clause is a nonempty set of literals.
A CNF is a set of clauses.
A K-rule is a pair $(F,C)$ where $F$ is a CNF and $C$ is a clause.
A Krom-style proof system (KPS) is a set of K-rules.
If $S$ is a KPS, then an $S$-proof of $C$ from $F$, or an $(S,F)$-proof of $C$, is a sequence $\langle C_1,..,C_n\rangle$ of clauses such that $C = C_n$ and for all $1\le i\le n$, either $C_i \in F$ or there is a K-rule $R = (G,A) \in S$ and a function $f : \{x,\sim x : x \in B \in G \lor x \in A\} \rightarrow \mathbb{Z}_{\ne 0}$ which respects negation such that letting $g(B) := \{f(a) : a ∈ B\}$, we have $C_i = g(A)$, and for all $B \in G$, there exists some $j < i$ with $C_j = g(B)$.
For fixed $S$, the language $\{(F,C) : F \vdash_S C\}$ is polynomial-time decidable:

read inputs F and C
if C ∈ F
    return true
let D = {x1,~x1,..,xn,~xn} be the set of literals occuring in F or C, and their negations
Contin := true
while Contin
    Contin ← false
    for (G,A) in S
        for h : {abs(x) : x ∈ B ∈ G ∨ x ∈ A} -> D # there are |D|^c such functions
            f(x) := (x > 0 ? h(x) : -h(-x))
            g(B) := {f(a) : a ∈ B}
            for B in G
                if g(B) ∉ G
                    continue in the for-loop where h is chosen
            if g(A) ∉ F
                push g(A) to F
                Contin ← true
if C ∈ F
    return true
else
    return false

$S$ is sound if for all CNF's $F$ and clauses $C$, the existence of an $(S,F)$-proof of $C$ implies that $F \vDash C$.
$S$ is complete for a class $\Gamma$ of CNF's if for all $F \in \Gamma$ and $C$, if $F \vDash C$ then $C$ is $(S,F)$-provable.
No KPS is complete for full $SAT$, since any clause of the form $\{-1,1,2,3,..,n\}$ is tautological, but for any system $S$, $sup\{|A|  : (\emptyset,A) \in S\}$ is only finite, making the clause $(S,\emptyset)$-unprovable for sufficiently large $n$.
$\{(\{\{1\},\{-1\}\},\{2\})\}$ is complete for $1$-$SAT$, and represents the rule $a,\sim a \vdash b$.
$\{(\emptyset,\{1,-1\}),(\{\{1\}\},\{1,2\}),(\{\{1,2\},\{-1,3\}\},\{2,3\})\}$ is complete for $2$-$SAT$, and represents the system consisting of the rules (1) $\vdash a\lor\sim a$, (2) $a\lor a \vdash a\lor b$, and (3) $a\lor b, \sim a\lor c \vdash b\lor c$.
Question 1. Is it known that no sound KPS can be complete for $3$-$SAT$?
If such a KPS was found, it would imply $P=NP$ and the polynomial-boundedness of natural propositional proof systems.
I am particularly interested in the completeness of the system $S_3 = \{(\emptyset,\{1,-1,2\}),(\{\{1,2,3\},\{1,2,4\},\{-3,-4,5\}\},\{1,2,5\})\}$ for $3$-$SAT$, where the main rule corresponds to the fact that if $a \land b \Rightarrow c$, $a \land b \Rightarrow d$, and $c\land d\Rightarrow e$, then $a\land b\Rightarrow e$.
Question 2. Can $S_3$ be shown to be complete for $3$-$SAT$, or at least some restricted class thereof such as $Horn$-$SAT\cap 3$-$CNF$ or the pigeonhole principle?
An $(S,F,d)$-proof is the same as an $(S,F)$-proof $\langle C_1,..,C_n\rangle$, except that we have a function $h : \{1,..,n\} \rightarrow \{0,..,d\}$, and the last part of the old definition, namely "$C_j = g(B)$", is strengthened by additionally requiring that $h(j) < h(i)$.
So far, I have been able to show that if $\langle C_1,..,C_n,C_{n+1}\rangle$ is an $(S_3,F\cup \{\{a,b,c\}\})$-proof of $C_{n+1} = \{d,e,f\}$ with $C_1,..,C_n \in F$, then for $x=a,b,c$ there exists an $(S_3,F\cup\{ \{\sim d\}, \{\sim e\}, \{\sim f\}\},5)$-proof $\langle D_1,..,D_{23}\rangle$ of $\{\sim x\}$.
However, the algorithm given above takes $O(n^8)$ steps on the RAM model of computation in the case of $S_3$. Krom's original algorithm for 2-SAT had a running time of $O(n^3)$, but this upper bound has since been improved to $O(n)$, even if we want to find a satisfying assignment when one exists.
Question 3. How quickly can we solve the $S_3$-provability problem? If this system happens to be complete for $3$-$SAT$, how quickly can we find satisfying assignments to consistent formulae?


texts:
We define a regular tree language as in the book TATA: It is the set of trees accepted by a non-deterministic finite tree automaton (Chapter 1) or, equivalently, the set of trees generated by a regular tree grammar (Chapter 2). Both formalisms hold close resemblances to the well-known string analogues.

  Is there a regular tree language in which the average height of a tree of size $n$ is neither $\Theta(n)$ nor $\Theta(\sqrt{n})$?

Obviously there are tree languages such that the height of a tree is linear in its size; and in the book Analytic Combinatorics it is shown e.g. that binary trees of size $n$ have average height $2\sqrt{ \pi n}$. If I understand Proposition VII.16 (p.537) of the mentioned book correctly, then there is a wide subset of regular tree languages that have average height of $\Theta(\sqrt{n})$, namely those in which the tree language is also a simple variety of trees fulfilling some extra conditions.

So I was wondering whether there is a regular tree language showing a different average height or if there is a true dichotomy for regular tree languages.


texts: Construct a Deterministic Pushdown Automaton for unequal number of elements

texts:
Can anyone help me construct a deterministic PDA for the following language:

$$L=\{w\in(a,b)^* \mid \#_a(w)\neq \#_b(w)\}$$

Or can anyone check if the following solution is correct?


texts: The most efficient algorithm to distribute items?

texts:
I am trying to design an algorithm that would help me distribute in this example case, 'students' to different exam rooms.

All the constraints for this Theoretical problem would be:

[1]"One student can only be at the exam room at a specific time "... meaning that only one student can give an exam in one of the rooms. No two students can share a room even if their exam starting times is exactly same.

[2]The number of rooms used has to remain a minimum.

[3] We could imagine that there are unlimited number of rooms that are available for use.

As inputs I only have the (sorted) exam starting times for students.

Can anyone suggest an algorithm which would always keep the number of "rooms used" to a minimum?

[Note: Multiple students may have the same exact starting times.]


texts: If L is regular language then each equivalence class is also regular?

texts:
L is a regular language. Let's say that E is one of L's equivalence classes - is it true/false that E is also regular?

The equivalence relation is, from Wikipedia: "Given a language L, and a pair of strings x and y, define a distinguishing extension to be a string z such that exactly one of the two strings xz and yz belongs to L. Define a relation RL on strings by the rule that x RL y if there is no distinguishing extension for x and y."


texts:
Let's denote a total increasing computable function $f: \mathbb{N} \rightarrow \mathbb{N}$. How to prove that the plot of $f$ is a decidable subset of $ \mathbb{N} \times \mathbb{N}$?

My solution:
1) First of all, we consider a plot as a $X \times Y = \{ (x, y) | x, y \in X, Y \} \subset \mathbb{N} \times \mathbb{N} $. We know, if the function in monotone and total, it's actually bijective.
So, my algorithm looks like this: we receive a pair $(a, b)$ and we want to check, if it belongs to $X \times Y$. So, we just calculate $f(a)$: if $f(a)=b$, we print 1, else we print 0.

Could someone tell me, for what purpose the condition of the function's
monotonicity was added?