PROPOSAL FOR A NEW COURSE

Date of proposal: 4/10/06

Title: Topics in Algorithms

Department and Course Number: CSCI 301

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

Credit: 1/2   Hours/week: 6 in one module

One-time:     or    Permanent Offering: X

Instructor: Darrah Chavey

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 205. Corequisite: Mathematics 160 or 200.

Catalog description (50-150 words, please):

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

Investigation of general techniques for the design, comparison, and analysis of different major classes of algorithms. The precise topic varies but possible offerings include: geometric algorithms; parallel and distributed algorithms; net-centric algorithms; analysis of algorithms; graph algorithms; and genetic algorithms. May be repeated for credit if topic is different.

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

The course generally looks at algorithms that are more sophisticated than what can be easily programmed by a college-level student. The focus is on the conceptual understanding of a collection of algorithms in a specific disciplinary focus.

Usually, the students will implement a small number of these algorithms, but will be expected to demonstrate understanding of many others within that focus area. Potential focus areas are listed in the catalog description.

We expect to offer a section of this course with a focus on an area selected with input from current majors at least every other year. At present, we expect to alternate such an offering with one which focuses more directly on topics recommended by CC2001. The topics from that curriculum recommendation are:

• AL5. Basic computability (6)
• AL6. The complexity classes P and NP
• AL8. Advanced algorithmic analysis

"Basic computability" refers to which kinds of problems can be solved by a computer, and which kinds of problems are known to be unsolvable.
"Complexity classes P and NP" refer to which classes of problems are solvable by a computer within a reasonable amount of time, and which are "theoretically" solvable, but apparently not within any reasonable amount of time (e.g., the life of the universe).
" Algorithmic analysis" refers to a precise mathematical analysis of the time that would be taken by certain algorithms to solve certain classes of problems.

Part of the purpose of this course is to give students the opportunity to customize, to some extent, the material of their upper-level course choices. They should be able to affect, to some extent, what precise course offering will be made, and should be able to choose from at least two different offerings to fulfill their major.

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.

• The topics are listed above.

Course goals/objectives/outcomes: 

• Students should understand a particular class of problems as studied by professional computer scientists
• They should understand at least some of the basic solution tactics used to solve, or approximate solutions to, that class of problems
• They should learn the approaches to at least one class of sophisticated algorithms, beyond the level of what can be expected of 1st or 2nd year students.
• While they should appreciate the difficulties and challenges of actual implementations of these algorithms, they should also do enough implementation or analysis of selected algorithms to appreciate the feasibility of solving such problems more generally.

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.

Will vary with offering.

Form revised 11/04