Unformatted text preview:

HW 4Due: Wed Nov. 8CS105: Great Insights in Computer ScienceMichael L. Littman, Fall 2006Covering Lectures 7 and 81. Sock Sorting BugsEach of the sock sorting routines below has a fatal flaw (bug). Match the description of a flaw to the name of the sorting routine that has the flaw.a. When there’s only two socks left, tries to grab a third.b. Replaces a sock that's already been matched.c. Replaces the same sock twice in a row.d. Forgets to replace socks if they don’t match.exam styleSock Sortersdef sorterA(): a = getSock() b = getSock() if not match(a,b): replaceSock(a) replaceSock(a)def sorterB(): a = getSock() b = getSock() while match(a,b): replaceSock(a) a = getSock()def sorterC(): a = getSock() b = getSock() if match(a,b): returndef sorterD(): a = getSock() b = getSock() c = getSock() if not match(a,b): replaceSock(a) replaceSock(b) replaceSock(c)2. Song GrowthHow many syllables do you sing in n verses of the following three songs? Choose from O(n), O(n lg n), O(n2), and O(n2 lg n).Verses are separated by blank lines.a. b. c. exam stylea. Girl Named FredI'm in love with a girl named Fred.My reasons must be clear:When she shows you all how strong she is,You'll stand right up and cheer!With an F and an R and an E and a D,And an F-R-E-D, Fred! Yeah!I'm in love with a girl named Fred.She drinks just like a Lord!So sing a merry drinking song,And let the wine be poured!Fill the bowl to overflowing,Raise the goblet high!With an F and an R and an E and a D,And an F-R-E-D, Fred! Yeah!I'm in love with a girl named Fred.She sings just like a Bird!You'll be left completely speechless,When her gentle voice is heard!Doobie doobie wah wah wah!Fill the bowl to overflowing,Raise the goblet high!With an F and an R and an E and a D,And an F-R-E-D, Fred! Yeah!I'm in love with a girl named Fred.She wrestles like a Greek!You will clap your hands in wonder,At her fabulous technique!Clap clap-clap-clap clap clap-clap-clap.Doobie doobie wah wah wah!Fill the bowl to overflowing,Raise the goblet high!With an F and an R and an E and a D,And an F-R-E-D, Fred! Yeah!I'm in love with a girl named Fred.Who dances with such grace!You are bound to sing her praises,‘Til you're purple in the face!Bravo! Bravo! Bravissimo!Bravo! Bravissimo!Clap clap-clap-clap clap clap-clap-clap.Doobie doobie wah wah wah!Fill the bowl to overflowing,Raise the goblet high!With an F and an R and an E and a D,And an F-R-E-D, Fred! Yeah!I'm in love with a girl named Fred.She's musical to boot.She will set your feet a-tapping,When she plays upon her lute!Tap Tap-tap Tap-tap tap.Bravo! Bravo! Bravissimo! Bravo! Bravissimo!Clap clap-clap-clap clap clap-clap-clap.Doobie doobie wah wah wah!Fill the bowl to overflowing,Raise the goblet high!With an F and an R and an E and a D,And an F-R-E-D, Fred! Yeah!I'm in love with a girl named Fred.A clever, clownish wit!When she does her funny pantomime,Your sides are sure to split!Ha-ha-ha-ha, Ho-ho-ho-ho, Ha-ha-ha-ha-Ho!Tap Tap-tap Tap-tap tap.Bravo! Bravo! Bravissimo!Bravo! Bravissimo!Clap clap-clap-clap clap clap-clap-clap.Doobie doobie wah wah wah!Fill the bowl to overflowing,Raise the goblet high!With an F and an R and an E and a D,And an F-R-E-D, Fred! Yeah!b. L-YYou're wearing your squeaky shoesAnd right there taking a snoozeIs a tiger, so how do you walk on by?Silently ... silently ... silent ... L-YYou're a secret agent manWho's after the secret planHow do you act so they don't know you're a spy?Normally ... normally ... normal ... L-YAt an eating contest you boastThat you can eat the mostHow do you down your fiftieth piece of pie?Eagerly ... eagerly ... eager ... L-YOn the lake your boat upsetAnd your clothes got soaking wetHow do you stand and wait for them to dry?D-d-d-d-d patiently ... d-d-d-d-d patiently ... patient ... L-YIn the public libraryYou fall and you hurt your kneeBut the sign says "quiet please," so how can you cry?Quietly .... quietly .... quiet ... L-YAs you walk along the streetA porcupine you meetHow do you shake his hand when he says hi?Carefully ... carefully .... careful ... L-YYou enter a very dark roomAnd sitting there in the gloomIs Dracula! Now how do you say goodbye?Immediately ... immediately ... immediate ... L-Y[by Tom Lehrer]c. Little MonkeysFive little monkeys, swinging from a tree,Teasing Mr. Alligator, “Can’t catch me!”Along comes Mr. Alligator, quiet as can be,SNAP! that monkey right out of the tree.Four little monkeys, swinging from a tree,Teasing Mr. Alligator, “Can’t catch me!”Along comes Mr. Alligator, quiet as can be,SNAP! that monkey right out of the tree.Three little monkeys, swinging from a tree,Teasing Mr. Alligator, “Can’t catch me!”Along comes Mr. Alligator, quiet as can be,SNAP! that monkey right out of the tree.Two little monkeys, swinging from a tree,Teasing Mr. Alligator, “Can’t catch me!”Along comes Mr. Alligator, quiet as can be,SNAP! that monkey right out of the tree.One little monkey, swinging from a tree,Teasing Mr. Alligator, “Can’t catch me!”Along comes Mr. Alligator, quiet as can be,SNAP! that monkey right out of the tree.No little monkeys, swinging from a tree,Away swims Mr. Alligator, as full as can be.3. Exponential Right?Which of these Newsweek excerpts use the term “exponentially” correctly? If it is correct, give the exponential equation it implies.a. Current approaches aren’t working; even though home users and many companies started filtering their e-mail two years ago, the overall amount of junk mail has ballooned —exponentially.b. Once I got into digital photography the number of pictures I took exponentially increased.c. Since 1986, when e-filing began with just 25,000 tax returns filed online, the number of e-filed returns has risen exponentially, with more than 68 million individual returns e-filed in 2005--that's more than 50 percent of all returns.d. "We are exponentially better than we were on that dreadful September morning," says Maura Harty, assistant secretary of state for consular a!airs.exam style4. Sing, Sing a Song• Describe a generalized version of a real song that can be sung for n verses.• Show us the first 3 or 4 verses.• Tell us how the number of syllables grows with the number of verses (O(n), O(n2), O(n log n),


View Full Document

Rutgers University CS 105 - Great Insights in Computer Science

Download Great Insights in Computer Science
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Great Insights in Computer Science and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Great Insights in Computer Science 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?