texts:
Let $G=(V,E)$ which is undirected and simple. We also have $T$, an MST of $G$. We add a vertex $v$ to the graph and connect it with weighted edges to some of the vertices. Find a new MST for the new graph in $O(|V|\cdot \log |V|)$.

Basically, the idea is using Prim algorithm, only putting in priority-queue the edges of $T$ plus the new edges.

I don't fully understand the reason it works. Why it has to be a minimum spanning tree? What about a case where the heaviest edge in $T$ is $9$ for example, and we have other edges in the graph (And not in $T$) with the same weight?

It was also claimed that $|V|-1$ of the edges must be from the old graph and the other one will be one of the new - I'm not sure it's even correct. What do you think?


texts: Which implementation for the Maclaurin Series for the cosine function is better?

texts:
First, sorry if this post is off-topic. I consider it too analytic for stack overflow.

  In Numerical Analysis subject I must explain which one is better (has less error).
  The recursive implementation seems to be better with the inputs I have used, but I don't know the reason.

  Can someone explain to me which one is better and why? Having in mind round-off error and loss of significance using doubles.

Iterative implementation:

$$\cos{x} = 1 - \frac{x^2}{2!} + \frac{x^4}{4!} - \frac{x^6}{6!} + \ ... \ + (-1)^n\frac{x^{2n}}{(2n)!}$$

Recursive implementation:

$$y_{n+1} = (-1)^n$$
$$y_{k} = \frac{y_{k+1}x^2}{(2k)(2k-1)} + (-1)^{k-1}, \  \text{for} \  k=n,\ n-1,\ n-2,\ ... \ 1$$


texts: Confusion converting BNF to regular expression

texts:
I have a Computer Science A-Level exam tomorrow and I've been trying to get this question answered by my teacher but she's not been too helpful so asking here instead.

In an exam question, I have the following BNF grammar, where _ denotes a space.

<fullname> ::= <title>_<name>_<endtitle> |
               <name> |
               <title>_<name> |
               <name>_<endtitle>

<title> ::= MRS | MS | ... | SIR

<endtitle> ::= ESQUIRE | OBE | CBE

<name> ::= <word> |
           <name>_<word>

<word> ::= <char><word>

<char> ::= A | B | ... | Z

The mark scheme says that the first rule, fullname, can be represented with a regular expression. But I'm not really sure how you could represent it with a regular expression when it's made up of other rules that can't be represented by regular expressions themselves e.g. name which is recursive. Also I thought regular expressions were made up of just letters and symbols e.g. a*b? . Forgive me if I don't seem too knowledgable on this because the resources we have for the A-Level are pretty awful.


texts: Do functions with slower growth than inverse Ackermann appear in runtime bounds?

texts:
Some complicated algorithms (union-find) have the nearly-constant inverse Ackermann function that appears in the asymptotic time complexity, and are worst-case time optimal if the nearly constant inverse Ackermann term is ignored.

Are there any examples of known algorithms with running times that involve functions that grow fundamentally slower than inverse Ackermann (e.g. inverses of functions that are not equivalent to Ackermann under polynomial or exponential etc. transformations), that give the best-known worst-case time complexity for solving the underlying problem?


texts: What are some concrete (near-)"worst-case" examples of subset-sum?

texts:
I've written a subset-sum solver. It outputs all subsets that sum to a given value, iteratively.
I'm measuring its performance by the average amount of time taken per subset found.

However, I suspect it may be faster than existing solvers in "near-worst" cases, but I don't know how to check this.
What are some concrete examples of near-worst-case subset-sum problems I can try it on?

Note that I'm looking for reasonable examples here (< 64 bits -- i.e., numbers that actually pop up in the real world), not, for example, an instance with 500 digits. I'm looking for reasonable examples here. The idea is that I'm trying to solve real-world subset-sum problems well in "hard" cases.


texts: Minimal DFA with more states than its equivalent NFA

texts:
I understand that using a bad case for subset construction as provided through an example in the book -  Introduction to Automata Theory, Languages and Computation, we can definitely have an NFA with $n+1$ states, and get a corresponding minimal DFA with $2^n$ states due to the power set logic.

But, my question is, is there a case where you can have an NFA  (with or without epsilon moves), with $n$ states, having an equivalent minimal DFA of $p$ states, where $p \neq 2^n \ and \ p > 2n$ ?


texts: Finding the upper bound of the length of a closed walk

texts:
I am having trouble understanding a part of the proof of Lemma 2 (Page 184).

It says the length of the tour is $$ \leq  \lceil n^{1/2} \rceil + \triangle(n + \lceil n^{1/2} \rceil) + \sqrt{2} $$ I don't understand how they came up with this inequality. I can understand where the $\sqrt{2} $ comes from, since we have to travel from the final point to the initial point and that is the length of the diagonal. As for the rest, to me somehow it seems that the inequality should be $$ <(\triangle + 1)(n + \lceil n^{1/2} \rceil) + \sqrt{2}$$, where I have used the triangle inequality.

I am having also a hard time simplifying my inequality to something along the lines $c \sqrt{n} $ where $c>0$ whereas the one given in the proof is easier to manipulate.


texts: looking for counterexample for my algorithm for maximum independent set in Bipartite Graph

texts:
We wish to find the maximum independent set in a bipartite graph. My intuition led me to the following algorithm. (Assume that the bipartite graph is connected and has at least 3 vertices, if not run the algorithm on each component)

Given $G=(L,R,E)$
Let $S$ be the set of vertices with degree $1$. Note that since graph is connected and has at least $3$ vertices, $v,u\in S\implies (v,u)\not \in E$. (If $S$ is empty, go to step $5$)
Add the vertices in $S$ to the independent set. $\forall s\in S$, remove $s$ and neighborhood of $s$ from $G$
If the graph is connected, repeat steps $2-4$. If it is disconnected, repeat the steps $2-4$ for each component.
if $|L| > |R|$, add $L$ to the independent set, else add $R$

Obviously, the output is some independent set, not necessarily the maximum. However, I could neither prove nor come up with an counter example. Any help will be appreciated.
https://cs.stackexchange.com/a/3033 has a answer which does not rely on intuition


texts: Implementing supplies in Coin change problem

texts:
I started an algorithm course in C two months ago, for the last weeks I've been trying to solve this problem , i ran out of time but I cannot find an acceptable solution. Basically It's a coin change problem, Given a sum (S) I need to find (and print) the combination that uses the least amount of coins, I can only use coins that are available. For example:
INPUT: S=10 Coins={2,3,4,5} Supply={1,3,1,0} OUTPUT: 3 3 4

I've been able to solve the normal coin change problem but I can't seem to find a way to manage supplies so that the program doesn't use a coin when its supply=0.


texts: Similarities and differences in major process algebras

texts:
To my knowledge, there are three major process algebras that have inspired a vast range of research into formal models of concurrency. These are:

CCS and $\pi$-calculus both by Robin Milner
CSP by Tony Hoare and
ACP by Jan Bergstra and Jan Willem Klop

All three seem to have to this day a quite active following and vast amounts of research has been done on them.

  What are the key similarities and differences of these approaches?
  Why has research in process algebra diverged instead of converged, in the sense that there is no one universal model to unify the field?


texts:
The following O(n^2) sorting algorithm works but I can't figure out why.

array a // length n, indexed 0 to n-1

for ( i = 0; i < n; i++)
   for ( j = 0; j < n; j++)
       if(a[i]<=a[j])
            swap(a[i],a[j]);

It seems it is not bubble sort as after a single iteration neither the minimum or maximum is in place. (And also it needs n^2 comparisons instead of n*(n-1)/2)

How would you prove this algorithm sorts ? How is this sort algorithm called?

An execution of the sort for the example :

initial target
194600925
592040703
20865352
814014281
792862803

target after iteration 0
814014281
194600925
20865352
592040703
792862803

target after iteration 1
194600925
814014281
20865352
592040703
792862803

target after iteration 2
20865352
194600925
814014281
592040703
792862803

target after iteration 3
20865352
194600925
592040703
814014281
792862803

target after iteration 4
20865352
194600925
592040703
792862803
814014281


texts: Parallel Floyd-Warshall algorithm in Assembler - possible?

texts:
I want to implement parallel Floyd-Warshall algorithm in assembler.
The FW algorithm is all about if and assign statements executed in an inner-most loop:
# D is an adjacency matrix of size n x n
for k : n
  for i : n
    for j : n
      if (D[i, j] > D[i, k] + D[k, j])
        D[i, j] := D[i, k] + D[k, j]

I want to achieve simple parallelization on the assembly level, by unrolling the inner-most (index with j) loop. For example, I can assume that the graph is of some size 4n and in the inner-most loop I can do j += 4 instead of j++.

My question: will this parallelization work?
In my opinion, this should work if all the assignments performed within one full inner-most loop cycle are independent. Full inner-most loop cycle means k = const, i = const, j = changes, whereas independent means that the order of iteration over j loop does not matter (and hence: order of assignment).

I have prepared a simple visualization of full middle loop cycle for an adjacency matrix of size 4 x 4, for k = 2.

Before I start with the implementation I wanted to make sure that it will actually work. :)


texts:
A similar question has been asked here, but this one is more complicated and has more constraints.

I'm trying to find an algorithm to solve the following (real-life) problem:

A customer has $M$ amount of money each month that he wants to invest according to her preferred asset allocation.
Example

60% stocks
20% bonds
20% REITs

She has a list of "favourite" financial instruments and a preferred allocation in each of the asset classes, e.g.:

Stocks: C (60%) and AAPL (40%)
Bonds: AGG (70%) and LQD (30%)
REITs: VNQI (100%)

Now, the algorithm would provide an investment advice (how many units and what financial instruments to buy) according to the following constraints:

Total sum of purchases with fees cannot exceed $M$ (amount of money).
Units are integer and indivisible, you can buy either one or two stocks but not 1.5. Since the customer ivests small(-ish) sums, this constraint becomes important. Example: $M$ is \$500 and AAPL is \$173 per unit!
Main goal is fee minimisation (again, since the sum invested is not large, fees become relatively large). Instruments have different fees that not flat-rate. E.g.: fees for buying C are "\$1 if transaction sum is <\$100, 0.30% otherwise", but for VNQI they're "\$10 if sum < \$2000, 0.40% otherwise".
Second goal is allocation that is approximately close to the "model allocation" above. Note that the model is concerned with asset classes, not individual instruments. That means the customer can buy only C or only AAPLto attain the desired 60% in Stocks. However, remember that there's also a preferred allocation within an asset class; if we decide not to buy C this month, then we'll need buy more of it next time to keep the stocks in balance.
Fee minimisation can be attained by limiting the number of transactions. That means we can decide to buy, e.g., C, AGG and VNQI only, and think about buying AAPL and LQD next month. We can go even further and decide not to buy a whole asset class at all if the first solution has fees that are too high (above some pre-determined limit). In that case we'll remember that decision and buy more of it next month.

Now, I've been thinking about this for some time; I had my CS lessons over fifteen years ago, so had to rack my brain :)
My first thought was of Bin packing problem. Nah. Doesn't really fit.
Then I remembered about Multi-dimensional unbounded knapsack. Again, not what I was looking for.
Considered Quadratic programming and Dantzig's simplex algorithm for linear programming. Not exactly fitting...

