COMPUTING SCIENCE 210
Data Structures and Algorithms

COURSE DESCRIPTION AND REGULATIONS

Fall Term, 1998

Quick Links

Course Outline

Assignment Weightings

Percentage Conversions

Calendar Description:

Introduction to algorithm analysis and O-notation. Search and sorting algorithms. Mathematical algorithms. Tree and graph traversal algorithms. Abstract data types.

Requirements:

• Prerequisite -- CSC 120, MAT 110 or 111, and 120.
• Corequisite -- MAT 250.

Objectives:

1. to gain an appreciation for the value of separating the specification of an abstract data type from its implementation;
2. to understand the method and utility of analyzing the efficiency of an algorithm independently of any particular implementation on a particular comuter system;
3. to learn the differences between various algorithms of the same class (such as sorting algorithms) and various implementations of the same abstract data type so that the appropriate one may be selected for each particular application;
4. to increase the repertoire of algorithms and data structures which are at the student's disposal for future application in a variety of problem domains.

Method of instruction:

The lecture component of this course will present a wide variety of algorithms, abstract data types and possible implementations, along with the mathematical tools to analyze their efficiency and assess their appropriateness in different contexts. The course will use C++ as the application language, and will use advanced features of C++, including dynamic memory allocation, templates, function parameters, virtual functions, polymorphism, inheritance, and operator overloading, to implement generic abstract data types.

The lab portion of the course will consist of two types of applied experiences:

1. "closed" labs which it is anticipated will be completed within the 50-minute lab period and in which, typically, an implementation of a particular algorithm or abstract data type is provided and the student experiments with it to deduce its behaviour or modifies it to improve its performance;
2. "open" labs in which a problem or abstract data type is presented and students are assigned the task of writing a program to solve the problem or implement the ADT by working on their own outside of (or in addition to) the scheduled lab session.

Textbooks:

• Pothering and Naps, Introduction to Data Structures and Algorithm Analysis with C++ (West, 1995).
  [Errata list for this textbook is available here.]
• Dale, Weems, and Headington, Programming and Problem Solving with C++ (D.C. Heath, 1996).

Both textbooks are required, and material from them will be included on the exams. However, if you do not already have a copy of the Dale et al. textbook from CSC 120, you may wish to share the textbook with another student, since we will only be covering the last chapters of that text. (On the other hand, you may wish to purchase it if you do not feel confident of your skills in C++ programming, since it presents the basic constructs of the language in a clear fashion.)
 

Attendance and Course Work Policy:

In accordance with Augustana's policy on attendance and course work, any student who is absent from more than 15% of the lectures (i.e., four lectures) or who fails to submit two or more lab and/or programming assignments may be suspended from the course (which includes being refused permission to write the final examination).
 

Grading Policy:

Grades will be awarded using the Augustana University College nine-point grading system. (See also the verbal descriptions of the grade points.) For assignments marked in percent, the percent/grade equivalents in this course will be approximately as indicated in the following table:

Your performance will be evaluated through six lab assignments, four programming assignments, a mid-term exam, and a final exam. Assignments are due at the start of the class or lab period on the due date stated in the course outline or on the assignment specification. Assignments will be accepted for up to three days following the due date. Late assignments will be subject to a 5% per day penalty. Submissions will not be accepted after these deadlines without a valid medical excuse or for other reasonable cause approved by the instructor prior to the due date.
 

The weighting of exams and assignments will be as follows:

	Lab assignments:	24%
	L1 - 3%
	L2 - 3%
	L3 - 4%
	L4 - 5%
	L5 - 4%
	L6 - 5%
	Programming assignments	26%
	P1 - 5%
	P2 - 8%
	P3 - 6%
	P4 - 7%
	Mid-term exam	15%
	Final exam	35%

 

Course Outline:

The approximate dates on which the various topics of the course will be presented, along with an indication of which pages or sections of the textbook(s) are to be read in connection with each topic, are given in the accompanying course outline.

Links

Course Materials Index

Top of this Document

Instructor Contact Information