HEKTO
  • Member for 8 years, 1 month
  • Last seen this week
  • United States
What is "rank" in a binary search tree and how can it be useful?
Accepted answer
12 votes

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 ...

View answer
Computer science for programmers
Accepted answer
11 votes

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 ...

View answer
Why are struct and class essentially the same in C++?
Accepted answer
9 votes

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 ...

View answer
Solving T(n) = 2T(n/2) + log n with the recurrence tree method
6 votes

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}$, ...

View answer
Space complexity analysis of binary recursive sum algorithm
Accepted answer
6 votes

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 ...

View answer
Intersection of O(n) expanding circles with line from the origin
Accepted answer
5 votes

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. ...

View answer
Weight functions in graph algorithms
5 votes

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 ...

View answer
what is the time complexity for an algorithm that operations to complete grows by 4 when doubling the input length?
Accepted answer
5 votes

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

View answer
Complexity for finding a ball that maximizes the number of points lying in it
Accepted answer
5 votes

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 ...

View answer
How to edge-color a directed acyclic graph so that every path visits none or all edges of each color?
Accepted answer
4 votes

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 ...

View answer
Maximal subsets of a point set which fit in a unit disk
Accepted answer
4 votes

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 ...

View answer
Simplifying the Boolean expression $A + \bar{A}\bar{B}$?
Accepted answer
4 votes

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
How to minimally extend a digraph such that all nodes are on a cycle?
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
Hamiltonian path in directed graph
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
Data structure for adjacent rectangles
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
Big O relation between $2^n$ and $2^{2n}$
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
Are there problems with complexity between $O(n^c/\log^b n)$ and $O(n^{c - \varepsilon})$?
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
Binary Plane Partition: do we have to split a line segment?
Accepted answer
3 votes

The answer is "No". Please see a counterexample below:

View answer
Minimum circles to cover a set of points and avoid another set of points
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
Optimal solution for Weighted points problem
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
how to calculate $2^{5000}$ mod 10 without calculator in fast way?
3 votes

$$2^N \bmod 10 = 2^{(N-1) \bmod 4 + 1} \bmod 10$$ (try to prove it)

View answer
Parallelization of priority queue-based algorithms
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
Find axis-aligned rectangle with maximum area in a point set in the Euclidean plane
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
Searching for an item over a non-uniform query distribution
Accepted answer
3 votes

The Optimal Binary Search Tree is exactly what you need. Welcome to the site!

View answer
What is the signal going from the computer to the screen?
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
criterion for two line segments intersecting
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$$ ...

View answer
What edges are not in a Gabriel graph, yet in a Delauney graph?
Accepted answer
2 votes

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 ...

View answer
Number of double wedges containing a point
2 votes

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 ...

View answer
Finding closest line segment intersecting rays
Accepted answer
2 votes

You'll need two data structures - for vertical rays and for horizontal rays. I'll describe a data structure for vertical rays. Draw a vertical line through each segment end - you'll get a set of ...

View answer
How to edge-color a directed acyclic graph so that every path visits none or all edges of each color?
2 votes

This answer is an improvement for my (already accepted) original answer, which describes an exact, but potentially very slow algorithm. This improvement was inspired by the @pcpthm answer, however I ...

View answer