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

learn more… | top users | synonyms (1)

0
votes
0answers
11 views

How to ensure that no manipulation to data records has been made

Let's say I have a transaction history, like this: Transaction #1: Add 5 Transaction #2: Add 8 Transaction #3: Remove 2 Transaction #4: Cancel Transaction #2 Is ...
0
votes
1answer
30 views

Why does Skiena reserve space for n+1 adjacency lists?

I am reading up on graph theory from the book Algorithm Design Manual - Skiena. And he shows a structure of a graph as follows : ...
1
vote
1answer
33 views

improving java 8's implement to hash map using avl tree

Java 8 got a new implement to hashmap (using a tree). I have understand that in the worst case, it may be O(n) for lookup. Will changing this implement to an avl tree change this O(n) case to ...
1
vote
0answers
21 views

What is the psuedo-code for Tremaux's Algorithm as a Depth First Search to solve a maze?

I was interested in the Tremaux Algorithm as a Depth First Search to solve a Maze. Unfortunately I was not able to understand what Data Structures are and how they could be used. For example, I saw a ...
1
vote
0answers
15 views

Resources to learn about distributed data structures? (DHT, Merkle Tree, etc.)

I'm having a hard time finding comprehensive literature on distributed / p2p data structures... for example, I have found the book "Handbook of Peer-to-Peer Networking", which seems to be what I want ...
3
votes
0answers
28 views

Are there any practical drop-in replacements for BSTs in the case where data are integers?

There are a number of specialized data structures that implement ordered dictionaries for integer keys: van Emde Boas trees, y-Fast tries, fusion trees, etc. Each of these data structures implement ...
0
votes
0answers
36 views

Succinct Data-Structures

What is a possible data structure $X$ which stores non-negative integers $x_1, x_2, ..., x_n$ which supports the following operations: $index(k, X)$ returns the biggest $i$ so that $\sum_{i=1}^n x_i ...
3
votes
0answers
30 views

Data Structure for k Nearest Neighbour Search in D dimension using only point cloud as query points

I have a point cloud of N points in D-dimensional space with periodic boundary conditions, where N can range from 500 to 10^8 and D can range from 1 to 20. The distribution of points varies wildly, ...
1
vote
1answer
46 views

Why isnt node checked for nil value in start when transplanting binary tree

Whilst I was reading CLRS I came across this: When TRANSPLANT replaces the subtree rooted at node u with the subtree rooted at node v, node u’s parent becomes node v’s parent, and u’s parent ends ...
1
vote
1answer
44 views

What exactly (and precisely) is “offset”?

Just like my previous question concerning 'hash'; what exactly is an (or the) "offset?" Is it a value or data type? Or is it an address location? I have heard it used in different contexts within the ...
2
votes
1answer
38 views

How to construct a running kd-tree?

I have a stream of 3-tuples of type (x,y,t) where x and y are in the range ...
0
votes
1answer
22 views

Looking for a use case of a $k$-$d$ tree with a norm other than $L^2$

In Python's implementation of $k$-$d$ tree it is possible to manually change the norm used for computing distances from $L^2$ to $L^p$. When would one use a norm other than $L^2$ in a $k$-$d$ tree?
1
vote
0answers
27 views

Trying to understand a way to split an AVL tree in O(log n)

I'm trying to understand a presentation about AVL trees. It says that the way to split AVL trees in node x is as follows: You search for the node x and mark every left son of every node when you turn ...
0
votes
0answers
20 views

On an AVL tree insertion/deletion, which nodes have their height changed and why?

I've begun learning about AVL trees. It seems that the assertion with this data structure is that with every insertion/deletion, the only nodes whose height changes are nodes on the path towards the ...
3
votes
1answer
218 views

What is the difference between a R-tree and a BVH?

I've just read about R-Trees: The key idea of the data structure is to group nearby objects and represent them with their minimum bounding rectangle in the next higher level of the tree; the "R" ...
0
votes
0answers
20 views

RMQ with single index update in array

Range Minimum Query (RMQ) can be solved in (O(n), O(1)) if the array is known to be static by dividing it into blocks and then using Cartesian tree numbers to detect "similar" blocks. Link: ...
10
votes
7answers
2k views

