Computer Science S-111 Intensive Introduction To Computer .

10m ago
145 Views
5 Downloads
4.51 MB
559 Pages
Last View : 12d ago
Last Download : 1m ago
Upload by : Maxine Vice
Transcription

Computer Science S-111Intensive Introduction to Computer ScienceHarvard Summer School 2021David G. Sullivan, Ph.D.Unit 1: Getting Started1-1: Course Overview; Programming in Scratch . 11-2: Programming in Java . 201-3: Procedural Decomposition Using Simple Methods. 27Unit 2: Imperative Programming I2-1: Primitive Data, Types, and Expressions. 402-2: Definite Loops . 73Unit 3: Imperative Programming II3-1: Methods with Parameters and Return Values . 1023-2: Using Objects from Existing Classes . 1253-3: Conditional Execution . 1483-4: Indefinite Loops and Boolean Expressions . 171Unit 4: Processing Collections of Data4-1: Arrays . 1884-2: File Processing . 2184-3: Recursion . 230Unit 5: Object-Oriented Programming5-1: Classes as Blueprints: How to Define New Types of Objects. 2485-2: Inheritance and Polymorphism . 286Unit 6: Foundations of Data Structures6-1: Abstract Data Types . 3136-2: Recursion Revisited; Recursive Backtracking . 332Unit 7: Sorting and Algorithm Analysis7-1: Fundamentals . 3527-2: Divide-and-Conquer Algorithms, Distributive Sorting . 372Unit 8: Sequences8-1: Linked Lists . 3948-2: Lists, Stacks, and Queues. 427Unit 9: Trees and Hash Tables9-1: Binary Trees and Huffman Encoding . 4609-2: Search Trees . 4839-3: Heaps and Priority Queues . 5029-4: Hash Tables. 515Unit 10: Graphs . 531

Unit 1, Part IIntensive Introduction toComputer ScienceCourse OverviewProgramming in ScratchComputer Science S-111Harvard UniversityDavid G. Sullivan, Ph.D.Welcome to CS S-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 programs to expressthose algorithms fundamental data structures for imposing order on acollection of information the process of comparing data structures & algorithmsfor a given problemCSCI S-111, Summer 2021David G. Sullivan, Ph.D.1

Computer Science and Programming There are many different fields within CS, including: software systems computer architecture networking programming languages, compilers, etc. theory AI Experts in many of these fields don’t do much programming! However, learning to program will help you to developways of thinking and solving problems used in all fields of CS.A Rigorous Introduction Intended for: future concentrators who plan to take moreadvanced courses others who want a rigorous introduction no programming background required,but can also benefit people with prior background Allow for 20-30 hours of work per week start work early! come for help! don't fall behind!CSCI S-111, Summer 2021David G. Sullivan, Ph.D.2

CS 111 Requirements Lectures and sections attendance at both is required Ten problem sets (40%) part I "written" problems part II "programming" problems grad-credit students will have extra work on most assts. Four unit tests (25%) given at the end of lecture (see the schedule) Final exam (35%) Friday, August 6Textbooks Required: The CSCI S-111 Coursepack contains all of the lecture notes print it and mark it up during lecture Optional resource for the first half:Building Java Programs by Stuart Reges and Marty Stepp(Addison Wesley). Optional resource for the second half:Data Structures & Algorithms in Java, 2nd editionby Robert Lafore (SAMS Publishing).CSCI S-111, Summer 2021David G. Sullivan, Ph.D.3

Course Staff Instructor: Dave Sullivan Teaching Assistant (TA): Ashby Hobart See the course website for contact info. and office hours Piazza is your best bet for questions. For purely administrative questions: [email protected] will forward your email to the full course staffOther Details of the Syllabus Schedule: note the due dates and test dates no lectures or sections on most Wednesdays exceptions: July 7 (July 5 is off), July 14 (July 16 is off),August 4 (August 5 is off) Policies: 10% penalty for submissions that are one day late please don't request an extension unless it's an emergency! grading Please read the syllabus carefully and make sure that youunderstand the policies and follow them carefully. Let us know if you have any questions.CSCI S-111, Summer 2021David G. Sullivan, Ph.D.4

