3

$\DeclareMathOperator\s{size}\def\f#1{\lfloor#1\rfloor}\def\c#1{\lceil#1\rceil}$As already pointed out by gnasher729, the statement is not literally true when $n\equiv1\pmod3$: if $n=3k+1$, there are binary trees of size $n$ whose all subtrees have size either $\le k<n/3$ or $\ge2k+1>2n/3$. A version suitable for all $n$ can be proved as follows. Let $\...


2

Here is one simple idea -- not sure if it's practical. Define $\mathsf{sketch}_n(X)$ to be a length-$n$ bitstring in which bit $i$ is set iff there exists $x \in X$ such that $x = i \mod n$. In practice, this means that inserting an element $x$ into a set involves turning on bit $x \mod n$. $\mathsf{disjoint}_n(\cdot)$ is defined as before. Then $\mathsf{...


2

GCC C++ case study Let's also get some insight from one of the most important implementations in the world. As we will see, it actually matches out theory perfectly! As shown at https://stackoverflow.com/questions/2558153/what-is-the-underlying-data-structure-of-a-stl-set-in-c/51944661#51944661, in GCC 6.4: std::map uses BST std::unordered_map uses hashmap ...


2

Yes, there are many types of lists depending on the arrangement of objects and the complexity of different types of operations. For example: Binary Tree or d-ary tree is a hierarchical structure that stores nodes in the form of parent and child nodes. Directed or Undirected Graph can be represented using adjacency list data structure which represents all ...


2

Let us denote the solution for a string $w$ and a set $A$ of remaining letters by $s(w,A)$. Also let $A = a_1 < \cdots < a_n$. If $w$ equals $>^{n-1}$ then clearly the solution is $a_n a_{n-1} \ldots a_1$. If $w$ starts with a run of $\ell$ many $>$'s (possibly $\ell=0$), then the first $\ell+1$ letters of any solution must be $a_{\ell+1} \ldots ...


2

This is the special case of the multidimensional knapsack problem where each item (tray) has the same value (consider the set of trays you don't select). It presumably remains NP-hard, but can be solved by a number of methods. Probably the easiest to try first is to formulate this as an instance of integer linear programming and then apply an ILP solver to ...


1

Databases have some issues that "mere mortal" data storage doesn't concern itself with, such as transaction safety and disk failure. Here are a few classic papers on the topic: Astrahan et al (1976), System R: A Relational Approach to Data Base Management, ACM TOMS 1:2, pp 97-137. Stonebreaker et al (1976), The Design and Implementation of INGRES, ...


1

A "list" or "sequence" is an ordered collection of elements. So there are a lot of lists. In addition to an Array and a Linked List: Doubly Linked List https://en.wikipedia.org/wiki/Doubly_linked_list (including XOR linked list) Unrolled Linked List https://en.wikipedia.org/wiki/Unrolled_linked_list K-ary tree (including Binary Tree) ...


1

Yes. Use any linear function as your hash function. If $h(x)= \alpha x + \beta \bmod n$, where $\alpha,\beta$ are fixed constants, then $$h(x+\delta) = h(x) + \alpha \delta \bmod n.$$ Consequently, $\mathsf{shift}$ can just rotate the bitstring right by $\alpha \delta$ positions. Note that if $n$ is prime this hash function is 2-universal, so it should be ...


1

If you tried to get the longest stick out of 10, and they were shown to you in random order, how would you proceed? Here’s a simple strategy, based on the simple idea that it’s daft to pick a stick that isn’t the longest so far: Don’t take any of the first four sticks, then pick the first stick that is longer than the longest so far. How will this work out? ...


1

Consider the variant of the problem in which the people are arranged in a segment instead of circle and let $S(n)$ be the number feasible arrangements for $n$ people. Now lets go back to your original problem, and let's name $C(n)$ the number of feasible arrangements of $n$ people. Clearly $C(0)=C(1)=1$ and $C(2)=2$, so we will henceforth suppose that $n \ge ...


1

What's wrong with (i) + j + k ? I live in a world where floating-point arithmetic has rounding errors, and where integer arithmetic has overflow checks, so (i + j) + k and i + (j + k) are most definitely not the same, for example if i is a large positive integer, and j, k are two large negative integers then the second one can produce an overflow (crash) ...


1

It’s not true for trees with 3k+1 nodes. There is supposed to be a subtree with k+1/3 to 2k+2/3 nodes, that is k+1 to 2k nodes. Take a tree starting with only left nodes until we have a subtree of 2n+1, and then both sub trees have size n. The theorem fails. So assume n = 3k or n = 3k+2. n = 3k: We start with N = root of the tree. As long as N has a subtree ...


1

Preprocessing: For each $(k_i, v_i)$ pair, and for each $x \in k_i$, add $(x, (k_i, v_i))$ to a map data structure (e.g., a hashtable) with $x$ as the key. To process a query $q$, for each $y \in q$ look up all values in the map, append all of them to a list, and finally remove duplicates (or instead add them directly to a data structure that can collapse ...


1

Think of the hash function as a box with input and output values. Here, the number of possible output values is fixed to 10 (because of the mod10). Hence, uniformity depends on the input and the function. Our input is uniform in this case(whole numbers). But the functions seem to mess up this uniformity(or variability). We'll choose the one which preserves ...


Only top voted, non community-wiki answers of a minimum length are eligible