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.
Questions tagged [data-structure]
145 questions
1
vote
1 answer
How can i prove for all $k$, $n^k = \mathcal{O}(2^n)$?
the problem is to prove that for all natural $k$, $n^k=\mathcal{O}(2^n)$
Ive tried induction but i dont think i solved it right (found different C for the base and the step), i also saw this post:How to prove that $n^k = O(2^n)$
but i want to solve…
Lightbolt
- 11
1
vote
1 answer
Looking for formulas to create a virtual binary tree from a simple list with an incremental index
I have a task to make data structure like a binary tree (pic. 1).
Where each node has only two child nodes, for each node I should may get its nesting level, and for every two nodes, I can get the distance between them vertically. new nodes inserts…
1
vote
0 answers
Can these coin-toss-game strategies be described efficiently?
Consider a game with three players where each player starts with $100$ tokens and a (possibly unfair) coin.
In turns, a player decides how many of her tokens she puts on Heads. Her other tokens will be put on Tails. Her coin is then flipped and she…
Albert Hendriks
- 333
1
vote
1 answer
Asymptotically, can supercomputers easily solve the Travelling Salesman Problem, why or why not?
I just want to know if supercomputers could easily solve the TSMP or would still take a lot of time, as it does now?
rpj
- 37
0
votes
2 answers
When converting from base10 to base5 data representation, how do I deal with floating point numbers?
(Note: This question was originally on StackOverflow. I was recommended to ask here instead.)
In regards to data representation, I am bit confused at how I would go about dealing with floating point numbers when manually converting between…
0
votes
1 answer
are my answers to master theorm true?
I'm trying to solve two problems with Master theorem (quoted at the end of this post). I have solved them and found some answers, but I'm not sure whether my answers are right or not. Can you please check my answers and if they have any problem,…
anita
- 33
0
votes
1 answer
Bloom Filters : Reduced number of bits
How can a bloom filter that uses m bits be reduced into a bloom filter with (m-1) bits, without using the whole dictionary? I've been stuck on this question for a long time and any help would be appreciated.
Srivatsav Palli
- 3
- 2
0
votes
0 answers
Optimising data blocks - The IKEA packaging dilemma
In my system (for info - written in C#) there are the following concepts:
Data Blocks: An array of bytes
Groups of Data Blocks: A list containing mutiple Data blocks
They can be many Data Blocks (1000's) of various sizes. The max size allowed…
0
votes
1 answer
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 are removed from the list, the list isn't updated, the object that is removed just…
Mihkel L.
- 131