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

learn more… | top users | synonyms (1)

0
votes
1answer
76 views

How can I learn about CS? [on hold]

I am an Junior in college and I have come to the realization that my school didn't to that good of a job of actually teaching real CS to the students. On my own, I have become a fairly proficient ...
-1
votes
1answer
38 views

Operation with same asymptotic cost on hash tables and lists

Let $x \in \{ \log n, n, \dots , n!\}$ some (cost) function. Are there interesting operations with runtime in $O(x)$ on lists which also have runtime in $O(x)$ on hash tables?
1
vote
0answers
17 views

Proof of Randomized Self-Adjusting Binary Search Tree

I developed a randomized self-adjusting binary search tree years ago, which I called a shuffle tree, but was unable to ever have it published because my proofs were rejected (with little explanation). ...
1
vote
0answers
23 views

Where To Put Duplicates in Max Heap?

Question: Suppose you have a list of integers and it might contain duplicates. Build a Max Heap using this list. Where would the duplicates of the max integer reside in this Max Heap data ...
1
vote
1answer
35 views

Given a Red-Black Tree of n keys, is there a way to quickly determine if a red-node exists?

My best attempt at a specific case of the problem where $n =$ 256: For a specific case that a RB tree has 256 nodes, we can use the RB tree theorem to deduce that the height of the tree $h \leq ...
3
votes
3answers
47 views

When inserting into a binary tree, is there a universal agreed upon place to insert then new node to minimize complexity?

Do programmers (in real life), always insert at the top node or somewhere else? Because in my text book CLRS it is not made very clear, so the insertion process can take a best case of O(1), if you ...
1
vote
1answer
20 views

What will trigger a worst time search for a binary heap and what is the run time?

I thought if the values in a max or min heap is monotonically increasing or decreasing, then this will trigger a worst case run time of O(n) because you will have to go through each and every single ...
3
votes
1answer
33 views

How can I calculate tree sizes to “stretch up” a finger tree?

I've been working on implementing an efficient Cartesian product operation (actually the <*> operation, but it amounts to about the same thing) for sequences ...
1
vote
1answer
74 views

LazyHeap data structure with $O(n)$ Insert, Delete, and Return operations

Consider a data structure called LazyHeap that supports the following operations: INSERT(x): Given an element $x$, insert it into the data structure. It has no cost. DELETE(x): Delete $x$ from the ...
0
votes
1answer
30 views

Rotations in splay trees

I am having some difficulties splaying the element 4 to the root. Considering the following splay tree. 0 \ 1 \ 2 \ 3 \ 4 ...
0
votes
1answer
26 views

How does these Probing time occurs for hash tables

I am having a hard time understanding the numbers of probing which might occur due to using different collision prevention method such as separate chaining, Linear Probing, double probing, which is ...
1
vote
1answer
29 views

How to find a 2-wise independent hash family that is not 3-wise independent?

I'm trying to find a family of hash functions mapping $\{1, 2, ..., 2^n\}$ to $\{0, 1\}$ that is 2-wise independent but not 3-wise independent. Any ideas on that? I know two 2-wise independent ...
-1
votes
0answers
32 views

Advantages and disadvantages of B-Trees [closed]

What are some disadvantages and advantages of btrees? I found couple but I just need a better clarification. (dont tell me that operations are logarithmic and b-tree always stays balanced). I need a ...
1
vote
0answers
37 views

Tradoff between space and false positive rate when using bloom filters

Bloom Filters have false positive rate of $\epsilon = 2^{-k}$ with a data structure of size $m = n\log (\frac{1}{\epsilon})\ln 2$. Suppose you fix the number of hash functions at $k \le 3$. What is ...
1
vote
1answer
27 views

Supporting queries for finding how many intervals in a dynamic set of 1D intervals contain a given point

You want to create a data structure that can store 1 dimensional intervals and also support the query for finding the total amount of intervals intersecting a given point. One solution would be for ...
-1
votes
0answers
31 views

Dynamically weighted priority queue? [closed]

Elements are stored in a single dynamic data-structure $D$ Element ranks are computed by: $\forall i \in n\quad f(i,\ x_i+1) : x_i \in \mathbb{Z^+}$ The function $f$ is weighting based on the value ...
1
vote
1answer
43 views

Amortized analysis of virtual, dynamic array using potential function

