texts: Randomly assign n elements to n agents such that each agent only knows its own element

texts:
Problem
I'm working on an app that involves shuffling and distributing playing cards to players. As a challenge, I tried to solve this problem in a way that doesn't require a trusted intermediary.
In other terms, the task is to find a distributed algorithm that

uniquely assigns $n$ agents numbers $1..n$
allows each agent to know nothing about the assignment but its own
when revealing the assignment, allows other players to verify the assignment

We also assume that knowing other's assignment is an advantage for each agent, and revealing its own prematurely a disadvantage. Agents are also assumed to be able to talk with each other in a way hidden from all other agents.
Partial solution
The solution I came up with works only under the assumption that adversaries do not collaborate.
The idea is to create a set of $n$ nonces, and assign each agent exactly one nonce. The set is then passed from agent to agent in an agreed upon order, hidden from all others, until each agent received the set exactly once. Each time an agent receives the set, it swaps its nonce with a new one, memorizes the new nonce, and confirms receival of the set to the others. This entire procedure is done twice, at which point, all agents have received the set at least once after all other agents swapped their nonces, making it impossible to recognize and hence map the nonces to the other agents.
When the last agent receives the set the second time, it shares it with everyone, and all agents confirm to the others that their nonce is contained in the set. The agents then assign a number to each nonce in the set based on an agreed upon random seed, giving us the required unique assignment.
To allow ownership verification, instead of the nonces, agents put the hash value of their nonce on the set, revealing the actual nonce only when verification is required.

The problem with this solution is that if adversaries are allowed to collaborate, each time an adversary receives the set, they can compare their versions, identify changes and potentially derive which nonce belongs to other agents, allowing them to know what number got assigned to them.
All ideas are appreciated!


texts: What's an efficient algorithm to check if a binary operator is residuated?

texts:
Assume the binary operator is given as a table/matrix, so constant time to compute $xy$. And likewise, assume the (relation giving rise to the) partially ordered set is also given as a table, or in any case assume constant time to check if $x \le y$.
If I want to check if a finite binary operator is residuated, what's an efficient way to do this check with the operator and order given as in above data structures?
It looks like a "dumb" approach would be O($n^3$), i.e. for every $a$ and $b$ fixed giving rise to the inequation $ax \le b$, search for (the greatest) $x$ that satisfies it. If such an $x$ cannot be found (for some $a$ and $b$), then the operator is not resituated. (That also computes the residual if you keep searching for the greatest $x$ on each inequation).
Is there a faster way?


texts: Scheduling Repeating, Flexible Intervals with Restrictions on Overlap

texts:
I work in 52:17 work:break intervals, as there's some evidence showing it's an effective way to structure the day. However, meetings or planned breaks often require shifting that schedule, moving, shrinking, or expanding certain parts.
I'm trying to write a program which will do this for me, given a start time, an end time, and a list of calendar events which should either be treated as breaks or sprints. It should return a schedule consisting of as close an approximation to the 52:17 schedule that it reasonably can.
Problem statement:
Input:

Start of day time
End of day time
List of calendar events. User may classify events as "break" (e.g. lunch) or "sprint" (e.g. meetings). These are fixed/immovable.

Output:

A schedule that approximates the 52:17 intervals, accommodating the aforementioned events.

For example, say I want to work from 8-12 (duration = 240 minutes) uninterrupted. I want to start and end with "sprint". I can find the ideal breakdown as follows:
# Every span starts and ends with a sprint right now,
# though this can be modified later to handle other circumstances
function n_cycles(duration=240, break_time=17, sprint_time=52):
    cycle_time = break_time + sprint_time
    # If we're looking at an interval of less than the break time
    if duration <= break_time:
        # just call it a break
        return -1
    else if duration <= 52 minutes
        # just call it a sprint
        return 0
    else:
        cycles = 1
        accounted_time = sprint_time
        # If adding another cycle would exceed the duration by more than half
        while accounted_time < duration + cycle_time * 1.5:
            accounted_time = accounted_time + cycle_time
            cycles = cycles + 1
        return cycles

function span_interval(start_time, end_time, break_time=17, sprint_time=52):
    cycles = n_cycles(end_time - start_time, break_time, sprint_time)
    if cycles == -1:
        create_event(start_time, end_time, type=break)
    else if cycles == 0:
        create_event(start_time, end_time, type=sprint)
    else:
        duration = end_time - start_time
        ideal_cycle_time = sprint_time + break_time
        proportion = duration / (ideal_cycle_time + ideal_cycle_time * cycles)
        adjusted_sprint_time = sprint_time * proportion
        adjusted_break_time = break_time * proportion
        create_event(start_time, start_time + adjusted_sprint_time, type=sprint)
        start_time = start_time + adjusted_sprint_time
        for i in 0 to cycles:
            create_event(start_time, start_time + adjusted_break_time, type=break)
            start_time = start_time + adjusted_break_time
            create_event(start_time, start_time + adjusted_sprint_time, type=sprint)
            start_time = start_time + adjusted_sprint_time

So if we do this, we get:

8:00-8:48   Sprint #1
8:48-9:03   Break
9:03-9:52   Sprint #2
9:52-10:07  Break
10:07-10:56 Sprint #3
10:56-11:11 Break
11:11-11:59 Sprint #4

Easy! Optimal!
But say I want to add a work event from 10:00-10:15. Currently, I have a "naive" solution where any sprint event is treated as a whole sprint. Then, recursively, the part of the day before and the part of the day after are scheduled. Aside from the fact that the above pseudocode must be modified to end the first half with a break and start the second half with a break (easy), this is also obviously not optimal, since we now have a 15 minute sprint with breaks on either side. I could shift sprint #2 back 7 minutes and compensate on either side, but if I have an event that's 3 hours long, I'm going to need to delete events, not just shift them.
Any ideas about how I can better approach this problem? I'm interested in search algorithms like GAs, but I can't figure out how to structure the problem such that it can be modular and solutions can be heritable.
EDIT: rephrased and formatted in response to comments from D.W.


texts: Problem using the Arden's Lemma on one automata

texts:
I am trying to find the regular expression of this automata using the Arden's Lemma:

Let $L_{i}$ be the language accepted from the state $i$, this is what I got:

$L_{1} = 1^{*}0L_{2}$
$L_{2} = 1L_{1} + 0L_{3}$
$L_{3} = \epsilon + 0^{*}1L_{2}$

As the first state is the initial one, I have to solve $L_{1}$. As $L_{1}$ is expressed using $L_{2}$, I have to first solve $L_{2}$.

$L_{2} = 1(1^{*}0L_{2})+0(\epsilon + 0^{*}1L_{2}) \\ L_{2}=11^{*}0L_{2} + 0\epsilon + 00^{*}1L_{2} \\ L_{2}=(11^{*}0+00^{*}1)L_{2} + 0$

Using Arden's Lemma, I get $L_{2}=(11^{*}0+00^{*}1)^{*}0$

Thus we have now:

$L_{1}=1^{*}0L_{2}=1^{*}0((11^{*}0+00^{*}1)^{*}0)$

Yet, based on this expression, the word "000" isn't accepted. Where is my issues?


texts: In programming languages, generally we do not distinguish relations and functions. Is there a better way to deal with these two concepts?

texts:
When we write a mathematical formula, the rule $a=42$ (when we say let $a=42$) and testing them (when we write something like $\ldots \mathrm{if} x=42$) is written in a same equal sign. I think that both of them are representing some relation. However, while programming, we write = for the first circumstance and == for the second, and == is actually the infix representation of the equivalent testing function. Should they be treated as the same thing?

Previous question:

Are programming languages confounding relations and functions?

p.s. I have been asking this a few hours ago on StackOverflow, but they told me that it was on a wrong venue.

For example, the equivalent sign = has a lot of meanings, including returning a boolean value that tests whether to expressions are equal to some extent, setting up a rule that both side are equal, and assign the right side to the left side. And notations such as < and || are generally parsed as boolean operators. What's more, they do not distinguish predicates and boolean functions.

In my opinion, this is not a very elegant way to treat the 'rules'. I think notations like ≤ should be thought to be a relation, which means a≤b implies $(a,b)\in R_\leq$, where $R_\leq \subset S^2$ and $S$ is the domain of $a$ and $b$. Mathematically, ≤ is not a function at all (If it is, it should be something maps from a subset of $S^2$ to $\{True, False\}$). It is just representing some rules.

However, while programming, we generally do not realize the difference between them. We may consider k = a < b as a simpler way to write something like k = True for a<b, False otherwise. However, I believe that this makes things confusing in some circumstances, for example, the use of =.

I have seen a lot of imperative and functional language that do not seem to respect these differences. Am I correct in this point of view? Is there a better way to solve this?


texts: Calculating all products of $n-1$ factors when given $n$ factors

texts:
Let's assume we have an operator
$$ \times: E^2\to E$$
of which we merely know that it is associative. Let's say a multiplication $e\times f$ always takes up a time of $M$ for all $e, f\in E$.

We're now given $n$ elements $e_1,...,e_n\in E$, and are tasked to calculate all $n$ products
$$\def\bigtimes{\mathop{\vcenter{\huge\times}}} p_j :=\bigtimes_{i=1\\i\neq j}^n e_i$$

Naively multiplying out all $n$ products takes $O(n^2M)$.

A more sophisticated approach that runs in $O(n^{3/2}M)$ splits $\bigtimes_{i=1}^n e_i$ at arbitrary positions into $\sqrt n$ factors.
For each of the $n$ products, we now only have to recalculate one factor, and multiply the resulting factor, and the other $k-1$ factors together.

What is the fastest algorithm for this problem, and how does it look like?


texts: Classification with optional/catchall attributes

texts:
Context
Let $S$ be a set of objects, each object $S_k$ containing a set of attributes $A_k\subseteq A$, where $A$ is a global set of attributes. Suppose each attribute $a_k\in A$ can take on integer values $[1,m_k]$. Suppose also that the objects in $S$ are unique, i.e. no two objects contain the same attributes and the same values for those attributes.
Given a target object $X$ that contains values for all of $A$, I want to find the objects in $S$ that match $X$, matching constituting equality of values of all attributes between two objects. This sounds like a job for ID3, but here's the catch: attributes an object in $S$ does not contain are catchalls: they match against any values of those attributes in $X$.
I'm looking for something in the neighbourhood of $\mathcal{O}(|A|\lg(|S|))$ worst-case time and $\Theta(|S|)$ space, which if I understand correctly ID3 achieves. I haven't the faintest clue what kind of pre-processing tradeoffs exist, but it would be nice if construction were $\mathcal{O}(|S||A|)$ and insertion were $o(|S||A|)$ so that I didn't have to reconstruct the tree every time.
I'm leaning towards an ID3-like algorithm, but I don't know if its performance holds with the catchalls, since multiple branches can be valid on the same level.


