The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
1answer
36 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
127 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
74 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
26 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: ...
4
votes
2answers
135 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
68 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
108 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
73 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 ...
4
votes
2answers
109 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
65 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
320 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
4k 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 ...