You often want to implement an array $A$ where the length fluctuates over time. If at some point $A$ has length $n$, then you would like to use space $O(n)$. Consider the following: At all moments, a ...
2
votes
1answer
47 views

$T(n) = \sqrt{n}\,T(\sqrt{n}) + n\log n$ [duplicate]

I tried to solve the recurrence $T(n) = \sqrt{n}\,T(\sqrt{n}) + n\log n$ with the master theorem but I can't get it to work. How many arrays exist in each step in the recursion tree? Or can I solve ...
3
votes
1answer
45 views

Counting nodes in a trie

I'm studying random tries in one of my classes, and was wondering if anyone could offer any guidance regarding a problem. Question: Given a random $m$-ary trie with $n$ total leaves, letting $I$ be ...
1
vote
1answer
43 views

Prove that this family of hash function is $3$-wise independent, but not $4$-wise independent

Consider the hash function mapping $w$-bit keys to hash values in $\{0,...,m-1\}$. Suppose $w=cr$. Interpret a $w$-bit key $x$ as a vector $(x_1,...,x_c)$ of $c$ $r$-bit keys. Consider the ...
2
votes
1answer
39 views

Use AVL trees instead of Chord algorithm for Distributed Peer to peer Hash tables

In distributed systems we use the Chord algorithm to create a p2p distributed hash table. While this algorithm is very useful and efficient wouldn't it be better if we used an AVL tree? Chord ...
2
votes
1answer
82 views

Show that the following family of hash functions is $2$-wise independent but not $3$-wise independent

I've really been thinking about and working on this problem for a while, and I would appreciate if someone could offer any help towards the solution. Consider the following family of hash ...
3
votes
1answer
100 views

Probability of probing $t$ locations in a Cuckoo hash is $O(\frac{1}{2^{t/2}})$ locations in the worst case

I was told this question may be better received here. Prove that the probability that an insertion into a cuckoo hash table probes $t$ array locations is $O(\frac{1}{2^{t/2}})$. Keep in mind ...
-1
votes
0answers
9 views

number of possible binary trees based on preorder traversal [on hold]

Can we know the number of possible binary trees based on preorder traversal for n nodes? thanks
7
votes
2answers
274 views

What is the most efficient algorithm and data structure for maintaining connected component information on a dynamic graph?

Say I have an undirected finite sparse graph, and need to be able to run the following queries efficiently: $IsConnected(N_1, N_2)$ - returns $T$ if there is a path between $N_1$ and $N_2$, ...
1
vote
0answers
40 views

Running time analysis of a segment tree

Can someone provide an analysis of the update and query operations of a segment tree? I thought of a way which goes like this - At every node, we make at most two recursive calls on the left and ...
1
vote
0answers
8 views

The most efficient way of finding/storing neighbourhood info during octree creation

Currently I have a program which at some point creates an octree and AFTER the creation loops through all the nodes, for every node (O(n2/2)) and thus finds the neighbours, by a brute-force box-box ...
3
votes
0answers
97 views

Range bit inversions and range set bit queries with a binary indexed tree

I am trying to solve this problem using a binary indexed tree. The problem can be summarized as follows: You are given a series of commands that operate on an array initially all zeroes. ...
1
vote
1answer
24 views

Implement opposite() method to tell if there are two opposite numbers, (x,-x)

Let a dictionary with the operations insert(), delete() and search(). Each one of them ...
2
votes
0answers
64 views

I need a better data structure than a graph with condition nodes

Suppose i have a cyclic weighted ($\mathbb{Z}$) directed graph where nodes are either simple or complex. a simple node is just a usual node whilst a complex node is a node that contains a set of ...
0
votes
1answer
48 views

Is there a name for the 'scope tree' organization?

I could describe JQuery as a library that allows you to easily select elements on and traverse the DOM, the DOM would be the name of the tree or organizational structure of the HTML. When you are ...
1
vote
0answers
12 views

Terminology for a partially unlinked doubly linked list?

Let's say you have a standard doubly link list implementation: struct List { int Number; struct List *blink; struct List *flink; }; and that you have ...
0
votes
1answer
24 views

Asymptotic runtime for querying an interval tree

Suppose that we have an array of size n and we want to build an interval tree for all possible ranges that can be created inside this array. So in our leafs we have ...
1
vote
1answer
49 views

