CSC 216: Intro to Software Engineering & Programming Concepts

Instructor: Dr. Sarah Heckman | Semester: Spring 2019

Table of Contents

# Administrivia

## Grades

WeightComponentAdditional Info
12%Guided Projects
34%ProjectsTwo projects. 3% of each is part 1. 14% of each is part 2.
Guided Projects12
Labs15
Exam 112Exam 1 will cover material from approximately the first third of the course.
Exam 212Exam 2 will cover material from approximately the first two-thirds of the course.
Exam 315Exam 3 will cover all materials for the course.

## Lecture

## Lab

## Assignments

## Academic Integrity

## Main Topics

# Object Oriented Design (OO)

N.B. These are defined with reference to Java.

## FAQ

## Vocabulary

## Methods

## Semantics

### Null Semantics

### Java Specifics/Oddities

### Invariants

### Cloning

## Composition and Delegation

## Inheritance

### Java Syntax

public class SubClass extends SuperClass {
  // This class has all of the (implemented)
  // functionality of the super class
}

### Usage

## Abstract Class

public abstract class Beer
implements Drinkable, Brewable {

  private String name;

  public Beer(String name) {
    this.name = name;
  }

  // Declare abstract methods
  public abstract boolean
  addIngredient(BeerIngredient i);
  public abstract Collection<BeerIngredient>
  getIngredients();

  // Implement inherited methods
  public void brew() {
    System.out.println(
      name + " is being brewed"
    );
  }

  // I don't have to implement Drinkable because
  // this is an abstract class
}

## Interface

public interface Brewable {
  void brew();
}

## Nested Classes

### Advantages

## Anonymous Objects

## Anonymous Classes

new Foo() {
  public int someState;
  public void doStuff() {
    // Do things
  }
}

## Exceptions

### Try-Catch-Finally Blocks

try {
  // Do things
} catch (ExceptionType name) {
  // Handle errors
}

try {
  // Statements
  // Exception thrown!
  // Statements skipped
} catch (UnmatchedExceptionType name) {
  // Would handle exception, but doesn't go in
  // here
} catch (MatchedExceptionType name) {
  // Handle thrown exception
} catch (AlsoMatchedExceptionType name) {
  // Would handle exception, but goes to first
  // catch block.
} finally {
  // Statements here are always executed!
}

try {
  // Throws either Exception1 or Exception2,
  // that need to be handled equally
} catch (Exception1 | Exception2 name) {
  // Handle exceptions
}

try (File f = new File()) {
  // May throw FileNotFoundException
} catch (FileNotFoundException e) {
  // Handle exception
}
// Resources automatically closed!

### Create Custom Exceptions

public class MyException extends Exception {
  public MyException(String message) {
    super(message);
  }
  public MyException() {
    super("Exception message");
  }
}

## Errors

# (Java) Libraries

## Library and Build Managers

## Java Iterators

Java collections can be iterated using a for-each loop.

for (Type item : container) {
  // Do things
}

This allows for more effiecient code, as you don't always have to pass through things multiple times. Instead, you can use an iterator which keeps track of its position and its value.

To make a class use iterators, you should implement Iterable<E>.

public class List<E> implements Iterable<E> {
  // Stuff
  public Iterator iterator() {
    // Make iterator and stuff
  }
  public class Iterator<E> {
    // Do stuff
  }
}

### API

## Limitations

## Misc

## Java GUIs

GUIs are event-driven. That is, we wait for the user to interact with the GUI and they can do whatever they want. We can, however, restrict their access.

This means, even close buttons, don't truly close the program.

To create a GUI, try storyboarding and consider what your user needs to do. Draw a picture of your planned GUI and adjust it as you think about what a user must do with it. Try sectioning things off into logical blocks or creating a tree of components.

Generally, thinking about things as columns and rows is very helpful.

Java uses the event model to handle events in GUIs. This uses event objects that encapsulate the information required to handle the event; this includes the information entered, the type of action, and the source of the event (e.g. a button).

An event model uses events, handlers, and listeners. Events are things that the user has done or things that have occurred. Handlers are things that notify listeners when events have occurred. Listeners are things that take action given certain events. In Java, the event is an EventObject and a listener is an EventHandler. Because of this structure, we must register listeners to the handler.

To create listeners, you create an object that implements ActionListener. There are many ways to do this:

Low level events are interactions with the operating system, like key pressed. Semantic events are user-actions, like button clicks and text edits.

To handle low level events, it is recommended to use Java's *Adapter abstract classes. These make it easier to handle low level events and "convert" them to action events.

