texts: Day-Stout-Warren algorithm for balancing BST. How does vine to tree work?

texts:
I was trying to understand the dsw algorithm for balancing a binary search tree in-place using this virgina tech page.

The wikipedia page and vt page are more or less similar. I am having a hard time trying to understand the underlying logic and also the functioning of the vine-to-tree method.

Correct me if am wrong.I am going by the vt page.
Initially in the vine-to-tree method , n = 9 , M=7 , so we make n - M = 2 rotations.( They just say to make 2 rotations , but are actually making rotations on alternate 2 nodes ).

The tricky part around which I am not able to wrap my head around:

While ( M > 1 )
  M = M/2;
  Make M rotations starting from the top of the backbone;

Since M is initially 7 , we would make (7/2) 3 rotations first time in the loop , and (3/2) 1 more rotation in the second iteration of the loop. However from the pictures below , the tree got balanced after just 2 rotations. Is some end condition missing in the page. Also nowhere is it mentioned to balance only alternate nodes , but they seem to be doing that.


texts: Lower bound on competitive ratio of $m$-machine scheduling

texts:
Given a sequence of positive reals $a_1, a_2, \dots, a_n$ and an integer $m$, for each $j$ assign $a_j$ to a machine $i$, $1< i < m$, so as to minimize the maximum, over $i$, of the sum of all reals assigned to machine $i$.

Theorem: There is no randomized $m$-machine scheduling algorithm with a competitive ratio less than $4/3$ for any $m \geq 2$.

The following is the Proof Sketch given in the paper:

  Consider the job sequences $m \times 1$ and $m \times 1, 2$. (Here $m \times 1$ denotes a sequence of $m$ 1’s.) If the algorithm schedules the $m$ 1‘s on $m$ different machines with probability $p$, the worst-case ratio between its cost and the optimal cost is at least $\max\{2 – p, 1 + p/2\} \sim 4/3$.

I have problem understanding the proof. I would really appreciate if anyone can explain the proof in details, especially how to arrive at the worst-case ratio of $\max\{2-p, 1+p/2\}$.


texts:
I am working on the following problem:

Suppose that $T$ is a spanning tree of a graph $G$, with an edge cost function $c$.  Let $T$ have the cycle property if for any edge $e' \not \in T, c(e') \geq c(e)$ for all $e$ in the cycle generated by adding $e'$ to $T$.  Let  $T$ have the cut property if for any edge $e \in T$, $c(e) \leq c(e')$ for all $e'$ in the cut defined by $e$.
Show that the following three properties are equivalent

T has the cycle property,
T has the cut property, and
T is a minimum cost spanning tree.

I believe that to show that 3. implies 1., we suppose otherwise, and then show that this would give a cycle with an edge that can replace another edge in T and that is cheaper, whence we have a contradiction.  Similarly, I believe to show that 3. implies 2., we similarly suppose otherwise, and then show that this would give a cut with an edge that can replace another edge in T and that is cheaper, whence a contradiction.
However, I am not sure how to prove the other implications needed for this problem.  My feeling is to somehow use a similar argument to what I listed, but "in reverse".
Any help with this problem would be greatly appreciated.


texts:
Consider the usual RGB color palette, for which each color (red, green, blue) has $256$ distinct intensities. Can the set of all $2^{24}$ colors be expressed as a ternary linear code? If so, give a basis. If not, explain why not.

I'm confused on how to solve this because I've only worked with binary linear codes. Can somebody please walk me through it?


texts: Motivation for Inverse Reinforcement Learning

texts:
Learning a policy from sparse reward information (a reward function where a positive reward is only generated at the goal state) is challenging due to the resulting sparse feedback.
One solution is to shape the reward to enrich feedback during learning. Unfortunately, shaping the reward is challenging and often leads to unusual behavior or even situations where the learning agent just harvests intermediate rewards rather than achieving the task.
A proposed solution is to have an expert generate demonstrations of the desired task and have the learning agent learn a reward function that is consistent with the demonstrated behavior. The learning agent can then use this learned reward function to learn an optimal policy.
This last point is where I am confused. The whole motivation for IRL is learning, that is, finding a policy when the model is unknown, but why would the learning agent not know its own transition model? On the other hand, if the transition model is known, then finding the optimal policy from the learned reward function is not actually a learning problem.


texts: Measuring the Union of Products of Intervals

texts:
Verbose Motivation for this Question

Inspired by this paper about how the problem of counting unlabelled subtrees that are unique up to isomorphism is #P-complete, I was thinking about the problem for the specific case of caterpillar graphs. (a caterpillar graph, $C$, will become a path graph, $P(C)$, by removing all their leaves) This lead me to an interesting subproblem, where, given an array $[l_0,l_1 \dots l_d]$ you need to compute:

$$ \sum_{i=0}^d \int \bigcup_{k=0}^{d-i} \prod_{j=k}^{k+i} [0,l_j]$$

Here, we are taking a Lebesgue unit measure of a union of $(i+1)$-dimensional intervals. (for each cartesian product, the length of 1st dimension is $[0,l_k]$, and the $m$th dimension is $[0,l_{j+m}]$) This monstrous equation arises due to the partial-order of possible sub-trees which include exactly $(i+1)$ vertices of $P(C)$. (in the actual problem, it's a little complicated, because you have to account for over-counting due to symmetry that occurs from reversing the order of your array, but for now I'll just concern myself with the cleaner subproblem)

My actual questions

I'm curious about computing the Lebesgue unit measure of the union of $n$ $i$-dimensional intervals which are each defined by a list of $i$ 2-tuples which are represent a cartesian product along orthogonal axes.

What's the complexity of measuring the union of $n$ $i$-dimensional intervals? (I found that this is Klee's measure problem, we specifically have $O(n^{d/2})$ for dimensions $d \geq 3$, and $O(nlog(n))$ for $d =1,2$)
Are there significant improvements in the case were intervals have some obvious partial-order? (ex: each interval is a subset of $[0, +\infty]^i$, and have a corner at $[0]^i$)
Similarly, are there note-worthy improvements if we restrict ourselves to intervals whose corners all belong to $\mathbb{Z}^i$?

Upon further consideration, I feel like the answer to this question might be quite useful for my second question. However, I am still unclear exactly what's the best way to calculate measure once we've identified the relevant intervals, and if the $O(nlog(n))$ sorting generalizes to higher dimensions.


texts: Divide and Conquer Algorithm to calculate $a^n$

texts:
I am attempting to create an algorithm which given the value of $a \in \mathbb{R}$ and $b \in \mathbb{N}$, calculate $a^n$.

So for example, using the Java language pattern, the algorithm will be defined as follows:

public double exp(float a, int n) {
    ...
}

But I am unable to determine what would be possible sub-problems of this problem as there is not set from which I can create subsets.

How can I achieve this using a divide and conquer method?


texts: Constructing Tree (forest) from Ancestor function

texts:
Question:

Suppose I have a

set of male people, and
a function isAncestor(person1,person2) that checks whether person1 is an ancestor of person2 in O(1) time. Eg, isAncestor(grandfather, grandson) would return true.

What are some fast algorithms for constructing a complete "family tree"  by using only this information? (or "family forest" as not everyone may be related to a single common ancestor).

Comment:

This is not homework or from a book. It is derived from some issues I'm having coupling an adaptive finite element code to some blackbox mesh generation software, boiled down to the core problem and expressed in an analogy that shares the same mathematical structure. Right now I have a brute-force $O(n^3)$ method that seems horribly inefficient.

Thank you for any help.

Results:

I've implemented Gilles suggestion in Matlab and tested it. Here is the pseudocode, code, and unit test script. I release it all to the public domain.

Pseudo-code:

function buildAncestorForest
    roots = empty list
    for each person p
        roots = graft(p, roots)

    subfunction new_roots = graft(q, old_roots)
        descendents = empty list
        nondescendents = empty list
        for each person t in old_roots
            if q is an ancestor of t
                append t to descendents
            else
                append t to nondescendents

        if descendents is still empty
            q_is_incomparable = true;
            for each person t in old_roots
                if t is an ancestor of q
                    new_roots = old_roots;
                    new children of t = graft(q, old children of t)
                    q_is_incomparable = false;
                    break for loop
            if (q_is_incomparable)
                new_roots = append q to old_roots;
        else
            new_roots = append q to nondescendents;
            for each person t in descendents
                children of q = graft(t, children of q);

Matlab code:

https://github.com/NickAlger/MeshADMM/blob/master/buildAncestorForest.m

Unit test script:

https://github.com/NickAlger/MeshADMM/blob/master/test_buildAncestorForest.m


texts: Basic complexity theory (in Oracle Separation of BQP and PH)

texts:
I have some basic questions about complexity theory that came up when I tried to understand the result by Raz and Tal that BQP$^O\nsubseteq$ PH$^O$.
Aaronsons paper was helpful, but I still have some questions left.

Raz and Tal derive Corollary 1.5 from 1.4 "by the relation between black-box separations and oracle separations", but aren't those the same thing? I thought the following all mean the same:

black-box model
oracle model
relative/relativized problem
query complexity

It would make more sense to me if Corollary 1.5 follows from 1.4 by the relation between promise problems and decision problems in the black-box model.
I am not sure how to interpret the fact that there is randomness in the problem. I think of a class such as BPP as languages solvable by a regular Turing machine with access to a random tape, which can make an error with a constant probability over its random bits. However we need to consider the worst case instantiation of the problem (right?). For a language to be in PH, there needs to be a PH-machine (without access to randomness) that does not fail on any input. Now for any oracle-output coming from one distribution there is a non-zero probability that it was actually generated by the other distribution, so the PH-machine will be wrong sometimes. Why is that argument not sufficient to show that the problem is not in PH (or any other "zero-error" class for that matter)?
What exactly is meant by an AC$^0$ circuit with access to an oracle? I've seen this described as "a circuit with access to the oracle's truth table", which I could understand if the oracle solved a decision problem $f: \{0,1\}^n \rightarrow \{0,1\}$, then the circuit input nodes are $x_i = f(i)$ for $i \leq 2^n$. However, here the oracle samples from one of two distributions on $\{\pm 1\}^{2N}$ and the circuit is defined as $A: \{\pm 1\}^{2N} \rightarrow \{\pm 1\}$. Does that mean the circuit only gets access to a single query output?


texts: What does "associative" exactly mean in "n-way set-associative cache"?

texts:
I'm trying to grasp what does associative actually mean in n-way set-associative cache. I understand n-way set-associative cache as a concept; n is the degree of associativity, i.e., how many cache lines a set can hold.
If I take associative to mean "having the tendency to connect", I get to the "sets tend to connect to...", what, memory addresses?
But I'm not sure if this is the correct understanding.


texts: Isn't std::bernoulli_distribution inefficient? Designing a bit-parallel Bernoulli generator

texts:
C++11 has a convenient Bernoulli RNG, illustrated at
http://en.cppreference.com/w/cpp/numeric/random/bernoulli_distribution .
However, distilling an entire random integer into a single random bit seems inefficient when the expectation parameter $p$ is rational with a small or power-of-two denominator.
Is there a reasonably fast way to generate 32 random Bernoulli bits at once in such cases? My application uses long streams of bits, so I can keep track of statistics if needed (but this would consume runtime).


