# Tagged Questions

The tag has no usage guidance.

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 ...
77 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 ...
89 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 ...
25 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: ...
89 views

### How do I interpret this divide and conquer algorithm for removing duplicates in a list?

Consider the following divide and conquer algorithm to remove duplicates in a list. The text is in French. What is the meaning of the variables $c1, c2, d1, d2$? Why are only the variables $c1, d1$ ...
31 views

151 views

### counting arithmetic progressions $a, a+r, a+2r$ in a list

I have a large list $L$ of numbers and I need to count instances of elements $a,b,c \in L$ such that $a +c = 2b$. A brute-force approach would be to check all possible triples $(a,b,c)$ and this will ...
113 views

### Finding number not in list with wildcards

I have a list like this: 1*0*0 1**0* 0*0** 001** Where the number of elements in each row is $n$ and * is a wildcard for 0 or 1. I need a polynomial-time ...
35 views

### Join large list of pairs

I have a list of millions of pairs of strings, and I want to join all of the pairs that have matching members into lists without duplicates. Example input: ...
205 views

### Lazy lists with call-by-value reduction strategy

I am currently writing lists with lazy semantics in the pure lambda-calculus with call-by-value reduction strategy. I tried to construct pleasant to use and relatively efficient "lazy" functions on ...
407 views

### More efficient algorithm for determining if one list is a sublist of another list

I'm trying to build an algorithm which takes two lists of natural numbers and finds if every element of the first list is displayed at least once in the second list. What if the list is sorted? An ...
80 views

### Counting occurrences of one vector inside another

I am asked to check if a vector contains another vector as a subvector. For example: $$v_1 = (4, \underline{3, 4}, 9, 10, 28, 5, 12, \underline{3, 4})$$ $$v_2 = (3, 4)$$ The answer here will be two, ...
222 views

### Skip lists with limited height

This is homework, so please only hints. I didn't want to put this on StackOverflow since this is mostly about theory, and SO gets inundated with too many questions. I am asked to find a method of ...
80 views

### Does a function distribute over lists or does it commute with them?

Assume that we have an operation $f$ such that $$f([a_0,\ldots, a_n])= [f(a_0),\ldots,f(a_n)]$$ Do we say that $f$ distributes over lits or do we say it commutes with lists? Which one is the ...
126 views