PROPOSAL FOR A NEW COURSE

Date of proposal: 4/10/06

Title: Algorithms and Design

Department and Course Number: CSCI 205

Crosslisted?   Yes   No X     If yes, crosslisting department and number:

Credit: 1   Hours/week: 6

One-time:     or    Permanent Offering: X

Instructor: Steven Huss-Lederman

How will this course be taught, given present staffing, without creating a course overload?

This course proposal is part of a comprehensive change to the computer science curriculum. The course load under this proposal will not create an overload.

Are there any course fees? If so, specify what the course fees are intended to cover.

None

Prerequisite(s):

Computer Science 201.

Catalog description (50-150 words, please):

If applicable, include the following language at the end:  “May be repeated for credit if topic is different.”

Covers many basic data structures including advanced linked-lists, skip lists, general and balanced trees, hashing, and graphs along with algorithms including diverse sorting methods. Details of complexity analysis and recursion are covered. In contrast to Computer Science 201, students will learn and implement the details of these algorithms. Furthermore, students will design and implement solutions to problems. Finally, students learn to analyze the tradeoffs in choosing different data structures and algorithms. (LW)

Additional course content description (aims, purposes, etc.) beyond the catalog description:

This course in intended for someone with an interest in computer science. Though it is a follow-on to CSCI 201, it has a very different flavor. The emphasis is on taking the conceptual ideas learned in CSCI 201 and augmenting that information with details on how computer scientists implement these techniques. Thus, the techniques themselves, rather than the application, is the focus of the course. It is also imperative that students be able to apply these ideas in new situations where the concepts apply but changes are needed to be viable. Students also gain a deeper understanding of how computers actual deal with software through a detailed study of recursion. Additionally, students learn the mathematical basis of complexity and recursion. They also apply complexity in more complex situations. Through extensive programming exercises, students will significantly increase their ability to implement software and design solutions to general problems.

The lettered/numbered lines below come from CC2001. Underlined items are considered essential to a basic curriculum in computer science. Numbers in () indicate minimum number of hours to cover in a lecture style according to CC2001.
Items with a * indicate we plan to cover them in multiple courses.
Other lines include additional topics we plan to cover or clarification of topics we will cover within a CC2001 topic.

• *PF2. Algorithms and problem-solving (6)
  apply algorithms to solving problems: both on paper and with code
• *PF3. Fundamental data structures (14)
  advanced linked-lists, skip list, general and balanced trees, hashing, graphs, and heap implementation
• *PF4. Recursion (5)
  Activation records, vs. iteration, induction
• AL1. Basic algorithmic analysis (4)
  Lots big-O for algorithms, math basis & concepts of big-O
• AL2. Algorithmic strategies (6)
  Tradeoff of data structures
• AL3. Fundamental computing algorithms (12)
  details of sorting, as relate to data structures
• created exceptions; design of solution, and solidifying coding from 131: esp references & larger solutions/design

Course goals/objectives/outcomes: 

At the end of this course students should be able to:

• implement a large number of the classic data structures and algorithms
• learn more advanced data structures and algorithms
• analyze the tradeoffs between different data structures and algorithms in the context of new problems
• create design documents and critically analyze designs done by others
• appreciate the mathematical basis for complexity and recursion

Course structure. Check all that apply:

 Lecture/Discussion X      Studio     Lab/Workshop X    Other (Specify)

If current library or equipment holdings are inadequate, estimate the cost of additional holdings required.

adequate.

Please attach names of a proposed text and/or core readings.

Java Structures: Data Structures in Java for the Principled Programmer, 2nd ed., Duane Bailey, ISBN 0-07-239909-0, 2003. This is the same textbook as CSCI 201. We hope to be able to utilize the same book but will consider separate texts to better meet the goals of each course.

Form revised 11/04