Algorithms In order to solve a problem using a computer,you need to come up with one or more algorithms. An algorithm is a step-by-step description of how toaccomplish a task. An algorithm must be: precise: specified in a clear and unambiguous way effective: capable of being carried outProgramming Programming involves expressing an algorithm in a form thata computer can interpret. We will primarily be using the Java programming language. one of many possible languages The key concepts of the course transcend this language.CSCI S-111, Summer 2021David G. Sullivan, Ph.D.5

What Does a Program Look Like? Here's a Java program that displays a simple message:public class HelloWorld {public static void main(String[] args) {System.out.println("hello, world");}} Like all programming languages, Java has a precise set of rulesthat you must follow. the syntax of the language To quickly introduce you to a number of key concepts,we will begin with a simpler language.Scratch A simple but powerful graphical programming language developed at the MIT Media Lab makes it easy to create animations, games, etc.CSCI S-111, Summer 2021David G. Sullivan, Ph.D.6

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.CSCI S-111, Summer 2021David G. Sullivan, Ph.D.7

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 takesa value (10, 1, etc.) a pull-down menu with choices (meow)Program Building Blocks: Statements (cont.) Clicking on any statement in a script executes the script. When rearranging blocks, dragging a statement drags itand any other statements below it in the stack. example: dragging the wait command belowCSCI S-111, Summer 2021David G. Sullivan, Ph.D.8

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 controlFlow 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.CSCI S-111, Summer 2021David G. Sullivan, Ph.D.9

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 executedWhat Does a Program Look Like? Recall our earlier Java program:public class HelloWorld {public static void main(String[] args) {System.out.println("hello, world");}} Here's the Scratch versionCSCI S-111, Summer 2021David G. Sullivan, Ph.D. and here's the result:10

Stage Coordinates Dimensions: 480 units wide by 360 units tall Center has coordinates of 0, 0What does this program draw?CSCI S-111, Summer 2021David G. Sullivan, Ph.D.11

How many changes would be neededto draw this figure instead? (What are they?)How could we draw this figure?CSCI S-111, Summer 2021David G. Sullivan, Ph.D.12

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?CSCI S-111, Summer 2021David G. Sullivan, Ph.D.13

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 nameCSCI S-111, Summer 2021David G. Sullivan, Ph.D.14

Program Building Blocks: Operators Operators create a new value from existing values/variables.Our Program with Variables and OperatorsCSCI S-111, Summer 2021David G. Sullivan, Ph.D.15

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:Program Building Blocks: Boolean Expressions Blocks with pointed edges produce boolean values: true or false Boolean operators:CSCI S-111, Summer 2021David G. Sullivan, Ph.D.16

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.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 executedCSCI S-111, Summer 2021David G. Sullivan, Ph.D.17

How can we deal with invalid user inputs?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.CSCI S-111, Summer 2021David G. Sullivan, Ph.D.18

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.CSCI S-111, Summer 2021David G. Sullivan, Ph.D.19

Unit 1, Part 2Programming in JavaComputer Science S-111Harvard UniversityDavid G. Sullivan, Ph.D.Programs and Classes In Java, all programs consist of one of more classes. For now: we'll limit ourselves to writing a single class you can just think of a class as a container for your program Example: our earlier program:public class HelloWorld {public static void main(String[] args) {System.out.println("hello, world");}} A class must be defined in a file with a name of the formclassname.java for the class above, the name would be HelloWorld.javaCSCI S-111, Summer 2021David G. Sullivan, Ph.D.20

Using an IDE An integrated development environment (IDE) is an applicationthat helps you develop programs. We’ll use the Dr. Java IDE. PS 0 told you how to obtain and install it. With an IDE, you do the following: use its built-in text editor to write your code instruct the IDE to compile the code turns it into lower-level instructions that can be run checks for violations of the syntax of the language instruct the IDE to run the program debug as needed, using the IDE's debugging toolsUsing Dr. JavaCSCI S-111, Summer 2021David G. Sullivan, Ph.D.21

Format of a Java Class General syntax:public class name {code goes here }where name is replaced by the name of the class. Notes: the class begins with a header:public class name the code inside the class is enclosed in curly braces({ and })Methods A method is a collection of instructions that performsome action or computation. Every Java program must include a method called main. contains the instructions that will be executed firstwhen the program is run Our example program includes a main method with asingle instruction:public class HelloWorld {public static void main(String[] args) {System.out.println("hello, world");}}CSCI S-111, Summer 2021David G. Sullivan, Ph.D.22

