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

learn more… | top users | synonyms (1)

1
vote
1answer
39 views

What is the complexity of Array[n] and Object.value

I faced a great doubt about the Complexity of two ways of calling a information. First I have an Array, if I call an array in a program like this: print array[0] ...
-4
votes
0answers
28 views

The c++ code says file cannot be opened. Can anyone tell me whats wrong in my code? [on hold]

Question: Write a program that reads students’ names followed by their test scores. The program should output each students’ name followed by the test scores and relevant grade. It should also find ...
0
votes
0answers
13 views

What's the intuition behind the update operation of the binary index tree? [duplicate]

There are many tutorials on binary index tree on the Internet, for the update operation, they all find the the next node of node i to update by ...
0
votes
0answers
52 views

Understanding Chazelle's bin packing algorithm

I'm having trouble understanding Chazelle's algorithm ,which is discussed in this paper The bottom-left bin-packing heuristic: an efficient implementation by B. Chazelle (1983), especially in ...
0
votes
0answers
11 views

what is the Time complexity of matrix multiplication? and how can it be determined? [closed]

I tried to obtain it from a program. It gave me a graph whose equation is in exponential form.
1
vote
1answer
35 views

What do you call a “non-probabilistic Bloom Filter”?

One of my coworkers came up with a nice technique to solve a problem and I feel like it must already have a name. I just don't don't know how to figure out what it is. It is a technique for caching ...
6
votes
0answers
74 views

When used as call stack, do garbage-free spaghetti stacks form a DAG?

I'm looking into implementation techniques for programming languages, and recently came across spaghetti stacks, which are supposedly a good fit for a continuation passing style model (given their use ...
5
votes
1answer
39 views

Is FKS hashing really linear space?

In FKS hashing, I wonder if the size of the table $G[ 1..n]$ (used to record the functions $g_i$ which is chosen randomly; one entry per bucket) is really strictly $O(n)$. Given that the probability ...
13
votes
0answers
115 views

Why hasn't functional programming researched dynamic trees?

By dynamic trees I am referring the definition stated in Sleator & Tarjan's paper "A data structure for dynamic trees" in 1983. Since then, few efforts have been done in the functional programming ...
1
vote
1answer
34 views

Shifting deletion algorithm for linear-probing hash table

I'm looking for the algorithm for deleting an element from a linear-probing hash table that does a delete-and-shift instead of just using tombstone elements. The basic idea is quite simple - but I ...
-4
votes
1answer
33 views

Constructing binary search tree from given data

The data are in alphabets. U, N, I, V, E, R, S, I, T, Y, O, F, P, O, K, H, A, R, A. Perform pre, in and post order traversals. I'm confused as how to construct it in the 1st place. Only sense i ...
3
votes
1answer
64 views

Why do you need to fill the first element of array when implementing heap?

I'm looking at Heap data structure implementation from different sources. What I found is that sometimes it's implemented with the first element of array set to magic (default, unused?) value. For ...
1
vote
1answer
44 views

Are there data structures that mix a tree structure with lists?

I suppose something like this could probably be easily designed, however I was wondering if there's a data structure that somehow uses both list and tree to access data. Something like this (I'll be ...
1
vote
0answers
235 views

Large non-array data structure to describe order of elements

I'm looking to store the order of a series of elements and access the elements in "pages" (elements numbered 101-150, for example) as well as add and delete them. This is being implemented in a graph ...
1
vote
1answer
54 views

Amortised analysis of binary heap insert and delete-min

I'm trying to figure out how to do amortised analysis of heap insert and heap delete-min using potential function. We can assume, that insert is O(logn) and delete-min is O(logn) too. The goal is ...
0
votes
2answers
69 views

Correct way to implement linked list

I'm doing this challenge on Hacker Rank that wants me to implement a linked list. It seems to want me to find the last-added instance of node and change its head to link to my new instance of node. ...
1
vote
3answers
70 views

Zero-based array implementation with logarithmic insertion time

Normal zero-based arrays (ie not those with a sort order) have constant lookup time, but linear insertion time. For a specific problem I was musing about a balanced tree that would allow for an zero-...
2
votes
2answers
271 views

Is this probability distribution data structure already discovered?

