CSC 222: Computer Programming II
Spring 2004
Course Overview
Course Goals
* To know and be able to use basic programming tools for object-oriented
problem solving (e.g., classes, encapsulation, data hiding, and templates).
* To appreciate the role of algorithms and data structures in problem solving
and software design, recognizing that a given problem might be solved with
a variety of algorithms and structures (e.g., object-oriented design,
searching and sorting, recursion, stacks, queues, and linked lists).
* To be able to design and implement a program to model a real-world system,
and subsequently analyze its behavior.
* To develop programming skills that can serve as a foundation for further
study in computer science.
Object-oriented Programming
C++ basics
review of fundamental prgoramming constructs from CSC221
enumerated types (enum), const-reference parameters, default parameters
classes and objects
class = abstract data type (ADT); object = instance of class
private vs. public, data fields & member functions (methods)
constructor, separate compilation
object-oriented design: first identify objects, model as classes
interacting classes, private member functions
templated classes, templated functions
inheritance
inheriting data fields & member functions, overriding/adding functionality
IS_A relationship, private vs. protected, virtual member functions
code testing strategies
Data Structures
vectors and arrays
advantages of vectors over arrays
member functions: [], size, resize, push_back, back, pop_back
resizable vs. growable vectors, parallel vectors/arrays
list ADT: add, isStored, numItems, displayAll
implementation built on top of vector, templated
List class, derived SortedList class (utilizing binary search)
stack ADT: push, pop, top, empty, size
vector implementation, library
stack applications: delimiter matching, reverse Polish, run-time stack
queue ADT: enqueue (push), dequeue (pop), front, empty, size
library
queue applications: simulating customer lines, print queues, ...
pointers and dynamic structures
dynamic vs. static memory allocation
dereferencing operator (*), address-of operator (&), new, delete
pointers underlying: arrays, reference parameters, vector implementation
sorting/searching lists of objects vs. lists of pointers to objects
destructors, copy constructors, overloaded assignment operators
linked lists, -> operator, stack & queue implementations
Algorithms
algorithm analysis
big-Oh notation, rate-of-growth
worst case vs. average case vs. best case performance
searching
sequential search O(N) vs. binary search O(N log N)
sorting
insertion sort O(N^2) vs. selection sort O(N^2) vs. merge sort O(N log N)
mixing selection & merge sorts
recursion
base case(s), recursive case(s)
avoiding infinite recursion, recursion vs. iteration
simulations and modeling