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

learn more… | top users | synonyms (1)

1
vote
0answers
35 views

kd-tree stores points in inner nodes? If yes, how to search for NN?

The link in wikipedia about kd-trees store points in the inner nodes. I have to perform NN queries and I think (newbie here), I am understanding the concept. However, I was said to study Kd-trees ...
0
votes
0answers
19 views

Does an associative array represent a mapping?

An associative array is a set of pairs (key, value). Does it represent a mapping, or a relation (i.e. does it allow the same key to be associated to different values)? Does it represent an ...
3
votes
1answer
46 views

What is this problem? Largest set of contiguous x values for which the same y value can be held

I'm trying to find a linear solution with a small constant factor but I'm not sure what to search for, or even how to succinctly describe it. The best I've come up with is: Given a set of ...
1
vote
2answers
43 views

“Minimum Stack”

I am now preparing for a test in my algorithms course and I have stumbled upon a question about a data structure which seems too trivial for me, but is probably not trivial at all. The question is: ...
5
votes
3answers
93 views

Compact representation of paths in a graph

I've a subset of the simple paths in a graph. The length of the paths is bounded by $d$. What's the most compact way (memory-wise) I can represent the paths such that no other paths apart from the ...
3
votes
1answer
50 views

Finding nd - m dimensional neighbors for a given node within a balanced hyperoctree

I'm writing a balanced $n_d$-Hyperoctree data structure in which the only fundamental operations I provide are edge traversals between parent and child nodes. I'm storing the nodes using a Morton ...
1
vote
2answers
76 views

Why should leaf nodes in a red-black tree be black?

From the property of Red-Black Trees we know that: All leaves (NIL) are black. (All leaves are same color as the root.)(Comren et al "Introduction to Algorithms") But what is the reason that we ...
-1
votes
1answer
33 views

insert and delete in order statistic tree

I am having trouble in understanding order-statistics tree . Definition : Every node in tree stores the number of descendants of itself . Can you please explain the Algorithm or pseudocode how to ...
4
votes
1answer
22 views

What progress has been made on persistent catenable deques in the last decade?

Kaplan and Tarjan came up with the first ones in 1995; Okasaki came up with a simpler, amortized version in 1997 using lazy evaluation (See Okasaki for references). Then a couple years later, Kaplan, ...
1
vote
1answer
31 views

Is this a proper Max Heap Data Structure

I was trying to understand the concept of Max-Heap. And to my understanding its a complete binary tree and each parent has a value greater than its children.The example I was going though had the ...
1
vote
1answer
61 views

Recurrence of T(n) = T(n/3) + T(2n/3) [duplicate]

I've searched online for this but I only seem to find answers for a similar equation: T(n) = T(n/3) + T(2n/3) + cn But the one I'm trying to solve is: ...
4
votes
3answers
74 views

Efficiently representing a set of sets

(The question is an extension of this unanswered question on stackoverflow) If we have a set of strings, we can efficiently represent them with tries. Common branches can also be merged, resulting in ...
1
vote
0answers
71 views

What is a suitable Data Structure in this scenario?

$n_1$ is the number of insertions per unit time. $n_2$ is the number of deletions per unit time. $k$ is the number of searches per unit time. I have 4 possible cases: 1. $k \gg n_1,n_2$ with ...
1
vote
1answer
41 views

Why do we use several bits instead of a single bit for storage of objects in Bloom Filters

Bloom filters are a variant of hash tables except it is much more space efficient at the cost of a low probability of false positives . How it works : Assume there are 10000 bits , 3 hash functions ...
0
votes
1answer
71 views

Disjoint Set - Tree Implementation with Union-By-Rank and Path Compression

Union-By-Rank and Path Compression is supposed to improve the performance of a tree implementation of a disjoint set. However, in looking at the UNION(x, y) operation, I noticed that if x and y ...
5
votes
1answer
158 views

What is the expected number of nodes at depth d of a tree after i random insertions

Suppose one wanted to build a tree at random. Let the first insertion at step $i = 1$ be the root node. From here, nodes are inserted into the tree at random one at a time. How would one go about ...
1
vote
1answer
17 views

Do the two huffman trees have the same corpus?

