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

learn more… | top users | synonyms (1)

-1
votes
1answer
16 views

Fit stack of stone of varying length into a well of varying length

I have a stack of m stones of different Diameter. stack = [5,4,9,20,1] And a Well that is of depth n with varying diameter at different depths . ...
3
votes
1answer
31 views

Red-black tree. Adding a red child to a red node with a black sibling

According to my lecture notes, adding a red child to a red node with a black sibling in a red-black tree, is equivalent to changing a 3-node into a 4-node in a 2-3-4 tree. I've built several red-black ...
0
votes
0answers
11 views

Persist and sync custom sorting information [closed]

Assume a task app like asana with multiple client apps and the data must be synced across multiple systems. I have a list of 'tasks' and they can be custom sorted. What is the optimum way for me to ...
0
votes
1answer
79 views

What are the main ideas used in a Fenwick tree? [duplicate]

While I was solving a programming competition question, I came across a technique advertised as suitable for the solution. A so called Fenwick tree (a.k.a binary indexed tree) was at the heart of this ...
3
votes
1answer
19 views

n-polygon lattice datastructure?

I'm trying to simulate a boardgame what can be played on a board with an arbitrary lattice, anything from triangles to heptagons to 37-sided regular polygons is allowed. Moreover the shape of the ...
0
votes
1answer
33 views

Spatial data structures are part of Computational Geometry? [on hold]

