Questions about ways of storing data so that it can be used advantageously by algorithms.

learn more… | top users | synonyms (1)

0
votes
1answer
19 views

How Can we make $O(N)$ order statistic queries with Fibonacci heap in $O(N)$?

We have a Fibonacci heap with $N$ unique elements we want to make $O(N)$ order statistic queries (e.g., what is the element number 7 in this collection if it was sorted). Moreover, we know that the ...
2
votes
1answer
34 views

Does a reentrant list for signal queue in a single-thread environment exist?

I need to handle Unix signals in a single-threaded application with the following goals: Signals doesn't mask on receive (thus, the signal handler must be reentrant). I am not allowed to lose signal ...
3
votes
1answer
32 views

Data structure for optimal deduplication of common subsets

Consider a database with the following properties: It stores symbols (represented as 64-bit integers) and sets of symbols Sets may contain thousands of symbols, and there may be thousands of sets ...
-1
votes
1answer
56 views

augmenting AVL, intervals

Show how to augment dictionary of intervals (insert, delete, search) in order to make possible answer to following questions: Check if given interval $[a, b]$ intersects with some interval in a ...
2
votes
1answer
26 views

Understanding the fundamentals of building an in-Memory Distributed Graph

I am working on a project where I have to build an in-memory distributed graph capturing the relation between similar files(based on some similarity metric) stored in shared file system over multiple ...
-1
votes
0answers
19 views

C++ STL container suited for finding the nth element in dynamic ordered list? [closed]

Using balanced BST like AVL or Red-Black-Tree, we can easily maintain a set of values that: Insert/delete/query given value. Count the elements that smaller/larger than given value. Find the element ...
2
votes
1answer
44 views

Best data structure for high dimensional nearest neighbor search

I'm actually working on high dimensional data (~50.000-100.000 features) and nearest neighbors search must be performed on it. I know that KD-Trees has poor performance as dimensions grows, and also ...
-1
votes
1answer
56 views

Can a Red Black tree be constructed of only black nodes using RB insert only?

I am trying to construct a red black tree out of only black nodes. I know it is possible getting it after some deletions but I am trying to construct one only via insertion orders. Is it possible? I ...
2
votes
3answers
128 views

Memory usage of a BST or hash table?

I would like to use a data structure allowing fast access, either a balanced binary search tree (BST) for $O(\log n)$ access time or an open hash table for constant access time. 1) What is the exact ...
1
vote
1answer
38 views

Collisions in independent hashing

Let $H$ be a $s$-wise independent family of hash functions from $\{1,\ldots,M\}$ to $\{1,\ldots,N\}$. It is easy to bound one collision, but are there good bounds for muliple collision ?
-2
votes
4answers
80 views

What is an array of arrays called when all arrays have the same size?

If I have an array a of arrays, in many languages they may have different size. Is there a word for an array of arrays where all the arrays have the same length? Edit: An array of arrays may have the ...
1
vote
0answers
22 views

Any applications that need fast insert or delete for quadtrees?

I know that quadtree could be used in collision detection. But most articles I found are related with quadtree construction and retrieval. I wonder if there are some circumstances which involve both a ...
-1
votes
1answer
30 views

How to find a symmetric predecessor / successor [closed]

Lets say we have a binary tree $T$ and we want to insert key $k$. Now, assuming $k\not\in T$, how do we find the symmetric predecessor/successor of $k$? Does this relate to (pre/in/post)-order ...
4
votes
0answers
82 views

Does this data structure already exist, and is there a better alternative?

Consider a polymorphic Haskell function type, like the type for .: (a -> b) -> (b -> c) -> a -> c This type ...
1
vote
2answers
46 views

Which all nodes will qualify as an ancestor?

I was going through the fundamentals of tree structure and the definition for ancestor is as follows: A node u is an ancestor of v if there is a path from u to v. Consider the node ...
0
votes
1answer
60 views

Pairs distance to ordering?

