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 1: Meeting 2

 

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 1 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, let me know and I will schedule some time for meeting.

UMD Meeting Discussion points/summary

  • Main concepts from the chapter
  • Benford's law
  • Philosophy of normal distribution (WHY is it so prevailent in nature?)
  • identities, summations, etc. 

We spent most of our time going through the chapter. We discussed some of the proofs in detail: 

  • jensen's inequlity
  • conditional expectation
  • the proof on page 45-46 of the branching process example
  • the proof of lemma 10 (in the digital version, the number is different in the hard copy), in particular why the interchange of sums with the change of limits is justified, and why the second sum simply becomes an extra 'j' term. 
  • none of us were clear as to why exactly the authors included the explicit statement that, "the interchange of (possibly) infinite summations is justified, because the terms being summed are all non-negative." why is this qualification needed? what bad things could happen if some of the terms WERE negative?

We spent some time remembering/discussing properties of various equalities, identities, and distributions including:

  • the harmonic, geometric, and arithmetic means
  • binonial identity
  • the factorial form of the binomial coefficient

we discussed but didn';t solve in detail problems 1,5 and 6. but unfortunately we found the chapter rather dense and none of us had much time to do problems this week.

we also discussed that after chapters 3 and 4, it would be nice to take a short break from reading and have a week focused just on solving problems. 

feel free to add/edit other stuff. just trying to get some memory jogs down :). if/as we solve more problems we should post them. 

Task Discussion


  • Saravanan   June 6, 2011, 3:25 a.m.

    @All, 

    I have updated solutions of some Alice Chap2 problems to the flickr group. I will put them in the inline comment sometime tomorrow . Hope this helps :)

  • Kotaro Hara   June 6, 2011, 9:42 p.m.
    In Reply To:   Saravanan   June 6, 2011, 3:25 a.m.

    Awesome :) Thank you!

    We are thinking about having one week to revise previous chapters' excercises after next week. (which is after finishing the 4th chap of the Alice book.) Your answers will be so useful!

  • Jessy Kate Schingler   June 6, 2011, 9:53 p.m.
    In Reply To:   Kotaro Hara   June 6, 2011, 9:42 p.m.

    agreed, you rock!!! 

    saravanan, do you want/need somewhere to host the actual pdfs instead of the jpgs? i mean the images are readable, i'm just thinking since you went to the trouble of making nice pdfs we could post them somewhere... anyway let me know, i can host them on my server or dropbox if you want. 

  • Saravanan   June 7, 2011, 2:45 a.m.
    In Reply To:   Jessy Kate Schingler   June 6, 2011, 9:53 p.m.

    Jessy,

    One of the reasons I uploaded the files as images is to avoid them from getting indexed by search engines. I am sure most profs will not be pleased if students can find them via google :) 

    That said, here are the dropbox links for pdf and the LaTeX code :

    Chap 2 : http://dl.dropbox.com/u/31579472/aliceChap2Solns.pdf and http://dl.dropbox.com/u/31579472/aliceChap2Solns.tex

    Chap 1 :   http://dl.dropbox.com/u/31579472/aliceChap1Solns.pdf and http://dl.dropbox.com/u/31579472/aliceChap1Solns.tex 

    I tentatively intend to keep them in the dropbox for a while so tat if i solve any new problems in chap1/2  during week 5, it will be automatically updated.  Of course, You are welcome to mirror these files in your server.

     

    Any suggestions for avoid dissemination outside P2PU is welcome .. 

  • Saravanan   June 6, 2011, 3:15 a.m.

    Regarding "none of us were clear as to why exactly the authors included the explicit statement that, "the interchange of (possibly) infinite summations is justified, because the terms being summed are all non-negative." why is this qualification needed? what bad things could happen if some of the terms WERE negative?"

    You are right to claim that in finite summations. But infinite summations are a different beast. There are lot of summations that "conditionally converge" based on their constituent summations. For, if you order them in one way they converge and in other way they diverge ! IIRC, One of the key reasons for this anamoly is that associativity does not always hold in infinite series.

    I cannot , on the top of my head, think of an example to show when the interchange creates trouble. But I can give a canonical example where arbitrary summation leads to bizzare results. 

    Let X=1 and Y=-X (ie -1). Consider the summation s = \sum_{i=1}{\infty} X + \sum_{i=1}{\infty} Y. Common sense says that this must add to 0. But if you rearrange the terms,

     

    s = 1 + \sum_{i=2}{\infty} X + \sum_{i=1}{\infty} Y

    s = 1 + infinty-infinity

    s=1

    In fact, you can make the summation to be anything !  Part of the trouble is due to indiscrete mixing of positive and negative items. 

    Hope this helps :)