# Principles of Computer Programming II

CST 283

## Course Description

Prerequisite: CST 180 or CST 183. Introduces data structures and object-oriented programming. Includes array processing, sorting and searching algorithms, and pointer variables, and recursive programming. Studies data storage and retrieval using lists, stacks, queues, and trees. Utilizes object oriented programming methods including classes, composition, and inheritance. Credit may be earned in CST 283, CST 280, or CST 281 and CST 282 combined, but not in more than one. (60-0)

## Outcomes and Objectives

### Demonstrate computer literacy skills to successfully use software development environments.

#### Objectives:

• Utilize an integrated development environment to create a project workspace.
• Enter and edit program source code using a text editor.
• Manage multiple project, data, and source code files.
• Use a compiler to check program diagnostics and correct syntax errors.

### Analyze algorithms for information manipulation from various data structures.

#### Objectives:

• Define the basic concept of algorithm efficiency including the definition of the order of magnitude (big-O) of an algorithm.
• Define the basic concept of algorithm efficiency including the definition of the order of magnitude (big-O) of an algorithm.
• Analyze and measure the efficiency difference between the linear search and binary search.
• Describe a high probability ordered search as an improvement to a linear search.
• Describe and trace basic O(N2) sorting algorithms including bubble sort, selection sort, and insertion sort.
• Describe and trace recursive O(Nlog2N) sorting algorithms including quicksort, mergesort, and heapsort.
• Recognize the big-O for a collection of sorting algorithms and define the best and worst in terms of efficiency.
• Measure numerous sorting algorithms for best and worst efficiency with a variety of list configurations.

### Use constructs of a programming language to solve problems.

#### Objectives:

• Implement programs applications separated into multiple file modules.
• Evaluate bitwise operations including bitwise and, or, exclusive-or, shift, and compliment.
• Define implementations of data structures using bitwise operations.
• Utilize generic template classes for data type independence.
• Describe and utilize the boolean (bool) data type in a variety of algorithms including an array of boolean values.
• Define arrays, array indexing, and array processing using loops.
• Apply dynamic data allocation with appropriate use of keyword "new."
• Define potential risks and errors that could occur using dynamic data allocation.
• Perform hexadecimal counting and required conversations to and from decimals.
• Explain exception handling and implement a basic exception handling programming construct.

### Perform critical analysis to create working software solutions.

#### Objectives:

• Analyze alternative solutions to a given programming problem and select the best approach.
• Develop and implement a variety of testing strategies to verify correctness of programs.
• Diagnose and debug syntax, run-time, linker, and logic errors to create a working and correct software solution.
• Document program source code for clarity and readability using accepted documentation standards including comments, indentation, and other techniques.
• Integrate and re-use previously working program code into new software development.
• Develop systematic test plans, create test cases and test data to verify program correctness.
• Execute tests and correct logic errors based on test results.
• Build user-friendly computer programs for a variety of real-world problems.

### Define and practice basic principles for software engineering and design.

#### Objectives:

• Describe a variety of simple design methods and techniques for computing algorithms.
• Define information hiding, its value, and how it is implemented using a programming language.
• Define fundamental software engineering principles including the software life cycle, software quality, and basic software testing methods.
• Define the value of software documentation and utilize basic documentation techniques including definition of preconditions and post-conditions.
• Describe methods to desing generic and re-usable data structures and classes.

### Implement abstract data types as basic custom classes.

#### Objectives:

• Define the concept and value of data abstraction.
• Define the abstraction levels for defining data including the abstract, implementation, and application levels.
• Describe basic classifications of abstract data type operations and distringuish between transformers and observers for a variety of data structures.
• Create and apply a basic class to implement and abstract data type.
• Describe the purpose and value of class constructors.
• Define "set" and "get" methods necessary for a class to protect private data members.
• Instantiate objects, and call their member functions, and apply objects to solve a basic software problem.

### Examine a problem domain and model an object-oriented solution.

#### Objectives:

• Identify object attributes and behaviors and determine significant events that define a problem.
• Specify objects that exist within system boundaries and identify object relationships and interactions.
• Determine hierarchical relationships between objects and determine the need for inheritance to implement object oriented principles.
• Classify object relationships in terms of access, ownership, inheritance.

### Design classes to implement object-oriented solutions.

#### Objectives:

• Use access specifiers in class creation.
• Create destructor member functions and define the necessity for destructors.
• Describe the necessity and implementation of copy constructors for various dynamically allocated classes.
• Pass objects to functions.
• Categorize accessor, mutator, and iterator member functions.
• Specify scope of objects, methods, and attributes.
• Describe different access specifiers for derived classes.
• Override base class functions in the derived class.
• Use virtual functions to implement polymorphism.
• Distinguish between assignment and initialization.

### Apply various data structures to solve problems.

#### Objectives:

• Describe fundamental operations of a sequential list.
• Describe, analyze, and modify unsorted and sorted lists implemented with arrays.
• Implement array-based list searching using both linear search and binary search.
• Describe, analyze, and modify unsorted and sorted lists implemented with linked structures.
• Build general data nodes for use in various dynamic data structures.
• Apply an array-based list class to implement a software solution to a practical problem.
• Apply a linked list class to implement a software solution to a practical problem.
• Describe and trace linked list implementations using arrays.
• Describe variations of linked lists including circular and doubly linked lists.
• Describe the fundamental operations of a stack abstract data type including push and pop.
• Describe, analyze, and modify stack classes implemented with arrays.
• Describe, analyze, and modify stack classes implemented with linked structures.
• Apply a stack class to implement a practical software solution to a practical problem.
• Convert arithmetic expressions to and from infix notation, prefix notation, and postfix notation and convert arithmetic expression patterns using stacks.
• Describe the fundamental operations of a queue abstract data type including enqueue and dequeue.
• Describe, analyze, and modify queue classes implemented with arrays.
• Describe, analyze, and modify queue classes implemented with linked structures.
• Describe a basic queuing simulation using a random number generator.
• Apply a queue class to implement a practical software solution to a practical problem.

### Apply tree data structures to solve problems.

#### Objectives:

• Define a tree data structure and differentiate from a common tree and a binary tree.
• Describe the fundamental operations of a binary search tree including special terminology related to tree data structures.
• Describe, analyze, and modify a binary search tree implemented using linked structures.
• Apply a queue class to implement a practical software solution to a practical problem.
• Define tree traversal patterns including preorder, inorder, and postorder traversals.
• Relate binary tree traversal patterns to creation and overall balance.
• Describe a binary expression tree and relate tree traversal patterns to arithmetic infix, prefix, and postfix notation.
• Define a heap data structure and its relationship to trees.
• Implement a heap using arrays and describe the algorithms for inserting and deleting data with heaps.
• Describe and analyze a heap implemented using linked structures.
• Apply a heap to class to implement a priority queue.
• Describe the purpose of hashing and the function of a hash function.
• Compare and contrast a hash table with a list and define attributes of a good hash funchtion.
• Describe methods for managing data collisions for a hash table operation.
• Describe and trace a data structure build using hashing and chaining of linked lists.
• Define a graph data structure and represent the edge set and vertex set of a graph.
• Compare and contrast undirected graphs, directed graphs, and weighted graphs.
• Represent a graph data structure using an adjacency matrix.
• Describe the fundamental operations of a graph data structure.
• Define graph traversal patterns including depth-first and breadth-first search.
• Describe various problems for which graphs can be applied to represent data patterns.

### Apply recursive programming to solve problems.

#### Objectives:

• Compare and contrast recursive and iterative algorithms.
• Define the value and appropriate uses of recursive programming.
• Create recursive algorithms including definition of the base case and general case for function returns.
• Trace recursive algorithms and define the behavior of computer algorithms running recursive algorithms.
• Implement a variety of algorithms using recursive approaches.
• Integrate recursive strategies into sorting algorithms as well as for processing various non-linear data structures.