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

learn more… | top users | synonyms (1)

-1
votes
1answer
23 views

How to find a symmetric predecessor / successor

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
69 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
43 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
57 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
32 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 ...
0
votes
1answer
25 views

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

assume i have a polygonchain 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
59 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
38 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
85 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
37 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
69 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
8 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
591 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
73 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 ...
8
votes
1answer
65 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
30 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
35 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
92 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
77 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
74 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
53 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
65 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
47 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
68 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
112 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
44 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
105 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 ...
0
votes
1answer
65 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
26 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
40 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
40 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
94 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
167 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
26 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
166 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 ...
0
votes
1answer
42 views

What is the advantage of seperate chaining over open addressing?

Hash tables resolve collisions through two mechanisms, separate chaining or open hashing and open addressing or closed hashing. Though the first method uses lists (or other fancier data structure) ...
5
votes
1answer
98 views

Is it possible to implement a dictionary with efficient access according to insertion order?

I am trying to build a generic data structure that needs to hold keys and values and in the same time keep track on the indices in which keys and values were put in, like arraylists do but in a ...
4
votes
1answer
51 views

How are graph representations containing only (i, j) instead of both (i, j) and (j, i) named?

When working with undirected graph algorithms using an adjacency-list type structure, it's sometimes enough to store a given edge (i, j) just stored in the list of ...
0
votes
1answer
44 views

A many-to-many mapping data structure

What would be a good way representing: i. Given a key, return all the data values associated with that key AND ii. Given a data value, return all the keys that are associated with that data. So far, ...
1
vote
1answer
31 views

Formula for returning the size of a circular array

I've come across a way of implementing a circular array that represents a double ended queue. Let the circular array have the following instance variables: ...
4
votes
2answers
114 views

Split in AVL tree with complexity $O(\log n)$

Can the split operation be implemented for AVL trees with complexity $O(\log n)$? I'm interested in links to articles or any specific information about this subject. The split operation divides the ...
3
votes
0answers
37 views

Finding the distance to the nearest neighbor for each point in a set of points in $R^n$

I have a list of points in $R^n$, and for each point I want to find the Euclidean distance to the nearest other point in the list. I don't need to know the coordinates of the nearest neighbor; I only ...
3
votes
1answer
34 views

Why in a min priority queue (heap based) it is called “decrease-key” and not just “set-key”?

When you call decrease-key in a min priority queue, you are basically setting the key, you can accidentally put a higher key, right? so why isn't it called "set-key" or "update-key"? why (according to ...
2
votes
0answers
39 views

Segment trees with insertion/deletion

I have a range query problem to solve. This problem requires not only range queries and update, but also insert or delete an element of the array. There is a series of operations that must be done in ...
-1
votes
1answer
29 views

Fit stack of stone of varying length into a well of varying length

I have a stack of m stones of different Diameter. stack = [5,4,9,20,1] And a Well that is of depth n with varying diameter at different depths . ...
3
votes
1answer
36 views

Red-black tree. Adding a red child to a red node with a black sibling

According to my lecture notes, adding a red child to a red node with a black sibling in a red-black tree, is equivalent to changing a 3-node into a 4-node in a 2-3-4 tree. I've built several red-black ...
0
votes
1answer
164 views

What are the main ideas used in a Fenwick tree? [duplicate]

While I was solving a programming competition question, I came across a technique advertised as suitable for the solution. A so called Fenwick tree (a.k.a binary indexed tree) was at the heart of this ...