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

learn more… | top users | synonyms (1)

-1
votes
0answers
5 views

Linked List With Map

Can someone help me solve these operations. I am trying to study for my test and wanted to do these as practice but I am lost and need guidance. Implement the Map ADT using a singly linked list: • ...
2
votes
1answer
32 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 ...
4
votes
0answers
59 views

Optimize binary search on Segment Tree by storing past result

Consider a segment tree $S[k]$ that is built for ranged sum operations. This segment tree represents an array $A[n]$. It is easy to see that a weighted random algorithm $A$ using a binary search on ...
0
votes
0answers
22 views

“Accelerated” Ray Tracing [closed]

I want to create "accelerated" ray tracing. I want recommendations about great courses or books about data structures and algorithms which can provide me enough knowledge so that I can implement my ...
4
votes
1answer
102 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 ...
0
votes
1answer
28 views

Suffix Tree algorithm complexity [on hold]

I really get confused by all the different complexities you find around. One is $O(n \log n)$, the next $O(n \cdot |\Sigma|)$. Personally I think it's the last one, but I'm really not that confident ...
-2
votes
0answers
18 views

Convert Infix expression to Prefix (Operators- AND, OR etc) [closed]

I am trying to convert Infix expression to Prefix Can someone help with pointers on how to proceed.. For e.g. This would be converted (LCO) OR (near (time, attend, n=5)) OR (adp) OR (Kronos) OR ...
2
votes
1answer
71 views

Lowest Common Ancestor from children up?

I've seen algorithms for finding the lowest common ancestor from the root of a tree. However, I'm interested in finding the LCA of two distinct Nodes in a (not necessarily binary) tree from the bottom ...
2
votes
1answer
37 views

Guessing the structure of a finger tree from the number of elements

I'm writing a data structure library, and I want to write an efficient algorithm for adding many elements to a finger tree (from an iterable sequence). I'm going to do this by constructing a finger ...
0
votes
0answers
24 views

Immutable data structures for 2d+ lattices

I would like to find an immutable/persistent data structure that allows efficient updating for 2d (or higher) lattices/arrays/matrices, and reasonable performance when appending in any direction. ...
4
votes
1answer
101 views

Tallest Person Average Memory Updating?

We ran into a problem that was mentioned in an interview 2 days ago. Can you help us with any idea or hint? A sequence of $n$ people, $\langle\,p_1,p_2,\dotsc p_n\,\rangle$ enter a room. We want to ...
1
vote
0answers
37 views

Potential method analysis for Insert and Extract-max on a Max heap data structure

Suppose that you do some sequence of operations on a max heap, in this case only Insert and Extract-max. Whenever the heap ...
1
vote
2answers
37 views

Why the pointer in linked list is of structure type? [closed]

Since any node points to a memory location is there any specific need in using it's pointer as structure type.Why couldn't we use integer as the pointer type in linked list rather than structure?
1
vote
0answers
23 views

Applications of Linked Lists [closed]

I tried looking in the internet but couldn't get any applications of linked list used in day-to-do life.Could anyone list any applications of linked list?
-3
votes
0answers
38 views

Diameter and some Formula on Graph Theory [on hold]

in an undirected graph G, we define: Diameter is maximum of minimum paths between two vertex of a graph. L(s) is maximum length of minimum paths from s to ...
0
votes
1answer
36 views

Searching through a heap complexity

Pretend you want to search through a max-heap to find a specific element. I know there is no such option but still... Would it take worse case O(n) or O(logn) time? I am assuming O(n) since the ...
1
vote
1answer
37 views

Can nodes in red-black trees have one nil child and one non-nil child?

I don't recall hearing that nodes in red-black trees can't have one nil child and one non-nil child. However, I did hear that red-black trees have a worst-case height of $2log_2(n + 1)$, where n is ...
3
votes
0answers
41 views

How to apply path compression to Multi-Bit Trie

Reading a bit about the subject of Multi-Bit tries and IP matching in: High Performance Switches and Routers H. Jonathan Chao, Bin Liu. Page 33 Network Routing: Algorithms, Protocols, and ...
3
votes
1answer
50 views

