CS10 Midterm Study SessionAugust 1, 2011This Presentation is Online Follow along & access from home. http://bit.ly/a3YV0QStuff to KnowThe midterm is this week! ● It will be administered online and is self-administered with an honesty policy.The midterm is cumulative, but you can bring two cheat sheets with you.If there are any programming questions on the written portion of the midterm, you will receive a list of all of the blocks that you will need to use.Grade Breakdown Online10/60Written 50/60What's on It?Anything that we've covered in the lectures, readings, or labs is fair game.The search engine lab will not be tested.The Twitter presentation is testable. If you missed Raffi's presentation or would like to see it again, it is available online.http://vimeo.com/16057918Some new stuff we've been over since the quest:AlgorithmsAlgorithmic ComplexityConcurrency Recursion Applications that Changed the WorldSocial Implications of ComputingTonight's Plan123Give you an idea of what to study.Go over big ideas from readings and labs.Let you polish your programming skills with some exercises.[Readings] Games with a Purposehttp://doi.acm.org/10.1145/1378704.1378719 Build games that involve tasks that are easy for humans but hard for computers. Use the information gained during gameplay for other computer-based tasks.[Readings] Scratch: Programming for Allhttp://portal.acm.org/citation.cfm?doid=1592761.1592779 Design goals:More tinkerableMore meaningfulMore social[Readings] Blown to Bits (1/6)http://www.bitsbook.com/wp-content/uploads/2008/12/chapter2.pdf (pp. 32 - 42) Koans! Also: technology is neither good nor bad, but presents us with both risks and opportunities.[Readings] The Free Lunch is Overhttp://www.gotw.ca/publications/concurrency-ddj.htm What does the "free lunch" refer to? Why is it over?[Readings] Spending Moore's Dividendhttp://portal.acm.org/citation.cfm?doid=1506409.1506425 The increasing hardware speeds has led to an increase in languages that are powerful but not efficient. Software is a gas.[Readings] Blown to Bits (2/6)http://www.bitsbook.com/wp-content/uploads/2008/12/chapter2.pdf (pp. 32 - 42) We leave digital footprints and fingerprints everywhere we go online. Increasingly popular technology (RFID, EDR, GPS) sometimes records information in the physical world without our knowledge.[Readings] Blown to Bits (3/6)http://www.bitsbook.com/wp-content/uploads/2008/12/chapter3.pdf Digital information can often be easily changed, and these changes can be remembered. Information we want to be understood is described in protocols.Information we don't want to be understood can be hidden with techniques like steganography.[Readings] Blown to Bits (4/6)http://www.bitsbook.com/wp-content/uploads/2008/12/chapter4.pdf Search has changed the way that we interact with information. Major factor in the permanence of bits.How search works.[Readings] Blown to Bits (5/6)http://www.bitsbook.com/wp-content/uploads/2008/12/chapter5.pdf Why were attempts to create a "backdoor" in encryption products picked up and shortly dropped after the terrorist attacks of 9/11? Major challenge of computational cryptography solved by public key cryptography.[Readings] Blown to Bits (6/6)http://www.bitsbook.com/wp-content/uploads/2008/12/chapter6.pdf Copyright & Digital Ownership: how was Napster different? Digital rights managementTake-away: ownership isn't clear cut anymore.[Programming] Algorithms What are algorithms?[Programming] Algorithms What does this algorithm do?[Programming] Algorithms Problem 1 Count the number of times a particular letter shows up in a sentence.[Programming] Algorithms Problem 1 Solution (iterative)[Programming] Algorithms Problem 1 Solution (recursion)[Programming] Algorithms Problem 1 Solution (recursion #2) You may not have seen the reporter version of the IF block -- it does the same thing as a normal IF but reports the first value when true and the second value when false.[Programming] Algorithms Problem 2 Add all of the multiples of 8 or 10 below a certain number and report the sum.[Programming] Algorithms Problem 2 Solution (iterative, recursive also possible)[Programming] ConcurrencyHow many things can a computer do at one time?What is concurrency?[Programming] Algorithmic ComplexityExamples of Complexities x = the number of "things" your algorithm runs onConstant 1Logarithmic log(x)Linear x Quadratic x2Exponential 2x[Programming] RecursionMake sure you can IDENTIFY and CREATE YOUR OWN recursive blocks.[Programming] Recursion<Fractals from Fall 2010 Midterm>[Programming] RecursionProblem 1 Count the number of elements in a list recursively without destroying the list.[Programming] RecursionProblem 1 Solution[Programming] RecursionProblem 2 Duplicate each item in a list. The output list should be twice as larger as the original input list.The list (A, B, C) becomes (A, A, B, B, C, C).[Programming] RecursionProblem 2 Solution[Programming] Challenge ProblemsChallenge #1 Report a new list that contains all of the elements from the original list, but with every nth element removed.The list (A, B, C, D, E, F, G) with n = 3 reports (A, B, D, E, G).[Programming] Challenge ProblemsChallenge #2 Write a recursive function that run-length encodes an input string. The block can report either a string or a list. The input string aabbbbbbccccc should report either 2a6b5c or (2, a, 6, b, 5, c).Run length encoding on Wikipedia: http://en.wikipedia.org/wiki/Run-length_encodingNote: a similar technique is used for some types of image