Formal Reasoning in Computer Science

This course will become read-only in the near future. Tell us at community.p2pu.org if that is a problem.

Task Navigation 

June 8: Meeting 3

 

NOTE: This is a wiki page -- anyone can add to this. Feel free to add/correct info here!

For people not at UMD, feel free to organize meetups at other locations! Add it here so people can find you. 

University of Maryland:

We'll be meeting Wednesday, June 8 at 6pm in AVW 3122 (we might go outside again if it's nice). Feel free to email Jessy with any questions jessy at cs dot umd.edu. We'll post discussion points, links and worked solutions to this page. 

University of Texas At Arlington : 

If anyone from UT Arlington is interested, contact Saravanan and I will schedule some time for meeting.

 

Maryland Meeting summary:

We talked about...

  • reviewed chapter contents, proofs
  • graphical representations of markov and chebyshev bounds (using the probability function)
  • why chebyshev is more powerful than markov
  • the meaning of the example on. p.64, for example if you set k to 1 you can an intuitive, trivial case
  • the coupon example and geometric distribution:

    • why sum from i = 0...inf of i*x^(i-1) = sum from i = 0...inf of (i+1)x^i
  • german tank problem!
  • problems 1-7
  • for Q1 - answer (n^2 - 1)/12... we pondered, WHY is there a 12? 

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.