Questions tagged [lists]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
1answer
36 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 ...
1
vote
1answer
34 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 ...
4
votes
3answers
1k 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. ...
2
votes
1answer
15 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. <...
0
votes
1answer
42 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 ...
1
vote
2answers
49 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 ...
1
vote
2answers
285 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) ...
0
votes
1answer
72 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 ...
3
votes
2answers
238 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?
2
votes
2answers
116 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}, (...
0
votes
1answer
52 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 ...
1
vote
1answer
36 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.
1
vote
2answers
55 views

Lexicographic permutation list

Does anyone have an algorithm for stepping through all permutations of n given arbitrary objects in lexicographic order? Thanks.
1
vote
2answers
128 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 ...
2
votes
1answer
1k 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 ...
0
votes
1answer
102 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 ...
6
votes
2answers
149 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: ...
1
vote
0answers
153 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
0answers
42 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 ...
1
vote
1answer
30 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.
1
vote
0answers
40 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 ...
4
votes
1answer
146 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) ...
0
votes
2answers
8k 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 ...
3
votes
1answer
366 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 ...
0
votes
0answers
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 ...
0
votes
0answers
105 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 ...
16
votes
3answers
27k 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 ...
1
vote
2answers
39 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 ...
0
votes
1answer
102 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 ...
0
votes
0answers
183 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 ...
1
vote
1answer
52 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 ...
2
votes
1answer
63 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 ...
1
vote
3answers
106 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?
2
votes
1answer
75 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 ...
3
votes
2answers
101 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
1answer
412 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 ...
8
votes
4answers
3k views

What's the fastest way to find the Kth smallest value in an unsorted list without sorting?

My initial algorithm: Compare element 0 with every other element, keeping track of how many elements are less than it. Repeat for each element until an element that is greater than exactly (k-1) ...
0
votes
1answer
184 views

Efficiently finding duplicates in lists of numbers

I decided to try my hand at solving the knapsack problem. My idea involved generating $i$ tables, where $i: 1 \le i \lt n$, and each cell of an $i$ table contains one of the possible sums of the ...
3
votes
1answer
2k views

Lambda calculus lists construction explanation

I have the following notes that introduce how lambda calculus handles lists. They go as follows: A list is something we can match on and deconstruct if it is not empty: ...
4
votes
1answer
51 views

Description of lists with functions in LISP

I have been given the following implementation of basic list functions in LISP: ...
1
vote
2answers
5k views

Find out duplicate number between 1 to N numbers

I first saw this question on this website where I was trying on Java puzzles. Here is the Question:- ...
-1
votes
1answer
56 views

Can randomization be proven?

There exists a collection c where c = {1, 2, 3} and a randomization of c, ...
1
vote
0answers
48 views

Fastest way to Add and Subtract multiple parts of a List

I am doing some research where I have a List containing numbers. For example {5,10,98,22,13,15} What is a fast algorithm to calculate all possible sums and ...
5
votes
3answers
5k views

The fastest algorithm for intersection of two sorted lists?

Say that there are two sorted lists: A and B. The number of entries in A and B can vary. (They can be very small/huge. They can be similar to each other/significantly different). What is the known ...
3
votes
1answer
526 views

Skip List randomization complexity

I understand the basics of Skip Lists and their implementation also the basic Search Insert ...
2
votes
2answers
469 views

Find the duplicates in a list of floating point numbers

I receive a list of real numbers ( float ) between $0$ and $1$. The list has length $N+1$ and I need to find two numbers on the list which are $\le \frac{1}{N}$ ...
1
vote
1answer
106 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 ...
1
vote
2answers
208 views

How can I get O(1) prepend on a random-access list?

I need a data structure that has the following operation: $\operatorname{prepend}([x_{n - 1}, ..., x_0], x_n) = [x_n, ..., x_0]$ $\operatorname{prepend}$ should be in $O(1)$. Assume that you have ...
2
votes
0answers
98 views

How do I merge these lists?

I ave a a collection of lists of objects: $a_1$ $a_2$ $a_3$... $b_1$ $b_2$ $b_3$... $c_1$ $c_2$ $c_3$.. I need to merge them into a minimal possible number of lists, each list must be as long as ...
3
votes
1answer
129 views

Algorithm for grouping identical neighbors in a list

I have a list that I want to reduce to a smaller list by grouping identical neighbors. This list has many many redundant entries. Example list: ...