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.

Filter by
Sorted by
Tagged with
0
votes
0answers
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&...
0
votes
0answers
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)$ ...
0
votes
0answers
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 ...
0
votes
0answers
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, ...
0
votes
1answer
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) ...
1
vote
1answer
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?
0
votes
0answers
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 ...
1
vote
0answers
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, ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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. ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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: ...
0
votes
1answer
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 ...
0
votes
0answers
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)}$ ...
0
votes
1answer
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 <...
3
votes
1answer
29 views

How to represent subset using 5-bit binary code?

For the set $V=\{a, e, i, o, u\}$, give the $5$-bit binary string that codes each of the following subsets: $\{a, i,o\}; \{e\}; V; \emptyset$; Which subset is represented by the $5$-bit string $...
0
votes
0answers
47 views

Directed Acyclic Graph (DAG) - longest path

I'm currently solving an exercise in which I've to show that any longest path in a nonempty forest (DAG) connects two different leaves of this forest. How do I show it in generally? We've had it in ...
0
votes
1answer
40 views

Recurrence $T(n) = T(\sqrt{n}) + \Theta(\log_2\log_2n) $

I want to solve the recurrence with iterative Method, but I don't know how to finish it. This is the last thing I solved, but how can I continue? $$T(n) = T(n^{1/2^i}) + \displaystyle\sum_{i=1}^{\...
0
votes
0answers
18 views

How to solve this recursive equation with induction?

Let $m$ be a natural number ($m>1$). Solve this recursive equation with induction method: $T(n)=m T(\frac n m)+O(n)$ actually, by Master's theorem, we get that we should prove $T(n)=O(n\log n)$ ...
0
votes
1answer
10 views

Ordering algorithm for datastructure with single update.

So I have a datastructure - a sort of List type - that needs to be ordered. When the order is set the elements know what comes before and after them. When objects ...
1
vote
1answer
29 views

Amortized analysis for datastructures having early high cost and then low cost

When reading about the accounting method of amortized analysis, it was mentioned that the bank balance cannot go negative. But what if I have some data structure (DS) which takes initial high cost and ...
0
votes
0answers
28 views

Big O proofing, need explanation on how to get the answer.

I have spent the whole day trying to understand Big O but I'm still confused. Hopefully someone can enlighten me. I have an example: $100𝑛+5∈𝑂(𝑛^2)$ [so i know $100n+5$ is Big O of $n^2$] [the ...
3
votes
1answer
146 views

Finding number of pairs of vertices in a graph such that the path between them has only one vertex common with a different given path

Given a tree with N vertices and N-1 undirected edges. 1<=N<=250000 There are certain queries to be performed. 1<=Q<=10^5 In each query we will be given two vertices,say a and b. We have ...
0
votes
1answer
68 views

Universal hashing family

I'm not really sure this question is proper for MathExchange but I have found it more suitable than StackOverFlow. So, I'm taking the course of Data Structures and Algorithms and we got some example ...
0
votes
1answer
231 views

Binary Tree interal nodes+leaves proof

Let us define the length of the inner path of a binary tree to be the sum of the depths of all internal nodes in the tree , Let us define the length of the outer path of the binary tree to be the ...
2
votes
1answer
60 views

sequence of $n$ Union-Find-operations: determine the minimum number of children in one tree with root $v$.

We have Union-Find-Structure consists of $n$ trees, which have exactly one element. Let $\sigma$ be a sequence of Union-Find-operations, so that all $n$ elements are in one tree with root $v$. ...
-2
votes
1answer
2k views

Divide an array into k-subarrays [closed]

Given an array A of size n <= 50, we have to divide it into k consecutive subarrays (k < n). The value of each subarray will be equal to the sum of elements in that subarray. Suppose the value ...
0
votes
0answers
48 views

Fibonacci Workings

The Fibonacci number sequence is given by $$F_n = F_{n−1} + F_{n−2},\ n \ge 2,\\F_0 = F_1 = 1$$ Suppose we write two consecutive Fibonacci numbers in the form of a $2 \times 1$ matrix $f$, where $$ ...
0
votes
0answers
30 views

Algorithms and Data Structures

I just started Masters on a different school than my bachelor degree and since Advanced algorithms is a compulsory subject and I never had Algo. for beginners, Im taking a bachelers level algorithms ...
2
votes
1answer
296 views

How to prove that total number of non-isomorphic labelled trees of order $n$ is $n^{n-2}$?

I predicted the formula by finding total number of non-isomorphic labelled trees of order 1 is 1 , order 2 is 1,order 3 is 3,order 4 is 16,order 5 is 125.But how do i prove it ? I am beginner in graph ...
2
votes
1answer
49 views

How to encode a line of points so you can connect long distances using short lines

So this is mostly a computer problem but this aspect is really math heavy and could probably be easily solved with some math insight so I thought I'd ask here. It might seem a little computery at ...
0
votes
0answers
30 views

Producing a range of 0-100 based on multiple variables with different units (percent, numerical)

I'm absolutely no statistics wizard and it is my first post here, so I hope you bear with me. I'm working in Excel on a project where I need to convert data from a number of variables into a "one ...
3
votes
1answer
381 views

Sort an array given the number of inversions

Given an array $A$ with $n$ integers in it, one way of measuring the distance of the array from a sorted array is by counting inversions. A pair of indices $i,j ∈ {0,...,n−1}$ is called an inversion ...
1
vote
1answer
35 views

Data transformation: new min, max and mean

I have a dataset of 31 values, of which the $min = -0,8,\ max = 11, 1$ and $mean = 5,0$. Is there a way to transform these data to a $\text{new} \ minimum (0.3), \ \text{new} \ maximum (11.4)$ and $...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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 ...
2
votes
0answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
50 views

Would this suffice in a visual type theory to define an abstract List type?

See the image. I got that from: wikipedia article. In that, I don't understand the first function nil : () -> L. What is ()...
0
votes
0answers
34 views

How to formulate the mth value of this question directly,

Well I had this question and i solved it using a computer program and i was wondering could this be done using maths directly as that would run faster(O(1) for those who know time complexity). ...