Lectures

No prep

• Register in Piazza.
• Bring your laptop to lab/discussion session this week and next to install java, eclipse and svn.
• Set up Turing's Craft using Code Lab Setup
• If you want to take proficiency exam, make a request.
• Come to all classes prepared, doing the pre-lecture activities ahead of time.
• Note that lectures will often begin with questions from the readings.

• Read the course policies
• Reading 000: About the readings
• Reading 001: Intro to Algorithms
• Reading 002: Intro to Algorithms (cont.)

• Reading 003: Architecture and Program Development
• Reading 004: Data Modeling
• Sign up for Turing's Craft
• Read VonNeumann.pdf
• Watch the video
• a copy of the sheet in the video.

• Reading 005: Development Cycle
• ch1.3 - The Java Virtual Machine
• ch1.4 - Fundamental Building Blocks of Programs
• Sign up for Turing's Craft and then complete the practice questions

• algorithm
• composition
• Java virtual machine
• variables and types
• control structures
• primitives
• subroutines

• Read: ch2.1 Syntax, Semantics, Pragmatics
• ch3.2 Programming is difficult (pseudocode, testing, debugging)
• Complete Turing's Craft questions.

• Architecture and Algorithm Development
• Developing a program is a four-step cycle:
  1. edit (write a new program or change an existing program)
  2. compile (encode program in bit string form)
  3. run program through tests to see how well it works
  4. debug to find errors and deduce their cause

• TC exercises 2.2
• Jason 3 - Types, Variables, and Expressions
• ch2.2 Primitive, types, literals, variables
• A 13-minute video showing the Eclipse, Subversion, checkout, commit, workflow for CS 125 MPs

• Starting java programming...
• Variables, Types, Operators, Expressions, Statements, Variable declaration and assignment.

• TC exercises 2.3
• ch2.3 Strings, Objects, Enums, and Subroutines
• Jason 4: Type checking, Input/Output, and Programming Style

• memory allocation
• reference variable
• dot operator
• difference between instantiation and creation
  (which requires allocation) of an object
• distinction between a class (description)
  and object, the allocation

• s1.equals(s2)
• s1.equalsIgnoreCase(s2)
• s1.length()
• s1.charAt(N)
• s1.substring(N, M)
• s1.indexOf(s2)
• s1.compareTo(s2)
• s1.toUpperCase()
• s1.trim()
• +

• TextIO
• System.out.println

• TC exercises 2.4
• ch2.3 Strings, Objects, Enums, and Subroutines
• ch2.4 Text Input and Output

• String functions
• Passwords, Facebook and Google - Powered by Strings

• TC exercises 2.5
• Jason 5 - Boolean Expressions, Simple Conditionals, and Statements
• ch2.5 Operators, expressions and casting

• Expressions, conditionals, and statements
• Boolean expressions: != ==
• Logical operators
• Relational operators:
  • Short circuiting
  • Using relational and logical operators together
  • Conditional introduced and statement redefined

MP 2 is out.

• TC exercises 3.1 and 3.5
• Jason 6 - Compound Statements, Scope, and Advanced
• Conditionals
• ch3.1 Compound Statements, Simple Loops
• ch3.5 If revisited

• Conditionals
• Compound statements
• Conditionals with compound statements
• Scope:
  • Examples of scope in conditionals
  • If-else statement
  • The dangling if-else problem

• TC exercises 3.3 and 3.4
• Jason 7- Loops
• ch3.3 Looping: do while (break and continue statements are not going to be used in this course)

• Loops: repeating code statements many times:
  • "While" loop:
    • single statement
    • compound statement
    • do while
    • common errors
  • "For" loop
• The dangling if-else problem
• Examples of loops in action

• TC exercises 3.3 and 3.4
• Jason 7- Loops
• ch3.4 For loops and Nested Loops

• Loops
• The dangling if-else problem
• Examples of loops in action

• TC exercises 7.1
• Jason 8 - One-Dimensional Arrays
• ch7.1 Creating and Using Arrays
• Assign value to a particular cell: arr[3] = 25;
• Read a value from a particular cell: TextIO.putln(arr[0]);
• Change a value in a particular cell; arr[3] = foo(someInt);

• Single-dimension arrays
• Motivation - the need for arrays
• Terminology - define array,cells,Index/subscript
• Memory allocation with the new operator
• Requires a ref variable int[] arr;
• Allocates dynamic memory for the array in heap
• Syntax: int[] arr = new int[someSize]; The [expr] "bracket" operator expects an integer expression; 0 based array structure
• Syntax: collection of a single type, the length property, common errors

• TC exercises 7.2
• Jason 10 - Processing Data Collections
• ch7.2 Processing Data Collections.
• Specifically:
  • 7.2.1) Arrays and for Loops: System.arraycopy()
  • 7.2.5 Arrays of Objects.
  • 7.2.6 Variable Arity Methods: The arity of a subroutine is the number of parameters

• Processing Data Collections
• Motivation - the need for processing collections of data
• Figure out what we want to do for each cell.
• Common Error: ArrayIndexOutOfBoundsException
• Terminology: Parallel arrays: The data for a given copy of the message is spread out across several arrays.

