4

Consider a data structure with operations $o_1,\ldots,o_k$. We say that these operations have amortized time $t_1,\ldots,t_k$ if any sequence of operations which contains $m_i$ operations of type $o_i$ runs in time at most $\sum_i m_i t_i$. This is essentially the same definition as yours, in a more general setting. We often allow $t_1,\ldots,t_m$ to depend ...


2

Regarding the first part. Answer 1 is incorrect. Consider the graph $G = (\{1,2,3,4,5,6\}, \{(1,2), (1,3), (2,3), (3,4), (4, 5), (4,6) \})$. The maximum degree of $G$ is $3$ but the degree of $x_{(3,4)}$ in $\widetilde{G}$ is $4$. Answer 2 is correct. Consider an edge $e=(u,v)$ of $G$. The number edges distinct from $e$ that are incident to $u$ (resp. $v$) ...


2

Let's check these in reverse order. Question B: your reasoning looks good as it demonstrates that both (1) and (2) are not strong enough. The choice (4) is a possible bound, but it's not as tight as it can be. Your example is extremal in a sense that you can't make the degrees any larger, meaning that your bound is, as the question asks, "closest ...


2

To see whether a "reduction is correct and well-defined", first look at the definition: what is a reduction? In this case, you require a so-called Karp reduction or a polynomial-time reduction from Edge-Coloring to Vertex-Coloring. In particular, it must hold that (i) the process runs in polynomial time and (ii) an instance $G$ of Edge-Coloring has ...


2

Any primitive operation that can be done with edge list, also can be done in adjacency list, but the main difference between them is time complexity of the primitive operations, for example, when you want find all adjacent vertices to some vertex $v$ the time complexity is $\Theta(|E|)$ but the same operation on adjacency list is $\Theta(deg(v))$ where $...


2

I'm assuming you are interested in going over all unordered pairs of distinct words in your given set of words $S$, a collection I denote by $S_2$. You can augment a trie for $S$ with a count of the words extending each node. Suppose that a node $v$ corresponds to a prefix of length $|v|$, and has $n(v)$ words extending it. Using $v \preceq x$ to denote &...


2

I am not sure about BallTrees, but kd-trees definitely support deletion (see my Java implementation here). I think the reason why it is often not implemented is that it is a lot more complex and may be a lot slower than a typical insertion. For example, you first need to find a proper replacement point. As @Andrea Nardi pointed out, in kd-trees insertion and ...


2

My experience comes mainly from kd-trees. I think this answers part of your question and the attached image really visualizes the problem. When you construct the kd-tree initially the tree is constructed in a way that is balanced. If you add vertices to the tree, especially if you are adding points in a trajectory (e.g. the points that an airplane traversed) ...


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