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

learn more… | top users | synonyms (1)

1
vote
1answer
20 views

Help in understanding the implimentation/application of scope trees

I’m learning (self-taught) about language implementation and compiler design, and I’m implementing a toy language to cement the concepts in my mind. However, I’m having trouble understanding how scope ...
0
votes
0answers
44 views

How do binary trees use memory to store its data?

So I know that arrays use a block on contiguous memory addresses to store data to memory, and lists (not linked lists) make use of static arrays and when data is appended to the list, if there is no ...
0
votes
0answers
15 views

Declarative and Procedural problem solutions [on hold]

Program solutions are structured and desigend based on the type of problem at hand. While looking up on when to apply OOD principles to a solution, I came across an article which states... ...
1
vote
1answer
51 views

How can a set offer better search performance than an array

While reading the following tutorial on iOS development Working with Foundation (section on Sets near the bottom), I came across the following statement: "Because sets don’t maintain order, they offer ...
3
votes
1answer
61 views

Data structure for ordered counted set

Is there a name for a counted set (multiset) that is ordered? For example lets say this data structure represents a shopping cart (or basket if you're British). The shopping cart shows the order the ...
0
votes
0answers
11 views

Simple Path to Route Algorithm [closed]

I'm currently conducting research into subway paths, but stand in front of a problem, with no programming knowledge and an extremely short time-limit. Probably the question I am asking is trivial, ...
1
vote
1answer
43 views

Traversals from the root in AVL trees and Red Black Trees

We all know that for insertion() operation in AVL tree following can happen: We traverse down the tree from root to appropriate node and there insert the key and then for maintaining height balance ...
0
votes
0answers
6 views

How to implement this test case in python? [migrated]

Q. Suppose that our banking system requires the ability to make joint accounts. Define a function make_joint that takes three arguments. A ...
0
votes
0answers
14 views

Problem occurring when changing hash table size

I'm practicing an exam for a data structures course. There's a question about a hash table with hash function: $$h'(k,i)=h_1(k)+i*h_2(k) \mod{11}$$ where $$h_1(k)=k \mod{13}$$ and $$h_2(k) = 1 + k ...
3
votes
1answer
67 views

Succinct bounded-sum array with $O(1)$ access

Assume we have a $n$ sized integer array $A$, and that we know that $\sum_{i\in[n]}A[i] \le M$. Assume we are using the RAM model with $\Theta(\log n)$ sized memory words (which can be read / written ...
4
votes
1answer
105 views

Why aren't tries generally used?

To store say integers (positive), we prefer to use red black BSTs. I have never seen a explicit use of a trie anywhere to store numbers. I believe we can convert numbers to string and store them in ...
3
votes
1answer
39 views

Algorithm for automatic/optimal database joins?

I'm curious if there is existing literature or well known algorithms out there for a problem I am working on. Given a normalized relational database with valid foreign key constraints and a list of ...
1
vote
2answers
95 views

Why can't hash tables provide O(n) sorting?

Since a sufficiently large hash table takes constant time to both insert and retrieve data, should it not be possible to sort an array by simply inserting each element into the hash table, and then ...
0
votes
1answer
59 views

Finding median weights in all paths of an AVL tree with weighted nodes

I need some help with proving the complexity of the following problem (I'm new here, so please excuse my "newbie-ness") Given: an AVL tree with keys: $1,2,..,n$, such that each node $i$ in the tree ...
0
votes
0answers
24 views

Augment B+ Tree to support given search query

Given a B+ tree with M=3. We assume that the tree is static and it is not necessary to update the B+ tree. Also we know that all key-value pairs are stored in the leaves of the B+ tree. Internal nodes ...
0
votes
1answer
22 views

d-ary heapsort analysis

I need to find a tight bound on the number of comparisons in a d-ary heapsort, in terms of d and n (the length of the array we ...
0
votes
1answer
40 views

Does XML covers the representation of any structured data and knowledge

I see nowadays XML is used to structure any file or data. It can represent the flat and hierarchical relations. It even can be used to show the parse tree of a sentence in a natural language. I am ...
1
vote
1answer
91 views

Algorithm: Cracking the Safe

A safe is protected by a four-digit $(0-9)$ combination. The safe only considers the last four digits entered when deciding whether an input matches the passcode. For instance, if I enter the stream ...
4
votes
2answers
157 views

Data structure for sparse matrices for an online problem

I need to compute a large linear optimization problem very often after recieving updates to my optimization problem. That is I have a linear problem to find an x such that $x_1 * c_1 + ... + x_n * ...
0
votes
0answers
23 views

Computing optimal assignments using little memory

I have two lists where each item in the first list has a rating for each item in the second. I need to determine an optimal matching (or the best x scenarios) where items are matched, but each item ...
5
votes
2answers
106 views

Is it possible to keep a “filtered” list up to date with changes in the source list in faster than O(n) time?

Description Say I have a source list like: ["a","b","c","d"] and want to run a capitalization filter so if I change, "b" to ...
0
votes
1answer
34 views

What is the advantage of seperate chaining over open addressing?

Hash tables resolve collisions through two mechanisms, separate chaining or open hashing and open addressing or closed hashing. Though the first method uses lists (or other fancier data structure) ...
5
votes
1answer
93 views

Is it possible to implement a dictionary with efficient access according to insertion order?

I am trying to build a generic data structure that needs to hold keys and values and in the same time keep track on the indices in which keys and values were put in, like arraylists do but in a ...
4
votes
1answer
51 views

How are graph representations containing only (i, j) instead of both (i, j) and (j, i) named?

When working with undirected graph algorithms using an adjacency-list type structure, it's sometimes enough to store a given edge (i, j) just stored in the list of ...
0
votes
1answer
40 views

A many-to-many mapping data structure

What would be a good way representing: i. Given a key, return all the data values associated with that key AND ii. Given a data value, return all the keys that are associated with that data. So far, ...
1
vote
1answer
28 views

Formula for returning the size of a circular array

I've come across a way of implementing a circular array that represents a double ended queue. Let the circular array have the following instance variables: ...
4
votes
2answers
98 views

Split in AVL tree with complexity $O(\log n)$

Can the split operation be implemented for AVL trees with complexity $O(\log n)$? I'm interested in links to articles or any specific information about this subject. The split operation divides the ...
3
votes
0answers
34 views

Finding the distance to the nearest neighbor for each point in a set of points in $R^n$

I have a list of points in $R^n$, and for each point I want to find the Euclidean distance to the nearest other point in the list. I don't need to know the coordinates of the nearest neighbor; I only ...
3
votes
1answer
31 views

Why in a min priority queue (heap based) it is called “decrease-key” and not just “set-key”?

When you call decrease-key in a min priority queue, you are basically setting the key, you can accidentally put a higher key, right? so why isn't it called "set-key" or "update-key"? why (according to ...
2
votes
0answers
34 views

Segment trees with insertion/deletion

I have a range query problem to solve. This problem requires not only range queries and update, but also insert or delete an element of the array. There is a series of operations that must be done in ...
-1
votes
1answer
28 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
33 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
1answer
133 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
20 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
36 views

Spatial data structures are part of Computational Geometry? [closed]

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 ...
3
votes
1answer
128 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 ...
2
votes
0answers
20 views

Why can't fractional cascading be used on two unrelated arrays?

According to both Wikipedia and my professor (see question 5.1), fractional cascading has to be done on arrays with related data. The specific question: A fellow student wants to compactly store ...
-2
votes
1answer
18 views

Computing vector load and stores [closed]

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
21 views

Skip lists with probability p [closed]

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
30 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
38 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
43 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
36 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
70 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 ...
16
votes
1answer
376 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
30 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
58 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
101 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
169 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
129 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 ...