CS 111 Essentials

Todd W. Neller

Note! This is not all that you are responsible for knowing. These slides summarize main content and defer details to required readings!

Class 1: Logging In, Course Website

• Read the reading assignments thoroughly. Class 1 and 2 readings before class 2. Class n readings before class n.
• Get familiar with structure and contents of our home page:
• http://cs.gettysburg.edu/~tneller/cs111/index.html
• Login and change your password:
• Open a Linux terminal window.
• Get your machine number <n> from the “Choosing a Lab Computer” section of http://cs.gettysburg.edu/~tneller/dept/remote.html
• ssh -l <username> -Y -p222 cs<n>.cc.gettysburg.edu
• yppasswd (Your password typing will not display.)
• exit or Control-D

Class 2: Hello.java, java, javac, bash

Source Code

.java extension

Plain text, human readable

Java Bytecode

.class extension

Binary, like machine-code

Intel

AMD

Qualcomm

javac

java

compile - translate program from higher-level language to lower-level language

interpret - translate and execute program on target processor

Intel JVM

AMD JVM

Qualcomm JVM

Java Virtual Machine (JVM)

Processors

Hello.java:

public class Hello {

public static void main(String[] args) {

System.out.println("Hello, world!");

}

}

Java commands:

javac Hello.java

java Hello

​

Bash commands: ls, mkdir, cd, nano/gedit, and many more in our Bash tutorial…

syntax

error

logic

error

Class 3: Eclipse, Style, and Comments

Programming style:

• (2 + 3) not (2+3); next-line/end-of-line block styles are both good, but be consistent. Control-A Control-I in Eclipse can help.
• One possible style guide: https://google.github.io/styleguide/javaguide.html
• Work towards a consistent, easily-readable style.

Comments:

// line comment (characters after "//" are ignored until end of the line)

/*

multi-line block comment

*/

/**

Javadoc multi-line block comment

*/

Working with Eclipse:

• Configure for Java 1.8
• New projects: use same folder for .java and .class
• Create a New Class with a blank (default) package
• “syso” and Control-space → System.out.println()
• Control-A (select all) Control-I (indent selected)

Class 4: Elementary Programming

Scanner - object for reading from stream of characters�System.in - standard input stream of characters�nextInt() - read the next integer from the Scanner�<type> <variable_name> = <value>; - variable declaration and assignment�System.out.print/println() - print a value without/with line break�(<type>) cast (convert) to datatype <type>

Class 5: Elementary Programming

final - Java constant, UPPERCASE_NAMING_CONVENTION

Math methods: Math.sqrt( ), Math.pow( , ), etc.

Number representations: bases, integer (42), binary (0b101010), octal (052), hexadecimal (0x2a), double (1.2, 3.4e-5d, -6.7e8D), float (1.2f, 3.4e-5F)

Integer division (1 / 2), floating-point division (1.0 / 2.0, (double) 1 / 2)

Remainder 5 % 3 == 2

Augmented assignment += -= *= /=

Preincrement (++i), postincrement (i++), pre/postdecrement (--i, i--)

Casting (type conversion), e.g. (int) truncates to an integer.

Math.round( ), Math.floor( ), Math.ceil( )

Class 6: Common Pitfalls, �Development Process

Common pitfalls:

• Undeclared, uninitialized, or unused variables.
• Integer underflow/overflow
• Roundoff errors
• Unintended integer division
• Redundant Scanners

Software Development Processes:

• Waterfall Model
• Spiral Model

Source: Wikimedia Commons

Source: Wikipedia

Class 7: Selection - boolean type, relational operators, if statements

boolean type true / false

Relational operators (<, <=, >, >=, ==, !=)

if statements, e.g. if-else chain: nested-if statement: �

Class 8: Selection - common errors, logical operators, random numbers

Common errors: missing braces, extra semicolon (after condition), bad style (e.g “== true”), dangling-else, assuming exactness of approximate floating-point operations.

