algorithms – PostOrder from preOrder and parent array

The preorder traversal of a labelled rooted tree is the sequence of labels obtained by the label of the root followed by the preorder traversals of the subtrees of the root in the order they appear.
The postorder traversal of the tree is obtained by the postorder traversals of the subtrees in the order they appear, followed by the label of the root.
A convenient way of representing a rooted tree is to label the nodes from $0$ to $n-1$ in preorder, and store an array parent, where $parent[i]$ gives the preorder number of the parent of the node whose preorder number is $i$.
Given such a representation, computes the list $L$ of preorder numbers of nodes in the order they occur in the postorder traversal of the tree. Assume $parent[0] = -1$ and the parent array is available.

algorithms – Black Box Problem

Suppose we have mysterious machine which return median $m$ of given set $S$ and set $S/{m}$ in constant time, where $S/{m}$ denotes the difference of $S$ and element $m$. Prove that we can sort any list of $n$ elements in linear time using such machine. (extra space is allowed)

Here is my idea, which works intuitively correct, but could not prove it mathematically:

Create a new array with $n$ elements and assign median $m$ of original set $S$ to the middle of array. In each iteration, we put new median of $S/{m}$ into the right or left of recently used element: if it was on the left, put new median on the left of that element, and similarly for rightmost element. However, I could not think on how mathematical proof would be possible here. Would welcome your comprehensive proofs for this problem.

Note: If number of elements is even, median is defined as smaller middle number.

algorithms – Set relationship between Big-Oh and Theta notations

I was reading “Introduction to Algorithms” by CLRS and it says that:

We write $f(n) = O(g(n))$ to indicate that a function $f(n)$ is a member of of the set $O(g(n))$. Note that $f(n) = Theta(g(n))$ implies $f(n)=O(g(n))$, since $Theta$-notation is a stronger notion than $O$ notation. Written set-theoretically, we have $Theta(g(n)) subseteq O(g(n))$.

Q1: What do the authors mean by strong notion? What is strong notion, when we use it, how does it help us (here) knowing one implication is stronger than the other and how does it affect when creating implication.

Q2: It seems contradictory in a sense by saying that $Theta$ is stronger notion than $O$ and then writing $Theta(g(n)) subseteq O(g(n))$.How to deduce and then interpret the second sentence from the first?

I would appreciate your answers.

algorithms – How to tell if a group of items is stacked horizontally or vertically based only on their positions?

How do you tell if a group of items is stacked horizontally or vertically given only the items x and y positions?

Vertical Group:

Horizontal Group:

• item 1 • item 2 • item 3

The items in the vertical stack can be moved left or right but each item is further down from the last.

The items in a horizontal stack can be higher up or lower down than the first item.

What I’m doing now to check for a vertical stack is to check if the second item Y position is greater than the first item Y position. But if it is a horizontal group of items and the items are stair-cased down from top to bottom then it would fail.

    if (secondItemY>topY) {
        return true;
    }

I almost had it figured out

algorithms – Partition a set of factors so that the difference between products is minimized

I’m sure this problem must be well-known…

Given a collection $S$ of numbers, partition them into exactly two sub-collections, $A$ and $B$ (I mean, by definition $B$ is just $S-A$) such that the difference of products
$$
Delta = left|left(prod_{xin B}xright) – left(prod_{xin A}xright)right|
$$

is as small as possible.

If it helps, you can assume that all the members of $S$ are integers, and in fact you can assume that they are all prime! In my particular use-case, we’re trying to split some big integer $n$ into its “squarest possible” pair of factors, and $S$ is simply a prime factorization of $n$ which we happen to have lying around.

What’s the best way to do this? The brutish ways I have thought of are:

  • Trial division (assuming everything is prime). Awful performance.
    int PS = productOf(S);
    for (int PA = sqrt(PS); PA >= 1; --PA) {
        if (PS % PA == 0) {
            int PB = PS / PA;
            return { factorsOf(PA), factorsOf(PB) };
        }
    }
  • Search all the possible partitions. Would give better performance, I think, because $lvert Srvert! ll prod{S}$, but still “obviously” a dumb algorithm.
    int currentDiff = productOf(S);
    intset currentA = {};
    for (intset A in partitionsOf(S)) {
        int PA = productOf(A);
        int PB = productOf(S)/PA;
        if (PB >= PA && PB-PA < currentDiff) {
            currentA = A;
            currentDiff = PB-PA;
        }
    }
    return { currentA, S - currentA };

Is there any simple-ish algorithm to solve this problem without relying on brute exhaustive search?

I wonder if it would work to minimize the difference of sums $sum_{xin B}{log{x}} – sum_{xin A}{log{x}}$, and if that problem has a simpler known solution…

algorithms – How to get a piece of the Pie? Theoretical Plate Stacking Problem

This is just a theoretical problem that I found in the wild and want to know your solution.

A stack of plates is made between you a cousin and a few others.

Every (4 to 7) many random hours the plate on the top of the stack is given a slice of pie yet at this point you can instantly replace the pie with a new empty plate the goal of the exercise is having your plate on top the longest to get the most pie.

Cousin 1: Watches when you have placed your plate on top of the pile and then after a random interval of time about long enough to avoid being called out for being unfair lets say 45min-1h places his plate on top of yours.

Cousin 2: Watches when Cousin 1s plate is on top of his and then waits the same interval to avoid being unfair.

myIdea:
The goal of the problem is to get more pie the most pie. And the only way that I see it as possible is to cheat more then your cousins.

IF you put down a plate then wait the minimum random interval after cousin 2 has placed his plate then you are likely only getting an equal share of time and probability of getting pie.

Cheating method: You do the same thing as both cousins but you time the the average time between cousins 1 and 2 placing their plates. Using this average of time you take half the time and the same standard deviation. I then post after cousin 2 in this time period which gives me an equal amount of pie as cousin 1 but more then cousin 2.

Is there any way to get more pie then both cousins?

algorithms – Number of words with substrings from the dictionary

Thanks for contributing an answer to Computer Science Stack Exchange!

  • Please be sure to answer the question. Provide details and share your research!

But avoid

  • Asking for help, clarification, or responding to other answers.
  • Making statements based on opinion; back them up with references or personal experience.

Use MathJax to format equations. MathJax reference.

To learn more, see our tips on writing great answers.

algorithms – Encoding a lot of categorical variables

I have 10 million categorical variables (each variable has 3 categories). What is the best way to encode these 10 million variables to train a deep learning model on them? (If I use one hot encoding, then I will end up having 30 million variables. Also, embedding layer with one output makes no sense (it is similar to integer encoding and there is no order between these categories) and embedding layer with two outputs does not make that much difference. Usually, we use embedding layer when number of categories is a lot). Please give me your opinion.

computer vision – Shape-from-shading algorithms?

Before I go to the effort of writing my own code, I was wondering if there is code available for shape-from-shading algorithms. These take an image (such as a black-and-white image, such as this) and infer the three-dimensional depth map based on the lightness at a point and constraints such as smoothness of the inferred surface, or properties of the light source (e.g., a point source from a known direction).