Programming and Problem Solving II
Revised: August, 2021
Course Description
A course on data structures and object-oriented programming. Object-oriented concepts
covered will include: exceptions, 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.
Prerequisite & Notes
- Prerequisite: Passing of CS 150 with at least a grade of C
- Corequisite: MATH 146, MATH 153, or MATH 255
- 4 Credit Hours
- Required for major, required for minor
Text
Frank M. Carrano and Timothy N. Henry, Data Structures and Abstractions with Java , Fifth Edition, Pearson, 2019.
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.
- Inheritance, Interfaces and Related Topics
Discussion of Java inheritance, method overloading/overriding, class hierarchies,
generic types, dynamic and static typed variables, exceptions, polymorphism, abstract
classes, Java Interfaces.
- ADTs and Related Topics
The List Abstract Data Type (ADT) and its implementation using array-based data and
linked-based data structures; 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 ADTs
A brief introduction to sorting; sorted lists; inheritance and lists; mutable, immutable,
and cloneable objects; sequential search versus binary search.
- The ADTs in Detail
The Discussion of various ADTs. Examples, may include Stacks, Queues, Maps, Dictionaries,
or others; Included ADTs are at the discretion of the instructor.
- The Tree ADT (Time Permitting)
General trees and binary trees; tree traversals; implementation of the Binary Tree
ADT; binary search trees.