Logical operators: && (and), || (or), ! (not), ^ (exclusive or - either or)

Random numbers:

Class 9: Selection - switch, selection operator, operator precedence, debugging

Switch statement: Selection/ternary operator (if-else expression!):�

​

​

​

​

​

Operator precedence: (var++ var--), (+ - (unary) ++var --var), casting, !, (* / %), (+ - (binary)), (< <= > >=), (== !=), ^, &&, ||, ?, (= += -= *= /= %=)

condition ? true_expression : false_expression

Debugging in Eclipse:

• Vogella tutorial
• Set breakpoints
• Run step by step, step over, etc.
• Inspect variables

Source: Vogella tutorial

Class 10: Math package, characters

Math.___(...) - many of Java’s mathematical functions are of this form, using doubles and radians:

toRadians, toDegrees, sin, cos, tan, asin, acos, atan, log, log10, exp, pow, sqrt, round, floor, ceil, max, min, abs

Math.PI, Math.E - constants 𝜋, e

char - a single 16-bit Unicode character primitive data type

Character.___(...) - Java’s character functions, e.g.:

isDigit, isLetter, isUppercase, isLowercase, toUppercase, toLowercase

​

Class 11: Strings

String - a fixed (“immutable”) list of characters

substring, length, charAt, compareTo, equals, equalsIgnoreCase, regionMatches, startsWith, endsWith, indexOf, lastIndexOf, concat, replace, toUppercase, toLowercase, valueOf

Integer.parseInt(“...”), Double.parseDouble(“...”)

index

char

Class 12: printf, JOptionPane popups, Scanner

Class 13: Loops - while, do-while

Output:

0 1 2

Output:

3 2 1

Class 14: Loops - for, loop choice

Loop Choice:

• Counter-controlled? → for
• At least one iteration? → do-while
• Otherwise → while

Class 15: Loops - Nested Loops

Consider a “stepping stone” strategy for implementation, either inside-out/outside-in.

Class 16: Methods - syntax

Method syntax:

<modifiers> <return type> <method name>(list of parameter declarations) {

code block

}

modifiers:

• access specifiers (e.g. public, private)
• "static" - associated with the class (e.g. MethodFun)

return type:

• "void" - no return value
• the type of a value that is returned by the method to the method "caller"

Method signature: <method name>(list of parameter declarations)

• method name - lowercase camelCase
• "(formal) parameters" - comma-separated pairs of type and varName

Class 17: Methods - Modularization Benefits

Benefits of modularization with methods:

• Enables code reuse: Define a method, reuse it repeatedly
• Easier to maintain/debug: Test, debug, and modify in one place rather than many (often forgetting to keep copies in sync)
• Easier cognitively: Divide problem into subproblems, solve subproblems in methods, and compose subproblem solutions by using the methods to solve the original problem.

Class 18: Methods - Variable Scope, Stepwise Refinement

Variable scope: the part of a program where a variable can be referenced

• Local variables: until end of surrounding code block
• Exception - for-loop declarations: entire for-loop body
• Parameter variable: entire method body

Top-down approach: Decompose problem into subproblems and express the solution in terms of subproblems that haven’t been solved yet. Repeat with subproblems as needed. Gradually implement from problems to subproblems to subsubproblems…

Bottom-up approach: Implement the smallest possible subproblems and gradually compose them into solutions of larger subproblems, etc.

Both top-down and bottom-up approaches may be used together.

Class 19: Arrays - basics of 1D arrays

Common array algorithms: initializing iteratively (data, random), accumulating, finding smallest/largest value/index, shuffling, shifting

Class 20: Arrays - copying contents, arguments and return values, variable-length argument lists

[0, 0, 0, 0, 0, 42, 2, 3, 0, 0]

[42, 2, 3]

[4, 5, 6]

​

​

Class 21: Arrays - searching, sorting, Arrays methods, main String[] args

Linear search: Iterate through array indices. Return the index if the target value is found. Otherwise, return -1 (not found).