• TC exercises 7.5 (If they exist)
• Jason 9 - Multi-Dimensional Arrays

• Multi-dimensional arrays
• Motivation - the need for multi-dimensional arrays
• Define multi-dimensional array
• Usage - show the multi-dimensional array
• Syntax: type [][] varname = new Type[sizeOfFirstDimension][sizeOfSecondDimension];
• still a collection of a single type
• how does the length variable work?
• Rectangular arrays: what does theMatrix.length return? What does theMatrix.length[0] return?
• common errors

• ch3.8 Partially-full arrays
• ch7.5 Two-Dimensional Arrays

• TC exercises 4.1
• Jason 11 - Procedural Composition and Abstraction
• ch4.1 Procedural Composition

• Procedural Composition and Abstraction
• Motivation - solving a problem with help
• Define: Procedural abstraction - Hide away the implementation details. Encapsulation.
• Example: Graphics

 if (iyear%4==0) leapYear=true

• TC exercises 4.2, 4.3, 4.4
• Jason 12 - Method Syntax
• lesson1 (15 min video), more (optional)

• function or subroutine
• Parameters
• Arguments
• Return statement
• "void" in place of a return type
• "public static"
• Syntax:
  • Method signature: return-type method-name(t1 p1,...,tn pn);Name;Return type;Zero or more parameters;
  • How the compiler does checks when a method is called;
  • Method definition - code for a method since it defines what the method does;
  • Method call - calling a method: method-name(argument1,...,argument n);
  • Scope in methods, Parameter variables, Local variables
  • How the compiler does type checking
  • Using methods from other classes; className.methodName(arg1,...,argN); the dot operator
  • Visual example of method calls (note cards)

• ch4.2 Static Subroutines and Static Variables
• ch4.3 Parameters (omit 4.35, 4.36)
• ch4.4 Return Values
• There are four things that every variable has: name, type, location in memory, value.

• TC exercises 4.7
• More about Methods
• ch4.6 Pre and Post-conditions. Bottom up Design
• ch4.7 Initialization and scope

• Methods (these are static from previous 2 lectures)
• Motivation
• Define:
  • Global variables
  • Overloading
  • Formal parameters or dummy parameters
  • Actual parameters or arguments
• Throwing exceptions: IllegalArgumentExceptions, NumberFormatException.

• TC exercises 5.1
• Jason 13 - Reference Variables and Objects
• Jason 14 - Objects and Methods
• ch5.1 Objects, Instance Methods, and Instance Variables

• Objects and reference variables
• Convert a parallel arrays and non-modular program written in main (one method) into an objected oriented model.
• Motivation - abstraction/encapsulation, organization, ease of use, code reuse, conceptualization. Design and building generalized software components
• Define: memory allocation and the new operator; Dynamic (heap) memory versus stack (local) memory; 3 types of data storage in Java {primitive type variables, reference variables, object state }
• Know the difference between a class and an object.
  • Recall from 5.1 in the reading that an object that belongs to a class is said to be an instance of that class.
  • The variables that the object contains are called instance variables.
  • The subroutines that the object contains are called instance methods.
  • If you do not allocate using "new," you have no object, and therefore no instance to use.
  • You need create to allocate, and instantiation represents only the first step (the intention) to allocate an object.
• Usage & syntax:
  • int [] scores; // declare reference variable scores (initializes to null)
  • scores = new int[Size]; // allocate the space for the object;
• What is a null pointer exception? Are all reference variables automatically initialized to null?
• Integration of topics:
  • Method overloading
  • Private and public access member specifiers
  • Getter and Setter methods - defines a property

• TC exercises 5.2
• Jason 18 - static versus non-static, and Constructors
• ch5.2 Constructors and Object Initialization

• Deadline to drop a UG semester course without grade of W
• Two kinds of methods: instance method, class method
• Four kinds of variables and when to use them: local variable, parameter variable, instance, class variable

• ch5.3.1
• ch5.3.3
• Programming with Objects

• Understand these terms:
• Java features:
  • Built in classes (5.3.1)
  • The class "Object"
  • Hash code
  • The toString() method
• Subclasses (more in 5.5 when we talk about inheritance)

• TC exercises 5.4
• ch5.3 continued

• TC exercises 5.5
• ch5.5 Inheritance, Polymorphism, and Abstract Classes
• ch5.6 this and super

ch8.2 Writing correct programs

ch8.3 Exceptions and try..catch

Chortle 71 (alternate)

Chortle 72 (alternate)

Chortle 72 (alternate)

Chortle73 (alternate), Jason 24

ch9.1.1, Jason 26

Jason 27

Jason 27

Lecture Video

Selection Sort Video

Jason 31, 32

Jason 31, 32

Jason 33

Jason 33

Jason 35

• Analysis of recursive methods
• iOS programming

• Jason 38, 39
• Jason 40

• Model-View-Controller
• iOS programming
• Why Mergesort is always O(N Lg N) with O(N)

Jason 40

• Quicksort
• Algorithm Analysis

Advice

• Why Quicksort is usually O(N Lg N) and requires no additional space
• Final Exam Practice