Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
9 views

Functor to represent directed acyclic graphs for (co)induction

The general theory of induction and coinduction is usually presented in terms of initial algebras and finial coalgebras for certain endofunctors (monads) on the category of sets. (See for example ...
-2
votes
1answer
49 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
36 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
15 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 ...
3
votes
1answer
48 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
42 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
15 views

Time Complexity of Building Heap

The Question is as given above. In this answer: https://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity, I note that the building a heap is already O(n) complexity, ...
0
votes
0answers
10 views

Calculating maximum number of splits that can occur during insertion of $n$ keys in B Tree of order $m$

(I dont know if this question is valid candidate for math.stackexchange, but puttin it anyway as I believe this might require maths expertise) I can calculate this by trying out manually inserting $n$...
0
votes
0answers
26 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 ...
0
votes
0answers
24 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$ ...
3
votes
1answer
106 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
28 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
63 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
36 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
30 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
128 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 ...
0
votes
0answers
24 views

What is the min/max number of leaves/non-leave nodes in B+ tree?

Let $n=100$ be the order of a B+ tree which is represents $10^4$ unique values (e.g. primary keys in a database). What is the minimum and maximum number of leaves and non-leave nodes in the tree? ...
2
votes
0answers
80 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
43 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
25 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
50 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
65 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
47 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
35 views

Does Magma with identity (unital magma) form list structure?

It's sort of famous that Monoids form Lists. It seems to me that Magma with identity (unital magma) also form list structure. Am I correct? Any additional instruction is most grateful.
0
votes
0answers
32 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). ...
0
votes
0answers
15 views

Detection of functional structures

I am already doing some research and just can not make headway and hope that some math experts can help me. I would like to detect the mathematical structure on the basis of a data set, for example, ...
0
votes
1answer
113 views

matrix columns represented by binary search tree

I've been reading this paper on the persistence algorithm: https://people.mpi-inf.mpg.de/~mkerber/ck-phcwat-11.pdf Given a matrix M with columns $M_j$. it states on page 3 that we may add two ...
0
votes
1answer
30 views

Set in an algebra of a data structure

For an algebra of a data structure, I want to define a set: A parliament consists of at least 600 members. Each member has a name and belongs to a party. The name of a member must not occur more than ...
0
votes
0answers
12 views

What is a suitable index to express similarity in two observations of the same set of variables containing ratios?

Is there an index that would express any kind of similarity between the values in the same variable sets of two observations, for example the distribution of energy-sources of two countries. I work ...
1
vote
0answers
39 views

proof 0 (f (n)) = 0 (g(n)) if and only if f (n) E 0 (g(n)) and g(n) E O (f (n))

The problem : For arbitrary functions f and g : IN -> IR*, prove that O(f (n)) = O(g(n)) if and only if f ( n ) ∈ O ( g ( n ) ) and g ( n ) &#...
0
votes
1answer
40 views

Given two arrays A1,A2, return if for a given X , there is a pair of ai∈Ai such that a1+a2=X (𝑂(n log(𝑛)))

The question is fairly easy to understand, the problem is i need the algorithm running time to be 𝑂(n log(𝑛)), which i couldn't achieve. Given two arrays with positive integers,lets call them A1,...
1
vote
2answers
66 views

Prove Statement with Asymptotic Notation

The questions is to prove or disprove $n!=O(n^n)$ Using the definitions of big O, I consider: $n!<=n^n$ Using induction I get: $P(1): 1<=1$ $P(k+1): (k+1)!<=(k+1)^{k+1}$ Then moving ...
0
votes
1answer
208 views

Implementing a function with 3x8 decoder and a minimal number of logical gates

so I've got this question that I'm stuck on for a very long time and help would be really appreciated! It goes like this: Implement the function: f(a,b,c,d)=∑(0,1,3,4,8,9,15) with a 3x8 decoder and ...
0
votes
0answers
18 views

Interpreting order of magnitude correctly?

Given this data table: The lowest value: $79.3$ And the highest value: $1.27\times10^9$ If so, why would there be zero before the power? Such as $e+009$. That notation was a bit confusing.
0
votes
1answer
259 views

Show that $\sum \limits_{i=1}^n $ log(i) = Θ(n log n) [duplicate]

I need to prove or disprove: I start with the Big O notation: $\sum \limits_{i=1}^n $ log(i) = Θ(n log n) $\sum$ log i ≤ $\sum$ log n = n log n (dont know if this is enough or not)
2
votes
0answers
85 views

Containing intervals

I need to come up with a linear time algorithm for the following problem: "You are given an input array containing n intervals whose endpoints are distinct integers between 1 and 10n. Each interval ...
0
votes
0answers
58 views

What is a complexity of a doubly-connected edge list?

What is a complexity of a doubly-connected edge list? Is it a number of half edges plus the number of the faces plus the number of the vertices?
2
votes
1answer
131 views

Why is it enough for a vertex in a doubly connected edge list to store only one half edge for which the vertex is an origin?

Why is it enough for a vertex in a doubly connected edge list to store only one half edge for which the vertex is an origin? How could we find all incident edges having only that one half edge with ...
2
votes
0answers
70 views

How to interpret the zipper of a set?

A set with elements of type $a$ typically is represented in type theory by $Set \ a: a \to bool$ or, as an algebraic expression $Set \ a: 2^a$. The idea is that, for each element of the type $a$, you ...
1
vote
0answers
77 views

A Special Tree decomposition

Given an undirected tree $G=(V,E)$, I want to decompose the tree into several subtrees. Let's denote the size of $i$th subtree by $|v_i| \, \forall \, i \in {1,2,...n}$. Note that the resulted ...
1
vote
0answers
57 views

Black red tree - creating a node with at most one child

Let's assume I have a black red tree with integers values, for which I know the values of the nodes, but not the topology of the tree. I can insert new numbers into the tree, but cannot insert ...
0
votes
2answers
2k views

Black Depth in Red-black Tree?

Wikipedia's Red-black tree states the last property of a Red-black tree: Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes. Some definitions: ...