texts: finding a an object with constant velocity on an infinite grid in discrete time steps

texts: Assume you have an object moving at a constant velocity(up, down, left, right) in a grid. You have unlimited resources (memory, time). At any given time step in the grid, you can "guess" the location of the object, and you win if it is currently at that position. Without relying on probability techniques, what would be the best way to approach catching this object?


texts: When is a regexp is not a Regular Expression?

texts:
Since I'm studying for my formal languages college course, I stumbled upon these fascinating posts (One Two) which describe how to find a prime number using a regexp. As I said, a regexp, not a regular expression.
Since a regular expression can match strings computed by a Finite State Automata and finding a prime number can't be done by a FSA, the regexp shown in the blog post is not entirely a regular expression since it does backtracking to match the string.

Since I've never really used any regular expression, now, my question:

How can I immediately recognize a regexp from a "true" regular expression just by looking at it?

Definitions: By regular expression, I refer to the notion as defined in formal languages.  By regexp, I mean the notion supported by modern programming languages; the regexp syntax often contains additional features, such as backreferences.  Regexps as seen in programming languages are strictly more powerful than formal languages style regular expressions.


texts: A* without heuristic more efficient than Dijkstra

texts:
I am using the module networkx to operate on graphs made from OpenStreetMap.
I wanted to compare the shortest path algorithm to find which one is faster, and I compared Dijkstra and A*.
The problem is : A* is most of the time faster than Dijkstra even though I didn't defined any heuristic function.
I understood that A* with $h=0$ was equivalent to Dijkstra, then why is it not the same time?


texts: Gradient Descent in MLPs using Computational Graphs

texts:
I'm working through Deep Learning by Goodfellow et al. The textbook introduces backpropagation for MLPs in page 203 (http://www.deeplearningbook.org/contents/mlp.html). However, it does not expand further and illustrate the (full or stochastic) gradient descent update.

I'd like to confirm the full gradient descent update is as below. Is this correct?

Gradient descent derivation

From Deep Learning


texts: Proving $A$ avoiding $B$ regular if $A$ and $B$ are regular

texts:
Suppose we define an operation such that

$$A \text{ avoiding } B = \{w \in A \mid w\text{ has no substring in }B\}\,.$$

How can I prove that, if $A$ and $B$ are regular then $A\text{ avoiding }B$ is regular too?
I know I should either construct a DFA/NFA or use closure properties, but where to start?

What I come up with is that $A = (A\text{ avoiding } B) \cup \{w \mid w\text{ has a substring in }B\}$ and then I've tried to prove that $\{w \mid w \text{ has a substring in }B\}$
 is regular by constructing a DFA for it. That would show that $A \text{ avoiding } B$ is also regular.


texts: When is it useful to split critical edges?

texts: Some compilers have utility functions that split critical edges in the control flow graph. I assume that this is not done as an optimization in itself, but rather to simplify other analyses and transformations. In what cases would splitting critical edges be useful?


texts: If f(n) = O(g(n)), then is log(f(n)) = O(log(g(n)))?

texts:
I guess this is true, because log is a strictly increasing function, but how do I prove it formally?

I tried something like:

Let $f(n)$ and $g(n)$ be monotonically increasing functions, $c \in \mathbb{R}$ and $n_0 \in \mathbb{N}$, such that $0 \leq f(n) \leq c g(n)$, for all $n \geq n_0$. We must find $c'$ and $n_0'$ such that $$\log(f(n)) \in \{h(n) \mid 0 \leq h(n) \leq c' \log(g(n)), \forall n \geq n_0'\}\,.$$

I got as far as
$$f(n) \leq c g(n) \implies \log(f(n)) \leq \log(c g(n)) = \log(c) + \log(g(n))\,.$$

Then I got stuck.

Thanks in advance!


texts: Heuristics for space-efficient storing of Unordered Finite Sets in a DFA

texts:
I've got an algorithm I'm working on that generates, stores, and iterates through a large number of finite sets. I'm finding that memory is a bottleneck long before time is.

The finite sets are subsets of the vertices $V$ in my graph, so each finite set is small, there's just a lot of them.

In an effort to save space, I've started representing the finite sets as binary words of length $|V|$, with a 0 indicating the element is not in the set, a 1 indicating that it is. I'm storing the collection of these words as an acyclic deterministic automaton (also known as DAWG, directed acyclic word graph).

However, this requires a fixed ordering of the potential elements, which is fine, but arbitrary. If a different ordering were more likely to produce a smaller output set, I'd be happy to use it.

I'm wondering:

Is there a known, efficient algorithm for finding the permutation which gives the smallest DFA representing a set of finite sets?
If not, has any research been done on heuristics for orderings which have been shown to often produce smaller DFAs?


texts: Complexity of an algorithm with multiple inputs

texts:
I've just started reading about the complexity of algorithms, but everywhere I look, it is only defined for one input $n$. For example an algorithm is cubic if its complexity is $O(n^3)$.

But what about when the complexity depends on several inputs? For example if an algorithm has complexity $O(n^2k)$, is it 'cubic', or maybe 'quadratic in $n$ and linear in $k$'?

I've also seen phrases such as 'cubic in $k$ and $n$'; what does this mean exactly?


texts:
I am currently working my way through An Introduction to Analysis of Algorithms to stay sharp with recurrences as well as learn generating function techniques. However my analyses and the books analyses for the first few sample problems on ordinary generating functions differ. I've checked and rechecked [my work as well as errata on the webpage], but cannot see how the authors made certain leaps. For example:

Given the recurrence $a_{n} = a_{n-1} + 1$ for $n \geq 1$ with $a_0 = 0$ and letting $A(z) = \sum_{n \geq 0} a_n z^n$ I have the following steps:
$$ \begin{align*}
\sum_{n \geq 1} a_n z^n &= \sum_{n \geq 1} a_{n-1} z^n + \sum_{n \geq 1} z^n \\
A(z) - a_0&= zA(z) + \frac{z}{1-z} \\
A(z)(1 - z) &= \frac{z}{1-z} + a_0\\
A(z) &=\frac{z}{(1-z)^2} + \frac{a_0}{1-z}
\end{align*}$$

Since $a_0 = 0$ we just end up with $$A(z) = \frac{z}{(1-z)^2} \\ a_n = n$$.

However, the authors' derivation is the following:
$$ \begin{align*}
\sum_{n \geq 1} a_n z^n &= \sum_{n \geq 1} a_{n-1} z^n + \frac{1}{1-z} \\
A(z) - 1 &= zA(z) + \frac{1}{1-z} \\
A(z) &= \frac{z}{(1-z)^2} \\
a_n &= n\\
\end{align*}$$
Am I crazy, how did they get $A(z) - 1$ in the 2nd step? They do the exact same thing in the next example for $a_n = 2a_{n-1} + 1$. Is this just a typo? I would expect them to subtract $a_0z^0 = a_0$. Where did that $-1$ come from?


texts: I was looking through some lecture slides on algorithm analysis and found that in general an array access counted as a basic operation, but it did not seem to count as one when accessing the first element (e.g. A[i] is a basic operation but A[0] isn't). Does only accessing the first element count as a basic operation, and if it doesn't, does accessing  an array by a predefined index (e.g. A[5]) count as one, and why is this the case?


texts: Calculate number of ways to color matrix using inclusion-exclusion principle

texts:
This was asked in a recent contest.
The question asked to count the number of ways to color an $M \times N$ matrix with $K$ colours such that no two adjacent cells (sharing an edge) have the same color.
In other words, I want to count the number of different graph colorings of a grid graph: the graph of a $N \times M$ grid. The limits were $1 \le N,M \le 8$ and $1 \le K \le 1000000000$.

Is it possible to count the number of colors using the inclusion-exclusion principle, and if so, how? I saw another question that solves the special case (where $M=2$) using inclusion-exclusion, so I'm wondering if that kind of approach can be generalized here.


texts: Why we cannot prove that a computable function is total?

texts:
We know that we cannot find an algorithm that would prove that a computable function "f" is total if it IS total. How come?

When a function is total, it must have a proof (derived from soundness and correctness of logic). And proof is a finite sequence of symbols, so why does simple enumeration through all the sequences (which ends in finite time) not provide us with a proof?


texts:
In relation to the thread Proving that the conversion from CNF to DNF is NP-Hard (and a related Math thread):

How about the other direction, from DNF to CNF?  Is it easy or hard?

On Page 2 of this paper, they seem to hint that both directions are equally hard when they say "We are interested in the maximal blow-up of size when switching from the CNF representation to the DNF representation (or vice versa)".

But DNF-SAT is in P and CNF-SAT is NP-complete.  So given a DNF expression $\phi_1$, there should be an equisatisfiable CNF expression $\phi_2$ whose length is polynomial in the length of $\phi_1$. And the $\phi_1 \to \phi_2$ conversion can be done in poly time.  Is this correct?

Edit: Changed equivalent to equisatisfiable (that is, additional variables are allowed in $\phi_2$).


texts: Classify the set of all TMs whose languages from the accepting problem

texts:
Let $$L = \{ \langle M \rangle \mid M \text{ is a Turing machine so } A_{TM}  \leq_m L(M) \}$$
The question is whether $L$ is in $\mathcal{R}, \mathcal{RE}, co-\mathcal{RE}$ or in $\overline{\mathcal{RE} \cup co-\mathcal{RE}}$ ?

I gained some progrees showing  $L \notin co- \mathcal{RE}$:

Define reduction $f:A_{TM}\rightarrow L$ on input $\left\langle M,w\right\rangle$ returns:

if $M$ accepts $w$ return $ \left\langle U_{TM}\right\rangle $
($L \left(U_{TM}\right)=A_{TM}$ so $\left\langle U_{TM}\right\rangle \in L$)
if $\left\langle M\right\rangle$ rejects $w$ return 1 (not a TM encoding hence not in L)

$f$ is computable and $\left\langle M,w\right\rangle \in A_{TM}\iff f\left(\left\langle M,w\right\rangle \right)\in L$ hence $A_{TM}\leq_m L \implies L\notin co-\mathcal{RE}$.

Now I want to show that $L \notin \mathcal{RE}$. And I'm stuck..

Notation:

$A_{TM} = \{ \langle M,w \rangle \mid  M \text{ is a TM}, w \in L(M)\}$

$H_{TM} = \{ \langle M,w \rangle \mid  M \text{ is a TM and $M$ halts on $w$} \}$


texts: Karp hardness of directed monochromatic triangle problem

texts:
Monochromatic problem is a classic NP-complete problem.
Does the complexity stay NP-complete if we use directed graph?
DIRECTED MONOCHROMATIC TRIANGLE problem:

Input: A digraph $G(V,A)$
Output: YES if there exists a triangle-free bipartition of $A$, otherwise NO.

A triangle-free bipartition of $A$ is a partition $A=A_1\dot{\cup}A_2$ such that both $G[V,A_1]$ and $G[V,A_2]$ are triangle-free.
Note that a triangle in a digraph is the set of $3$ vertices $\{u,v,w\}$ such that $(u,v),(v,w),(w,u)\in A$. It means that we only allow triangle that has consecutive arcs. For example, $(u,v),(u,w),(w,u)$ does NOT form a triangle.


texts: Do white box methods for feature extraction exist for facial recognition?

texts:
Part of something I'm working on (or rather begin working on) involves white box approaches to facial recognition. I previously worked on something for character recognition using scene segmentation and neural networks but for faces I'm trying to challenge myself by not using neural networks or other AI strategies.

Consider a potential algorithm that takes a headshot photo as an input and the outputs are some metrics about said face. Like the eye color, skin color, hair color, philtrum width and height, distance between eyes, etc. What techniques exist that I should look into on how to implement this?

My concern is mostly with feature extraction from points of interest from a face. I think my difficulty is algorithmically describing the composition of a face to pull metrics.


texts:
I came across this problem in the “Elements of Programming Interviews” interview preparation book, and also on the site, leetcode.com (link to problem).

Problem statement – Letter Combinations of a Phone Number

"Given a digit string, e.g., “23”, return all possible letter combinations that the number could represent.  The mapping of digits to numbers is the same as on a telephone number pad.
So for “23”, the combinations are, ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]."