texts:
Elements are stored in a single dynamic data-structure $D$
Element ranks are computed by: $\forall i \in n\quad f(i,\ x_i+1) : x_i \in \mathbb{Z^+}$
The function $f$ is weighting based on the value of $i$
$f$ can be redefined, when it is $D$ is restructured accordingly

Where $D$ supports insert in no more than $\mathcal{O}(\log_2 n)$, and delete-min, get-min, decrease-key in $\mathcal{O}(1)$. Linear space is preferred.

To use Haskell notation:  (\(f,x) -> f x + 1)((\i -> i*2), 5). However I might change the weighting to e.g.: f = \i -> quot i 2. Trivially one can construct new priority-queues for new definitions of f. I would like it to restructure in less than $\mathcal{O}(n)$. Is that possible?

Is there a solution for the implementation of $D$ which takes less than $\mathcal{O}(n)$ to complete 4.?


texts: Recognizably turing machine question (reject / loop)

texts:
The definition of proving recognizability using dove tailing is below. However I'm wondering if we can also prove loop or reject in the same way?

Give a deterministic TM D that recognizes L such that if $w \in L$ then D accepts w. Or if $w \notin L$, then D does not accept $w$. I realized this definition states on whether D accepts a $w$ like

$A_{*111} = \{\langle M \rangle \mid M$ is a TM, and $M$ accepts some string that ends with 111$\}$, which is recognizable and easy to prove through dovetailing.

Now how about

$R_{*111} = \{\langle M \rangle \mid M$ is a TM, and $M$ reject some string that ends with 111$\}$?  Is this also recognizable and would the proof be the same as the one above ? I think this will work but what about

$L_{*111} = \{\langle M \rangle \mid M$ is a TM, and $M$ loops on some string that ends with 111$\}$?

How do you check if something loops?


texts: Can all languages have semantic and logical errors?

texts:
I have been reading about PHP and many authors mention semantic and logical errors separately. As an example of a semantic error, they give a function called with incorrect number of parameters: this will not be caught by the parser, but will throw an error when run.

Yet in languages such as C++, this will be caught by the compiler. I would say that it's a syntax error then. What is the difference then between a semantic and a logical error?

For example, in How to think like a computer scientist, the author uses "logic error" and "semantic error" interchangeably. On the other hand, in the Visual Basic .NET. Primer Plus, "logic error" is separated from "semantic error".


texts:
Given the functions $()=^{n}$ and $()=10^{10n}$, I am trying to establish the following relationship: $()\notin o(())$.

I know to show for the opposite, $()\in o(())$,  I would need to choos $c$ and $n_{0}$ such that $\exists$ $c$, $\exists$ $n_{0}$, $\forall n\geq{n_{0}}$ then $f(n)\leq c. g(n)$, but how should I choose $c$ and $n_{0}$. Note that I am beginner in studying CS and any help would be greatly appreciated.


texts: Algorithm for getting symetric vertex sets of undirected graph

texts:
For my application problem, I am searching for an algorithm that can find all symmetric vertex sets of an undirected labeled graph.

My definition of symmetric vertex set is:
Let $G$ be a graph with vertex set $V$ and edge set $E = \{u,v\}, u,v \in V$. If $S \subseteq V$ and there exits an isomorphism $f$ on this graph such that for every $v\in S$, we have $f(v) \in S$, then $S$ is called a symmetric vertex set.

I have searched some graph matching algorithms, but have gotten no clue so far. I am wondering if any one can give me a hint, I will work on it.


texts: A decision algorithm to choose what partner to use

texts:
Background

I have a setup where I need to make an API call to a partner to initiate a financial transaction. I have multiple partners, and I need to choose which one to use each time a transaction needs to happen. The characteristics differentiating two partners are:

if the transaction is accepted or not (acceptance)
the cost of the transaction (fee charged by the partner, assumed to be constant over time)
the speed of the transaction (assumed to be constant over timefor each partner)

The characteristics of a transaction are especially:

amount
currency
(several other factors such as the user's country, the payment method he chose, etc)

Additional info: the acceptance rate of a partner is subject to
   change arbitrarily over time.

.

Algorithm

As you probably guessed, I am currently thinking about solutions and algorithms that could be used to solve the following problem.

  Inputs:

  a transaction (with all its characteristics)
  the database of all transactions having ever happened, containing for each transaction

  the partner used
  the fee charged
  if the transaction was accepted or not

  Output: the best partner to use to execute the transaction.

Obviously, the first step is to define best. Do we value speed more than cost? Do we value the expected acceptance rate more than both the cost and speed? etc.

Another important aspect I mentioned earlier is that the acceptance of the same transaction by the same partner might change over time. This means that the algorithm should sometimes try a partner that is believed not to be currently the best just to be able to, for instance, check if a partner's acceptance rate has improved over time.

My question

I'm obviously not asking someone to write a magic algorithm solving that. I have a background of CS, but I am unsure about what algorithms and types of algorithms are usually used to solve this kind of problem. I would be grateful to be given some extra terminology (e.g. if this is a typical problem with a particular name in the domain) and resources to be able to dig into the problem.

Please don't hesitate to ask if something is unclear.

Thank you!

[Edit] After searching a bit more on the web, it seems that this problem has a lot in common with the multi-armed bandit problem. However I believe that the algorithms presented to solve this problem (e.g. UCB1) could be suboptimal in this context, because they wouldn't take into account the characteristics of a transaction and act as if the partner didn't take them into account.


texts: Upper bound on the average number of overlaps for an interval within a set of intervals

texts:
Let $\mathcal{I}$ be a set of intervals with cardinality $L$, where each interval $I_i \in \mathcal{I}$ is of the form $[a_i, b_i]$ and $a_i, b_i$ are pairwise distinct non-negative integers bounded by a constant $C$ i.e. $0 \leq a_i < b_i \leq C$. We say a pair of intervals $I_i, I_j \in \mathcal{I}$ overlap if the length of overlap is $> 0$.

Define a function $F(i)$ which computes the number of intervals in $\mathcal{I} \backslash I_i$ that interval $I_i$ overlaps with.
\begin{equation}
F(i) = \sum_{j=1, j \neq i}^{L} Overlap(I_i, I_j)
\end{equation}
where the function $Overlap(I_i, I_j)$ is an indicator function which returns 1 if $I_i, I_j$ overlap, else it returns 0.

The average number of overlaps for the intervals in $\mathcal{I}$, denoted by $Avg(\mathcal{I})$ is given by $Avg(\mathcal{I}) = \dfrac{\sum_{i=1}^{L}F(i)}{L}$.

The question is, suppose we are allowed to choose the intervals in the set $\mathcal{I}$ with the following additional conditions:

For any $t \in [0, C]$, we have at most $M$ (and $M < L$) intervals in $\mathcal{I}$ such that $t$ is contained within those $M$ intervals. Stated differently, at most $M$ intervals overlap at any point in time.
Any interval in $\mathcal{I}$ overlaps with at most $K$ other intervals, and $M < K < L$.

then, what is an upper bound on $Avg(\mathcal{I})$ for any choice of the intervals in $\mathcal{I}$ satisfying 1, 2?

In case you are wondering, this problem is of interest to me in order to be able to study the run-time of a scheduling algorithm.

I am unable to come up with a non-trivial upper bound for $Avg(\mathcal{I})$ and would be interested to know if the problem I stated has been studied. I am also open to ideas on how one may be able to obtain a tight upper bound for $Avg(\mathcal{I})$.


texts: Dynamic programming algorithm to find largest triangle in binary square matrix where elements equal “1”

texts:
I'm struck how to find DP recurrence for:
You are given a binary square matrix M of size nxn. We define a (p,q, l)-triangle of M, where p >= 1,
q >= 1, L >= 1, p+L >= n+1, and q+L >= n+1, as the set of elements M[i, j] satisfying p =< i < p+L,
q =< j < q+L, and i+ j < p+q+L. Design an algorithm to find the largest (p,q, l)-triangle of M (“largest”
means l is maximized) such that all its elements are “1”
EDIT: I added the original problem as requested:

solution:
I think I need to check first if:
element equal 1,
if so, check the element to its left, element in its top and element diagonally if equals "1"
if so increment the result,
but not sure how to put this into recurrence.


texts: Program to Translate Turing Machine to Tableau?

texts: Is a program available to translate a Turing Machine program to Boolean tableau format as used for example in proofs of the Cook-Levin theorem?


texts: Why selection sort is a stable sort algorithm?

texts:
One of the specifications of sort algorithms is stability, which means items with the same value in different indices are not replaced after applying sort algorithm.
Why selection sort is unstable and can we make a sort algorithm stable by changing its swap condition?


texts: Compare Hidden Markov Model's sample with ground truth data

texts:
I have a time-serie and I fit different HMMs on it, each with a different number of hidden states.
Now after sampling from the models , I'd like to compare the results with the ground truth data and find the model that gets closer to the real world data in the original time-serie.
For now I simply compared visually the distribution of the values generated by the HMMs and the distribution of values in the time-serie, but I'd like to compute a number indicating which model generates better samples.


texts: What is the approximation for odd cycle transversal?

texts:
What is the best approximation for odd cycle transversal?    (on general graphs)
Sorry if this is easily found  everything I found about odd cycles is about paramaterized complexity and kernels


texts:
i am trying to formulate an algorithm for syntax checking for simple boolean expression like (var1 = 10) or (var2 > 100).
evaluation part seems to be easy as i will convert infix to postfix and evaluate postfix without 'paren()'.

i am not fully sure which method should i be using.

can any one point me to a book with algorithm or a link.


texts: Asymptotic bound of a recursive function

texts:
Consider the following procedure computing a dummy function. Which one is a correct asymptotic bound for the running time of F(N) expressed in terms of N?

F(i):
    if i<3then
        return 0
    end if
    return F(i−1) + F(i−2)

$• A. O(N)
• B. O(N^2)
• C.O(2^N)
• D. O(N log(N))$

This may seem like a dumb question but I have no idea how to get asymptotic bounds for recursive methods. I got the following recurrence relation:
$T(n)=T(n-1)+T(n-2)$
but I'm not sure where to go from here. The answer is supposed to be C.


texts:
If the definition of Initial Algebra is:

"An object is initial if there exists a unique morphism from the object to every
object in the category"

Why do we need such object, and could any one give an example ?


texts: Peer discovery: What class of network algorithm prioritises low latency above all else?

texts:
I'm trying to flesh out a proposed application model where all peers in a distributed network discover each other in the least possible propagation time.

But I'm reached the limit of my knowledge of network theory and my naive search keywords return too many disparate PDF white-papers to narrow down.

So my question is: What protocol or class of algorithm for discovering every peer in a network prioritises low latency over every other network characteristic?


texts: Modified Counting Inversions problem using divide and conquer

texts:
Given an array $A$, find the number of pairs $(i, j)$, such that $ i > j$ and $A[i] \ge A[j]$.

This is a modified version of the famous problem of Counting Inversions, only in this version it allows the elements to be equal as well. I have an algorithm for the classical counting inversions problem implemented, so i´d like to know if it can be adapted to solve this version. Thanks ahead.

Link to the algorithm (written in C++):

https://repl.it/@MateusBuarque/CountingInversion


texts: Need help finding/writing an algorithm to reassign items to groups with minimal changes

texts:
I have some users in groups, like this (groups are letters, users are numbers):
{
  a: [1, 2, 3],
  b: [4],
  c: [5],
  d: [6],
  e: [7, 8, 9, 10]
}

I receive a new description of the grouping of these users like this:
[1, 2, 3, 4, 5, 6, 11],
[7, 8, 9, 10]

Now, I need to rearrange the users to minimize "changes", so in this case, they'd end up like this:
{
  a: [1, 2, 3, 4, 5, 6, 11],
  e: [7, 8, 9, 10]
}

A more nuanced example is this:
from:
{
  a: [1, 2, 3, 4, 5, 6]
  b: [7],
}

to:
[1, 2, 3, 7]
[4, 5, 6]

options:
{
  a: [1, 2, 3, 7],
  c: [4, 5, 6]
}
{
  a: [4, 5, 6]
  b: [1, 2, 3, 7], // THIS IS BEST
}

In this example, the second choice is best, because we move [1, 2, 3] to b rather than [4, 5, 6] to c and [7] to a.
I've been trying to come up with some heuristics, like starting with the largest invalidated group, then in that group, take the largest group that are still together after the change, and letting them keep their place.
That kind of thing seems to work, except in the second example, I can't think how to make it pick option 2 over option 1.
I'm wondering if this is a solved problem, if it can even be done without multiple passes and comparisons, and if I'm attacking this in a vaguely sensible way.
Any guidance would be greatly appreciated.


texts:
I'm reading an article about indexing in Redis. There is a link to so-called Hexastore, it's referred to as a data structure. The link doesn't work, which makes me feel I'm missing something.

I understand from the article that

  the hexastore provides a representation for relations between objects,
  formed by a subject, a predicate and an object. A simple relation
  between objects could be

  antirez is-friend-of matteocollina

What are the key use cases of Hexastore as a data structure? Which indexing problems can it solve along with the quoted example above? How does it work?

There is a paper about Hexastore on the internet, which has a long explanation. Could anybody put it in a nutshell?


texts: Construct an equivalent NFA for the given regular grammar

texts:
Given is the regular grammar G = ({A,B}, {a,b}, P, A) with the rules

P : A → aB, a, ε (where ε is the empty word)
    B → bA, b

  For this regular grammar, create an equivalent NFA.

A regular grammar is a 4 tuple G = (N, Σ, P, S).

So our NFA is made up of 2 states, A and B. The initial state is A and it's also the ending state because the rule says we have the empty word ε in the state A. If we read an a from state A, we go to the state B.
But I don't know what that single a means in the first rule?

From state B, if we read a b, we go to state A. But again, what does this single b mean in this rule?

All in all I would construct the NFA for the regular grammar G like that:


texts: Fastest algorithm for finding the number of primes in a range

texts: Is there an algorithm for finding the number of primes in a given range $[N, M)$ that works in time linear to $M-N$? For context, $N$ and $M$ can go up to $10^{10}$, but the distance between N and M is at most $2\times10^7$. I know that the sieve of Eratosthenes method works in $O(n\log\log n)$ time, but it would require calculating the number of primes up to $M$, which goes up to $10^{10}$ so it would be too slow.


texts: Relation between dominance and post-dominance

texts:
Dominator and post-dominator trees are useful data structures which are used to encode static analysis information. Dominator trees for example are used to compute the dominance frontiers for SSA conversion, whereas post-dominator trees are used to compute control dependencies of a statement. Post-dominance is usually computed by calculating dominance of a reverse CFG.

Strictly speaking, if some node a dominates node b, it does not necessarily imply that b post-dominates a. So, the question is 1) what is the relation between dominance and post-dominance? 2) Is there a graphical representation that can encode both relations, and are there any theoretical work that spells out the properties of this representation?

