Course Information for Fall 2013
Time: MWF 10:00-10:50
Place: Roberts 312
Final exam: Thursday December 12th at 6pm (Exam 6)
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
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.
- 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.
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.
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
Stacks and queues
Trees and heaps
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.