There are plenty of solutions online and in books. However, I’m curious to know about the fundamentals of this problem.

Is this problem essential asking for the Cartesian product of multiple sets? If so, what are some efficient algorithms to compute this? Some solutions reference DFS and BFS. How are DFS and BFS related to this problem (are they possibly referring to the type of recursion being used to solve the problem) ?

Thanks


texts: Iterate over two different non-binary tree graph

texts:
I'm working to solve a problem based on two non-binary tree graphs, that they need to be iterated together in order to find a valid combination.

I did a basic implementation that works, but it have a few flaws. Let me first explain a bit.

The point is that I have two trees, and each node have "n" children nodes, and that "n" child have another "n", and so on ("n" is constant, I mean for example if "n=14" then every node have 14 children and every child have another 14 children).

Also, that "n" value is constant and the same for both trees.

Having this concept, I need to find a combination of two nodes that fulfill some condition (that condition is user-specified, so for exapmple porpouse let's say we need to have two nodes with equal content).

I made an algotihm that iterates over all two trees, but it does in a parallel mode (I mean, if the solution is root/node1/node2/node5 + root/node3/node3/node14 it works, but having root/node1/node2 + root/node14 will not find it).

So, my algorithm does not cover 100% of valid posibilites. So my question is:

How can I iterate doing left/right join bewtween two trees?

Thank you


texts: Number of finite strings over a countably infinite alphabet

texts: If the alphabet is countably infinite, then is the number of finite-length strings over this alphabet countably or uncountably infinite?


texts:
Got a final coming up, so I gotta get this concept down.

Given $A= \{(G_1,G_2 \mid G_1$ and $G_2$ are two CFG's and $L(G_1)=L(G_2) \}$.
Is $A$ decidable?

Would it be sufficient to take an undecidable language such as $B= \{x \mid L(M_x)$ is a CFG $  \}$. Then reduce it to A with function $f(x) = G'_{M_x}$?


texts: Without using the Time Hierarchy Theorem, is there any other way to prove P /= EXP

texts:
I haven't found any way to show this was the case (that P/=EXP, without using the Time Hierarchy Theorem)
If you can find a way to show this, can you give a short explanation of this,and also if possible link a paper supporting  your conclusion.
Thank you so much


texts: Non deterministic turing machine vs Turing machine with stay option

texts:
According to book by Peter Linz, the transition function for non deterministic Turing machine is:

  $Q\times \Gamma\rightarrow 2^{Q\times \Gamma\times \{L,R\}}$
  where,

  $Q$ is a set of states
  $\Gamma$ is a set of tape alphabet
  $L$ is a movement of head to left
  $R$ is a movement of head to right

whereas the definition given by wikipedia is

  $Q\times \Gamma \rightarrow (Q\times \Gamma \times \{L,S,R\})$

Book by Ullman et. al. says above transition function is of "Turing machine with Stay option". Ullman's book does not give any formal definition for non deterministic Turing machine. So which definition is correct? I feel Peter Linz's book gives correct definition. Or both are same?


texts: Is it necessary that Minimum/Maximum Heap must be a Binary Heap?

texts:
I find this extremely wrong, that a lot of books, articles, video tutorials, online courses or trainers define Minimum/Maximum Heap data structure as a particular type of the Binary Heap data structure.. however! according to the definition of what is Heap Data Structure, that's wrong! Heap can be perfectly fine either Binary or non-Binary.

I have also read this in some Google Engineer's blog, that my thoughts are correct on this.

Any take? maybe I'm wrong? nothing, at all, restricts the Minimum/Maximum Heap that they must be necessary Binary Heap variations. Node can have 3 children, and it would still fit the Minimum/Maximum Heap definition.

Question is: how do you think? am I wrong or not? what's your take on this?


texts: Algorithm for dividing works into threads by priority

texts:
TL;DR
Is there an existing algorithm for dividing W works each with priority P using T threads? If there isn't, could you direct me to a solution?
Expansion
given:
W - amount of works [0,Infinity)
P(w) - priority [1,10]
T - available threads [0,Infinity).
N(w) - "neighbors" of a work w in its thread
There is an inverse proportionality between P(w) to N(w):
$$
{\displaystyle P(w)={\frac {factor}{N(w)}}}
$$
If there are more available threads than works, each work can have its own thread. If there are more works than available threads, then multiple works have to share a single thread. The more a work is prioritize, the less neighbors it gets in a thread allocated for them.
Example#1
given
$$
P(w_1) = 10,P(w_2) = 8,P(w_3) = 5,P(w_4) = 3
$$
$$
T=3
$$
Should result:
$$
N(w_1) = 0,N(w_2) = 0,N(w_3) = 1,N(w_4) = 1
$$
Example#2
given
$$
P(w_1) = 10,P(w_2) = 8,P(w_3) = 5,P(w_4) = 3
$$
$$
T=2
$$
Should result:
$$
N(w_1) = 0,N(w_2) = 2,N(w_3) = 2,N(w_4) = 2
$$
There aren't more constraint.
The following options are valid:

a work w1 with priority 10 can have a neighbor w2 with priority 1 in the same thread I.E. when there is only one available thread.
a work w1 with priority 10 and a work w2 with priority 1 can have zero neighbors, I.E. where they are the only works, and there are two available threads.


texts: Can we recognize the difference of two strings of $2^n$ length using polynomial size strings?

texts:
Is it possible to transform binary strings of length $2^n$ to $n^c$ binary strings of sized $n^d$ such that
$$\forall s_1,s_2 \; \exists i \in \{1,\cdots,n^c\} \; f_i(s_1)\neq f_i(s_2),$$
Where two strings $s_1,s_2$ have length $2^n$ and $\forall i\in\{1,\cdots,n^c\}, \; f_i(s_j)\leq n^d, \;  j\in \{1,2\}$?

It seems a little similar to hash functions but since we don't have any restrictions (e.g. having uniform distribution or being oneway) our hands are open to define whatever we like.

I think it's not possible. Because we have $2^{2^n}$ strings of size $2^n$ and transformring them into polynomial size strings means we have put many strings in a single string. But when I make an example this comes to my mind that maybe by defining a good design for each function we can recognize the difference by probability one.

One example can be:

For $c=3$ and $d=1$,

$f_1$: it takes string of length $2^n$ and transforms it to $mod\, n$.

$f_2$: it takes string of length $2^n$. (suppose we have divided $2^{2^n}$ strings into $\frac{2^{2^n}}{n}$ collections) If the input belongs to $i$th collection, $f_2$ transforms it to $i$.

$f_3$: it takes string of length $2^n$ and transforms it to the number which shows its $1$s number.

The probability that for two strings $s_1$ and $s_2$, these three maps $f_1, f_2,f_3$ be the same would be
$$\frac{1}{n}\times \frac{1}{n} \times \frac{1}{2^{2n}}$$
That is negligible.

So my question is that can we ever understand the difference of two long strings with probability $1$ using polynomial size strings?


texts: Perturbative Kolmogorov Complexity Bounds

texts: Are there any known bounds on the impact of changing (for example) one bit in a string on the resulting string's Kolmogorov Complexity? In mathematical terms, does the equation $|K(x) - K(x')|$ (with $K(x)$ as the Kolmogorov Complexity of $x$ and $x'$ as the string resulting from changing an arbitrary bit of $x$) have a non-trivial lower bound?


texts:
I know it is true that if A is not in P, and A reduces B, then B is not in P.
But is it true for NP as well?
If A is not in NP, and A reduces to B, does this mean B is not in NP?
Why or why not?
Thanks!


texts:
I recently read that a feed forward neural network with a single hidden layer can represent any continuous function to great precision (ref.).
Then how can we justify adding more that one hidden layer to our network ?


texts: How to divide an unsorted list in linear time where every element in the first part is smaller than every element in the second list

texts:
How to divide an unsorted list into two equal parts in linear time, where every element in the first part is smaller than every element in the second part

I tried to use QuickSort but in can result in $O(n^2)$ worst-case time complexity.


texts: Dynamic graph (?) - combination of connections between vertices that for each 3 exist min 1 edge

texts: I have to find number of ways (combination) to create graph that for each 3 vertices there are minimum 2 vertices connected. There is n vertices. For example when n=3, there are 7 possible combinations. How can I make this with maybe dynamic programming?


texts: Converting 4 variable if else condition to Linear integer program

texts:
There are four variables: $x_1, x_2, x_3, x_4$.
If you choose either $x_3$ or $x_4$ or both — then you should choose exactly one of $x_1$ or $x_2$.
If you choose neither $x_3$ or $x_4$ — then there is no restriction in choosing $x_1$ or $x_2$.
I have come up with the following if else logic for this, but cannot proceed from there.

If $x_3+x_4 = 0$ then $x_1 + x_2 \ge 0$
If $x_3 + x_4 \ge 1$ then $x_1 + x_2 = 1$

Can you let me know how to come up with an integer linear program with this understanding?


texts:
I'm searching for an algorithm to distribute values from a list so that the resulting list is as "balanced" or "evenly distributed" as possible (in quotes because I'm not sure these are the best ways to describe it... later I'll provide a way to measure if a result is better than other).

So, for the list:

[1, 1, 2, 2, 3, 3]

One of the best results, after re-distributing the values, is:

[1, 2, 3, 1, 2, 3]

There may be other results as good as this one, and of course this gets more complicated with a less uniform set of values.

This is how to measure if a result is better than other:

Count the distances between each item and the next item with the same value.
Calculate the standard deviation for that set of distances. A lower dispersion means a better result.

Observations:

When calculating a distance and the end of the list is reached without finding an item with the same value, we go back to the beginning of the list. So, at most, the same item will be found and the distance for that item will be the length of the list. This means that the list is cyclic;
A typical list has ~50 items with ~15 different values in varied quantities.

So:

For the result [1, 2, 3, 1, 2, 3], the distances are [3, 3, 3, 3, 3, 3], and the standard deviation is 0;
For the result [1, 1, 2, 2, 3, 3], the distances are [1, 5, 1, 5, 1, 5], and the standard deviation is 2;
Which makes the first result better than the second (lower deviation is better).

Given these definitions, I ask for a clue of which algorithms or strategies should I search for.


texts: Characterization of lambda-terms that have union types

texts:
Many textbooks cover intersection types in the lambda-calculus. The typing rules for intersection can be defined as follows (on top of the simply typed lambda-calculus with subtyping):

$$
\dfrac{\Gamma \vdash M : T_1 \quad \Gamma \vdash M : T_2}
      {\Gamma \vdash M : T_1 \wedge T_2}
      (\wedge I)
\qquad\qquad
\dfrac{}
      {\Gamma \vdash M : \top}
      (\top I)
$$

Intersection types have interesting properties with respect to normalization:

A lambda-term can be typed without using the $\top I$ rule iff it is strongly normalizing.
A lambda-term admits a type not containing $\top$ iff it has a normal form.

What if instead of adding intersections, we add unions?

$$
\dfrac{\Gamma \vdash M : T_1}
      {\Gamma \vdash M : T_1 \vee T_2}
      (\vee I_1)
\qquad\qquad
\dfrac{\Gamma \vdash M : T_2}
      {\Gamma \vdash M : T_1 \vee T_2}
      (\vee I_2)
$$

Does the lambda-calculus with simple types, subtyping and unions have any interesting similar property? How can the terms typable with union be characterized?


texts: I have two random variables, X and Y, and Y is a positive real number.  I can sample from $p(y|x)$, but I need to sample from $p(x)$, which I know to be proportional to $\frac 1 {E[y|x]}$.  I could estimate $p(x)$ from the mean of a lot of samples from $p(y|x)$ and then use a Metropolis algorithm, but sampling from y isn't cheap, so sampling a lot of them for each step is somewhere between prohibitively expensive and ain't gonna happen.  Is there a better way to do this?


texts: Edit distance of list with unique elements

texts:
Levenshtein-Distance edit distance between lists
is a well studied problem.
But I can't find much on possible improvements if
it is known that no element does occurs more than once in each list.

Let's also assume that the elements are comparable/sortable
(but the lists to compare are not sorted to begin with).

In particular I am interested
if the uniqueness of elements makes it possible to improve upon
Ukkonen's algorithm for edit distance
which has time complexity $O(\min(m,n)s)$ and
space complexity $O(\min(s,m,n)s)$,
where $s$ is the minimum cost of the editing steps.

More formally,

  how efficiently can we compute the edit distance between two given strings
  $s,t \in \Sigma^*$
  with the promise that they don't have any repeated letters?

$\Sigma$ is a very large alphabet.


texts: Segment 3d mesh into multiple 3d meshes with equal size

texts:
Given a 3d mesh, for example the stanford bunny, how can I segment the mesh in a way that each segment has a roughly equal size between them? Assuming the target number of segments is given as an input.

To keep things simple, let's start with assuming the vertices are uniformly distributed in the mesh, therefore the problem can be simplified to segmenting the mesh so each segment has roughly the same vertices.

I've seen methods like finding a bounding box of the mesh, and divide the bounding box uniformly and segment the mesh based on that. But the problem with this method is the size of each segment can be quite different if the shape of the original mesh is irregular.

I've also seen a method based on Shape Diameter Function, but again the size of each segment can be different depends on the original mesh.

The problem is I am not sure what's the right keyword to look up on Google to see what's being done in the literature. I would appreciate any pointers.


texts: Graph of MSTs of a graph - 2 msts connected if differ by 1 edge - is this single-component?

texts:
Suppose we take all MSTs of a graph and build a new graph where each vertex corresponds to a MST of the first graph and two vertices are connected if their corresponding spannings trees differ by only one edge.

Is this second graph make of a single component?

I am guessing it is, but guessing is not prooving...

Because any cut of the graph will give MSTs that differ by one edge - one of the edges that cross the cut with minimum weight.

Is there a name for this problem?


texts: Is a Turing machine too strong of a model to model physical computation?

texts:
I've heard many times people debate the possibility of a real world computation that is impossible for a Turing machine, especially in the context of a human mind. Implying that the Church-Turing thesis is wrong and that a Turing machine does not accurately model any possible real world computation. To me, it seems that not only is the Turing machine not too restrictive, it's actually unrealistically strong. Namely, it has unbounded tape and time in which to perform its computation!

I suppose that the counterargument to this would be that unbounded is not the same as infinite, and in an idealized model of the physical universe we really have unbounded space and time in which to perform computations (neglecting minor details like the expected heat death of the universe and the possibility of finite space). But still, it seems as though we are basing our ideas of what is computable on an unreasonably strong model.

So, are there any attempts to capture the notion of computability and what we know to be computable in the physical world in a model that is finite in nature? Or is there some deep inherent reason why unboundness is a requirement of any such model?

Edit: To address the comments so far - I know that a Turing machine with bound tape is equivalent to a DFA, and therefore definitely does not capture in any reasonable way the notion of possible real world computations. I was rather referring to models that might not resemble Turing machines at all.


texts:
We define a Pythagorean triple as a triple $\langle a,b,c\rangle$ such that $a,b,c\in \mathbb N$ and $a^2+b^2=c^2$.

In order to avoid duplicates, we say that a triple $\langle a,b,c\rangle$ is legit iff $b>a$.

Let $\mathcal P$ be the set of all legit Pythagorean triples.

We define a lexicographic order $\prec$ on $\mathcal P$, such that $$\langle a_1,b_1,c_1\rangle\prec\langle a_2,b_2,c_2\rangle\iff (a_1< a_2)\vee ((a_1=a_2)\wedge(b_1<b_2)$$

Let $$L_\mathrm{PT}=\{\langle \langle a,b,c\rangle,n\rangle \mid \langle a,b,c\rangle \text{ is the $n$'th triplet in } \mathcal P\text{ w.r.t.}\prec\}$$

  What can we say about the complexity of $L_\mathrm{PT}$?

We say that a triple $\langle a,b,c\rangle$ is minimal if $gcd(a,b,c)=1$.
Let $\mathcal P_\mathrm{M}$ be the set of all legit, minimal triples.

We define $$L_\mathrm{PT}'=\{\langle \langle a,b,c\rangle,n\rangle \mid \langle a,b,c\rangle \text{ is the $n$'th triplet in } \mathcal P_\mathrm{M}\text{ w.r.t.}\prec\}$$

  What can we say about the complexity of $L'_\mathrm{PT}$?


texts:
I'm not even sure if this is the right StackExchange to post this, but it seems like sentiment analysis would go here.

What would be the best approach to determine if two people on Twitter are actually friends?

I think that the first criteria would be that they are following each other. This would eliminate all of the celebrities, companies, etc. that a person follows.

The second criteria could be physical proximity to one another. If two people tweet from the same general areas, then there's probably a higher chance that they actually know each other.

After that, I'm not sure what criteria I should look for. Would sentiment analysis of their tweets to each other be a viable option? With that friendly sentiment could indicate that they actually know each other.


texts: Multiple correct answers for compilation

texts: When you are asked to hand compile into assembly language, are there multiple correct answers? For example, in https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-004-computation-structures-spring-2017/c11/c11s3/compilation_answers.pdf, can you get the correct solution even if your solution doesn't match the solution given?


texts: Inapproximability result implies apx-hardness?

texts: If an optimization problem is known to be inapproximable up to some precision, does this automatically imply that the problem is apx-hard?


texts:
Typically the notion of quantum Turing machine is introduced with its transition function.

$$
\delta:Q\times \Gamma\rightarrow \mathbb{C'}^{Q\times \Gamma\times\{L,R,0\}}
$$

Where $\mathbb{C}'\subseteq\mathbb{C}$ is a computable subset of $\mathbb{C}.$ This sort of definition basically gives any 1-qubit unitary gates "for free," you only need one step to perform any such unitary transform.

We knew that there's Solovay Kitaev theorem saying that any single qubit transformation could be approximated by a finite set of gates, but sometimes it still require more than $\Omega(1)$ gates to do this (grow with the precision). So it's natural to ask whether there exist an "efficient" approximation, so that when we're using just regular gates, the complexity would be roughly the same. (e.g. with only some polynomial amount of resources added up).

  Let's say we're given another QTM with transition $\delta'$ only allowing $O(1)$ gates as a generating set of a dense subset of $SU_2(\mathbb{C})$, then we redefine the $BQP_{\delta'}$ with it, is it the case that $BQP_{\delta'}=BQP_{\delta}$?


texts: Determining whether $ L = \{ 0^n1^{n^2} | n \ge 0 \} $ is a CFL

texts:
Assuming $L$ is defined as follows:

$$ L = \{ 0^n1^{n^2} | n \ge 0 \} $$

I'm trying to either prove/disprove whether $L$ is CFL or not.

My intuition tells me its not CFL since I cannot express the power $n^2$ by itself using CFL, but I'm having trouble proving so using the pumping lemma.
Also, I failed to create any such PDA (which my intuition says its impossible).


texts: Algorithm to figure our deps in a graph that can resolve deps from cache (dictionary) of walked paths

texts:
I have a graph like this that starts from one top node and has cycles:

I need to write an algorithm to figure if node1 depends on node2. The most primitive algorithm I've written simply starts with node1 and recursively follows all available edges looking for node2 starting from node1. It's very inefficient because I traverse the graph over and over again. I'm wondering if there's an algorithm I can look at that caches nodes and dependencies it already walked through so that I don't go through paths I've walked once and can figure if there's a dependency or not from cache?
For example, if I'm given node D and the question is whether it depends on node F, I'll walk D->E->F, and when next time I get the question if node E depends on F, I'll get that from cache without walking the graph.
Thanks for any ideas and suggestions!


texts:
Is $a^mb^n$ where $m=n^2$ a CFL?

I have a doubt regrading this problem. Say if we pop $n$ number of $a's$ from the stack for each $b$ then it is a CFL (to be exact DCFL) right?

On the other hand I have this doubt, do we know the number of $b's$ we are provided with, if not how can we pop $n$ number of $a's$ for each $b$? So this case doesn't make it a CFL right?

Which of these 2 cases are applicable? Are we always aware of the number of $b's$ we have? Then shouldn't it be a regular language?


texts: How can fuzzy logic be applied to computer language design?

texts: Is fuzzy logic in any way applicable to general-purpose language design? If yes, then how would a computer language theoretically benefit from first order support of fuzzy logic?


texts:
There is a non-regular language that exists the pumping lemma for regular language?

I didn't find one.

Edit:
 From what i understood the pumping lemma does not prove that it is a regular language becuse there are non regular languages that "support" the pumping lemma.
Thanks.


texts: Name of binary encoding scheme for integer numbers

texts:
I once found on Wikipedia a nice technique for encoding $k \in (2^{n-1}, 2^n)$ uniformly distributed integer numbers with less then $\log_2n$ average bits/symbol, thanks to a simple to compute variable length code. Basically it used $\log_2n$ for some symbols and $\log_2n - 1$ for some others.

Unfortunately all my Googling has failed me. I recall something similar to "variable length binary", but I keep ending on VLQ which are a different beast. Since I know your memory better than mine, can you help me?


texts: wondering if anyone can give me some advice. I’m 17 and just about to leave high school and Morgan Stanley have offered me a job as an analyst and said they’d pay for me to get a BSc degree in Software development from a good uni (Strathclyde) and if I do well I’ll progress to a tech associate in 4 years. But I’ve also got an offer to study a MSc in Computing Science at a good uni (St Andrews) and I don’t know what is better to get into software engineering - with your experience in the tech industry what do you think would be better long term?


texts:
We have $n$-players in a game. We have a population of players we can choose from. Each player score is a normally distributed random variable and each player has a cost to add to the team. We are limited to $n$-players and the total cost must be less than or equal to $m$.

The total score for a team is calculated as the sum of all of the individual player's score on that team. Our goal is to maximize the expected team score while staying under our allowed player weight and number of players.

Now, suppose that in this game we drop the score of the player that has the lowest score on the team and do not consider it in the total team score.

Does a deterministic algorithm exist that will allow us to reach the optimal solution?


texts: How should I "read" a dereference operator?

texts:
For example, when I look at some code like

int x = 1;
int * y = &x;

I can read it like

x equals 1
y equals the address of x

but how would I "read" something like

*y = 1;

My best guess is

The value at address y equals 1

But I'm wondering if there's a better way to think about it.


texts: Pumping Lemma for regular languages proof doubt - Sipser Book

texts:
I was reading the proof of pumping lemma from Sipser's book. I couldn't understand certain things mentioned there.

In the second paragraph he has written, "because $r_l$ occurs among first $p+1$ places, we have $l \le p+1$". Here, does $l$ denotes the number of states visited?

Also he wrote  "We know that $j \neq l$, so $|y| > 0$; and $l \le p+1$; so $|xy| \le p$"

What I didn't understand is

$j \neq l$
$j \neq l$, so $|y| > 0$
$l \le p+1$; so $|xy| \le p$


texts:
Give a finite state diagram for a DFA that accepts any word in the language $L = \{w \mid w \in \{a, b\}^* \text{ and }w \text{ alternates } a\text{'s and }b\text{’s and has an even number of }b\text{’s}\}$.

My attempt: I am having problem on how to deal with the even part of b.


texts:
You're given N integer arrays. Each array can have different size and contains unique values. However same integers can be found in different arrays.
The goal is to partition those arrays into K groups such that:

Arrays grouped together don't share any integer
I want to minimize the number of groups

Example:
Input: [[1, 2, 3], [2, 4, 5], [6, 7, 8], [4, 6, 10]]
Suboptimal Solution using 3 groups:

group 1: [[1, 2, 3], [6, 7, 8]]
group 2: [[2, 4, 5]]
group 3: [[4, 6, 10]]

Optimal Solution using 2 groups:

group 1: [[1, 2, 3], [4, 6, 10]]
group 2: [[2, 4, 5], [6, 7, 8]]

Any idea on how to solve this effectively?


texts:
The convex hull of a point set is a well understood problem and nice optimal solutions are known in the case of a finite point set and a simple polygon.

For a convex polygon, the hull is the polygon itself. When it is concave, the difference is made of "pockets" which are also polygonal regions, and you can iterate until all pockets are convex.

I am wondering if there is any theory about this process and an efficient algorithm to construct the hierarchy, possibly as a generalization of Melkman's algorithm?


texts:
I want to prove that $\{A^iB^jC^k \mid i=j \text{ or } j=k\}$ is a not a regular language using the pumping lemma.

I've found that the only way to obtain a contradiction is when $x \in A^*$, $y \in B^*$, $z \in C^*$,
 as $y$ is unable to be pumped up and still fit in the language. However if I have any combination of
 $y \in B^*C^*$ or $y \in A^*B^*$ and either $x$ or $z$ is empty,
 it appears as if $y$ can be pumped and thus this would be a regular language. The only way I can think that this would violate the rules of pumping lemma is if $|xy| ≤ P$. Assuming that $P$ is $2$ (which may be completely wrong), then the above still wouldn't violate the pumping lemma and thus this would be a regular language, right?


texts: Crossover operator in genetic algorithms in Neural Networks

texts:
I am developing a neural network that is trained using a genetic algorithm.
The neural network is a multilayer perceptron using $\tanh$ as its activation function. Currently, the genotype of the neural network is by its weights. I used the method of making a connectivity matrix and linearizing it according to this paper: http://sci2s.ugr.es/keel/pdf/keel/articulo/NN-Garcia05.pdf

What is a good crossover method for this? I've tried uniform crossover but it is too disruptive as there is no improvement whatsoever. Single-point crossover is discouraged as I have read, so what should I use?


texts: How can I solve the recurrence $f(n) = 3f(\frac{n}{4}) + \log(n)$?

texts: The master theorem didn't work here. I tried to do the substitution method but I ended up with an additional term: $2Σ(i \cdot 3^i)$. Also I should find the solution $g(n)$ such as $f=\Theta(g)$.


texts: How is the complexity of recursive algorithms calculated and do they admit better complexity than non-recursive algorithms?

texts:
How are asymptotical time complexities calculated for recursive algorithms?

Recursive algorithms call themselves and therefore take up more space compared to non-recursive algorithms. But are they better taking time complexity into account? If they are better than non-recursive algorithms, then how are they better and why (not)?


texts: How to use Parikh's Theorem to show language is not context free

texts:
Parikh's Theorem  is quite complicated, I understand intuition of that theorem but I don't see how to use that to prove that language is not context free. I kindly ask you to show me how to do, language isn't important, but for definiteness:

$$ L=\{0^m1^n:m>n\text{ or }(m\text{ is prime and }m\leq n)\}$$


texts: Generating a random path in a grid without deadlock

texts:
I want to write an algorithm that takes an $n \times n$ grid and a number $L$, generate a random walk of length $L$ on the grid that doesn't visit the same cell twice.

One simple solution would be keep randomly choosing a neighbour of the last cell to add to the path. I found that for small density (i.e. $L < 0.625n^2$), I can repeat this algorithm a large amount (at least $1000$) times and can almost find some complete path without deadlock, i.e. without a a state where the path is incomplete but there is no more move available (i.e. all neighbours of the current cell is already filled). A DFS can lead to a deadlock state, and from my experiments, most of the end states are deadlocks, hence it is very hard to get to a complete state with DFS. But for larger density, it is nearly impossible to avoid deadlock no matter how many times I repeat.

My second attempt is to backtrack one step if the current $i^{th}$ step results in a deadlock (i.e. delete the last action from the list of possible actions at $(i-1)^{th}$ step and randomly choose a remaining action to retry). However it apparently took forever to finish the path (it kept going forward and backward when $i$ reaches $0.625n^2$).

Is there any suggestion for a fast algorithm that have fairly high probability of avoiding deadlocks? I'm fine with pseudo-randomness.


texts:
This is my basic setup: I have five time slots (A, B, C, D, E; each day has these five time slots) over 60 days that all need to be filled with n people each (n must remain a variable). However, each person has a different availability (ex. ABDE, BCDE, AE, BCD, etc.). I want this to be distributed equally so all workers get the same number of shifts, but some workers should be able to input in a number of shifts that they want to do.

I recognize that this is a subproblem of the nurse scheduling problem, and I have spend a few hours trying to grind through some academic papers on it. However, it gets very convoluted very quickly and I get lost somewhere in the mix, as I do not have a knowledge of these kinds of algorithms. This seems to be a simpler version with fewer constraints, so I was wondering what a simple yet effective algorithm would be to solve this problem and if you could provide details on it.

I have come up with a two crude algorithm ideas, and I don't know which of these (if any at all) would be the most effective:

First distribute work to the person with (1) the least number of shifts assigned so far and then (2) with the least number of availabilities.
Distribute all work days to those with the least number of availabilities, but fill a person's entire schedule before progressing on to the next person. Shifts get assigned by determining which time slot (A/B/C/D/E) has the least number of people working it.

The thing that I don't like about each of these algorithms is that it seems very easy to get stuck at any given point, and from there I really wouldn't know what to do.

Thanks.


texts: Rounding logarithm to next integer — Potential function

texts:
The problem is IV-3 of this pdf: potential function.

Defining a potential function as $\Phi(i) = 2i - 2^{\lfloor{\log_2i}\rfloor+1} + 1$

The solution states that if $i$ is not an exact power of $2$, we have:

$$\Phi(i) = 2i - i + 1 .$$

This means that $2^{\lfloor{\log_2i}\rfloor+1} = i$. I'm having some trouble understanding this equality.

Can somebody shed some light?


texts: What does the exact $\mu$-recursive program for minimization look like?

texts:
The minimization of a given primitive recursive function $f$ is computed by the following expression:

$
\newcommand{\pr}[2]{\text{pr}^{#1}_{#2}}
\newcommand{\gpr}{\text{Pr}}
\newcommand{\sig}{\text{sgn}}
\text{Mn}[f] = \gpr[g, h] \circ (\pr{1}{1}, \pr{1}{1})
$

$g = \sig \circ f \circ (\pr{1}{1}, c^1_0)$

$h = \text{Cond}[\text{t}_\leqslant \circ (\pr{3}{3}, \pr{3}{2}), \pr{3}{3}, \text{Cond}[ \text{add} \circ (\text{t}_= \circ (\pr{3}{3}, \text{ suc} \circ \pr{3}{2}), f \circ (\pr{3}{1}, \text{suc} \circ \pr{3}{2})), \text{suc}  \circ \pr{3}{2}, \text{suc}  \circ \text{suc}  \circ \pr{3}{2} ]]$

The first call to the function ($\text{Mn}[f] \circ (\pr{1}{1}, \pr{1}{1}) (n, k)$) will return at most k+1 and terminate for all inputs, if $f$ is total recursive.

A $\mu$-recursive search would not necessarily terminate, if no $z \leqslant k$ such that $f(n, z) = 0$. But I fail to see how that $\mu$-recursive expression would look in contrast to the above one, meaning $-$ what would the part of the expression look like, that makes the function not terminate.


texts:
Given $k$, a $k$-domino is a non-ordered pair of integer values of $[\![0, k-1]\!]$, for example $\langle 0, 3\rangle$ or $\langle 1, 1\rangle$ are dominoes, the domino $\langle 3, 0\rangle$ being the same as $\langle 0, 3\rangle$.
A sequence of length $n$ of dominoes is a sequence $(d_0, d_1, …, d_{n-1})$ where $d_i = \langle a_i, b_i\rangle$ is a domino, and $\forall i \in [\![0, n-2]\!], b_i = a_{i+1}$. For example, $\langle 2,3\rangle\langle 3,5\rangle\langle 5,2\rangle\langle 2,1\rangle$ is a sequence of length 4.
Given $k$ and $N$, and a set $S$ of $N$ distincts $k$-dominoes, I want to find the longest sequence of dominoes constructible using each domino in the set $S$ at most once.
My ideas so far are to use some kind of backtracking algorithm: I try to complete a sequence of dominoes with a new domino – among those not used, or not eliminated – and if it is valid, I continue; if there is no valid domino, I delete and elimininate the last domino to try again. I am using hash table to keep track of the remaining dominoes.
I wondered if there is a more efficient/elegant way to do it, maybe by pre-sorting the set $S$ before trying to construct sequences of dominoes, or using dynamic programming in a way I haven't found yet.
I also thought of constructing a graph with each domino as a vertex, but I don't really know how to put edges because of the two faces of the domino: if I add an edge between two dominoes that have a common value, then I risk to find $\langle 1,2\rangle\langle 2,3\rangle\langle 2,0\rangle$ as a valid sequence…
One of the ideas proposed in the comments is to construct a graph where vertices are integers of $[\![0,k-1]\!]$ and edges are dominoes of $S$ (domino $\langle a , b\rangle$ is an edge between $a$ and $b$, possibly a loop if $a = b$). The question is now equivalent to finding a longest path in this graph. The problem is that it is not similar to longest path problem because the path are not necessarily simples (meaning a path can cross the same vertex multiple times). One would need to keep track of used edges to find the longest path, so it does not really simplify the problem.
The problem is difficult and seems even $NP$-hard, but I still want to find an efficient algorithm solving it. My current backtracking solution find the answer for $k = 20$ and $N = 30$ in 10 sec (for a randomly generated set of distinct dominoes), but it increases quickly if I lower the value of $k$ or increase the value of $N$ (even $k = 15$ and $N = 30$ is taking ~30 minutes).


texts: Looking for an algorithm to minimize cost of edge traversals in a bipartite graph subject to constraints

texts:
I have a set of urns that can each hold different amounts of sand. Porters can deliver sand to each urn subject to a transport fee per unit of sand. Each porter has a finite amount of sand they are capable of delivering to each urn. The objective is to fill the urns with all the available sand while minimizing total cost. Here's a motivating example:

Black circles show porters. The value in the center of the porter circles show the total amount of sand they can transport. Gray squares show urns. The value in the center of the urns show the amount of sand an urn can hold. Porter_Urn edges show the cost of transporting 1 unit of sand to a given urn. Using this example, Porter 1, which has 100 units of sand could transport 1 unit of sand for a cost of 50 to Urn 3, which can hold a total of 65 units of sand. That would be very expensive!
Is there an algorithm to solve this optimization problem? It seems like maybe a maximum flow problem or maybe a multi-knapsack problem? Or some other algorithm from Operations Research?


texts:
Let $G$ be a weighted graph with a weight function $w \longrightarrow \mathbb{R}^{+}$. Let $G'$ denotes the weighted matrix with adjacency matrix
$$A_{G'} = \sum_{i=0}^{k} (xA)^{i}$$
where $k$ is integer and $x$ is a variable.
I am not getting what is $A_{G'}$ matrix? Is it contains all walks of length $k$ or is it something else?


texts: What is the Expected run time of an algorithm that randomly generates N unique strings of length D?

texts:
I was trying to rigorously/mathematically analyze the runtime of the following algorithm:

while i < n {
    b_D = randomly_generate_bit_array_length(D) # simply selects each bit randomly with 1/2 prob of choosing 0 or 1.
    if b_n NOT in HashTable[b_D]:
        HashTable[b_D] = b_D
        i++
}

First I started by thinking what is the probability of two strings matching and realized that the probability is equal to the probability of all bits matching:

$$ Pr[b^1 = b^2] = Pr[\cap^D_{i=1} \{ b^1_i = b^2_i\} ] = \frac{1}{2^D} = 2^{-D}$$

Then I realized that its crucial to know what the probability of a collision happening with something in the hash table if the hash table has $k$ elements (notice that its an equality because there are no intersections with events since all elements in the hash table are assumed to be unique):

$$ Pr[collision] = Pr[\cup^k_{i=1} \{ b^{current} = b^{HashTable}\} ] = k 2^{-D} $$

now the way I would normally proceed to calculate this is by writing the runtime $T(n)$ in terms of indicator random variable or some type or random variable and them compute an expectation over the distribution of coin flips of the algorithm.

$$ \mathbb{E}[T(n)]$$

however, I am having difficulties writing this step. The main issue is that it seems that in principle this algorithm could run forever (with low probability) so its possible that we loop several time in the same iteration trying to find a non colliding binary string. I think this weird unknown repetition is what I am having a hard time including in the summation. Anyone has any suggestion on how to proceed?

I think I just had a realization of maybe how to do this. Define:

$$ X_i = \text{variable indicating if it took i steps to complete} $$

then we can do:

$$ T(n) = \sum^{\infty}_{i=1} i X_i $$

the difference from usual algorithms like this is that the first $n$ terms have to be zero since we need $n$ strings, so we can never take less than $n$ steps since we need $n$ strings.

Now I just need to compute $Pr[X_i]$.


texts: Pseudocode algorithm to check encoding of Turing machine

texts:
My question goes like this:

  Write an algorithm (in pseudocode) that on input $w$, checks that $w$ encodes a valid Turing machine $\langle M\rangle$. e.g, you need to validate that the structure is correct, that $\delta(q_a,a)$ is undefined for every symbol $a$, etc.

Unfortunately, I got no idea how to tackle it. I have a clue that induction might be needed, but it didn't help me. Any help will be appreciated. Thank you!


texts: Is there a formal definition of sub-instances or sub-problems?

texts:
A decision problem is denoted as a language $L \subseteq \Sigma^{*}$.
For every instance $x \in \Sigma^{*}$, we say $x$ is a yes-instance if $x \in L$ and a no-instance if $x \not\in L$.
For some algorithms (e.g. devide-and-conquer, dynamic programming), we may consider some sub-instances firstly, given an instance $x$.
I want to know whether I can let the substrings or the prefixs (suffixs) of $x$ be (all of) the sub-instances.
Is there a formal definition of sub-instances?


texts: How to check if $m$ numbers in a sequence satisfy a condition, such that all these numbers are spaced apart by at least $k$?

texts:
Suppose we have a sequence $s$ with $n$ elements from $s[1..n]$. I want to check if there exists $m \leq n$ elements in this sequence that each satisfy some simple condition (that can be tested in $O(1)$ for each $s[i]$), such that all of these elements are spaced apart by at least $k$. Is there an algorithm that can achieve this in $O(n)$ time?

For example, suppose we have $s=[3, 4, 13, 2, 6, 4, 1, 9, 11, 5]$ and we are trying to verify if there exists $m=3$ elements that satisfy the condition $s[i] \leq 4$ and are spaced apart by at least $k=2$. This is true because $s[1] = 3, s[4] = 2, s[7] = 1$ and $s[1], s[4], s[7]$ are spaced apart by at least $2$.

A naive solution that I thought of involved iterating through the sequence and recording each $s[i]$ that satisfies the condition, and then for each $s[i]$, trying to find $m-1$ others that don't violate the spacing requirement. I'm not sure how I can do this in $O(n)$ time. Is it possible?


texts: Using Prim's for finding minimum cost arborescence in a special setting

texts:
I have a complete graph G which is directed. In essence, a node is connected to all other nodes in the graph. Also, for every pair of nodes, say v and u, there exists two weighted edges one from u tov, and another from v to u.

Under such a configuration for the graph, if I use prim's algorithm, will the algorithm give me an arborescence, which is minimal to the root node, though not to the graph?

I understand that a single run of the prim's algorithm need not give a minimum cost arborescence for the graph. But by finding minimal arborescence by considering each one of the node in graph as root node and then using prim's algorithm, wouldn't this give me the minimum cost aroborescence.

Since the graph G is complete, isn't it guaranteed that an arborescence exist for any given node in G? SO doesn't finding all the minimal cost arborescence for each of the rooted node using prim's and listing them would lead to finding the minimum cost arborescence

I use prim's algorithm as a search procedure for a machine learning structured predction task. So, increase in complexity is not the major concern here for the time being. Using Chu-Liu-Edmond's is not an option under our setting.


texts: Find rectangle of minimum area where dimensions are larger than minimum

texts:
Problem: Given a collection $S$ containing $|S|=n$ rectangles defined by dimensions $(x,y)\in R^2$ (width and height of rectangles are real numbers), find the rectangles with the minimum area ($A_i = x_i * y_i$) where $(x_i \geq a)$ and $(y_i \geq b$) for any $(a,b) \in R^2$.

The naive solution $F(S,a,b)$ will solve this with $O(n)$ runtime complexity and $O(1)$ memory complexity: loop through all the rectangles that are larger than the minimum required values $(a,b)$ for $(x,y)$, remember the one with the smallest area $x*y$ and return that. This requires no preparation or indexing of any kind, just a simple loop (sorting according to area beforehand won't improve the $O(n)$ worst-case runtime complexity).

Can this problem be solved with an algorithm with faster than $O(n)$ runtime complexity and up to O(n) memory complexity?


texts:
I have several lists of varying size, each index of the list contains both a key and an object : list1.add('Key', obj).

The lists are all sorted.

My aim is to iterate through the list and match 1 or more items in list 2,3,4 or n to an item in the mainList using the key.

Currently I do something along the lines of:

for i to list1 size
   for j to list2 size
   if list1[i] = list2[j]
      do stuff

As I loop through I'm, using boolean values to exit quickly using a if current != previous check and I'm deleting the object from the list I take it from.

it's working fine but I now have another list that I need to match and possible another n lists afterwards. The lists are of different sizes.

the 2 options that I can see are to either repeat the above segment of code several times where the inner list is changed - I do no like this approach.

The other option is to extend the above and once one inner loop is finished, move onto the next:

  for i to list1 size
       for j to list2 size
       if list1[i] = list2[j]
          do stuff
       for k to list2 size
       if list1[i] = list2[k]
          do stuff

I'd like to think I'm correct in thinking that the 2nd is more efficient however I'm unsure. Also, is there a better way?

Thanks for any advice / help.

Edit:  Barmar in SO has stated that they are the same time complexity but it might be considered off-topic so I've added here in case it'll help someone else and in case there is a better solution.


texts: Boolean variable true iff equation is satisfied in ILP

texts:
Assuming $y$ is a boolean variable in an ILP program (that is $y \in Z$, s.t. $0 <= y <= 1$) and $x_1$, $x_2$ are bounded integer variables between $0$ and $M$. I want to encode the following high level constraint:

$$y = 1 \iff x_1 \le x_2$$

So far I've got this:

$$x_1 \le x_2 + (M+1)y$$

This enforces that whenever $x_1 > x_2$ is true, $y$ must be $1$ or the equation won't hold. However, if $x_1 \le x_2$, nothing is restricting $y$ and thus could either be $0$ or $1$.

What other equation could I add in order to encode the constraint?


texts: Minimum Number of Integers From a List that Add up to N (Dynamic Programming)

texts:
A problem I'm working on requires me to find the minimum # of integers from a given list that add up to $N$, or more specifically:

  Given a list $L$ of $K$ integers, $[a_1, a_2, ... , a_k$], where each $a_{i+1} > a_i$ and each $a_i > 0$, design an algorithm that finds the minimum number of such $a_i$ that their sum adds up to $N$.
   You can use each $a_i$ an unlimited number of times. You may assume $N$ is a possible sum for any $L$.

  Example: $L = [1, 3, 5]$. $N = 10$. The optimal choice is $5 + 5$. A possibility is using $10$ $1$'s, but that is not optimal.

I thought I found the optimal solution using a greedy algorithm, where we start with $0$ add the largest integer from $L$ without going over.

But my greedy algorithm fails in this case:

  Integers: $[1, 5, 7]$, $N = 10$; greedy algorithm gives $7+1+1+1$, but optimal solution is $5+5$.

The people I've talked to suggested taking a Dynamic Programming approach, but I am not quite comfortable with DP. What suggestions or hints do you have for thinking of a DP approach? I think I should approach this recursively, but in what way? Should I keep breaking it down to halves until I find individual components (kinda like mergesort), and see what numbers these components add up to in $L$?


texts:
Given a tree $T$ rooted at $1$. Each node might have more than 2 children. You want to create a tree $S$ where each node have $2$ or less children or a binary tree. For each node $u$ in $T$ which had more than $2$ children. Let $D$ be the number of $u$'s children. You can add $D-2$ node to replace the edge connecting $u$ and its children to form a new tree where $u$ is the root and the leaf nodes are its children. There are many possible ways to create $S$. Find the minimum depth of $S$ where depth is the maximum distance from root to some leaves.

My idea is to use Dynamic Programming approach. Let $dp[u]$ be the minimum depth we can make for subtree which $u$ is the root. Let $v$ be the child node of $u$. My approach is to sort $dp[v]$ in descending order and then use Dynamic Programming on the sorted list in $O(n^3)$. Similar to the solution of Matrix Chain Multiplication. But this approach is too slow. Is there any greedy solution so that I can calculate $dp[u]$ in $O(n)$ or $O(n log n)$?


texts: Is SelectionSort faster than QuickSort in the worst case scenario?

texts:
Is SelectionSort faster than QuickSort in the worst-case scenario?

QuickSort, in the worst case, allegedly does $n^2$ comparisons. And SelectionSort, if I am not mistaken, always does $n^2/2$ operations. By that logic, there should be a permutation for an array of any size for which SelectionSort is faster than QuickSort. Am I missing something?


texts:
I'm working on homework for my formal languages and automata course. The text we are using is the first edition of Hopcroft and Ullman (1979).

Specifically, I'm unsure how to justify that my regular expression for exercise 2.10 (c) is correct. The question asks for a regular expression for the set of all strings not containing the substring 101 (over the alphabet $\{0, 1\}$). Additionally, it asks for justification that the regular expression you write is correct.

I came up with the regular expression
$$0^*1^*0^* + (1 + 00 + 000)^* + 0^+1^+0^+.$$

As for the justification, what exactly are they looking for?


texts: Does array always have a wasted space of O(n)?

texts:
In this question it's stated that dynamic array wasted space is O(n). Here is the explanation why:

  Because, when a dynamic array is full, its size is increased by some
  factor α. This means that, immediately after growing, a dynamic array
  holding n items has size about nαnα, so the amount of wasted space is
  n(α−1)=O(n)n(α−1)=O(n).

I'm wondering if it's always O(n). Maybe there is some logic similar to this one which proves that wasted space is not O(n)?


texts: Is there a name for the class of functions whose totality can be proved using "Ackermann-like" reasoning?

texts:
Primitive recursion is recursion where totality can be proved because there is a single natural number parameter that strictly decreases in every recursive call. Put another way, the recursion terminates because there is a parameter with order type $\omega$ that strictly decreases under the ordering in each call.

The Ackermann function is the standard example of a recursively-defined function that is not primitive recursive. Its totality can be proven by arguing as follows: at each recursive call, either the first parameter decreases, or the first parameter stays the same and the second parameter decreases. At the calls where the first parameter decreases, the value of the second parameter might blow up by a huge amount, but this is OK because the whole parameter tuple is still decreasing under the lexicographical order. Since the lexicographical order is a well-ordering, the recursion must terminate. We are effectively using the fact that the parameter tuple is ordered like the ordinal $\omega^2$ and arguing that the recursion terminates because that ordinal exists and is well-ordered.

We can consider the class of functions that is defined like the primitive recursive functions, but instead of being closed under primitive recursion, it is closed under this stronger form of recursion using lexicographical reasoning on parameter tuples (for any finite number of arguments—basically the ordinals less than $\omega^\omega$). This is a natural class of total recursive functions which includes all of the primitive recursive functions as well as the Ackermann function. Is there a standard name for this class of functions?


texts:
I am looking at the diverse subset problem in Kleinberg and Tardos, shown in the image:

Why can't we give a polynomial time algorithm for this? Cant we iterate through each person a, and then each item i, and then see for each person b $\neq$ a if b has bought item i, then conclude that a and b cannot be diverse? And if we get through all items and no item that a has bought has been bought by b therefore implies they're diverse? Then we do this with each customer. What's wrong with this approach?


texts: Computation of normalized first derivative in discrete case

texts:
I am reading a paper on recognition of online handwritten characters. One of the features proposed in the paper is "normalized first derivatives, $(\hat{x}'_t,\hat{y}'_t)$", which they have defined as follows:

$$
\hat{x}'_t=\frac{x'_t}{\sqrt{(x'_t)^2+(y'_t)^2}}\quad\quad
\hat{y}'_t=\frac{y'_t}{\sqrt{(x'_t)^2+(y'_t)^2}}\,,
$$
where

$$
x'_t=\frac{\sum_{i=1}^2i(x_{t+i}-x_{t-i})}{2\sum_{i=1}^{2}i^2}\quad\quad
y'_t=\frac{\sum_{i=1}^2i(y_{t+i}-y_{t-i})}{2\sum_{i=1}^{2}i^2}$$
I have couple of doubts with respect to these definitions:

If the derivatives are to be normalized, what is the significance of the denominators in the definition of $x'_t$ and $y'_t$?
Why is the difference scaled by $i$ in the numerator? What I understand is that this scaling gives more weight to the points farther from the central point.


texts: Efficiently convert an NFA with multiple $\varepsilon$ edges and accepting states into a regular expression

texts:
Given an NFA with alphabet $\Sigma = \{a, b, c\}$ defined in the diagram, is there a way to efficiently convert it into a regular expression?

The way I solved this problem is to first convert the NFA into a DFA using equivalent classes, and then proceed with the method described here. I feel in this case, that method is very inconvenient, as there are many loops and multiple accepting states. I wrote down all the partial regexps regarding to each accepting state alone, then unioned them together, then eliminated the redundant parts. My answer is $a(a^+ \cup b^*a \cup c^*)^+$.

I also tried to eliminate the $\varepsilon$ edges first then start from the "sanitized" NFA, but there were way too many edges in this case, and was very confusing during the process.

Edit: as @DavidRicherby has commented below, converting the NFA to DFA first is not necessary and makes the problem more complex.


texts: What are the closure properties of LL(k) languages?

texts:
Suppose I have two LL languages $L_1, L_2$, both describable by LL($k$) grammars for the same $k$, and regular language $R$. Which of the following are also LL languages, and can they be described by LL($k$) grammars?

$L_1 \cup L_2$ (union)
$L_1 \circ L_2$ (concatenation)
$L_1^*$ (Kleene star)
$L_1 \cap R$ (intersection with a regular language)


texts:
Problem Statement: Given a Problem $(A)$ such that: Any proposed solution $(S_0)$ is guaranteed to be polynomial size w.r.t. $A$. Now, consider a fixed set of $K$ properties $\{k_0, k_1,...k_c\}$, where each property is $coNP-Complete$.

For any solution $S_0$ is considered a valid solution iff: "None of the property in $K$ has a $NO$ instance for $S_0$".

Example: For some hypothetical problem $(A')$ let the solution $S_0'$ be a simple graph with $n$ nodes. Let $k_i$ be the property: "$S_0'$ does not contain  a clique with $n/4$ nodes".

Query: Assuming the highly improbable scenario that $P=NP$, it implies $P=NP=co-NP)$. Thus, all the properties in $K$ are $P-Complete$. Does that imply that finding the solution $(S_0)$ for $(A)$ is in $P$ ?
It seems so but still need confirmation.


texts: Enumeration of corner points of a polytope

texts:
Given a linear program, is there any library or available code to enumerate all the corner points of a polytope ?.

PS: Simplex method finds one corner point depending on the objective, but I need to enumerate all the corner points.

Thanks in advance!


texts: Is my algorithm to find the median of 2 sorted arrays O(log(m + n))?

texts:
I came up with a solution for LeetCode Problem 4:
Median of Two Sorted Arrays
The expected efficiency of this should be $O(\log(m+n))$, where $m$ and $n$ are the lengths of nums1 and nums2.
For my solution I decided only to process only the first half of nums1 and nums2.
Does that count as logarithmic time, or is it still linear time?
My Java code:
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // Don't need the entire array - only the first half
        int maxSize = nums1.length + nums2.length;
        int size = maxSize / 2 + 1;

        // Merged array and its index
        int[] merged = new int[size];
        int m = 0;

        // Left index, right index
        int l = 0;
        int r = 0;

        // Build the merged array
        while (m < merged.length) {
            if (l >= nums1.length) {
                // Left array exhausted - just add the right array
                merged[m] = nums2[r];
                m++;
                r++;
            } else if (r >= nums2.length) {
                // Vice versa
                merged[m] = nums1[l];
                m++;
                l++;
            } else {
                // Compare left and right
                int a = nums1[l];
                int b = nums2[r];

                if (a > b) {
                    merged[m] = b;
                    m++;
                    r++;
                } else {
                    merged[m] = a;
                    m++;
                    l++;
                }
            }
        }

        // Debug
        // for (int x : merged) {
        //     System.out.print(x + ", ");
        // }
        // System.out.println();

        // Find median based on the first half
        if (maxSize % 2 == 0) {
            // Divide with 2.0 instead of 2: important!
            return (merged[size-1] + merged[size-2]) / 2.0;
        } else {
            return merged[size-1];
        }
    }
}

Pseudocode:

Make a new array $m$, which is the size of the first half of both arrays combined

Merge both arrays together in the correct order into the array $m$
(note that this will not fully iterate the first or second array, since $m$ is only the size of the first half of both combined arrays)

Return the last element of 'm', or the average of the 2 last elements of $m$ (the median of both sorted arrays)

Leetcode result:
Runtime: 2 ms, faster than 99.75% of Java online submissions for Median of Two Sorted Arrays.
Memory Usage: 40.1 MB, less than 81.65% of Java online submissions for Median of Two Sorted Arrays.


texts:
In most PL textbooks (even in language specifications) statments like if, while, for, break are categorized as flow of control statements.
However, it is not consistent; i.e. sometimes the same text uses control-flow statement (note the dash), or control flow statment, I read sentences that says control flows...

I understand those statements control the flow of execution, hence control of flow. But many texts (even wikipedia) says otherwise, implying control is something that flows in a program

What is the formal, language-agnostic definition of this concept in CS, if any?


texts: Advantages of using prime number as interval during a shell sort?

texts: As I understand it's best practice to always use a prime number during a shell sort for its interval. Why is this the case?


texts: Number of seeks in an I/O efficent algroithm

texts:
A seek is the task of positioning the read/write head of the disk to the required data block, and irrespective of the size of the data block, all contiguous data can be accessed using a single seek. Seek complexity of an algorithm is defined as the number of times the algorithm leaves one data locality for another, (or, in other words, chooses to read or write a block that is not physically contiguous with the last block read or written) thereby
necessitating a seek.

Now consider the simple I/O efficient Matrix Transposition algorithm. It takes $E_{P \times Q}$ as input and outputs its transpose $F_{Q \times P}$

Algorithm

Let $s=\sqrt{M/2}$

for $i = 1$ to $\lceil P/s \rceil$

$\hspace{20px}$for $i = 1$ to $\lceil Q/s \rceil$

$\hspace{40px}$ $F_{ji} = E^T_{ij}$

$\hspace{20px}$endfor

endfor

This is in fact a tiling method, that creates two tiles (matrix) of size $\sqrt{M/2} \times \sqrt{M/2}$ for input and output matrices and after its computation it writes the tile in to Disk.

When $P, Q \leq \sqrt{M/2}$ and matrix is in row-major order The two matrices fit in the main memory together (which is obvious). Simply Read $E$ in, compute $F$ and write $F$. It has been claimed:

  If a seek is needed between two rows, then $S = P + Q$ (where $S$ is number of seeks) If rows follow one another contiguously, then $S = 2$.

I can't understand the above sentence. If both matrices fit in memory, then why any seeks are needed?

Reference

This statement is in  I/O Efficient Algorithms for Matrix Computations Which is a Ph.D thesis. The definition is in Page 2 and the Algorithm in Page 12.

Thanks


texts: Finding duplicate in immutable array in linear time and constant space

texts: We have a array of $N$+1 integers. The integers range from 1 to $N$. The array contains at least one duplicate. Our goal is to find one of the duplicate entries. We have the constraint that we cannot modify the input array. Is there any solution to this problem which has $O(N)$ time complexity and $O(1)$ space complexity?


texts: Question about asymptotic analysis comparing two functions

texts:
I'd be glad for an explanation on the analysis of this exercise. Given these functions: $$f(n) = n^2 \\ g(n) = n^{2/3}$$

Show that $f(n) = O(g(n))$, or $f(n) = \Omega(g(n))$ and comment if $f(n) = \Theta(g(n))$

In my answer, it is $\Theta(g(n))$ with $n_0 = 1, C = 1$

PS: The exercise requires a mathematical demonstration of the answer.


texts: Defining preferred paths makes $A^*$ heuristic lose admissibility

texts:
In a geographical graph, where each edge's cost is equal to the physical distance between its nodes, one can be tempted to manipulate the cost of some of the edges, to make it a bit lower, in order to introduce preferred paths.

So that, in the following graph, the final route would be the one in green instead of the one in grey:

The issue with this approach is that using euclidean distance makes the heuristic not admissible anymore. As an example, if we're at point A on the graph above, the euclidean distance from A to Finish can be higher than the eventual cost from A to B to Finish, considering the lowered cost between AB.

As a result, when putting many preferred routes on a much more complex graph than the one above, then the optimality of the solution is not guaranteed anymore and $A^*$ can sometimes give very erratic results.

Final objective

The final objective for this question is to come up with a way to make some paths slightly preferred over the absolute, euclidean shortest paths, when trying to predict routes, in order to model non-geographical constraints, like density of traffic or tolls.

I can think of two main ways of avoiding the exposed issue:

change the heuristic to make it admissible again (but then, how?)
use a different strategy to deal with preferred path

Any help would be appreciated.


texts:
In generating reports, sometimes there is a need to produce quite involved phrases in one of natural languages given numerical or boolean parameters.

To get a feel of it, it is enough to take a look at convert integers into words or time ago algorithms.

These solutions use (procedural/OO/functional) programming and Turing-complete computations, but the question is, whether there is some declarative approach, or hybrid approach, which can be more generic for this class of algorithms? By hybrid I understand decomposed into preparation phase (calculating or defining all necessary units, tuples and conditions), and phrase generation phase, which works with declarative definitions (some kind of domain-specific language)?

The current approach I see in Open Source projects is like the above-mentioned questions: conditional statements interspersed with string interpolations or concatenations. I guess, there are more optimal ones.

What I am searching for is some right term for the problem. I am sure there is a lot of research on the topic, but I have so far failed to come with good keywords to find suitable theory. This is something in between of constant phrases and arbitrary text generation. Ideally, the declarative part should be something easy for domain experts, like a grammar.

In practice, there is also table-driven approach, but what about theories?

Also found this oldish work A flexible shallow approach to text generation by S. Busemann and H.Horacek, but it goes too fast into too specific cases.


texts: Comparison of $(\log^* n)!$ and $(n\log n)^b$

texts:
How can I compare $(\log^*n)!$ with $(n\log n)^b$?
I know that $n^b<n!$.


texts: Determining whether a digraph has a sink

texts:
Let $G= (V,E)$ be a directed graph with $n$ vertices.
A sink is a vertex $s\in V$ such that for all $ v \in V$, $(v,s) \notin E$.  Devise an algorithm that, given the adjacency matrix of $G$, determines whether or not $G$ has a sink in time $O(n)$.
Does this pseudocode code look good?
# Input: An adjacency matrix G

# Output: True if G has a sink and False if G does not have a sink.

Algorithm DetermineSink(G)
i←0
j←0
for 0 to len(G)
   if G[i,j] = 1 ∧ j ≠ i # if there is an edge emanating from i, it is not a sink.

     return False
   if G[j,i] = 0 ∧ j ≠ i # there exists no edge and hence it is not a sink

     return False
return True


texts:
I am trying to solve some past papers in preparations for my next exam and I've stumbled across the following exercise:

While I managed to solve most parts of the exercise, I am still unsure about the formula ((b)U(b)). I am unsure which node I should start checking from and on the general definition of U.

As far as I understood a state matches a general formula aUb if it satisfies the proposition b. So in this example would the states s1, s2 and s4 all satisfy ((b)U(b))? Am I approaching this the wrong way?

Thanks a lot


texts: There is a graph with N vertices numbered from 1 to N. Edge between a and b exists if and only if a|b or b|a. If a|b then the weight of the edge is b/a. If b|a then the weight of the edge is a/b. Given two vertices u and v, I want to find the length of the shortest path between them. I think that the shortest path should pass through gcd(u, v) or lcm(u, v) (lowest common multiple), but I can't prove it. Can someone tell if my theorem is correct? If it is not correct, then how to solve this? It is not my homework.


texts: Substitution-based Operational Semantics of algebraic datatypes

texts:
Assume, I want to define the operational semantics for some subset of ML.

e ::= \\x. e | e e | c | match e with p+ | A e*
v ::= ... | \\x. e | ... | A v*
p ::= A p* -> e | x

Where e is the expression language, v are the values or normal forms, p are the patterns and A are the constructors for my algebraic datatypes.

Also assume I want to define the semantics based on substitution, not on environments. Finally, the language should be typable, e.g. every constructor will only be allowed to be applied to the same number of arguments.

So I assume, I have to introduce a "construct" operation and a "data declaration" and then substitute every constructor with an appropriate datatype declaration. But how does one define this "construct" operation? And how does the data declaration look like in an untyped calculus?


texts: Is there a name for the problem of spatially organizing a graph as to minimize total edge length?

texts:
The problem is that of spatially (with or without a fixed spatial dimension) organizing a graph so that each node becomes a cell in a grid, and each edge becomes a line, such that the total combined length of all lines (edges) is the minimal.

I want to know if that problem has a name, and how complex it is. I also would like to know if this problem is easier if done incrementally (i.e., starting with an empty graph and adding/removing nodes as to maintain that property).


texts:
I'm studying value representation in modern languages. The idea is that since in many situations the size of objects can be unknown, one can introduce a box representation of it. This box representation is just a block stored at the heap with a tag to identify it.

My questions is as follows: who deals with the size of the block? who decides the type of the tag? I'm pretty sure it is the runtime system who has to deal with it. But then what is done in compile time? How does a compiler represent objects at compile time?


texts: Interesting Speedup & Amdahl's law problem

texts:
I have found a problem on my Computer Architecture textbook which I have some issues with:

We have a process which spends its time in the following way:

50% of the time, it executes common arithmetic (non-floating point) instructions
10% of the time, it executes floating point instructions
40% of the time, it executes a function which has 4816896 instructions, which is 60% of the total of instructions

After improving the function's algorithm, we end up with 983040 instructions executed on the function instead.
Assuming that each instruction is executed in one cycle, it asks about the performance improvement after this instruction number reduction.

By calculating the speedUp in CPI before and after in the improved functions (4,9), and then using Amdahl's law, we get an increase of 46,7% in performance.
After this, it asks to calculate the speedUp again, but this time by checking the increase in MFLOPs.
How could this be done if we don't know anything about execution times?


texts: Theoretical foundations of robust and distributed services

texts:
I have the notion of a social network which is robust against malicious attacks from the outside. My vision is a system that is structurally built up as a distributed network of equal servers that operate on the same data and offer the identical services. Users should all interact on the same network, independent of the respective server they communicate with. The idea is to prevent (at least theoretically) every opportunity to bring the whole system down and to achieve a total failure of the whole service. Obviously the design of such a system is not trivial because of proper synchronization mechanisms. On the other hand there is the challenge to convey the participants to the appropriate servers. Hope you got my idea roughly.

The thing is that I only have a vague notion how such a system can function, and furthermore have seemingly successful passed over the relevant lectures about distributed systems in my cs studies. I'm therefore a little bit in a lack of an overview of relevant literature, scientific papers describing theoretical models and also real world examples.

Can anyone help me out with references, links and helpful explanations?


texts:
In an coding exam, I was once asked this question:

  Assuming that you are only sorting Integers in ascending order, which algorithm do you use when you want to prioritize speed the most, but you also want to save space?

The options were:

  LSD Radix Sort
  Merge Sort
  Quick Sort

I think an argument can be made between LSD Radix Sort and Quicksort.

Radix sort would function in $O(k n)$ and Quicksort would function in $O(n \log n)$ and worst case, $O(n^2)$

I chose Radix Sort as the answer, but I'm curious as to what others had to say.


texts: Prove the halting problem is undecidable using Rice's theorem

texts:
Is it possible to prove that the Halting problem is undecidable using Rice's theorem? Here's what I've tried and failed:

We want to reduce Rice's Theorem (decide if a language has the nontrivial property P) to the Halting Problem
We want to say "if the Halting Problem can be solved, then we can decide if a language as nontrivial property P"

Here's how I thought the proof might go:

Suppose we have a machine H that solves the halting problem. We want to use this machine to decide if a language has property P.
We construct a machine that uses H to decide a language has property P.

Example: Take P to be "language contains the string 1".

We want to use H to decide if the language of a TM M contains the string 1, i.e that the TM halts and accepts when given input 1.

Now, if M halts on 1, that doesn't mean it accepts 1, so we don't know if L(M) contains 1. On the other hand if M does not halt on 1, that certainly means that L(M) does not contain 1.

And that's where I'm stuck. Is it actually possible to use Rice's theorem to prove that the halting problem is undecidable?


texts: What is meant by Category theory doesn't yet know how to deal with higher-order functions?

texts:
In reading Uday Reddy's answer to What is the relation between functors in SML and Category theory? Uday states

  Category theory doesn't yet know how to deal with higher-order
  functions. Some day, it will.

As I thought Category theory was able to serve as a foundation for math, then it should be possible to derive all of math and higher-order functions.

So, what is meant by Category theory doesn't yet know how to deal with higher-order functions? Is it valid to consider Category theory as a foundation for math?


texts: What does flow denotes in the minimum-cost network?

texts: What is flow in context of minimum-cost network? I know that a minimum cost network is a directed graph G={V,E}, where each edge has a cost and capacity value. The problem is to find best 'path' to send d amount of flow from source to terminal node so that the total cost is minimized. My question is: what does flow denotes?