Computer Science 111 Introduction To Computer Science I .

10m ago
187 Views
22 Downloads
5.12 MB
413 Pages
Last View : 6d ago
Last Download : 9d ago
Upload by : Samir Mcswain
Transcription

Computer Science 111Introduction to Computer Science IBoston University, Fall 2020Unit 0: Course Overview; Intro. to Computational Problem-SolvingCourse Overview . 1Programming in Scratch . 7Unit 1: Functional Programming in PythonPython Basics . pre-lecture: 20 / in-lecture: 35Lists; Intro. to Functions . 38 / 43Making Decisions: Conditional Execution . 47 / 53Variable Scope; Functions Calling Functions. 60 / 66A First Look at Recursion . 71 / 77More Recursion . 81Recursive Design . 85 / 88Higher-Order Functions; List Comprehensions . 92 / 98More Recursive Design . 103Lists of Lists; ASCII Codes and the Caesar Cipher . 110 / 116Algorithm Design . 123Unit 2: Looking "Under the Hood"Binary Numbers . 130 / 138Gates and Circuits; Minterm Expansion; Bitwise Addition . 146 / 153Minterm Expansion Revisited . 169Circuits for Arithmetic; Assembly Language: A First Look . 173 / 181Loops in Assembly Language . 193 / 196Assembly Language: Loops Revisited; Functions . 200 / 206Assembly Language: Review; Using the Stack. 211 / 216Unit 3: Imperative Programming in PythonDefinite Loops; Cumulative Computations . 223 / 231Indefinite Loops (plus User Input) . 239 / 244Program Design with Loops . 252Nested Loops . 259 / 262References and Mutable Data. 273 / 2812-D Lists; References Revisited . 292 / 296Unit 4: Object-Oriented Programming in PythonUsing Objects; Working with Text Files . 305 / 312Classes and Methods . 319 / 330More Object-Oriented Programming; Comparing and Printing Objects . 341 / 345Dictionaries and Markov Models . 352Board Objects for Connect Four. 363Inheritance . 369AI for Connect Four . 374Unit 5: Topics from CS TheoryFinite-State Machines . 389Algorithm Efficiency and Problem Hardness . 402Table of Hmmm Instructions . 412The slides in this book are based in part on notes fromthe CS-for-All curriculum developed at Harvey Mudd College.

Introduction to Computer Science ICourse OverviewComputer Science 111Boston UniversityWelcome to CS 111!Computer science is not so much the science of computersas it is the science of solving problems using computers.Eric Roberts This course covers: the process of developing algorithms to solve problems the process of developing computer programsto express those algorithms other topics from computer science and its applicationsCS 111, Boston UniversityFall 20201

A Breadth-Based Introduction Five major units: weeks 0-4:computational problem solvingand "functional" programming weeks 4-7:a look "under the hood"(digital logic, circuits, etc.) weeks 7-9:imperative programming weeks 9-12:object-oriented programming weeks 12-end: topics from CS theory In addition, short articles on other CS-related topics. Main goals: to develop your computational problem-solving skills including, but not limited to, coding skills to give you a sense of the richness of computer scienceA Rigorous Introduction Intended for: CS, math, and physical science concentrators others who want a rigorous introduction no programming background required,but can benefit people with prior background Allow for 10-15 hours of work per week start work early! Less rigorous alternatives include: CS 101: overview of CS CS 103: the Internet CS 105: databases and data mining CS 108: programming with a focus on web apps for more -coursesCS 111, Boston UniversityFall 20202

Course Materials Required: The CS 111 Coursepack use it during pre-lecture and lecture – need to fill in the blanks! PDF version is available on Blackboard recommended: get it printed one local option: FedEx Office (Cummington & Comm Ave) Required in-class software: Top Hat Pro platform used for pre-lecture quizzes and in-lecture exercises create your account and purchase a subscription ASAP(see Lab 0 for more details) Optional textbook: CS for Allby Alvarado, Dodds, Kuenning, and Libeskind-Hadas rScience/dp/1590282906Learn from Anywhere Rotations for those who choose to attend in person.Also live-streamed and recorded. Initial rotations based on LfA status on Student Link update today if needed! if your LfA status is In Person but you don't plan to attendthis lecture in person, email me today Initial rotations posted on Blackboard by Thursday night. may be adjusted later please check Blackboard before coming to lecture See the syllabus for: more info about our LfA approach expectations for students who wish to attend in personCS 111, Boston UniversityFall 20203

