Questions tagged [lists]
The lists tag has no usage guidance.
84
questions
1
vote
3
answers
66
views
Can there exist a deque like data structure that supports amortized $O(1)$ random access?
A lot of modern languages usually have a "list" or "vector" structure which allows for amortized $O(1)$ append and removal from back as well as amortized $O(1)$ random access.
I'm ...
- 375
1
vote
1
answer
40
views
Linear time alg for checking if numbers in a list are close
Suppose we have an unsorted list of $n$ integers. What is the best algorithm we could use to detect if there exists a pair of ints that are 'close' to each other. Close being within some arbitrary int ...
- 113
0
votes
0
answers
13
views
Keeping in a list a list of recent insertions/removal to/from a list of lists
I have a list of lists T.
I stress test my database software by randomly adding and removing sublists and elements of sublists to/from T and from/to my database. (After this I compare T with the ...
- 503
0
votes
1
answer
37
views
Logic for Computer Science - How to define msort, merge and split functions inductively?
In "Modelling Computing Systems: Mathematics for Computer Science", I came across a logic exercise to inductively define a merge sort function 'mergeSort', with a hint to first define ...
1
vote
0
answers
37
views
What is the literature implementation of self-organizing lists?
I'm trying to implement self-organizing lists DS to publish as a public module. Over the course of Algorithms, we learnt that if you add a new element to the list, it should still do the huriectics. ...
- 223
-1
votes
1
answer
139
views
Efficiently sorting a list of integers depending on the index of said integers in a second list
Introduction
Hi everyone,
I am currently pondering how to efficiently design an algorithm for a sorting problem and hope that someone here may help me out a bit.
The problem
I have two lists of ...
5
votes
0
answers
265
views
Prove: Self-organizing list that uses Move-to-Front is 2-Competitive
Preparing for my finals in my "advances algorithms" course. Usually there is a question to prove one of the theorems that was given over the course. I'm currently trying to write a full ...
- 223
0
votes
0
answers
120
views
Design a data-structure $BankAccount$ that supports the following operations in constant time complexity
Problem:
Design a data-structure $BankAccount$ that supports the following operations in $ \underline{\text{constant time complexity}} $. Meaning $O(1) $.
$Init()$ - initializes bank account $L$ with ...
- 233
1
vote
1
answer
40
views
Why doesn't this implementation of Skip List simply return the current node when its key is equal to the query key?
I was studying Skip Lists in section 3.10 of Advanced Data Structures by Peter Brass and was confused about a detail of how the search algorithm in implemented. (This is self-study, not homework).
The ...
1
vote
0
answers
27
views
Finding max values at a point given a list of ranges
In coding competitions I usually see problems that involve dealing with values in given ranges. A typical example is, given a list of 3-tuples defined as so
...
- 111
4
votes
2
answers
252
views
Is there another type of list than arraylist and linked-list?
My question is not about how arraylists or linked-lists work, but why there aren't other types of lists.
From my understanding, memory is accessed linearly by adresses. Thus, you have the choice to ...
- 185
1
vote
1
answer
58
views
Position in the Linked-list
I am reading Data Structures and Algorithms by Alfred Aho, Jeffrey Ullman, et al. In the section about lists it's said:
We should note that a position in a linked-list implementation of a list ...
user127304
0
votes
3
answers
394
views
What do you call a data structure containing multiple lists?
I was thinking about a data structure to make concatenation of lists easier, something that contains multiple lists (in a sequence) internally, but can be treated as a single contiguous list. I know ...
- 103
1
vote
2
answers
121
views
A silly doubt on Computer Science Objects: Arrays, Lists, Strings, and Vectors, are they the same concept?
First of all I'm a Physics Student and I've been arguing with my brother concerning the usage and the fundamental meaning of a vector on Computer Science (CS).
I) Vectors
A vector have a axiomatic ...
- 141
1
vote
1
answer
3k
views
What is the difference between python list and c++ vector?
I read about the similarities between the python list and c++ vector and it looks as if the only difference is python list is heterogeneous. Are there any other differences? How are they both ...
- 155
1
vote
1
answer
49
views
What is the theoretical result of flattening a list containing only itself?
Consider the following python code
X = [None]
X[0] = X
This has many fun properties such as
X[0] == X
and
...
- 11
2
votes
1
answer
21
views
Generate slice that contains element
Suppose I have the array:
[2, 3, 4, 5, 6, 7, 8, 9]
Now based on few parameters:
current_item - currently selected item.
<...
- 123
1
vote
2
answers
75
views
What is the name of the data structure that is a tree on the backend but has a list like API?
I'm looking for the name of a data structure. It is organized like a balanced tree. The elements need not be comparable. Instead of asking if the tree contains a thing (like you would with a ...
- 516
1
vote
1
answer
67
views
Historical examples of bad security policies/mechanisms that we got stuck with through switching costs?
The following process seems to be a recurring one:
Initial design. Commercial organisations invent and implement a design that seems at the time to work.
Problem discovered, new design suggested. Due ...
- 4,072
1
vote
2
answers
587
views
Sorting a large list of test scores
You have a large list (say N > 10000) of test scores which you would like to sort. The test scores are between 1 and 100. What is quickest way to sort the list?
First thought. We have a O(N log N) ...
- 143
1
vote
1
answer
883
views
Difference between a skiplist and an Indexable skiplist
Can someone please help me understand the main differences between a simple skiplist and an indexable skiplist? How does an indexable skiplist work in comparison to a normal skiplist (maybe a little ...
- 11
3
votes
2
answers
199
views
Minimizing the iterative sum of pairs of numbers in a list
Given the tuple (list, value):
$$\left(\left[x_1, x_2, \cdots x_n\right], y\right)$$
You may choose two adjacent values in the list to modify the tuple as:
$$\left(\left[x_1, x_2, \cdots x_{i-1}, (...
- 133
0
votes
1
answer
126
views
Lazy streams and infinite series
I just started Unix System Programming with Standard ML and starting on page 22 Shipman begins to explain a pure functional way of avoiding the constant state changes of typing at a keyboard:
A ...
- 131
1
vote
1
answer
91
views
What is an array that can be iterated circularly an infinite amount of times called?
I have a feeling that the answer is either a "circular linked list" or a finite state machine, but the answer is probably a circular linked list.
- 145
5
votes
3
answers
530
views
The origin of list data structure
Does anyone know when the list data structure was mentioned in computer programming/algorithms? Who gave birth to this list concept?
- 153
1
vote
2
answers
149
views
Lexicographic permutation list
Does anyone have an algorithm for stepping through all permutations of n given arbitrary objects in lexicographic order?
Thanks.
2
votes
1
answer
4k
views
How to best maintain a sorted list from a stream of integers?
If I have an incoming stream of integers how can I best maintain a sorted list of them? The only way I can think of is to binary search for the position and shifting the remaining elements to the ...
- 153
1
vote
2
answers
903
views
Algorithm/data structure to quickly check if an integer is a member of any [lower, upper] interval
Are there any existing algorithms/strategies to test if an integer value is within the bounds of any of a list of intervals, where each interval is denoted by a [min, max] pair?
The naive approach is ...
- 163
0
votes
1
answer
463
views
Parallel Algorithm for Data Averaging
I am trying to write an efficient Parallelised algorithm for Data Averaging. By this I mean I have a list of tuples (K, V1, V2, V3) and in the end, I want a dictionary mapping K to the average of all ...
7
votes
2
answers
625
views
Can a list with $\mathcal{O}(1)$ access have an insertion complexity better than $\mathcal{O}(n)$?
It seems intuitive that there's no list data structure which has $\mathcal{O}(1)$ worst case time complexity for random access and a worst case complexity better than $\mathcal{O}(n)$ for insertion: ...
user97294
1
vote
1
answer
2k
views
What is the most efficient algorithm for creating a list of unique values from a list of pairs of value?
Background
I have a list of 50 million $A-A_i$ pairs, where $i>1$, and $A$ and $A_i$ are some text. I need to extract the $A$ values from the list, so I get a new list of unique $A$ values.:
$$
\...
2
votes
0
answers
53
views
Abstract Data Type
I have been studying data structures. In that I have come across topics like Array being defined as Power set of cross product of set of objects and set of natural number and list being defined as ...
- 131
1
vote
1
answer
42
views
Abstract Data Types and their Implementation [closed]
I wanted to know if there is good resource to learn about the ADTs like set ADT, list, array, boolean etc and their implementation.
- 131
1
vote
0
answers
50
views
Terminology Questions: Data-structure consisting of lists without repetitions
I've google around and have been unsuccessful in finding a name for a data-structure consisting of a list whose elements are unique.
I've seen "unique sorted lists", but I'm looking into the more ...
- 894
5
votes
1
answer
618
views
Given a RxC grid, how to generate N 2D points randomly such that no 3 points are collinear?
Context, I have a geometric algorithm that is sensitive to collinear points and receives as input a list of points in 2D generated randomly. Suppose that I have a Boolean function nonCollinear(x,y,z) ...
- 265
4
votes
1
answer
1k
views
Fastest way to search a word in a word list?
I have a word list like "English Open Word List" used to create word games.
The list is in txt file with space between words, like;
aa
aah
aahed
.........and so on.
I want to search it while typing ...
- 43
0
votes
0
answers
42
views
create distance (ment is high difference between values) between Vertexes in a list
Given are some vertexes, arranged in a list (so there every vertex is connected with two others and there are no circles in the graph). Every Vertex contains one number. Now you can lower the Number ...
- 1
0
votes
0
answers
252
views
Big O Notation for Return List is it O(N)?
what is the Big O for Returning List? aka return list (e.g. list=[1,2,...])
is it o(1) or o(n) and is there a good website for average big o for different operations including sorting for simple ...
- 101
1
vote
2
answers
18k
views
Time complexity to check if there is an edge between two nodes in an adjacency list
I know that the time required to check if there exists an edge between two nodes in an adjacency matrix is $O(1)$ because we can access it directly (i.e: $M[i][j]$). However, I didn't really get why ...
- 113
1
vote
2
answers
58
views
How would I go about determining popularity and relevance among articles and use it to improve my search algorithm
Disclaimer:
First of all I've had a lot of trouble finding the right stack exchange site for this question and I don't know if it's correct here either.
The Problem:
I'm working on a search algorithm ...
- 123
0
votes
1
answer
376
views
Remove duplicates of first elements of pairs
A list of pairs is given using Python. I want to remove duplicate occurrences of the first element of the pair leaving only one occurrence of each first element paired with the highest second element ...
- 33
0
votes
0
answers
229
views
List of scheduling problems and their statuses
As of 1993, there are 4536 scheduling problems, 3821 were proven to be $NP$-hard, 417 polynomially solvable, and 298 still open.
Where can I find the most up-to-date list of scheduling problems and ...
- 152
1
vote
1
answer
65
views
Is there a name for the "tree" aproach to listing things?
I've only been studying computer science for a few weeks, so I apologize if this is a silly or naive question.
Suppose we're trying to list all elements of the set $$C(r) = \{(x,y,z) \in \mathbb{N}^3 ...
- 134
1
vote
3
answers
122
views
Partial intersection of 10 sorted lists of integers
Suppose I want to find the numbers that appear in at least 3 of the 10 sorted lists, is there an efficient way to do it apart from iterating over all 10 of them in parallel?
- 171
23
votes
3
answers
44k
views
When are adjacency lists or matrices the better choice?
I was told that we would use a list if the graph is sparse and a matrix if the graph is dense. For me, it's just a raw definition. I don't see much beyond it. Can you clarify when would it be the ...
- 351
2
votes
1
answer
76
views
General name for linked lists based on hashes
I am thinking of a particular datastructure, but don't know the name of it.
A sequence of elements may be modeled by a collection of some X, where each X consists of:
The element, serialized as a ...
2
votes
1
answer
85
views
Expected Time for LookUpSkipList
A skip list
Let C(k) = the expected length of the path that raises k levels backwards.
Thus C(0) = 0
For any node P in the path, with k levels higher to go, there are two cases:
P is a node of ...
- 123
3
votes
2
answers
107
views
Gauss-Jordan using stacks and list
I have a homework assignment in which I need to write an implementation of Gauss-Jordan with complete pivoting. Complete pivoting is a modification to the basic Gauss-Jordan algorithm in which rows ...
4
votes
1
answer
574
views
How to use structural induction to prove law on lists
I want to prove that the following equation holds using structural induction on (finite) lists
...
- 123
3
votes
3
answers
3k
views
Why does linear search have $\frac{n}{2}$ comparisons on average?
I'm reading the Wikipedia page on Linear Search and it is mentioned that there are on average $\frac{n}{2}$ comparisons.
I tried working this out on my own.
First I considered the number of cases. ...
- 155