Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

-1
votes
0answers
9 views

C String Input failure [on hold]

How to get array of strings until if the input is null.The number of strings is unknown.Please help me to fix this
1
vote
1answer
42 views

Is there any sort of formal definition of terms like 'data type', 'abstract data type', etc?

If not (because I assume not) is there some kind of reference or book that provides some theoretical foundation to these concepts? I've been learning about data structures and abstract data types for ...
0
votes
0answers
16 views

Left-Right-Rotation of AVL-Tree

For AVL-Tree there exists the following Rotations for Balancing: Left Rotation Right Rotation Left-Right Rotation Right-Left Rotation My Question is about the Naming for the Double-Rotations. ...
4
votes
2answers
75 views

Data structure for a tree of points moving in space

I'm trying to come up with a data structure for a following model: Nodes representing points in space are structured in a tree (general rooted tree with no restrictions). Let's call these nodes "...
2
votes
1answer
34 views

Does this “reference” problem have a name?

I have the following problem which I think is so common that I expect it to have an official name (and standard algorithm of course). The situation is as follows: I receive distinct items (A...E in ...
0
votes
0answers
4 views

What function will allow me to pull data from a column in a data frame based on the value in the columns in R? [migrated]

I'm trying to pull data out of a dataframe from a specific column based on the value in the column. For example: ...
0
votes
1answer
69 views

How to get all in constant time?

We are planning to design a system where following operations are supported. ...
0
votes
2answers
67 views

A data structure to do a specific lookup fast

I have 30,000 items; each item has 30 parameters that take values from 0 to 5. These parameters are named $p_0$ to $p_{29}$ and their value is an integer between 0 and 5. I want to store these items ...
-1
votes
1answer
37 views

Data structure with AVL and Hash table

Suggest a Data Structure for N elements that support on the following operations: Describe the Data Structure on a sketch and literally, describe how each method work. \begin{array}{|c|c|c|c|} \hline ...
0
votes
1answer
57 views

What is the most compact (space efficient) method of storing an array of distinct integers?

I have an array of distinct integers which I want to save in the most compact manner. I may have to do occasional lookups, deletions, and insertions in this array so the compression algorithm must ...
0
votes
1answer
20 views

Return course order with class prerequisites

Question: Given Input: Courses and their dependencies(prerequisites) such as A < B; A < C; B < D; C < D return course order in the order a student can take. i.e answer should return A, B, ...
0
votes
1answer
37 views

Is there a fast algorithm for computing the rolling mode of an array of integers?

I was wondering if there exists an efficient algorithm for calculating the "rolling mode of an array of integers. By rolling mode I mean that we have an array of integers of size $n$ and a sliding ...
0
votes
2answers
28 views

Datastructure for a set of axis aligned rectangles that enables querying for point containment

I am trying to find a reasonable data structure for representing a partition of an (axis aligned) rectangular domain into a set of (axis aligned) rectangles. I need to be able to look up for a given ...
0
votes
0answers
12 views

How to organize m-numbers into a [1..n] depth tree where the branching factor is variable and the nodes at the lower levels add up to their parents?

I need to organize a set of energy consumption numbers to determine the metering strategy (which would be tree-like) where the lower nodes add up to their parents(with some tolerance). How do I do ...
3
votes
2answers
57 views

Finding pairs of numbers in array whose reciprocals sum to 1

Given an array of numbers. Find all pairs of numbers satisfying the condition $1/a + 1/b < 1$. For example: Input: $2, 3, 1, 0.5, 3, 1.6$. Output: $(2,3), (3,2), (3,3), (3,1.6), (1.6,3)$. We can ...
1
vote
0answers
44 views

I have to write a JS program to solve a 4x5 grid puzzle . how to I write code to construct a tree with all possible moves? [closed]

Here is the link to the puzzle: http://www.cs.brandeis.edu/~storer/JimPuzzles/ZPAGES/zzzQuzzle.html My idea is to construct the tree of all possible moves and then use a search algorithm (probably ...
2
votes
0answers
32 views

Abstract Data Type

I have been studying data structures. In that I have come across topics like Array being defined as Power set of cross product of set of objects and set of natural number and list being defined as ...
1
vote
1answer
23 views

Abstract Data Types and their Implementation [closed]

I wanted to know if there is good resource to learn about the ADTs like set ADT, list, array, boolean etc and their implementation.
1
vote
2answers
95 views

What is the name of a rooted tree whose nodes may have edges to their descendants?

A tree is a special kind a graph. However, I came across a data structure which is a like a rooted tree, but where nodes are authorized to have direct links to any of their descendants. Shortcuts if ...
1
vote
0answers
23 views

Incremental strongly connected components

For a changing directed graph, I would like to maintain information about strongly connected components. The graph operations are incremental: only vertex addition and edge addition. What data ...
1
vote
1answer
36 views

Why time complexity of union-find is $O(lgN)$ with only “Union by Rank”?

I'm studying time complexity of Union-Find data structure. I saw time complexity of union and find function depends on some conditions. without anything: $O(N)$ with Union by Rank: $O(\log N)$ with ...
3
votes
2answers
43 views

sort n numbers in the range [0,1] without multiplying or dividing

Given an array with n real numbers, each in the range [0,1], I need to sort them. Moreover, the only operations that are allowed are comparisons or copying. It means I cannot multiply or divide the ...
1
vote
3answers
68 views

Is the capacity of a hash table a constant value?

In this paper, page 4, it is said: "...there is always a constant expected number of elements that map to the same slot" Assume we have a set $S$ of $n$ values, and we want to insert them into a ...
1
vote
0answers
34 views

How to find the maximum size of a B+ tree?

I came across this paper (page 16) which explains how to calculate the size of B+ trees. According to it the maximum number of nodes at level $i$ is $2(n/2)^{i-1}$ for a B+ tree of order $n$. Thus a ...
2
votes
1answer
65 views

Clarification reg. jump consistent hashing

I was reading the paper on Jump consistent hashing, and I'm having some trouble understanding one particular line (page 5, paragraph 2) "Since we want P(j ≥ i) = (b+1) / i, we set P(j ≥ i) iff r ≤ (b+...
2
votes
1answer
36 views

Selecting a subtree in an array representation of a binary tree

Consider a zero-indexed array representation of a binary tree (as in a binary heap), where 0 is the root The left child of i is ...
7
votes
3answers
207 views

Find common min in logarithmic time

I am looking for a data structure to store a set such that given two instances of size $O(n)$ which are known to have non-empty intersection, the minimum element of the intersection can be found in $O(...
0
votes
0answers
10 views

Dynamic deleting of edges in complete graph [duplicate]

Let's say we have complete graph, we want to build data structure that will allow us two things: Deleting edge from the graph. Telling if the nodes $u$ and $v$ are connected by at least one path in ...
1
vote
1answer
40 views

Candy Problem for k size window

I was solving this problem and end up learning two ways to solve this problem. One is two pass method and the other is considering peak and valleys (candies - interviewstreet). Both of these are O(n) ...
1
vote
1answer
27 views

Breadth First Search actually require specifically Queue instead of any other type of Collection?

As far as I know, Breadth-First-Search [BFS] theory traditionally requires a Queue to process a given level of a graph (i.e: wiki seems to assume so). But does BFS really actually require a Queue, ...
4
votes
2answers
217 views

Is there a name and efficient algorithm for this Tree Traversal method?

Consider a tree structured task list where intermediate nodes define sub-groupings of tasks but are not tasks themselves, and the leaves represent the actual tasks. I want to traverse this type of ...
5
votes
1answer
91 views

Most space-efficient lossy dictionary?

Short version: What is the most space-efficient lossy dictionary (with given false positive and false negative rates)? Long version: A lossy dictionary is a data structure $D$ that encodes a set $S$ ...
3
votes
2answers
129 views

Skip List estimate number of elements less than (or greater than) a value

I am looking for a thread safe data structure where an element can be searched in $O(\log n)$, for any value, $x$, the number of elements greater than (or less than) can be estimated in $O(\log n)$,...
1
vote
0answers
32 views

Terminology Questions: Data-structure consisting of lists without repetitions

I've google around and have been unsuccessful in finding a name for a data-structure consisting of a list whose elements are unique. I've seen "unique sorted lists", but I'm looking into the more ...
0
votes
0answers
22 views

L1 sampling for sampling edges of a graph

I am trying to sample the edges of an undirected graph using weights. The goal is to run a sparsification algorithm on the graph. I see the point that L1 norm is best for sparsification. Can someone ...
2
votes
1answer
47 views

String matching

I need to design a data structure to which I can efficiently add new words(Strings) and search for an existing word. Also, the search word can contain . in it which ...
1
vote
1answer
109 views

What is the level of the material contained in the book Data Structures and Algorithm Analysis in C++ (4th Ed) by Weiss?

The question is pretty much explained in the title. I have the necessary discrete math background and would like to learn algorithms and data structures in the process (of coding) - so the book quoted ...
2
votes
1answer
27 views

Heap structure in array, computing parent and child

I am studying data structures from Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, and in the section of heapsort it talks about a data structure beneath the algorithm : a heap, ...
0
votes
1answer
52 views

Storing Specific data on DB Table(s)

I have an Excel with 40columns and 20k rows, and i have to store it in a database but i cant figure the best approach for it, the excel format is like this: This table has 30 columns for days, then ...
1
vote
0answers
17 views

Example of binary trees with maximum rotation distance

In the 1988 paper Rotation Distance, Triangulations, and Hyperbolic Geometry, Sleator, Tarjan and Thurston show that for any pair of $n$-node binary trees, the maximum rotation distance between them ...
2
votes
1answer
49 views

Insert into binary tree and keep it balanced

Assuming each node stores its depth, how can I achieve this? Note that I'm not talking about a binary search tree so I shouldn't need rotations. All I want is filling the tree from left to right.
1
vote
2answers
25 views

Priority queue of constant size fit for extraction of K highest priority elements

In an algorithm I'm designing, I need to do this cycle on a priority queue of constant size N many times, as quickly as possible: get $K$ highest priority elements (do on them some outside ...
0
votes
1answer
50 views

Data structures that store efficiently detected features of an image

I struggle to find this, suppose I apply any feature detection algorithm. From my references it seems to me it's not usually explained what kind of data structures would be suitable for storing such ...
1
vote
0answers
16 views

Randomized meldable heap - meld is oversimplified?

On both Wikipedia and the paper it was introduced the randomized meldable heap uses the following procedure to meld two heaps: ...
2
votes
0answers
33 views

Analysis expected depth of a binary search tree given random values?

I have a guess about the problem above. Suppose I have a binary search tree $T$ initially empty. Suppose I drawn $x_1,\ldots,x_k$ (from some real interval $[a,b]$) keys and I want to insert the keys ...
2
votes
1answer
30 views

How to restore diagonal-symmetric matrix that has been shuffled?

I have a square matrix M, which originally looked like this: 133 199 101 121 142 133 199 101 156 142 133 199 108 156 142 133 (so symmetric around the diagonal). ...
0
votes
0answers
19 views

Generalized finger trees

While all explanations and implementations of finger trees I can find use 2-3 trees, in my understanding there is no impediment to generalize them to use B-trees instead. For 2-3 trees branch factor ...
4
votes
1answer
40 views

Can Depth-first search (DFS) with alphabetical traversal of neighbors be run in O(|V|+|E|) time?

I feel like the answer is no but I'm not sure. I think it's commonly accepted that DFS runs in $O(|V| + |E|)$ time. I've read a few explanations and they all make sense if the neighbour traversal for ...
1
vote
0answers
18 views

Merge unstructured with structured data

We have a database with well-formated and structured data. From time to time we get Excel - files from our clients. This Excel Files have to be imported to the database. It it very important that we ...
3
votes
1answer
73 views

What textbooks includes explanations of advanced data structures found commonly in competitive programming?

While looking through some problems on CodeForces, I noticed that there were several problems that required knowledge of techniques that just aren't covered in standard algorithm texts. Topics that ...