public class CSC216GUI extends JFrame
implements ActionListener {

  public CSC216GUI() {
    // Setup
    setTitle("CSC 216 GUI");
    setSize(400, 400);
    setLocation(600, 200);

    // Create main container
    Container c = getContentPane(
      new BorderLayout()
    );

    // Components
    JLabel lblCheer = new JLabel("Wolf!");
    c.add(lblCheer, BorderLayout.NORTH);

    JButton btnClick = new JButton("Click me!");
    // Anonymous class
    btnClick.addActionListener(
      new ActionListener() {
        void eventPerformed(ActionEvent e) {
          System.out.println("Anonymous class");
        }
      }
    );
    // Lamda expression
    btnClick.addActionListener(e -> {
      System.out.println("Lambda expression")
    });
    // GUI is listener
    btnClick.addActionListener(this);
    c.add(btnClick, BorderLayout.SOUTH);

    // so it actually closes
    setDefaultCloseOperation(EXIT_ON_CLOSE);
    // default is invisible :)
    setVisible(true);
  }

  public void eventPerformed(ActionEvent e) {
    System.out.println("GUI is listener");
  }

  public static void main(String[] args) {
    CSC216 gui = new CSC216GUI();
  }

}

## ListIterator

A List specifically for lists. All linked lists are doubly linked lists. To support inserting in doubly linked lists, you need to make the first and last node actual nodes and not names for the boundary nodes (like what I said when I created Walker). ListIterator's think about being between two nodes.

### ListIterator API

### AbstractSequentialList

AbstractSequentialList is an abstract class is useful for creating lists. This implements almost everything except for listIterator() and size() because everything is done through ListIterator.

# Design Patterns

## Families

## Model-View-Controller (MVC)

## Observer

You have a single object that you want to be able to notify any number of other objects about when it changes.

To do this, you make the single object you want to have other things observe extend Observable, which means it knows how to handle adding observers and notifiers. Then you have your observers extend Observer, which means they know how to handle being notified by an observable object.

Why would you do this? It allows you to decouple the thing your objects want to watch, meaning that it doesn't have to know about its listeners. This allows you to make easier to refactor to the higher level observers without breaking the observable.

This is commonly done in GUIs.

// In the Observable when something changes
this.setChanged();
notify();

## Singleton

A class controls the number of instances and the manner of creation of its instances.

Here, we will only ever use a singleton that manages one instance of itself.

Why do this? So outsiders only look at a single instance or controlled instance by the class.

## State Pattern

A way to implement FSMs with objects.

Essentially, you have a state object representing each state. The machine parses the input and calls the appropriate method on the current state object. That state object then acts and changes the parent state object as necessary.

# Design Suggestions

# Software Engineering & Design

## Methods of Showing Design

## Software Process

### Requirements/Analysis

### Design

### Implementation/Code

### Testing

### Integration

## Software Design Models

### Planned/Waterfall

Waterfall Design Process

#### Pros

#### Cons

### Iterative/Agile Model

#### Pros

#### Cons

## Task Planning

### Pros

## Testing

### Vocabulary

### Types of Testing

### Test Case Information

### Code Coverage

## Debugging

## Analysis Types

## UML (Unified Modelling Language)

### Class Diagrams

#### Class Attributes

#### Class Operations/Methods

#### Connectors

Event Class

Wolf Scheduler Diagram

### Sequence Diagram

### Tools for Creating UML Diagrams

# Algorithmic Efficiency

## Big O

NameBig O Notation
ConstantO(1)
LogarithmicO(log(N))
LinearO(N)
Log-LinearO(N∗log(N))
QuadraticO(N2)
ExponentialO(2N)

# Data Structures

## Stack

### Methods of Interaction

### Usage

### Uses

## Queue

### Methods of Interaction

## Trees

A tree is a directed, acyclic structure of linked nodes. These can be binary, heaped, and more.

Trees are inherently recursive and thus it is strongly recommended that you program recursively with it, especially traversal which is where you visit every node in the tree.

For traversals, you should probably draw a diagram to see what order and how you are traversing the tree.

Some uses of trees are representing the file structure using a filesystem tree, representing/implementing AI machines using decision trees, and compiling code using an abstract syntax tree / parse tree.

### Vocabulary

## Binary Search Tree

A binary tree is a tree where each branch only has two children.

A binary search tree is a binary tree that cannot contain duplicates where each branch is strictly greater than the max value in its left child's tree (and thus is greater than its left child) and strictly less than the min value in its right child's tree (and thus less than its right child) and each of its children are binary search trees.

A binary search tree has to take at most the height of the root node to find an element at a given element. This makes it important to try your best to keep the tree as close to its minimum height as possible (this means balanced). For balanced binary search trees, the efficiency is near O(log2(n)). For unbalanced binary search trees, the efficiency is near O(n).

### Adding Elements

  1. Start at the root as your branch.
  2. If the element is the same as the branch,
  3. Else if the branch is empty, insert the element there.
  4. Else if the element is less than the branch, add the element to the left side.
  5. Else if the element is greater than the branch, add the element to the right side.