I am aware of data structures such as DJ graph (combination of dominator edges + control flow edges not captured by dominator edges, called join edges) that are used for tasks such as dominance frontier calculation or performing exhaustive/incremental data flow analysis, but none on combined representation of dominance and post-dominance.

Any pointers or references to related work is highly appreciated.


texts: Indexing Edge Permutations for the Rubik's Cube

texts:
I'm working on a Rubik's Cube solver that implements Korf's algorithm, as published in his 1997 paper, Finding Optimal Solutions to Rubik's Cube Using Pattern Databases.  His method involves creating three pattern databases: one for the 8 corner cubies; one for 6 of the 12 edge cubies; one for the remaining 6 edges.

My question is about indexing the permutations of the edge pieces.  Mind you, each edge can be oriented in one of two ways, but my questions is not about the orientations, only the permutations.

With 6 edge positions and 12 edge cubies that could occupy them, there are 665,280 possible permutations (12 pick 6, or 12! / 6!).  For simplicity sake, let's say the edge cubies are numbered 0-11.  The 6-element partial permutations of these 12 cubies in lexicographical order is thus (0 1 2 3 4 5), (0 1 2 3 4 6), (0 1 2 3 4 7), ... (11 10 9 8 7 6).  Is there an efficient way to index those permutations?  Sequential indexing would be preferred, although that may not be possible.

One thought I had is to simply iterate through all 665,280 permutations and store the associated index.  That's doable, although it's rather memory intensive.  I'm looking for more of a minimal perfect hash approach.

For example, I have the indexing for the 8 corner cubies figured out.  For the 8 corner cubies, the Lehmer code for each permutation can be computed, and then that Lehmer code can be converted to a sequential index.  Korf describes how to do this in his 2005 paper, Large-Scale Parallel Breadth-First Search.  However, that paper does not address indexing partial permutations.

Related questions:

Indexing into a pattern database - Korf's Optimal Rubik's Cube solution
https://math.stackexchange.com/questions/97813/a-positional-number-system-for-enumerating-fixed-size-subsets


texts: Need Help Understanding MST Cutset Formulation

texts:
I just started learning about linear programming in my class, and I'm having some trouble understanding the MST Formulation Integer Linear Programming (Cutset Formulation).
This is the definition:

An integer linear program that solves the minimum spanning tree problem is as follows:
$$
\begin{align*}
\text{Minimize} & \sum_{\{u,v\} \in E} w_{u,v}x_{u,v} \\
\text{subject to} & \sum_{\substack{\{u,v\} \in E\colon \\ u \in S, v \notin S}} x_{u,v} \geq 1 & \text{for all $S \subseteq V$ with $0 < |S| < |V|$} \\
& \sum_{\{u,v\} \in E} x_{u,v} \leq |V|-1 \\
& x_{u,v} \in \{0,1\} & \text{for all $\{u,v\} \in E$}
\end{align*}
$$

$x_{ij}$ is defined to be $1$ if the edge $ij$ is in $T$.
What exactly does the optimum value represent here? Is it the number of edges that are used in our MST? If so, how does knowing the number of edges help us in forming the MST?
How does this ILP "work" to solve the MST problem?


texts: About Control Unit in CPU and Clock Cycle

texts:
I've been studying about CPU and I am trying to implement a small CPU, like MU0.
Control unit gets instruction and generates and gives several control signals to other parts of CPU, such as ALU, PC, ACC, etc. And I know that these works in one clock cycle.
But I have some quetions.

Meaning of Signals (0 or 1) in Clock Cycle

Each one clock cycle has signal 1 first and has 0 next. Since CPU is an electronic equipment, 1 would mean current is flowing (so, "turn on") and 0 would mean no current flow (so, "turn off").
So, does each control signals connected to the clock cycle circuit turn off when the clock cycle is 0 at the same time, if we ignore delays of the circuit?
If not, i.e., if control signals can be 1 although clock cycle is 0, I can state my hypothesis:
Clock signal is only meaningful and only used when signal toggles 1→0 or 0→1. Control unit can not work when its signal stays in the same value since it can not recognize time is going.
Is that true or false?

Timing to Control each Control Signals

(source: tistory.com)
Here is the structure of MU0, one of simple CPUs.
If we want to store data from memory with the address in PC to IR and increase PC by 1 (i.e., PC = PC + 1), the manual says that setting control signals as below would do that.

0 : Asel, Bsel, ACCce, ACCoe
1 : PCce, IRce, MEMrq, RnW
with ALU function B+1.

Note that the value of PC goes in ALU and the output of ALU is PC+1 since Asel(A selector), Bsel are 1.
But, since PCce(PC chip enabler) is 1, PC change the value by the input of PC, which is the output of ALU.
It seems good to make PC as PC+1. But my questions is:
This is an infinite loop theoritically since PC+1 would goes into ALU and PC+2 would save in PC, and then PC+2 would goes into ALU and PC+3 would save in PC, ... so and on until one clock cycle ends.
To avoid this, controlling timings would be different for each control signals. Is this really true, or is there another solution?
Thanks.


texts:
I have a thermal camera that I would like to overlay, automatically, to the output of a RGB-D camera (e.g. Kinect).

I have retrieved the intrinsic and extrinsics parameters of both cameras.

My objective is to calculate the disparity map between the two. That is, to map the matrix resulting from the depth image to the thermal image, in order to estimate the distance of each point in the thermal image.
From an intuitive standpoint, I should be able to align them because I have depth information in this case.

A solution that comes to my mind, it is as follows:

Step 1: for each pixel of the depthmap, estimate its corresponding 3D point. Let's call it Depth_3D.
Step 2: transform Depth_3D in Ther_3D. That is, given the 3D position of the point of the depth camera, find the 3D position of the same 3D point (object in the real world), but respect to the thermal camera. The relative position and orientation of the two cameras is known.

Problem: to perform step 2, I need the 3D rotation matrix (let's call it R3D) and 3D translation vector (let's call it T3D) to be able to map from the depth camera to the thermal camera, in the real world.

Step 3: Finally, using the intrinsic parameters of the thermal camera, project each Ther_3D into the thermal image.
Step 4: assign the depth to the obtained pixel, so that, at the end of the loop, the depth map of the thermal image is complete.

My doubt is about how to calculate R3D and T3D (please see step 2) using their relative position and orientation.
Other solutions are welcome of course.

Thanks in advance.


texts: Explanation of an explanation of Turing's proof to the halting problem?

texts:
I am reading the transcription of a lecture from a professor Scott Aaronson, specifically the section titled Turing Machines. In this section he describes Turing's proof of the Halting Problem.

  But can we prove there's no program to solve the halting problem? This
  is what Turing does. His key idea is not even to try to analyze the
  internal dynamics of such a program, supposing it existed. Instead he
  simply says, suppose by way of contradiction that such a program P
  exists. Then we can modify P to produce a new program P' that does the
  following. Given another program Q as input, P'

