CMPS 223, Data Structures and Algorithms
Course Description

Computer Science Department
California State University, Bakersfield
V2, 6/5/2003

Catalog Description:

Introduce the fundamental concepts of data structures and the algorithms on the foundation provided by the CMPS221-222 sequence within the framework of object-oriented programming methodology. Topics include recursion, fundamental data structures (including stacks, queues, linked lists, hash tables, Binary trees, and graphs), and the basics of algorithmic analysis.

Prerequisite:

CMPS 222

Units:

5

Coordinator:

Woogon Chung

Goals:

To provide the students with the knowledge and understanding of: the basis for

- both data and data type abstractions, and

- implementation possibilities for typical data structures, and related processing algorithms.

Current Text:

 Kruse and Ryba, Data Structures and Program Design in C++

Topics:

· [AL1] Object-oriented design: problems are analyzed via Object-Based Design paradigms

· [AL2] Basic algorithm design: Searching, Sortings are studied in depth

· [AL1,2] Algorithms and problem-solving: Classic techniques for algorithm design; problem-solving in the object-oriented paradigm; application of algorithm design techniques to a medium-sized project

· [AL3] Basic algorithmic analysis: Asymptotic analysis of upper and average complexity bounds; identifying differences among best, average,

and worst case behaviors; big "O" notation; standard complexity classes; empirical measurements of performance; time and space tradeoffs in

algorithms

· [PF4] Recursion: The concept of recursion; recursive mathematical functions; simple recursive procedures; divide-and-conquer strategies; recursive backtracking; implementation of recursion; recursion on trees and graphs

· [AL3] Fundamental computing algorithms: Searching algorithms, Sorting algorithms in contiguous array, link and binary tree search and

tree sorting.

· [PF3] Fundamental data structures: Pointers and references; linked list structures; implementation strategies for stacks, queues, and hash table

implementation strategies for trees.

· [PL6, SE8] Software engineering: Software project management; building a mid-sized system, in teams, with algorithmic efficiency in mind.

Laboratory:

 2.5-hours lab exercise to practice the implementations.

ACM/CSAB Category Content:

[AL1,2]	Algorithms and problem-solving	0.5
[PF3]	Fundamental data structures	1.0
[PF4]	Recursion	1.0
[AL3]	Basic algorithmic analysis	0.5
[AL2]	Algorithmic strategies	0.5
[AL3]	Fundamental computing algorithms	0.5
[PL6]	Software design	0.5
[SE8]	Software project management	0.5

Oral and Written Communication:

Students are required to submit documentation with their submitted projects.

Social and Ethical Issues:

Software reuse via available libraries of classes (such as Gnu libraries) and other open resources.

Encouraged to collaborate to develop moderate-sized project.

Problem Analysis:

UML description of the problems in the analysis phase.

Solution Design:

 UML description of the solution in the design phase.

Version & Date

Version 2, 6/5/2003

Comments

Based on ACM curricula 2001 in the format of ABET sample course description.