How to find middle element of linked list in one pass?

One of the most popular question from data structures and algorithm, mostly asked on telephonic interview.
1
vote
0answers
17 views

Bounded pairwise distance on moving points

Suppose you're writing a video game that takes place on a large rectangle (2d). You have a large list of entities (monsters, spells, and so forth, represented as points) living on this rectangle, and ...
-3
votes
1answer
32 views

Virtual address lookup without using all the space to store the physical addresses [closed]

How is a virtual address mapped to a physical address? The most logical solution I, with my meager knowledge, can think of would be to actually store the physical address. The problem with the above ...
3
votes
1answer
75 views

Prove/disprove the existance of a data structure that has O(log N) inserts/deletes and get k-th largest element in O(1)

Consider a sorted array. We can get the $k$-th largest element in $O(1)$, but insertions and deletions cost $O(n)$. Consider an order statistic tree. Insertions and deletions cost $O(\log{N})$, but ...
0
votes
0answers
37 views

minimum and maximum number of internal nodes for given number of leaves in 2-3 tree

I came across following question: Suppose a 2-3 tree has 19 leaves. What are the largest and smallest numbers of interior nodes the tree may have? Identify the correct value for minimum or ...
0
votes
0answers
15 views

Reverse linked list set logic in method B

I am trying to describe a reverse linked list in the B method. The structure I am trying to describe is below: F <- 1 <- 2 <- ... <- x <- L where ...
0
votes
0answers
42 views

Find keys between $x$ and $y$ in binary search tree

Given $x$ and $y$, I want to find keys $k$ such that $x<k<y$, in a binary search tree. Can this be done in time $O(n + h)$, where $n$ is the number of keys between $x$ and $y$, and $h$ is the ...
3
votes
0answers
22 views

How to realize a distributed queue with unreliable participants?

I want to build an application that relies on a distributed queue with participants in a decentralized (peer-to-peer) network. The participants cannot be relied on to correctly follow a protocol. I ...
0
votes
0answers
34 views

joining of binary trees

Suppose we have a set of binary trees with their inorder and preorder traversals given, and where no tree is a subtree of another tree in the given set. Now another binary tree $Q$ is given. Find ...
-1
votes
3answers
89 views

Terminology for trees

In a tree, I want to refer to a particular child of a node, the child of this child, the child of this child of this child, and then the child of this child of this child of this child. For instance, ...
3
votes
2answers
200 views

Is it admited to give the complexity of a function regarding the resulting data structure?

Assume that we have a data structure which uses $O(\log n)$ space to store an integer $n$ and has a function $f$ which replaces the integer $n$ stored by $2^n$, i.e. $n=2^n$. The time complexity of ...
3
votes
0answers
54 views

Tree of Despair: Collecting Data from a Tree with Multiple Types of Branching

Provided is a tree with three types of node. The structure of the tree cannot be modified and traversal of the tree is limited to querying a node for its children or its parent. The objective of the ...
1
vote
0answers
13 views

How to encode each possible b-tree of a sequence of n numbers?

Lehmer codes can be used to encode each possible permutation of a sequence of n numbers. Often the main goal is just to map a range of numbers from 1 to x to the possible permutations of a sequence of ...
4
votes
1answer
37 views

What to infer about maximum height of AVL tree from these three different formulae

I have came across following problem: What is the maximum height of any AVL-tree with 7 nodes? The recurrence giving number of nodes $n$ in the AVL tree for given height $h$ is as follows: ...
2
votes
2answers
79 views

Why do we need double-rotations to rebalance AVL trees?

I was reading about AVL tree rebalancing from Behrouz Forouzan's book. The book first defines Left High and Right High tree: Left High (LH) tree is a tree tree with the height of the left ...
6
votes
1answer
68 views

Data structure for efficient searching, when insertions and removals are only one-sided

I need a data structure for storing a number $n$ of elements, each of whom is associated with some different time $t_i$. $n$ varies and while it has a theoretical upper limit, this is many orders of ...
1
vote
0answers
46 views

Can partial sums of a counter array be computed in O(log n) time?