runs forever if Q halts given its own code as input, or
halts if Q runs forever given its own code as input.

  Now we just feed P' its own code as input. By the conditions above, P'
  will run forever if it halts, or halt if it runs forever. Therefore P'
  -- and by implication P -- can't have existed in the first place.

How would P(x) be defined here, the algorithm which can compute the halting problem?

halts if x halts
otherwise does ...

Is P allowed to "output" something or only halt or not halt? It can write to a tape correct? So it could output 1 if x halts or 0 if it does not and then halt itself?... By attempting to define P am I trying to disprove Turing?..

Would we not need to know the source code of P to modify it to produce P'?

Is the overall idea of the proof that a machine to solve the halting problem would not be able to prove that it itself halts given its own source as input?


texts: What is the SetHorspool string searching algorithm and how is it implemented?

texts:
What is the SetHorspool string searching algorithm with pseudo-code so it can be easily implemented in a language of choice?
This has been implemented in 2 libraries I have come across:

https://app-db.com/seqan/1.3/SPEC_Set_Horspool.html,
http://stringsearchalgorithms.amygdalum.net/.

But there seem to be very little details of the algorithm available online to understand its working.


texts: Physical Meaning Behind Matrix Factorization

texts: As we all know, Matrix Factorization is an effective method to do rating prediction jobs in recommender systems. Thanks to the work of Yahuda Koren. My question is why MF can do this job? What's the physical meaning behind it?


texts: Consider a Binary Deletion Channel with a deletion probability p of 1/2 and the channel has no error correction coding at all and that any given message can only be sent once. I want to conjecture that the capacity for the aforementioned channel is zero ( channel capacity for the Deletion Channel is presently unknown), can anyone point to any known complexity results that would point me in the direction of proving or disproving my conjecture?


texts: Seeking Efficient Approximation Algorithm for Adaptation of TSP

texts:
Consider the following adaptation of the traveling salesman problem:

  Given a complete, undirected graph $G$ with nonnegative edge weights,
  color each vertex either red or blue. Find the shortest path that
  visits all vertices exactly once (does not need to return to starting
  vertex), but does not visit vertices of the same color more than 3
  times in a row (i.e. the path

  $$red \to blue \to blue \to blue \to red$$

  is valid but

  $$red \to blue \to blue \to blue \to blue$$

  is not. Assume that there are the same number of red and blue
  vertices.

I'm trying to come up with an algorithm to at least approximate a shortest path given this constraint. My initial thought was the following (besides simply trying all $|V|!$ different paths):

Greedy Approach: Choose a starting vertex $v_0$ and at each step, simply choose the vertex $v_1$ that minimizes $d(v_0, v_1)$. However, keep a record of the colors of $v_{i}$, $v_{i-1}$, and $v_{i-2}$ at each step, and if the optimal choice of the next vertex $v_{i+1}$ violates the color constraint, choose the next best vertex.

The only problem I see with this is that you can 'run out' of vertices of a given color. That is, you could reach a point where there are more than $3$ vertices remaining, but they are all of the same color. This would make it impossible to complete the path.

My Question: Does anyone have any suggestions on algorithms to try? Maybe a modification to my suggested greedy approach to make it complete, or another paradigm all together?

(I know that this problem is $NP$-complete - that's why I'm seeking an approximation algorithm.)


texts:
I am trying to write an algorithm which produces a solution to a modified n by n sliding puzzle (assuming that an end state is reachable from the given start state). The change is as follows: tiles can belong to sets with other tiles and can occupy any of their positions as well, and the sets are disjoint. The image below shows an example on the right which is in one of many end states. A tile labeled with x numbers could be in any of the x positions it is labeled with. For example:

on the left we have 3x3 of: $\left\lbrace1\right\rbrace, \left\lbrace2\right\rbrace, \left\lbrace3\right\rbrace, \left\lbrace4\right\rbrace, \left\lbrace5\right\rbrace, \left\lbrace6\right\rbrace, \left\lbrace7\right\rbrace, \left\lbrace8\right\rbrace,$ and
on the right we have a 3x3 $\left\lbrace1,4,6\right\rbrace, \left\lbrace2,8\right\rbrace, \left\lbrace3\right\rbrace, \left\lbrace5\right\rbrace, \left\lbrace7\right\rbrace.$

My current thinking is to treat each tile as being in its own set, and exhaustively check if the initial state is solvable - in this example labeling the tiles in positions $1 $ (top left)$, 2, 4, 6,$ and $8$  as respectively $\left\lbrace1\right\rbrace, \left\lbrace2\right\rbrace, \left\lbrace4\right\rbrace, \left\lbrace6\right\rbrace, \left\lbrace8\right\rbrace$, then $\left\lbrace4\right\rbrace, \left\lbrace2\right\rbrace, \left\lbrace6\right\rbrace, \left\lbrace1\right\rbrace, \left\lbrace8\right\rbrace$, etc. and running some existing algorithm for the original puzzle if a solvable state is found.


texts: Filling a string with wildcards with minimum cost

texts:
You are given a string with wildcards, e.g. X***Y*Z. Your goal is to print an input string filling all the wildcards in the given string.

You are allowed to write data to the string in blocks of fixed size: character-by-character, you can write contiguous blocks of identical characters of length 2, 3 ... N: X, XX, XXX, etc. For example:

  Block: XX, apply to the 2 position in X***Y*Z => X*XXY*Z

It is allowed to overwrite same characters:

  Block: XX, apply to the 0 position in X***Y*Z => XX**Y*Z

When you choose a size of block you would like to use, let's say S, "preparation" costs occurs: S*L, where L - some input constant. Let's say, you picked the size 2 (cost is 2*L), then you are allowed to write XX, YY, and ZZ to the given string. When you write a block of data to the given string, writing cost occurs - some input constant C that is independent of the block size. When you choose some block length, e.g. 2, you have to fill all blanks using block_size = 2, you are not allowed to decrease or increase it in the middle of writing. For example, if you write the first piece of data to the given string as XX, later you are allowed to use YY and ZZ only. The same with other sizes.

Your task is to identify the minimum possible cost to fill all blanks considering costs of writing data and preparing a block.

Let's consider the example above in details. We are given a string X***Y*Z, L = 20, C = 10. For each option, there are a plenty of variants how to fill blanks.

1) We can fill all blanks with a block of size 1 using any characters from {X, Y, Z}. Thus, total cost is 1*20 (prepare a block of size 1) + 4*10 (fill 4 wildcards) = 60. Possible results, there are plenty of them:

  XYXZYXZ, XXXYYZZ...

2) We can use block size = 2. For example, overwrite X* with XX, ** with XX, Y* with YY, the total cost is 2*20 (prepare the block of size 2) + 3*10 (perform 3 writing operations to fill all blanks), the total cost is 70.
Example:

  Solution 1

  Init: X***Y*Z

  step1: write XX at 0 => XX**Y*Z

  step2: write XX at 1 => XXX*Y*Z

  step3: write YY at 3 => XXXYY*Z

  step4: write ZZ at 4 => XXXXYYZ

My current approach is, basically, straightforward brute-force - start with block_size = 1, iterate it up to N, each time try to fill all the wildcards. If current block overwrites existing data, try changing symbol type accordingly (If a block consists of X, try using Y). If it's not possible, try another symbol type/block size.

Is there any better way?


texts: Are C standard library functions considered part of C programming language

texts: Do we consider functions like printf part of C language even if it's not a keyword in it.


texts: Solving linear programming problem with mixed type of constraints

texts:
I have a query in solving the problem below:
An automobile company has two factories. One factory has 400 cars (of a certain model)
in stock and the other factory has 300 cars (of the model) in stock. Two customers order
this car model. The first customer needs 200 cars, and the second customer needs 300 cars.
The cost of shipping cars from the two factories to the customers is shown:

Customer 1
Customer 2

Factory 1
\$ 30
\$ 25

Factory 2
\$ 36
\$ 30

How should the company ship the cars in order to minimize the shipping cost?
I am confused about how to proceed with this problem. I have considered the slack variables $x_3$ through $x_6$, and conversion of the minimisation problem to a maximisation one, and got:
$\text{Maximise Z}=6x_1+5x_2-16200$
$\text{subject to, }x_1+x_2+x_3=400$
$~~~~~~~~~~~~~~~~~~~-x_1-x_2+x_4=-200$
$~~~~~~~~~~~~~~~~~~~x_1+x_5=200$
$~~~~~~~~~~~~~~~~~~~x_2+x_6=300$
$~~~~~~~~~~~~~~~~~~~x_1, x_2, x_3, x_4, x_5, x_6 \ge 0$
However, when I start with the dual simplex method, I cannot get an entering variable, since the $C_j-Z_j$ values of the first iteration are all $\gt 0$.
How do I solve this using simplex and/or dual simplex? Any help is appreciated.


texts: How to give an upper bound on this bin packing problem?

texts:
In the bin packing with fragile objects (BPFO) problem one is given a set of objects $\{1,\ldots,n\}$ where each object $i$ has a weight $w_i$ and a fragility $f_i$ for all $i$ in the set $\{1,\ldots,n\}$. (We assum that $w_i\le f_i$.) Also, we have a set of bins of infinite capacity (each) in which we want to place the objects.

The objective is to assign the objects to the minimum number of bins such that the sum of the weights in each bin is at most the minimum fragility. That is, if we assign the set of objects $S$ to bin $B$ than we must have:

$$\sum_{i\in S}w_i\le\min\limits_{i\in S}f_i.\quad\quad\quad  (1)$$

The BPFO problem is given in this paper. Let us denote the optimal value of BPFO by $OPT$.

I am trying to relax BPFO by modifying equation$~(1)$ as follows.

$$\sum_{i\in S}w_i\le f_i,\forall i\in S$$

Let us denote the optimal value of the relaxed problem by $OPTR$.

Now, I would like to upper bound $OPT$ by $OPTR$. How can I achieve this?

It is clear that a solution to BPFO is a solution to the relaxed problem and then $OPT\ge OPTR$.

Is there a way to say that $OPT\le \alpha(n)OPTR$ where $\alpha(n)\ge 1$ ?


texts: Measures of performance in machine learning

texts:
I'm new to machine learning and struggle to interpret the results I get from different measures of performance. If for several prediction models I have e.g. accuracy, precision, recall, F1, FPR, and MCC and want to find out which model performs best, what do I look for? I would assume accuracy is most important?

Also, what influence does the error have on the interpretation? E.g. method 1 has an accuracy of 87 +- 5% and method 2 has 84 +- 5% I would assume method 1 to be better. Is that correct?


texts: What does big O mean as a term of an approximation ratio?

texts:
I'm trying to understand the approximation ratio for the Kenyon-Remila algorithm for the 2D cutting stock problem.

The ratio in question is $(1 + \varepsilon) \text{Opt}(L) + O(1/\varepsilon^2)$.

The first term is clear, but the second doesn't mean anything to me and I can't seem to figure it out.


