According to this book (Chapter 3.2), a node in a BST has rank $k$ if precisely $k$ other keys in the BST are smaller. So, if you order all the BST nodes according to their keys, then each node with ...

Computer Science is a multifaceted discipline - and Algorithms and Data Structures is important part of it. You can try free video-courses, like Algorithms, Part 1, from Princeton University - it's ...

Bjarne Stroustrup writes in his The Design and Evolution of C++ book (item 3.5.1): At this point, the object model becomes real in the sense that an object is more than the simple aggregation of ...

The non-recursive term of the recurrence relation is the work to merge solutions of subproblems. The level $k$ of your (binary) recurrence tree contains $2^k$ subproblems with size $\frac {n}{2^k}$, ...

In a given tree, all the vertices of this tree correspond to binarySum() calls. The value of parameter n to binarySum() is halved at each recursive call. Also, each recursive call finishes after all ...

The solution outline: Step 1. Verify, that all the initial (at the moment $t=0$) wave circles don't contain your starting point $(0,0)$. If yes, then continue - otherwise exit, no escape. Step 2. ...

It means that each edge has only one weight, which is defined as a real number. So, this definition in compact form excludes many cases, for example: an edge doesn't have weight at all an edge has ...

Recurrent equation: $$T(n) = 4 \cdot T(\frac{n}{2})$$ $$T(1) = O(1)$$ Its solution: $$T(n) = \Theta(n^2)$$

It looks like a sublinear algorithm for the Ball Range Counting Problem isn't known for now. However, if you could accept a non-exact answer then you could approximate a disk by a set of squares with ...

You can color a pair of arcs $(a_1,a_2)$ by the same color, if and only if all the paths from the source to the sink, passing through the arc $a_1$, also pass through the arc $a_2$. Let's consider the ...

Let's define a function $f: \Bbb R \times \Bbb R \rightarrow \left [0, n \right ]$, returning a number of points from the set $P$, covered by a unit disk with the center at the point $(x, y)$. This ...

There is a Law of Distributivity of Boolean operation $\lor$ (disjunction, which is sometimes denoted by $+$) over Boolean operation $\land$ (conjunction, which is sometimes simply omitted): $$x \lor (... View answer Accepted answer 4 votes Find all the strongly connected components (SCC) of the original graph. Replace each SCC by a single node - the resulting graph G' will be acyclic. Find all the sources and sinks in G' - let m ... View answer 4 votes Proof by induction Basis. All complete oriented digraphs with two vertices have Hamiltonian path - it's obvious. Induction step. Let's assume that complete oriented digraph G_{n-1} with (n - 1) ... View answer Accepted answer 4 votes The sweeping algorithm, suggested by @adrianN, can be elaborated this way. Step 1. Put all your rectangles in a map of sets in such way, that: the map key is left boundary of rectangle the map value ... View answer Accepted answer 4 votes The more strong estimate is correct: 2^n = o(2^{2n}) Just look at definition of the little-o. For any constant c \gt 0 you need to find a constant n_0, such that for all n \ge n_0 you get 2^... View answer Accepted answer 4 votes The question is about upper bound (which is O(n^{2013} / (\log n)^{2012})) and lower bound (which is O(n^{2012.9})) – do they correspond to each other? According to definitions of Big-O ... View answer Accepted answer 3 votes The answer is "No". Please see a counterexample below: View answer 3 votes The following algorithm will find some set of circles, containing all the points in the set A except all the points in the set B. This solution might be not optimal (please see the @... View answer Accepted answer 3 votes This problem is a variation of the Maximal Independent Set (MIS) problem in graph theory. To understand that you need to convert your point set N into a graph G=(N,E), where any two vertices N_1,... View answer 3 votes$$2^N \bmod 10 = 2^{(N-1) \bmod 4 + 1} \bmod 10$$(try to prove it) View answer Accepted answer 3 votes Two old, but, I think, still very useful resources: M.T.Goodrich, M.R.Ghouse, and J.Bright. Sweep Methods for Parallel Computational Geometry. Algorithmica (1996), 15:126-153. - closely related to ... View answer Accepted answer 3 votes Step 1. Sort all the points according to their x-coordinate - you will get an array of buckets, where each bucket contains a (sorted) list of points with the same x-coordinate. You can drop (or ... View answer Accepted answer 3 votes The Optimal Binary Search Tree is exactly what you need. Welcome to the site! View answer 3 votes The memory you are asking about really exists and is called framebuffer. However, it's not easy to directly access this memory on modern computers, because it's intentionally hidden from user ... View answer 3 votes The vector equation:$$P_1 + \alpha * (P_2 - P_1) = P_3 + \beta * (P_4 - P_3)$$where P_1 = (x_1, y_1) etc., should have a solution in the unit square:$$0 \le \alpha \le 1, 0 \le \beta \le 1 ...

From my answer to a similar question: A Delaunay edge $(x,y)$ won't be a Gabriel edge, if the set of all the possible empty disks with $x$ and $y$ on their boundaries doesn't contain the disk with ...

The set of $2n$ lines on the plane form a well studied Arrangement of lines, which is a type of planar subdivision, composed of vertices, edges and faces. This planar subdivision used to be ...