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

learn more… | top users | synonyms (1)

3
votes
1answer
35 views

Data structure for counting bits set on a table

I have a table that contains only bits. I would like to be able to do the following two queries: SET any bit to 0 or 1; GET the number of bits that are set to 1 from the beginning of the table up to ...
0
votes
1answer
68 views

Are dictionaries and associative arrays the same thing?

With respect to abstract datatypes (ADTs), are the terms "dictionary" and "associative array" perfect synonyms or are there slight differences between them?
2
votes
1answer
25 views

Top N percent elements in a Queue

I implemented a queue using two stacks which gives me O(1) enqueue time, O(1) amortised time. Now suppose i want to find top 10% elements in the Queue at any time. How am i suppose to implement it. ...
0
votes
1answer
16 views

Searching for an item over a non-uniform query distribution

If I have a static set of $n$ items in a database that are all queried with uniform probability it makes sense to put them in a binary search tree. This way any given search will take, on average, ...
1
vote
0answers
17 views

Algorithm for the function “drop” in a binary random-access list

In the book Purely Functional Data Structures by Okasaki, exercise 9.1 asks: Write a function drop of type ...
4
votes
2answers
75 views

Decremental reachability in a grid graph

Consider an $n$ by $n$ grid graph. For example, the following. You can of course reach the top left corner from the bottom right. Now consider the graph dynamically with an arbitrary number of ...
0
votes
0answers
87 views

Dynamic distance from source in a directed graph (only incremental or only decremental)

At the beginning we have a directed unweighted graph of $n \leq 10^3$ vertices, and $m \leq 10^5$ edges, with some vertex being a source, and we perform updates and queries on it. An update is adding ...
1
vote
1answer
109 views

RMQ with $O(\sqrt{n})$ space?

I'm asked to design an RMQ data structure (Range Minimum Query: return index of $min$ in a range $[i,j]$) for an array that has $<=\log(n)$ local minimums (a local minimum is an index $i$ such that ...
1
vote
1answer
54 views

Creating a binomial heap from an array in Θ(n) time

I'm studying binomial heaps. A book tells me that insertion of a node to a binomial heap take $\Theta(\log n)$ time. So given an array of $n$ elements it would take $\Theta(n \log n)$ time to convert ...
10
votes
1answer
108 views

Efficient algorithms for vertical visibility problem

During thinking on one problem, I realised that I need to create an efficient algorithm solving the following task: The problem: we are given a two-dimensional square box of side $n$ whose sides are ...
4
votes
1answer
76 views

How to avoid cascading resizes when resizing hash tables?

With conventional collision resolution methods like separate chaining and linear/quadratic probing, the probe sequence for a key can be arbitrarily long - it is simply kept short with high probability ...
-1
votes
1answer
55 views

Implementability of a (abstract) data structure/type? [closed]

Do people consider the implementability of a (abstract) data structure or a data type, just like people do for implementability/computability of an algorithm? By implementability, I mean if a ...
5
votes
2answers
188 views

What is the connection between data structures and data types?

I have read some books and wikipedia, which seem to give not completely consistent definitions and notations. I try to understand the concepts, regardless of what they are called. Here are what I have ...
3
votes
1answer
169 views

What do queues and stacks correspond to in math?

Many (and I suspect all) abstract data types in CS correspond to some math concepts, and even share the same names, for example, set, map, record/tuple, .... As abstract data types, what do queues ...
0
votes
0answers
78 views

Does this algorithm on a circular linked list ever terminate?

Suppose we have a circular linked list that has nodes $1$ to $n$. L is a pointer that points to node 1 (with label $1$). Note ...
4
votes
4answers
91 views

Interleaving algorithm for 2 stacks

Suppose I have two stacks $<a_1,a_2,...a_m>$ and $<b_1, b_2,...b_n>$ and a third stack of size $m+n$. I want to have the third stack in the following manner, ...
0
votes
0answers
37 views

Implementing BTrees without pointers