Thanks to anon for contributing this wording: Every permutation $\pi:\{1,\cdots,n\}\to\{1,\cdots,n\}$ induces an $n\times n$ array $A(\pi)$ of the absolute differences, whose $ij$ entry is ...
0
votes
1answer
36 views

Can you increase data rate by increasing number of bits? [closed]

My question is on data rate and baud rate. data rate = baud rate * n The question is, can you keep on increasing the data rate by increasing baud rate or number of bits. I believe it can be ...
1
vote
1answer
42 views

Merging of two convex polygon chains in O(log n)

Assume I have a polygon chain implementation which is backed by a key-value store which stores the position of a point inside the chain as key and the point itself as value. So a polygon chain of the ...
1
vote
3answers
70 views

minimum subset of dominating 2D points

From an initial set $S$ of 2D points, how to efficiently compute a minimum(-size) dominating subset $M$ ? $M$ is a dominating subset of $S$ if for any $(x,y)$ in $S$ there is at least one point (a,b) ...
0
votes
2answers
54 views

Data structure with constant time operations

I need to use a data structure, implementable in C++, that can do basic operations, such as lookup, insertion and deletion, in constant time. I, however, also need to be able to find the maximum value ...
0
votes
2answers
91 views

Finding the median in a heap

Given a binary heap $H$, indexed in $[1..n]$, whose elements are integers, is there a way to quickly find its median in $O(\log n)$-time?
0
votes
2answers
43 views

Running time analysis of a linear algorithm seems to me quadratic

I have been analyzing an algorithm for several hours in order to find out why it is expressed as $O(n)$ (I saw this solution in a PowerPoint presentation which refers to it as a linear algorithm). I ...
1
vote
1answer
70 views

Getting the sorted sequence from a level-wise sorted min-heap

A heap sorted by levels is a heap which: Every parent is smaller than its children. The nodes in each level are sorted from the smallest to the greatest. I need to describe an algorithm with ...
1
vote
0answers
9 views

Saving a pointer to the n/4 node in AVL tree [duplicate]

I have an AVL Tree which every node has a filed with a key which is an integer. I need to save a pointer to the Minimum , Maximum and the $\left \lfloor \frac{n}{4} \right \rfloor $ nodes. the first ...
9
votes
3answers
608 views

What is the purpose of using NIL for representing null nodes?

In my Algorithms and Data Structures course, professors, slides and the book (Introduction to Algorithms, 3rd edition) have been using the word NIL to denote for ...
1
vote
1answer
75 views

Algorithm for finding the root element

I have the following interface: public interface TreeElement<T>{ public List<TreeElement<T>> getChildren(); } Now, suppose I have a ...
9
votes
2answers
85 views

Good snapshottable data structure for an in-memory index

I'm designing an in-memory object database for a very specific use case. It is single writer, but must support efficient concurrent reads. Reads must be isolated. There is no query language, the ...
0
votes
1answer
43 views

RAID: dedicated and distributed parity

I understand what parity is (Sort of): A data recovery mechanism where missing data is calculated based on the data that exists. However i have encountered terminology which i can't define or put ...
0
votes
2answers
45 views

For AVL Trees why is keeping a trit (left heavy, right heavy or balanced) sufficient?

I was listening to Eric Demaine's video lecture on AVL trees and there was a claim that comes up that keeping a trit on each node (to indicate whether the node is left heavy, right heavy or balanced) ...
1
vote
0answers
15 views
2
votes
1answer
50 views

Tolerated use of the term topology

In the field of data structures (and maybe in graph theory), can we use the term topology to speak about the shape of a tree? For instance, consider the two following trees : 1) The first one: Node ...
1
vote
0answers
96 views

a question of data structure

I need to suggest a data structure with memory complexity of O(n) that do the following actions: a. Init() – initialize an empty data structure. b. Insert (I,x) - insert to the i th place the ...
3
votes
1answer
88 views

Help in understanding the implementation/application of scope trees

I’m learning (self-taught) about language implementation and compiler design, and I’m implementing a toy language to cement the concepts in my mind. However, I’m having trouble understanding how scope ...
0
votes
1answer
115 views

