## Fifth assignment marked

sewe
Sonntagsinformatiker
Beiträge: 295
Registriert: 16. Jan 2009 14:53
Kontaktdaten:

### Fifth assignment marked

I just finished marking the fifth assignment. (I also put the model solution for it online.)

BTW, a surprisingly large number of people produced versions of merge and distinct that do work when combined to combine2. But let's discuss this on Friday.

z33ky
Neuling
Beiträge: 7
Registriert: 17. Apr 2012 20:29

### Re: Fifth assignment marked

The uploaded solution implements a distict that cannot properly handle finite lists (pattern matching fails with lists of size <= 1).
I would argue that "potentially infinite" does not mean guaranteed infinity.

And the algorithmic complexity of comb235 was not stated, although part of the Task description is "What is the algorithmic complexity of this computation?".

sewe
Sonntagsinformatiker
Beiträge: 295
Registriert: 16. Jan 2009 14:53
Kontaktdaten:

### Re: Fifth assignment marked

z33ky hat geschrieben:The uploaded solution implements a distict that cannot properly handle finite lists (pattern matching fails with lists of size <= 1).
I would argue that "potentially infinite" does not mean guaranteed infinity.
Thanks for pointing this out. The base cases are indeed missing (and not required for the rest of the tasks). I'll update the solution.
z33ky hat geschrieben:And the algorithmic complexity of comb235 was not stated, although part of the Task description is "What is the algorithmic complexity of this computation?".
It's O(n). For each element of comb235 you can get up to three calls to multLst and up to two calls to combine, which in turn call distinct and merge. Of these calls, only distinct has the potential to recurse multiple times without outputting a new list element (the x == y = distinct (y:xs) case), but this cannot happen more than once, as the "mult-lists" each have a different factor; even if the first elements of, e.g., [6,8,10, ...] (from multLst 2) and [6,9,12, ...] (from multLst 3) are equal, the second elements are not.

sewe
Sonntagsinformatiker
Beiträge: 295
Registriert: 16. Jan 2009 14:53
Kontaktdaten:

### Re: Fifth assignment marked

sewe hat geschrieben:It's O(n). For each element of comb235 you can get up to three calls to multLst and up to two calls to combine, which in turn call distinct and merge. Of these calls, only distinct has the potential to recurse multiple times without outputting a new list element (the x == y = distinct (y:xs) case), but this cannot happen more than once, as the "mult-lists" each have a different factor; even if the first elements of, e.g., [6,8,10, ...] (from multLst 2) and [6,9,12, ...] (from multLst 3) are equal, the second elements are not.
D'oh! This explanation is actually for using combine2 (did this "wrong" in the exercise class today too). For combine, it is even easier: combine produces exactly one element/call.