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, <stack> library stack applications: delimiter matching, reverse Polish, run-time stack queue ADT: enqueue (push), dequeue (pop), front, empty, size <queue> 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