Preparing for Lecture Short video(s) and/or readings fill in the blanks as you watch the videos! Short pre-lecture quiz complete online by 10 a.m. of the day of lecture(unless noted otherwise) won't typically be graded for correctness your work should show that you've prepared for lecture no late submissions accepted Preparing for lecture is essential! gets you ready for the lecture questions and discussions we won't cover everything in lectureCourse Websitewww.cs.bu.edu/courses/cs111 not the same as the Blackboard site for the course use Blackboard to access info. on: the pre-lecture videos/readings the pre-lecture quizzesposted by 36 hoursbefore lecture links to the recorded lectures – posted by end of dayCS 111, Boston UniversityFall 20204

Labs Will help you prepare for and get started on the assignments Will also reinforce essential skills Will also have rotations and be live-streamed.At least one lab each week will be recorded. First lab meetings during the week of Sept. 14 ASAP: Complete Lab 0 (on the course website) short tasks to prepare you for the semesterGrading1. Weekly problem sets final project (45%)2. Exams online with two time options (see syllabus) may require you to use a webcam and microphone access to cell phone with data plan recommended two midterms (25%) final exam (25%) wait until you hear its dates/times from me;initial info posted by Registrar will likely be incorrect;make sure you're available for the entire exam period!3. Pre-lecture quizzes (5%) full credit if you answer 85% of the questions (see syllabus)To pass the course, you must earn a passing grade oneach of components 1 and 2.CS 111, Boston UniversityFall 20205

Course Staff Instructors:Dave Sullivan (A1, C1, D1 lectures)Vahid Azadeh-Ranjbar (B1 lecture) Teaching Fellows/Assistants (TF/TAs)plus Undergrad Course Assistants (CAs) see the course website for names and tml Office-hour calendar:http://www.cs.bu.edu/courses/cs111/office hours.shtml For questions: post on Piazza or [email protected] Programming involves expressing an algorithm in a form thata computer can interpret. We will primarily use the Python programming language. one of many possible languages widely used The key concepts of the course transcend this language. You can use any version of Python 3 not Python 2 see Lab 0 for details Python is a relatively simple language,but we're going to start with something even simpler!CS 111, Boston UniversityFall 20206

Programming in ScratchComputer Science 111Boston UniversityScratch A simple but powerful graphical programming language developed at the MIT Media Lab makes it easy to create animations, games, etc.CS 111, Boston UniversityFall 20207

Scratch Basics Scratch programs (scripts) control characters called sprites. Sprites perform actions and interact with each other on the stage.the stagebuildingblocksforprograms/scriptsdrag building blocks here to create scriptsProgram Building Blocks Grouped into color-coded categories: The shape of a building block indicates where it can go.CS 111, Boston UniversityFall 20208

Program Building Blocks: Statements Statement a command or action Statements have bumps and/or notchesthat allow you to stack them. each stack is a single script A statement may have: an input area that takes a value (10, 1, etc.) a pull-down menu with choices (meow) Clicking on any statement in a script executes the script.Flow of Control Flow of control the order in which statements are executed By default, statements in a script are executed sequentiallyfrom top to bottom when the script is clicked. Control blocks (gold in color) allow you to affect theflow of control. simple example: the wait statement above pausesthe flow of controlCS 111, Boston UniversityFall 20209

Flow of Control: Repetition Many control statements are C-shaped, which allows themto control other statements. Example: statements that repeat other statements. Drag statements inside the opening to create a repeating stack.forms In programming, a group of statements that repeatsis known as a loop.Flow of Control: Responding to an Event Hat blocks (ones with rounded tops) can be put on top of a script. They wait for an event to happen. when it does, the script is executedCS 111, Boston UniversityFall 202010

