CSE373
Midterm #1 Review Sheet

Mathematical background

Know what a relation is (in the formal mathematical sense).  Understand the set-theory notation used with relations.

Understand properties such as reflexive, symmetric, transitive, anti-symmetric, equivalence relations, partial orders.  Be able to determine when relations have particular properties, both when the relation is given explicitly as a set and when the relation is defined in other ways (such as using English).

Understand what a function is in the formal (mathematical, set-theory) sense, and also informally.   Given a relation (defined in various ways) determine when it is or is not a function.

Understand logarithms and exponentials and be able to work with them (basic algebra).

Know basic series and summations (like 1+2+ ... n); be able to work with them algebraically; be able to recognize situations where they can be applied.

Chapter 3

Be able to give a precise definition of Big-O.  Be able to understand and apply the definition when working with specific functions.

Given a single statement in Java or pseudocode, understand its time cost.   Given a fragment of code, develop an "exact" time complexity formula for it, in terms of an appropriate parameter or parameters. 

Given an informal description of an algorithm or process, determine what its asymptotic complexity is.

Given a formula which represents a complexity, categorize it as closely as possible to one of the better known standard functions.

Know the hierarchy (complexity order) of common standard functions.

Given two functions, determine whether one is Big-O of the other.

Chapter 4 -- Recursion

Know the fundamental aspects of recursion: base cases, recursive cases, getting to to the base case, etc.

Be able to translate a recursive problem description or informal algorithm into code or pseudocode.

Be able to code recursive algorithms in actual Java, from scratch, for relatively short but non-trivial problems.  Some examples include array processing (finding max, summing, searching), computing products or powers or logs, etc.

Be able to trace a given recursive method to determine its operation or output.

Be able to analyze a given recursive method to discuss its complexity, at least informally.

Chater 4 -- Data Structures

Know the Stack (and Queue) as an ADT (know each of its operations).

Recognize situations where a Stack (or Queue) is appropriate in a problem solution.

Be familiar with a typical Java interface for a Stack (or Queue).

Be familiar with more than one programming approach to implementing a Stack (or Queue).

Java Programming

Know all Java fundamentals, including object-oriented features, as expected from a basic beginning programming sequence (such as 142/143).

Understand the differences and applications of interfaces, abstract classes, and concrete classes.

Be comfortable in a programming situation involving multiple files and classes, packages, your own code, external code, and libraries.

Be able to create a JUnit test class.

Given a Java method, be able to create an appropriate method to test it (whether using JUnit or not).

Other preliminaries

Know what an Abstract Data Type is.