June 8: Meeting 3

Task Discussion

• 
  Jessy Kate Schingler   June 22, 2011, 3:04 p.m.

  Reminder that we'll be meeting in AVW 3122 tonight at 6!

• 
  Alex Quinn   June 22, 2011, 11:04 a.m.

  I'm sorry, but I think I'd better skip tonight.  I have some work that I need to focus on.

• 
  Jessy Kate Schingler   June 22, 2011, 3:04 p.m.
  In Reply To:   Alex Quinn   June 22, 2011, 11:04 a.m.

  No worries Alex!

• 
  Saravanan   June 17, 2011, 7:22 p.m.

  Any one tried solving exercises from chapter 3 or 4?  I am quite curious to compare results !

• 
  Jessy Kate Schingler   June 18, 2011, 1:13 p.m.
  In Reply To:   Saravanan   June 17, 2011, 7:22 p.m.

  We went over exercises 1-7 (i think it was 7!) for ch.3 during our week 3 meeting... this week is a catchup week so i'm doing some more exercises. which ones did you do? maybe it would be useful to focus on the ones you've done so we can compare? :)

• 
  Saravanan   June 18, 2011, 4:54 p.m.
  In Reply To:   Jessy Kate Schingler   June 18, 2011, 1:13 p.m.

  Nice ! I did exercises 3.1-3.6,3.8, 3.10-3.12,3.14-3.16 and parts of 3.22.

  Over the weekend, I am trying to complete others . Specifically i am focussing on 3.9,3.13,3.17-3.20a , 3.24 and 3.25 . I also found the expected value for 3.7 but not its variance. 

• 
  Saravanan   June 19, 2011, 9:58 p.m.
  In Reply To:   Saravanan   June 18, 2011, 4:54 p.m.

  Final list of solved problems -  3.1-3.8,3.10-3.12,3.14-3.17,3.20,3.22,3.25

• 
  Saravanan   June 10, 2011, 7:27 p.m.

  Hello All, 

  I have a couple of queries in chapter 3. 

  (1) Did anyone get the event E_2 in lemma 3.10 pf the book ? (or lemma 13 in pdf) . I can see why E_1 can be true though

  (2) If |C| = 4n^(3/4) and we sort it , is there any simple argument to show the running time is definitely (sub)linear ? . For eg page 53 of book and 71 of pdf makes that claim. Asymptotically, I get n^(3/4) ln n which need not be sublinear. For eg if n=1000. Additionally, i cannot fully convince myself that it definitely linear - ie always less than say cn for some constant c. 

  Is there anything simple I am missing?

• 
  Jessy Kate Schingler   June 16, 2011, 11:46 a.m.
  In Reply To:   Saravanan   June 10, 2011, 7:27 p.m.

  I didn't read through that example yet but I think maybe Kotaro did?

  We've been planning to spend this week reviewing the material up till now. I'll try and read through that example this week :)

• 
  Saravanan   June 17, 2011, 12:48 a.m.
  In Reply To:   Jessy Kate Schingler   June 16, 2011, 11:46 a.m.

  Thanks Jessy. I have a informal idea for the two queries but nothing formal.

• 
  Kotaro Hara   June 18, 2011, 2:33 p.m.
  In Reply To:   Saravanan   June 10, 2011, 7:27 p.m.

  Hi Saravanan and Jessy.

  Hmm, I read through that chapter, but I could didn't quite get that part. Sorry that I cannot be a help! I'll read through that part again and will post here if I get something :)

• 
  Saravanan   June 19, 2011, 3:02 a.m.
  In Reply To:   Kotaro Hara   June 18, 2011, 2:33 p.m.

  Thanks Kotaro.  This is the informal argument  I have for part 2 is this :

  if |C| is 4n^0.75 then the time to sort is

  = 4n^0.75 log (4n^0.75)

  = 4n^0.75 (log 4 + 0.75 log n)

  = 2.408 n^0.75 + 3n^0.75 log n

  taking log on both sides, 

  log x = 0.75 logn + log(2.408+3logn)

  approx = 0.75 logn + log(3logn)

  = 0.75 logn + log3 + log logn

  For a digit with k bits, it becomes approx 0.75k + log 3 + log k . For large n , log k < 0.25 k. (see http://www.wolframalpha.com/input/?i=0.25k+%3C+log+k&a=*FunClash.log-_*Log10.Log- ) .   Hence the whole thing is less than k and hence sublinear.