Stage Coordinates Dimensions: 480 units wide by 360 units tall Center has coordinates of 0, 0What does this program draw?Note: In the current version of Scratch,clear has been renamed erase all.CS 111, Boston UniversityFall 202011

How many changes would be neededto draw this figure instead? (What are they?)How could we draw this figure?CS 111, Boston UniversityFall 202012

Flow of Control: Repeating a Repetition! One loop inside another loop! known as a nested loop How many times is the move statement executed above?Making Our Program Easier to Change It would be nice to avoid having to manually changeall of the numbers. Take advantage of relationships between the numbers. what are they?CS 111, Boston UniversityFall 202013

Program Building Blocks: Variables A variable is a named location in the computer's memorythat is used to store a value. Can picture it as a named box: To create a variable:Using Variables in Your Programnote: you must drag a variable into place, not type its nameCS 111, Boston UniversityFall 202014

Program Building Blocks: Operators Operators create a new value from existing values/variables.Our Program with Variables and OperatorsCS 111, Boston UniversityFall 202015

Getting User Input Use the ask command from the sensing category. The value entered by the user is stored in the special variableanswer, which is also located in the sensing category. Allowing the user to enternumSides and numCopies:Our Program With User InputsCS 111, Boston UniversityFall 202016

Program Building Blocks: Boolean Expressions Blocks with pointed edges produce boolean values: true or false Boolean operators:Flow of Control: Conditional Execution conditional execution deciding whether to executeone or more statements on the basis of some condition There are C-shaped control blocks for this: They have an input area with pointed edges for the condition.CS 111, Boston UniversityFall 202017

Flow of Control: Conditional Execution (cont.) If the condition is true: the statements under the if are executed the statements under the else are not executed If the condition is false: the statements under the if are not executed the statements under the else are executedHow can we deal with invalid user inputs?CS 111, Boston UniversityFall 202018

Final version We use two if-else statements tocheck for invalid inputs: one checks for numSides 3 one checks for numCopies 1 If an invalid input is found, we: show the sprite have the sprite sayan error message end the program Otherwise, we continue with the restof the program.More Info on Scratch We're using the latest version:https://scratch.mit.edu/projects/editor Creating a Scratch account is not required for this course.CS 111, Boston UniversityFall 202019

Pre-LectureGetting Started With PythonComputer Science 111Boston UniversityInteracting with Python We're using Python 3 (not 2). see Lab 0 for how to install and configure Spyder Two windows in Spyder: the editor and the IPython consoleThe prompt shows thatthe interpreter is waitingfor you to entersomething.CS 111, Boston UniversityFall 202020

Arithmetic in Python Numeric operators include: addition- subtraction* multiplication/ division** exponentiation% modulus: gives the remainder of a division Examples: 6 * 742 2 ** 416 17 % 21 17 % 3Arithmetic in Python (cont.) The operators follow the standard order of operations. example: multiplication before addition You can use parentheses to force a different order. Examples: 2 3 * 5 (2 3) * 5CS 111, Boston UniversityFall 202021

Data Types Different kinds of values are stored and manipulated differently. Python data types include: integers example: 451 floating-point numbers numbers that include a decimal example: 3.1416Data Types and Operators There are really two sets of numeric operators: one for integers (ints) one for floating-point numbers (floats) In most cases, the following rules apply: if at least one of the operands is a float, the result is a float if both of the operands are ints, the result is an int One exception: division! Examples:CS 111, Boston UniversityFall 202022

Two Types of Division The / operator always produces a float result. examples: 5 / 31.6666666666666667 6 / 3Two Types of Division (cont.) There is a separate // operator for integer division. 6 // 32 Integer division discards any fractional part of the result: 11 // 52 5 // 3 Note that it does not round!CS 111, Boston UniversityFall 202023

Another Data Type A string is a sequence of characters/symbols surrounded by single or double quotes examples: "hello" 'Picobot'CS 111, Boston UniversityFall 202024

Pre-LectureProgram Building Blocks:Variables, Expressions, StatementsComputer Science 111Boston UniversityVariables Variables allow us to store a value for later use: temp 77 (temp - 32) * 5 / 925.0CS 111, Boston UniversityFall 202025