Binary search: Assumes sorted data. It’s the number guessing game on indices! “Higher” or “lower” is based on comparison of target to value at current guess index. Return the index if the target value is found. Otherwise, when low > high (failure of search) return -1.

Selection sort: For each index i in succession, find the smallest value from indices >= i, swap it with the value at index i.

java.util.Arrays methods: sort, binarySearch, equals, fill, toString

In class C method main(String[] args), args is a String array containing the words following “java C”, so “java C Testing 1 2 3” would result in args being {"Testing", "1", "2", "3"}.

Class 23: Multidimensional Arrays - 2D array declaration, creation, access, operations, arguments, examples

• A 2D array is an array of arrays, i.e. a reference to a list of references to lists.
• Processing 2D arrays: initializing, printing (below), statistics (by row/col), comparing stats on rows/cols, shuffling (not as in text)

​

Class 24: Multidimensional Arrays - examples, 3D+ arrays

• A 3D array of type T is an array of arrays of arrays of Ts. An nD array of type T is an array of ((n-1) ⨉ “arrays of”) Ts. Array patterns generalize.

​

Class 25: Objects and Classes - defining & creating objects, fields, constructors, methods

• A object is a collection of related data (fields) and code (method).
• Classes are sets of objects.

​

Class 26: Objects and Classes - access specifiers, static keyword, getters & setters

• static = “associated with the class (set)”, i.e. one defined for class
• Non-static = “associated with the object (set member)”, i.e. one for each object.
• Access specifiers - public (access anywhere), private (access only in defining class)

​

…

Class 27: Objects and Classes - object arrays, immutable objects, variable scope, keyword this

• Object arrays and variables contain references to objects in memory, not the objects themselves. “null” = no object reference
• Immutable objects (e.g. Strings) have no setters/mutators. Their state is unchangeable after construction.
• Variable scope (continued):
• Static fields: later static & non-static fields, all static & non-static methods
• Non-static fields: later non-static fields, all non-static methods
• Keyword this is assigned a reference to the current object.
• In the Point constructor and setters (previous slides), “this.x” refers to the field x of this object, whereas “x” refers to the parameter x.
• Without “this.” preceding, Java assumes the most closely defined variable (searching for definition local? → parameter? → field?).
• Think of this as the “implicit parameter”. “pt.setX(5);” assigns �this = pt; and parameter x = 5;

Class 28: Object-Oriented Thinking - class abstraction, class relationships, design principles

• Class abstraction - separation of class use from class implementation (e.g. the user of the class sees the public methods/fields as their “interface”)
• Class encapsulation - the means by which the private implementation is hidden (e.g. private/public keywords)
• Procedural programming paradigm - think in terms of methods (a.k.a. procedures, functions, etc.)
• Object-oriented programming (OOP) paradigm - think in terms of objects, i.e. collections of related data and methods
• Associations - class relationships (e.g. student takes class, has address and ID)
• Aggregation - has-a relationship (e.g. student address)
• Composition - has-a relationship with exclusive ownership (e.g. student ID)

Class 29: Object-Oriented Thinking - wrapper classes, auto-(un)boxing, BigInteger, BigDecimal

