Lecture 26:ReviewCS105: Great Insights in Computer ScienceMichael L. Littman, Fall 20061: Introduction• Computers are everywhere creating new capabilities.• Computer science is the study of "reduction": making complex out of simple.• Skill: Reading barcodes.2: Bits and Switches• Bits: 0/1, simple but can represent anything• Skill: Evaluate an expression using and/or/not.3: Gates• Bits can be made out of many things.• Universal logic gates can simulate and/or/not.• Gates can be defined in terms of simpler gates (reduction).• Logical expressions, truth tables4: Binary• Some simple logic gates.• Skill: Recognize some simple functions of logic gates.• Representing numbers in binary.• Skill: convert between binary and decimal (base 10).• Skill: adding numbers in binary.5: Machine Language• Fundamental circuits:• CPU interprets machine instructions.• Memory holds data and programs and is addressed in binary.• Arithmetic circuits perform mathematical calculations.• Each clock cycle corresponds to a small instruction being executed.• Machine-language program is made from bytes.• Everything in the computer is made from these small instructions.6: Subroutines• The hierarchy: application programs -> software libraries -> high-level languages -> machine language -> logic blocks -> basic logic gates -> physical bits (transistors).• Subroutines can package up repeated operations (like song choruses).• Skill: Write a song as a series of subroutines.• Parameters let you use the same subroutine for related tasks.• The subroutine stack keeps track of the program's place.7: Algorithms• Sock matching.• Different approaches to a problem can be faster than others!• Skills:• Convert a truth table to a logical expression.• Convert and add binary numbers.• Count the number of gates in a (multilevel) logic block.8: Growth Rates• Computer scientists analyze algorithms by their running time as a function of the size of the input.• Can sing generalizations of songs with n verses.• Number of syllables is a pain to figure out as a function of n.• Big-O notation (asymptotic growth rate) simplifies the process.8: more• Major classes of song growth rates:• constant-size verses: linear O(n)• verses grow because includes a number, which grows: linear-logarithmic (O(n lg n)).• verses grow by a constant size: quadratic (O(n2)).• verses grow by a constant size and include larger numbers: quadratic-logarithmic (O(n2 lg n)).• Skill: Recognize growth rate of songs.8: more• Skill: Distinguish proper (growth rate) and improper ("big") uses of the word "exponential".• The growth-rate classes are also very useful for analyzing algorithms like the sock sorter.9: Compilers• People write programs in languages that cannot be directly run on the computer.• Compilers translate the programs into machine language that the computer can run.• Parser captures the structure of the program, allows for optimizations and code generation.• Interpreters don't translate the program, but just simulate it themselves.• Skill: Interpreting expression trees.10: Graph Algorithms• Google builds a map of the web by visiting web pages it knows about, then looking on those pages for the address of other pages.• This operation is called "graph search". Used to solve mazes, also.• Graph defined by nodes, links. Other terms: source, sink, path, cycle, connected components, tour, directed, undirected, tree. Node x is "reachable" from y if there's a path from y to x.11: Sorting Algorithms• Sorting speeds up the search for information in a list of n.• Selection Sort: Repeatedly find, remove the smallest. O(n2).• Binary search: Ask a question that splits the remaining set of options in half. O(lg n).• Quick Sort: Split into big/small elements relative to pivot. O(n lg n).11: more• Skills:• Is the use of “exponential” right?• Given a generalized n-verse song, what is its syllable growth rate?• How many comparisons does a sorting algorithm make?14: Computability• If an assumption leads to self contradiction, the assumption is broken.• Barber paradox, Godel’s theorem, Kantor’s diagonalization• Assumption that we can detect whether a program loops forever leads to a program that loops forever and doesn’t loop forever.• The “halting problem” is not solvable.15: Randomness• Some problems solved simply and efficiently using random numbers (survey, quicksort).• Seemingly random numbers can be generated using complex numerical mixing-up functions.• Random bits useful for sending secret messages.• Skill: Will a given subroutine halt on all inputs?17: Parallel Computation• Moore’s Law: Roughly, computers double in speed every year and a half.• Some problems can be sped up by letting more than one computer work on them at a time.• Some can’t!• Some others can, but only if you’re clever.18: Compression• The number of bits that it takes to represent a message varies with the encoding.• Finding a shorter encoding is “compression”.• Huffman encoding uses few bits for common characters.• Skill: Given a string, build a Huffman code for it, encode and decode strings.19: Neural Networks• Classifiers map feature vectors to yes/no.• Classifiers can be created automatically (learned) by analyzing a training set of examples.• Perceptrons use a linear threshold function and can solve linearly separable problems.• Decision trees can be constructed from examples and applied to new instances (demo).21: Genetic Algorithms• Search algorithm using a population to find good solutions.• Uses populations of individuals (often bitstrings) that mate if their fitness is sufficiently high to produce new generations of improved individuals.• Skill: Mate two bitstrings and find the result.• Nice summary of earlier concepts!22. Robotics• “while True” is useful when constructing programs that must continue to do the right thing.• Reinforcement learning defines task by specifying the reward function / goal and letting the program change its behavior to make things work.• Robots are just computers.Next Time• Final! Wednesday, Dec. 20, 12-3pm• This room.• Open book.With sincere apologies to Simon and Garfunkel...ABCFalseFalseFalseFalseTrueFalseTrueFalseFalseTrueTrueTrueABFalseTrueTrueFalseABCFalseFalseFalseFalseTrueTrueTrueFalseTrueTrueTrueTrueA = TrueB = TruelightOn = Truedef sorter1():