# Questions tagged [data-structure]

For questions about mathematical background of data structures, including analysis and proofs and for questions based on some data structure properties. Data structures aim to allow efficient processing of particular queries on the data they contain.

66 questions
Filter by
Sorted by
Tagged with
20 views

### can somebody give me a practical example of how pairwise deletion works?

I have not found any actual examples of how pairwise deletion is used to impute missing data. For example If i have 3 variables with the data set \begin{bmatrix}5&NA&9\\NA&3&7\\8&1&...
19 views

### Unique values in a table [closed]

I am a math dummy and try to express the following in a formula. I have a table (dataframe) with a set of columns. $|X| * unique(a)$ where $X$ represents the set of columns in the table, $unique(a)$ ...
27 views

### Sketches and containers

Here is an article about sketches Containers are data structures. Here is a paper that explains when a container is a comonad I am wondering if we can have sketches that are containers. Is there a ...
10 views

### Correlation and dependence of random variables: The connection.

Before I state my question I want to give some background information about where my question comes from. I am currently reading the paper: Online Matching with General Arrivals by Gamlath, Kapralov, ...
39 views

### Determine the largest size n of a problem that can be solved in time t , assuming that the algorithm to solve the problem takes f(n) microseconds. [closed]

For each function f(n) and time t in the following table, determine the largest size n of a problem that can be solved in time t , assuming that the algorithm to solve the problem takes f(n) ...
66 views

### Asymptotically, can supercomputers easily solve the Travelling Salesman Problem, why or why not? [closed]

I just want to know if supercomputers could easily solve the TSMP or would still take a lot of time, as it does now?
22 views

### For a set $\mathcal{S}\subset\mathbb{R}^n$, find a function $g(.)$, so that $s=g(x_1,…,x_r)$, $x_i\in\mathbb{R},r\leq n$, for each $s\in\mathcal{S}$

Thank you in advance for your help. I am trying to fight with a technical issue that I do not really know how to prove. I have a set of $n$ sensors that provide me with $n$ measurements –not ...
14 views

### Minimum number of nodes perfect binary tree

definition of perfect binary is "which all internal nodes have two children and all leaves are at same level" perfect binary tree i know max. node number: 2^h - 1 (h>=1) but i cant figure out, ...
23 views

### A undirected weighted graphh as a unique minimum spanning tree name an example. Answer included, but I don't understand

-1 Question: Give an example of a undirected, weighted graph that has two edges of equal weight, for which there is still a unique minimum spanning tree. There are many examples of such a graph. As a ...
15 views

### Is it possible to generate two dimensional Pareto distributed data with python?

I would like to generate 2D random data, which is Pareto distributed. a, m = 30., 2. # Shape and mode s = (np.random.pareto(a,1000) + 1) * m I am using the ...
58 views

### Topological Invariance in Data Structures

I need to do a PhD in Pure Mathematics and I am thinking of Topological Data Analysis. I want to use persistent homology and quiver representation to obtain topological features in data structures. ...
23 views

### Is the Hamming distance sensitive to sequence of bits?

Two binary strings ($110$) and ($100$) have a hamming distance of $1$, similarly ($110$) and ($111$) also have hamming distance $1$. Hamming distance is not sensitive to the sequence of bits. Is there ...
14 views

### how to generate variates from a particular categorical binary data?

So im working with more than 100 thousand samples dota2 dataset which consist of the winner and the "hero" composition from each match. I was trying to build winner of the match prediction model ...
36 views

### Generating a synthetic dataset

I want to generate a synthetic dataset for a simple method that estimates the uncertainty in regression using a neural network. The dataset is generated by sampling the following function with in the ...
72 views

### Distributivity of projection in relational algebra

Does a projection distribute over set difference in relational algebra: in other words does$$\Pi_a (A-B) = \Pi_aA - \Pi_aB$$ where projection is defined as projecting to a subset of attributes from ...
19 views

### What metrics can be used to describe the clustering of a group of points?

Consider a set of points $\Omega \subset \mathbb{R}^n$ (to make it simple, consider $n=2$). So you basically have a bunch of points on a plane. I need to find good metrics that can describe the ...
43 views

### What data structure does Graph Isomorphism Problem assume?

In Haskell, I can easily think of a data structure of quasi-labeled simple graphs: ...
31 views

### Find out order of two permutations

Consider we have two different permutations of the numbers in this set: $\{1,2,...,n\}$ In each question we can ask about the order of two numbers in each of these permutations, for example if we ask ...
15 views

### Creating a numeric index for a set

$Let \ S_0 = { (A), (B), (C), (D), (E) }$ From this, if we generate sets of permutations that do not contain duplicate elements, we get: $S_1 = {(AB), (AC), (AD),(AE),(BC),(BD),(BE),(CD),(CE),(DE)}$ ...
67 views

### Is it possible to invent a sorting algorithm for less than O(n)?

Currently for a large randomly generated array of elements lets say array of int can be sorted within O(n logn). Is it possible to invent a sorting algorithm for <...
29 views

271 views

### Time Complexity Of Binary Tree Subtree Algorithm

Given two binary trees, check whether one is a subtree of another one. This is my algorithm. Basically, it says: For two binary trees A and B, A is a subtree of B if they are the same tree. If ...
97 views

### Array based resizable Stack and Queue implementation

The task is to write Stack and Queue implementation based on resizable array. There are two requirements: 1) At any step capacity of array is O(current size of array) 2) amortized complexity of pop ...
46 views

### Graph data structure selection

I need to implement an algorithm that works on planar graphs and I want to select an appropriate data structure to represent them. The vertices are stored in an array, each with an associated pair of ...
432 views

### generating all possible k partition of an array

actually, I confronted a problem for generating all possible k partitions of an array. I tried to write the algorithm but actually, I am not able to. can anybody please give me the idea, how to code ...
129 views

### polynomial representation of binary in computer memory and its efficiency

I have noticed that in some cases 'polynomial representation' of a number is the preferred method to represent numbers in computer programs, especially those involving modular arithmetic and ...
115 views

### Are there standards for how to structure 4D vector math?

This is a somewhat subjective question, but I am also asking if there are a standards. This question is about the general math but some of it is in the context of computer programming. Some specific ...
26 views

### In Depth Treatment of 1-D Adaptive Mesh Refinement Analytics and Implementation

I am looking for a good resource for implementing adaptive mesh refinement (AMR) on a 1-D PDE and an analytical treatment. Pretty much everything I've found on AMR use 1-D as a toy example to show the ...
146 views

### Find K Closest pairs in a spatial database (Without specific query object)

Input: • N points {P1, …. , Pn} - each point is from the same dimension t: Pi = {x_1, …., x_t} where k is between 18-30 . • Distance function – dist(Pi, Pj) - returns a number that is the distance ...
71 views

### How do you define in particular a linked list in abstract type theory? Or would you even do that?

I understand somewhat how abstract List is defined. But still not 100%. Type theory literature is not that great yet. I want to know how to build basic data ...