• For each primitive type (e.g. int, double, boolean), there is a corresponding wrapper class (e.g. Integer, Double, Boolean) that wraps values up in containing Objects.
• Java automatically auto-boxes (primitive value → wrapper class object) and auto-unboxes (wrapper class object → primitive value) as the context requires.
• BigInteger / BigDecimal
• represent unlimited (except by memory) size/precision numbers
• are immutable, constructed from Strings, constants (e.g. ZERO, ONE, TEN)
• perform operations via methods (e.g. add, subtract, multiply, divide, etc.)
• For BigDecimal’s divide, one needs to also supply scale (# of decimal places) and RoundingMode parameters.

Class 30: Object-Oriented Thinking - String, StringBuilder, StringBuffer

• String objects
• are immutable,
• at compile time, multiple copies are “interned” to single objects, and
• have many useful methods, e.g. replace, replaceFirst, replaceAll, split, matches, toCharArray, valueOf(type) including type char[], parseInt, parseDouble, format, etc., some making use of regular expression (“regex”) patterns.
• StringBuilder / StringBuffer (synchronized) are mutable and can be used to efficiently build large Strings through repeated calls to an append method follow by a call to a toString method to build the String.

Class 31: Recursion - recursive problem solving, base case(s), recursive step(s)

• Recursion…
• solves a problem in terms of “smaller”, simpler, same problems, by
• defining solutions for simplest base case(s), and
• in general recursive case(s) defining a solution in terms of calls to the same method for simpler problems (closer to the base case(s)).

…

→ gcd(2226, 504)

→ gcd(504, 210)

→ gcd(210, 84)

→ gcd(84, 42)

→ gcd(42, 0)

→ 42

Class 32: Recursion - recursive helper methods

• Recursive helper methods (a.k.a. auxiliary functions) often have the full range of needed parameters for the recursive algorithm and are called by a top-level method that provides a simpler interface:

Class 33: Recursion - dynamic programming

• The dynamic programming (DP) pattern:
• trades off increased memory for improvement in computational time
• stores recursive solutions to smaller problems and reuses solutions
• computes and stores a solution only if that solution has not already been stored

​

​

Fibonacci number computation without DP

Fibonacci number computation with DP

Class 34: java.util Goodies - Generics, ArrayLists

• Java generics allow us to:
• parameterize types to create general data structures and algorithms
• enable type-checking of such implementations at compile time
• Example: ArrayList<Integer>, ArrayList<String>, etc.
• ArrayList<E> - where E is the type parameter of a list element
• An array-like list for when you don’t know the length beforehand
• Construction: ArrayList<Double> al = new ArrayList<>();
• Grow dynamically by one element: al.add(4.2);
• Array getter: a[0] ; ArrayList getter al.get(0)
• Array setter: a[1] = 2.3 ; ArrayList setter al.set(1, 2.3)
• Other methods: al.contains(0.0), al.remove(4.2), al.isEmpty()
• Compatible with for-each loop
• Like other java.util data structures we’ll cover, uses .size() (not .length() as with Strings or .length as with arrays)

Class 35: java.util Goodies - Stack, Queue (LinkedList), PriorityQueue, Set/HashSet/TreeSet

• Stack<E> - Last In, First Out (LIFO)
• Stack<Integer> stack = new Stack<>();
• stack.push(1) / stack.peek() / stack.pop() to (add/return/remove and return) the top element of the stack
• Queue<E> - First In, First Out (FIFO)
• Queue<Integer> queue = new LinkedList<>();
• queue.offer(1) / queue.peek() / queue.poll() to (add to the back/return from the front/remove and return from the front) of the queue
• PriorityQueue<E> - Least (or highest priority) element out
• PriorityQueue<Integer> pq = new PriorityQueue<>();
• Queue operations, but “front” is according to natural ordering or given Comparator<E> ordering
• Set<E> - a (unique) set of elements
• Set<Integer> set = new HashSet<>(); // no guaranteed for each loop ordering
• Set<Integer> set = new TreeSet<>(); // guaranteed sorted for each loop ordering
• Common operators: add, addAll, removeAll, retainAll, contains, isEmpty, remove

Class 36: java.util Goodies - Map/HashMap/TreeMap

• Map<K, V> - a mapping from keys of type K to associated values of type V
• arrays map non-negative ints to values of a type, where maps generalize this functionality to all types
• Map<String, Integer> map = new HashMap<>();
• Map<String, Integer> map = new TreeMap<>(); �// sorted for each loop ordering
• To create an association: map.put("zero", 0);
• To see if an association exists: map.containsKey("zero")
• To look up an association: map.get("zero") → 0
• To remove an association: map.remove("zero")

​