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

learn more… | top users | synonyms (1)

9
votes
0answers
63 views

Efficient algorithms for vertical visibility problem

During thinking on one problem, I realised that I need to create an efficient algorithm solving the following task: The problem: we are given a two-dimensional square box of side $n$ whose sides are ...
-2
votes
0answers
45 views

Design Structure in Computer Science [on hold]

How can we create Data Structure that insert and delete order be O(log n) and find all of the elements that bigger than a and lower than b in O(log n)? My hint is AVL Tree, but about finding element ...
-5
votes
0answers
38 views

ส็็็็็็็็็็็็็็็็็็็(ಠ益ಠส็็็็็็็็็็็็็็็็็็็ Why this emoticon does what it does? [on hold]

My question is: Why the hell does this emoticon breaks the line ส็็็็็็็็็็็็็็็็็็็(ಠ益ಠส็็็็็็็็็็็็็็็็็็็ like this? I mean, how computers allow this? I know this is not the best 'computer ...
0
votes
0answers
28 views

Complexity analysis of Dynamic Connectivity problem [on hold]

In the dynamic connectivity problem using Euler Tour (in graphs) we make 3 fundamental operations: insert , delete, find_root. And the trick for getting the desired complexity is using a branching ...
4
votes
1answer
71 views

How to avoid cascading resizes when resizing hash tables?

With conventional collision resolution methods like separate chaining and linear/quadratic probing, the probe sequence for a key can be arbitrarily long - it is simply kept short with high probability ...
-1
votes
1answer
53 views

Implementability of a (abstract) data structure/type? [closed]

Do people consider the implementability of a (abstract) data structure or a data type, just like people do for implementability/computability of an algorithm? By implementability, I mean if a ...
5
votes
2answers
176 views

What is the connection between data structures and data types?

I have read some books and wikipedia, which seem to give not completely consistent definitions and notations. I try to understand the concepts, regardless of what they are called. Here are what I have ...
3
votes
1answer
159 views

What do queues and stacks correspond to in math?

Many (and I suspect all) abstract data types in CS correspond to some math concepts, and even share the same names, for example, set, map, record/tuple, .... As abstract data types, what do queues ...
-2
votes
0answers
33 views

AVL-tree rotations

Let's suppose that I delete an item from an AVL-tree and the tree gets unbalanced. Is there more than 1 different set of rotations to get the tree balanced ? Take this example: I have this tree ...
0
votes
0answers
74 views

Does this algorithm on a circular linked list ever terminate?

Suppose we have a circular linked list that has nodes $1$ to $n$. L is a pointer that points to node 1 (with label $1$). Note ...
4
votes
4answers
90 views

Interleaving algorithm for 2 stacks

Suppose I have two stacks $<a_1,a_2,...a_m>$ and $<b_1, b_2,...b_n>$ and a third stack of size $m+n$. I want to have the third stack in the following manner, ...
0
votes
0answers
34 views

Implementing BTrees without pointers

I am trying to implement a BTree in a pointer-free language as a proof-of-concept. However, a question came to my mind: every time I need to split a node, I need to do a deep copy of all the nodes in ...
-1
votes
0answers
32 views

Big O analysis of algorithm used to check for subtree of binary tree

This is the algorithm I used to check if a Binary tree is a subtree of another Assuming A is the pointer to root of Binary tree P and B is the pointer to the root of Binary tree T. Funtion ...
2
votes
2answers
92 views

Quickly locating nearest rectangle from a point

The problem is as follows: There are several rectangles in the plane (they are not necessarily axis-aligned), how can we index them in such a way that given a point $p$ we can quickly locate the ...
4
votes
2answers
95 views

Using singly linked list instead of a doubly linked list?

Are there advantages of implementing a singly instead of a doubly linked list other than space?
0
votes
1answer
27 views

Hashing and number of comparisons [duplicate]

Say, I want to put N objects into a hash table. How do I figure out how big the size of the table needs to be to have K comparisons on average when the table is: half full? three quarters full? all ...
0
votes
1answer
30 views

Depth of any node x in Weighted Quick-Union Algorithm

I know from Sedgewick's book on algorithms that the max depth of any node x from a set of N nodes is at most log2(N) applying the algorithm(which says to put the shorter tree beneath to avoid tall ...
0
votes
1answer
46 views

what's the meaning of LOC(X[j]) = $L_0$ + cj in TAOCP's 5.4.1R?

in TAOCP vol3 2nd Edtion's 5.4.1R Replacement Selection, there is a paragraph describing a data structure and example for Replacement Selection as follows: the algorithm below uses a data structure ...
6
votes
0answers
92 views

Approximate nearest neighbour in practice

I have $10^3$ vectors each of dimension $10^4$. Each dimension takes an integer from a limited range. I would like to build a data structure that will answer approximate nearest neighbour queries ...
4
votes
4answers
271 views

A “triangular” data structure for commutative relationships

A multiplication table is symmetric over a diagonal, so only about $n^2/2$ of the elements in an $n \times n$ multiplication table contain unique information. Same goes for addition tables. In fact, ...
-1
votes
1answer
60 views

Learning, understanding and using algorithms [closed]

I am a 2nd year computer science student. We all have subjects about Data Structures, Theories, more more theories we all know that i have a subject this semester Design Analysis of Algorithms. So ...
1
vote
1answer
99 views

Term for binary search tree using hashes?

I was looking for a way to easily store and access a symbol table using the least memory and code as possible and I went with a BST. Symbols, however, tend to be defined in order as in foo0, foo1, ...
1
vote
1answer
38 views

Finding Hash of Substring [i, j] in O(1) using O(|S|) pre computation

Given a string S of length n characters, is it possible to calculate the Hash of its substring [i, j] (From index i to index j. Inclusive) in O(1) using some form of precomputation ? Maybe a ...
1
vote
2answers
121 views

Finding shortest path from a node to any node of a particular type [closed]

I have an un-directed, un-weighted graph G.Starting from a given node A, i want to find whether there is a path from A to a node of a certain type .There can be many nodes of that type. The problem is ...
0
votes
2answers
97 views

B-Tree and how it is used in practice

I understand what a B-Tree is (I already implemented a B-Tree in Java with insert and delete methods that preserve the invariant). However I do not understand exactly how it is used for example for ...
1
vote
2answers
60 views

Don't understand one step for AVL tree height log n proof

I came across a proof that the an AVL tree has O(log n) height and there's one step which I do not understand. Let $N_h$ represent minimum number of nodes that can form an AVL tree of height h. Since ...
5
votes
4answers
491 views

What's the difference between a binary search tree and a binary heap?

These two seem very similar and have almost an identical structure. What's the difference? What are the runtime complexities of each?
1
vote
1answer
36 views

Combined linked/array-like data structures for a set of non-intersecting sub-intervals of integer interval?

This question is related to my previous question: Looking for a set implementation with small memory footprint I'm looking for information about combined data structures, which can efficiently ...
1
vote
1answer
41 views

Partial Range Query on Inverted File with Combined Index

I am currently reading Multidimensional and Metric Data Structures by Hanan Samet for fun. The combined index is discussed on page 5-6. I do understand it in the sense that the inverted file itself is ...
-1
votes
2answers
55 views

Is there only one optimal BST?

as i read some material about Optimal BST, i ran into a trouble. for following key i find two optimal BST with Average Cost = 30. 1 optimal BST using Dynamic programming Algorithm and 1 by hand ! ...
0
votes
2answers
50 views

Is there a term for a tree where the values of the children add up to a fixed value?

I have a tree with percentages of the following form ...
-2
votes
1answer
45 views

Min-Heap Insertion Problem

I try to insert 4-9-3-7 and 1 (left to right) into a Min-Heap (using array implementation). Then 5 times Remove Smallest Number from this Min-Heap. how many swap between two elements in array ...
1
vote
2answers
57 views

choice of data structure for domino tilings

A domino tiling is a tesselation of a region in the plane by 2 × 1 squares. What is a good data type for storing and manipulating such objects? In my current manipulation, use an array to ...
0
votes
1answer
35 views

How to design xml schema for digital circuits? [closed]

how can i design XML Schema for logical and digital circuits? i cant find any help or manual for this work for example i have a digital circuits with AND OR NOR ,... gates now i want design xml ...
0
votes
2answers
108 views

High Dimensional Data Structures

I have a 20-dimensional dataset, with a large amount of data points. I would like to have each dimension discretized into bins. Per bin, I would like to be able to access two neighbours per dimension ...
0
votes
0answers
19 views

Amortized analysis of nested loop

I have a fairly simple algorithm, consisting of an inner while-loop in an outer for-loop. Even though the algorithm is simple enough, it's quite hard to explain exactly what it does. However, it's ...
0
votes
1answer
26 views

Join large list of pairs

I have a list of millions of pairs of strings, and I want to join all of the pairs that have matching members into lists without duplicates. Example input: ...
3
votes
2answers
90 views

Are there any CS-trees named after flora-trees?

This is meant to be a fun question, and I hope it's not too off topic. Is there a defined mathematical object or data structure that has a name collision with a type of physical tree in the real ...
-3
votes
1answer
60 views

Building a Red Black tree out of a sorted array [closed]

If I have a sorted array of size $n$, can I build a Red Black tree out of it in $O(n)$ time in a different algorithm rather than splitting the tree in half every time or the straightforward way that ...
0
votes
1answer
42 views

Find longest path between two disjoint sub-sets of vertices $V_1, V_2 \subset V$ of a Graph

I have a homework question which I would appreciate some help with: Let there be a DAG $G=(V,E)$ with positive weights. For every two different vertices $v_1, v_2$ we will define $D(v_1, v_2)$ to ...
2
votes
0answers
44 views

Binary heap of size $n$ splitting to 2 heaps of size $n/2$ [closed]

Input: A binary heap of size $n$. $n$ is even. Output: 2 binary heaps of size $n/2$ each. I found this question in a solved algorithms test and the solution said: "There is no better solution than to ...
1
vote
1answer
35 views

Order of steps in Kosaraju-Sharir

The Wikipedia summary of the Kosaraju-Sharir algorithm is as follows: Let G be a directed graph and S be an empty stack. While S does not contain all vertices. Choose an arbitrary ...
-1
votes
1answer
29 views

Efficient search with removal

I want to search from a given set of elements. Along with that I also want to remove that searched element. The problem is that the number of these queries is $q=O(n)$, where $n$ is the number of ...
2
votes
1answer
36 views

Binomial heap multiplying nodes

Input: A max binomial heap $H$, and a pointer to a node $V$. Output: A max binomial heap, where all the children of $V$ are multiplied by 2. I have tried solving this by taking out the node $V$ ...
2
votes
1answer
48 views

Lower-bounding the Membership Problem in the Bitprobe Model

I am working through the following paper "Data Structures for Storing Small Sets in the Bitprobe Model" by Radhakrishnan et al. and am confused regarding one of their arguments about a lower bound. ...
1
vote
2answers
73 views

directed graph data structure with fast in/out neighbor query

If I store a directed graph $G$ in adjacency list format, one can find all the out-neighbors $j$ of a given vertex $i$ in $\mathcal O(d)$ time, where $d$ is the max degree of the graph. These are all ...
0
votes
0answers
71 views

Recurrence Equation in Algorithm [duplicate]

Can anyone help me in solving this complex recurrence? \begin{eqnarray} T(n) &=& n +\sum_{k-1}^n T(n-k)+T(k) & Where& T(1) = 1. \end{eqnarray} although this topic will already ...
2
votes
1answer
90 views

(AVL Trees) What is the maximum possible difference between the number of nodes in the root node's subtrees? [duplicate]

Question: If an AVL tree has height h (assume h ≥ 2), what is the maximum possible difference between the number of nodes in its two subtrees? Prove your answer. Your answer should not use big-Oh or ...
-1
votes
1answer
51 views

Number of Different AVL Tree

I studying the related question. http://stackoverflow.com/questions/13500560/number-of-ways-to-create-an-avl-tree-with-n-nodes-and-l-leaf-node but it's not so general. In-fact, We want to know ...
4
votes
1answer
257 views

Array-like immutable (persistent) data structure implementation with fast indexing, append, prepend, iteration

I'm looking for a persistent data structure similar to array (but immutable), allowing for fast indexing, append, prepend, and iteration (good locality) operations. Clojure provides persistent ...