Let $A[1 . . . n]$ be a given array of $n$ integers, where $n = 2^m$. The following two operations are the only ones to be applied to A: Add(i, y): Increment the value of $A[i]$ by $y$. ...
3
votes
2answers
85 views

Ideal value of d in a d-ary heap for Dijkstra's algorithm

I stumbled upon the following statement: By using a $ d $-ary heap with $ d = m/n $, the total times for these two types of operations may be balanced against each other, leading to a total time ...
2
votes
1answer
113 views

Does my simple, static hash table have O(1) worst case lookup?

Will the following simple hash table construction algorithm be able to construct a static hash table in $O(n)$ expected time, and will the worst case access time be $O(1)$? If not, what are the ...
-2
votes
1answer
36 views

Best search in Heap Array

Can someone give me the best search algorithm in a max heap? In particular simply implemented as an array. I knew it has complexity of $O(N)$ but it can be done better. For example, if $A[i] < ...
-1
votes
2answers
90 views

An algorithm to check if all intervals are disjoint

There are $n$ intervals on the real line , the intervals are given with start- and end point. The $i$-th interval is $(d_i,f_i)$ where $d_i$ is the start point and $f_i$ is the end ...
0
votes
0answers
21 views

Fundamental representation of data relationships?

This is an offshoot of this question Which is more fundamental: key-value or subject-predicate-object? Is there any fundamental, hypothetical or practical, representation of data relationships? Both ...
1
vote
2answers
57 views

Which is more fundamental: key-value or subject-predicate-object?

There seems to be two approaches to store data in NoSQL databases: Key-Value - The Key is usually stored in a hash-table referencing a ...
3
votes
1answer
37 views

Keeping a binary search tree by splitting nodes (like a B-Tree)

A B-tree is kept balanced (i.e. all leaves at same depth) by splitting a node when adding a child that won't fit, and propagating this splitting up to the root. Can the same technique be used to keep ...
0
votes
0answers
28 views

Hashtable vs cache-oblivious

This question has been asked in the theoretical community, but deemed as too practical. I am moving it here, I hope it is on-topic. I'd like to know more about real performances of data structures, ...
1
vote
0answers
23 views

What data structure is best suited for nested values and count of values?

I have incoming stream of data which has following values. Country, City, State Along with maximum number of unique values to store (e.g. 50,22,12). I need to design a system which will keep count of ...
4
votes
2answers
120 views

What data structure might this game use?

This question is not about game development or about actual implementation details. I was playing Little Alchemy yesterday. (Warning: Productivity hazard.) You start with the four classical ...
6
votes
2answers
46 views

A key-value datastructure with fast (on average) member move and nearest neighbors search?

I have a 3 dimensional float key search space (say a simulation world). I want to keep my values (ints, agent ids) in a data structure that can perform nearest neighbors search (with search for N ...
4
votes
1answer
64 views

Heap comparison based sorting question

I need some help with this question from my problem set. I do not want a solution but some $\textbf{hints}$ on how to proceed. Given $n$ records in a file that are so numerous, that just storing ...
5
votes
2answers
66 views

Is it possible to build a heap from the root to the leafs?

Most books on data-structures will briefly introduce heaps (aka priority queues) and then move to describe the "trick" allowing heaps to be implemented as arrays. I've been looking for a way to ...
2
votes
1answer
51 views

A heap based problem

I have been struggling with this question from my problem set. I do not want a solution but some hints on how to proceed. You are given a file of numbers which represent the values of associated ...
3
votes
2answers
70 views

Achieving better than the theoretical False Positive Rate for Bloom Filters

I implemented a standard Bloom Filter in C++, and tested it on different sizes, with varying values of the ratio ${c = n/m}$ where ${n}$ is the size of the filter, and ${m}$ is the number of elements ...
0
votes
0answers
51 views

Reverse linked listed — formal method?

I am trying to do some formal modeling of a linked list, however instead of referencing the next block, each block needs to reference the previous block instead. Is there already any formal methods ...
3
votes
1answer
63 views

How to come up the number of nodes on a given level in heaps?

CLRS asked it's readers to prove that there are at most $\lceil n/2^{h+1} \rceil$ nodes of height $h$ in any n-element heap as an exercise. The principle of Mathematical Induction can be used to prove ...