I am trying to implement a BTree in a pointer-free language as a proof-of-concept. However, a question came to my mind: every time I need to split a node, I need to do a deep copy of all the nodes in ...
2
votes
2answers
98 views

Quickly locating nearest rectangle from a point

The problem is as follows: There are several rectangles in the plane (they are not necessarily axis-aligned), how can we index them in such a way that given a point $p$ we can quickly locate the ...
4
votes
2answers
96 views

Using singly linked list instead of a doubly linked list?

Are there advantages of implementing a singly instead of a doubly linked list other than space?
0
votes
1answer
27 views

Hashing and number of comparisons [duplicate]

Say, I want to put N objects into a hash table. How do I figure out how big the size of the table needs to be to have K comparisons on average when the table is: half full? three quarters full? all ...
0
votes
1answer
49 views

Depth of any node x in Weighted Quick-Union Algorithm

I know from Sedgewick's book on algorithms that the max depth of any node x from a set of N nodes is at most log2(N) applying the algorithm(which says to put the shorter tree beneath to avoid tall ...
0
votes
1answer
46 views

what's the meaning of LOC(X[j]) = $L_0$ + cj in TAOCP's 5.4.1R?

in TAOCP vol3 2nd Edtion's 5.4.1R Replacement Selection, there is a paragraph describing a data structure and example for Replacement Selection as follows: the algorithm below uses a data structure ...
6
votes
0answers
92 views

Approximate nearest neighbour in practice

I have $10^3$ vectors each of dimension $10^4$. Each dimension takes an integer from a limited range. I would like to build a data structure that will answer approximate nearest neighbour queries ...
4
votes
4answers
276 views

A “triangular” data structure for commutative relationships

A multiplication table is symmetric over a diagonal, so only about $n^2/2$ of the elements in an $n \times n$ multiplication table contain unique information. Same goes for addition tables. In fact, ...
-1
votes
1answer
62 views

Learning, understanding and using algorithms [closed]

I am a 2nd year computer science student. We all have subjects about Data Structures, Theories, more more theories we all know that i have a subject this semester Design Analysis of Algorithms. So ...
1
vote
1answer
101 views

Term for binary search tree using hashes?

I was looking for a way to easily store and access a symbol table using the least memory and code as possible and I went with a BST. Symbols, however, tend to be defined in order as in foo0, foo1, ...
1
vote
1answer
44 views

Finding Hash of Substring [i, j] in O(1) using O(|S|) pre computation

Given a string S of length n characters, is it possible to calculate the Hash of its substring [i, j] (From index i to index j. Inclusive) in O(1) using some form of precomputation ? Maybe a ...
1
vote
2answers
125 views

Finding shortest path from a node to any node of a particular type [closed]

I have an un-directed, un-weighted graph G.Starting from a given node A, i want to find whether there is a path from A to a node of a certain type .There can be many nodes of that type. The problem is ...
0
votes
2answers
106 views

B-Tree and how it is used in practice

I understand what a B-Tree is (I already implemented a B-Tree in Java with insert and delete methods that preserve the invariant). However I do not understand exactly how it is used for example for ...
1
vote
2answers
65 views

Don't understand one step for AVL tree height log n proof

I came across a proof that the an AVL tree has O(log n) height and there's one step which I do not understand. Let $N_h$ represent minimum number of nodes that can form an AVL tree of height h. Since ...
5
votes
4answers
575 views

What's the difference between a binary search tree and a binary heap?

These two seem very similar and have almost an identical structure. What's the difference? What are the runtime complexities of each?
1
vote
1answer
39 views

Combined linked/array-like data structures for a set of non-intersecting sub-intervals of integer interval?

This question is related to my previous question: Looking for a set implementation with small memory footprint I'm looking for information about combined data structures, which can efficiently ...
1
vote
1answer
41 views

Partial Range Query on Inverted File with Combined Index

I am currently reading Multidimensional and Metric Data Structures by Hanan Samet for fun. The combined index is discussed on page 5-6. I do understand it in the sense that the inverted file itself is ...
-1
votes
2answers
55 views

Is there only one optimal BST?