Are spatial data structures like BVH - Bounding Volume Hierarchy ,kD-Trees etc are part of Computational Geometry( http://graphics.stanford.edu/courses/cs268-14-fall/) or of Data structures and ...
2
votes
1answer
111 views

How to improve my these specific math skills? [closed]

I am student of CS. Problem is, I feel that I don't have enough math knowledge to solve mathematical problems. When some programming problems arises which needs some math skills to solve then despite ...
-1
votes
0answers
16 views

Serialization graph - confusion

I don't know how to produce a serialization graph from the following information. As where I've highlighted every possible Read/Write, Write/Read and Write/Write. They are dealing with different ...
-1
votes
1answer
14 views

Computing vector load and stores

If $a,b,c,y$ are all scalar doubles, then $y = a\cdot b$ would result in 16 bytes from loading $a,b$ and 8 bytes for storing $y$, a total of 24 bytes transferred. Likewise, $y = a\cdot b + c$ results ...
0
votes
0answers
16 views

Skip lists with probability p [on hold]

Let's say we have a skip list that in which probability $p$ is the chance that an element will get promoted. What boundary for height can we get with probability $1-1/n$? What about expected search? ...
0
votes
0answers
26 views

What is the complexity of this recursive merge of two ordered Python lists?

This is not an assignment, but it is related to my Data Structures class. I just wrote this Python code to merge two ordered python lists. I do know that I could do something like this: list1 + ...
1
vote
1answer
32 views

Are there any theorems/formulas that apply to the height of comparison trees?

I have been drawing some binary comparison trees, which correspond to compares made to sort an array, and I was wondering if there is any formula to determine the height of a comparison tree for an ...
2
votes
1answer
40 views

Searching for multiple partial phrases so that one original phrase can not match multiple search phrases

Given a predefined set of phrases, I'd like to perform a search based on user's query. For example, consider the following set of phrases: ...
1
vote
1answer
35 views

Double ended queue data abstraction and axioms

I am trying to show the data abstraction for a double ended queue along with the axioms. A double ended queue is a queue where items can be added to and remove from either end of the queue. I have ...
1
vote
1answer
62 views

Heap-like data structure allowing peek at largest & smallest

For the purpose of implementing an optimization algorithm (finding the minimum of a multivariate function) I want to create a data structure that supports the following operations: load from array ...
14
votes
1answer
246 views

Why are Red-Black trees so popular?

It seems that everywhere I look, data structures are being implemented using red-black trees (std::set in C++, SortedDictionary ...
2
votes
1answer
29 views

Represent an octree as a binary tree of thrice the depth?

In an octree, each node has up to eight child nodes. This can be implemented with eight pointers per node that are set to null pointers if the child is not used. Another implementation uses a byte as ...
1
vote
1answer
47 views

The most appropriate way to implement a heap is with an array rather than a linked list, why is this?

The most appropriate way to implement a heap is with an array rather than a linked list, why is this? I don't completely comprehend why this is? is it because it is easier to traverse?
3
votes
1answer
72 views

A median of an AVL. How to take advantage of the AVL?

Here is the source of my question. Given a self-balancing tree (AVL), code a method that returns the median. (Median: the numerical value separating the higher half of a data sample from ...
6
votes
1answer
155 views

Optimize binary search on Segment Tree by storing past result

Goal Let $A[n]$ be an arbitrary array of integers of length $n$. Let $S$ be a segment tree, represented by an array of records: each record containing the left and right bounds ($[l,r]$) of the ...
4
votes
1answer
119 views

Gray Code Generation

I am trying to generate a $n$-bit gray code where I can specify two strings $s$ and $t$ that must be consecutive in that gray code. I know that there are ways to generate specific codes (such has the ...
0
votes
1answer
37 views

Suffix Tree algorithm complexity [closed]

I really get confused by all the different complexities you find around. One is $O(n \log n)$, the next $O(n \cdot |\Sigma|)$. Personally I think it's the last one, but I'm really not that confident ...
2
votes
1answer
42 views

Guessing the structure of a finger tree from the number of elements

I'm writing a data structure library, and I want to write an efficient algorithm for adding many elements to a finger tree (from an iterable sequence). I'm going to do this by constructing a finger ...
0
votes
0answers
24 views

Immutable data structures for 2d+ lattices

I would like to find an immutable/persistent data structure that allows efficient updating for 2d (or higher) lattices/arrays/matrices, and reasonable performance when appending in any direction. ...
4
votes
1answer
113 views

Tallest Person Average Memory Updating?

We ran into a problem that was mentioned in an interview 2 days ago. Can you help us with any idea or hint? A sequence of $n$ people, $\langle\,p_1,p_2,\dotsc p_n\,\rangle$ enter a room. We want to ...
1
vote
0answers
42 views

Potential method analysis for Insert and Extract-max on a Max heap data structure

Suppose that you do some sequence of operations on a max heap, in this case only Insert and Extract-max. Whenever the heap ...
1
vote
2answers
40 views

Why the pointer in linked list is of structure type? [closed]

Since any node points to a memory location is there any specific need in using it's pointer as structure type.Why couldn't we use integer as the pointer type in linked list rather than structure?
1
vote
0answers
30 views

Applications of Linked Lists [closed]

I tried looking in the internet but couldn't get any applications of linked list used in day-to-do life.Could anyone list any applications of linked list?
0
votes
1answer
41 views

Searching through a heap complexity

Pretend you want to search through a max-heap to find a specific element. I know there is no such option but still... Would it take worse case O(n) or O(logn) time? I am assuming O(n) since the ...
1
vote
1answer
49 views

Can nodes in red-black trees have one nil child and one non-nil child?

I don't recall hearing that nodes in red-black trees can't have one nil child and one non-nil child. However, I did hear that red-black trees have a worst-case height of $2log_2(n + 1)$, where n is ...
3
votes
0answers
50 views

How to apply path compression to Multi-Bit Trie

Reading a bit about the subject of Multi-Bit tries and IP matching in: High Performance Switches and Routers H. Jonathan Chao, Bin Liu. Page 33 Network Routing: Algorithms, Protocols, and ...
4
votes
1answer
71 views

Why isn't the time complexity of constructing a Fenwick tree tighter than $O(n\lg n)$?

Intuition: Suppose I have an array of nonzero integer values $A[n]$ and a partially constructed Fenwick tree of this array: $F[k], n>k$. I can see why inserting the next element would be worst ...
1
vote
1answer
55 views

What is “Oracle Access”?

I'm reading a paper for school and I have come across a passage that I don't understand. It says "If we allow the query to access the entries of the array through an oracle, it is possible to obtain a ...
2
votes
3answers
40 views

Existence of functions that only tests memberships without revealing any information about the members

Given a set of strings $\{s_1, s_2, \cdots, s_n\}$, is there a way to encode them to a program $P$, such that given some string,$s$, the program can test the membership efficiently (deterministically ...
-4
votes
2answers
58 views

Rearranging linear tree with right rotates [closed]

I ran into a fun interview question, yesterday. Can anyone help me? Suppose a binary tree with six nodes is given, such that each node has only a left child. With how many "right rotate" ...
1
vote
0answers
26 views

Longest increasing subsequence using 2-3 tree

While preparing for my data structures final I came across this problem: A - a given array of integers of length n. Propose data structure which supports the following operations: Init(A) - ...
1
vote
0answers
32 views

Median-of-medians for sorting finger trees incrementally

Haskell's Data.Sequence uses Hinze-Paterson 2-3 finger trees to represent finite sequences. The types are defined below for concreteness. Currently, the library ...
1
vote
1answer
17 views

What are the tradeoffs between implenting dataframes as a series of columns vs a series of tuples

I was reading the documentation for Julia's Dataframe package, and the package implements Dataframe by a series of a columns each of a single type. From reading the docs, it looks like that's how R ...
3
votes
0answers
38 views

Efficient deletion in Fenwick tree

Suppose there is an array of nonzero integer values A[n], which has a Fenwick tree representation F[n]. The most simplistic way ...
1
vote
0answers
34 views

Efficient data structure for set to union of sets mapping

What I have is the following: A mapping $f : key \rightarrow set$ that works in constant time An inefficient mapping $g : \{key\} \rightarrow \cup_{k \in \{key\}} f(k)$ where this union is slow Is ...
-2
votes
1answer
76 views

Find K-th next element in O(log n) time

We want to store a set S of distinct positive integers and support the following operations on S: Insert(a): insert integer a !∈ S into S. Delete(a): delete integer a ∈ S from S. ...
0
votes
1answer
56 views

The number of Binary Search Tree that exist with same Postorder and Inorder

how many BST exist with same postorder and inorder traversal? I know that in binary tree (Not BST), it is one. but i have a book from that said for BST it is CATALAN number. i become confused.
0
votes
0answers
66 views

What data structure would help find nearby coordinates quickly?

I need to write a program that does the following: Take an input list of objects whose properties include latitude and longitude to, say, 5 decimal places Store them in a data structure once Provide ...
3
votes
1answer
110 views

Data structure for a static set of sets

I have collection $U$ of sets, where each set is of size at most 95 (corresponding to each printable ASCII character). For example, $\{h,r,l,a\}$ is one set, and $U = \{\{h,r,l,a\}, \{l,e,d\}, ...
2
votes
2answers
95 views

Can one insert non-unique elements into an AVL tree?

Is it possible to insert a sequence of non-unique elements into an AVL tree? For example, what is the AVL tree result of inserting 3, 3, and 3 into an initially empty AVL tree? Is it: ...
0
votes
2answers
153 views

Is there a way to find path length to a node from root in a binary tree?

I went through the algorithm’s for finding the LCA of two nodes in a binary tree (let’s say the values are random – not a binary search tree) and I chose the method where the path to root is stored in ...
0
votes
1answer
41 views

undirected graph without weights and DFS [closed]

following question on undirected graph without weights can be solved by using DFS and in O(|V|+|E|) times. check that G is ...
0
votes
1answer
21 views

What is the name of this size method calculating the size of a node?

My confusion is that if the recursive call calls the left nodes, and then adds with the right nodes, how are the nodes that are to to right of the left nodes and vice versa being called? ...
-1
votes
1answer
81 views

Sorting tuples with respect to multiple criteria

Given $n$ rows with $k$ columns, is there a storage mechanism/data-structure and/or algorithm that enables dynamic restructuring such that I can get the top $t=\mathcal{O}(1)$ results efficiently? ...
3
votes
3answers
718 views

How are hash table's values stored physically in memory?

Question: How are hash table's values stored in memory such that space if efficiently used and values don't have to be relocated often? My current understanding (could be wrong): Let's say I have 3 ...