Methods (cont.) General syntax for the main method:public static void main(String[] args) {statement;statement; statement;}where each statement is replaced by a single instruction. Notes: the main method always begins with the same header:public static void main(String[] args) the code inside the method is enclosed in curly braces each statement typically ends with a semi-colon the statements are executed sequentiallyIdentifiers Used to name the components of a Java program likeclasses and methods. Rules: must begin with a letter (a-z, A-Z), , or can be followed by any number of letters, numbers, , or spaces are not allowed cannot be the same as a keyword – a word like classthat is part of the language itself (see the Resources page) Which of these are not valid identifiers?n1avgSalarynum valuescourse name2n Java is case-sensitive (for both identifiers and keywords). example: HelloWorld is not the same as helloWorldCSCI S-111, Summer 2021David G. Sullivan, Ph.D.23

Conventions for Identifiers Capitalize class names. example: HelloWorld Do not capitalize method names. example: main Capitalize internal words within the name. example: HelloWorldPrinting Textpublic class HelloWorld {public static void main(String[] args) {System.out.println("hello, world");}} Our program contains a single statement that prints some text. The printed text appears in a window known as the console.CSCI S-111, Summer 2021David G. Sullivan, Ph.D.24

Printing Text (cont.) The general format of such statements is:System.out.println("text");where text is replaced by the text you want to print. A piece of text like "Hello, world" is referred to asa string literal. string: a collection of characters literal: specified explicitly in the program ("hard-coded") A string literal must be enclosed in double quotes. You can print a blank line by omitting the string literal:System.out.println();Printing Text (cont.) A string literal cannot span multiple lines. example: this is not allowed:System.out.println("I want to print a stringon two lines."); Instead, we can use two different statements:System.out.println("I want to print a string");System.out.println("on two lines.");CSCI S-111, Summer 2021David G. Sullivan, Ph.D.25

println vs. print After printing a value, System.out.println"moves down" to the next line on the screen. If we don’t want to do this, we can use he next text to be printed will begin just after this text –on the same line. For example:System.out.print("I ");System.out.print("program ");System.out.println("with class!");is equivalent toSystem.out.println("I program with class!");Escape Sequences Problem: what if we want to print a string that includesdouble quotes? example: System.out.println("Jim said, "hi!""); this won’t compile. why? Solution: precede the double quote character by a \System.out.println("Jim said, \"hi!\""); \" is an example of an escape sequence. The \ tells the compiler to interpret the following characterdifferently than it ordinarily would. Other examples: \n a newline character (goes to the next line) \t a tab \\ a backslashCSCI S-111, Summer 2021David G. Sullivan, Ph.D.26

Unit 1, Part 3Procedural Decomposition(How to Use Methods to Write Better Programs)Computer Science S-111Harvard UniversityDavid G. Sullivan, Ph.D.Example Program: Writing Block Letters Here's a program that writes the name "DEE" in block letters:public class BlockLetters {public static void main(String[] args) {System.out.println("-----");System.out.println(" \\");System.out.println(" ");System.out.println(" ();System.out.println(" -----");System.out.println(" ");System.out.println(" ----");System.out.println(" ");System.out.println(" -----");System.out.println();System.out.println(" -----");System.out.println(" ");System.out.println(" ----");System.out.println(" ");System.out.println(" -----");}}CSCI S-111, Summer 2021David G. Sullivan, Ph.D.27

