Department of Mathematical and Digital Sciences

Bloomsburg University of Pennsylvania

COMPSCI 355

Home • Policies • Schedule • Resources • Style Guide

**Fall 2016**

Tu/Th 2:00-3:15 in Navy 209

Professor: Drue Coles

E-mail: dcoles@bloomu.edu

Phone: 570-389-4626

Office: 235 Ben Franklin Hall

Office Hours: 11:00-12:00 Mo-Th and 3:00-3:30 Mo/We

**Text:**
Data Structures and Algorithms in C++, 2nd edition, Goodrich et al., John Wiley & Sons,
2011.

**Prerequisite:** COMPSCI-255 and MATH-185. In particular, students should be
able to implement linear data structures such as stacks and queues in C++, and write code
using the classes that implement these structures in the Standard Template Library. A basic
understanding of recursion and proof by induction (from MATH-185) is also assumed.

**Overview.**
Data structures are organized containers of information designed for efficient access or
updates. This course provides a comprehensive introduction to the design, analysis, and
implementation of non-linear data structures and of algorithms that operate on them. The
ideas of this course are language-independent but we will use C++ for implementation.

**Outcomes.**
Upon completion of the course you will be able to:

- determine the asymptotic complexity of algorithms and the tradeoffs implicit in different implementations.
- specify abstract data types and implement them as C++ template classes.
- choose correctly among different algorithms and data structures to solve a given problem.
- analyze and implement standard sorting, tree balancing, and general graph algorithms.
- apply techniques of recursive backtracking and dynamic programming.
- define NP-completeness and identify techniques for dealing with NP-complete problems in practice.

The Association for Computing Machinery (ACM) has identified 18 core areas of knowledge in computer science. The analysis of algorithms is one of these areas. The ACM recognizes that knowledge of fundamental data structures and algorithms, and the ability to reason about the efficiency of algorithms, are essential for both scientists and software developers.