How do binary trees use memory to store its data?

So I know that arrays use a block on contiguous memory addresses to store data to memory, and lists (not linked lists) make use of static arrays and when data is appended to the list, if there is no ...
1
vote
1answer
56 views

How can a set offer better search performance than an array

While reading the following tutorial on iOS development Working with Foundation (section on Sets near the bottom), I came across the following statement: "Because sets don’t maintain order, they offer ...
3
votes
1answer
68 views

Data structure for ordered counted set

Is there a name for a counted set (multiset) that is ordered? For example lets say this data structure represents a shopping cart (or basket if you're British). The shopping cart shows the order the ...
1
vote
1answer
56 views

Traversals from the root in AVL trees and Red Black Trees

We all know that for insertion() operation in AVL tree following can happen: We traverse down the tree from root to appropriate node and there insert the key and then for maintaining height balance ...
1
vote
0answers
19 views

Problem occurring when changing hash table size

I'm practicing an exam for a data structures course. There's a question about a hash table with hash function: $$h'(k,i)=h_1(k)+i*h_2(k) \mod{11}$$ where $$h_1(k)=k \mod{13}$$ and $$h_2(k) = 1 + k ...
3
votes
1answer
70 views

Succinct bounded-sum array with $O(1)$ access

Assume we have a $n$ sized integer array $A$, and that we know that $\sum_{i\in[n]}A[i] \le M$. Assume we are using the RAM model with $\Theta(\log n)$ sized memory words (which can be read / written ...
4
votes
1answer
118 views

Why aren't tries generally used?

To store say integers (positive), we prefer to use red black BSTs. I have never seen a explicit use of a trie anywhere to store numbers. I believe we can convert numbers to string and store them in ...
3
votes
1answer
46 views

Algorithm for automatic/optimal database joins?

I'm curious if there is existing literature or well known algorithms out there for a problem I am working on. Given a normalized relational database with valid foreign key constraints and a list of ...
1
vote
2answers
110 views

Why can't hash tables provide O(n) sorting?

Since a sufficiently large hash table takes constant time to both insert and retrieve data, should it not be possible to sort an array by simply inserting each element into the hash table, and then ...
1
vote
2answers
152 views

Finding median weights in all paths of an AVL tree with weighted nodes

I need some help with proving the complexity of the following problem (I'm new here, so please excuse my "newbie-ness") Given: an AVL tree with keys: $1,2,..,n$, such that each node $i$ in the tree ...
0
votes
0answers
27 views

Augment B+ Tree to support given search query

Given a B+ tree with M=3. We assume that the tree is static and it is not necessary to update the B+ tree. Also we know that all key-value pairs are stored in the leaves of the B+ tree. Internal nodes ...
0
votes
1answer
50 views

d-ary heapsort analysis

I need to find a tight bound on the number of comparisons in a d-ary heapsort, in terms of d and n (the length of the array we ...
0
votes
1answer
41 views

Does XML covers the representation of any structured data and knowledge

I see nowadays XML is used to structure any file or data. It can represent the flat and hierarchical relations. It even can be used to show the parse tree of a sentence in a natural language. I am ...
1
vote
1answer
97 views

Algorithm: Cracking the Safe

A safe is protected by a four-digit $(0-9)$ combination. The safe only considers the last four digits entered when deciding whether an input matches the passcode. For instance, if I enter the stream ...
4
votes
2answers
182 views

Data structure for sparse matrices for an online problem

I need to compute a large linear optimization problem very often after recieving updates to my optimization problem. That is I have a linear problem to find an x such that $x_1 * c_1 + ... + x_n * ...
0
votes
0answers
27 views

Computing optimal assignments using little memory

I have two lists where each item in the first list has a rating for each item in the second. I need to determine an optimal matching (or the best x scenarios) where items are matched, but each item ...
5
votes
4answers
174 views

Order-preserving update of a sublist of a list of mutable objects in sublinear time

Description Say I have a source list like: ["a","b","c","d"] and want to run a capitalization filter so if I change, "b" to ...