texts: Tracking Solution with Multiple Matrices in Dynamic Programming

texts:
We recently figured out a Dynamic Programming solution to compare two trees using concepts of edit distance in strings. It goes something like this-

$A[i', i, j', j] = \min \begin{cases} B[i', i-1, j', j] + c(i) \\ \min_{j_1 \le k \le j} \{A[i',  p(i),  j_1, k] + B[p(i) +1, i-1, k+1, j] + d \}
\end{cases}$

$B[i', i, j', j] = min\begin{cases} B[i', i-1, j', j-1] + c(i,j) \\ A[i', i, j', j]
\end{cases}$

We start at $B[0, 0, 0, 0]$ and finally obtain the answer at $B[0, n, 0, n]$

My question is how do we trace back the solution? This is the first time I see an addition of two different matrices while finding a minimum (see the second condition in A). Is there a standard way of tracing back for such algorithms?


texts: Can the runtime of functions with no loops change with the number of calls?

texts:
How can we perform time complexity analysis on a function that has no loops?

int somefunction(int param) {
  if (something)
    do this;
  else
    do this;
}

Would the time complexity of this function change depending on how many times the function is called within a program? I currently believe that the time complexity is O(n), because it is dependent on the amount of times that we call it.


texts: Do quantum logic gates work differently than traditional logic gates?

texts:
In a traditional computer calculations are done with logic gates that check inputs with AND gates etc. But in a quantum computer, are calculations performed differently since the qubit can be in states other than 1 or 0?
I understand that qubits can have values other than 1 and 0, however, before it is used as input into a logic gate, does the qubit need to be observed and defined as either a 1 or a 0? Or is the logic gates used in a quantum computer fundamentally different from a traditional computer?


texts: Converting Turing machine into the source code in industrial programming language?

texts:
Are there methods how to convert Turing machine (e.g. neural Turing machine or other rigorous Turing machine) into the source code/program that is written in some industrial programming language like C++, Java, JavaScript? There is a lot of work on Turing machine synthesis reinforcement learning, but it is very important to convert such inferred results into a programming language. One should be able to do that because of meta-interpretative learning that allows inferring new predicates/functions and allows to use compositionality for the program synthesis.

Here is a question that asks for a compiler that compiles code in languages such as C++/Java into Turing machines. Stackexchange has not come up with the answer up to now, but some examples are provided in comments, notably, the Turing machine compiler from the Ruby language.

My question is whether the disassembler (transpiler, re-compiler) that takes Turing machine as input (there are low level languages that describe the Turing machine, see for example here — some kind or Turing ASM) can translate this WB language program into Java, C++, Haskell or other high-level programming language that have functions, predicates and higher-order structures.


texts: How did we go from Binary to something like Python?

texts:
If there's one thing the pandemic has shown us its that High school Geometry did not save us. I am a high school math teacher and I understand my job and its usefulness only exist in a post scarcity economy. That being said, my Principal is making me teach computer science as an elective, a subject I never studied in college, I was a pure math major my minor was in finance and I got questions for you big brains. I re-enrolled into my old CUNY non matric to take some computer science courses to better service these kids.
I have a firm understanding of how binary works as an input for computers and I like to believe my students have one as well. Right now were exploring ASCII and representing alphabetic symbols using binary, but I myself don't know how computer scientists made the jump from 1's and 0's to something like python. If yall got the time and would like to help me understand that bridge I'm all ears. In the mean time I'll continue my research and do my best to show these kids something worth wild.


texts:
I am having trouble solving the following task:

  Given is the language $$D=\{ \langle M, w \rangle \mid \text{$M$ is a Turing machine and $M$ enters all states on input $w$}\}$$

  Prove that $D$ is not decidable by reducing $$A_{\mathrm{TM}}=\{\langle T, w \rangle \mid \text{$T$ is a Turing machine and $T$ accepts $w$}\}$$ to $D$.

My solution and proof idea

(I am not sure if they are correct.) Assume that $D$ is decidable. Let $R$ be a decider for $D$ and $S$ for $A_{\mathrm{TM}}$. We know that $A_{\mathrm{TM}}$ is not decidable. However, if we manage to show it is decidable using $R$ as subroutine, we derive a contradiction and have therefore shown that $R$ is not decidable either.

Now I have got to a point where I do not know further because I have problems finding ways of showig the contradiction since I cannot see a connection between entering all states and accepting input $w$. If the TM enters all states, it is still unclear if the input is also accepted.

I guess I have to run R on a modification of $T$ so that I can derive a contradiction.


texts:
I'm trying to solve the contiguous subarray problem on CodeSignal & I came up with the following solution which is based off of Kadane's Algorithm. My implementation passed the given test data set however upon submission, it failed. There's no reason given on CodeSignal & I can't look at it since I just started doing it & have less coins.
I can't figure out why my solution is failing but the solution based on online pseudo code works, even though my solution passed the preliminary tests. I think it might have to do with integer overflow or some other reason that's why I've come here to seek help from experts.
My implementation:
 public int findConsecutiveSubarray(int nums[]) {
    int currentSum = 0;
    int max =Integer.MIN_VALUE;;

    int i=0;
    while(i < nums.length) {
        currentSum += nums[i];

        if(max < currentSum)
            max = currentSum;

        if(max < nums[i]) {
            max = nums[i];
            currentSum = nums[i];
        }

        i++;
    }
    System.out.println("maxSum : "+ max);
    return max;
}

Solution based on online:
int arrayMaxConsecutiveSum2(int[] nums) {
        int currentMax = 0;
        int globalMax = 0;

        globalMax = currentMax = nums[0];

        for(int i=1; i<nums.length; i++) {
            currentMax = Math.max(nums[i], currentMax + nums[i]);
            globalMax = Math.max(globalMax, currentMax);
        }

    return globalMax;
}


texts:
I don't even know the right words to describe my problem, so I'll start with an example:

"aabaa", "ccrcc", "ffaff" are equivalent to some extent, because they all have the same length and follow the same formula: twice one letter, once another letter and finally twice the first letter again.

As I said, I lack even the vocabulary to describe this commonality of structure, so the first part of my question is: what is this kind of structure called and how is it studied?

The second part of my question is: do you know of an algorithm to transform a string into a representation of its structure? Or maybe more simply, an algorithm that would assess if two strings share the same structure?


texts: Saving information from reaching definition

texts:
I am learning about compilers at the moment and in my textbook it is briefly mentioned that UD/DU (Use-Def, Def-Use Chains) a way of saving information from the reaching definition is. It is just said that, when a variable is used, it has a list of the reaching definitions.

The problem that I am having is, that I am not clearly understanding the way this information is being used. How can this help the compiler optimize the code? Are there any other ways of saving (using) this information?


texts: How hard can identifying non-membership in a semi-decidable language be?

texts:
A language is called semi-decidable if there is an algorithm for identifying members. There are well-known examples of semi-decidable languages where identifying non-members is equivalent to $\emptyset'$, such as the Halting Problem.

My question is: how hard can identifying non-membership be?


texts: Number of binary search trees with maximum possible height for n nodes

texts:
I'm using the definition of the height of a tree as the longest possible path from the root to a leaf by its number of edges, e.g. a tree of 2 nodes has a height of 1.  With that in mind, what would be the number of binary search trees (don't have to be balanced) that have the maximum possible height for n-nodes?

So far, I know that the maximum height of any binary search tree of n-nodes is n-1 since we're counting edges.  So for example, a binary search tree of 3 nodes has a maximum height of h = 3-1 = 2 and there are 4 possible trees with n-nodes that have the maximum height of 2.

I also know that for n-nodes, there are (2n)!/((n+1)!n!) possible trees.

I'm able to find this manually for trees where n is small but would like to find a formula for any n.

EDIT:
The BST definition I am working with defines a Binary Search tree as a binary tree where each node has at most 2 children and does NOT need to be nearly-complete, so you could have a tree of 3 nodes with a height of 2.  It also satisfies the BST property where all nodes in the left subtree of a node x has keys smaller than x's key and all nodes in the right subtree of a node x has keys larger than x's key.


texts:
In ext4 file system, the files are spaced out as far apart as reasonably possible to allow for efficient reallocation. Why do we not do this in memory?

Why not allocate one memory as page 20, and the next large allocation as page 100 to allow for excess expansion before and after the current allocation? I feel that makes sense for large frequently changing-in-size buffers. For smaller buffers, doing so would probably be a drain on memory because we have to allocate each page for a small amount of bytes(but perhaps do it within a block too in the malloc impl). This would also provide greater memory corruption prevention, allowing segfaults(or windows equivalent) to happen quicker(specifically for larger buffers).

Why don't we do this? I get it on modern 32-bit systems because of limited address space, but why not on 64-bit?


texts: Definition of NP-hardness for non-decision problems

texts:
As I understand, the term "NP-hardness" is applicable when we also talk about optimization or search problems (i.e. return the satisfying assignment for 3-SAT). How do we formally define NP-hardness for such problems? The standard definition:

The problem is NP-hard when any problem from NP is polynomial-time reducible to this problem

doesn't make much sense, because of how the reduction is defined:

Language $A$ is polynomial-time reducible to $B$ if there exists a poly-time computable function $f$, such that $x \in A$ iff $f(x) \in B$.

The problem is that $B$ (e.g. our search problem) doesn't define a language (there may be other equivalent definitions, such as $A(x) \in \{true, false\}$, but they'll lead to the same problems).
My friend suggested that we can define a second poly-time computable function $g^{-1}$, which converts an "answer" for $B$ to answer for $A$: $x \in A$ iff $g^{-1}(B(f(x)))$ is $true$, where $B(y)$ is any correct answer for $y$. This makes sense, but I've never seen that.
So, what's the standard definition? For an answer, I would also ask for an appropriate citation (not to Wikipedia or random slides).


texts: Why is it that O(N + P) where P < N/2 reduces to O(N)?

texts:
My book says that

  If $P < N/2$ then we know that N is the dominant term so we an drop the $O(P )$."

If it was $O(N + P)$ where $P > N/2$ what would it reduce to?


texts: why should I go for logistic regression?

texts:
I am a student working on a Database management project with a bit of Python coding involved. The project is about Review Analysis.Basically I am trying to read a review and determine how good or bad it is.

I have a file of good and bad words with its scores like :: good = 2, better =3,best=4;

By this , I have written a code for sentiment analysis of the review which gives me the score of the review considering every single word.

Since the range varied from - infinity to + infinity, I had to scale it down to a range of 0 to 1.
A graphical representation must be done on this data; i.e. the score of review ,may it be from -infinity to +infinity or 0 to 1.

I was advised to go for logistic regression plot by my guide.
Why logistic regression? Is there a better way?


texts: What is the Best and easiest way to create a Classifer for Sentiment Analysis

texts: Sentiment analysis using Machine Learning is a hot topic. In the present situation when a person doesn't have a problem in having the training data set then which way should we create the classifier possibly the NaiveBayes classifier?


