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

learn more… | top users | synonyms (1)

-1
votes
0answers
23 views

Usage of (advance) data structures? [on hold]

We all are pretty much aware about Big Table is one of the data structure used by Google. There must be some other data structures used by industry leaders like Google, Microsoft, and Facebook. Can ...
0
votes
1answer
64 views

Proving that an $n$-element heap has at most $\lceil \frac{n}{2^{h+1}-1} \rceil$ nodes

I am having trouble proving that an n-element heap can have at most $\lceil \frac{n}{2^{h+1}-1} \rceil$ nodes. Please note that I am proving a loose bound. First I proved that a complete binary tree ...
4
votes
1answer
106 views

Where can I find information on Data Structures used in common software?

As part of a course I am teaching on Data Structures, I want students to research and present the use of Data Structures in popular software/services. However, basic googling shows me that this ...
0
votes
1answer
55 views

Which in-memory data structure can accommodate billions of md5 value?

For my application, I have to store billions of md5 values, and before storing new md5 I wanna make sure that it doesn't exist already in it. I tried using hash data structure, it worked well but no ...
0
votes
1answer
17 views

What is a limitation of using an array concerning capacity? [on hold]

Is it that you need a separate method to expand the array whenever it goes over the capacity?
3
votes
2answers
102 views

Algorithm for finding a mouse hole in a wall in O(n) time

There is this question: As a result of the US Election, a wall is built along the entire Canadian border. You have been told there is a mouse hole in the wall, but it can only be seen when you ...
0
votes
0answers
23 views

why are integers considered as an ADT?

According to the definition of ADT on wikipedia , it is given that ADT is a mathematical model for data types , And as per wikipedia, definition of mathematical model says that it is composed of ...
3
votes
0answers
43 views

Describe data structure using equations

Good afternoon. At work I'm currently developing a system which takes user input (well structured) and then stores it in memory to do some processing. The input is basically a dataset formed by ...
0
votes
1answer
32 views

Reb-black tree amortized cost of the rebalancing

I've read in different sources that the amortized cost of a red-black tree rebalancing is constant (at least during the tree creation using only insertions). How can it be proved?
-1
votes
1answer
37 views

Complexity and Recurrence relation for Lowest Common Ancestor Binary Tree

I have written this solution for finding the Lowest Common Ancestor in a Binary Tree. Now I wanted to find the time complexity of this problem by solving via recurrence relation. Can someone suggest ...
1
vote
1answer
121 views

Efficiently locating the maximum value in interval over large amounts of data points

I have a set of $n$ two-dimensional data points $(x_i,y_i)$. I want to efficiently answer the following query: Given an arbitrary interval of $x$-values, find the highest and lowest points within ...
3
votes
1answer
40 views

Delete a consecutive range of leaves from a binary tree

