# Tagged Questions

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

39 views

### What is the complexity of Array[n] and Object.value

I faced a great doubt about the Complexity of two ways of calling a information. First I have an Array, if I call an array in a program like this: print array[0] ...
28 views

### The c++ code says file cannot be opened. Can anyone tell me whats wrong in my code? [on hold]

Question: Write a program that reads students’ names followed by their test scores. The program should output each students’ name followed by the test scores and relevant grade. It should also find ...
13 views

### What's the intuition behind the update operation of the binary index tree? [duplicate]

There are many tutorials on binary index tree on the Internet, for the update operation, they all find the the next node of node i to update by ...
52 views

### Understanding Chazelle's bin packing algorithm

I'm having trouble understanding Chazelle's algorithm ,which is discussed in this paper The bottom-left bin-packing heuristic: an efficient implementation by B. Chazelle (1983), especially in ...
11 views

### what is the Time complexity of matrix multiplication? and how can it be determined? [closed]

I tried to obtain it from a program. It gave me a graph whose equation is in exponential form.
35 views

### What do you call a “non-probabilistic Bloom Filter”?

One of my coworkers came up with a nice technique to solve a problem and I feel like it must already have a name. I just don't don't know how to figure out what it is. It is a technique for caching ...
74 views

### When used as call stack, do garbage-free spaghetti stacks form a DAG?

I'm looking into implementation techniques for programming languages, and recently came across spaghetti stacks, which are supposedly a good fit for a continuation passing style model (given their use ...
39 views

### Is FKS hashing really linear space?

In FKS hashing, I wonder if the size of the table $G[ 1..n]$ (used to record the functions $g_i$ which is chosen randomly; one entry per bucket) is really strictly $O(n)$. Given that the probability ...
115 views

### Why hasn't functional programming researched dynamic trees?

By dynamic trees I am referring the definition stated in Sleator & Tarjan's paper "A data structure for dynamic trees" in 1983. Since then, few efforts have been done in the functional programming ...
34 views

### Shifting deletion algorithm for linear-probing hash table

I'm looking for the algorithm for deleting an element from a linear-probing hash table that does a delete-and-shift instead of just using tombstone elements. The basic idea is quite simple - but I ...
33 views

### Constructing binary search tree from given data

The data are in alphabets. U, N, I, V, E, R, S, I, T, Y, O, F, P, O, K, H, A, R, A. Perform pre, in and post order traversals. I'm confused as how to construct it in the 1st place. Only sense i ...
64 views

### Why do you need to fill the first element of array when implementing heap?

I'm looking at Heap data structure implementation from different sources. What I found is that sometimes it's implemented with the first element of array set to magic (default, unused?) value. For ...
44 views

### Are there data structures that mix a tree structure with lists?

I suppose something like this could probably be easily designed, however I was wondering if there's a data structure that somehow uses both list and tree to access data. Something like this (I'll be ...
235 views

### Large non-array data structure to describe order of elements

I'm looking to store the order of a series of elements and access the elements in "pages" (elements numbered 101-150, for example) as well as add and delete them. This is being implemented in a graph ...
54 views

### Amortised analysis of binary heap insert and delete-min

I'm trying to figure out how to do amortised analysis of heap insert and heap delete-min using potential function. We can assume, that insert is O(logn) and delete-min is O(logn) too. The goal is ...
69 views

### Correct way to implement linked list

I'm doing this challenge on Hacker Rank that wants me to implement a linked list. It seems to want me to find the last-added instance of node and change its head to link to my new instance of node. ...
70 views

### Zero-based array implementation with logarithmic insertion time

Normal zero-based arrays (ie not those with a sort order) have constant lookup time, but linear insertion time. For a specific problem I was musing about a balanced tree that would allow for an zero-...