### Course Information for Fall 2013

Time: MWF 10:00-10:50

Place: Roberts 312

Final exam: Thursday December 12th at 6pm (Exam 6)

### Instructor Information

Prof. Stephanie R. Taylor (Lectures)

Office: Roberts 224D

Email: s r taylor _at_ colby _dot_ edu

Office hours: M 1:30-3:30, T 2-5, R 1:30-3:30

By appointment (email me), and whenever my door is open

Prof. Kyle Burke (Labs)

Office: Roberts 224C

Email: k g burke _at_ colby _dot_ edu

For Kyle's office hours, see his schedule

### Catalogue description

CS 231 Data Structures and Algorithms. An introduction to the primary data structures and algorithms of computer science. Data structures to be covered include stacks, queues, lists, trees, graphs, heaps, and hash tables. Algorithms include searching and sorting and insertion, deletion, and traversal for common data structures. Students will learn and use Java for programming assignments. Prerequisite: A grade of C- or higher in Computer Science 151. Four credit hours.

### Learning goals

- Students understand the advantages and disadvantages of fundamental data structures and can implement them using object-oriented design principles.
- Students understand, can implement, and can calculate the time and space efficiency of classic search, sort, and traversal algorithms, including the use of big-Oh notation.
- Students understand the tradeoffs between different implementation of data structures and algorithms and can make appropriate design decisions based on application data requirements.
- Students can use fundamental data structures and algorithms appropriately to solve a variety of computational problems.
- Students can communicate the result of their work and describe an algorithm.

### Prerequisite

CS 151. You should know how to program in at least one programming language; most students who took CS 151 will know Python. Although Java is used as the programming language in this course, no prior experience with Java is necessary.

### Course Objectives

This course develops some of the fundamental skills used in computer science: data structures, algorithms, and computational analysis. Data structures refer to the ways of organizing and storing information in computer programs. Algorithms operate on data to sort, search, or modify information. Algorithm analysis provides the tools necessary to determine which data structures and algorithms are best suited for a particular application.

By the end of this course, you should be able to:

Solve computational problems in the Java programming language using data structures and employing object-oriented design principles and adequate documentation.

Implement a data structure based on an abstract data type definition with appropriate use of data encapsulation and proper consideration of class invariants.

Implement searching, sorting, and traversal routines, and analyze their time and space complexity using big-Oh notation.

Select an appropriate data structure to use in a program based on application data requirements and access patterns.

Communicate the results of your work and describe algorithms to an audience of your peers.

The following is a list of topics we will likely cover, although not necessarily in this order:

Object-oriented design: encapsulation, composition, inheritance, interfaces, and polymorphism

Lists: array-based and linked

Searching and sorting

Algorithm analysis

Recursion

Stacks and queues

Trees and heaps

Graphs

Hash tables

### Recommended Textbook

There is no required textbook. Instead you are encouraged to use the many free online Java resources.

One such resource is the book by Clifford Shaffer entitled *A Practical Introduction to Data Structures and Algorithm Analysis*, Java version of Edition 3.2. It is available free online at http://people.cs.vt.edu/~shaffer/Book/index.php

### Links to Java Language Resources

For more resources, and links to free Java development environments, go to the reference materials page.