Questions about ways of storing data so that it can be used advantageously by algorithms.
1
vote
1answer
22 views
Matrix of a graph and computational complexity
Given a simple undirected graph with no self-loops, $G = (V,E)$, where $V = {1,2,...,n}$, an $n × n$ matrix $A$ is said to be the adjacency matrix of $G$ if $A_{i,j}$ is $1$ if $(i, j) ∈ E$ and $0$ ...
2
votes
0answers
26 views
Bug in wikipedia page for Van Emde Boas tree?
The Wikipedia page for vEB trees (specifically the version from 27 September, 2018),
gives the following pseudocode for finding the successor element of x in the vEB tree (of universe of size M):
<...
0
votes
0answers
21 views
Minimal hashing function for integers that satisfy specific constraints
I'm looking for a kind of way to create a minimal perfect hash function given a set known integers.
More specifically, I have M numbers within the range 0-N with N > M.
Does it exist a way to create ...
0
votes
0answers
9 views
AVL Tree:Deletion proof
Show that at most one node in an AVL tree becomes temporarily imbalanced after the immediate deletion of a node as a part of standard remove map operation.
How should I start and what should I use to ...
2
votes
1answer
38 views
Largest rectangle problem
Recently while solving programming challenges for the fun of it, I encountered a challenge which left me kind of puzzled and yearning for a proper solution, other than brute forcing. The problem (...
0
votes
1answer
24 views
Determining an appropriate number of buckets for a hash function
I would like to select an appropriate number of buckets in my hash table for this scenario:
A hash table with collision resolved is required to hold about 10000 records. Each record is to be indexed ...
2
votes
1answer
23 views
minimum number of nodes that traverse all the graph
In the following graph, we can traverse entire graph if we select the nodes 0 and 2. I am looking for an efficient algorithm which returns this two nodes. Note that this is neither vertex-cover ...
0
votes
1answer
59 views
Calculate the average length of the linked lists in a hash table
I am learning hash tables, and I would like to know how to determine the average length of the linked lists.
For example: A hash table holds about 10,000 employee records. Each record is indexed by ...
2
votes
0answers
10 views
What are some of the simplest applications of heavy hitter problem?
I am learning about stream algorithms and am implementing Count-Min sketch data structure. I am also learning to approximately solve the HH problem with sublinear space complexity.
I want to know ...
1
vote
0answers
39 views
Insertion in 123 skip list
I had a problem in my exam dealing with 1-2-3 skip lists.
I have a problem with the insertion process in a 1-2-3 skip list. What I understand is that if the minimum of heights of 2 nodes in a 123 ...
2
votes
3answers
41 views
BST - Sufficient condition for connecting a node to a parent
Let's assume that we have a binary search tree with node Y that hasn't a right child and for whom a successor exists in the tree.
I want to prove that if I insert a node X into the tree and node X is ...
2
votes
1answer
14 views
Approximating unique string occurrences using a small, fixed amount of memory
Is there a small-memory way to estimate how many unique strings have been encountered without needing to know the strings themselves? The trick is that we only have a tiny amount of memory to track ...
1
vote
0answers
19 views
How did the Registers get their names?
I'm interested in how the computer registers got their names, for example:
eax and ebx. I couldn't find anything.
1
vote
0answers
22 views
Intuition behind balancing of link/cut data structure
My question concerns link/cut tree structure after an access operation. I am assuming an implementation with splay trees. As far as I can tell, once you access a node v and splay it to the root, it no ...
0
votes
0answers
13 views
Data structure for fixed sized records that only need to support full scans
Background
I'm building a memory-mapped inverted index for document search. The inverted index stores (docId, tokenId) pairs, and the whole memory-mapped file is divided into blocks.
A block has a ...
1
vote
1answer
25 views
Understanding basic queue and dequeue operations
CLRS gives the following implementation for a queue's enqueue and dequeue operations
...
1
vote
0answers
23 views
Direct addressing on a huge array
A Question from CLRS book:
(CLRS 11.1-4) We wish to implement a dictionary by using direct addressing on a
huge array. At the start, the array entries may contain garbage, and initializing the
...
1
vote
1answer
25 views
How to find the number of Binary Search Trees with given number of nodes and leaves?
With 7 nodes of distinct values (unique), how many Binary search trees (BST) can be formed such that:
Exactly $1$ leaf node(s) present?
Exactly $2$ leaf nodes present?
I was able to solve the first ...
-1
votes
0answers
34 views
Does ORM sacrifice the database design?
First of all, I hope my question will not be considered too practical for CS. I'm wondering if using Object-relational mapping implies a not well designed database. I will use a concrete example with ...
1
vote
3answers
74 views
Data structure for getting the k'th largest element
I'm given a set of $n$ numbers. Is there a data structure that builds in $O(n)$ (linear time) and gets the $k$'th largest element in $O(k)$ time? Also, is there anything better than $O(k)$?
1
vote
1answer
31 views
when to use preorder, postorder and inorder binary search tree traversal strategies
What are some examples of when to use preorder/postorder practically? When does it make more sense than in-order?
1
vote
0answers
21 views
What is the algorithm to determine valid push and pop sequences for stack when repetition of numbers are allowed?
Unlike traditional problems dealing with push and pop sequences of distinct numbers, I would like to know the procedure to determine the validity of the stack operations for sequences of non-distinct ...
0
votes
1answer
25 views
How can we form a graph from this problem?
So from the above diagram, we can move either right or down. So a binary tree is built that way. It's written ...
2
votes
2answers
32 views
A data structure that makes finding close objects easy
I’m working on a project that involves a robot and a very large number of reference points. The robot moves around, while the reference points are fixed in space. I would like the robot to be able to ...
1
vote
1answer
13 views
Algorithm for commonalities across related objects
I am making early forays into the application of algorithms to best solve a problem and I am finding it difficult to choose the best application.
The problem is give the data below (two columns) ...
0
votes
1answer
64 views
Inorder Traversal of the Ternary Tree
According to wikipedia , Definition of In-order Traversal on Binary Tree :-
...
0
votes
0answers
17 views
Solving range updates and point queries for a special case
Initially we have an array of size N, all set to 0.
We have operations of two kinds:
$Increment$ the range $[L, R]$ by 1.
$Get$ the current value at $idx$.
If these queries were interspersed with ...
0
votes
1answer
27 views
All the possible inputs for a given AVL tree
Given an AVL tree,what are the possible inputs so that the same given tree is formed(please dont mention brute force technique)?
0
votes
0answers
25 views
Best data structure to store and query ip-address ranges
I would like some input on what is the best data structure to store and query ip-address ranges.
I will have v4 and v6 ip-address ranges.
The number of ip-ranges will less than 500.
0
votes
0answers
13 views
0
votes
1answer
29 views
Strengths and limitations of arrays [closed]
What are the strengths and limitations of arrays? What considerations go into choosing an array over another data structure, or vice-versa?
0
votes
1answer
45 views
Which Data Structure should I use to store words from a novel?
So, I was learning Data Structures in Java on my own. And there was a "challenge question" in the book.
The question basically asked me to make a data structure that could store all the words in a ...
1
vote
2answers
38 views
Given a sorted dictionary of words, find order of precedence of letters
This question is found at: https://www.geeksforgeeks.org/given-sorted-dictionary-find-precedence-characters/
Given a sorted dictionary (array of words) of an alien language, find order of characters ...
3
votes
0answers
30 views
If we could use electrons as information storage, how would we model a database?
It's not completely incredible that electrons are accessible information storage units. So let's say there is a breakthrough and we suddenly have read/write access to every electron on the planet. ...
0
votes
1answer
21 views
Fill the time slot with the best match
If I have the following array: pieces = {35,15,20,25,30,10} and the time slot is 80 minutes.
How do I do the following:
1. ...
0
votes
1answer
41 views
The validity of the potential function for splay tree
The paper "Self-Adjusting Binary Search Trees" defines (Page 658) the potential function for analyzing the amortized cost of a sequence of $m$ splay operations as the sum of the ranks of all nodes in ...
0
votes
2answers
50 views
In Breadth-first search and depth-first search what is the purpose of visited flag
In Breadth-first search and depth-first search, in this source code https://gist.github.com/gennad/791932
...
0
votes
0answers
31 views
2 heaps with 'mutual' pointers
I was wondering if it's possible to build 2 heaps from the same array, one would be max heap and the other one min heap (using build-Heap $O(n)$ algorithm, not the dynamic way of inserting the ...
0
votes
2answers
87 views
Data structure for finding max, inserting and deleting in O(1) and O(n) space
This is an interview question. I need to implement a data structure that supports the following operations:
Insertion of an integer in $O(1)$
Deletion of an integer (for example, if we call delete(7),...
1
vote
1answer
68 views
How many rotations after AVL insertion and deletion
Is it true that inserting an element to an AVL tree requires $O(1)$ rotations?
How many rotations, does deletion from AVL require?
I've searched for these two questions with no luck so far.
1
vote
1answer
17 views
A question about linked list
I would like to check the answer of this exercise:
A circular doubled linked list with N elements has pointers that cost k bytes each of space in memory. How many bytes do the pointers of this list ...
0
votes
0answers
18 views
Understanding time complexities of unique data structures
Imagine the following data structure:
A pair of arrays where one array is longer than the other, and both
arrays are kept sorted. The length of the shorter array is the square root of the length of ...
0
votes
1answer
22 views
Order of given value in AVL tree
given an AVL tree with $size$ value to any vertex $v$ in the tree (which is the size of the tree rooted in $v$), is it possible to tell for a given value in the tree, what its order in the sorted ...
1
vote
1answer
22 views
Asymptotic bound of a heap's height
Today I was taught that since the height of a heap cannot exceed $\log n$, it is $O(\log n)$; height in my class was defined as the maximum number of steps in a simple path from a leaf to the root. ...
1
vote
1answer
55 views
Is there any sort of formal definition of terms like 'data type', 'abstract data type', etc?
If not (because I assume not) is there some kind of reference or book that provides some theoretical foundation to these concepts? I've been learning about data structures and abstract data types for ...
2
votes
1answer
71 views
Left-Right-Rotation of AVL-Tree
For AVL-Tree there exists the following Rotations for Balancing:
Left Rotation
Right Rotation
Left-Right Rotation
Right-Left Rotation
My Question is about the Naming for the Double-Rotations. ...
4
votes
2answers
91 views
Data structure for a tree of points moving in space
I'm trying to come up with a data structure for a following model: Nodes representing points in space are structured in a tree (general rooted tree with no restrictions). Let's call these nodes "...
3
votes
1answer
41 views
Does this “reference” problem have a name?
I have the following problem which I think is so common that I expect it to have an official name (and standard algorithm of course).
The situation is as follows:
I receive distinct items (A...E in ...
0
votes
1answer
85 views
How to get all in constant time?
We are planning to design a system where following operations are supported.
...
0
votes
2answers
68 views
A data structure to do a specific lookup fast
I have 30,000 items; each item has 30 parameters that take values from 0 to 5. These parameters are named $p_0$ to $p_{29}$ and their value is an integer between 0 and 5. I want to store these items ...
