CS 307 Topics List
The following are the major topics and sub topics covered in CS307, Foundations of Computer Science. Students should understand all the topics listed. Exams will be based on these topics, but exams will not simply ask for the definition of the concept. This list is a constant work in progress.
Review of CS 1 topics in Java
primitive data types
identifiers
variable declarations
local variables
variable scope
constants, final variables
mathematical expressions
precedence rules
mathematical operators
if, if else, if else if
boolean expressions
boolean operators
for loops
enhanced for loops (foreach loops)
while loops
method (procedure, function) headers
overloading methods
parameters and arguments
value parameters and reference parameters
return values
casting
implicit widening cast
explicit narrowing casts
preconditions, post conditions, assertions
import
Java packages
import
java.lang package
Strings
System.out.print and System.out.println methods
string concatenation
problem solving
problem decomposition and abstraction
standard Java classes: String, System, Math,
Integer, Double, Character, Scanner, File, Arrays, ArrayList, Random
autoboxing
Pointers
what is a pointer and pointee
uses of pointers, sharing
linked data structures
pointer arithmetic
the null pointer
dereferencing
dereferencing the null pointer, Null Pointer Exception (NPE)
object variables in Java
== and .equals comparisons for object variables
dynamic memory allocation, the new operator
passing pointers as value parameters, side effects
stack memory and heap memory
garbage collection
Arrays in Java
array variables
the length field
allocating arrays
initializer lists
array indices
accessing an element
Array Index Out Of Bounds Exception (AIOBE)
array initial values
arrays of objects
resizing (recopying arrays)
searching array for value
removing items from an array
adding items to array
array transformation
capacity vs. occupied portion of array
shuffling an array
shifting items in an array
array manipulations
2 Dimensional arrays and multi dimensional arrays in Java
2D arrays in Java
row and column conventions
manipulation of 2D arrays
Object Oriented Concepts - Introduction
abstraction
encapsulation
inheritance
polymorphism
using pre existing classes
what is a class? programmer defined data types
reading javadoc documentation
creating objects, calling constructors
method invocation, the dot operator .
message passing
mutators and acccessors
changing the state of an object
finding out something about an object
Building classes
defining the interface for a new data type, behaviors
implementing a new data type, fields and methods
classes and files in java
constructors
overloading constructors
the default constructor
this and constructor calls
public methods
private variables
instance vs. class variables (static)
final variables
initial values of instance variables
scope of instance variables
public vs. private, when to use and implication
planning for reuse
pre and post conditions, again
dynamic allocation of objects. Object variables and actual objects
the implicit parameters this
equals and toString methods, overriding methods
getClass
the instanceof operator
class methods and instance methods
accessing fields of the non calling object
immutable objects
Inheritance and polymorphism
the is-a and has-a relationships
inheritance relations terminology
inheritance in Java, exactly 1 class
the Object class (cosmic super class, Big Bang of Java classes)
the real picture of objects
behaviors from parents and ancestors
private and inheritance
protected and inheritance
multiple inheritance
class hierarchies
overriding methods
partially overriding methods, using super
the super.super.foo fallacy
specialization, adding methods and fields
implication of Object class, equals, toString, getClass
final methods and classes
constructors and inheritance
chain of constructor calls
using super to specify constructor called
lack of default constructor, implication for descendant classes
abstract classes and methods
implementing an abstract method
object variables of classes that are abstract
polymorphism
dynamic binding / dynamic dispatch
compiler vs. runtime method checks
genericity
class cast exception
Java interfaces
implementing an interface
the Comparable interface and the compareTo method
the relation between compareTo and equals
Exceptions
Error handling code
syntax vs. runtime vs. logic errors
Checked vs. unchecked exceptions
throwing an exception
try catch blocks
the finally block
common exceptions in Java
Algorithm Analysis
formal definition of Big O
formal definition of Big Omega
formal definition of Big Theta
rules of algorithm analysis, what can be considered 1 executable statement?
application of Big O, determining t(N) for a piece of code, actual number of executable statements as a function of N
application of Big O, determing f(n) for a piece of code, approximate number of executable statements as a function of N
various Big O functions, O(1), O(logN), O(sqrt(N)), O(N), O(NlogN), O(Nsqrt(N)), O(N^2), O(N^3), O(N^x), O(2^N), O(x^N), O(N!)
given a piece of code, what is the Big O?
given a Big O function, a value of N, and a runtime, what is the predicted runtime for different values of N?
best case, average case, and worst case performance
effect of processor speed on time to complete an algorithm
Big O with multiple independent variables, e.g. matrix addition
logarithms
The summation of 1 to N, formula, implications
Big O space requirements of algorithms
Recursion
concept of a stack, push, pop, top
the runtime stack
what happens when a method gets called
what happens when a method ends
concept of recursion
bases cases, identifying bases cases
recursive step, identifying and implementing recursive steps
using recursion when iteration will work
Big O of recursive methods
recursive backtracking
exhaustive searching using recursion
breadth first vs. depth first search
knapsack problems
Sorting and searching
algorithm for sequential search
when to use sequential search
algorithm for binary search
when to use binary search
break even point for sorting in order to do binary search
Big O for sequential and binary search
algorithms for simple, N^2, sorts: insertion sort, selection sort
best case / worst case performance of simple sorting algorithms
algorithm for the shell sort
algorithm for quicksort
algorithm for merge-sort
Big O for shell, quick, and merge sorts
hybrid sorts
enabling generic sorting and searching with the Comparable and Comparator interfaces
Abstract data types
basic operations for all abstract data types (adts)
behavior vs. implementation, using interfaces to define adts
properties of basic adts
bags
sets
lists
stacks
queues
priority queues
trees, binary trees, binary search trees, balanced binary search trees
maps, dictionaries
hash tables
graphs
iterators
Java Iterable
and Iterator
interfaces
the Java Collection interface, Java Collections framework
implementing generic containers via inheritance and polymorphism
implementing generic containers via Java generics
Lists
list interface, operations on list
various implementations of lists
array lists
linked lists, traditional
linked lists, alternative
using lists
Big O of list operations based on implementation
amortized Big O analysis
Big O space analysis
Iterators:
Java iterator interface: hasNext, next, remove methods
use iterators
Iterable interface
implement iterators as inner classes
Stacks
Stack interface
implementations of stack
Big O of stack operations based on implementation
using stacks
print out contents of a stack
balanced symbol checking
infix and postfix notation
conversion of infix expression to postfix expression
evaluation of postfix expressions
Queues
Queue interface
implementations of queues
wraparound in native arrays
Big O of queues operations based on implementation
using queues
priority queue interface and implementation
Trees, Binary Trees, Binary Search Trees, Balanced Binary Search Trees
definition of rooted trees
full tree
complete tree
perfect tree
path length
depth
height
implementation of binary trees
tree traversals, preorder, in-order, post-order, level-order, results and implementations
accessing elements of a tree
naive insertion algorithm
naive deletion algorithm
effects on tree with multiple inserts and deletes
finding the depth of a node
finding the height of a tree
balanced binary search trees
Big O of operations on binary trees
red-black trees, rules
insertion into a red-black tree
using binary trees and priority queues in Huffman encoding schemes
Other ADTs
introduction to maps, hash tables, graphs, and sets
General skills
design and implement a class based on a problem description
decompose a problem into classes, implement classes to create a solution, create classes that may be reused
use existing classes to help solve a problem
use existing classes and operations from those classes based on documentation
design an interface
implement an interface
extend classes using inheritance
determine errors in existing code (syntax errors, runtime errors, logic errors)
determine the purpose of a given piece of code
extend a given piece of code
use pre and post conditions for methods and behaviors
write pre conditions, post conditions, and assertions for code
debug code using a debugger
debug code by eye
trace code and what the value of variables are at various points in the execution