as i read some material about Optimal BST, i ran into a trouble. for following key i find two optimal BST with Average Cost = 30. 1 optimal BST using Dynamic programming Algorithm and 1 by hand ! ...
0
votes
2answers
51 views

Is there a term for a tree where the values of the children add up to a fixed value?

I have a tree with percentages of the following form ...
-2
votes
1answer
45 views

Min-Heap Insertion Problem

I try to insert 4-9-3-7 and 1 (left to right) into a Min-Heap (using array implementation). Then 5 times Remove Smallest Number from this Min-Heap. how many swap between two elements in array ...
1
vote
2answers
58 views

choice of data structure for domino tilings

A domino tiling is a tesselation of a region in the plane by 2 × 1 squares. What is a good data type for storing and manipulating such objects? In my current manipulation, use an array to ...
0
votes
1answer
38 views

How to design xml schema for digital circuits? [closed]

how can i design XML Schema for logical and digital circuits? i cant find any help or manual for this work for example i have a digital circuits with AND OR NOR ,... gates now i want design xml ...
0
votes
3answers
135 views

High Dimensional Data Structures

I have a 20-dimensional dataset, with a large amount of data points. I would like to have each dimension discretized into bins. Per bin, I would like to be able to access two neighbours per dimension ...
0
votes
0answers
23 views

Amortized analysis of nested loop

I have a fairly simple algorithm, consisting of an inner while-loop in an outer for-loop. Even though the algorithm is simple enough, it's quite hard to explain exactly what it does. However, it's ...
0
votes
1answer
26 views

Join large list of pairs

I have a list of millions of pairs of strings, and I want to join all of the pairs that have matching members into lists without duplicates. Example input: ...
3
votes
2answers
90 views

Are there any CS-trees named after flora-trees?

This is meant to be a fun question, and I hope it's not too off topic. Is there a defined mathematical object or data structure that has a name collision with a type of physical tree in the real ...
-3
votes
1answer
66 views

Building a Red Black tree out of a sorted array [closed]

If I have a sorted array of size $n$, can I build a Red Black tree out of it in $O(n)$ time in a different algorithm rather than splitting the tree in half every time or the straightforward way that ...
0
votes
1answer
42 views

Find longest path between two disjoint sub-sets of vertices $V_1, V_2 \subset V$ of a Graph

I have a homework question which I would appreciate some help with: Let there be a DAG $G=(V,E)$ with positive weights. For every two different vertices $v_1, v_2$ we will define $D(v_1, v_2)$ to ...
2
votes
0answers
45 views

Binary heap of size $n$ splitting to 2 heaps of size $n/2$ [closed]

Input: A binary heap of size $n$. $n$ is even. Output: 2 binary heaps of size $n/2$ each. I found this question in a solved algorithms test and the solution said: "There is no better solution than to ...
1
vote
1answer
35 views

Order of steps in Kosaraju-Sharir

The Wikipedia summary of the Kosaraju-Sharir algorithm is as follows: Let G be a directed graph and S be an empty stack. While S does not contain all vertices. Choose an arbitrary ...
-1
votes
1answer
29 views

Efficient search with removal

I want to search from a given set of elements. Along with that I also want to remove that searched element. The problem is that the number of these queries is $q=O(n)$, where $n$ is the number of ...
2
votes
1answer
38 views

Binomial heap multiplying nodes

Input: A max binomial heap $H$, and a pointer to a node $V$. Output: A max binomial heap, where all the children of $V$ are multiplied by 2. I have tried solving this by taking out the node $V$ ...
2
votes
1answer
51 views

Lower-bounding the Membership Problem in the Bitprobe Model

I am working through the following paper "Data Structures for Storing Small Sets in the Bitprobe Model" by Radhakrishnan et al. and am confused regarding one of their arguments about a lower bound. ...
1
vote
2answers
87 views

directed graph data structure with fast in/out neighbor query

If I store a directed graph $G$ in adjacency list format, one can find all the out-neighbors $j$ of a given vertex $i$ in $\mathcal O(d)$ time, where $d$ is the max degree of the graph. These are all ...