texts: What's the difference between phi and lambda in regular expression?

texts:
I've been learning on Formal Languages and Automata of Peter Linz(6th edition).
In the chapter 3 of this book, it explains the primitive regular expression.

But I don't know what is the difference between $\phi$ and $\lambda$.
Of course, I know $\lambda$ means the empty string, so that $\lambda s=s\lambda$.
And the textbook explains the meaning of $\phi$ is the empty set.
And more, the textbook explains that $\phi$ can be accepted by a deterministic finite automata $\left< Q, \Sigma, \delta, q_0 , F \right>$ in which $Q=\{ q_0, q_1 \}$, $\forall a \in \Sigma:\delta(q_0,a)\text{ is not defined}$, and $F=\{q_1\}$.

So, I guess the meaning of the $\phi$ is the rejected string.

But How can the expression $(\phi *)*$ mean $\lambda$?
And what's the meaning of the expression $a\phi$?


texts: Is there a universal identity or zero value for folding?

texts:
I'm using Haskell notation for illustration, hopefully it is known widely enough for this to make sense.

In the following fold function the second argument is what I'm calling the identity:

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

It is trivial to fold/reduce over a list of values with certain operations such as addition or multiplication. e.g.

mySum :: (Num a, Foldable t) => t a -> a
mySum = foldr (+) 0   --NB. Works because 0 is the additive identity

myProduct :: (Num a, Foldable t) => t a -> a
myProduct = foldr (*) 1  --NB. Works because 1 is the multiplicative identity

But not all operations have an obvious identity value.

My question is whether there is such thing as a universal identity value, or a function whereby you can find the identity value, or if you can contrive a scheme so that there now is one.

i.e. can you somehow define a z value such that:

foldrUniversal :: Foldable t => (a -> b -> b) -> t a -> b
foldrUniversal f = foldr f z

or could you have a function that determines it:

findIdentity :: (a -> b -> b) -> z  --is this possible?

foldrUniversal f = foldr f (findIdentity f)

or can you use some trick so that you always have an identity value even if you don't know what it should be?

(Note that I'm not stuck on a programming problem.  I already know about foldr1 in Haskell, or using the head of the list as the identity and then the tail of the list as the list argument.  I posted in cs.stackexchange instead of StackOverflow because I'm interested in the theoretical possibilities.)


texts: Ε-R diagram with conditions , is it possible?

texts: I want to create a database and model it with an E-R diagram. This database should be about a library. An entity is the member of the library, where the member can borrow books from the library. However , the member cannot borrow more than 5 books and cannot borrow any more books , if he hasn't returned every book of which the time to return it has expired. Ιs it possible to model this condition with an E-R diagram?


texts: Ensure groups of four 3-tuples have 9 unique numbers

texts:
Note: I know the numbers are arbitrary, but this problem about this size has practical implications. It is an applied algorithm problem.

Suppose you have 200 bins. Each bin would be very happy to have the integer sequence: 1, 2, 3, 4, 5, 6, 7, 8, 9. And the algorithm would be very happy if all bins get that.

The algorithm is allowed to choose four 3-tuples from a collection of 800 3-tuples. It will assign assign 4 of them to each bin. So each bin will have four 3-tuples assigned to them. These 3-tuples have the following properties:

They are pseudo-randomly generated all at once as a collection of 800 3-tuples.
Each number in a generated 3-tuple is unique. For example, (1, 1, 2) and (7, 4, 4) are impossible but (1, 2, 3) and (8, 2, 9) are possible.
Each value within the 3-tuple can only be a number from 1 to 9. For example, (10, 3, 15) is an impossible tuple. The 3 could occur, but 10 and 15 could not.

A corollary from point 1 is that it could be the case that some integers occur less than the amount of bins that exist. In such a case the application would be very happy if as many bins get a numerical sequence from 1 to 9 and the other bins get as close as possible to such a sequence. For example, suppose that the number 9 has been randomly generated in 180 3-tuples, then at least 20 bins will not get the number 9, but they hopefully should be able to get the integers 1 to 8.

Here is an example of 2 bins and 8 3-tuples. The following numbers are pseudo-randomly generated.

(3, 8, 2)
(2, 1, 5)
(2, 7, 8)
(7, 8, 5)
(7, 8, 4)
(7, 5, 8)
(7, 9, 5)
(4, 7, 3)

Assigning them to two bins as optimal as possible by the requirements yields:

Bin 1 - Sequence: 1, 2, 3, 4, 5, 7, 8, 9
(2, 1, 5)
(4, 7, 3)
(7, 9, 5)
(7, 8, 5)

Bin 2 - Sequence: 2, 3, 4, 5, 7, 8
(2, 7, 8)
(7, 8, 4)
(7, 5, 8)
(3, 8, 2)

Note: in this particular example there is no 6. There is one 1 and one 9. This means that the 1 and the 9 automatically go to Bin 1. The integer 6, well it simply isn't there, so it cannot be assigned to a bin.

My first question: Design an algorithm that ensures the most optimal solution.

My second question: is a generalized or analogous version known as a certain problem or field in mathematics?

I suppose this problem is a variant of the set cover problem. However, instead of covering a universe, 200 'universes' need to be covered. Or said in another way: the universe needs to be covered 200 times in such a way that the cover can be split up into 200 groups of four 3-tuples.


texts: Design a Turing Machine which accepts strings $x \# y$ where $x \ge y$

texts:
Imagine you are designing a TM where $x$ and $y$ are binary representation( $x \ge y$). the TM should accept $1101\#1001$ and reject strings such as $110\#10001$, as well as it could reject if you have more than one $\#$ or less than one $\#$.

Now, I have tried doing this. my idea is that:

For step one is to mark the left side first input as X, then scan to the right until you find a # sign, go to step 2, else if # sign not there reject
For step 2, zigzag left most side and compare each input to compare the 1's with each other. but i think i'm way off.


texts: Why does the author say that the sender in GBN protocol resends packet n to N(window size) when ack for packet n gets lost?

texts:
I was reading about the comparison of TCP with GBN protocol and I came across this text in the book Computer Networks: A Top Down Approach, 6th Edition by Jim Kurose on page 249;

Consider also what happens when the sender sends a sequence of segments 1, 2, . . . ,
N, and all of the segments arrive in order without error at the receiver. Further suppose
that the acknowledgement for packet n < N gets lost, but the remaining N – 1 acknowledgments arrive at the sender before their respective timeouts. In this example, GBN
would re-transmit not only packet n, but also all of the subsequent packets n + 1, n + 2,
. . . , N. TCP, on the other hand, would re-transmit at most one segment, namely, segment n. Moreover, TCP would not even re-transmit segment n if the acknowledgement
for segment n + 1 arrived before the timeout for segment n.

I don't understand why the author says GBN behaves this way when instead GBN receiver sends cumulative acknowledgements and the GBN sender should have no problem even if an ACK is missing when higher ACKs have been received before timeout.
Any input here would be appreciated.


texts: Find maximal subset with interesting weight function

texts:
You are given $n$ rows of positive integers of length $k$. We define a weight function for every subset of given $n$ rows as follows - for every $i = 1, 2, \dots, k$ take the maximum value of $i$-th column, then add up all the maximums.
For example, for $n = 4$, $k = 2$ and rows $(1, 4), (2, 3), (3, 2), (4, 1)$ the weight of subset $(1, 4), (2, 3), (3, 2)$ is $\max\{1, 2, 3\} + \max\{4, 3, 2\} = 3 + 4 = 7$.
The question is, having $m \leq n$, find the subset of size $m$ (from given $n$ rows) with maximal weight.
The problem looks trivial when $m \geq k$, but how can one solve it for $m < k$? Looks like dynamic programming on subsets could work for small $k$, isn't it? Are there other ways to do it?


texts: Expected search times with quadratic vs linear probing

texts:
Why exactly does quadratic probing lead to a shorter avg. search time than linear probing?

I fully get that linear probing leads to a higher concentration of used slots in the hash table (i.e. higher "clustering" of used  consecutive indices). However, it's not immediately trivial (to me at least) why that translates into higher search times in expectation than in quadratic probing, since in both linear and quadratic probing the first value of the probing sequence determines the rest of the sequence.

I suppose this has to do more with the probability of collisions between different probing sequences. Perhaps different auxiliary hash values are less likely to lead to collisions early in the probing sequence in quadratic than in linear hashing, but I haven't seen this result derived or formalized.


texts:
I wonder if there is a formula to calculate the sum of n/1 + n/2 + n/3 + n/4 + ... + 1. (Integer division)
The number n can be as large as 10^12, so a formula or a solution having the time complexity of O(logn) will work.
This is how far I can get:

The sum can be described as n * (1 + 1/2 + 1/3 + 1/4 + ... + 1/n). The series inside the parenthese is the Harmonic Progression which has no formula to calculate. So I don't think this can lead to a solution.

Playing with some numbers, this is what I get:

11 + 5 + 3 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1
10 + 5 + 3 + 2 + 2 + 1 + 1 + 1 + 1 + 1
9 + 4 + 3 + 2 + 1 + 1 + 1 + 1 + 1
8 + 4 + 2 + 2 + 1 + 1 + 1 + 1
7 + 3 + 2 + 1 + 1 + 1 + 1
6 + 3 + 2 + 1 + 1 + 1
5 + 2 + 1 + 1 + 1
4 + 2 + 1 + 1
3 + 1 + 1
2 + 1
1

So by skipping the number 1s, we can reduce the time by a half. If using a loop to calculate the sum, we only need to loop until n/2. Since the rest contains only number 1s.
I've been trying to come up with a formula to calculate the series that is not 1 + 1 + ... + 1.
Please help if you know the acceptable answer (a formula or a O(logn) solution).


texts: Is there an algorithm to switch from classical notation to concatenative stack-based notation?

texts:
Reading a bit about Joy, I was wondering if there wasn't an algorithm to switch from classical notation and style to concatenative and stack-based style.

Of course, for simple mathematical expressions without variables, for example, you just have to convert the expression into the inverted Polish form:

f = 3 + 5 * (7 - 1) / 2

→

f = 3 5 7 1 - * 2 / +

But what if our function has variables? It's easy to find ourselves the expected result when the expression is simple, like here for example:

square(x) = x * x

→

square = dup *

But for a more complex function, it becomes almost impossible to reason :

-- This is a Haskell code
qsort [] = []
qsort (x:xs) = qsort ys ++ x : qsort zs
    where
        (ys, zs) = partition (< x) xs

→

qsort =
    [small]
    []
    [uncons [>] split]
    [enconcat]
    binrec

(According to Wikipedia, in the page linked above.)

So, is there any way to make a computer do this kind of conversion? (Also, should the order of the arguments in a function be reversed?)

I haven't found any algorithm on the Internet that meets these expectations. It seems to me however to have searched well. I also imagine that a conversion like the quick sort function, as shown above, would probably be more complicated to generate, but I mean: the logic behind must be the same as a more simple expression.