In Java, it is recommended to do adds by reassigning your node with a function.

public void add(E element) {
  this.root = add(overallRoot, value);
}
private Node add(Node branch, E element) {
  if (branch == null) {
    branch = new Node(element);
  } else if (E < branch.data) {
    // You'd really do compareTo here but it's
    // hard to read
    branch.left = add(branch.left, element);
  } else {
    branch.right = add(branch.right, element);
  }
}

### Getting Elements

### Removing Elements

  1. Find your appropriate node.
  2. If you have two children, set yourself to the min of the right tree (or max of the left tree).
  3. If you have one child, replace yourself with your child.
  4. If you have no children, kill yourself.

## Heaped Trees / Heaps

A heaped tree or heap is a tree which satisfies the heaping property, that is each node is either greater than or less than its children. If it has the prior, it is called a max heap because the root is the max element. If it has the latter, it is called a min heap because the root is the min element.

# Data Structure Modification

## Searching

How do you find things in data structures? One way is by arranging things in some natural order.

There are two categories, sorted and unsorted.

There are many methods, each have trade-offs:

// This is like java.util.Arrays#binarySearch
private static int
binarySearch(int[] list, int value, int min,
             int max) {
  if (min > max) {
    // Missed element
    return -1;
    // java.util.Arrays#binarySearch(array,
    // value) returns -(min + 1), or insertion
    // point
  } else {
    // List not empty
    int pivot = (min + max) / 2;
    if (value < list[pivot]) {
      //
      binarySearch(list, value, min, pivot - 1);
    } else if (value > list[pivot]) {
      binarySearch(list, value, pivot + 1, max);
    } else {
      return pivot;
    }
  }
}

## Sorting

Sorting is ordering items into their natural ordering. There are many different ways to do this, each with trade offs:

# Finite State Machines

## Diagrams

## Examples

Vending Machine Diagram

Pascal Real Constant Compiler

Simple Text Processing for 'abba'

wc as a FSM

StateA-Za-z\nOther
01: ++wc, ++cc0: ++lc, ++cc0: ++cc
11: ++cc0: ++lc, ++cc0: ++cc

## While-Switch Idiom

while you have input:
  switch(STATE):
    case STATE_0: ...
    case STATE_1: ...
    case STATE_2: ...
    case STATE_3: ...

// Replicates wc functionality
while ((next = br.read()) != −1) {
  ch = (char) next;
  switch (state) {
    case 0:
      if (ch == '\n') {
        ++lc;
        ++cc;
      } else if (Character.isLetter(ch)) {
        state = 1;
        ++wc;
        ++cc;
      } else {
        ++cc;
      }
      break;

    case 1:
      if (ch == '\n') {
        state = 0;
        ++lc;
        ++cc;
      } else if (Character.isLetter(ch)) {
        ++cc;
      } else {
        state = 0;
        ++cc;
      }
      break;

    default:
      System.out.println(
        "Invalid state: " + state
      );
  }
}

## Object Oriented Implementation

This only works for object-oriented paradigms.

Use the state pattern. This is useful if all your states have to handle all/most types of input.

This works with bounded recursive loops. (This is when a state has some data, which is formally illegal but simplifies implementation.)

## Functional Implementation

This only works with functional paradigms.

Instead of having objects that implement a common interface, you can have a set of functions that represent state. Each function knows how to handle an arbitrary input, parses it, and returns the appropriate state (function).

You set the current function to the call of the current function with the input.

StateFunction curr = defaultStateFunction
while input:
  // curr returns a StateFunction
  curr = curr(input)

This does not work with bounded recursive loops.

# Recursion

## Verification Methods

## Important Notes

## Types of Recursive Functions

## Creating a Recursive Solution

## Public-Private Pairs in Recursive Methods/Functions

Sometimes you need more information to accumulate in a recursive method that always has the same default value. To do this, you create a public method that has only a restricted number of parameters. This public method then calls on the private method with the "default value".

This is essentially a workaround for not having true default values and also making sure your clients don't have to worry about that.

public void crawl(File f) {
  crawl(File, "");
}

public void crawl(File f, String indent) {
  System.out.println(f);
  if (f.isDirectory()) {
    for (File subfile : f.listFiles()) {
      crawl(subfile, indent + "  ");
    }
  }
}

## Using Control Flow as a Data Structure

Using recursion, you can use the method call stack as a data structure. How? You store a local variable in the method cal, call the method recursively, and then do something with the local variable after the recursive method completes.

// This only works with synchronous method calls
void reverseLines(Scanner input) {
  if (input.hasNextLine()) {
    // "Push" something onto the "stack"
    String line = input.nextLine();
    // Add a new method to the call stack
    reverseLines(input);
    // "Pop" something from the "stack"
    System.out.println(line);
  }
}

# Misc

## Horner's Rule