Programming and Problem Solving II

Revised: December 2008 (Bill Kreahling)

Course Description

A course on data structures and object-oriented programming. Object-oriented concepts covered will include inheritance, encapsulation, composition, and interfaces. Data structures covered will include lists, queues, stacks, binary trees, and binary search trees. Algorithms considered will include traversing, iterating, inserting, removing, and searching. Recursion will be emphasized. Big-O notation will be introduced and used throughout.

Text

Book Rental: Required: Frank Carrano, Data Structures and Abstractions with Java, Second Edition, Prentice Hall, 2008. (http://vig.prenhall.com/catalog/academic/product/0,1144,013237045X,00.html)

Supplemental: Mark Holliday, Lecture Notes for CS 150 (http://paws.wcu.edu/holliday/LectureNotes/150/lectures.html)

Grading Procedure

Grading procedures and factors influencing course grade are left to the discretion of individual instructors, subject to general university policy.

Attendance Policy

Attendance policy is left to the discretion of individual instructors, subject to general university policy.

Course Outline

• Brief Java Review
  Several key Java concepts will be re-introduced within the framework of a brief review of CS 150, using memory diagrams.
• Inheritance and Interfaces and Related Topics
  Discussion of Java inheritance, method overloading/overriding, class hierarchies, generic types, dynamic and static typed variables, Java exceptions, polymorphism, and abstract classes.
• ADTs and Related Topics
  The List Abstract Data Type (ADT) and its implementation using array-based data and linked-data; iterators as objects used to traverse collections of data;
• Recursion and Algorithm Efficiency
   A discussion of recursive algorithms and how they compare to iterative algorithms. How recursion is accomplished; a discussion of stacks and heaps; a brief overview of algorithm efficiency focusing on Big-Oh notation.
• More Topics Related to the List ADT
  A brief introduction to sorting; sorted lists; inheritance and lists; mutable, immutable, and cloneable objects; sequential search versus binary search.
• The Tree ADT
  General trees and binary trees; tree traversals; implementation of the Binary Tree ADT; binary search trees.
• The Stack ADT and the Queue ADT (Time Permitting)
  The Stack ADT and its implementation; algebraic expressions and stacks; the Queue ADT and its implementation.
• The Dictionary ADT (Time Permitting)
  The Dictionary ADT and its implementation; a brief introduction to hashing.