Maybe there is a special algorithm / special case for this kind of problem? Or shall I invent a new one? :)


texts: Turing Machine that both halts and loops in NP

texts:
This is in regards to a specific TM:

$UNIQUE: \{$ TM | TM loops on at least an input, and TM also halts on at least one input $\}$

This is a play on the Halting Problem, where it basically combines $HP$ as well as $\overline{HP}$ into one. We know that $HP$ is NP-Hard, we also know that $\overline{HP}$ is NP-Hard, but would combining the two also be NP-Hard? How would the proof for this go?


texts: How to do a reverse topological sort using depth first search?

texts:
I'm doing a replacement for the venerable make utility that will support, among other things, automatic cleaning. The utility figures out automatically what files and directories are targets, and then deletes those, if the user wishes to do a clean operation. However, a file may reside in an automatically created directory, meaning I should do a topological sort for the targets, where every file has an arc towards the parent directory, and every directory has an arc towards its parent. So, for example:

objhierarchy/obj/foo.o has an arc towards objhierarchy/obj
objhierarchy/obj has an arc towards objhierarchy

What complicates the things is that the files need to be deleted in the reverse order. So, in the example given, you need this order: (1) objhierarchy/obj/foo.o, (2) objhierarchy/obj, (3) objhierarchy.

Topological sort seems like a good solution, but it gives the opposite order. So, a topological sort of the directory parent graph would yield (1) objhierarchy, (2) objhierarchy/obj, (3) objhierarchy/obj/foo.o.

A solution could be a buffer of pointers that is reversed in-place (or just iterated in the reverse order), but I would like to avoid allocating extra memory.

What is the best way to get the files deleted in the reverse order? Can the topological sort algorithm based on depth first search be modified to call some callback function in a reverse order?


texts: Construct a PDA that recognizes $L = \{w : w \neq a^n b^n : n ≥ 0\}$

texts:
I'm trying to find the PDA of the above language. I understand that this is the complement of the language
$L_1=\{w : w=a^nb^n : n\geq0\}$
However, I can't understand the idea behind constructing the PDA. Even if I construct the PDA for $L_1$, and convert the non-accepting states to accepting states and vice-versa, the resulting PDA will still not accept all strings belonging to $L$. Any help is appreciated in this regard.


texts: Is there a simple way of calculating perceptron weights based on a classification graph?

texts:
I am studying for an AI exam and I'm looking for a better way of solving the following problem:

  Graph shows a classification problem in the unit square $[0,1]^2$, where Class A
  is denoted by the grey area in the figure (not including the points on the dotted lines),
  and Class B occurs otherwise.

To solve this problem, there is a need of constructing 2 perceptrons: both perceptrons output 1 if the input lies in the grey area, and at least one of the perceptrons outputs 0 otherwise.

There are 3 ways of finding appropriate weights for inputs and biases that I know of:

Trial and error
Perceptron learning algorithm (involving random weights, learning rate, multiple epochs)
Geometrical way of finding the vectors of weights (involving finding an orthogonal line to boundary function)

All of them are quite time consuming when you do it with just pen and paper.

Is there a simple way of calculating/finding perceptron weights based on a classification graph?


texts: Time-complexity of recursive defined code

texts:
How would I set up a recursive formula for time-complexity for this code:

int b(int n, int x) {
    int erg = x;
    if (n>1) {
        for (int i = 1; i <= n; i++) {
           erg = erg+i;
        }
        for (int k=0; k<3; k++) {
           erg = erg + b(n/3,erg/9);
        }
    }
    return erg;
}

Is my assumption correct, that it would be something like this? $$T(n)=n(T(\tfrac{n}{3})+n)$$

But how to deal with the if statement and the second for loop, since it is independent of $n$?


texts: Importance of recursion in computability theory

texts: It is said that computability theory is also called recursion theory. Why is it called like that? Why recursion has this much importance?


texts: Finding a solution to the following conditions?

texts:
So for these 5 conditions, I am trying to find the solution/formula for them.
What would $a_n$ equal basically? If it helps, the recurrence relation these 5 conditions were generated from was $a_n = a_{n - 1} + 2n$.   Any help would be greatly appreciated.

$$
\begin{align*}
a_0 &= 4 \\
a_1 &=  6 \\
a_2 &= 10 \\
a_3 &= 16 \\
a_4 &= 24
\end{align*}
$$


texts: Worst runtime of Delaunay triangulation algorithm

texts: I am a math major without a strong background in theoretical computer science and I have to show that the worst case running time of the Delaunay algorithm is $O(n^2)$, when I know that the expected runtime is $O(n\log n)$. Can someone help me with this?


texts: What equivalence relation does this algorithm produce for an cyclic directed graph with labeled edges?

texts:
I have a directed graph, which can be cyclic, where each node contains a value.

Nodes are not labeled, and different nodes can contain the same value.

The outgoing edges of a node are ordered, or labeled, (1, 2, 3, ... N), where N is the number of outgoing edges from the node.  (That is, it's a k-ary tree, if such a term can be used for a cyclic structure).

For each node in the graph, I produce a description of that node using the algorithm below.  Nodes are considered the "same" (equivalent) if they end up having the same description.

My motivation is that I'd like to produce a hash value from the description which will be the same for nodes where their value and the subgraph reachable from the node are (recursively) the same... however, if the descriptions are the same, the hash will be the same, so we don't need to worry about the hash.

I describe the data structure reachable from the node in this simple way:

Number the nodes in the subgraph reachable from the node, which I can do in a specific order (such as breadth-first, ignoring nodes already numbered) because the outgoing edges of a node are labeled.
Describe the subgraph reachable from the node by listing the nodes in the subgraph in order by the assigned number, and for each node in the list include in the hash the node's value and for each outgoing edge for the node (in label order), include the number assigned to the tail node of the edge.

For example, for a tree with nodes containing values A, B, C, and D:

I calculate describe A by assigning 0, 1, 2, 3 to the nodes containing A, B, C, D, and describe the values and edges this way:

0: A [1 2 3]
1: B []
2: C [0]
3: D []

Note in particular the outgoing edges from the node containing "A" are ordered (B, C, D), which makes this a unique description of the subgraph (which it wouldn't be if edges were unordered).

And similarly, to calculate the description for C:

0: C [1]
1: A [2 0 3]
2: B []
3: D []

As another example:

both nodes get the same description, because the algorithm produces the same description when run for each node.

Now, I'm assuming I haven't just solved the isomorphism problem for labeled graphs ;-)

Thus I'm guessing this algorithm describes some special case of graph isomorphism easier to solve than the general problem... or, it's not a solution to graph isomorphism because we're comparing nodes not graphs... or the algorithm is flawed doesn't produce the result I think it does! :-)

But I don't know enough computer science to be able to tell which nodes exactly would be characterized as the "same" or "different" by this algorithm.