Suppose I have a binary tree containing $n$ leaves and whose depth is $d$, where the data is in the leaves (the internal nodes don't hold data values). I want to delete a consecutive interval of ...
5
votes
1answer
64 views

Finding a small element in a changing array

Consider having an integer array $A$ with $n$ elements, in addition to any data structure you like. The array is initialized to zeros. The goal to to support two operations: ...
-2
votes
0answers
35 views

Insertion a value into a list at a certain position in constant time

My problem is that I have an ordered list of pairs (1,x_1), (2,x_2)... (n,x_n). I have to be able to add (k,y) s.t. k is less than n and I want it to stand in the k-th position in the list. However, I ...
1
vote
1answer
34 views

Trying to understand max heapify

I tried watching http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-4-heaps-and-heap-sort/ to understand heaps and ...
5
votes
2answers
51 views

How does DFS produce MST and All pairs shortest paths in unweighted graphs?

I was reading Application of DFS from here where I came to a statement which I cannot really understand. Would anybody mind explaining this to me. For an unweighted graph, DFS traversal of the ...
0
votes
1answer
30 views

Indexing billion domain names / strings

I am trying to find any datastructure/algorithm suitable to index & retrieve domain names & its associated documents. The records that need indexing will typically be like: ...
0
votes
1answer
44 views

Ways to implement a decision making process involving complex rules [closed]

I'm investigating different solutions for solving what looks like a decision making problem. Although the domain I'm working on is different, for the problem at hand, it's quite easy explaining with ...
3
votes
1answer
34 views

Best data structure for storing an ordered list, where each item is located on a separate server?

I need a structure that resembles an RSS feed of items, but each item is on a different network machine. Users cannot insert in the middle of the feed but only at its head. Deletions are possible. ...
1
vote
2answers
235 views

Why don't nodes carry as many pointers as possible in a skip list?

From this main picture explaining how skip lists work from Wikipedia, we see that some nodes carry different amounts of pointers to other parts of the list: Wouldn't it make more sense to have ...
4
votes
2answers
1k views

What would we call this datastructure?

Suppose we have a datastructure that is a list containing elements that are either a leaf or another layer of the datastructure (recursively defined). What would we call this? It isn't a tree, since ...
-1
votes
1answer
38 views

Random quadtrees

I have $N$ uniformly distributed 2D points and I want to find out how many points lie in some small rectangular region. However, the number of points can be arbitrarily large (e.g., $N=10^8$), so I ...
4
votes
3answers
74 views

Data structure to store sphere points (latitude,longitude) and retrieve all points within a distance

I have a set of thousands~millions of points on a sphere's surface, each with latitude, longitude. I want to quickly get all points within a distance d of a ...
0
votes
1answer
33 views

Data structure for set of intervals - query for all intervals contains given point

We're given a set of $n$ intervals $[a_i, b_i]$, $i=1...n$. I am looking for a data structure which makes it possible to query for all intervals that contain the point $x$. My proposition is using ...
-1
votes
1answer
55 views

Every AVL tree may be red black tree

I proved by induction that every AVL tree may be colored such that it will be red black tree. The problem is that I can't see an error in my proof. Look at my proof. Induction for height. Let's ...
5
votes
6answers
836 views

Hash table collisions: why use a linked list if we can use a hash set?

One way to deal with the problem of collisions for a hash table is to have a linked list for each bucket. But then the lookup time is no longer constant. Why not use a hash set instead of a linked ...
2
votes
0answers
70 views

Respresting data when I have to move back and forth

I am having data where I would be given customers and there priorities. The priority would be food type and there flavours. In total there are N food type and 2 flavour (spicy and non spicy) so in ...
1
vote
3answers
88 views

Usefulness of a linked list with a cycle

Is a singly-linked list that contains a cycle considered a corrupted data structure or is there some practical use for it? (You could argue that a car without its front shield is not corrupted, if ...
0
votes
2answers
64 views

Is queue a storage allocation area in memory?

We mainly study about heap and stack data structures which act as storage allocation area in memory. Is it that queue is also a storage allocation area in memory? As far as I know, process control ...
0
votes
0answers
21 views

Joining k 2-3 trees

I was given the following question, and would like your help with it: Let $T_1, T_2, T_3, ..., T_k$ be a collection of k 2-3 trees. The height of tree $T_i$ is marked $h_i$. Assumptions: 1) every key ...
4
votes
1answer
36 views

Variations of Depth First Travesal

While learning depth first traversal, I realise there are two approaches that are followed. Method 1. The first one is as given in the Forouzan's book is as follows: Push the initial node onto the ...
10
votes
5answers
1k views

What is the earliest use of “trees” in computer science?

I have a little history question, namely, as the title says, I am looking for early uses of trees (as a data structure, search tree, whatever) in computer science.
1
vote
2answers
96 views

AVL tree such that each insert causes rotation (single or double)

Could you give me an example of an AVL tree for which inserting an element at an arbitrary (i.e. every) position causes a rotation (double or single)? I have tried to come up with an example, but I ...
2
votes
2answers
90 views

What is the trick used in skip lists to minimize $k + \frac{n}{k}$?

I was reviewing skip lists and the first step is to have two lists, the bottom one ($L_0$) of length n and the top one ($L_1$) of size k. Usually one traverses the "express line" (i.e. the top lane ...
1
vote
0answers
25 views

Data structure to store a large power-law graph with constantly updated structure

I am looking for data structures to store power-law (hence mostly sparse, but few dense too) graphs whose structure is continuously being modified, including new vertices being added and edge weights ...
1
vote
1answer
35 views

Finding a (minimal?) program that maps $M$ items to indices $[0,M)$

Let's say there are $M$ strings that we are trying to create a perfect hash for such that we get as output of the hash $[0,M)$ with no collisions, when hashing those $M$ items. I know that there are ...
0
votes
1answer
33 views

Two red children in a red-black tree

My data structures exam contains the following question: Which of the statements below about red-black trees is true? (select one or more) Every path from the root to a leaf has the same ...
0
votes
1answer
24 views

Identify balanced and full binary search tree insert order

I'm inserting numbers 1 thru 15 into a binary search tree one by one. I need to come up with an order to insert these elements for it to result in a full and balanced binary tree. I've tried to create ...
0
votes
0answers
56 views

How to implement auxiliary procedures for LCS algorithm by Hunt/Szymanski

I have read a paper [1] which explains an algorithm for finding the longest common subsequences. I have problem with coding of creating matchlist of Algorithm 2 on ...
1
vote
2answers
69 views

Effective finding height of avl tree

I am searching effective way to find out height of AVL tree. In each node there is balance factor ($bf$). $$bf(root)=height(root.left) - height(root.right). $$ And now we can find height in $O(\log ...
0
votes
1answer
37 views

How the deletion takes place in B+ Tree

My professor was giving a lecture on B+ Trees deletion, and I got very confused. According to him for deleting any key from a B+ Tree: ...
1
vote
2answers
64 views

Hash table versus binary search lookup for unchanging data

Let's say I have some static, unchanging data (no adds, modifies or deletes) which is looked up by a string value, and that I'm looking to minimize size in memory while also trying to minimize lookup ...
3
votes
1answer
49 views

Why is the path compression (no rank) for disjoint sets $O(logn)$ amortized for Find-Set?

I was trying to understand why using only path compression (no rank) would yield $m log(n) $ total run time for a sequence of $m$ operations for Find-Set. I was told that the potential function: $$ ...
0
votes
1answer
51 views

Successor of 6 is 7 or 9? [closed]

What is the successor of 6 in this tree: 7 or 9?
0
votes
0answers
45 views

kd-tree for triangular range queries

Any Ideas for a linear size data structure that can answer triangular range queries, but only for triangles whose edges are either horizontal, vertical, or have slope +1 or −1. It's queries should ...
2
votes
1answer
44 views

Efficient haircuts

I have a real vector $v$. From this vector, I want to extract a sequence of integers, $ix$. The first integer is found by, $ix_0=argmax(v)$. 1 is then subtracted from $v_{ix_0}$, and the process is ...
1
vote
1answer
18 views

Finding a lower bound for the amount of comparisons for sorting $k$ subarrays with $\frac n k$ elements

Let the input be an array of $n$ elements, with $k$ sets $S_1,...,S_k$ such that each set has $\frac n k$ elements. The elements in each $S_i$ are larger than the elements in $S_{i-1}$. ...
0
votes
0answers
20 views

Apriori vs Associative Mining

From what I know the Apriori mining algorithm falls under the category of associative mining, meaning it extracts information using rules based on relationships in the data. When I do research on both ...
0
votes
2answers
106 views

non-binary self balancing tree

I'm looking for a tree data structure that allows to keep the tree balanced in high (minimum high as possible). I mean, suppose a tree where: each node has a parameter k that is the maximum number ...
1
vote
0answers
18 views

What is an easy-to-implement linear or non-quadratic suffix array construction algorithm?

The algorithm described here in "Linear Work Suffix Array Construction" (2006) has compact C++ code that is too abstract for me to follow. Is that still the current easy-to-implement linear algorithm? ...