Selection problem on the union of two ordered dictionaries

Suppose we are given two ordered dictionaries S and T each with n items, and that S and T are implemented by means of array-based ordered sequences. Describe an O(log n) time algorithm for finding ...
0
votes
0answers
27 views

How many array access in keys[j] = keys[j-1]; vals[j] = vals[j-1];?

Are there two or four array accesses in the line keys[j] = keys[j-1]; vals[j] = vals[j-1]; I think it should be four. The reason I'm asking this is in ...
3
votes
1answer
75 views

Range update + range query with binary indexed trees

I am trying to understand how binary indexed trees (fenwick trees) can be modified to handle both range queries and range updates. I found the following sources: ...
3
votes
0answers
25 views

Fast and space efficient data structure for nearest neighbors in 3 dimensions?

I am looking for data structures to answer nearest neighbor queries in 3D which are reasonably space efficient (ie use at most $O(n^{1+\epsilon})$ space) and fast ($O(n^{\epsilon})$ or $O(log^k(n))$ ...
3
votes
1answer
49 views

Where does the terminology of open addressing resp. closed hashing come from?

One of the basic methods of hashing is called "Open addressing, or closed hashing" according to wikipadia (and several books). Why the names "open" and "closed", and why these seemingly contradictory ...
2
votes
2answers
52 views

Balancing a Binary Search Tree

I was reading about binary search trees on it's Wikipedia article. I was a little confused by this image. Why is it that the right branch to the head node does not have a sub-tree? I understand why it ...
3
votes
1answer
240 views

Binary Indexed Trees: Why does i & -i work?

I already read this related question on the intuition behind binary indexed trees, and while the answer explains how the tree structure works, it does not really explain how this correlates back to ...
-1
votes
1answer
33 views

Bubblesort generalization [closed]

I was comparing and analyzing the sort algorithms thereby came across a machine which took 200 secs to sort 200 names but to generalize, in 800 secs wouldn't it sort 800 names?
0
votes
1answer
35 views

Which permutations can not be obtained by moving elements through two stacks?

I have a Stack1 which has the entries a,b,c ( with a on the Top) and Stack2 which is empty.The condition is. An entry pooped out of the stack1 can be printed immediatly or pushed to stack2. An ...
0
votes
0answers
8 views

Bulk-loading R-tree with data with extent

When bulk-loading R-tree with points one can simply sort the elements by some coordinate and split to equal-sized chunks. But if the elements have some extent, sorting them by their coordinate value ...
2
votes
1answer
103 views

compressing a set of binary strings with fixed length

I'm looking for a data structure / algorithm to store an unordered set S of binary strings of a fixed length n (i.e. all ...
1
vote
1answer
32 views

Wouldn't a Red-Black tree fix up after insertion mess up the BST ordering?

I've been reading about fixing up after an insertion into a red black tree. (http://web.cse.ohio-state.edu/~lai/2331/0.Red-Black%20Trees.pdf) The most surprising part is not that there are 6 things ...
0
votes
0answers
28 views

Are if statements avoidable is we define a program according to explicit state transitions? [duplicate]

This question occurred to me some time ago when I was thinking about whether or not if statements are fundamental in computation. Consider a program that manages a ...
5
votes
1answer
104 views

Why do we need “Bloom Filters” if we can use hash tables?

A Bloom filter is a probabilistic data structure designed to tell, rapidly and memory-efficiently, whether an element is in the set or no. If we can use hash tables where we have O(1) in best time, ...
1
vote
1answer
40 views

Find k maximum numbers from a heap of size n in O(klog(k)) time

I have a binary heap with $n$ elements. I want to get the $k$ largest elements in this heap, in $O(k \log k)$ time. How do I do it? (Calling deletemax $k$ times yields a $O(k \log n)$ complexity. ...
3
votes
1answer
55 views

Split-Find: maintaining dynamic graph connectivity information, under edge deletion

Is there a data structure to keep track of the connected components of a dynamic graph, when the graph might by changing by deleting edges of the graph? Let $G$ be an undirected graph. I have two ...
-1
votes
1answer
40 views

Min/max height of B-tree

I have a question asking for the minimum and maximum height $h$ of a B-Tree with 1000 elements under following conditions: each block can save 1 to 4 records, the number of internal nodes is ...