Grammars; review

Programming concepts

Programming concepts

Client vs. implementer

We started the course with introducing the idea of the client view (what a piece of code does) from the implementer view (how the code does it). This is a key idea in computer science known as encapsulation, which hides details of our programs inside a class. In practice, we’ve been encapsulating classes by declaring fields as private and writing comments that avoid exposing implementation details.

Instead of writing programs within the main method, we instead learned how to design classes that manage state (fields) and provide behavior (methods) that a client can create and use in their programs. This helped us learn to think about what the client does and doesn’t know, and how to make sure the state of our object is consistent between method calls.

Reference semantics

We’ve seen how Java evaluates programs, particularly stressing the difference between values and variables. Values are the data in a program, such as integers, booleans, or references to objects. Variables are names that store values. To evaluate a = b, we ask for the value of b and assign it to the name, a. The same rule applies to regardless of whether the data is a primitive type or a reference type.

Time complexity

Runtime analysis is about quantifying the amount of time a program will need to run by estimating the number of steps taken to execute the algorithm as a function of the input size. In the worst case, the order of growth of the runtime of indexOf is directly proportional to N, the number of elements in the list.

Abstract data types

Abstract data types are high-level specifications for the behavior of data types without specifiying concrete implementation details, such as lists, sets, stacks, queues, and maps.

Data structures are the concrete implementations for abstract data types. For example, the linked nodes data structure can implement the list abstract data type, but it can also implement the stack or queue abstract data types as well.

Both abstract data types and data structures are general ideas. Java programmers typically use interfaces to represent abstract data types and implement the interface using classes. The List interface represents the list abstract data type, and the LinkedList class implements the List interface using linked nodes.

List

An ordered sequence of elements with indices that has dynamic length. Operations include adding at an index, adding at the end, removing at an index, getting the value at a particular index, checking if the list contains a value, etc.

ArrayList uses a (resizing) array to store the data. Fast access to elements given an index because arrays have random access, but slow to insert at an index since it’s necessary to shift everything over.
LinkedList uses linked nodes to the store the data. Fast to add or remove from the front since we can just change the references, but getting the value at an index is slow.

Set

A collection of unique values without associated indices. Operations include adding a value, removing a value, checking if the set contains a value, etc.

TreeSet stores the data in sorted order, but is a bit slower than HashSet.
HashSet stores the data in an unknown order, but is a bit faster than TreeSet.

Stack

A collection that only allows data to be added or removed from the top of the structure.

Stack class represents a stack. Note that Java’s implementation is “leaky” since it extends Vector (ArrayList) so it inherits all of the methods from the list abstract data type.

Queue

A collection that only allows data to be added at the end and removed from the front.

Represented by the Queue interface and implemented with the LinkedList class

Map

A more generic version of an array, with any key type. Operations include adding a key-value mapping, removing a mapping, getting all the keys, getting all the values, etc.

TreeMap is similar to TreeSet but implements the map data type instead.
HashMap is similar to HashSet but implements the map data type instead.