Example Program: Writing Block Letters The output looks like this:---- \ /---- ---- --- ---- ---- --- -----Code Duplicationpublic class BlockLetters {public static void main(String[] args) {System.out.println("-----");System.out.println(" \\");System.out.println(" ");System.out.println(" ();System.out.println(" -----");System.out.println(" ");System.out.println(" ----");System.out.println(" ");System.out.println(" -----");System.out.println();System.out.println(" -----");System.out.println(" ");System.out.println(" ----");System.out.println(" ");System.out.println(" -----");}} The code that writes an E appears twice – it is duplicated.CSCI S-111, Summer 2021David G. Sullivan, Ph.D.28

Code Duplication (cont.) Code duplication is undesirable. Why? Also, what if we wanted to create another word containing theletters D or E? What would we need to do? A better approach: create a command for writing each letter,and execute that command as needed. To create our own command in Java, we define a method.Defining a Simple Static Method We've already seen how to define a main method:public static void main(String[] args) {statement;statement; statement;} The simple methods that we'll define have a similar syntax:public static void name() {statement;statement; statement;} This type of method is known as static method.CSCI S-111, Summer 2021David G. Sullivan, Ph.D.29

Defining a Simple Static Method (cont.) Here's a static method for writing a block letter E:public static void rintln("}{ -----"); "); ----"); "); -----"); It contains the same statements that we used to write an Ein our earlier program. This method gives us a command for writing an E. To use it, we simply include the following statement:writeE();Calling a Method The statementwriteE();is known as a method call. General syntax for a static method call:methodName(); Calling a method causes the statements inside the methodto be executed.CSCI S-111, Summer 2021David G. Sullivan, Ph.D.30

Using Methods to Eliminate Duplication Here's a revised version of our program:public class BlockLetters2 {public static void rintln("}{ -----"); "); ----"); "); -----");public static void main(String[] args) {System.out.println("-----");System.out.println(" \\");System.out.println(" ");System.out.println(" s Can Be Defined In Any Order Here's a version in which we put the main method first:public class BlockLetters2 {public static void main(String[] args) {System.out.println("-----");System.out.println(" \\");System.out.println(" ");System.out.println(" ();writeE();System.out.println();writeE();}public static void rintln("}{ -----"); "); ----"); "); -----");} By convention, the main method should appear first or last.CSCI S-111, Summer 2021David G. Sullivan, Ph.D.31

Flow of Control A program's flow of control is the order in which its statementsare executed. By default, the flow of control: is sequential begins with the first statement in the main methodFlow of Control (cont.) Example: consider the following program:public class HelloWorldAgain {public static void main(String[] args) orld");System.out.println();.}} We can represent the flow of control using a flow ln("world");System.out.println();CSCI S-111, Summer 2021David G. Sullivan, Ph.D.32

Method Calls and Flow of Control When we call a method, the flow of control jumps to the method. After the method completes, the flow of control jumps backto the point where the method call was made.public class BlockLetters2 {public static void rintln("}{ -----"); "); ----"); "); -----");public static void main(String[] args) {System.out.println("-----");System.out.println(" \\");System.out.println(" ");System.out.println(" ();writeE();System.out.println();.Method Calls and Flow of Control (cont.) Here's a portion of the flowchart for our program:main method:writeE rintln(" -----");System.out.println(" ");.System.out.println();System.out.println(" -----");.CSCI S-111, Summer 2021David G. Sullivan, Ph.D.33

Another Use of a Static Methodpublic class BlockLetters3 {public static void writeD() {System.out.println("-----");System.out.println(" \\");System.out.println(" ");System.out.println(" /");System.out.println("-----");}public static void rintln("}{ -----"); "); ----"); "); -----");public static void main(String[] args) .println();writeE();}}Another Use of a Static Method (cont.) The code in the writeD method is only used once,so it doesn't eliminate code duplication. However, using a separate static method still makes theoverall program more readable. It helps to reveal the structure of the program.CSCI S-111, Summer 2021David G. Sullivan, Ph.D.34

Procedural Decomposition In general, methods allow us to decompose a problem intosmaller subproblems that are easier to solve. the resulting code is also easier to understand and maintain In our program, we've decomposed the task "write DEE"into two subtasks: write D write E (which we perform twice). We can use a structure diagram to show the decomposition:write DEEwrite Dwrite EProcedural Decomposition (cont.) How could we use procedural decomposition in printingthe following lyrics?Dashing through the snow in a one-horse open sleigh,O'er the fields we go, laughing all the way.Bells on bobtail ring, making spirits bright.What fun it is to ride and sing a sleighing song tonight!Jingle bells, jingle bells, jingle all the way!O what fun it is to ride in a one-horse open sleigh!Jingle bells, jingle bells, jingle all the way!O what fun it is to ride in a one-horse open sleigh!A day or two ago, I thought I'd take a ride,And soon Miss Fanny Bright was seated by my side.The horse was lean and lank; misfortune seemed his lot;We got into a drifted bank and then we got upsot.Jingle bells, jingle bells, jingle all the way!O what fun it is to ride in a one-horse open sleigh!Jingle bells, jingle bells, jingle all the way!O what fun it is to ride in a one-horse open sleigh!CSCI S-111, Summer 2021David G. Sullivan, Ph.D.35

Procedural Decomposition (cont.)Dashing through the snow in a one-horse open sleigh,O'er the fields we go, laughing all the way.Bells on bobtail ring, making spirits bright.What fun it is to ride and sing a sleighing song tonight!Jingle bells, jingle bells, jingle all the way!O what fun it is to ride in a one-horse open sleigh!Jingle bells, jingle bells, jingle all the way!O what fun it is to ride in a one-horse open sleigh!printVerse1printRefrainprintHalfRefrainA day or two ago, I thought I'd take a ride,And soon Miss Fanny Bright was seated by my side.The horse was lean and lank; misfortune seemed his lot;We got into a drifted bank and then we got rintVerse2printHalfRefrainCode Reuse Once we have a set of methods, we can use them to solveother problems. Here's a program that writes the name "ED":public class BlockLetters4 {// these methods are the same as beforepublic static void writeD() {.}public static void writeE() {.}public static void main(String[] args) {writeE();System.out.println();writeD();}}CSCI S-111, Summer 2021David G. Sullivan, Ph.D.36

Tracing the Flow of Control What is the output of the following program?public class FlowControlTest {public static void methodA() {System.out.println("starting method A");}public static void methodB() {System.out.println("starting method B");}public static void methodC() {System.out.println("starting method C");}public static void main(String[] args) {methodC();methodA();}}Methods Calling Methods The definition of one method can include calls to other methods. We've seen this already in the main method:public static void main(String[] args) {writeE();System.out.println();writeD();} We can also do this in other methods:public static void foo() {System.out.println("This is method foo.");bar();}public static void bar() {System.out.println("This is method bar.");}CSCI S-111, Summer 2021David G. Sullivan, Ph.D.37

Methods Calling Methods (cont.) What is the output of the following program?public class FlowControlTest2 {public static void methodOne() {System.out.println("boo");methodThree();}public static void methodTwo() {System.out.println("hoo");methodOne();}public static void methodThree() {System.out.println("foo");}public static void main(String[] args) {methodOne();methodThree();methodTwo();}}Comments Comments are text that is ignored by the compiler. Used to make programs more readable Two types:1. line comments: begin with // compiler ignores from // to the end of the line examples:// this is a commentSystem.out.println();// so is this2. block comments: begin with /* and end with */ compiler ignores everything in between typically used at the top of each source fileCSCI S-111, Summer 2021David G. Sullivan, Ph.D.38

Comments (cont.)/** DrawTriangle.java* Dave Sullivan ([email protected]s.bu.edu)* This program draws a triangle.*/block commentspublic class DrawTriangle {public static void main(String[] args) {System.out.println("Here's my drawing:");line comments// Draw the triangle using characters.System.out.println(" ");System.out.println("/ \\");System.out.println(" /\\");System.out.println(" /\\");System.out.println(" -------");}}Comments (cont.) Put comments: at the top of each file, naming the author and explainingwhat the program does at the start of every method other than main,describing its behavior inside methods, to explain complex pieces of code(this will be more useful later in the course) We will deduct points for failing to include the correct commentsand other stylistic problems.CSCI S-111, Summer 2021David G. Sullivan, Ph.D.39

Unit 2, Part 1Primitive Data, Variables,and Expressions;Simple Conditional ExecutionComputer Science S-111Harvard UniversityDavid G. Sullivan, Ph.D.Overview of the Programming esting/DebuggingCSCI S-111, Summer 2021David G. Sullivan, Ph.D.40

Example Problem: Adding Up Your Change Let's say that we have a bunch of coins of various types,and we want to figure out how much money we have. Let’s begin the process of developing a program thatdoes this.Step 1: Analysis and Specification Analyze the problem (making sure that you understand it),and specify the problem requirements clearly andunambiguously. Describe exactly what the program will do, without worryingabout how it will do it.CSCI S-111, Summer 2021David G. Sullivan, Ph.D.41

Step 2: Design Determine the necessary algorithms (and possibly otheraspects of the program) and sketch out a design for them. This is where we figure out how the program will solvethe problem. Algorithms are often designed using pseudocode. more informal than an actual programming language allows us to avoid worrying about the syntax of the language example for our change-adder problem:get the number of quartersget the number of dimesget the number of nickelsget the number of penniescompute the total value of the coinsoutput the total valueStep 3: Implementation Translate your design into the programming language.pseudocode code We need to lear

Intensive Introduction to Computer Science Course Overview Programming in Scratch Computer Science S-111 Harvard University David G. Sullivan, Ph.D. Unit 1, Part I Welcome to CS S-111! Computer science is not so much the science of computers as it is the