The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
1answer
79 views

Structural induction over list

I want to prove that unique(reverse(L)) = reverse(unique(L)) where L is a List. List has the following constructors: ...
-1
votes
1answer
45 views

Operation with same asymptotic cost on hash tables and lists [closed]

Let $x \in \{ \log n, n, \dots , n!\}$ some (cost) function. Are there interesting operations with runtime in $O(x)$ on lists which also have runtime in $O(x)$ on hash tables?
0
votes
1answer
42 views

How to write all $r$-tuples with a certain property in a list [closed]

I have the following question: Let $a,b,c,d$ be four natural numbers with $a \leq b$ and $c\leq d$. I have written a program that produces a list, which has as entries all 2-tuples $(x,y)$ with ...
4
votes
3answers
142 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 ...
3
votes
1answer
84 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 ...
0
votes
1answer
29 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: ...
2
votes
2answers
175 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 ...
4
votes
2answers
218 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 ...
-1
votes
2answers
69 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, ...
2
votes
1answer
136 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 ...
2
votes
0answers
79 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 ...
5
votes
2answers
117 views

Longest subsequence such that A[i].x < A[i+1].y

I have an issue for which I am looking for an algorithm (if it exists) What I have: An array of items which have certain properties, e.g. item $A$ has properties $x$ and $y$. Example: $[ A(x,y), ...
6
votes
1answer
69 views

Is there a term for the general method used in XORed linked list?

The XOR linked list is perhaps the most prominent example of storing a reversible hash of two values and using a known value and the stored hash value to derive the other value. Is there a term for ...
3
votes
1answer
2k views

Constructing of Double Connected Edge List (DCEL)

For a given planar graph $G(V,E)$ embedded in the plane, defined by list of segments $E= \left \{ e_1,...,e_m \right \} $, each segment $e_i$ is represented by its endpoints $\left \{ L_i,R_i ...
4
votes
1answer
349 views

Building ideal skip lists

I'm trying to find the best algorithm for converting an “ordinary” linked list into an “ideal" skip list. The definition of an “ideal skip list” is that in the first level we'll have all the ...
4
votes
3answers
5k views

Quicksort vs. insertion sort on linked list: performance

I have written a program to sort Linked Lists and I noticed that my insertion sort works much better than my quicksort algorithm. Does anyone have any idea why this is? Insertion sort has a ...