Great Theoretical Ideas In Computer Science Anupam Gupta Lecture 4 CS 15 251 Sept 8 2005 Unary and Binary Fall 2005 Carnegie Mellon University Your Ancient Heritage Let s take a historical view on abstract representations Mathematical Prehistory 30 000 BC Paleolithic peoples in Europe record unary numbers on bones 1 represented 2 represented 3 represented 4 represented by by by by 1 2 3 4 mark marks marks marks Prehistoric Unary 1 2 3 4 PowerPoint Unary 1 2 3 4 Hang on a minute Isn t unary a bit literal as a representation Does it deserve to be viewed as an abstract representation In fact it is important to respect the status of each representation no matter how primitive Unary is a perfect object lesson Consider the problem of finding a formula for the sum of the first n numbers We already used induction to verify that the answer is n n 1 Consider the problem of finding a formula for the sum of the first n numbers First we will give the standard high school algebra proof 1 2 n n 1 3 n 1 n S n 2 2 1 S n 1 n 1 n 1 n 1 n 1 2S n n 1 2S n n 1 S 2 1 2 n n 1 3 n 1 n S n 2 2 1 S Algebraic argument n 1 n 1 n 1 n 1 n 1 2S n n 1 2S Let s restate this argument using a UNARY representation 1 2 n n 1 3 number of white dots n 1 n S n 2 2 1 S n 1 n 1 n 1 n 1 n 1 2S n n 1 2S 1 2 n n 1 n S number of white dots n 2 2 1 S number of yellow dots n 1 n 1 n 1 n 1 n 1 2S n n 1 2S 1 2 n n 1 3 n 2 1 1 2 n 1 2 n n 1 3 n 1 n S n 2 2 1 S n 1 n 1 n 1 n 1 n 1 2S n n 1 2S number of white dot number of yellow dot n n There are n n 1 dots in the grid n n n n n 1 n 1 n 1 n 1 n 1 2 n n 1 3 n 1 n S n 2 2 1 S n 1 n 1 n 1 n 1 n 1 2S n n 1 2S number of white dot number of yellow dot n n n 1 S 2 n n n n n n 1 n 1 n 1 n 1 n Very convincing The unary representation brings out the geometry of the problem and makes each step look very natural By the way my name is Bonzo And you are Odette Yes Bonzo Let s take it even further nth Triangular Number n 1 2 3 n 1 n n n 1 2 nth Square Number n n n 1 n2 Breaking a square up in a new way Breaking a square up in a new way 1 Breaking a square up in a new way 1 3 Breaking a square up in a new way 1 3 5 Breaking a square up in a new way 1 3 5 7 Breaking a square up in a new way 1 3 5 7 9 Breaking a square up in a new way 1 3 5 7 9 52 The sum of the first 5 odd numbers is 5 squared The sum of the first n odd numbers is n squared Pythagoras Here is an alternative dot proof of the same sum nth Square Number n n n 1 n2 nth Square Number n n n 1 n2 nth Square Number n n n 1 n2 Look at the columns n n n 1 Look at the columns n n n 1 Sum of first n odd numbers High School Notation n n 1 1 2 3 4 1 2 3 4 5 1 3 5 7 9 Sum of odd numbers High School Notation n n 1 1 2 3 4 1 2 3 4 5 1 3 5 7 9 Sum of odd numbers Check the next one out area of square is n 1 2 n 1 2 n 1 area of new square is n 2 n n 1 2 n 1 n area of new square is n 2 New shaded area n n n n 1 n n n 1 n n n n 1 2 n 1 n n n 2 n 1 2 n n 2 n 1 2 n n 2 n 1 2 n 2 n 1 2 n n 2 13 23 33 n3 n n 1 2 2 Can you find a formula for the sum of the first n squares The Babylonians needed this sum to compute the number of blocks in their pyramids Can you find a formula for the sum of the first n squares The ancients grappled with problems of abstraction in representation and reasoning Let s look back to the dawn of symbols Sumerians modern Iraq Sumerians modern Iraq 8000 BC Sumerian tokens use multiple symbols to represent numbers 3100 BC Develop Cuneiform writing 2000 BC Sumerian tablet demonstrates base 10 60 notation no zero solving linear equations simple quadratic equations Biblical timing Abraham born in the Sumerian city of Ur Babylonians absorb Sumerians 1900 BC Sumerian Babylonian Tablet Sum of first n numbers Sum of first n squares Pythagorean Theorem Pythagorean Triplets e g 3 4 5 some bivariate equations 1600 BC Babylonian Tablet Take square roots Solve system of n linear equations Egyptians 6000 BC Multiple symbols for numbers 3300 BC Developed Hieroglyphics 1850 BC Moscow Papyrus Volume of truncated pyramid 1650 BC Rhind Papyrus Ahmes Ahmose Binary Multiplication Division Sum of 1 to n Square roots Linear equations Biblical timing Joseph is Governor of Egypt Harrappans Indus Valley Culture Pakistan India 3500 BC Perhaps the first writing system 2000 BC Had a uniform decimal system of weights and measures China 1200 BC Independent writing system Surprisingly late 1200 BC I Ching Book of changes Binary system developed to do numerology Rhind Papyrus Scribe Ahmes was the Martin Gardener of his day Rhind Papyrus had 87 Problems A man has seven houses Each house contains seven cats Each cat has killed seven mice Each mouse had eaten seven ears of spelt Each ear had seven grains on it What is the total of all of these Sum of first five powers of 7 1 X X X X 1 2 3 n 2 n X n 1 1 X X1 We ll use this fundamental sum again and again The Geometric Series A Frequently Arising Calculation X 1 1 X1 X2 X3 Xn 2 Xn 1 A Frequently Arising Calculation X 1 1 X1 X2 X3 Xn 2 Xn 1 X1 X 2 X3 Xn 1 Xn 1 X1 X2 X3 Xn 2 Xn 1 1 Xn Xn 1 Action Shot Mult by X is a …
View Full Document
Unlocking...