My goal would simply be educational, I would be interested in seeing these conversions.


texts: Computational power of deterministic versus nondeterministic min-heap automata

texts:
This is a follow-up question of this one.

In a previous question about exotic state machines, Alex ten Brink and Raphael addressed the computational capabilities of a peculiar kind of state machine: min-heap automata. They were able to show that the set of languages accepted by such machines ($HAL$) is neither a subset nor a superset of the set of context-free languages. Given the successful resolution of and apparent interest in that question, I proceed to ask several follow-up questions.

It is known that deterministic and nondeterministic finite automata have equivalent computational capabilities, as do deterministic and nondeterministic Turing machines. However, the computational capabilities of deterministic push-down automata are less than those of nondeterministic push-down automata.

  Are the computational capabilities of deterministic min-heap automata less than, or are they equal to, those of nondeterministic min-heap automata?


texts:
Assuming P = NP, why should P be a subset of NPC?
Here is how I understand it:

P is a subset of NP
NPC is a subset of NP

if we solve an NP Complete problem on a deterministic machine in polynomial time then

NP is a subset of P
P=NP (from 1 and 3)
NPC is a subset of P (2 and 3)

But why is P a subset of NPC, if P = NP?
This question has been asked before and the answers just pointed to the definitions of NP, P and NP-C. I have gone through the definitions but still require a detailed picture.


texts: What is the most straight forward, easy to verify algorithm to construct a valid password from a character stream?

texts:
Let's say we are given an infinite character stream like the following:

nqDoo8NkPsDn0gVf(pAI)dwa^Vq7OfAgt@KDUkjN5ZXY1yK6w7ygW6S&@L0EsUEq9...

What is the most straight forward way to construct a valid password from the stream? A valid password must pass a number of conditions, for example:

At least 8 character long
Consist of both lower & upper characters
Consist of at least 2 special characters

(Or other common password validations)

In addition, the result should depends on the input stream. That is, a same input should result in a same password and a significantly different input should yield a different password (most of the time). This is because using same / very similar passwords for all users is no good for security concerns.

The algorithm should be as straight forward as possible so a human can easily verify the result, given the same character stream and set of conditions.

My first attempt:

Pick the first condition from the set. E.g. Consist of both lower & upper characters
Build a string that fulfills this condition. Skip any characters not taken. E.g. Take nD from the stream nqDoo...
Repeat for the other conditions and concat each of the result string. E.g. nD -> nD() -> ...
Pad with immediately upcoming characters to fulfill length requirements. E.g. nD() -> nD()dwa^

Problem 1:
The result depends on the ordering of the conditions which cannot be logically determined. I feel like this is unnecessarily implementation dependent and can be confusing without access to the source code.

Problem 2:
I am not sure how to handle special conditions such as "Do not contains dictionary words". Should I check after step 4 and start over with the unused characters if these special conditions fail? Yet another confusing step for verification.

What is a better algorithm?


texts: How to solve linear system with modulus operation?

texts:
I came across linear equation $G(x,y) = g_k(x,y) l_k(x,y)$ mod $(y^{2^{k}})$ while reading factoring algorithm see section 3 for bivariate polynomials. I need to find the $G(x,y)$ and $l_k(x,y)$.

Given : $g_k(x,y)$, where $deg_y(g_k(x,y)) < y^{2^{k}}$ and $deg_x(g_k(x,y)) < d $.
Find : $G(x,y)$ and $l_k(x,y)$. (non trivial)

I know that $G(x,y) = g_k(x,y) l_k(x,y)$ forms a linear system with $y^{2^{k +1}} \times 2d $ many equations and I can solve those equations. But I don't know how to solve correctly $G(x,y) = g_k(x,y) l_k(x,y)$ mod $(y^{2^{k}})$.

Here is a problem, suppose after multiplying $g_k(x,y)$ and $l_k(x,y)$, I got a term $y^{2^{k}}$, but after doing mod operation this term is going to become $0$. So my question is, how to resolve this issue.


texts:
Question: Assume there are $n$ distinct gifts on the real line. Their
positions are $\{x_1, ..., x_n\}$ and each of them has an individual
value $p_i$.
Now you can choose a subset of them such that any two gifts in your
choice are at a distance more than 5. What’s the maximum total value you
can get? Design an algorithm to solve this problem, analyze the running
time and prove the correctness.
You can assume the gifts are given in order of their locations, i.e.,
$x_1 < x_2 < ... < x_n$.
I have tried memoization and breaking down the problem into smaller
steps but I am not sure what this specific sub case would look
like.


texts: Data structures that store efficiently detected features of an image

texts:
I struggle to find this, suppose I apply any feature detection algorithm. From my references it seems to me it's not usually explained what kind of data structures would be suitable for storing such features.

For example in opencv it seems to me that the Canny Edge detector will return a matrix (I assume the code/gray level code is like relating high pixel value with the the feature in that specific pixel). I think it would be useful to know what data structures could actually be useful in this case to navigate through all the extracted features instead of iterating through all the pixels.

So the question is... in general (or at least line features) what data structure is usually useful? and how is such data structure constructed?

As a specific example... I'd like to extract all the edges of a given image, name such edges $e_1,\ldots,e_n$. Then I need to access to the pixels that lie both to the left and right of such edge(not all, just pixels that are close enough to $e_i$, for all $i$). Finally I need to perform some operations on such pixels.

To summarize something like:

$e_1,\ldots,e_n \leftarrow extractEdges(I)$

$\forall i \in \left\{ 1,\ldots, n\right\}$

$\;\; S_l \leftarrow pixelsLeft(e_i)$

$\;\; S_r \leftarrow pixelsRight(e_i)$

$\; \; doSomething(S_l,S_r)$

Above $I$ representes the input image.

Thank you


texts: Show that a regular language L contains only palindromes if and only if all words of length at most 3n are palindromes

texts:
This is an extension of a previous question asked by a different user earlier:

Let $x, u, v, w, y, x', u', v', w', y'$ be words satisfying

$y'x' = xy$.
$y'u'x' = xuy$.
$y'v'x' = xvy$.
$y'w'x' = xwy$.
$y'v'u'x' = xuvy$.
$y'w'v'x' = xvwy$.

Then $y'w'v'u'x' = xuvwy$.

Now, using the above result, show that a regular language $L$ recognized by an NFA $M$ consists purely of palindromes if and only if $\{x \in L : |x| < 3n\}$ consists purely of palindromes, where $n$ is the number of states in $M$.  When I say that some language "consists purely of palindromes," I mean that every string in the language is a palindrome.


texts:
In many to many multithreading model the processor threads are multiplexed to a lesser or equal number of kernel threads.
What exactly does it mean??
Does it mean that if a kernel is executing a blocking system call then the other threads will be shifted or multiplexed to other kernel threads??

Also is many to many a collection of many to one and one to one multithreads


texts:
I've been looking into computer assisted music composition lately for my school project. While searching for literature I came across GenJam, an interactive jazz improvisation software which uses genetic algorithms to produce musical phrases.

I was wondering If anyone has done some work on computer generated music and could suggest term papers, books or other reading material I should look into.


texts: is {a,b}* a regular language? And How to know a language is regular or not without using pumping lemma

texts: I still confuse what is a regular language. I read some books, i know if language likes (a^n b^m| n,m>0), it will be regular language since n and m are not related. I know using pumping lemma can prove a language is regular or not, but for this one{a,b}*, i don't know how to do it.


texts: The most efficient algorithm for finding the highest valid number for an API

texts: I have many API endpoints that take IDs that are constantly increasing. I want an algorithm to find the highest number in the least amount of requests. I need to do this without knowing what the previous highest number was. I am thinking something like binary search would work but would it be the most efficient? I also don't know what the maximum would be.


texts: time efficient key value store for fast lookup

texts:
Let's state a collection of key/values.

Key is an unsigned integer (0 - 2^32-1). Hense there are comparable.
Value is few bytes fixed size.

There are 4M items in the collection.
Keys are not evenly spread in the key space i.e there is no way to predict hole size between two consecutive keys.

This collection is created once and never modify after that, even if not prohibited.

The aim is to lookup a value by its key. But if key is not found then the previous one (as in integer natural order) must be returned.

I'm looking for a data-structure that can be mmap on disk which would be reasonably space efficient but most importantly very time efficient for
the lookup function.

There is no known pattern on how the keys are queried.


texts: Is there a measure of space usage over time?

texts:
We typically measure algorithm efficiency by space efficiency and then time efficiency e.g. this algorithm takes O(n) time and O(n) space.
However, I feel this does not capture the full story.

Say we have a process that looks like this. Assume memory allocation is O(1) time complexity for simplicity.

process(n):
  mem = allocate(n)
  for 0 to n:
    ... do O(1) stuff
  end
  free(mem)
  end

The above process takes O(n) time and O(n) space.

Here's another process that takes O(n) time and O(n) space.

process(n):
  for 0 to n:
    ... do O(1) stuff
  end
  mem = allocate(n)
  ... do O(1) stuff
  free(mem)

In the both processes you're using O(n) space. In the first one you're using the space over the course of the entire process. In the second, you're using it only at the very end. Is there a way to formalize the difference?


texts:
I'm trying to prove a language is not regular through using pumping lemma, but can't seem to come up with any way of doing it.

The alphabet is:

$$ \Sigma = \{c, d\} $$

The language is:

$$ A = \{z \in \Sigma^* \mid c(z) > d(z)\} , \text{where $c(w)$ and $d(w)$ means occurrences of $c$ or $d\in z$  }$$

I tried to define a string like so:

Pumping length = P

$$ s = c^{(P+1)}d^P $$

Here is how I tried to solve it:

If we select P = 5. Then s = ccccccddddd and split it in 3 parts. Where x = ccccccd, y = ddd and z = d. (Is that even allowed though as |xy| <= P, but now |xy|=10 and 10>5). If I then do y^2. Then I get s = ccccccdddddddd, so now d>c which proves the string is not in the language. Does this then prove that the language is not regular?


texts:
I am attending algorithms and data structures course in my University and my professor gave me an interesting question the other day. He told me to think about it.

What is a problem, a task, and a solution?

It seems to me like it's more of a philosophical question. All of those 3 things correlate to one another.

To me, it seems like if we have a problem, we then have a task to solve it, which we might be able to do with an algorithm, which is a solution.

What do you guys think would be the answer to this question? Does it have some kind of deeper meaning about algorithms, or am I just overthinking it?


texts: Complexity of finding an alternating Hamiltonian (x,y)-path in edge bicolored complete graphs

texts:
Let $G$ be a simple complete graph with an edge-2-coloring.  An alternating Hamilton (x,y)-path is a Hamiltonian path which starts at vertex $x$ and ends at vertex $y$ such that the colors of its edges alternate along the path. In [1], J. Bang-Jensen and G. Gutin pose the following problem:

  Problem 5.14 Is there a polynomial time algorithm for finding an alternating (x,y)-hamiltonian path in $G$ with $x, y$ given?