Consider the following Huffman trees: I was asked if those trees can have the same corpus. My answer was no, based on these calculations: For the right tree: $a_1 \le a_2$ $a_1 + a_2 \le a_5$ ...
0
votes
0answers
46 views

Amortized Cost of a delete from an extendable heap

Given an extendable heap with $n$ elements and an array size of $A$, I'm trying to use the accounting method to find the amortized cost of a delete. We want a load factor of $\frac{1}{4}$. So, ...
1
vote
1answer
66 views

How can I have constant time initialization for multi-dimensional arrays?

For a regular array, I understand that if we have the tradeoff of space vs time, and we use more space to implement a Which, Data, and When pointers to the actual array, we can initialize the array in ...
0
votes
1answer
127 views

Impact on the order of elements on the cost of searching in a linked list

I have the following homework question that I am struggling with. I have read the corresponding chapter from the book, but no guidance there. Consider a linked list $X: X_1 \to X_2 \to X_3 \ldots$. ...
4
votes
2answers
62 views

Generation of random binary trees

Given n, I want to randomly generate a binary tree (unlabelled) that has n end nodes. Could someone kindly provide a reference containing an algorithm for doing that? I attempted to do as follows: ...
0
votes
2answers
156 views

Basic action for every data structure O(1) [closed]

My lecturer for Algorithms said that most of the data structures I will encounter in the algorithms course I am taking have a basic action which is of O(1). Ex: Binary heap. Basic action is: ...
3
votes
3answers
177 views

Algorithm Request: “Shortest non-existing substring over given alphabet”

I'm looking for an (efficient) algorithm to solve the following problem: Given a string $S$ and a set of characters $M$, find the shortest string composed only of characters in $M$ that is not ...
1
vote
0answers
31 views

Binary search tree with $n$ internal vertices [closed]

How can we prove a binary search tree with $n$ internal vertices has height $h = \lceil \log(n+1) \rceil$?
3
votes
0answers
38 views

Updating the Cheriton-Tarjan MST algorithm to use binomial heaps?

The Cheriton-Tarjan MST algorithm finds MSTs in time O(m log log n) in arbitrary graphs by using a cleverly-modified version of a leftist heap data structure to store edges. It was developed in 1976. ...
2
votes
0answers
47 views

What are applications of alphabetic trees?

Earlier this week a paper was released describing an algorithm for building optimal alphabetic ternary trees. The alphabetic property as described on Wikipedia as Alphabetic trees are Huffman ...
2
votes
0answers
22 views

Polylogarithmic value-bounded concurrent data structures such as max register, counter, and monotone circuit

