New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

CS 200

by: Mrs. Carolyne Abbott
Mrs. Carolyne Abbott
GPA 3.71

David Evans

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

David Evans
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 11 page Class Notes was uploaded by Mrs. Carolyne Abbott on Monday September 21, 2015. The Class Notes belongs to CS 200 at University of Virginia taught by David Evans in Fall. Since its upload, it has received 19 views. For similar materials see /class/209647/cs-200-university-of-virginia in ComputerScienence at University of Virginia.

Similar to CS 200 at UVA

Popular in ComputerScienence


Reviews for CS 200


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/21/15
Menu Lecture 2 Questions from Lecture 1 Notes Formal Formal Systems Systems MIDLsystem and Languages English Languages Scheme C5150 Computer Science University ofViIginia David Evans Computer Science hm WWW c5 Virginia ecuevans Slsnrallzms mime Language 2 Cumiatg s g ensg If it takes 60 seconds to compute a photomosaic for Problem Set 1 today on a typical PC estimate how Are there any nonrecursive natural long It Will tke CSZOQast denlts In tokcompzugfp languages What would happen to a t e same p otomosaic ow ong WI It ta e In society that Spoke one gt 2008 2005 12 18 D ff rence In years 12 number of morith gt U 50 2 2 Number of monine 18 numberofdoublings a cording to Moore 5 Law gt2 quot 1218 4 60 seconds today Zdwblings by 2008 Not covered In Class 1after today you gt 60 at 2 2 2 2 lSsecmds In 2amp38 154 should be able to answer this gt exactgtinexact 60 2 2 2 2 33975 60 seconds today 4 doublings by 2011 3 75 seconds In 2011 oonunue forever Slsnfall znns ream 2 mutant 3 mummvrts sswsa 515 Fall zms ream 2 Language 4 FM Cmmsy a ea Formal Systems Set of symbols Primitives Formal SyStems Set of rules for manipulating symbols Hofstadter Rules of Production Rules of Inference Also Rules of Combination Slsnfall znns ream 2 mutant Computersuence swarm new image s E Computer scienc The MIU System Symbols M I U Rules of Production Rule I If you have a string ending in I you can add a U at the end Rule II Suppose you have Mx Then you may ad Max to your collection Rule III If III occurs in one of the strings in your collection you may make a new string with U in place ofIII Rule IV If UU occurs inside one of your strings you can drop it 31511 F 2 m 2 myqu 7 m Compuwt eyr SakiIce Survey Summary 26 Responses Years 6 First 1 Second 9 Third 8 Fourth Majors 10 Cognitive Science 4 Biology 3 Undecided 2 Economics Art History Chemistry Electrical Engineering Foreign Affairs Mathematics Neuroscience Psychology Sociology Previous computing 15 None 5 A Little 6 Lots MIU System Example Start with MUI produce MIU Rules of Production Rule I If you have a string ending in I you can add a U at the end Rule II Suppose you have Mx Then you ma add Mxx to yourcollection Rule III If III occurs in one of the strings in your collection you may ma e a new string with U in place 0 Ru e IV If UU oocurs inside one of your strings you can drop t 31511 F 2 m 2 myqu a m Compuwt eyr SakiIce Survey Summary Bodos vs Krispy Food 18 Bodos 9 Krispy Kreme Full survey responses will be posted over the weekend 31511 F 2 m 2 myqu m Compug ers m 31511 F 2 m 2 myqu m Compug ers m Languages 31511 F 2 m 2 myqu m compu gs m What is a language Webster A systematiemeans of communicating ideaseefed rngs by the use ofeenventie alieeel signs sounds gestures or marks having understood meanings 31511 F 2 m 2 myqu 2 m compu gs m Linguist s Definition Charles Yang A description of pairs 5 M where Sstands for sound or any kind of surface forms and M stands for meaning A theory of language must specify the properties of Sand M and how they are related an F 2 m 2 cm 3 m Computer Languages and Formal Systems What is the difference between a formal system and a language With a language the surface forms have meaning Caveat computer scientists often use language to mean just a set of surfaoe forn39s an F 2 m 2 cm 4 m Compu What are languages made of o Primitives almost all languages have these The simplest surface forms with meaning 0 Means of Combination all languages have these Like Rules of Production for Formal Systems Ways to make new surface forms from ones you already have 0 Means of Abstraction all powerful languages have these Ways to use simple surface forms to represent complicated ones cs 5 F ms 22 2 my 15 What is the longest word in the English language gm Write E It ftff 31511 F 2 m 2 myqu 5 m campugg suit According to Guinness floccipoccinihilipilification the act afrenderhg useless 31511 F 2 m 2 myqu 7 m Cumpmhl r sag Making Longer Words antifloccipoccinihilipilification the act of rendering not useless antiantifloccipoccinihilipilification the act of rendering not not useless as F 2 m2 myqu m Cumpmg r 39 9c Language is Recursive No matter what word you think is the longest word I can always make up a longer one word anti word If you have a word you can always make up a new word by adding anti in front Since the result is a word you can make a longer new word by adding anti in front again Recursive Definitions We can define things in terms of themselves Recursive definitions are different from circular definitions they eventually end with something real word a nti word W0rd floccipoccinihilipilification 31511 F 2 m 2 MW m Computer 5 mum 31511 F 2 m 2 MW 2 m Computer 5 mum Recursive Definitions Allow us to express infinitely Pany things starting with a ew This is powerful We will see lots of examples In this course Does English have these Primitives o eg anti oocipoocinihilipili cation Morphemes smallest units of meaning 0 eg anli opposite Means of combination eg Sentence Subject Ierb Object Precise rules but not the ones you learned in grammar sc 0 51439 a senlence with a praaasl39b39an is sumeb u39ng L with which we m7natput Winsmn Churchill 31511 F 2 m 2 MW 2 m Compuggr m 31511 F 2 m 2 MW 22 m Compuggr m Does English have these Means of abstraction Pronouns she he it they which etc Confusing since they don t always mean the same thing it depends on where they are used The these in the slide title is an abstraction for the three elements of language introduced 2 slides ago The they in the confusing sentence is an abstraction for pronouns How should we describe languages Detour History of Computer Programming 31511 F 2 m 2 MW 2 m compn x s m 31511 F 2 m 2 MW 24 m compn x s m Electronic Numerical Integrator and Computer Early WWII computer But not the world s rst PS4 Built to calculate bombing tables Memory size twenty 10 decimal digit accumulators 664 bits ENIAC 1946 12 mm Apollo Guidance Computer 1969 1 inch You 23 miles cs150 Fall 2005 Lecture 2 Language 25 Directions for Getti ng 6 Choose any regular accumulator ie Accumulator 9 Direct the Initiating Pulse to terminal 5 The initiating pulse is produced by the initiating unit39s a terminal each time the Eniac is started This terminal is usually by default plugged into Program Line 11 described later Simply connect a program cable from Program Line 11 to terminal 539on this Accumulator Set the Repeat Switch for Program Control 5 to 6 Set the Operation Switch for Program Control 5 to Set the ClearCorrect switch to C Turn on and clear the Eniac Normally when the Eniac is first started a clearing process is begun If the Eniac had been previously started or if there are random neons illuminated in the accumulators the Initial Clearquot button of the Initiating device can be pressed 9 Press the Initiating Pulse Switchquot that is located on the Initiating WN PONQMP deVIce 10Stand back tut C quot FRFS 93 PEE C5150 Fall 2005 Lecture 2 Language 25 m Computer Sciencre alumni u m Admiral Grace Hopper 19061992 0 Mathematics PhD Yale 1934 o Entered Navy 1943 0 First to program Mark I rst large computer 51 feet long 0 Wrote rst compiler 1952 program for programming quotNobody beI39e ied that I had a running compUtel39S compVerandnobody o Codesigner of COBOL most walld touch it They Mime commaS Widely used programming DUdgnydg language until a few years ago arithmetic cs150 Fall 2005 Lecture 2 Language 27 Dare and Doquot Guest on David Letterman tut C quot FRFS 93 PEE C5150 Fall 2005 Lecture 2 Language 25 m Computer Sciencre alumni u m Nanostick How far does light travel in 1 nanosecond gt de ne nanosecond 1 1000 1000 1000 1 billionth of a s gt de ne lightspeed 299792458 m s gt lightspeed nanosecond 149896229500000000 gt exactgtinexact lightspeed nanosecond 0299792458 just under 1 foot Dell machines in Small Hall have 18GHz Pentium 4 CPU GHz GigaHertz 1 Billion times per second They must finish a step before light travels 66 inches cs 150 Fall 2005 Lecture 2 Language 29 m Computer dewritte by hm ma mist Compiler translates J from code in a high Compiler level language to machine code Code maiC hirie can run DiScheme uses an interpreter An interpreter is like a compiler except it runs quickly and quietly on small bits of code at a time cs 150 Fall 2005 Lecture 2 Language 30 m Computer it LN John Backus 0 Chemistry major at UVA entered 1943 o Flunked out after second semester 0 Joined IBM as programmer in 1950 o Developed Fortran first commercially successful programming language and compiler C5150 Fall 2005 Lecture 2 Language 31 IBM 704 Fortran manual 1956 STATEMENT NORMAL SEQUENCING a l3 Next executable statement GO TO ii Statement n 7 EWEMTWWM last W F ASSIGN i T0 n Next executable statement 7 GO TO nhnzp ohm i Statement n1 IF ta nnzn3 Statement l11ltzl l3 as a less than or greater th SENSE LIGHT i 7 Next executable statement Statement nnZ as Sense Light i ON or OFF quot as Sense Switch i DOWN or UP 7 quot A in El IF SENSE LIGHT i nhn IF SENSE SWITCH i hm a m In It I n rutCo Pt C5150 Fall 2005 Lecture 2 Language 32 m m 1 r SCI n M Cquot Pita Ev Describing Languages Fortran language was described using English Imprecise Verbose lots to read Ad hoc Do 10 11 10 Assigns 1 10 to the variable D0101 Do 10 11 10 Loops for I 1 to 10 Often incorrectly blamed for loss of MarinerI Wanted a more precise way of describing a language C5150 Fall 2005 Lecture 2 Language 33 Backus Naur Form nontermna replacement We can replace nontermnawith replacement A Bmeans anywhere you have an A you can replace it with a B Some replacements are termnals a terminal is something that never appears on the left side of a rule A in C mP FS 9i99ESH C5150 Fall 2005 Lecture 2 Language 34 A tut manganese BNF Example Sentence NP Verb NP 33 NOW What are the Noun Dave term77315 Dave Scheme rocks sucks Noun Scheme How many Verb 3 rocks different things can we express Ver 33 SUCkS with this language 4 but only 2 are true BNF Example Sentence NP Verb NP Noun NP Noun and NP How many Noun 3 Dave different things can we express N 0 3 SCheme with this Verb rocks language Infinitely many Verb sucks Recursion is powerful A cs1so Fall zoos Lecture 2 Language 35 lm Computg cienkcen A cs1so Fall zoos Lecture 2 Language 35 IE Compgtgrnyhswc tenkoen VVhatis Computer Science CS150 Fall 2005 1 Introduction quot computer Science 41 vtu JNlVlZRSI39l39Y ff ViRt 39l N IE 5 Let AB and CD be the two given numbers not relatively prime It is required to find the greatest common measure of AB and CD If now CD measures AB since it also measures itself then CD is a common measure of CD and AB And it is manifest that it is also the greatest for no greater number than CD measures CD Euclid s Elements Book VII Proposition 2 3OOBC A CS150 Fall 2005 1 Introduction 3 Computgr SCICI IICC m flu Nl39lquotRSl39l3939rf39 lRGlle t The note on the in ected line is only difficult to you because it is so easy There is in fact nothing in it but you think there must be some grand mystery hidden under that word in ected Whenever from any point Withouta given line you draw a long to any point in the given line you have in ected a line upon a given 7539 Ada Byron age 19 letter to Annabella Acheson explaining Euclid 1834 A 7 CS150 Fall 2005 1 Introduction 4 Computgr SCICIVICC uriw leiksrn39gr mmxm What is the difference between Euclid w and Ada It depends on what your definition of is is Bill Gates at Microsoft s antitrust trial A V CS150 Fall 2005 1 Introduction 5 Computgr SCICIIICC with x139l Rlt139 gr39 mama Geometry vs Computer Science Geometry mathematics is about declarative knowledge what is If now CD measures AB since it also measures itself then CD isa common measure of CD and AB Computer Science has little to do with beige or translucent blue boxes called computers and is not a real science A 7 CS150 Fall 2005 1 Introduction 5 Computgr SCIEIflCC iii MW XlVliRSl39I39Ygl39 IRUINIA Computer Science How to knowledge 0 Ways of describing information rocesses com utations p p 0 Ways of predicting properties of information processes What kinds of things do we want to predict Science Engineering Other About reathings like bowling balls black holes antimatter electrons comets etc 0 Math and Computer Science are about fake things like numbers graphs functions lists etc Computer Science is a useful tool for doing csl urzll 2m5 unumunmn 7 ComRutng E EzIE cam Fall zuus lemmmm a gig Compiitgg iggggu Science Engineering 0 Understanding Nature through Engineering is deSign under Observation constraint Engineering is synthetic it strives to create what can be but it is constrained by nature by cost by concerns of safety reliability environmental impact manufacturability maintainability and many other such 39Ilities39 William Wulf real science but not a real science Esl rzll 2m5 lemdutmm 9 Comp ESl Fall zuus Linnummm 10 m Comm Apollo Guidance Computer 1969 we Why did they need to fit the 1 CUb39c Foot guidance computer in the rocket ESl Fall 2m5 l lntmdumun 11 Measuring Computers 0 1 bit smallest unit of information True or False 0 or 1 If we start with 2 possible choices and get 1 bit we can eliminate one of the choices i m Compmgs eswss ESl Fall mm 1 innummm 12 muc mmirsr szsiisa H h 2 Computing Power 19692005 0 muc power39 in Apollo Control Computer Units 0 Apollo Computer 30720 bits of changeable memory 0 Lab machines have 512 MB RAM 1 Megabyte 1024 Kilobyts 1 Kilobyte 1024 Bytes 1 Byte 8 bits H 512 MB gt 512 1024 1024 8 4294967296 43 Billion bits gt round 386 1024 1024 8 30720 139810 eimuum simuum Moore s Law computing power mm doubles every 18 months You have 105 404 times more power than AGC IIf Y quot uidance computer power is 1 inch 13 ComRuteI c c1151 rquot ms 1 1111111111quot we 1 llquot Computer My Constraints Computer Scientists Face So what is computer science Not like those for engineers wSeienee Cost weight physics etc No its about fake things like numbers not If 8 Million times what people had in 1969 abOUt ObseI39Van and undersmndlng nature isn t enough for you wait until 2007 and you 39 39 will have 20 Million times More like those for Musicians and Poets No we don t have to deal with engineering type constraints Imagination and Creativity 0 Liberal Art Complexity of what we can understand c1151 rquot ms 1 1111111111quot E 00mm c1151 rquot ms 1 1111111111quot m CDMPHESE Liberal Arts 1100 The Liberal Arts Illiberal Arts 96 I7 03 U arts for the nonfree pursued for economic B Q bers reasons 39 39 uadriVium 4 roads Liberal Arts TriVium 3 roads Q arts for the free pursued for intrinsic reasons smdyofmeaningin Rheum argument written expression comprehensm fdiscourse Gmm l Logic Arithmetic MUsic nu mber or ry W 0 me discovering quanu cauon mm o Astronomy We will see all of these in this class c1151 rquot ms 1 1111111111quot c1151 rquot ms 1 1111111111quot 1a compute 11m Course Expectations 9 C C5150 Fall 2005 1 Introduction 19 Im39 Course Road map Computer Science 3 c 1st Class 3 g from EuCIa and Ada g a 1390 PS 15 gr 3 Quantum Computing Lecture f i E and a the War0 Wide Web PS 67 g 5 4 V 2 or A c5150 Fall 2005 1 Introduction 20 frquot Computg tegkcen M What You Should Expect o The fourth coolest class at UVa Less cool than PHYE162 PHYE163 PHYE164 o This course will be consistent with the original notion of a Liberal Arts education 0 This course will be as consistent as possible with Mr Jefferson s vision for the University sassep JnoA quot2 Jo asaul padxa plnous not C5150 Fall 2005 1 Introduction 21 Like Drinking from a Firehose quot ii It may hUIt a little bit and a lot of water will go by you but you won t go away thirsty A 1 1 11 EITII39 ComP F w fn A c5150 Fall 2005 1 Introduction 22 mi Comptrth Sctegce Help Available 0 Me David Evans Call me Dave or Coach Office Hours will be posted after your surveys Aways available by email if I don t reply in 24 hours send again and complain 0 Assistant Coaches David Faulkner and Dan Upton 0 Web site httpwwwcsvirginiaeducslSO Everything goes on the web you should visit it often 0 Your classmates read the course pledge carefully What I Expect of You 1 Everything on the Course Pledge You should actually read it not just sign it you will lose points on PSl if your submission reveals that you didn t read it 2 You are a Jeffersonian Student 1 Believe knowledge is powerful 2Interested in lots of things ahead of your time 3Want to use what you learn to do good things 4Care more about what you learn than grades and degree requirements A c5150 Fall 2005 1 Introduction 23 m Compqtgr SCIeIIce m mm MW A c5150 Fall 2005 1 Introduction 24 runquot Computer Sctefgce xi n Background Expected Language Reasonable reading and writing in English Understanding of subject verb and object Math Whole numbers add subtract multiply divide Exponentiation logarithms we will review Logic and or not Computer Literacy read email browse web If I ever appear in expect anything else stop me 31511 F m 25 m Computer saws mum Shameless Pitch We need more students in this class Recruit your friends Recruit your enemies Recruit random CLAS students Iwi course action anyone who comes Friday into the class cs n r ms lnlrodudlon 27 What is the longest word in the English language Mm 29 m compu rsc a A Course for Everyone CLAS SEAS Commerce Arch etc o 15 2nd 3rd 4 5 11 Years Community Scholars Faculty No background expectedbut challenging even for students with lots of previous CS courses if you ve already taken CS415 talk to me first Computer Science future majorsbut worthwhile even if you don t take another CS course 31511 F m 25 m Computer saws mum First Main Theme Recursive Definitions cs n r ms lnlrodudlon za According to Guinness floccipoccinihilipilification the act 0frenden77g usee55 E F m 3 m compact saw


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Janice Dongeun University of Washington

"I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.