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 ...
