Questions about ways of storing data so that it can be used advantageously by algorithms.
4
votes
0answers
119 views
Google Code Jam Great Wall Problem
So, Google Code Jam round 1C has just wrapped up, and one of its problems seems rather elusive to me: https://code.google.com/codejam/contest/2437488/dashboard#s=p2
A quick summary of the problem is ...
3
votes
0answers
44 views
how to represent Sparse Matrices
I have been using Harwell Boeing format, also known as Compressed Column Strorage (CCS) in order to store Sparse Matrices.
Could you please suggest me some other way to store/represent sparse ...
0
votes
1answer
21 views
Sequential hash tree traversal
A lot of articles say that hash tree traversal cost to any randomly chosen leaf is $\mathcal{O}(\log_2 N)$ ($N$ is a number of leafs) and that is right. If we have a tree of 8 leafs it will take us at ...
2
votes
1answer
36 views
Changing AVL's balance factor to some other $s>2 \in \mathbb{N}$
Given we change the rule to:
$-s \ \ \leq$ height(left-subtree) - height(right-subtree) $\leq \ \ s$
I was wandering whether it's possible and how would it affect the trees' height, would it ...
0
votes
1answer
24 views
change the info part of each node in binary tree [closed]
i have a binary tree.
2
/ \
3 4
/ \ \
5 1 8
\ /
6 9
I want to change the info part of each ...
2
votes
1answer
34 views
Prove that inserting $n$ sorted values in to an AVL using AVL insertion is $\Theta\left (n \log \left ( n \right ) \right )$
We're asked to prove the above mentioned lemma but I having a hard time proving this rigorously.
We did prove that given $n$ values AVL's height is $\Theta\left (\log \left ( n \right ) \right )$ So ...
6
votes
2answers
93 views
Is there a binary tree structure with fast access to recently accessed elements and worst $O \left( \log n \right )$ complexity?
The idea of splay trees is very nice as they move frequently accessed elements to the top, which can gain a considerable speed up in many applications. The drawback is that in the worst case an ...
5
votes
1answer
78 views
Is there a binary search tree datastructure which can avoid becoming badly weight-balanced?
This is a follow-up question of "Not all Red-Black trees are balanced?" and "AVL trees are not weight-balanced?".$\def\le{\leqslant}\def\ge{\geqslant}$
Definition: For a rooted tree $T$ and a ...
0
votes
0answers
43 views
Best case analysis for shell sort
The exercises in a textbook I studied asks about the best case for shell sort. I have scribbled a derivation for the same along the margins almost two years ago. Basically I don't know if this was my ...
1
vote
1answer
34 views
How is sound input and output data converted to use with machine learning networks?
Suppose one has a couple of .wav files with English spoken words, multiple ones for each word, and for each such set there exists a transcription of their right output, the pronunciation as ascii ...
2
votes
1answer
52 views
performance between the data structures
I have developed two existing data structures and I want to see their performances over a certain algorithm. In this case I use Dijkstra's algorithm with binary and Fibonacci heaps. Just to ask, if I ...
6
votes
4answers
195 views
Data Structure for Set Intersection?
Is there any data structure that maintain a collection of set (of finite ground set) supporting the following operations? Any sublinear running time will be appreciated?
Init an empty set.
Add an ...
0
votes
1answer
55 views
How to perform bottom-up construction of heaps?
What are the steps to perform bottom-up heap construction on a short sequence, like 1, 6, 7, 2, 4?
At this link there are instructions on how to do for a list of ...
5
votes
1answer
68 views
What is a compact way to represent a partition of a set?
There exist efficient data
structures for representing set
partitions. These data structures have good time complexities for operations
like Union and Find, but they are not particularly ...
1
vote
1answer
36 views
Finding the element that occurs more often than the other
I want an algorithm that calculates which element, among two, appears more often than the other in a sorted array. The array will have only two types of elements.
Example : $aaaaaabbb$
Here ...
1
vote
0answers
35 views
Which data structure to use to solve equations?
Let's say I have two equations for a geometric object (a rectangle):
$\left\{
\begin{array}{l}
x \ge 0 \\
y \ge 0 \\
A \ge 0 \\
P \ge 0 \\
A = x*y \\
P = 2*x + 2*y
...
3
votes
1answer
63 views
AVL tree with fixed height and as few elements as possible
I have been reading about AVL trees, at the moment I'm trying to figure out how to determine the height of a tree and how to draw an AVL tree of some height with minimum number of elements.
In a ...
3
votes
1answer
69 views
Number of possible search paths when searching in BST
I have the following question, but don't have answer for this. I would appreciate if my method is correct :
Q. When searching for the key value 60 in a binary search tree, nodes containing the key ...
8
votes
3answers
197 views
Why is it best to use a prime number as a mod in a hashing function?
If I have a list of key values from 1 to 100 and I want to organize them in an array of 11 buckets, I've been taught to form a mod function
$$ H = k \bmod \ 11$$
Now all the values will be placed ...
3
votes
1answer
44 views
When two siblings in a heap are equal, how do you bubble down?
I have a heap where both child nodes of the root are 10, and I'd like to perform an operation to remove the min value 9.
I proceed to replacing the root with its next of kin, 18. However when I ...
5
votes
2answers
148 views
Colour a binary tree to be a red-black tree
A common interview question is to give an algorithm to determine if a given binary tree is height balanced (AVL tree definition).
I was wondering if we can do something similar with Red-Black trees.
...
3
votes
1answer
107 views
Get the running time of forest disjoint sets
If you have a forest implementation of disjoint sets, and have the union by weight/rank heuristic where you append the smaller one. Then why is the worst case running time Θ(m log n)? (m is the ...
1
vote
1answer
82 views
Complexity of algorithm inserting an element in a circular linked list at the front end
In a circular linked list, if an elements needs to be inserted at front [just before the node pointed by head], can be done in O(1) (see the answer here)
But in a book currently, I have, it is ...
5
votes
1answer
68 views
A vector-like data structure with allocation table; O(1) indexing time required
I am a beginner in data structures and recently came across a vector implemented on an array, which is extended on demand. Of course the table cannot be extended "in place", we must allocate a new ...
15
votes
1answer
171 views
Weighted sum of last N numbers
Suppose we're receiving numbers in a stream. After each number is received, a weighted sum of the last $N$ numbers needs to be calculated, where the weights are always the same, but arbitrary.
How ...
2
votes
1answer
114 views
How to get expected running time of hash table? [duplicate]
If I have a hash table of 1000 slots, and I have an array of n numbers. I want to check if there are any repeats in the array of n numbers. The best way to do this that I can think of is storing it in ...
2
votes
1answer
61 views
Hash function - uniformity / strong universality
I am currently learning how randomised Hashing works.
So, you have a class (aka family) $H$ of hash functions, each of which maps the universe $U$ to the hash table $N$.
That class is called ...
3
votes
1answer
104 views
How to compute amoritized cost for a dynamic array?
I am trying to understand how to do the amortized cost for a dynamic table. Suppose we are using the accounting method.
Let A of size m be an array of n elements. When $n = m$, then we create a new ...
6
votes
2answers
84 views
Test if there are two subsets which cover a set
Given a set $S$ of $n$ elements, and a set $\mathcal{X}$ of $m$ subsets of $S$, decide if there exist $U,V \in \mathcal{X}$, s.t. $U \cup V = S$.
Brute force would take time $O(nm^2)$ but is there ...
6
votes
2answers
98 views
Are probabilistic search data structures useful?
A SkipList provides the same $O(\log n)$ bounds for search as a balanced tree with the advantage that rebalancing isn't necessary. Since the SkipList is constructed using random coin flips, these ...
2
votes
3answers
463 views
Increase-key and decrease-key in a binary min-heap
In many discussions of binary heap, normally only decrease-key is listed as supported operation for a min-heap. For example, CLR chapter 6.1 and this wikipedia page. Why isn't increase key normally ...
9
votes
0answers
123 views
Is there a data-structure which is more efficient than both arrays and linked lists? [duplicate]
Background:
In this question we care only about worst-case running-time.
Array and (doubly) linked lists can be used to keep a list of items and implement the vector abstract data type. Consider the ...
0
votes
0answers
20 views
Algorithm for query comparison
Lets say I have a global dataset and I run queries over those data set.
For example my dataset would be
#id, #Name, #Employee, #Birthdate, #number_of_children
1, Nick, Nasa, 1982, 1
2, Jack, Exon, ...
2
votes
0answers
47 views
Leftist heap - determining time complexity
The time complexity of merge (union) operation is said to be $O(\lg (n_1 + n_2))$, where $n_1$ and $n_2$ are the numbers of elements in the merged heaps, respectively. I do not understand this - the ...
0
votes
1answer
79 views
What graph data structure works fastest with Dijkstra's algorithm?
What data structure should I store my graph in to get the best performance from the Dijkstra algorithm?
Object-pointer? Adjacency list? Something else?
I want the lowest O(). Any other tips are ...
2
votes
1answer
92 views
Is search a binary heap operation?
According to the Wikipedia page, search is "not an operation" on binary heaps (see complexity box at top-right).
Why not? Binary heaps may not be sorted, but they are ordered, and a full graph ...
2
votes
1answer
25 views
Sharing of nodes in Persistence data structure
I asked a question on persistence data structure here. After that I came across an article on code project. I have got a question on the following figure from the same article:
The author says:
...
7
votes
3answers
192 views
Why do we use persistent data structures in functional programming?
Functional programming employs persistent data structures and immutable objects. My question is why is it crucial to have such data structures here? I want to understand at a low level what would ...
4
votes
2answers
85 views
Lossless data compression must make some messages longer? [duplicate]
I read on Wikipedia and in lecture notes that if a lossless data compression algorithm makes a message shorter, it must make another message longer.
E.g. In this set of notes, it says:
Consider, ...
2
votes
2answers
63 views
Finding the height of a d-ary heap
I would like to find the height of a d-ary heap. Assuming you have an Array that starts indexing at $1$ we have the following:
The parent of a node $i$ is given by: ...
10
votes
0answers
124 views
How does the runtime of the Ukkonen's algorithm depend on the alphabet size?
I am concerned with the question of the asymptotic running time of the Ukkonen's algorithm, perhaps the most popular algorithm for constructing suffix trees in linear (?) time.
Here is a citation ...
2
votes
4answers
107 views
Is a relational database just a $ \geq 2$-dimensional array?
In terms of comparing data structures, is a relational database just a >1 dimensional array? I'm just asking because I don't know much about databases, but I know a bit about data structures.
I am ...
11
votes
2answers
117 views
Are link-cut trees ever used in practice, for max flow computation or other applications?
Many max flow algorithms that I commonly see implemented, Dinic's algorithm, push relabel, and others, can have their asymptotic time cost improved through the use of dynamic trees (also known as ...
2
votes
1answer
61 views
0 and 1 Queries in tables of N*N cells
There is a square table composed of N*N Cells. Initially all cell is filled with a number 0.
Two types of Operations can be ...
3
votes
2answers
116 views
Algorithm for building a suffix array in time $O(n \log^2 n)$
I've been working with suffix arrays lately, and I can't find an efficient algorithm for building a suffix array which is easy to understand. I have seen in many sites that there is an $O(n \log^2 ...
2
votes
1answer
55 views
MinHeap represented by an array - two simple statements
I'm trying to prove/disprove two statements. I just want to make sure with you I'm on the right line.
These are the following statements:
Preface : Let A[n] be an array of min-heap (a min-heap ...
2
votes
6answers
179 views
Algorithm books on a range of topics
I've been tasked with building a library of books on algorithms for our small company (about 15 people). The budget is more than 5k, but certainly less than 10k, so I can buy a fair number of books. ...
3
votes
1answer
45 views
Is there a term for the general method used in XORed linked list?
The XOR linked list is perhaps the most prominent example of storing a reversible hash of two values and using a known value and the stored hash value to derive the other value. Is there a term for ...
1
vote
1answer
73 views
Input that causes an operation on a binomial heap to run in $\Omega(\log n)$ time?
I was studying binomial heaps and its time analysis. Are there any inputs that cause DELETE-MIN, DECREASE-KEY, and DELETE to run in $\Omega(\log n)$ time for a binomial heap rather than $O(\log n)$?
3
votes
1answer
67 views
What sort of algorithm/communication model/data structure do collaborative real time editors use?
I am researching collaborative editing systems for some work, but so far my search is turning up blank.
Collaborative real-time editing systems almost all have features like:
Many users can edit ...