Problem formulation I have implemented an interesting probability distribution data structure: having $n$ elements $a_1, a_2, \dots, a_n$ in the data structure with respective positive weights $w_1, ...
1
vote
1answer
72 views

Is there a way to determine if a collection is a palindrome within a time bound?

I'm learning about data structures, and there's a problem where, given a collection of words $X = (x_1, x_2, \dots, x_n)$ (can include duplicates), I have to find out if it's a palindrome or not. I'm ...
-3
votes
1answer
51 views

What is the amortized time complexity of inserting an element to this heap?

Assume you implement a heap using an array and each time the array is full, you copy it to an array double its size. What is the amortized time complexity (for the worst case) of inserting elements ...
2
votes
2answers
77 views

How can I get O(1) prepend on a random-access list?

I need a data structure that has the following operation: $\operatorname{prepend}([x_{n - 1}, ..., x_0], x_n) = [x_n, ..., x_0]$ $\operatorname{prepend}$ should be in $O(1)$. Assume that you have ...
1
vote
5answers
131 views

Why is b-tree search O(log n)?

B-tree is a data structure, which looks like this: If I want to look for some specific value in this structure, I need to go through several elements in root to find the right child-node. The I ...
0
votes
1answer
34 views

Complexity of testing membership in a disjoint set

I have a disjoint set data structure (sometimes known as a union-find data structure) where I store a value in each "node". I want to look up a node by value. How can I do this? The representations ...
0
votes
1answer
42 views

Where does the process reside in memory?

When a program runs in CPU, it turns into a process. In what kind of data structure is the process stored in a system memory? Heap or Tree or some other data structures?
0
votes
0answers
27 views

Linear hashing vs extendable hashing - memory

could you give me an example when linear hashing costs more memory than extendable hashing? And the other side, when extendable hashing takes more memory than linear hashing?
5
votes
1answer
132 views

Suggest a data-structure that supports the following operations with time complexity of $ O(log(n)) $

Iv'e been struggling a lot with this one. I am looking for a data-structure (could be a modification of an existing type of data-structure, or a combination of more than one data-structure), which ...
-1
votes
1answer
34 views

Priority Queue using an AVL tree, run time question

This is a question I want to answer in pseudocode: This is regarding a sort of priority queue using an AVL tree. I initialize a global variable (named GLOB) with 0. I receive from the user an input ...
1
vote
1answer
33 views

Wikipedia does not list insertion complexity for arrays - why?

Wikipedia does not list insertion complexity for arrays in the list of linked-list implementations. Is this because insertion operations are not defined on the array ADT?
0
votes
0answers
23 views

T(n)=T(n-2)+T(n-3)+T(n-4)+2 is O(log n)? [duplicate]