It might be that different nodes (different in the usual way that you'd typically characterize the isomorphism of labeled graphs) are nonetheless "close enough" for my purposes that I don't mind that they get the same description.

And, if this simple algorithm does produce the result I want, I'd be eager to know if a more efficient algorithm exists.  But I can't ask that question without being able to specify what the simple algorithm does do.

Or, if I did understand what equivalence relation the algorithm produced, I might see that the algorithm was indeed flawed for my purposes.

Can you help?


texts: Reason for differences between ways of specifying trees

texts: Might be an odd question but how is it that when you specify a tree using an adjacency list emphasizing leafs first you state only need state 0 or 1 parent for each node but when you define a tree in another matter, emphasizing the root first (moving inward), you must specify any number of child nodes for each node? Seems like the second method requires more data to specify the same tree than the first. Or perhaps that’s not the case for all trees?


texts: Why does my Genetic Algorithm not work for higher number of individuals?

texts:
I am using a cooperative coevolutionary genetic algorithm, the algorithm is given in A cooperative coevolutionary approach to function optimization by DeJong et. al. (1994), for optimizing a 62 dimensional function. One difference being that I am minimizing instead of maximizing. I am also using roulette selection, however since I need to minimize, the fitness is defined as the (maximum_fitness - actual_function_value).

I tried running the algorithm with 10, 20, 50 and 100 individuals, each about 5 runs. The one with 20 individuals had the lowest value of convergence while the others converged at what seems to be a higher local minima.

As far as I know, the more the individuals, the higher is the chance of escaping local minima. Is there any reason why that is not true for my case?


texts: Minimum depth of addition and multiplication circuit using XOR and AND gates

texts:
What are the minimum depth circuits possible for addition and multiplication of two n-bit numbers using just AND and XOR gates?
I read somewhere that we can achieve constant depth for addition if we have an OR gate. Can I achieve that using XOR gates?


texts:
The Böhm-Jacopini theorem states that any 'unstructured' program can be rewritten in structured way. There is a companion theorem that states that in this structuring process the tests that are performed may not be the same as the original.

Does anyone have a reference for this other theorem?


texts: How to show that the complement of a language in $\mathsf P$ is also in $\mathsf P$?

texts:
If $L$ is a binary language (that is, $L \subseteq \Sigma = \{0,1\}^∗$) and $\overline{L}$ is the complement of $L$:

How can I show that if $L \in \mathsf P$, then $\overline{L} \in \mathsf P$ as well?


texts:
If $u,v \in \mathbb{R}^d$ are two $d$-dimensional vectors, say that $u\le v$ if $u_i \le v_i$ for all $i=1,\dots,d$.  In other words, comparisons on vectors will be pointwise.

Let $S,T$ be two subsets of $\mathbb{N}^d$ of size $m$.  Is there an efficient way to test whether there exists $s\in S, t \in T$ such that $s\le t$?  The naive algorithm does $m^2$ comparisons between vectors; is there a more efficient algorithm?

If $d=1$, this is very easy: we simply find the smallest element in $S$ and the largest element in $T$, which can be done with $O(m)$ comparisons.  But already when $d=2$, it seems much harder.  Any ideas?


texts: How do RNN's handle providing output with different dimension than input

texts: It seems like an RNN has to have the ht-1 needs to be the same size as the input vector since they're being added to one another, but if you're doing something like modeling to another language or classification, how would you handle this?  I'd imagine you'd just have a fully connected layer that would predict the output, but I was wondering if there is a standard convention?


texts: I know it's possible to build a Finite State Transducer for converting numbers from base 2 to base 4 or 8 or other powers of 2 (translating from base N to base N^M is easy). However I've never seen a FST that can convert numbers from base 1 to base 2 or viceversa. Can a FST even do this? If so, can you please give some hints on building such a FST?


texts: pragmatic way to compute/ search/ match MSBs operation

texts:
consider integers represented as base 2 (strings). define a relation called "n-msb matching" that is true when the 1st n msbs (MSB is "most significant bits") match (of two integers). what is a pragmatic way of searching/ computing the following?

  given n2, find x, n such that n·3x is "many msb matching" (with n2).

note am not necessarily looking for efficient. a nice/ ideal answer would also analyze the complexity (ie # of possible solutions, hardness of finding etc)

background: naturally arises in Collatz conjecture study.


texts:
I'm taking an intro to computability course right now and I'm having some trouble with a couple examples that the professor doesn't seem too clear on.

We're learning about languages and doing some Kleene star examples. For instance, we were asked:

True or false, L+ = L or L+L+ (L+ being positive closure). We determined this was true, because if it's L1 then it equals L, and if its L2 or greater then it can be made from the L+L+ (ie. L2 would be L1L1).

True or false, L*=L* L*. We determined this was true with similar reasoning.

We were also told that any L0 is just the empty string.

Now the one that I'm having trouble with:

0* (empty set) = lambda (empty string).

We were told this is true, and I understand that it would be true for 0 0, but what about 01, 02, 03, ...

If it's only true for one case then the statement can't be true in general. I asked the professor after class and she didn't have any explanation for it. Would appreciate any help wrapping my head around this.


texts: Does register renaming remove all kinds of WAR hazard?

texts:
For the following two instruction

[Note: MOV Destination, Source ]

i1 : MOV R1, R2
i2 : ADD R2, R3

Since i1 is reading from R2 and i2 is writing to R2 there is a WAR data dependency and by register renaming like below we can remove this hazard

i1 : MOV R1, R2
i2 : ADD R4, R3

What are the other possible situations where such WAR hazard can occur ? and does register renaming solve all kinds of WAR hazard ?


texts: Can a Turing Machine decide if a regular expression matches all strings of exactly some length $l \geq 1$?

texts:
Earlier I asked the question: Can a Turing Machine decide if an NFA accepts a string of prime length?. The answer introduced me to Parikh's theorem, which I've been reading about. The concept of Parikh's theorem, if we apply it to regular expressions, allows us to break down a regular expression into expressions that only have one level of Kleene-star nesting.

So: $aa(b(cc)^*)^*$ can have a list of expressions created using the same methodology as Parikh's theorem where none of the new expressions in the final list has nested Kleene-stars. The linear subsets will use starred expressions

To make it more clear, I'm referencing this paper: http://people.inf.ethz.ch/torabidm/par-ext.pdf.

I'm not too concerned with it actually being a regular expression, DFAs or NFAs would work fine. It seems easier to work with as an RE.

I want to know if the problem is decidable:

Instance: A regular expression $R$

Question: Does there exist some length $l \ge 1$ such that $R$ accepts every string of that length (ie. if its alphabet is $\Sigma$, it accepts $\Sigma^l$, for some $l \ge 1$.

I'm pretty sure the problem actually is decidable but it's a tough one. I've enjoyed pondering it so far and would love to see what someone more experienced than myself can come up with.


texts:
I'm trying to create an algorithm in C# that given a list of ranges (segments) it produces a compacted list of them:

Example 1

Input:
[1, 3], [2, 6]

Output:
[1, 6]

Example 2

Input:
[1, 2], [2, 3]

Output:
[1, 3]

Example 3

Input:
[1, 2], [4, 6], [2,4]

Output:
[1, 6]

Too visualize the problem better, this problem is similar to this:
if you have a shop that opens from Monday to Tuesday and from Tuesday to Sunday, then you can say that your shop opens from Monday to Sunday. This is what the algorithm should do: to simplify the ranges and give the minimum set of merged ranges.

I'm absolutely lost on how to approach this problem. Thanks in advance.


texts:
I have a bunch of wmv files (~300), named the following way: video1.wmv -> videox.wmv. Some of these video files, are exact duplicates of one another (same format, same bitrate, same length, basically, they were copied and renamed, so the only thing that differs from them is their name). Is there any way to find out if two video files from this group are identical or not, so I would be able to filter out the duplicate ones?

Comparing their size is unfortunately out of the question, because I manually went through some of them, and because each of them is around the same length(even the non duplicate ones), some have identical sizes, but they are not identical per se.

If there is a possibility, I would prefer a method which could be implemented as a PHP script, but any other method of comparing them would be welcome.

Thanks!


texts: Computing maximum-cost subtree that uses at most k edges

texts:
I'm looking for an efficient algorithm for the following problem:

Input: a binary, complete tree with a cost on each edge, an integer $k$
Output: the maximum-cost subtree containing $\le k$ edges

For purposes of this problem, a subtree is defined to be a connected subset of edges.  Each edge of the tree has a cost, and the cost of a subtree is the sum of the costs of the edges in the subtree.

Only edges have a cost, which is always positive. The tree always has a root node from which only one path originates and from which we must search, in the example it is the node numbered 1. I read somewhere that it's possible to use a hashing function to compute it, but there was no explanation given.

I would also be interested to learn of an algorithm that works for graphs that aren't just binary trees.

Here's an example, with the desired subtree marked in yellow:


texts: What can't guarded fragment of FO express?

texts:
I have some basic confusions about the definition of the guarded fragment of first-order logic. Hopefully someone can tell me where I'm wrong.

GF in FO is defined by:

Atomic formulas, $x=y$ and $R(x_1,...,x_n)$, are guarded formulas.
If $\phi,\psi$ are guarded formulas, so are $\neg \phi$ and $\phi \wedge \psi$.
For variables $\{x_j,...,x_m\} \subseteq \{x_i,...,x_n\}$ and guarded fomula $\phi$ and atomic formula $A$, $\exists x_j\ A(x_i,...,x_n) \wedge \phi(x_j,...,x_m)$ is a guarded formula.

My reasoning is: for arbitrary FO formula of form $\exists x\ \phi$, I can just pick some relation $T$ that's always true and over all variables, and it's then equivalent to $\exists x \  T \wedge \phi$, a guarded formula. Other forms follow from this. So FO reduces to GF.

But that's obviously not true. I can't figure out where my mistake is. Could someone let me know where I got it wrong?

For example, isn't
$$
\forall x\ \exists y\ \forall z\ \phi
$$
equivalent to
$$
\forall x\ (T \to \exists y\ (T \wedge \forall z\ (T \to \phi)))
$$


texts: Can we generate random numbers using irrational numbers like π and e?

texts: Irrational numbers like $\pi$, $e$ and $\sqrt{2}$ have a unique and non-repeating sequence after the decimal point. If we extract the $n$-th digit from such numbers (where $n$ is the number of times the method is called) and make a number with the digits as it is, should we not get a perfect random number generator? For example, if we're using $\sqrt{2}$, $e$ and $\pi$, the first number is 123, second one is 471, the next one is 184 and so on.


texts: Check if intersection of several 2D half-planes is empty

texts:
I have a large set of half-planes $a_ix+b_iy + c_i \geq 0$.
What I need is is the fastest way to determine if they have at least one common point.
Currently I build a convex polygon by adding half-planes sequentially, there are $O(n^2)$ checks if a point belongs to a half-plane.
I need an algorithm that does $O(n \log n)$ or $O(n)$ checks.


texts: Finding the largest possible area covered by M rectangle under a given histogram

texts:
Finding the largest rectangular area possible in a given histogram is a well-known problem and have linear solution. I have a similar but different problem.
In my problem, we have $M$ rectangles instead of one rectangle in the previous problem.

So, my problem is to find the largest area under a histogram by $M$ rectangles which don't have overlap with each other. It should be noted that the bottom edge of all rectangles should be on the vertical axis of the histogram.

Is there any tractable solution for large $N$ (where $N$ is the number of bars in the histogram).

Edit:
@Apass.Jack suggested an approach with the complexity of $\Theta(MN^2)$, but after implementation, it needs some days for running! Is there any faster solution?
For clarification, the value of $N$ is around $10^7$ and the value of $M$ is around $10^3$.


texts: Creating a large tuple from smaller tuples via a monad or applicative

texts:
Suppose I have a term $a :\alpha$ of the Simply-Typed Lambda Calculus (in the following, $\alpha, \beta, \gamma$ stand for arbitrary types) and I want to lift it to a term
$\lambda x_{\beta}. \;(x, \, a)$
I could use a function $\lambda z_{\alpha}, x. \;(x,\, z)$.
Suppose we then form $(b, a) : \beta \times \alpha$, by applying $\lambda x_{\beta}. \;(x, \, a)$ to $\,b_{\beta}$.
We might want to add $c$ to the beginning of this to form $(c, b, a) : \gamma \times \beta \times \alpha$. We could do this (here $\pi_1$ and $\pi_2$ are projections)) by having a function $\lambda z'_{\beta \times \alpha}, z. \,(z,\, \pi_1 z',\, \pi_2 z')$. And again, we could cook up a function to form $(d,\, c,\, b,\, a)$ and $(e,\,d,\, c,\, b,\, a)$ (so on and so forth).
I could do things in the way above; however, I wondered whether there was a way of doing this kind of operation via an applicative or a monad. Then I could (ideally) use the operations of the monad or applicative, to lift term $a$ (perhaps into $\lambda x.\,(x, \, a)$, and then form these tuples $(b, a), (c, b, a), (d, c, b, a)$, etc, by the operations of the monad or applicative.
If you know a way of doing this I would be very interested.


texts: Higher-ranked polymorphism without explicit application or subtyping?

texts:
So, I'm familiar with two main strategies of having higher-ranked polymorphism in a language:

System-F style polymorphism, where functions are explicitly typed, and instantiation happens explicitly though type application. These systems can be impredicative.
Subtyping-based polymorphism, where a polymorphic type is a subtype of all of its instantiations. To have decidable subtyping, polymorphism must be predicative. This paper provides an example of such a system.

However, some languages, like Haskell, have impredicative higher-ranked polymorphism without explicit type applications.

How is this possible? How can type-checking "know" when to instantiate a type without an explicit instantiation or cast, and without a notion of subtyping?

Or, is typechecking even decidable in such a system? Is this a case where language like Haskell implement something undecidable that happens to work for most peoples' use cases.

EDIT:

To be clear, I'm interested in the uses, not definitions, of polymorphically-typed values.

For example, suppose we have:

f : forall a . a -> a
g : (forall a . a -> a) -> Int
val = (g f, f True, f 'a')

How can we know that we need to instantiate f when it's applied, but not when it's given as an argument?

Or, to separate ourselves from function types:

f : forall a . a
g : (forall a . a) -> Int
val = (g f, f && True, f + 0)

Here, we can't even distinguish the use of f as applying it versus passing it: it's instantiated when passed as an argument to && and +, but not g.

How can a theoretical system distinguish these two cases without a magical "you can convert any polymorphic type to its instance" rule? Or with a rule like that, can we know when to apply it, to keep decidability?


texts:
The following graph has consistent heuristic.

An A* algorithm will alter its first guess ACD to the correct shortest path ABD... if it has consistent heuristic, doesnt it mean, that AB should be found before AC?


texts: Recursive equation for complexity: T(n) = log(n) * T(log(n)) + n

texts:
For analyzing the running time of an algorithm , I'm stuck with this recursive equation :
$$
T(n) = \log(n) \cdot T(\log n) + n
$$
Obviously this can't be handled with the use of the Master Theorem, so I was wondering if anybody has any ideas for solving this recursive equation.

I'm pretty sure that it should be solved with a change in the parameters, like considering $n$ to be $2^m$, but I couldn't manage to find any good fix.


texts: Do dynamic/static languages associate types or classes to values or variables?

texts:
In Practical Foundation of Programming Languages by Harper

  There have been many attempts by advocates of dynamic typing to
  distinguish dynamic from static languages. It is useful to consider
  the supposed distinctions from the present viewpoint.

  Dynamic languages associate types with values, whereas static languages associate
  types to variables. Dynamic languages associate classes, not types, to values by tagging them with identiﬁers such as num and
  fun. This form of classiﬁcation amounts to a use of recursive sum
  types within a statically typed language, and hence cannot be seen as
  a distinguishing feature of dynamic languages. Moreover, static
  languages assign types to expressions, not just variables. Because
  dynamic languages are just particular static languages (with a single
  type), the same can be said of dynamic languages.
  Dynamic languages check types at run-time, whereas static language check types at compile time. Dynamic languages are just as surely
  statically typed as static languages, albeit for a degenerate type
  system with only one type. As we have seen, dynamic languages do
  perform class checks at run-time, but so too do static languages that
  admit sum types. The difference is only the extent to which we must
  use classiﬁcation: always in a dynamic language, only as necessary in
  a static language.

What do the first two sentences in the first part try to say:

What do dynamic languages associate  with values: types or classes or both?
What is the significance of associating types or classes to values or variables? Do static languages associate types to variables but not to values? Do dynamic languages associate types or classes to variables besides values?

Thanks.


texts: What would be a decent threshold for classification problem?

texts:
I'm using machine-learning algorithms to solve binary classification problem (i.e. classification can be 'good' or 'bad'). I'm using SVM based algorithms, LibLinear in particular. When I get a classification result, sometimes, the probability estimations over the result are pretty low. For example, I get a classification 'good' with probability of 52% - those kind of results I rather throw away or maybe classify them as 'unknown'.

EDITED - by D.W.'s suggestion

Just to be more clear about it, my output is not only the classification 'good' or 'bad', I also get the confidence level (in %). For example, If I'm the weather guy, I'm reporting that tomorrow it will be raining, and I'm 52% positive at my forecast. In this case, I'm sure you won't take your umbrella when you leave home tomorrow, right? So in those cases where my model does not have a high confidence level I throw away this prediction and don't count it in my estimations.

Unfortunately, I can't find articles regarding thresholding the probability estimations...

Does anyone have an idea what is a normal threshold that I can set over the probability estimations? or at least can refer me to a few articles about it?


texts: Not able to simplify a sum over reciprocals of $\log i$

texts:
Every time I solve these questions, I get stuck at the end where I need to find a closed form for the summation.

Here in this case, I have reached until this point:
$$
\begin{align}
T(n) &= T(n-2) + 1/\lg n \\
&= T(n-4)+ 1/\lg(n-2) + 1/\lg n  \\
&= T(n-6) + 1/\lg(n-4) + 1/\lg(n-2) + 1/\lg n. \qquad (1)
\end{align}
$$
Assuming $T(1) = 1$, I put $n - 6 = 1$ and substituted into (1):

$$ T(6) = T(1) + 1/\lg3+ 1/\lg 5+ 1/\lg7.$$

Now at this point I am not able to find out $\sum_{i=1}^n 1/\lg(2i-1)$.

On similar grounds , I become blank for another recurrence relation $T(n) = T(n-1)+1/\lg n$,
and my solution drills down up to here:
$$T(n) = T(1)+ 1/\lg2 + 1/\lg3 + 1/\lg4 + \cdots.$$

How do I evaluate such sums?


texts: Difference between read-only Turing machine and non-erasing Turing machine

texts:
I cannot quite feel the difference between two models.

The first one is read-only Turing machine which is basically the same as Turing machine with write protected input. See this question for example: Single-tape Turing Machines with write-protected input recognize only Regular Languages

It was said that it indeed recognizes only regular languages because there is no way to copy an input without rewriting it somewhere.

And there are non-erasing Turing machines that (in binary representation) cannot overwrite $1$ with $0$. This is equivalent to full power Turing machine as it was explained here Non-erasing Turing machines and loss of generality and in the paper http://arxiv.org/pdf/1304.0053

But what is the difference? We still cannot copy some strings like $1111$ due to lack of overwriting power.

So why it is weak when we cannot write only on input but strong when we cannot overwrite $1$ with $0$ everywhere? Why we can encode strings in one case but not the other?


texts: Does proving P^NP = NP have an implication in the P=NP question?

texts: For language $O$, by $P^O$ I am referring to the set containing every language that can be decided by a polynomial-time deterministic TM with oracle access to $O$ (see Arora and Barak, Chapter 3, definition 3.5).


texts:
I am looking for references (pedagogic and beginner friendly!) to these two topics,

hierarchical temporal memory algorithms applied to deep planning problems
(multi-layer) neural networks trained via SGD (after some bottom-up pre-learning using autoassociator / RBM algorithms)

Can someone help with a reference (hopefully online!) which can get me started?

It would be best I could find some course-notes.


texts: Why are dependently typed languages such as Agda used for proofs, if supercompilers for simpler typed languages can do the same?

texts: Proof assistants such as Agda can be used to assert properties about programs, such as "the double of a number is even". Interestingly, supercompilers can be used for the same purpose, creating typeless proofs. Even more interestingly, macro tree transducers can, too. My question is: what is the relationship between those? What does a dependently typed language have that makes it more powerful than other type systems as far as theorem proving goes, considering proofs can be done without types?


texts: Minimum cost to match $n$ people with $m$ shops

texts:
We are given coordinates of $n$ people and $m$ shops. We should find a matching such that each person is matched with exactly one shop, and one shop is matched with at most one person.The total cost of one matching is sum of all matchings, and for each matching its cost is calculated as Manhattan distance between those two points. It will always hold that $m > n$.

For me, this looks a lot like the bipartite matching problem, however I'm not sure what to do with the costs of the matchings. I started thinking about algorithms that starts with one trivial matching and update it if making some other matching decreases the cost. However, I'm not sure if this will work. What is the correct way to solve this problem. I don't have much experience with matching algorithms, so I'm not sure how to approach this problem.


texts:
So In a review section, our professor asked:

Given integers $N$ and $M$

Is $O(N+M)$ exponential or polynomial.

It's exponential, but I just don't see how that is. I would have thought it's linear.


texts: Round-Robin schedule: process A's time quantum expires at the same time as a process B arrives. What happens next?

texts:
Let's assume we are to implement a Round-Robin algorithm. What will happen in a case when a process has completed it's time quantum at the same time as another process arrives. Let's say we have a time quantum of 3 CPU cycles and a process A's burst time is 5 CPU cycles. If it runs from 0 to 3 (in CPU cycle time), and another process B also arrives at time 3 (in CPU cycle time), which process goes to the ready queue first? Is it possible for the process A to run 2 consecutive time quanta if the next process arrives at the same time as it completes it's first time quantum? This is one of those edge cases and it's very hard to find an explained example on the Internet.
Thanks.


texts: Scheduling a sequence of queue operations that push and pop items at specified times

texts:
What is the time complexity of the following problem?

Definitions

A FIFO is a queue functional unit supporting four commands: PUSH (data to back of queue), POP (the head of the queue), PNP (POP the head of queue and PUSH it to the back), NOP (do nothing). Each command takes one unit of time to execute.

FIFO code (or a schedule of commands) is a sequence of commands to execute.

Problem Description

We are given $n$ items of data $T_1,\dots,T_n$, and $n$ triplets $(T_1,t^{in}_1,t^{out}_1),\dots,(T_n,t^{in}_n,t^{out}_n)$. $t^{in}_i$ and $t^{out}_i$ identify the time when $T_i$ is PUSHed and POPed respectively.  We're guaranteed that $t^{in}_i<t^{out}_i$ for every $i$ and $t^{in}_i,t^{out}_i$ are all unique.

The goal is to produce FIFO code (a schedule of commands) that push each $T_i$ at time $t^{in}_i$ and pop it at time $t^{out}_i$, by adding NOP and PNP commands between the PUSH and POP commands given.  No extra PUSH or POP commands can be added: the resulting code must contain exactly $n$ PUSHes and $n$ POPs.

Example

Input:
$(T_1,2,4)$,
$(T_2,1,5)$

Solution:

PUSH $T_2$
PUSH $T_1$
PNP
POP // T_1
POP // T_2


texts: Given recurrence relation $T(n)=8T(n/6)+n \log n$, I get that the running time of the leaves should be $n^{\log_6 8}$ and $f(n)$ should be $n \log n$, but how can I know which one is bigger ?


texts: Implementing a decoding algorithm for directed figure codes

texts:
I have to implement algorithm, where definitions, input and output of program go as follows:

  $Σ$ - finite, non-empty alphabet

  A
  translation
  in
  $Z^2$
  by vector
  $u
= (
u_x
, u_y
)
∈
Z^2$
  will be denoted by
  $τ_u$
  ,

  $τ_
u
:
Z^
2
∋
(
x, y
)
→
(
x
+
u_x
, y
+
u
_y
)
∈
Z
^2
.$

  Definition 1 (Directed Figure): Let $D\subset Z^2$be finite and connected, $b,e\in D$, $b,e$ don't necessary have label,  and $l:D→Σ$
  . A quadruple$f = (D, b, e, l)$ is called a directed figure (over $Σ$) with:

  domain $dom (f) = D$ ,

  start point begin $(f) = b$,

  end point $end(f)= e$,

  labelling function  $label(f)= l$.

  Example of Directed Figure:

  $(
[
(0
,
0)
,
(1
,
0)
,
(1
,
1)
]
,
(0
,
0)
,
(1
,
2)
,
[
(0
,
0)
→
a,
(1
,
0)
→
b,
(1
,
1)
→
c
]
)$

  The set of all directed figures over $Σ$ is denoted by $Σ^⋄$

  Definition 2 (Catenation): Let $x= (D_x, b_x, e_x, l_x)$ and $y= (D_y, b_y, e_y, l_y)$be directed figures. Catenation of $x$ and $y$ with respect to mamerging function $m: Σ×Σ→Σ$ is defined as $x◦_m y = (D_x∪τ_{x_e−y_b}(D_y), b_x, τ_{x_e−y_b}(e_y), l)$

  where

  $l(z) = l_x(z)$  for $z∈D_x \setminus τ_{x_e−y_b}(D_y)$,

  $l(z) = τ_{x_e−y_b}(l_y)(z)$ for $ z∈τ_{x_e−y_b}(D_y)\setminus D_x$,

  $l(z) = m(l_x(z), τ_{x_e−y_b}(l_y)(z))$ for $z∈D_x∩τ_{x_e−y_b}(D_y).$

  Definition 3 (Code)
  $X
⊆
Σ
{^⋄_
m}$
  is a
  code
  if for any
  $x
_1
, . . . , x
_k
, y
_1
, . . . , y
_l
∈
X$
  the equality
  $x_
1
◦_
m
. . .
◦_
m
x_k
=
y_
1
◦_
m
. . .
◦_
m
y_
l$
  implies
  $k
=
l$
  and
  $x_
i
=
y_
i$
  for each
  i
  $∈{
1
, . . . , k
}$
  .

  Input:

  Code,
  Catenation of $x_1,x_2,\dots,x_n$ with respect to a merging function, where $x_1,x_2,\dots,x_n$ belong to a code  (uniquely decodable)
  merging function
  $m
: Σ
×
Σ
→
Σ$

  Output:
  $x_1,x_2,\dots,x_n$

The definitions of directed figure, catenation, and code are in the paper from https://dmtcs.episciences.org/455/pdf by Michal Kolarz and Wlodzimierz Moczurad. (pages 3,4,5, respectively)

My first task was to implement a catenation of directed figures which was easy, now I have to do similar problem, but backwards.
I thought about this problem for two days, but nothing really comes to my mind.
I had a few ideas but when I've thought about them deeper, they had some flaws in them.
Any ideas about how this algorithms should look like would be appreciated.


texts: Show that a Language can be Generated by a regular grammar

texts:
I'm looking for hints on the following exercise from Introduction to Automata Theory, Languages and Computation by Hopcroft and Ullman.

  Let $G$ be a grammar where all the productions are of the form $A\to xB$ and $A\to x$, where $A$ and $B$ are single variables and $x$ is a string of terminals. Show that $L(G)$ can be generated by a regular grammar.

This is from the second chapter of the book, so the solution should just require grammars (automata don't appear until chapter 3).

I assume that "Show that $L(G)$ can be generated by a regular grammar" means that I have to show the language generated, since this can be shown as regular grammar just by pointing out the productions.

This is where I get a bit confused...

Edit: Wrong usage of production so this is wrong, therefore what i did below is the wrong way to tackle this exercise

If i start doing the productions:
\begin{align*}
A&\to xB\\
\text{(with second)} A&\to AB\\
\text{(with  first)} A&\to xBB
\end{align*}
And so on... so in the (n)th step
$A^* → x^{n-1}B^n$ Since There would always be one $B$ more than $x$.

I was thinking that maybe I could change $xB$ for $A$ then for $x$ again to have just the string of terminals $x$ resulting in what the language generates, and this is where I think I am probably not understanding something right. I assume I am wrong because there cant be a non terminal when generating a Language...Right? Or am I just doing it all wrong?

Thank you for your time. I'm learning in Japan and my professor's English isn't very good so I can't ask him.


texts:
You have a square matrix of weights $W$ and a square matrix of distances $D$. You want to find a permutation $\sigma$ minimizing $$\sum_{i,j} W_{i,j} D_{\sigma(i), \sigma(j)}$$

Is there a known algorithm for that? Is the problem NP-complete? Is the optimal solution easily approximable?


texts: What is the algorithm to determine valid push and pop sequences for stack when repetition of numbers are allowed?

texts:
Unlike traditional problems dealing with push and pop sequences of distinct numbers, I would like to know the procedure to determine the validity of the stack operations for sequences of non-distinct numbers.

For example,

Push : 1 2 1 2 2 2 1

Pop : 2 2 1 2 2 1 1

is a valid operation for stack.

Any way to figure this out in n steps?


texts: Languages with Multiple Arbitrary Return Values

texts:
I am designing a DSL for writing numerical simulations. I am working on a specific issue related to returning values from functions, and I am wondering if any other existing language solves the same problem.

A toy example of a basic "simulation kernel" in my DSL looks something like this:

function MySimulationKernel()
    res1 = foo1()
    res2 = foo2()
    res3 = foo3()
    res4 = foo4()
end

Once the simulation kernel has been implemented, I would like to run it and collect the simulation results. The problem is that which result(s) need to be collected is not known by the function.

For example, one user of MySimulationKernel might only need the value of res1, however another user might need res1 and res4. In this example, we have 4 different such values, so there are 16 possible combinations of output values:

$16 = {4 \choose 0} + {4 \choose 1} + {4 \choose 2} + {4 \choose 3} + {4 \choose 4}$

In practice, we have hundreds of these possible output values from a simulation kernel. It does not make sense for the simulation kernel to list out its possible result values, it is safe to assume that any local variable of the function is a potential result that the simulation user needs to collect from a function call.

Essentially, it seems that what to return is a separate concern from what to compute. The simulation kernel is concerned with what to compute, and it would be preferable if that code was not cluttered at all with any logic about what to return since that is a separate concern. The function callee must somehow specify what to return, and that is properly a concern of the function callee.

Note that the type and size of these different result values can vary drastically. In some cases, a result is just a single floating-point value (and would be highly efficient to return from the function). But in other cases, the result value could be a multi-gigabyte array and outputting that array from the simulation has a very high computational cost, so we want to avoid returning values unless they are requested at the function call.

What I am looking for are example of how other languages might solve this problem. It seems like such a simple problem that others must have already encountered and solved it (I hope). Any pointers in the right direction would be helpful.

The closest I solutions I found are the Policy-Based Design / Strategy Pattern [1], and Aspect-Oriented programming [2]. These solutions are definitely overkill for the problem I am trying to solve. They also require a heavy-duty object-oriented language, which doesn't make a lot sense in this DSL.

[1] https://en.wikipedia.org/wiki/Policy-based_design

[2] https://en.wikipedia.org/wiki/Aspect-oriented_programming


texts:
What is the cardinality of the set of regular grammars?  The caveat is that I'm only interested in grammars which are 'structurally' different.  Sorry I don't know how to talk about this in a formal way, but what I mean is that the actual symbols are arbitrary to me.

So for example the grammar with:
{N={α},
Σ={x},
P={α→x},
S=α}

Is equivalent to the grammar:
{N={β},
Σ={y},
P={β→y},
S=β}

Hopefully I am being understood!  I believe this set is countable because for every N and Σ there are only a finite number of production rules which can be formulated.  For example, for:

N={α} and
Σ={x}

The only unique sets of production rules are:

{{α→x}}

{{α→xα}}

{{α→x}, {α→xα}}


texts: Finding integer square root for large integers [find asymptotic time complexity]

texts:
So I found this tasks in one book I am practicing from where it says:
"Find a divide-and-conquer algorithm for finding square roots for large integers and along this, find its asymptotic time complexity". Results can be in integer range.
I am not sure which algorithm should I use, but I started with recursive method where I count the medium between two borders and go on until i find the perfect score, or if begin border becomes greater than the end one. What I have problem here is how to measure complexity for this problem and I am not even sure does this method count as divide-and-conquer?


texts: Pumping Lemma Proof (Type of wcw language)

texts:
I have the language $L = \{ dkd\space \mid d \in \{a,b\}^*, k \in \{a,b\} \}$ and i have to show that it's non-regular using the pumping lemma.
The structure of the language i think can be explained as (based on definition above) $\{a^{n}b^{n}ca^{n}b^{n} \mid c \in \{a,b\}\}$
Based on pumping lemma, it must have this 3 properties:

$\lvert y \rvert \gt 0$
$\lvert xy \rvert \le p$
$xy^iz\in L$ for all $i \ge 0$.

Based on that, i have $a^{p}b^{p}ca^{p}b^{p}$ and $ 4p+1 \ge p $
Based on 2nd property there must be 9 scenarios (i guessed that from the theory):
One of them should be this one:

x = $\{a^{i}$} $\space $ y = $a^{p-i}$ $\space$ z= $b^{p}ca^{p}b^{p}$

Based on the 3rd property i can use $xy^{2}z$ = $a^{i}$$a^{p-i}$$a^{p-i}$$b^{p}ca^{p}b^{p}$ eventually giving me $a^{p}$$a^{p-i}$$b^{p}ca^{p}b^{p}$, the explaination is: it fails since $a$'s of the start arent the same (in number) with the $a$'s of the end.
If the above is correct how i find the other 8 scenarios and it does make any difference that my $c$ is ($a$ or $b$) instead of a single constant character?


texts:
Given two integers m and n where m < n find the maximum pair-wise xor sum.
The question is how to choose m distinct integers from 1 to n such that using those m numbers yields the maximum pair-wise xor sum.

The maximum pair-wise xor sum is calculated on a set of integers x as
F(x) = sum( number_of_bits( xor(x[i], x[j]) ) for i = 1 to k, j = (i + 1) to k )

For example:
if x = [4, 6, 8], let CB(num) return number of 1 bits in the number.
F(x) = CB(4 xor 6) + CB(4 xor 8) + CB(6 xor 8)
= CB(2) + CB(12) + CB(14)
= 1 + 2 + 3
= 6

The brute force solution could be to generate all subsets of size m and then computing the pair-wise xor sum for each and then taking the maximum out of those.  That would be exponential in terms of time.


texts: Designing CFG that accepts # of 1's = # of 2's + # of 3's

texts:
Designing following language $\{ w \mid w\in\{0, 1\}^* \mbox{ such that } |w|_0 = |w|_1\}$ is easy.

  Note $ |w|_0 $ means number of occurrences of 0.

$$
S \to 0S1 \mid 1S0 \mid SS \mid \lambda
$$

Then how about this? Language $\{ w \mid w\in\{1, 2, 3\}^* \mbox{ such that } |w|_1 = |w|_2 + |w|_3\}.$

It is somewhat difficult for me. Below is my solution. Is it correct?

$$
S \to XSX \mid \lambda
$$
$$
X \to 1123 \mid 1132 \mid 1213 \mid 1231 \mid 1312 \mid 1321 \mid 2113 \mid 2131 \mid 2311 \mid 3112 \mid 3121 \mid 3211 \mid \lambda
$$


texts: Closure of regular languages under non-contiguous subsequence

texts:
Suppose there is a language $L$ on alphabet $Σ$.
Now consider the language

$$ S(L) = \{x : wxy ∈ L, w, y ∈ Σ^*\} ∪ \{x : w ∈ L,\text{ and $x$ is a subsequence of $w$}\}. $$

How to prove that if $L$ is regular then $S(L)$ is also regular?

For first part I think if there is a DFA that accepts $wxy$ then there is a DFA that accepts $x$. For second part I have no clue. Can anyone shed some light on this or can provide a formal proof for this?


texts:
I have a markov chain with $Q(u,v)$ as transition probability matrix and $\pi(u)$ as stationary distribution defined on state space $\Omega$. The dimension of matrix $Q$ is $nxn$ and vector $\pi$ is $1xn$.

I need to construct a vorticity matrix $\Gamma (u,v)$ of dimension $nxn$ which has below properties

$\Gamma$ is skew symmetric matrix i.e, $$\Gamma (u,v) = -\Gamma (v,u) \quad ,\forall \, u,v \in \Omega $$
Row sum of $\Gamma$ is zero for every row i.e, $$ \sum_v \Gamma (u,v) = 0 \quad ,\forall \, u \in \Omega $$
Third property is, $$\Gamma(u,v) > -\pi (v)Q(v,u) \quad ,\forall \, u,v \in \Omega  $$

My question is : How to construct vorticity matrix $\Gamma (u,v)$ which satisfies above three properties? I need to construct at least one such matrix.

Is there any systematic way to build such matrices

NOTE: Transition probability matrix  $P$, and stationary distribution $\pi$ has below properties

Row sum of $P$ is one for each row,
 $$\sum_v P(u,v)=1 \quad ,\forall \, u \in \Omega$$
$\pi$ is probability distribution hence,
 $$\sum_v \pi(v) = 1$$
Stationary distribution condition for $\pi$,
 $$\sum_u \pi(u) P(u,v)  = \pi(v) \quad ,\forall \, v \in \Omega $$


texts: Proving an upper-bound on the cost of all calls to rebuild() during a sequence of m operations in a scapegoat tree

texts:
I'm reading through Open Data Structures by Pat Morin and am currently looking at scapegoat trees. The book is free and can be downloaded from here: http://opendatastructures.org/ods-java.pdf

On page 179, the author uses a "credit scheme" to prove an upper-bound on the cost of all rebuild() calls during a sequence of m operations, but I'm having a little trouble understanding how this credit scheme works.

  Lemma 8.3. Starting with an empty ScapegoatTree any sequence of m
  add(x) and remove(x) operations causes at most O(mlogm) time to be used
  by rebuild(u) operations.

  Proof. To prove this, we will use a credit scheme. We imagine that each
  node stores a number of credits. Each credit can pay for some constant, c,
  units of time spent rebuilding. The scheme gives out a total of O(mlogm)
  credits and every call to rebuild(u) is paid for with credits stored at u.

The questions I have are:

Can a node store more than one credit?
If for example we have a tree with n = 4 and q = 4 (add 1,5,2,4 in this order), does this mean that we will end up with a total of 6 credits distributed among the nodes in the tree?
How does a credit "pay" for the rebuild operations? Does he mean that 1 credit = the time or resources used to rebuild one node?


texts: Does this behavior have a formal name, and if so, what is it?

texts:
This is related to the issue asked about in this other question.

For the sake of this question, let's assume that we have a variable v that can have any value from the set of values

  "a", "b", "c", ..., "z"

In this case then the programmers wants to have specific code executed when the value of v is not "x", "y", or "z".

So the following IF statement is constructed:

  if (v != "x" || v != "y" || v != "z") {//do something}

Above statement would always return true, due to that the 3 conditions using negation are checked independently of each other.

Consequently, at any given time, any single one of the 3 conditions can evaluate to TRUE, leading to the entire IF statement evaluating to TRUE.

Anyway so the question I wanted to ask is, does this behavior or situation have a formal name, and if so, what is it?


texts: Coordinates of the center and the radius of the circle on the image

texts: What is the simplest possible way to calculate the coordinates of the center and the radius of the circle on the image (for example BMP and I'm interested in image of the Sun included below)?


texts: Design a data structure with constant insertion and sublinear range maximum query

texts:
Suppose we have access to a stream of ordered pairs, where the $i^{\text{th}}$ element in the stream is an ordered pair $(a_i, b_i)$, where $a_i$ is a timestamp and $b_i$ is an arbitrary real. How can we design a data structure with the following two methods:

$\mathcal{O}(1)$ insert
Sublinear lookup to determine when, given some timestamp $q$ as an argument, find the maximum value of $b_i$ for all elements $(a_i, b_i)$ already in our data structure with $a_i$ in the range $(q-1, q)$.

Note: The $a_i$'s are not necessarily in sorted order in the stream. There are no additional assumptions about the the distribution of the timestamps or the values $b_i$. While I am looking for a solution with worst-case time complexity for both methods, I would also be interested in seeing if the data structure could be achieved in amortized time complexity for each or both methods.


texts: Functional dependencies , minimizing SUU->V

texts: Can SUU->V or any functional dependency that contains two or more times each attribute be simplified to the same dependency with one attribute? So SUU->V becomes SU->V or STTT->Q becomes ST->Q ?


texts: Can old hardware be practically useful for CS problems of modern day?

texts:
Thinking about specific settings on WorldBuilding.SE, it turns out I need help from people who are more in touch with CS and Clusters. For those who curious about how it started, backstory here, relevant details will be provided in the body of the Q. A note, despite that joking setting, it has some bearing in reality as a concept.
premise
Motorola 68000 (specs: 8MHz, 1.5 Watt, 16/32bit, 16MB address space, ~100'000 FLOPs)
if we take old hardware as a calculating node and arrange about 19e15 calculating nodes of it in some sensible way, connect them onboard with 1MBit lanes, networks, etc
On paper, we may have a supercomputer, with a peak performance of 1'922'654 PetaFLOPs.
I assume, maybe incorrectly, that most or any task run in BOINC can be run on that cluster as well.
Highly compartmentalized tasks may run as well, which I hardly can name any besides hashing, some cryptography, searching.
ping to the system is 5 seconds, it isn't on the planet, so not that many realtime applications.
question
The problem I have is to assigns some value for the setup - a value for potential uses of that setup for modern practical applications.
Which CS problem solving can be run on such hardware and earn money?
Or is it more on paper and modern-day deep learning, big data, etc aren't fit for that cluster of low-performing nodes?


texts: Lower bound for sorting n arrays of size k each

texts:
Given $n$ arrays of size $k$ each, we want to show that at least $\Omega(nk \log k)$ comparisons are needed to sort all arrays (indepentent of each other).

My proof is a simple modification of the decision tree argument used to obtain the lower bound for comparison-based sorting of one array. More specifically, I argue that there are in total $k!^n$ possible permutations for the entries in all given arrays, and that a binary tree with that number of leaves is of height $h \in \Omega(nk \log k)$. Is that argument correct?

Furthermore, I was told that merely observing that one needs $\Omega(k \log k)$ comparisons for each of the arrays and we need to sort $n$ times in total (for $n$ arrays) is not a sufficient argument. Why is that? My answer would be that this is just one possible approach to this problem, and not a general argument excluding each and every other potential comparison-based algorithm for solving the given task with less than $\Omega(nk \log k)$ comparisons.
However, this is not particularly concise and I would consider a rather technical argument (which I don't see) as more appropriate. What would that be?


texts: How can I prove that a set is complete for $\Pi_2$ complete? Can you give me an example proof? Say for $All_{TM}$ = Turing machines whose accepted language is all strings?


texts: Proving a language is Not Regular without using Pumping Lemma?

texts:
I was wondering how one would go about proving a language is Not Regular without using the traditional pumping lemma contradiction.

$$L = \{ 1^k 0^n 1^n 0^k \mid k \geq 0, n \geq 0\}$$

I've seen a method before where you would Intersect this language with another one and show that the result is Not regular. But I'm lost on what to intersect it with.


texts: Design an NFA to accept a, ad, abc, abd, but not e, abcd?

texts:
I've made the following diagram to accept a, ad, abc, abd but I don't it to accept e, abcd, how can I limit that?

Updated
I modified the diagram in another attempt:


texts: 0/1 Knapsack problem with overlapping items

texts:
Here's a doozy:

Given a knapsack with a capacity W, and n overlapping items (definition of overlapping to follow), which items should we take to maximize the value of the knapsack?

In this problem, you can think of an "item" as a bag of coins with the following properties:

There are many, many different types of coins (1M+)
Every coin is worth the same amount
Each bag has at most one of any type of coin

For example, bag 1 might have two coins, one of type A and another of type B. And bag 2 might have two coins, one type B and one type C.

We can only take one of each type of coin. So picking bag 1 and bag 2 would mean that we have 3 total coins (one A, one B, and one C).

How can we figure out which bags to take to maximize the number of coins you can take?

The subproblems aren't independent, so I don't think we can use dynamic programming.

For extra credit:

How can we get within a certain threshold, say 10%, of the capacity W as fast as possible?


texts: Is there a faster solution for the Google Code Jam Great Wall Problem

texts:
Consider the following Google Code Jam round 1C question:

The Great Wall of China starts out as an infinite line, where the height at all locations is $0$.

Some number of tribes $N$, $N \le 1000$, will attack the wall the wall according to the following parameters - a start day, $D$, a start strength $S$, a start west-coordinate, $W$, and a start east-coordinate, $E$.  This first attack occurs on day $D$, on range $[W,E]$, at strength $S$.  If there is any portion of the Great Wall within $[W,E]$ that has height $< S$, the attack is successful, and at the end of the day, the wall will be built up such that any segment of it within $[W,E]$ of height $< S$ would then be at height $S$ (or greater, if some other attack that day hit upon the same segment with strength $S' > S$)

Each tribe will perform up to $1000$ attacks before retreating, and each attack will be determined iteratively from the one before it.  Every tribe has some $\delta_D$, $\delta_X$, and $\delta_S$ that determines their sequence of attacks:  The will wait $\delta_D \ge 1$ days between attacks, they will move their attack range $\delta_X$ units for each attack (negative = west, positive = east), though the size of the range will stay the same, and their strength will also increase/decrease by a constant value after each attack.

The goal of the problem is, given a complete description of the attacking tribes, determine how many of their attacks will be successful.

I managed to code a solution that does work, running in about 20 seconds:  I believe the solution I implemented takes $O(A\log A + (A+X)\log X)$ time, where $A =$ the total number of attacks in a simulation (max $1000000$), and $X =$ the total number of unique edge points on attack ranges (max $2000000$).

At a high level, my solution:

Reads in all the Tribe information
Calculates all the unique $X$-coordinates for attack ranges - $O(A)$
Represents the Wall as a lazily-updated binary tree over the $X$ ranges that tracks minimum height values.  A leaf is the span of two $X$ coordinates with nothing in-between, and all parent nodes represent the continuous interval covered by their children. - $O(X \log X)$
Generates all the Attacks every Tribe will perform, and sorts them by day - $O(A \log A)$
For each attack, see if it would be successful ($\log X$ query time).  When the day changes, loop through all unprocessed successful attacks and update the wall accordingly ($\log X$ update time for each attack). - $O(A\log X)$

My question is this:  Is there a way to do better than $O(A\log A + (A+X)\log X)$?  Perhaps, is there some strategic way to take advantage of the linear nature of Tribes' successive attacks? 20 seconds feels too long for an intended solution (although Java might be to blame for that).


texts: In a CSP, what is an extensional constraint?

texts: When talking about Constraint Satisfaction Problems (CSP), what does the term extensional constraint mean?


texts: How much calculus do you actually use (not counting use of a graphing calculator)?

texts: I'm wondering if it's worth it to pursue some deep study into calculus. Already, I have some familiarity with derivatives, limits, and integrals. Though, I also have a graphing calculator that's helped me in high school and college a algebra.


texts:
I was reading CLRS about BFS and DFS, and the algorithms presented therein, which I take to be somewhat standard, constructs a forest in DFS that includes all the nodes, whereas BFS only constructs a tree from a chosen node $s$, and leaves out all the other nodes that are not reachable from $s$.

It seems the BFS can be adapted to construct other trees to include non-reachable nodes from $s$ and form a "BFS forest", analogous to operation of the DFS. What is the reason for constructing a forest in DFS, but only a tree (that excludes unreachable nodes) in BFS?


texts: Devising an algorithm to remove "complete" sets of numbers from a list of numbers

texts:
Suppose I have a list of numbers consisting of numbers 1 through 5, where some numbers repeat. Define a set of numbers to be "complete" if it consists of each of the numbers 1-5 exactly once. Now, I want to pull out as many possible complete, sorted (lowest to highest) sets from this list. How can I do this (efficiently)?
Here is the solution I have in mind so far. Traverse through the list, and place each number into a pile of numbers that is the same number. For example, place all the 1s into a pile, all the 2s into a pile, and so on. Then, go through all of the piles and determine the minimum number of elements in a pile. For example, if the pile of 2s has five 2s and all other piles have greater than or equal to five elements, then 5 is the minimum number of elements. This minimum, call it min, will give us the number of complete sets in the list. Finally, go through the piles in order and pull out the elements one by one until you form a complete set, and again to form another complete set, and so on until min number of complete sets. Tada! You now have pulled out as many possible complete, sorted sets from this list.
Here is an example:
Let's say the list is 3 2 1 2 2 3 4 5 5 4 4 3 4 1 1 2 5. We traverse the list and put them into piles:
333 2222 111 4444 555
The minimum number of elements in a pile is 3, so we have 3 complete sets. Now just go through the piles in order and pick up elements one by one:
12345
12345
12345
And tada! We have pulled out as many complete, sorted sets as possible.
Where I am lacking in my solution is figuring out how to efficiently go through the piles in order or make an efficient way of ordering the piles so that I can easily go through them in order.
I'd love to hear any feedback, especially other algorithms you might devise or ways to go about ordering. Thanks!


texts: Class of the language of Turing machines that loop on at least one input

texts:
$L = \{ \langle M \rangle \mid \text{there is at least one input string on which the \(M\) does not halt} \}$

Here, for a Turing machine $M$, the notation $\langle M \rangle$ denotes an encoding, over some alphabet, of the code of the Turing machine. To which of the following language classes does $L$ belong?

Regular.
Context-free but not Regular.
Recursive but not Context-free.
Recursively enumerable but not recursive.
Not recursively enumerable.


texts: A pathfinding algorithm for graphs in which arc weights can change over time

texts:
So I'm not really sure even what to be googling for solutions to this. Hence this question, hopefully, someone can point me in the right direction.

Here's the situation, I have a weighted undirected graph of nodes and arcs. I have an implementation that uses A* for pathfinding on this graph. However, I now have a situation where the weights (cost) of each arc can change over time. That is at each step in the A* pathfinding algorithm the weights of the entire graph can change.

So I'm trying to see if there is an existing algorithm or alteration of A*-like algorithm that handles changing weights well. If anyone has any keywords I should be looking into I'd appreciate any pointers you can provide.


texts: Hash multiple integers directly using FNV-1a

texts:
An alternative version of FNV-1a hash spread on the internet, which operates directly on integers instead of bytes. The offset basis and prime are the same used in the original version, which operates on bytes.

With this version, is the statistical quality of the produced hash similar to the original algorithm?

Alternative version operating on integers:

#include <cstdint>

#define OFFSET_BASIS 2166136261ul
#define FNV_PRIME 16777619ul

uint32_t hash(uint32_t i, uint32_t j, uint32_t k)
{
   return ((((((OFFSET_BASIS ^ i) * FNV_PRIME) ^ j) * FNV_PRIME) ^ k) * FNV_PRIME);
}

Original version operating on bytes:

#include <cstdint>

#define OFFSET_BASIS 2166136261ul
#define FNV_PRIME 16777619ul

uint32_t hash(char* data, size_t bytes)
{
   uint32_t h = OFFSET_BASIS;

   for (size_t i = 0; i < bytes; ++i)
   {
      h = (h ^ data[i]) * FNV_PRIME;
   }

   return h;
}


texts: Relation between size of address bus and memory size; memory Segmentation in 8086

texts:
My question is related to memory segmentation in 8086. I learnt that,

  8086 has a 20 bit address bus. And so it can address 2^20 different addresses. Which means it has an memory size of 2^20, i.e, 1MB.

I have a few doubts:

What I understand from the fact that 8086 has a 20 bit address bus is that it could have 2^20 different combinations of 0s and 1s, each of which represents one physical address. What I don't understand is that how does 2^20 different address locations mean 1 MB of addressable memory? How is total number of different addresses locations  related to memory size (in Megabytes)?
Also, correct me if I'm wrong, the 16 bit segment registers in 8086 hold the starting address of the different segments in the memory (Code, Stack, Data, Extra).My question is, aren't the addresses in memory of 20 bits? Then how can the 16 bit register hold 20 bit addresses? If it contains the upper 16 bit of the 20 bit address, how does the processor make out to which exact address location it has to point?

P.S: I am a beginner is micro-processors and total reliant on self study, so kindly excuse if my questions seem a bit silly.

Thanks in advance.


texts:
A graph $G$ is said to be a  model of a first-order sentence $\varphi$ if $G$ satisfies $\varphi$. Now let $\varphi(x_1,...,x_r)$ be a first order formula with free variables $x_1,...,x_r$. What is the standard terminology for a tuple of vertices $(v_1,...,v_r)$ of $G$ such that $G$ satisfies the formula $\varphi(v_1,...,v_r)$ obtained by substituting $x_i$ with $v_i$?

What I'm having trouble is to find the right terminology to connect $G$ to the assignment. The only thing I can think now is the following.

"$(v_1,...,v_r)$ is a satisfying assignment for $\varphi$ in $G$."

But maybe there is a shorter way.


texts: How much math does one need to know to understand discrete math/structures for computer science?

texts:
Normally universities teach discrete math / discrete structure. My question is, how much math does one need to know to understand this area? Is calculus required or will precalculus do just fine? Does one need to have done proofs before to be able to understand this area?

Thank you all for your answers.

Note: My apologies if this has already been asked. after my investigation i could not find any similar questions. If you believe this is the case please share where this has been answered and i will gladly end/remove this.


texts: Is there any compiler IR paradigms other than Three Address Code and Static Single Assignment (SSA) Form?

texts:
Specifically, I have tried boiling down the operations of a VM into the smallest possible standardized units and arrived at this:
allocate_stack(size)
fetch(offset_from_stack_pointer)
store(offset_from_stack_pointer)
call(index)

So you might have:
allocate_stack 6
fetch -2
store 0
fetch -1
store 1
call 72

Basically, the allocate_stack would tell you how much space you are allocating for fields in the stack. Then the fetch would queue up something relative to the stack to be stored (or fetch_a would fetch an absolute address). Then store would store the fetched value in the space relative to the stack (or store_a for absolute position). And finally, call <index> would call that specific function.
So basically these are 2-address codes instead of 3-address codes. Does anything like this exist out there where they've expanded upon the idea to find compiler optimizations and such, like 3-address-code and SSA form? If not like this, does anything else exist outside of 3-address-code and SSA form?


texts: How can I keep track of the state of a sequence after rotating parts of it multiple times?

texts:
Given a sorted array

1 2 3 4 5 6 7 8

and an operation that takes the N-th element out the array and puts it in front (or rotates the first N elements to the right by one), leaving the following for N = 3

4 1 2 3 5 6 7 8

I need to be able to figure out the state of the array, after performing an arbitrary number of these operations.

I've implemented a simple algorithm using std::rotate that simulates this behavior, but the problem is that my input data set is too large, and rotating the physical array gets really slow.

I've also tried doing this in a std::list (linked list), while keeping a separate array of pointers to every K-th element, so that I could access anywhere in the list in near constant time, while benefiting from the fast removal. This approach requires moving the pointers (or iterators in my implementation) every time I rotate, but since I have less pointers than the actual elements in the array (say 1 pointer per 1000 list elements), this isn't so expensive. All in all, this solution turns out to be about 2 times faster than the vector in some cases, in others it's less fast, but it's still too slow.

I don't need to store the actual array, I only need to be able to compute the value of any element in it. I can see how to do this easily if I only had to do one rotation, where the 0th index would be the rotated element, everything before the rotated element would be shifted one to the right by one and everything on the right side of the element would be kept in place, but I don't see how to keep this up when I do multiple rotations.

One of the possible solutions I found was using interval trees, though this seems rather complex and I'm not sure if it would be more efficient given the high number of rotations needed.

TL;DR: Given a sequence of the first N natural numbers, perform K rotations and figure out the final state of the sequence. For the sake of example, set N = 10^6 and K = 10^5.


texts:
I have a Set $S$ of objects, a set $U$ of users and a map $c: U \rightarrow S^{\prime}$, where
$S^{\prime} \subset S$ and $\emptyset \notin S^{\prime}$.

Every time I add a new entry to $c$, i.e. adding a new user $u$ with her associated subset of $S^{\prime}$, I need to get the list of other users with whom she covers $S$. However, I don't need to get all possible covers. I only need to get with how many $x$ other users she covers $S$, at most. In other words, I need to find who's complementing each other to cover $S$ 2 by 2, 3 by 3, ... , $x$ by $x$.

Is there an efficient method to do it? Or an efficient data structure? If no, is there any trick I can make to get good results? e.g. encode the elements of $S$ and do some sort of mathematical operations? Is any efficient solution possible at all?

Please let me know if I haven't explained my problem well enough.


texts: Douglas-Peucker line simplification algorithm time complexity

texts:
I am analyzing the time complexity of the Douglas-Peucker line simplification algorithm. Reading online I've found that it has a worst-case running time of $O(n^2)$ where $n$ is the number of points on the line. However, I haven't been able to provide complete proof. Here is the pseudo-code I am working with:

Here is my analysis:
Line 1: $O(1)$
Line 2: We can say that it goes through all points in the polyline formed by the first point and the last point in $PL$ and return the point with the maximum distance to the straight line between the mentioned points. We can safely say this is $O(n)$
Lines 4-6: If we are here we are doing two recursive calls. The number of elements used in each call could be different (not always in half). Depends on the point found in Line 2. Leaving implementation details aside, we can say that splitting is $O(1)$. Also, we have a $JOIN$ operation which would take $O(n)$ to join both lists.
Line 8: This is also a $JOIN$ operation but this only takes $O(1)$.
After looking at these steps I think we have the following recurrence relation:
$T(n) = T(index + 1) + T(n - index) + 2n$ where $index \in \{1, \dots, n-1\}$
Am I right? If so, how could I prove this is $O(n^2)$? Master Theorem?
Thank you very much in advance
EDIT: Changed description on Lines 4-6. Thus, also changed recurrence formula.


texts: algorithm for connectivity by path of given length

texts:
Given an unweighted, undirected graph $G=(V,E)$ without loops or multiedges, and vertices $v,w$, one can use breadth-first search to check if $v$, $w$ are connected, and in particular the algorithm will return a shortest path between them.
BFS has time complexity $O(|V|+|E|)=O(|V|^2)$.
Now let $k$ be some fixed integer (not part of the input).
Is there an algorithm that takes $G$, $v,$ $w$, and checks whether there is a path between $v$ and $w$ of length $k$? What would be its time complexity?


texts: What are the approaches to private computations?

texts:
I'm talking about the ability to safely run a virtual machine on a physical device that is not trusted. It is necessary that the owner can not access the data that the virtual machine operates on.
I am interested in what theoretical or practical implementations exist without special hardware.

I know about homomorphic computations (this in theory fully satisfies my question), but for now it's incredibly slow. It will take many years before the protocols of homomorphic calculations just approach application in practice.

I also read about Intel SGX, which implements enclaves. The RAM stores only encrypted data, which is decrypted at the input to the processor and is again encrypted at the output. The disadvantage of Intel SGX is that you need special hardware.
How could you do without a special hardware? How can we store a key for decrypting data from RAM so that the owner of this physical device can not recognize this key?


texts: Alternatives to evolutionary computing for structure, design and policy optimization (optimal structure search)?

texts:
I once had this question https://math.stackexchange.com/questions/1083338/structural-design-meta-optimization-is-there-mathematical-theory-optimiza about the methods for finding optimal structures, designs and policies (as another kind of structures - set of rules), i.e. optimization of the structure of the models not just the parameters for some pre-selected structure. So far I am sure that the genes of evolutionary computation (EC) can effectively encode structure and evolutionary computing can perform effective search for more optimal structures. EC algorithms are quite sophisticated - there is evolutionary programming (for search of strings in some grammar) and there is cultural algorithms (which incorporates already known certain knowledge for speedup of the search). But are there some other kind of search procedures (besides evolutionary computing) for searching more efficient structures. EC is stochastic search methods and is there deterministic search methods for the search of optimal structure? I expect only key-words, pointers and trends.

Or - more clearly - is EC the most general search framework? Are there search alogrithms or approaches than can not be reduced to the string of application of crossover, mutation and other operators of EC?


texts: Why is the satisfiability of ESO formulas not equal to the satisfiability of FO formulas?

texts:
Existential second-order logic (ESO) formulas have the form
$$\Phi = \exists R_1 ... \exists R_k. \phi$$
where $R_1...R_k$ are relation symbols and $\phi$ is a FO formula,
which can use the relation symbols $R_1...R_K$ as well as other relation symbols.
My claim is that

  $\Phi$ is satisfiable if and only if $\phi$ is satisfiable.

Indeed, satisfiability of a FO formula means finding a universe and an interpretation of all relation symbols. Therefore, we have an implicit quantification $\exists R_1 ... \exists R_k$ in front of the FO formula $\phi$, when considering satisfiability. (For validity, the claim does  not hold.)

But the claim must be wrong since people study satisfiability of ESO separately from that of FO. What do I miss?


texts:
Let's say we have $n$ items of size $si_i$ and $m$ containers, each has a capacity $sc_i$. Every container can have at most one item at a time, provided its size is less than or equal its capacity.

Now we add time axis to this problem, because otherwise it would be trivial. Every item $i$ starts to exist at time $t_{i1}$ and ceases to exists at $t_{i2}$. You could visualize this with Gant diagram. There are no limitations of how many items may exist simultaneously, or anything like that. All we know that every item has its birth and death time. Also $t_{i1}, t_{i2} \in \{0,1,2,...,59\}$ and $t_{i2}>t_{i1}$. These are all constraints on $t_{i1}$ and $t_{i2}$

How to assign containers to all items, assuming the solution exists? The naive approach is to assign the smallest possible container to every item, but the order does matter:

If the are two avaliable containers $c_1$ and $c_2$ of capacity $sc_1=10$ and $sc_2=12$, if $c_1$ is assigned to the 1st item (because it's the smallest available container), and $c_2$ to the 2nd item (again, the smallest available container), the 3rd item won't have any available container. However if you assign the smallest container to 2nd and then 1st item, there will also be a container of capacity $12$ for the 3rd item, because it won't be blocked by the 2nd item.

Does this problem as a name already? And is there any simple algorithm to solve it, except brute force?


texts: Set theory pertaining to category theory and functional programming

texts:
I'm reading an unfinished Introduction to Category Theory/Products and Coproducts of Sets and have come across the following:

A power set of a set is the set of all its subsets. A script 'P' is used for the power set. Note that the empty set and the set itself are members of the power set.
\begin{equation}\mathcal{P}\{1,2,3\} = \{\varnothing,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}\end{equation}
Set operations are functions from the product of a power set to a power set.
\begin{equation}\text{Union}:\mathcal{P}(X) \times \mathcal{P} \to \mathcal{P}(X),
\text{Union}(A,B) = A \cup B\end{equation}

I don't understand the last part.
To me a product of a power set should equate to a set of tuples where the first of the ordered pair is a subset from first power set and the  second is a subset from the second power set. Whereas a power set is just a set of subsets.
How can this mismatch be explained or is it a mistake?

Taking on board the advice below:
If the set $X$ is a singleton value $1$, then:
\begin{equation}X = \{1\}\end{equation}
The power set of $X$ is then:
\begin{equation}\mathcal{P}(X) = \{\varnothing,\{1\}\}\end{equation}
The product of $\mathcal{P}(X)$ is then:
\begin{equation}\mathcal{P}(X)\times\mathcal{P}(X) = \{(\varnothing,\varnothing),(\varnothing,\{1\}),(\{1\},\varnothing),(\{1\},\{1\})\}\end{equation}
Applying $\text{Union}$ to the $\mathcal{P}(X)\times\mathcal{P}(X)$ is:
\begin{equation}\mathcal{P}(X)\times\mathcal{P}(X) = \{(\varnothing,\varnothing)\mapsto\varnothing,(\varnothing,\{1\})\mapsto\{1\},(\{1\},\varnothing)\mapsto\{1\},(\{1\},\{1\})\mapsto\{1\}\}\end{equation}
As the result is a set, duplicates can be removed:
\begin{equation}\{\varnothing,\{1\},\{1\},\{1\}\} = \{\varnothing,\{1\}\}\end{equation}
Thus:
\begin{equation}\mathcal{P}(X)\times\mathcal{P}(X) \to\mathcal{P}(X)\end{equation}
And so the set operation of $\text{Union}$, which is one of a family of set operations (a set of functions) is a function from the product of a power set to a power set


texts: Proof of correctness of algorithm to determine whether the elements of an array are repeated an equal number of times

texts:
I apologize for the long title, but I really didn't know how to write it different without lacking informations about the content.

I recently had an university exam about Parallel Algorithms. One exercise asked me to write an algorithm to determine if the elements of an array, let's call it A, were repeated an equal number of times.

For example:

1) A = 1 8 8 1 8 1 1 8 : the answer is yes, every number is repeated 2 times.

2) A = 7 8 8 5 5 4 7 8 : the answer is no.

I had to write the algorithm for a particular model of parallel computing, a PRAM: the model required me to use some techniques to avoid read/write conflicts, and other problems, but this is not relevant. What I ended up with was a new array, let's call it B, which I can define as follow: Given the array A, B[i] contains the number of repetitions of the element A[i] within A.

For example:

1) A = 1 8 8 1 8 1 1 8

B = 4 4 4 4 4 4 4 4

2)A = 7 8 8 5 5 4 7 8

B = 2 3 3 2 2 1 2 3

As you might think and expect, the only thing left to do would be to check if every element of B is equal to the other, but.. it turns out I'm masochist, and the pressure of the exam (plus I had a bit temperature) led me to take another path. Moreover, comparing elements of an array is not immediate using this computing model.

So, to check if all the elements of B are the same, I summed all of them and divided the result by the number of elements of B: if the result was equal to an element of B (for example the first, B[0]) then the algorithm returned true (false otherwise).

Taking the example above:

1) sum = 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 = 32 --> 32 / 8 = 4 = B[0] --> Yes.

2) sum = 2 + 3 + 3 + 2 + 2 + 1 + 2 + 3 = 18 --> 18 / 8 ≠ 2 = B[0] --> No.

I know it's absurd, but that's what I came up to.

I checked this approach with a lot of different combinations of arrays/numbers, and it seems to work. Thing is, I'm having an hard time in finding a (mathematical) proof that the algorithm is correct. Besides the result of the exam, which I still don't know yet, I'm very interested in knowing if there's some mathematical proof/explanation which states that this approach is correct or not, and that's why I need an help.

I hope I have posted the question in the right StackExchange site. If not, please redirect me to the right site.

Thank you in advance.


texts:
I am looking for an efficient algorithm that can partition an area $B \subset \mathbb{R}^2$ into disjoint subsets $B = \bigoplus_i U_i$ such that a test function is constant on each of the subsets, $f \vert_{U_i} = \mathrm{const.}$

For example, consider the following partitioning:

The indicated numbers are the return values of the test function in each cell. I want to recover the partitioning, given area error bounds, with the least number of function calls.

My current approach uses a recursive grid-based method that tests at each vertex of an intial $n \times n$ grid. If not all vertices of a grid cell have the same function value, the cell is subdivided and the process repeats. This needs many subdivisions, and the initial grid must be "fine enough".

I am curious if a specialized approach exists, and if there is a common name for this problem.


texts:
I was doing some reseach and I came across a website that had listed 16 different boolean logic operators. I was wondering if all of them were real, and if so, what do they do.

https://www.researchgate.net/figure/Method-for-implementing-all-16-Boolean-logic-functions-in-a-single-MR-unit-with-a_fig1_303770111


texts: Trade offs implementing ADTs and Solution independence

texts:
I was told here is more appropriate than stack overflow so:
I'm writing an essay about ADTs and algorithms and I have to discuss the trade-offs with implementing ADTs, the only things which come to mind are time and space, however the previous topic was about determining algorithmic efficiency, which again was time and space and so I'm second guessing myself.
My trade offs that I came up with were time vs space and efficiency of one action vs another ( like how a linked list based stack can add items more efficiently than a static array based stack)
In terms of solution independence I am meant to talk about several advantages to it I have come up with the ability to reuse the code again and again but after that I am drawing a bit of a blank and cant seem to find any good resources talking about it; would someone have any ideas or even have somewhere they could point me towards?


texts:
I am working on tiny programming language (for our specific tasks). It's a script language.
It looks like a library for C++ that can execute a code of this language. This library parses a source code and create required entities in the memory, i.e. a source code isn't compiled in byte code, it keeps in the memory as C++ objects and all next calls use these objects in the memory.
My question is can I call that library interpreter? Or has it some specific name?
Just I read an interpreter is a program that executes a source code by logical blocks or pre-compile it into byte code but my library does a nothing from this. It parses a whole source code and after works with objects in the memory.


texts: Artificial Neuron: question on definition and inhibited signals

texts:
This is an artificial neuron of a NOT function from Rojas's ML book.  I have a question on it's behavior.  It's my understanding that the neuron produces a signal if it's inputs $x_1$ summed are $\geq 0$.

In the following picture, if $x_1$ is 0, then the threshold 0 is met and there is an 1 output signal from this neuron.  If $x_1$ is 1, then the signal is inhibited by the neuron and the threshold of 0 is met, in which the neuron should have a 1 output signal.  This does not make sense to me as I would expect the neuron to have an output of 0 if $x_1$ is 1.

I'm also confused on NOR as pictured:

Appreciate if anyone can provide guidance on how this neuron works with the inhibitory signal into it.  The book defines the neuron is that of McCulloch–Pitts.

Thanks


texts: What are the limitations of symbolic model checking?

texts:
What are the limitations of the Symbolic Model Checking?

As far as I know, "state-space explosion" can still happen by this technique but it can explore much larger state space.

So, is the Symbolic Model Checking always better than the conventional model checking? If not, when to apply which one?

By the conventional model checking I mean:
Clarke Jr, Edmund M., et al. Model checking. MIT press.

And by Symbolic model checking I mean:
McMillan, Kenneth L. "Symbolic model checking." Symbolic Model Checking. Springer, Boston, MA, 1993. 25-60.


texts: An infinite language with no infinite RE or co-RE subsets?

texts:
Are there any languages that are infinite (that is, they contain infinitely many strings) but which do not have any infinite subsets that are RE or co-RE languages? This seems related to simple sets, but I can't seem to find any examples of languages with these properties.

Thanks!


texts: Non-existence of PSPACE-hard unary language

texts:
I'm trying to prove that unless $\mathsf{P}=\mathsf{PSPACE}$, there is no unary language which is $\mathsf{PSPACE}$-hard.

Assuming there is an unary language $A$ which is $\mathsf{PSPACE}$-hard, it doesn't seem reasonable to solve $A$ in polynomial time. How can this be proved then?