Lecture note.docx

46 Pages
Unlock Document

York University
Electrical Engineering and Computer Science
EECS 3101

CS 302 09/06/2011 Algorithm: set of rules used to solve a problem  The steps that describe how to solve a problem A detailed list of instructions that, when followed, result in some predictable/desired outcome Unambiguous: instructions must precisely say what to do for each step and where to go next Executable: can be carried out in practice Terminating: must eventually come to an end *The language we use to specify instruction should be precise and unambiguous (a formal language.) Natural Languages: languages humans use to communicate (e.g. English), which are full of ambiguity, for  example: Time flies like an arrow Fruit flies like a banana Formal Languages: precise and unambiguous languages used to communicate specific ideas. An algorithm transforms an initial state into some final state after executing a sequence of  operations How do we determine if an algorithm works as desired? We carefully perform the algorithm to see what results.  It works if we get the desired outcome (final state). We call this tracing. We’ll use the formal language Java to implement algorithms. What do we assume will happen when someone executes (performs) our algorithms? They will start at the beginning/top. They will do instructions in order, one after another, from top to bottom (we will call this sequencing). They will stop at the end/bottom. What makes an algorithm good? It works as desired. It is efficient (takes fewer steps). It is robust (handles errors well). It is user friendly. It is clear (well­structured, well­documented). It is general. Write a Java program that displays: “Hello World!” public class HelloWorld { public static void main (String[] args) { System.out.println(“Hello World”); } } What’s a class? It’s a container for a program’s code. What’s the name of the class above? HelloWorld *Start class names with an Uppercase letter What’s a file? It’s a container of related information that’s kept in secondary storage. The file storing this class should be named…? HelloWorld.java  The file name must be  identical  to the class name and have an extension of .java What’s a method? It’s a container for instructions that do a particular task or solve a particular part of a problem. *Java programs begin executing at the first instruction in the main method and stop after executing the last  instruction in main. What’s a statement? It’s an instruction!  There are many different kinds of statements and they end with a semicolon ;. What does Sytem.out.println do? It displays what’s between the parentheses. *println follows the output with a new line, where as print does not. We use Eclipse to make programs: Editing: entering text into a source file (.java) Compiling: translating the source file to a class file (.class) Running: using the JVM to execute the class file JVM­ Java Virtual Machine *Remember the lines in this program!  We will be using them again and again and again… Comments make program more understandable but are IGNORED by the computer Multiline comment: /*…….*/ Single line comment: //……. public class HelloWorld { public static void main (String[] args) { System.out.println(“Hello World”); } } What are braces, {}, used for? Recall a class and a method are containers.  Braces mark the beginning and ending of those  containers. Body: what’s between {} Headings: what comes before { *Make sure every opening brace{ has a matching closing brace }! What’s a reserved word? It’s a word defined by the PL to have a specific purpose public, class, static, void *Reserved words cannot be used for naming things. What’s an identifier? It’s a name we give to a class, a method, a variable, etc. Classes: HelloWorld, String, System Methods: main, println Variables: args, out *When choosing identifiers, naming rules must be followed and naming conventions should be followed. What’s a variable? It’s a container forsingle  value that can change.  It can store only one particultype  of data. How does the computer know the variable’s type? Before a variable can be used, its type is specified in a declaration statement.  The form is:  ; It a variable holds a whole number (e.g., 1000, ­22), what type should be used? int ▯ if the range of values is ­2 billion to +2 billion we call these integers If a variable holds a real number  Double ▯ if the range of values is +/­3.4*10^308  We call these floating­point value How is a variable given a value? Either by initializing it in the declaration statement or by using an assignment statement. *When reading an assignment statement replace the = with the word “gets”. For example: month = 12;  “month GETS 12” Form of the Assignment Statement:  = ; LHS of = is a variable RHS of = can be: a literal value: count = 112233; a variable: count = numberOfStudents; an expression: count = count +1; *Commas are NOT allowed in number!  112,233 results in a compile­tile error. *Tracing assignment statements 1. Figure out the value of the result on the right 2. Assign the value on the left Mixing Numeric Types Assigning an integer value into a floating­point variable works just fine double accountBalance = 1000; Assigning a floating­point value into an integer variable doesn’t work! int numberOfStudents = 22.11; Why? It’s like trying to cram a large object into a small box.  It doesn’t fit and that’s illegal. To do this you must use a type cast: int numberOfStudents = (int) 22.11; Does this work? int count = 0.0; NO! 0.0 is type double. What’s a constant? It’s a single value that CANNOT change (during execution).  It can either be an explicit value (called a  literal or hard­coded constant), or it can be a named constant (just called a constant). *Use named constants to make your program more understandable and easier to update/correct! Integer Constant: 11, 1234567, ­2 Floating point constant: .009, 8., 3.77 String constant: “string”, “howdy” Write a named constant for 3.2% interest rate. final double INTEREST_RATE = .032; Form: final   = ; *When naming constants use the final modifier, which tells the compiler this is the final value it gets and any  attempt to give it another results in a compile­time error. Expression It’s a combination of operators and operands that is evaluated to obtain a result value. Operator It’s a symbol (+,­,*,/) that instructs the computer to perform  Operand It’s a literal, constant, variable, result from another expression, a value returned by a method, or other  source of information to be processed. Basic Arithmetic Operations: Basic mathematical operations are defined for integer and floating­point types including: Binary operations: addition, subtraction, multiplication division, and remainder division. Unary operations: plus sign, minus sign *Division depends on the type of operands! 11/2.0= 5.5, 11.0/2=5.5, 11/2=5 (not 5.5), 0.0/2.0=0.0, 11/0.0= error! *Integers also haveremainder  division (% modulus). 11 % 4=3, 11 % 2=1 , 0 % 2=0, 10 % 20=10, 22 % 0= error! Adding or subtracting by 1 are common operations: count = count +1; // increment count = count – 1; // decrement Instead: count++; // increment count ­ ­ ; // decrement Use ++ and ­ ­ in statements by  themselves  (as shown) to avoid confusing results. Updating a variable based on its original value is another common operation: User input makes our programs more GENERAL! Algorithm for calculating programs (rectangle area): 1. Get input ▯ ( read length and width) 2. calculate result ▯ (area  is length*width) 3. output the result ▯ ( display area) Write a complete Java program that calculates the number of licks to get to the center of a Tootsie Roll  Tootsie Pop (TRTP) using this formula: 375*(diameter/length) diameter is the diameter of the TRTP length is the length of the tongue measured from its tip to the center of the top lip Java provides a pre­written class named Scanner, which allows you to get input from a user. 3 things needed to use pre­written classes: 1.) Tell the compiler where to get the code by using an import statement: import  java.util.Scanner; 2.) Make a software object by declaring and initializing it: Scanner stdIn = new Scanner(System.in); 3.)Use the software object by calling methods like these:  = stdIn.nextInt();  = stdIn.nextLine(); Character Type: char A char variable holds a single character (stored as an integer value) A char literal is surrounded by single quotes, for example:  ‘B’, ‘1’, ‘:’ What is output by this code: char first, middle, last; first = ‘J’; middle = ‘D’; last = ‘S’; System.out.prntln(“Hello, “ + first +middle + last +  String is another pre­written class from which we can make software objects (simply called objects). It  does the work of storing and doing tasks on sequences of characters such as words, phrases, etc. *Software objects make programmers more efficient! To use Strings: 1.) We don’t need an import statement (but could have): import java.lang.String; //automatically imported 2.)We do need to make a String object. String name1 = “Deb”; String name2 = new String(“Jim”); 3.) We can then ask the string object to do tasks: name1.charAt(0) String operations: Assignment and initialization using = Concentration using + String methods: By calling methods we can do many useful things with strings length: returns the number of characters in the string object String name = “Elmer Fudd”; System.out.print(name.length() + “ letters”); Output? 10 letters charAt: returns the character at the specified position System.out.println(name.charAt(6)); Output? F Java has two distinct categories of variables: Primitive variables: store one value of a basic type int age; double rate; char myInitial; Reference variable: store an address that says where to find it’s software object elsewhere in memory  (more later) Scanner consoleIn = new Scanner(System.in); String name = “Jim”; Note reference types are Java class names. To ask objects to do a task we use this form: The if statement: We make decisions in a program with if statement: Form: if () { } The condition gives a true/false result Execution depends on this result True: do the statement False: skip and do nothing! Achieving the full power of programming requires being able to control the flow of execution. There are 3 ways the flow of execution is controlled: Sequencing: (AKA Stepping) doing one thing after another from start to finish Deciding: (Selecting, Branching) doing something when a condition is true Looping: (AKA Repeating) doing something again and again as long as a condition remains true Given:   int year;      // >0, year Write a code fragment that displays if year is the current year if (year == 2011) { S.o.pln(“It’s the current year, “ + year); } Comparison Operators: ==, !=, <=, =, > The condition must be in parentheses. Braces surround the statement(s) that make up the body of the if statement.  Indentation is used to make  the body standout. We do not put a semicolon after the condition. Write a code fragment that displays whether or not the year is in the past. if (year  2011) { System.out.println(“The year ” + year + “ is in the future.”) } else if (year .step() .on() if (greenBall.on(1)) { greenBall.step(“right”); greenBall.step(“right”); } else if (greenBall.on(2)) { greenBall.step(“right”); } **Don’t use else when you want each if to be tested.** Write a code fragment to move ball onto cup 3 given 3 cups numbered 1 to 3, 1 green ball and 1 rainbow  ball. Assume these method for Ball class: .step() .on() .jump() Nesting: when you put one statement in the body of another as in this example which puts an if  statements inside of if statements. Use nesting to solve problems requiring multiple levels of decisions. Compound Conditions: AND Rule: use AND if all the conditions must be true for the compound condition to be true. OR Rule: use OR if just one of the conditions must be true for the compound condition to be true. Lazy? Stop after the first true condition. Logical Operators: allows us to compound conditions and reduce redundancy. ! ▯ NOT || ▯ OR && ▯ AND if (month == 10 && day == 31) { System.out.println(“It is Halloween.”); } Switch Statements: Parentheses surround the controlling expression, which must evaluate to an int or char value. The controlling expression can be just a single variable but Braces surround the list of cases that make up the body of the switch statement. Each case is followed by a case constant that’s an integer or character literal, which must be followed by a  colon. If no match is found with a case constant, then the default clause is executed.  If there is no default clause,  then the switch statement ends. **End in else when there’s only one possibility left. General algorithms often need to be able to repeat steps while a condition is true. We do this using a while loop: Form: while () {         } Use looping statements to make your code shorter, more readable and more general. Write a code fragment using a while loop that displays the numbers between 1 and MAX (inclusive), where  MAX is an integer constant. int count = 1; while (count <= MAX) { System.out.println(count); count++; } A key requirement when using looping is to ensure that the loop eventually comes to an end (i.e., it  terminates). Infinite Loop: a loop that doesn’t end. 3 forms of loop termination Counter Termination Repeat for a fixed number of times (definite) User­Query Termination Repeat as long as the user wants (indefinite) Sentinel value termination  Repeat until the sentinel value is reached (indefinite)  The   do   loop  Form: do {         } while (); Do the statements Evaluate the condition, which gives a true/false result True: repeat statements False: continue with any code after the loop Don’t forget the ; after the condition The body of a do loop always executes at least once. Write a code fragment using a do loop that displays the numbers between 1 and MAX (inclusive), where  MAX is an integer constant. int count = 1 do { System.out.println(count) count++ } while (count <= MAX); Under what circumstances will the do loop produce a different result than the while loop version? When MAX is 0 or negative the count always increments past MAX! Software Objects 1. Find it: i. Import jave.util.Random; 2. Make it:  Random ranGen = new Random(); • Creates a random number generator (using the clock as a seed) results in a  different number sequence each time you execute  Random ranGen = new Random (seed);  Creates a random number generator with a seed value ensures the same  number sequence each time you execute 3. Use it:   = ranGen.nextInt (N); • returns a random integer uniformly distributed from 0 up to N A very productive approach to programming is incremental development. Add a part, test, debug, and another part, test, debug,… An ineffective approach to debugging is programming by permutation. Debugging Advice: Determine the input sequence leading to the bug then use it to trace your code to the problem. Use output statements to locate the area of the bug and to see the values in variable, results of expression,  etc. Seed your random number generator to ensure it generates the same number sequence each time your  program is run.  The   for   loop : Translate the while code into one that uses a for loop: int count = 1; while (count <= MAX) { System.out.println(count); count++; } for (int count = 1; count <= MAX; count++) { System.out.println(count); } Use for loops for counter terminated loops, loops a specified amount of times. Parentheses surround the loop header, which has three parts each separated by semicolons. Braces surround the loop body, which has the statement(s). 1. Execution begins with initialization of the loop counter (index variable) 2. Next check if the condition is true, if it is false the loop ends 3. If the condition is true, then loop’s body is executed. 4. After the loops body I executed, then update the loop counter. Then go to step 2 to check the condition again! Operator Precedence: Precedence specifies the default order that operators are executed in an expression with multiple operators. 1. Grouping () 2. Unary ! + ­ 3. Multiplicative * / % 4. additive + ­ 5. relational  >= 6. equality == != 7. logical and && 8. logical or || 9. assignment = *= /= %= += ­= ROT: operator of the same precedence level do left to right When in doubt use parentheses We’ll provide a precedence table on exams. Arrays: allow a program to manipulate large amounts of data in an efficient and organized manner Array: List of values of the same type ordered by position Element: a piece of an array that stores one value Index: an integer corresponding to an element’s position Declaring and Constructing: []  = new []; Declare an array of doubles name nums having 11 elements: double[] nums = new double [11]; What is the type for nums[2]? Double For nums? Double[] OR array of doubles Write the code to assign the 3  element 11.9: nums[2] = 11.9; Element Access: [] the index can be anything that evaluates to an int Write the code to assign the middle element 22.5: nums[11/2] = 22.5; OR nums[5] = 22.5; Write the code to increment the value of the first element: nums[0]++;  Bounds Checking: The index is automatically checked to ensure it’s within the bounds of the array.  If it’s not, the program  crashes resulting in an ArrayIndexOutOfBoundsException! Write the code to display the last element: System.out.println(nums[10]); Length Property: .length this gives the number of elements in the array (which may be 0)! System.out.println(nums[nums.length – 1]); Write the code to display the entire array (make it general). for (int i = 0; i []  = {}; values in the list are separated with commas values must be compatible with the array’s element type the length of the array is the number of values in the list Declare an array of chars named letters having A – E: char[] letters = {‘A’, ‘B’, ‘C’, ‘D’, ‘E’}; Draw a memory diagram of the array: 0 1 2 3 4 A B C D E We’ve assumed that the arrays we’re using are completely filled with values, but this might not always be  the case. Partially­filled arrays: it is possible for only part of the array to be used. Used element: are kept at front of the array Unused element: are kept at the back Another variable: is used to store the number of used elements (currentSize) Write the code to display the last element of the counts array: System.out.println(counts[currentSize­1]); Write the code to display the used part of the counts array: for (int i = 0; i  largest { largest = a[i]; } } Shifting arrays: int x = //some index, 0 to currentSize­1 for (int i = x; i 
More Less

Related notes for EECS 3101

Log In


Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.