how can i prove that T(n)=T(n-2)+T(n-3)+T(n-4)+2 is O(logn)? or T(n)=T(n-1)+T(n-3)+1 the same.. when T(0)=1 T(1)=2 T(2)=3 T(3)=5 T(4)=8 etc`.. it's a Q about AVL-2 tree,the same rules of AVL tree ...
0
votes
0answers
24 views

How to ensure that no manipulation to data records has been made

Let's say I have a transaction history, like this: Transaction #1: Add 5 Transaction #2: Add 8 Transaction #3: Remove 2 Transaction #4: Cancel Transaction #2 Is ...
1
vote
1answer
36 views

Why does Skiena reserve space for n+1 adjacency lists? [closed]

I am reading up on graph theory from the book Algorithm Design Manual - Skiena. And he shows a structure of a graph as follows : ...
1
vote
1answer
91 views

improving java 8's implement to hash map using avl tree

Java 8 got a new implement to hashmap (using a tree). I have understand that in the worst case, it may be O(n) for lookup. Will changing this implement to an avl tree change this O(n) case to ...
1
vote
0answers
27 views

What is the psuedo-code for Tremaux's Algorithm as a Depth First Search to solve a maze?

I was interested in the Tremaux Algorithm as a Depth First Search to solve a Maze. Unfortunately I was not able to understand what Data Structures are and how they could be used. For example, I saw a ...
1
vote
0answers
24 views

Resources to learn about distributed data structures? (DHT, Merkle Tree, etc.)

I'm having a hard time finding comprehensive literature on distributed / p2p data structures... for example, I have found the book "Handbook of Peer-to-Peer Networking", which seems to be what I want (...
3
votes
0answers
32 views

Are there any practical drop-in replacements for BSTs in the case where data are integers?

There are a number of specialized data structures that implement ordered dictionaries for integer keys: van Emde Boas trees, y-Fast tries, fusion trees, etc. Each of these data structures implement ...
0
votes
0answers
39 views

Succinct Data-Structures [duplicate]

What is a possible data structure $X$ which stores non-negative integers $x_1, x_2, ..., x_n$ which supports the following operations: $index(k, X)$ returns the biggest $i$ so that $\sum_{i=1}^n x_i ...
1
vote
0answers
19 views

Succinct Data-Structures [closed]

I can't find a data structure which stores an ordered list of non-negative integers $X=(x_1,\ldots,x_n)$ with the following operations: $\mathrm{Index}(k, X)$ returns the largest $i$ such that $x_1+...
3
votes
0answers
34 views

Data Structure for k Nearest Neighbour Search in D dimension using only point cloud as query points

I have a point cloud of N points in D-dimensional space with periodic boundary conditions, where N can range from 500 to 10^8 and D can range from 1 to 20. The distribution of points varies wildly, ...
1
vote
1answer
50 views

Why isnt node checked for nil value in start when transplanting binary tree

Whilst I was reading CLRS I came across this: When TRANSPLANT replaces the subtree rooted at node u with the subtree rooted at node v, node u’s parent becomes node v’s parent, and u’s parent ends ...
1
vote
1answer
58 views

What exactly (and precisely) is “offset”?

Just like my previous question concerning 'hash'; what exactly is an (or the) "offset?" Is it a value or data type? Or is it an address location? I have heard it used in different contexts within the ...
2
votes
1answer
42 views

How to construct a running kd-tree?

I have a stream of 3-tuples of type (x,y,t) where x and y are in the range ...
0
votes
1answer
27 views

Looking for a use case of a $k$-$d$ tree with a norm other than $L^2$

In Python's implementation of $k$-$d$ tree it is possible to manually change the norm used for computing distances from $L^2$ to $L^p$. When would one use a norm other than $L^2$ in a $k$-$d$ tree?
1
vote
0answers
29 views

Trying to understand a way to split an AVL tree in O(log n)

I'm trying to understand a presentation about AVL trees. It says that the way to split AVL trees in node x is as follows: You search for the node x and mark every left son of every node when you turn ...
0
votes
0answers
23 views

On an AVL tree insertion/deletion, which nodes have their height changed and why?

I've begun learning about AVL trees. It seems that the assertion with this data structure is that with every insertion/deletion, the only nodes whose height changes are nodes on the path towards the ...
4
votes
1answer
244 views

What is the difference between a R-tree and a BVH?

I've just read about R-Trees: The key idea of the data structure is to group nearby objects and represent them with their minimum bounding rectangle in the next higher level of the tree; the "R" ...
0
votes
0answers
24 views

RMQ with single index update in array

Range Minimum Query (RMQ) can be solved in (O(n), O(1)) if the array is known to be static by dividing it into blocks and then using Cartesian tree numbers to detect "similar" blocks. Link: http://...
10
votes
7answers
2k views

How to find middle element of linked list in one pass?

One of the most popular question from data structures and algorithm, mostly asked on telephonic interview.
1
vote
0answers
19 views

Bounded pairwise distance on moving points

Suppose you're writing a video game that takes place on a large rectangle (2d). You have a large list of entities (monsters, spells, and so forth, represented as points) living on this rectangle, and ...
-3
votes
1answer
34 views

Virtual address lookup without using all the space to store the physical addresses [closed]

How is a virtual address mapped to a physical address? The most logical solution I, with my meager knowledge, can think of would be to actually store the physical address. The problem with the above ...
5
votes
0answers
130 views

Prove/disprove the existance of a data structure that has O(log N) inserts/deletes and get k-th largest element in O(1)

Consider a sorted array. We can get the $k$-th largest element in $O(1)$, but insertions and deletions cost $O(n)$. Consider an order statistic tree. Insertions and deletions cost $O(\log{N})$, but ...