Expressions Expressions produce a value. We evaluate them to obtain their value. They include: literals ("hard-coded" values):3.1416'Picobot' variablestemp combinations of literals, variables, and operators:(temp - 32) * 5 / 9Evaluating Expressions with Variables When an expression includes variables, they are firstreplaced with their current value. Example:(temp - 32) * 5 / 9( 77 - 32) * 5 / 945* 5 / 9225/ 925.0CS 111, Boston UniversityFall 202026

Statements A statement is a command that carries out an action. A program is a sequence of statements.quarters 2dimes 3nickels 1pennies 4cents quarters*25 dimes*10 nickels*5 penniesprint('you have', cents, 'cents')Assignment Statements Assignment statements store a value in a variable.temp 20 is known as theassignment operator General syntax:variable expression Steps:1) evaluate the expression on the right-hand side of the 2) assign the resulting value to the variable on theleft-hand side of the Examples:int quarters 10intintCS 111, Boston Universityquarters val 25 * quarters25 * 10250Fall 202027

Assignment Statements (cont.) We can change the value of a variable by assigning ita new value. Example:num1 100num2 120num1num1 50100num2120num1num2120num1 num2 * 2num1num2120num2 60num1num2Assignment Statements (cont.) An assignment statement does not create a permanentrelationship between variables. You can only change the value of a variableby assigning it a new value!CS 111, Boston UniversityFall 202028

Assignment Statements (cont.) A variable can appear on both sides of the assignmentoperator! Example:sum 13val 30sum13val3030sum sum val13 3043sumvalval val * 2sumvalCreating a Reusable Program Put the statements in a text file.# a program to compute the value of some coinsquarters 2dimes 3nickels 1pennies 4# number of quarterscents quarters*25 dimes*10 nickels*5 penniesprint('you have', cents, 'cents') Program file names should have the extension .py example: coins.pyCS 111, Boston UniversityFall 202029

Print Statements print statements display one or more values on the screen Basic syntax:print(expr)orprint(expr1, expr2, exprn)where each expr is an expression Steps taken when executed:1) the individual expression(s) are evaluated2) the resulting values are displayed on the same line,separated by spaces To print a blank line, omit the expressions:print()Print Statements (cont.) Examples: first example:print('the results are:', 15 5, 15 – 5)'the results are:'2010output: the results are: 20 10(note that the quotes around the string literal are not printed) second example:cents 89print('you have', cents, 'cents')output:CS 111, Boston UniversityFall 202030

Variables and Data Types The type function gives us the type of an expression: type('hello') class 'str' type(5 / 2) class 'float' Variables in Python do not have a fixed type. examples: temp 25.0 type(temp) class 'float' temp 77 type(temp)CS 111, Boston UniversityFall 202031

Pre-LectureStringsComputer Science 111Boston UniversityStrings: Numbering the Characters The position of a character within a string is known as its index. There are two ways of numbering characters in Python: from left to right, starting from 00 1 2 3 4'Perry' from right to left, starting from -1-5 -4 -3 -2 -1'Perry' 'P' has an index of 0 or -5 'y' has an index ofCS 111, Boston UniversityFall 202032

String Operations Indexing: string [index ] name 'Picobot' name[1]'i' name[-3] Slicing (extracting a substring): string [ start : end ] name[0:2]'Pi' name[1:-1] name[1:]'icobot' name[:4]fromthis indexup to butnot includingthis indexString Operations (cont.) Concatenation: string1 string2 word 'program' plural word 's' plural'programs' Duplication: string * num copies 'ho!' * 3'ho!ho!ho!' Determining the length: len(string) name 'Perry' len(name)5 len('')# an empty string – no characters!0CS 111, Boston UniversityFall 202033

Skip-Slicing Slices can have a third number: string [start : end : stride length ]s 'boston university terriers'0123456 s[0:8:2]'bso '78910 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25# note the space at the end!Skip-Slicing (cont.) Slices can have a third number: string [start : end : stride length ]s 'boston university terriers'012345678910 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 s[5:0:-1]CS 111, Boston UniversityFall 202034

Python BasicsComputer Science 111Boston UniversityWhat is the output of the following program?x 15name 'Picobot'x x // 2print('name', x, type(x))CS 111, Boston UniversityFall 202035