Why isn't the time complexity of constructing a Fenwick tree tighter than $O(n\lg n)$?

Intuition: Suppose I have an array of nonzero integer values $A[n]$ and a partially constructed Fenwick tree of this array: $F[k], n>k$. I can see why inserting the next element would be worst ...
1
vote
1answer
51 views

What is “Oracle Access”?

I'm reading a paper for school and I have come across a passage that I don't understand. It says "If we allow the query to access the entries of the array through an oracle, it is possible to obtain a ...
2
votes
3answers
40 views

Existence of functions that only tests memberships without revealing any information about the members

Given a set of strings $\{s_1, s_2, \cdots, s_n\}$, is there a way to encode them to a program $P$, such that given some string,$s$, the program can test the membership efficiently (deterministically ...
-4
votes
2answers
55 views

Rearranging linear tree with right rotates [closed]

I ran into a fun interview question, yesterday. Can anyone help me? Suppose a binary tree with six nodes is given, such that each node has only a left child. With how many "right rotate" ...
1
vote
0answers
21 views

Longest increasing subsequence using 2-3 tree

While preparing for my data structures final I came across this problem: A - a given array of integers of length n. Propose data structure which supports the following operations: Init(A) - ...
1
vote
0answers
28 views

Median-of-medians for sorting finger trees incrementally

Haskell's Data.Sequence uses Hinze-Paterson 2-3 finger trees to represent finite sequences. The types are defined below for concreteness. Currently, the library ...
1
vote
1answer
15 views

What are the tradeoffs between implenting dataframes as a series of columns vs a series of tuples

I was reading the documentation for Julia's Dataframe package, and the package implements Dataframe by a series of a columns each of a single type. From reading the docs, it looks like that's how R ...
3
votes
0answers
31 views

Efficient deletion in Fenwick tree

Suppose there is an array of nonzero integer values A[n], which has a Fenwick tree representation F[n]. The most simplistic way ...
1
vote
0answers
34 views

Efficient data structure for set to union of sets mapping

What I have is the following: A mapping $f : key \rightarrow set$ that works in constant time An inefficient mapping $g : \{key\} \rightarrow \cup_{k \in \{key\}} f(k)$ where this union is slow Is ...
-2
votes
1answer
68 views

Find K-th next element in O(log n) time

We want to store a set S of distinct positive integers and support the following operations on S: Insert(a): insert integer a !∈ S into S. Delete(a): delete integer a ∈ S from S. ...
0
votes
1answer
44 views

The number of Binary Search Tree that exist with same Postorder and Inorder

how many BST exist with same postorder and inorder traversal? I know that in binary tree (Not BST), it is one. but i have a book from that said for BST it is CATALAN number. i become confused.
0
votes
0answers
61 views

What data structure would help find nearby coordinates quickly?

I need to write a program that does the following: Take an input list of objects whose properties include latitude and longitude to, say, 5 decimal places Store them in a data structure once Provide ...
3
votes
1answer
105 views

Data structure for a static set of sets

I have collection $U$ of sets, where each set is of size at most 95 (corresponding to each printable ASCII character). For example, $\{h,r,l,a\}$ is one set, and $U = \{\{h,r,l,a\}, \{l,e,d\}, ...
2
votes
2answers
47 views

Can one insert non-unique elements into an AVL tree?

Is it possible to insert a sequence of non-unique elements into an AVL tree? For example, what is the AVL tree result of inserting 3, 3, and 3 into an initially empty AVL tree? Is it: ...
0
votes
2answers
117 views

Is there a way to find path length to a node from root in a binary tree?

I went through the algorithm’s for finding the LCA of two nodes in a binary tree (let’s say the values are random – not a binary search tree) and I chose the method where the path to root is stored in ...
0
votes
1answer
39 views

undirected graph without weights and DFS [closed]

following question on undirected graph without weights can be solved by using DFS and in O(|V|+|E|) times. check that G is ...
0
votes
1answer
20 views

What is the name of this size method calculating the size of a node?

My confusion is that if the recursive call calls the left nodes, and then adds with the right nodes, how are the nodes that are to to right of the left nodes and vice versa being called? ...
-1
votes
1answer
77 views

Sorting tuples with respect to multiple criteria

Given $n$ rows with $k$ columns, is there a storage mechanism/data-structure and/or algorithm that enables dynamic restructuring such that I can get the top $t=\mathcal{O}(1)$ results efficiently? ...
3
votes
3answers
579 views

How are hash table's values stored physically in memory?

Question: How are hash table's values stored in memory such that space if efficiently used and values don't have to be relocated often? My current understanding (could be wrong): Let's say I have 3 ...
0
votes
1answer
92 views

Example of worst case input for Build-Max-Heap

Is there a worst-case inputs for Build-Max-Heap? I know there is but I just couldn't paint a clear picture of it in my head.
0
votes
1answer
49 views

Set Intersection with asymmetric set sizes

I'm looking for an algorithm to perform set intersection where set $N_1$ is very small and set $N_2$ is very large. Due to the constraints of the problem I am solving, I cannot rely on an algorithm ...
0
votes
1answer
86 views

Build-Max-Heap vs. HeapSort

I'm not sure whether my definition for these 2 terms are correct. Hence, could you help me verify that: HeapSort: A procedure which sorts an array in place. Build-Max-Heap: A procedure which runs in ...
0
votes
0answers
54 views

Improve the runtime of hashtable operations by keeping lists in sorted order

The following is a question from the textbook Introduction to Algorithms, however a solution to the problem is not given... Professor Marley hypothesizes that he can obtain substantial performance ...
1
vote
2answers
33 views

Red Black Tree clarification

I am quite new to Red-Black trees, and therefore I am having a bit of difficult time trying to understand them. One of the properties of the Red-Black tree is that every red vertex must have two ...
3
votes
3answers
230 views

How should I design a hash table where all the keys are permutations?

I need to create a hash table to store values for (possibly all) permutations of 123456789, which is exactly 362 880 keys. Given that I know how all the keys look ...
3
votes
1answer
86 views

Data structure to hold and retrieve points in a plane

Definition 1: Point $(x,y)$ is controlling point $(x',y')$ if and only if $x < x'$ and $y < y'$. Definition 2: Point $(x,y)$ is controlled by point $(x',y')$ if and only if $x' < x $ and $ ...
0
votes
0answers
28 views

Data Structure implementation to store Sweep Line Status in Sweep Line Algorithms

I have been trying to implement the data structure for storing the sweep line status in sweep line algorithms (eg. Bentley-Ottmann for line segment intersection) and finding it difficult to implement ...
4
votes
2answers
310 views

Data Structure for Representing a Math Expression

I'm looking to improve my object-oriented design skills and I came across a problem which asked to design classes to represent a mathematical expression such as (a + b) * ( c - d / e) in memory so ...
-2
votes
1answer
27 views

Removing arbitrary element from Max Heap

Which of the following strategies is more feasible? Strategy 1: Remove the element from the array, compress the array and reheapify. Strategy 2: Update the value of this node to the current maximum ...
0
votes
1answer
42 views

Finding A String Using A Suffix Array/Table

Is it possible to find out a string only having its corresponding suffix array/table and knowing that the string contains only, for instance, letters "f", "g", "r"? If so, how is that possible?
6
votes
1answer
34 views

The XOR cut-set structure, and combinatorial designs

Given a graph $G(V,E)$ and a subset of vertices $T \subseteq V$, define $\mathsf{cutset}(T)$ = the set of edges connecting a vertex at $T$ with a vertex at $V\setminus T$. Our goal is to preprocess ...
0
votes
1answer
48 views

Creating an K-nary tree that is balanced in both width and depth for N nodes. N known a priori

Given N items you want to put into a tree, think very generally here like a phone tree, and your goal is to keep the tree from getting "too wide" and "too deep". How many children (K) do you put at ...