CS 261   (4 credits)
Data Structures
Spring 2005

Schedule        Announcements and Clarifications

Score Posting        Links

Lecture Owen 103   MWF 3:00-3:50 (3/28/05 - 6/3/05)
Instructor
Prof. Timothy A. Budd (contact info)
Office Hours MWF 10:00-11:30, Dearborn 218
Teaching Assistant Joey Lawrance, lawrance@eecs.oregonstate.edu
(Office hours MW 4-5:30, F 1:20-2:50 in Dearborn 119)
Prerequisites CS 162, Math 232
Textbook Timothy Budd, Classic Data Structures in Java, Addison-Wesley, 2001
Course Learning Objectives
  1. Define and distinguish between the following concepts as they relate to object oriented programming: abstraction, implementation, encapsulation, modifiability, inheritance, modularity, polymorphism, specialization, layering, and composition.
  2. Write a program that defines one or more abstract data types as well as create one or more implementations for each abstract data type.
  3. Describe why object oriented programming techniques typically improve software correctness, maintainability, modifiability, reliability, and robustness.
  4. Given an algorithm or an example of program code that may contain iterative constructs, indicate the asymptotic time complexity of the algorithm or code.
  5. Given a data structure (either linear such as a vector or linked list or non-linear such as a tree, heap, etc.), give the asymptotic time complexity of various operations (such as adding, finding, or removing individual elements or sorting all the elements). Likewise, given the asymptotic time complexity for various common operations on data structures, you should be able to indicate which abstract data type or types exhibit those execution characteristics.
  6. Answer questions regarding the space utilization of common data structures in terms of the long-term storage needed to maintain the structure as well as short-term memory requirements of operations such as sorting.
  7. Describe the properties, interface, and behavior of basic abstract data types such as collection, bag, indexed collection, sorted collection, stack, and queue.
  8. Write general-purpose, re-usable, object-oriented data structures that implement one or more abstract data types. You should also be able to compare and contrast the operation of common data structures (such as linear structures, priority queues, tree structures, hash tables, maps, and graphs) in terms of time complexity, space utilization, and the abstract data types they implement.
  9. Write a program or function that correctly uses recursion to perform a specified task.
Schedule Check here every week; the schedule is subject to "adjustments"
In the past I have used a series of power-point lectures. This term I am going to be trying something different, this is admittedly experimental. I will evaluate the success of this approach as the term progresses, and adjust the schedule as necessary.
Communication There is a class mail list established for this course. I will use this to send e-mail to the entire class where appropriate. You can also use this as you wish, simply by sending e-mail to class-cs261@engr.oregonstate.edu.

There is also a web-based form you can use if you want to send anonymous e-mail to the professor. There is no way that mail generated from this source can be traced back to an individual.

Grades There will be a number of homework sets, programming assignments, two midterm exams, and a final. The grades for these will be weighted so that the homework is about half of the final grade, and the exams the remaining half.
Academic Honesty Policy See the university, college, department, and course policies.
Obviously, compliance is expected.