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

learn more… | top users | synonyms (1)

2
votes
1answer
9 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
0answers
23 views

Deleting and querying the kth element

Given an array A containing N elements. I want to know what is best suitable data structure to handle these 2 queries : Delete Kth element from the array. Report current Kth element of the array. ...
-1
votes
0answers
17 views

Which book contain these topics from data structure [on hold]

I cannot find these topics in the books I own or have searched on google. Please guide me through this : Data structures for maintaining ranges, intervals and disjoint sets with applications. Basic ...
-1
votes
1answer
24 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 ...
1
vote
1answer
41 views

Random Binary search tree

What is the difference between a randomly built binary search tree (using n keys )and choosing a binary search tree (of n key) from a random distribution
2
votes
1answer
64 views

How can you iterate through a hash table in constant time?

I am studying data structures and the book "How to Think About Algorithms" by Jeff Edmonds (pages 46-47) claim that: "Hopefully, all the elements that are in your set happen to be placed into ...
1
vote
1answer
40 views

Data structure for range-value-sum

I have to be able to perform insert, delete, range-value-sum, and range-2-max-values with a data structure. Range-value-sum(xl,xr): with a range [xl,xr] (for a range query), it reports the sum of ...
2
votes
2answers
59 views

Count points in 2-d range

You are given an array $A$ of size N $(N\leq 1\,000\,000)$ containing all integers $1..N$ exactly once. You are required to answer query in $O(\log^2 N )$ and to preprocess in $O(N\log^2N)$: How ...
0
votes
0answers
26 views

Partial Sum operation & solution - Optimizing to O(logn)

I approached this problem where I have to write an add(key, value), insert(key, value), delete(key,value) and partial_sum(value) which reports the sum of all the elements in the structure that are ...
-1
votes
0answers
76 views

Count distinct and same substrings in a range

Given a string T with n lowercase letters T[1..n]. For each substrings T[l..r], we can assign them two values, k1 and k2, which are defined as following. K1 is the number of different ...
0
votes
2answers
35 views

Elements in a less than a value in a subarray

Let A be an fixed array of size n. Q(i,j,k) is number of elements from A[i] to A[j] which are less than k. Currently I am using segment tree with each node containing sorted array of leaf elements. ...
0
votes
1answer
34 views

Union grouping in bipartite graphs?

I'm trying to figure out a good (and fast) solution to the following problem: I have two roles I'm working with, let's call them players and teams having many-to-many relationship (a player can be on ...
-1
votes
0answers
13 views

AVL Tree Augment [duplicate]

Minimum_(K): Return element of k with smallest key. If I were to describe, how do i augment the AVL tree so that it supports this minimum_(k) operation in constant (1) time?
-2
votes
0answers
15 views

Number of nodes in a B-Tree

How many nodes does a resulting B-Tree(min degree 2) have if I insert numbers from 1 to n in order? I tried inserting nodes from 1 to 20 there was a series for the number of nodes coming but i could ...
2
votes
2answers
107 views

Data structure to insert, update and sort indexes by frequency and query an index for a particular cumulative frequency

Here is the description of the data structure I am looking for: Initial Original Data Index | Frequency | 1 3 2 1 3 7 4 2 5 6 Now it should be ...
0
votes
1answer
105 views

Do data structures help to reduce complexity of operations, at the cost of something else? [closed]

I often heard that using data structures help to reduce (time or space) complexity of some operations. I wonder if that is achieved at the cost of something else? When solving a problem, is ...
-3
votes
2answers
113 views

Is Horowitz and Sahni's data structure book outdated? [closed]

I found that Fundamentals of data structures (1982) by Ellis Horowitz and Sartaj Sahni draws my attention naturally, probably because of their formal treatment of data structures, and their choice ...
0
votes
0answers
65 views

Proof by induction for a splay tree?

I'm preparing for an exam about Trees. One of the questions that appear in Mark Allen Weiss' "Data Structures and Algorithms Analysis in C++" is: Prove by induction that if all nodes in a splay ...
0
votes
1answer
19 views

Use of -1 to express edge cases in computer programs and data structures [closed]

Often I will encounter the use of - or even use myself - the value -1 as an edge case in otherwise integer data structures. For instance, as the value for ...
-1
votes
2answers
84 views

Are “data structures” part of algorithms or of programming languages?

I often heard that "program = algorithm + data structure". But I notice that It seems to me that a data structure is (or may be) just a data type or extension thereof. Is it correct? But a data ...
0
votes
2answers
31 views

Recursion: base case vs. small version

I'm reviewing the definition of recursion and in my notes are two questions about a recursive problem. One question asks about the base case, the other one about the small version of the problem, I ...
1
vote
1answer
31 views

Smallest(k) in red-black tree. How is it O(logn)?

Is it the same as find minimum for a binary search tree? I know recoloring runs in O(logn) and rotations are O(1). Even if we are wanting it to find the 'k-th' smallest key in the red-black tree. ...
1
vote
1answer
82 views

How can one search in O(log n) time in a red-black tree?

How does the search operation for a red-black tree work and how does it take $O(\log n)$ time, where $n$ is the number of items? I know a red-black tree takes $O(\log n)$ recolorings and $O(1)$ ...
-2
votes
1answer
51 views

Algorithm for checking if all subarrays have an unique element

How to check if all subarrays of the array contain at least one unique element for NlogN complexity, where N is the length of the array? For example: ...
4
votes
0answers
42 views

Concurrent priority queue with lazy increase-key

I could use a priority queue supporting the find-and-delete-min, and lazy-increase-key operations. The last term is my ...
4
votes
3answers
571 views

When are binary trees better than hashtables in real world applications?

I am currently bushing up on my data structures and basic algorithms, part of that is the Binary Tree. I do understand the algorithms, and how to implement a binary search tree and such. I do so how ...
2
votes
2answers
44 views

Efficient representation of a given surjective function $\{1 \ldots N\} \rightarrow \{1 \ldots M\}$ when $N \gg M$

More precisely: The input is set of $M$ sets (most likely stored sequentially on disk) that contain partitions of the set $\{1..N\}$. I want to efficiently (as far as memory and time complexity goes) ...
3
votes
2answers
192 views

How many structurally different trees can be formed with n nodes?

Is there any exact formula for finding number of structurally different unlabeled trees can be formed with $n$ nodes? I searched a lot and I found some approximation formulas, e.g. here.
1
vote
1answer
34 views

Proving correctness of an AVL-Tree colouring algorithm

I came up with the following recursive algorithm to colour the nodes of an AVL tree so that the resulting tree is red-black. The logic is that the algorithm first colours the root and, recursively, ...
3
votes
0answers
26 views

Term for index-like data structures

There's a class of data structures where you preprocess some other data structure in order to answer queries about it more efficiently. That includes trivial things like sorting/hashing, less trivial ...
3
votes
1answer
51 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
76 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
61 views

Top N percent elements in a queue

I implemented a queue using two stacks which gives me $O(1)$ en-queue 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 ...
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
19 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
3answers
88 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
92 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
119 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
74 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
122 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 ...
5
votes
2answers
99 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
57 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
204 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
176 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
84 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
102 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
39 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
103 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
101 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
28 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 ...