While reading the research paper Polylogarithmic Concurrent Data Structures from Monotone Circuits [@JACM'2012] by James Aspnes, Hagit Attiya, and Keren Censor-Hillel, I am not sure about some points ...
6
votes
2answers
153 views

Looking for a set implementation with small memory footprint

I am looking for implementation of the set data type. That is, we have to maintain a dynamic subset $S$ (of size $n$) from the universe $U = \{0, 1, 2, 3, \dots , u – 1\}$ of size $u$ with ...
5
votes
1answer
132 views

What is a clairvoyant algorithm?

When talking about general data structure design, my lecture notes talk about one of the concerns being cost of operations. As well as the individual cost, it mentions amortized cost. But then it goes ...
-1
votes
1answer
128 views

AVL Trees - Maintaining Closest Pair information on a Delete [duplicate]

In the accepted answer to my question Data Structure For Closest Pair Problem, I do not see why deletion works. Let's say (x, y) are the closest pair before the delete. If the node to be deleted is ...
1
vote
1answer
222 views

Data Structure For Closest Pair Problem

Suppose I have a list of distinct integers. I'm looking for a data structure that will support the operations search, insert, ...
2
votes
0answers
34 views

The research area of data exchange format,i.e. the format that stores serialized objects [closed]

As we know, if we want to design and implement a programming language like JAVA, C++ and C language, we will reference the compilation theory. Similarly, if we would like to design and implement a ...
1
vote
0answers
57 views

Triangle mesh surface area after affine transformation

Let $\mathbb{M}$ be the set of all 3D triangle meshes. Let $a:\mathbb{M} \rightarrow \mathbb{R}$ be a function that computes surface area of the mesh. Let $\mathbb{T}$ be the set of 3D affine ...
1
vote
0answers
35 views

LLRB Tree How to prove if left and left of left node are black, then this node must be a red node?

Im learning the delete operation on Left-leaning Red Black Tree invented by Prof. Sedgewick. In delete operation, a node could be only deleted from a 3-node or a 4-node but 2-node. In order to ensure ...
1
vote
1answer
20 views

Understanding expected time bound for unsuccessful search in R-way tries

As per Tries slides (page 17) from Algorithm 4th edition book by Robert Sedgewick, the asymptotic expected runtime for an unsuccessful search in $R$-way tries miss is $O(\log_R N)$. Can someone please ...
1
vote
1answer
74 views

Minimum number that cannot be formed by any subset of an array

We have an array of Integers, $A[]$ and we have to find the minimum number that is not the sum of a subset of array using the elements from $L$ to $R$ indices. I was thinking of using coin change DP ...
-1
votes
1answer
40 views

Case distinction in B-tree deletion

Here is how deletion in B-trees is described: If the key k is in node x and x is a leaf, delete the key k from x. If the key k is in node x and x is an internal node, do the following. ...
-1
votes
1answer
33 views

How to determine the address of an element in a square matrix given the base address? [closed]

I was asked this question in examination. A square matrix $M$ of size $10 \times 10$ is stored in memory with each element requiring 4 bytes of storage. If the base address at $M[0][0]$ is $1840$, ...
0
votes
0answers
15 views

Is there a fusion law for the mapreduce operation used on conc-lists?

Conc lists are similar to cons lists. In contrast to folds, mapreduce is the main "iterating" operation used on it. Composed mapreduces produce intermediate lists. Is there a fusion law for them, ...
-1
votes
3answers
189 views

Which data structure to use for accessing min/max in constant-time?

I need a data structure which can include millions of elements, minimum and maximum must be accesable in constant time and inserting and erasing element time complexity must be better than linear.
1
vote
1answer
72 views

Queue, moving the element at the tail to the head

Suppose I have a queue where I pull from left and push to the right, and suppose I have the contents in the queue as $a b c @ d e$ (from left to right, left is head, right is tail). Is there a simple ...
-1
votes
1answer
89 views

how to calculate Average-Case complexity time by using worst-case and best-case complexity time?

For example let's say that we know that the worst-case running time is o(n) and the best-case is o(1). how can i get the average-case running time using the given big Ohs?
0
votes
3answers
52 views

How are image files, sounds, data, etc. compiled/linked in to a single file?

I'm both asking for me & future readers as to how pictures, sounds, textures, assets, and such are compiled and linked in to one binary/program, and how that process works. I have seen this in ...
1
vote
2answers
217 views

Dijkstra's algorithm for edge weights in range 0, …, W

Suppose I want to run Dijkstra's algorithm on a graph whose edge weights are integers in the range 0, ..., W, where W is a relatively small number. How can I modify that algorithm so that it takes ...
2
votes
2answers
79 views

What is this hash of array data structure called?

I've created a data structure that is a hash of arrays with a special property: the hash keeps track of the combined order in which items are appended to its arrays. For example (pseudocode): ...
1
vote
1answer
40 views

Doesn't post-order traversal require subtrees to be evaluated separately?

Consider this tree: If I traverse it using post-order, I'd start at B (as it is the leftmost leaf) and that's where my misunderstanding begins. I know B is the first and A will be the last node in ...
0
votes
1answer
72 views

Data structure to use for a consumable message queue where it's safe for messages to overwrite one another

I have a queue of messages representing filesystem operations that need to be processed in order. A message may succeed or fail when it's sent. A change message, for example, is generated when a user ...
1
vote
2answers
43 views

Hashing a Specific Range Of a Character Array [closed]

I need to process queries to Hash various ranges of a character array. I am currently using the Arrays.hashCode from the standard java library. But the problem is that this method is too slow. Also my ...
9
votes
1answer
138 views

Data structure for map on intervals

Let $n$ be an integer, and let $\mathbb{Z}$ denote the set of all integers. Let $[a,b]$ denote the interval of integers $\{a,a+1,a+2,\dots,b\}$. I am looking for a data structure to represent a map ...
-2
votes
1answer
48 views

best case for binary search tree creation [closed]

I want to know the best case time complexity of creating binary search tree and explanation.I know for insertion of a node in bst best case is O(1).