What about this program?x 15name 'Picobot'x 7.5print(name, 'x', type(x))What are the values of the variablesafter the following code runs?xyxzxCS 111, Boston University 56y 3x yx 2x55y6Fall 2020zComplete this tableto keep track ofthe values ofthe variables!36

What is the value of s after the following code runs?s 'abc's ('d' * 3) ss s[2:-2]Skip-Slicing Slices can have a third number: string [start : end : stride length ]s 'boston university terriers'012345 s[0:8:2]'bso '678910 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25# note the space at the end! s[5:0:-1]'notso' s['viti'::]# what numbers do we need? s[12:21:8] s[21::3]CS 111, Boston UniversityFall 2020# what do we get?37

Pre-LectureListsComputer Science 111Boston UniversityLists Recall: A string is a sequence of characters.'hello' A list is a sequence of arbitrary values (the list's elements).[2, 4, 6, 8]['CS', 'math', 'english', 'psych'] A list can include values of different types:['Star Wars', 1977, 'PG', [35.9, 460.9]]CS 111, Boston UniversityFall 202038

List Ops String Ops (more or less) majors ['CS', 'math', 'english', 'psych'] majors[2]'english' majors[1:3] len(majors) majors ['physics']['CS', 'math', 'english', 'psych', 'physics'] majors[::-2]Note the difference! For a string, both slicing and indexing produce a string: s 'Terriers' s[1:2]'e' s[1]'e' For a list: slicing produces a list indexing produces a single element – may or may not be a list info ['Star Wars', 1977, 'PG', [35.9, 460.9]] info[1:2] info[2:][1977] info[1] info[-1][-1]1977460.9 info[-1] info[0][-4]CS 111, Boston UniversityFall 202039

Pre-LectureIntroduction to FunctionsComputer Science 111Boston UniversityDefining a Functionthe function's namedef triple(x):return 3*xmust indentCS 111, Boston Universityx is the input or parameterthis line specifies whatthe function outputs (or returns)– in this case, 3 times the inputFall 202040

Multiple Lines, Multiple Parametersdef circle area(diam):""" Computes the area of a circlewith a diameter diam."""radius diam / 2area 3.14159 * (radius**2)return areadef rect perim(l, w):""" Computes the perimeter of a rectanglewith length l and width w."""return 2*l 2*wWhat is the output of this code?x3def calculate(x, y):a yb x 1return a b 3y2ab(complete the rest on the next slide)print(calculate(3, 2))The values in the function call areassigned to the parameters.In this case, it's as if we had written:x 3y 2CS 111, Boston UniversityFall 202041

What is the output of this code? (cont.)xyabdef calculate(x, y):a yb x 1return a b 3print(calculate(3, 2))The output/return value: is sent back to where the function callwas made replaces the function callThe program picks up where it left offwhen the function call was made.CS 111, Boston UniversityFall 202042

ListsIntro. to FunctionsComputer Science 111Boston UniversityWhat is the output of the following program?mylist [1, 2, [3, 4, 5]]print(mylist[1], mylist[1:2])CS 111, Boston UniversityFall 202043

Note the difference! For a string, both slicing and indexing produce a string: s 'Terriers' s[1:2]'e' s[1]'e' For a list: slicing produces a list indexing produces a single element – may or may not be a list info ['Star Wars', 1977, 'PG', [35.9, 460.9]] info[1:2] [1977]35.9 info[1]1977 info[-1][35.9, 460.9]How could you fill in the blankto produce [105, 111]?intro cs [101, 103, 105, 108, 109, 111]dgs courses CS 111, Boston UniversityA.intro cs[2:3] intro cs[-1:]B.intro cs[-4] intro cs[5]C.intro cs[-4] intro cs[-1:]D.E.more than one of the abovenone of the aboveFall 202044

Functions With String Inputsdef undo(s):""" Adds the prefix "un" to the input s. """return 'un' sdef redo(s):""" Adds the prefix "re" to the input s. """return 're' s Examples: undo('plugged') undo('zipped') redo('submit') redo(undo('zipped'))What is the output of this code?xyabdef calculate(x, y):a yb x 1return a * b - 3print(calculate(4, 1))CS 111, Boston UniversityFall 202045

Practice Writing a Function Write a function avg first last(values) that: takes a list values that has at least one element returns the average of the first and last elements examples: avg first last([2, 6, 3])2.5# average of 2 and 3 is 2.5 avg first last([7, 3, 1, 2, 4, 9])8.0# average of 7 and 9 is 8.0def avg first last(values):first last returnExtra practice from the textbook authors!pi [3,1,4,1,5,9]L [ 'pi', "isn't", [4,2] ]M 'You need parentheses for chemistry !'048Part 1121620242832Part 2What is len(pi)What is L[0]What is len(L)What is L[0:1]What is len(L[1])What is L[0][1]What is pi[2:4]What slice of M is 'try'?What slice of pi is [3,1,4]What isWhat slice of pi is [3,4,5]Extra!These two aredifferent!is 'shoe'?M[9:15]What is M[::5]What are pi[0]*(pi[1] pi[2]) and pi[0]*(pi[1:2] pi[2:3]) ?These two are different, too CS 111, Boston UniversityFall 202046

Pre-LectureMaking Decisions:Conditional ExecutionComputer Science 111Boston UniversityConditional Execution Conditional execution allows your code to decide whetherto do something, based on some condition. example:def abs value(x):""" returns the absolute value of input x """if x 0:x -1 * xreturn x examples of calling this function from the Shell: abs value(-5)5 abs value(10)CS 111, Boston UniversityFall 202047

Simple Decisions: if Statements Syntax:if condition:true blockwhere: condition is an expressionthat is true or false true block is one or moreindented statements Example:def abs value(x):if x 0:x -1 * xreturn x# true blockTwo-Way Decisions: if-else Statements Syntax:if condition:true blockelse:false block Example:def pass fail(avg):if avg 60:grade 'pass'else:grade 'fail'return gradeCS 111, Boston University# true block# false blockFall 202048

Expressing Simple Conditions Python provides a set of relational operatorsfor making comparisons:operator nameless thanexamples greater thannum 60state 'Ohio' less than or equal toaverage 85.8 greater than or equal toname 'Jones'val 10price 10.99equal to(don't confuse with ) ! total 10letter 'P'not equal toage ! my ageBoolean Values and Expressions A condition has one of two values: True or False. 10 20True "Jones" "Baker"False True and False are not strings. they are literals from the bool data type type(True) class 'bool' type(30 6) An expression that evaluates to True or False is known asa boolean expression.CS 111, Boston UniversityFall 202049

Forming More Complex Conditions Python provides logical operators for combining/modifyingboolean expressions:nameandexample and meaningage 18 and age 35True if both conditions are True, and False otherwiseorage 3 or age 65True if one or both of the conditions are True;False if both conditions are Falsenotnot (grade 80)True if the condition is False, and False if it is TrueA Word About Blocks A block can contain multiple statements.def welcome(class):if class 'frosh':print('Welcome to BU!')print('Have a great four years!')else:print('Welcome back!')print('Have a great semester!')print('Be nice to the frosh students.') A new block begins whenever we increase the amountof indenting. A block ends when we either: reach a line with less indenting than the start of the block reach the end of the programCS 111, Boston UniversityFall 202050

Multi-Way Decisions The following function doesn't work.avggradedef letter grade(avg):if avg 90:grade 'A'if avg 80:grade 'B'if avg 70:grade 'C'if avg 60:grade 'D'else:grade 'F'return grade example: letter grade(95)Multi-Way Decisions (cont.) Here's a fixed version:avggradedef letter grade(avg):if avg 90:grade 'A'elif avg 80:grade 'B'elif avg 70:grade 'C'elif avg 60:grade 'D'else:grade 'F'return grade example: letter grade(95)CS 111, Boston UniversityFall 202051

Multi-Way Decisions: if-elif-else Statements Syntax:if condition1:true block for condition1e

Introduction to Computer Science I Course Overview Computer Science 111 Boston University Welcome to CS 111! Computer science is not so much the science of computers as it is the science of solving pro