2009 May 11 00:00:05 -*- inimino finishes 2.71 2009 May 11 00:02:08 i finished up to 2.67 2009 May 11 00:02:23 which did you go over last time? 2009 May 11 00:04:37 I think we got up to 2.58 last time 2009 May 11 00:06:35 Chris Conley mentioned that he wouldn't be able to make it today since he's travelling 2009 May 11 00:07:15 aamar was in here earlier though, maybe he got disconnected or something 2009 May 11 00:07:54 should we wait a bit? 2009 May 11 00:09:07 I don't mind waiting a few minutes 2009 May 11 00:09:39 cool im working on 2.68 2009 May 11 00:11:05 they dont mention it yet but this is a compressor no? 2009 May 11 00:11:33 yes 2009 May 11 00:14:12 --> aamar (i=cc0e9fb9@gateway/web/ajax/mibbit.com/x-01d4dd85747cf7be) has joined ##SICP 2009 May 11 00:14:23 --> seangrove (n=seangrov@cpe-76-90-50-75.socal.res.rr.com) has joined ##SICP 2009 May 11 00:14:44 <-- meanburrito920_ (n=John@76-217-6-100.lightspeed.irvnca.sbcglobal.net) has quit ("has been attacked by a grue") 2009 May 11 00:14:45 started? 2009 May 11 00:15:40 not yet 2009 May 11 00:15:50 i guess we should start 2009 May 11 00:16:00 ah 2009 May 11 00:16:05 yeah 2009 May 11 00:16:15 let's start 2009 May 11 00:16:27 ok great 2009 May 11 00:16:53 alright, 2.59? 2009 May 11 00:17:09 Exercise 2.59. Implement the union-set operation for the unordered-list representation of sets. 2009 May 11 00:17:17 http://github.com/mariorz/sicp/blob/ac0bc68bbe32d02af9fa90afdeb15bd6c355123c/2.ss#L1234 2009 May 11 00:17:26 http://mibbit.com/pb/X04dwS -- 2.59 2009 May 11 00:17:28 http://inimino.org/~inimino/projects/2009/SICP/chap_2/2.59 2009 May 11 00:17:55 -*- inimino waits for github 2009 May 11 00:18:15 ah yeah its a big download thats going to suck 2009 May 11 00:18:32 should ahve divided by problem 2009 May 11 00:20:28 oh well I guess all the links will be on that page then 2009 May 11 00:20:39 we can just scroll around 2009 May 11 00:20:41 we probably could have done this one by repeatedly calling adjoin-set 2009 May 11 00:20:50 and not calling element-of-set? 2009 May 11 00:21:47 I don't know 2009 May 11 00:21:59 does adjoin-set check for membership? 2009 May 11 00:22:06 yes 2009 May 11 00:22:07 it does 2009 May 11 00:22:33 oh it does 2009 May 11 00:22:44 yeah that should work 2009 May 11 00:22:46 I should have used cons in mine then 2009 May 11 00:22:58 it's inefficient as it is 2009 May 11 00:23:55 or yeah, just with repeated calls to adjoin-set 2009 May 11 00:24:05 that would have meen more elegant 2009 May 11 00:24:08 ok, next one? 2009 May 11 00:24:11 ok 2009 May 11 00:24:18 yes 2009 May 11 00:24:23 http://inimino.org/~inimino/projects/2009/SICP/chap_2/2.60 2009 May 11 00:24:26 so you guys cna just scroll on mine? 2009 May 11 00:24:34 yeah 2009 May 11 00:24:53 yes 2009 May 11 00:25:07 http://mibbit.com/pb/8R6MvH -- 2.60 2009 May 11 00:26:51 ah i forgot not use checking for membership in union-set 2009 May 11 00:27:39 ah 2009 May 11 00:28:23 I didn't take "design procedures" to mean that we had to actually write them 2009 May 11 00:28:42 otherwise seem the same, more or less 2009 May 11 00:29:00 they're pretty trivial anyway 2009 May 11 00:29:05 yes, they seem the same 2009 May 11 00:29:17 yeah, these weren't that hard 2009 May 11 00:29:23 ok, next? 2009 May 11 00:29:47 ok 2009 May 11 00:30:15 http://inimino.org/~inimino/projects/2009/SICP/chap_2/2.61 2009 May 11 00:30:22 http://mibbit.com/pb/YwvFYt -- 2.61 2009 May 11 00:31:09 mariorz: yours is exactly as mine 2009 May 11 00:31:26 all 3 are exactly the same 2009 May 11 00:31:29 ok I have a mistake in the (null? set) case... 2009 May 11 00:31:33 otherwise the same 2009 May 11 00:31:42 ok, aamar's too 2009 May 11 00:31:45 ah yeah 2009 May 11 00:32:02 oh yeah 2009 May 11 00:32:13 alright, next one? 2009 May 11 00:32:15 ok, 2.62? 2009 May 11 00:32:27 yeah 2009 May 11 00:32:30 http://inimino.org/~inimino/projects/2009/SICP/chap_2/2.62 2009 May 11 00:32:32 http://mibbit.com/pb/e3Yyrl -- 2.62 2009 May 11 00:34:08 all seem equivalent 2009 May 11 00:34:08 again pretty much teh same 2009 May 11 00:34:20 except for the use of let 2009 May 11 00:34:21 same again yeah 2009 May 11 00:34:24 yes 2009 May 11 00:34:37 I sort of assumed cons will be fast 2009 May 11 00:34:50 it's named after a machine instruction after all ;) 2009 May 11 00:35:23 2.63 ? 2009 May 11 00:35:32 http://mibbit.com/pb/0LzhyN -- 2.63 2009 May 11 00:35:37 I guess it will be implemented as nearly a direct memory read 2009 May 11 00:35:42 ok 2009 May 11 00:35:55 http://inimino.org/~inimino/projects/2009/SICP/chap_2/2.63 2009 May 11 00:36:08 I did not test this one but tried to prove it 2009 May 11 00:36:11 I may be wrong 2009 May 11 00:36:30 i did tests 2009 May 11 00:36:45 they return the same 2009 May 11 00:37:04 didnbt copy the session 2009 May 11 00:37:27 I skimped in my explanation compared to you 2009 May 11 00:37:54 aamar, yours and mine also disagree about the number of steps 2009 May 11 00:37:58 Yes, they do return the same; I think induction is the way to prove it. 2009 May 11 00:38:05 theyre both O(n) no? 2009 May 11 00:38:17 I do agree that the number of steps is greater. 2009 May 11 00:38:27 O( constant * n) = O(n) 2009 May 11 00:38:35 right 2009 May 11 00:38:48 So the "order of growth" I think is the same. 2009 May 11 00:39:07 yeah they may both be linear, just one is slower 2009 May 11 00:39:28 hm 2009 May 11 00:39:35 append is O(n) though right? 2009 May 11 00:39:53 since it has to walk all the way down the list 2009 May 11 00:40:22 yes 2009 May 11 00:40:32 so I think the first one might be O(n²) 2009 May 11 00:41:06 yes i think it is 2009 May 11 00:41:13 hm... why does append have to walk the list? 2009 May 11 00:41:30 how else does it get to the end of the first list? 2009 May 11 00:42:01 I thought there was a way, but I guess not. 2009 May 11 00:42:42 not without storing a pointer to the end of the list 2009 May 11 00:43:36 ok, think you're probably right 2009 May 11 00:43:41 alright, next one? 2009 May 11 00:43:57 The first seems to be O(n^2) 2009 May 11 00:43:59 ok 2009 May 11 00:44:00 what happens if it was O(1)? 2009 May 11 00:44:03 yes 2009 May 11 00:44:23 if it was O(1) (append i mean= then it would be O(n) 2009 May 11 00:44:29 or am i confused? 2009 May 11 00:44:42 if append was O(1) then I think both list->tree-1 and -2 would be O(n) 2009 May 11 00:44:50 yes 2009 May 11 00:45:00 which is what I had thought was the answer 2009 May 11 00:45:38 so the first one is O(n^2) 2009 May 11 00:46:05 yeah I think so 2009 May 11 00:46:22 2.64? 2009 May 11 00:46:58 k 2009 May 11 00:47:07 http://inimino.org/~inimino/projects/2009/SICP/chap_2/2.64 2009 May 11 00:47:28 http://mibbit.com/pb/Fq9MVg -- 2.64 2009 May 11 00:47:33 hm, looks like I forgot to draw the tree 2009 May 11 00:48:01 my explanation is pretty meager. 2009 May 11 00:48:20 i didnt draw the tree either 2009 May 11 00:48:26 but i concur with aamar :) 2009 May 11 00:48:27 Most crucially, I didn't think it was linear... trying to figure out if I'm right. 2009 May 11 00:50:03 ah 2009 May 11 00:50:10 mariorz: we had the same answers, I think 2009 May 11 00:50:11 i think youre right 2009 May 11 00:50:38 I think it must be linear, since it does have to parse the whole list at some point 2009 May 11 00:50:41 inimino are you sure? 2009 May 11 00:50:50 And it is essentially handling each element at some point 2009 May 11 00:51:12 true 2009 May 11 00:51:28 yes in case of a binary tree search one half is disscarded 2009 May 11 00:51:39 whihc accounts for the log growth 2009 May 11 00:52:00 not here 2009 May 11 00:52:23 I think aamar's drawing actually has 9 and 11 reversed 2009 May 11 00:52:45 so if you had a list of N items, and then instead gave it a list of 2N items, would you expect it to have a single extra step? 2009 May 11 00:52:57 about O() I think it cannot be less than linear 2009 May 11 00:53:09 since every element has to be places somethere 2009 May 11 00:53:25 s/places somethere/placed somewhere/ 2009 May 11 00:53:46 aamar: when searching a tree yes, not here 2009 May 11 00:54:02 ok i agree 2009 May 11 00:54:04 Okay, I think you're right that here it would take twice as many steps. 2009 May 11 00:54:24 So definitely my drawing wouldn't be right if the 9 and 11 were switched. 2009 May 11 00:54:36 But it's possible I should have the 5 at the root of the tree instead of the 7. 2009 May 11 00:55:10 Yes, I think it should have the 5 at the top 2009 May 11 00:55:52 hm 2009 May 11 00:56:29 I think 7 is at the top 2009 May 11 00:56:51 I have drawn the tree, if you reload that page 2009 May 11 00:56:58 as I think it should be 2009 May 11 00:57:14 http://mibbit.com/pb/zGYK5q -- 2.64 revised 2009 May 11 00:58:00 hm I think I might be wrong 2009 May 11 00:58:24 I think my description of what the algorithm does, and my drawing, agree with each other 2009 May 11 00:58:27 but both are wrong 2009 May 11 00:59:15 5 is going to be on top 2009 May 11 00:59:22 agreed 2009 May 11 00:59:28 on the first call to partial-tree, left-size will be 2 2009 May 11 00:59:35 so yeah, 5 should be on top 2009 May 11 00:59:38 so it has to be that second one 2009 May 11 00:59:42 you linked 2009 May 11 00:59:49 yup 2009 May 11 00:59:53 and my description - calculates the size of the left branch, as half the value of n, 2009 May 11 00:59:53 rounded down if n is odd. 2009 May 11 00:59:59 is wrong 2009 May 11 01:00:14 size of left branch is (n - 1) / 2 2009 May 11 01:00:25 rounded down if n was even 2009 May 11 01:00:30 right 2009 May 11 01:00:35 alright 2009 May 11 01:01:10 ok, next one then? 2009 May 11 01:01:44 ok 2009 May 11 01:01:48 k 2009 May 11 01:01:54 http://inimino.org/~inimino/projects/2009/SICP/chap_2/2.65 2009 May 11 01:02:17 ah, this one took me a long time 2009 May 11 01:02:25 http://mibbit.com/pb/m8mNwg -- 2.65 2009 May 11 01:03:05 aamar we have exactly the same 2009 May 11 01:03:45 all of us have the same, looks like 2009 May 11 01:04:07 looks the same 2009 May 11 01:04:14 I guess I rewrote some stuff 2009 May 11 01:04:24 yeah basically the same 2009 May 11 01:04:38 and I think aamar your intersection-set-tree is missing a tree->list 2009 May 11 01:04:48 erm, list->tree I mean 2009 May 11 01:05:02 anyway the same other than that 2009 May 11 01:05:08 right, thanks. 2009 May 11 01:05:14 I kept trying to think of some clever way to do this one 2009 May 11 01:05:15 true 2009 May 11 01:05:30 some way to combine the branches 2009 May 11 01:05:33 and all agreed on the O(n) no? 2009 May 11 01:05:39 but I think it might not be possible 2009 May 11 01:05:45 yeah I think these are all O(n) 2009 May 11 01:06:08 (assuming using tree->list-2) 2009 May 11 01:06:12 rebalancing the tree would be quite a bit of work 2009 May 11 01:06:25 good point 2009 May 11 01:06:26 And I agree that this is O(n) 2009 May 11 01:06:59 aamar: yeah it turned out to be complicated 2009 May 11 01:07:09 I didn't really get anywhere with it 2009 May 11 01:07:24 alright, next one? 2009 May 11 01:08:01 http://mibbit.com/pb/GAeUFh -- 2.66 2009 May 11 01:08:09 oh, yeah this one 2009 May 11 01:08:10 (a d a b b c a) 2009 May 11 01:08:19 the URI is longer than the answer ;-) 2009 May 11 01:08:46 hm, did I skip one? 2009 May 11 01:08:52 think so 2009 May 11 01:08:58 2.66 2009 May 11 01:08:58 whoops 2009 May 11 01:09:02 http://inimino.org/~inimino/projects/2009/SICP/chap_2/2.66 2009 May 11 01:09:46 ok all very similar it seems 2009 May 11 01:10:08 yes 2009 May 11 01:10:48 yeah 2009 May 11 01:11:09 did we all get the same answer on 2.67? 2009 May 11 01:11:14 this would be O(log*n) growth now no? 2009 May 11 01:11:23 hm... 2009 May 11 01:11:32 ok 2.67 2009 May 11 01:11:43 mariorz: which one? 2009 May 11 01:11:51 log n right 2009 May 11 01:12:04 agreed 2009 May 11 01:12:06 I agree 2.66 is O(log n) 2009 May 11 01:12:44 inimino: on 2.67, agreed, I got the same decoded message. 2009 May 11 01:12:44 ok 2009 May 11 01:12:46 lookup 2009 May 11 01:12:51 ok 2009 May 11 01:12:59 It was pretty disappointing, thought it would be a real secret message. 2009 May 11 01:13:04 yeah me too 2009 May 11 01:13:08 I was let down 2009 May 11 01:13:12 lol 2009 May 11 01:13:14 yeah 2009 May 11 01:13:18 i.e. "Be sure to drink your Ovaltine." 2009 May 11 01:13:29 that would have been impressive :-) 2009 May 11 01:13:31 oh well 2009 May 11 01:13:57 2.68 was interesting 2009 May 11 01:14:00 alright, 2.68 then? 2009 May 11 01:14:01 yes considering the dict 2009 May 11 01:14:12 oh yeah 2009 May 11 01:14:17 this one was fun 2009 May 11 01:14:26 mariorz: yeah, exactly :) 2009 May 11 01:14:31 http://inimino.org/~inimino/projects/2009/SICP/chap_2/2.68 2009 May 11 01:14:31 http://mibbit.com/pb/zEP99N -- 2.68 2009 May 11 01:14:34 well this is as far as i go gentlemen 2009 May 11 01:14:56 these look like fun sim going to try them on my own 2009 May 11 01:15:02 s/sim/own/ 2009 May 11 01:15:25 s/sim/so I'm/ ? 2009 May 11 01:15:49 heh 2009 May 11 01:15:51 ok 2009 May 11 01:15:57 er 2009 May 11 01:16:06 what inimino said 2009 May 11 01:16:19 alright 2009 May 11 01:16:43 see you guys later 2009 May 11 01:16:47 later 2009 May 11 01:16:51 mariorz: alright, see you next time 2009 May 11 01:16:56 aamar, you want to keep going or knock off for today? 2009 May 11 01:17:11 I'd be happy to continue -- just 5 more problems anyway 2009 May 11 01:17:22 I kind of want to see them, ok lets continue 2009 May 11 01:18:06 your answer to 2.68 is really different from mine... 2009 May 11 01:18:10 reading through it. 2009 May 11 01:18:29 yeah I did something a little different 2009 May 11 01:18:54 I thought about using memq but didn't like it 2009 May 11 01:19:53 so you head down to check each leaf instead 2009 May 11 01:21:20 yeah 2009 May 11 01:22:06 and then you carry false all the way up the 'failed' branches 2009 May 11 01:22:19 and then you need an additional check at the top level to turn a 'false' into an error 2009 May 11 01:22:27 yeah 2009 May 11 01:22:33 Okay. 2009 May 11 01:22:40 brb 2m sorry 2009 May 11 01:22:55 np 2009 May 11 01:23:19 It's helpful to see these alternate versions; considered doing them, but liked the simplicity of the memq solution, since it was available. 2009 May 11 01:23:46 http://mibbit.com/pb/4oIzxl -- 2.69 2009 May 11 01:24:09 ok, back 2009 May 11 01:24:41 http://inimino.org/~inimino/projects/2009/SICP/chap_2/2.69 2009 May 11 01:25:48 ok, these look the same 2009 May 11 01:26:51 I used (null? (cdr x)) to avoid testing the length 2009 May 11 01:27:37 there's probably some native singleton? test for lists, but I don't know what it is 2009 May 11 01:27:41 is that better? 2009 May 11 01:27:53 ok 2009 May 11 01:28:02 well, unless it's optimized, it would have to calculate the length 2009 May 11 01:28:18 which is also O(n) 2009 May 11 01:28:23 and the compare it to 1 2009 May 11 01:28:40 I see, thanks 2009 May 11 01:29:04 an interpreter could obviously optimize that away pretty easily but I didn't want to rely on it 2009 May 11 01:29:31 alright, 2.70? 2009 May 11 01:29:49 yes 2009 May 11 01:29:59 http://mibbit.com/pb/mFRx0E -- 2.70 2009 May 11 01:29:59 http://inimino.org/~inimino/projects/2009/SICP/chap_2/2.70 2009 May 11 01:30:34 nice, same answer 2009 May 11 01:30:51 I didn't bother including the encoded string, but looks like the same 2009 May 11 01:31:19 yeah 2009 May 11 01:31:27 ok, next? 2009 May 11 01:31:29 sure 2009 May 11 01:31:39 http://inimino.org/~inimino/projects/2009/SICP/chap_2/2.71 2009 May 11 01:31:54 http://mibbit.com/pb/TK2qS2 -- 2.71 2009 May 11 01:32:35 mirror image 2009 May 11 01:32:55 yeah 2009 May 11 01:33:05 I didn't do the additions, but same otherwise 2009 May 11 01:33:16 and same answer at the end 2009 May 11 01:33:24 next one? 2009 May 11 01:33:25 I think according to the code above yours comes up in the right orientation, but it is basically arbitrary. 2009 May 11 01:33:35 Yes, the end answers are the same. 2009 May 11 01:34:05 yeah I think the choice of left and right branch is basically arbitrary 2009 May 11 01:34:24 yes, ok 2009 May 11 01:34:34 http://mibbit.com/pb/pXHLTy -- 2.72 2009 May 11 01:34:47 http://inimino.org/~inimino/projects/2009/SICP/chap_2/2.72 2009 May 11 01:36:56 Okay, we agree that the most frequent symbol can be made to be an O(1) search, if one is trying to make that one fast. 2009 May 11 01:37:24 yes 2009 May 11 01:37:49 I'm not sure I buy your second paragraph yet. 2009 May 11 01:38:25 If you search the most frequent character last, then you're going to do a lot of comparisons with very infrequent characters before you get there, no? 2009 May 11 01:38:39 well 2009 May 11 01:38:57 the code that I wrote in 2.68 is different 2009 May 11 01:39:27 Yes, sure. 2009 May 11 01:40:03 the second paragraph or third? 2009 May 11 01:40:44 Third, I meant. 2009 May 11 01:40:48 ok 2009 May 11 01:41:08 it will compare once with every other character before it gets there, yes 2009 May 11 01:41:26 Actually, I do buy it. 2009 May 11 01:41:32 so if there are n-1 other characters then it does that every time it has to encode the most frequent symbol 2009 May 11 01:41:39 ok 2009 May 11 01:42:00 Interesting point. 2009 May 11 01:42:36 So for the least common character, in your code, with the trees drawn in the direction you have them, would take O(1). 2009 May 11 01:42:37 ? 2009 May 11 01:43:26 And if you switch operations, it would really take O(n) ? 2009 May 11 01:43:46 I think it would take the least amount it can take on the least frequent character 2009 May 11 01:44:25 it still has to cons all the 0s onto the encoding, so I think it's O(n), but it only does one comparison 2009 May 11 01:45:02 and then all the 'if left' things short-circuit back up and it conses all the 0s on and returns that result 2009 May 11 01:45:07 Ok right 2009 May 11 01:47:00 okay, so that's it for today? 2009 May 11 01:47:21 yeah, I'm good 2009 May 11 01:47:49 what should we aim for next time? 2009 May 11 01:48:36 At a minimum, wrap chapter 2 2009 May 11 01:48:50 So that would give us 2.73 - 2.97 2009 May 11 01:49:13 2.4 has only 4 problems 2009 May 11 01:49:16 ok 2009 May 11 01:50:00 ok, sounds good to me 2009 May 11 01:50:04 2.5 seems to have some meat on it. 2009 May 11 01:50:05 great 2009 May 11 01:50:09 yeah 2009 May 11 01:50:30 alright, I'll send out logs later this evening 2009 May 11 01:50:58 see you on May 24 then :) 2009 May 11 01:51:17 see you then!