Does anyone happen to know the status of this problem? I believe the problem is in P if the endvertices are not specified.

[1] Bang-Jensen, G. and Gutin, G., Alternating cycles and paths in edge-coloured multigraphs: A survey, Discrete Mathematics 165/166 (1997) 39-60


texts: How do I do a biased shuffling of a deck of cards?

texts:
I currently have a deck of cards (in fact this deck is an array of sorted elements in descending order as indicated by the picture above), that I want to shuffle. However, the caveat is that I want the card near the top of the deck to be shuffled to a new position relatively close to the top, while a card near the bottom to be shuffled anywhere including the middle and bottom, but have a very unlikely chance of ending up near the top of the deck.

Therefore I would break down the problem as following:

A card in the top 33% of the deck has about:

90% chance of ending up in the top 33%
8% chance of ending up in the middle 33%
2 % chance of ending up in the bottom 33%

A card in the middle 33% of the deck has about:

5% chance of ending up in the top 33%
90% chance of ending up in the middle 33%
5 % chance of ending up in the bottom 33%

A card in the bottom 33% of the deck has about:

2% chance of ending up in the top 33%
8% chance of ending up in the middle 33%
90 % chance of ending up in the bottom 33%

The percentages of the shuffle do not need to be constant. I wouldn't mind if they were continuous probabilities across the entire deck. Would this boil down to a randomized selection problem? I have no clue as to how to approach this problem as of now.


texts: Optimizing AVL Tree operations for sequential data

texts:
I'm working on an implementation of a data structure that needs a tree-like data structure for accelerating look-ups.

The interesting part about this data structure is that the only operations on the AVL Tree are inserting and removing sequential integers in a stack-like fashion,

e.g.

Insert 0, 1, 2
Delete 2, 1
Insert 1, 2, 3
etc.

I have been using this site to gain some intuition about the problem.

AVL Trees seem to behave wonderfully for this situation, and I'd like to see how far I can take it. Specifically, I have the following conjectures that I would like proven/disproven:

Inserting sequential keys results in zero or one left rotations.
Deleting sequential keys results in zero or one right rotations.
Given only the number of nodes in the tree and the next operation (insert or delete), we can determine whether a rotation needs to be performed, either a single-left or single-right, along with the key of the node that needs to be rotated in O(1) time with O(1) extra space.

If these turn out to be true, height information doesn't have to be stored/updated for such a tree, making AVL Trees optimal for this particular application. I'm pretty sure that #1 and #2 are true, but #3 is the one I'm stumped on.

Note that this intended to solve the same problem as building and maintaining an optimal search tree given sorted inputs. If a simpler solution exists than thinking about the problem in terms of AVL Trees, I would be interested in that, as well. However, the implementations I have seen so far seem more limited and cumbersome, since they rely on a finalization step.

Also note that for #3, knowing how many levels up a rotation needs to happen is equally (perhaps even more) valuable.


texts: How to compare two circular sequences in linear time?

texts: We have two circular sequences, which means there is no start or end in the sequences, how to test if two sequence are equal or not in linear time? I have two circular sequences of E. Coli bacteria with length (4,639,221). I thought about attaching two sample of the first sequence and find the other one in it in linear time, but I was looking for a better idea, using a suffix tree is a suggestion that I think works for this problem.


texts: Piecewise defined polynomial time complexity?

texts:
As part of my research, I have recently written an algorithm for mining medical data. We are looking to potentially publish some of the data we collected however I would like to describe the algorithm I used in detail.

I was really curious about the algorithm so I recently programmed a dummy data generator and tested the algorithm. To my surprise, a simple plot of overall time vs. N (number of input arrays) yielded an almost perfect polynomial fit below N = 100000 and a secondary almost perfect polynomial fit at N >= 100000.

I am curious about potential explanations for this behavior and would be interested in learning more.


texts:
I was reading about decision problem. I understand that decision problem tell yes/no answer for an input. The decision is based on a decision procedure also called an algorithm.

The wikipedia says that

  It is traditional to define the decision problem equivalently as: the set of inputs for which the problem returns yes.

  These inputs can be natural numbers, but may also be values of some other kind, such as strings over the binary alphabet $\{0,1\}$ or over some other finite set of symbols. The subset of strings for which the problem returns "yes" is a formal language, and often decision problems are defined in this way as formal languages.

Whether I can take it like algorithm written in a programming language defines the set of all possibilities and gives the output based on the input?

So in computability theory, the problem should be encoded to some form? Is this same thing as the input tape and configuration of a Turing machine (set of 0's and 1's )?


texts: Some questions about the Computability of Turing Machines

texts:
I'm learning for a test and I have some important questions about Computability of deterministic and non deterministic Turing Machines.

Consider we have the partial functions $f,g,h,t: \mathbb{N} \rightarrow \mathbb{N}$ with $f$ is Turing Machine computable, $g$ not Turing Machine computable, $h$ is not While solvable and $t$ is While computable. Are the following answers correct? And is there anything changing if we had an non deterministic TM?

There is no proof to do words are ok :)

Is $f \circ g$ Turing Machine computable?
Is $g \circ f$ Turing Machine computable?
Is $t \circ h$ While computable?
Is $h \circ t$ While computable?

My answers:

First of all, we know that Turing Machine = While Computability. (#)

I would say, that we do not know if it is or is not TM computable, because there may a TM who can handle the output of an not TM computable function.
I would say no, because if whatever $g$ takes, it won't be TM computable.
and 4. Because  of (#) it is the same like 1. and 2.

Could that be right? It is for an multiple choice test and those questions are tricky.


texts:
I have two sets, let's call them C and T, of unpaired points, which could for example represent two types of cells. Hence, both points are drawn from the same underlying distribution, but the points in T underwent an additional process/function.
Although biologically debatable, I want to find the most similar points in the T set for each point in the C set. It does not need to be a 1:1 mapping, 1:n is also possible, because the sample sizes might be different.
How can I find such a mapping? Do you know any algorithms (or have other ideas) to achieve this?
First, I thought it makes sense to span a graph in both sets by drawing edges between points which are below a certain distance. The distance for each set has to be such that the number of vertices with n edges are approximately the same in both sets. Afterwards I could match all points with k neighbors in set C, with all points with k neighbors in set T. Although I have not implemented this yet, I am unsure how efficient this will be.


texts: Why are random numbers important to the study and application of computer science? I am new to computer science. So I am studying random numbers right now.


texts: Configuration of a space bounded turing machine

texts:
A configuration of a Turing machine is defined as the following:

an ordered triple $(x, q, k) ∈ Σ^* × K × N$, where $x$ denotes the string
on the tape, $q$ denotes the machine's current state, and $k$ denotes the
position of the machine on the tape.

I have read in a paper that a space-bounded non-deterministic Turing machine has at most $2^{dn}$ configurations on an input of length $n$, where $d$ is a constant. How do we know that this is true? What is $d$? How can we prove it?


texts: Why is the weight matrix diagonal in weighted least squares regression?

texts:
I was going through the theory for weighted least-squares fitting and I understood its basic underlying concepts, but I couldn't understand why exactly do we keep the weights as a diagonal matrix during calculations.
This might be a dumb question but I don't have much experience with matrices and I am in the process of using them to solve more real-world problems so any input will be helpful.


texts:
Here we see a very interesting attempt to show that $\mathrm{P} \ne \mathrm{NP}$ by Norbert Blum.

Here we see 116 previous attempts at solving P vs. NP.

Here we see the P vs NP problem defined as:

  The informal term quickly, used above, means the existence of an algorithm solving the task that runs in polynomial time, such that the time to complete the task varies as a polynomial function on the size of the input to the algorithm (as opposed to, say, exponential time).

Here the commentator writes:

  I think it's even less useful, even if P = NP it is possible that no one finds an algorithm. Creating a (useful) algorithm is independent of proving the theorem. Also interesting is that someone could create an algorithm that solves NP complete in polynomial time without proving P=NP. They would be unable to prove the algorithm correct though.

My question is: What is the utility of proving P=NP if we can't find an algorithm that can solve any NP problem in polynomial time?


texts:
How do you suggest I go about proving this:

Give a short, basic outline of a proof that Turing machines can accept all languages accepted by PDAs. You are allowed to use a non-standard Turing machine.

The best I can come up with is that since TMs are equivalent to computers, where as PDAs are not. A TM accepting any PDA-accepted language is understandable. (Church-Turing thesis)

BTW, I know PDAs accept CFLs, but is that all they accept?


texts: Is a Turing Machine that only takes strings of the form $0^*$ Turing Complete?

texts:
You have a Turing machine that only processes input on the form $0^*$. If it is given an input without 0's, it will simply halt without accepting or do anything else. Is it Turing Complete?

The set $0^*$ is countably infinite, since you can make the bijective function $f(x) : 0^* → \mathbb{N} $:

$f(x) = length(x)$

Where $length(x)$ is the length of the string (so you treat them as Peano Numbers).

I understand that the set of all programs (the programs that a Turing machine can run) are countable, and that the set of a Turing machines are also countable. But, can the set of string that the Turing machine can process (with no guarantees of halting) only be countably infinite (as in this case), or does it have to be uncountable?

My understanding of undecidable problems with regards to Turing machines is that they arise because there are languages that have a cardinality strictly greater than the natural numbers, e.g. $B^*$, where $B = \{0,1\}$, which has a cardinality equal to the real numbers. It seems to me that, although you can encode any integer with the language $0^*$, you can't encode an arbitrary language. The problem is: how can you encode recursively enumerable languages when all you have is unary notation? If this is indeed impossible (though I have a feeling it is possible; I can't see how the representation of numbers should be a fundamental hindrance), then it turns out that this particular Turing machine is not Turing Complete (or maybe you would say that it is not really a Turing machine).


texts: Given a regular language $U$, when does there exist $V$ such that $U^\omega$ = $\lim V$?

texts:
What I know is that $W = \lim V$ for some $V$ if and only if $W$ is the language of some deterministic buchi automata, namely that of $V$.

So, to attack this problem I tried to come up with some language of the form $U^\omega$ which cannot be determinized. But I keep failing trying to come up with something like this.

Is it true in general that given regular $U$, there is some regular $V$ such that $U^\omega$ = $\lim V$?


texts:
Given N points in a 2D plane, if we start at a given point and start including points in a set ordered by their distance from the starting point. After including every point, we check if there is a convex hull possible, we move all these points to a visited set and continue. Every time we determine a convex hull, we only move the points to the visited set if the so constructed convex hull contains all the points from the visited set.
How can we do count such convex hulls in as efficient manner as possible?


texts: Computational complexity of function $U^V$

texts: Given $(U,V)$ two integers of finite size, I have a question about the complexity of calculating the $V^U$, i.e. $V$ raised to the power $U$. Is their a polynomial time algorithm to do this? If not is this an NP-hard problem?