COMPUTING SCIENCE 210
Algorithm Analysis and Data Structures

COURSE DESCRIPTION AND REGULATIONS

Fall Term, 2005

Quick Links

Course Outline

Assignment Weightings

Percentage Conversions

Instructor: Dr. Jonathan Mohr
Office: N104	Phone: 679-1514
Office Hours: see instructor's home page	E-mail:

Calendar Description:

Introduction to algorithm analysis and O-notation. Abstract data types (lists, stacks, queues, trees, priority queues, dictionaries, sets), their implementations (linked lists, binary trees, heaps, binary search trees, balanced search trees, hash tables), and associated algorithms (iterators, inumerators, traversal, sorting, searching, retrieval).

Requirements:

Prerequisites -- CSC 120, MAT 110 or 111, and 120.

Corequisite -- MAT 250.

See also the Calendar descriptions of all Augustana Computing Science courses.
 

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 computer 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 Java as the application language, and will use advanced features of Java, including interfaces, inheritance, abstract classes, polymorphism, exceptions, and method 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 will be completed within the 75-minute lab period and in which
   • 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, or
   • problems and exercises are discussed and solved as a class or in groups;
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.

We will refer to the former type as "lab exercises" and to the latter as "programming assignments".

Textbook:

Michael T. Goodrich and Roberto Tamassia, Data Structures and Algorithms in Java, 4th edition (Wiley, © 2006).

In accordance with Augustana's policy on attendance and course work, any student who has an inordinate number of absences in a course or who neglects his/her academic work may be suspended from the course (which includes being refused permission to attend class sessions, submit assignments, and write examinations, including the final examination).

In this course, any student missing more than two class or lab sessions or failing to submit more than one assignment may be suspended from the course.

A suspended student will be notified of the suspension by e-mail and by paper mail addressed to the student's assigned campus mailbox. It is the student's responsibility to arrange a meeting with the instructor to discuss the terms under which the suspension may be lifted.

Grading Policy:

Grades will be awarded using the Alberta-wide standard alpha four-point grading system. 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 one set of written exercises, four programming assignments,a mid-term exam, and a final exam.

The due date for each programming assignment is indicated in the course outline. The due date for each written assignment will be indicated as part of the assignment specification. Late assignments will be subject to a 1% per hour penalty, except for a valid medical excuse or other reasonable cause approved by the instructor prior to the due date.

The weighting of exams and assignments will be as follows:

Unless otherwise specified, each programming assignment will be worth 10%.

Academic Integrity:

The University of Alberta is committed to the highest standards of academic integrity and honesty. Students are expected to be familiar with these standards regarding academic honesty and to uphold the policies of the University in this respect. Students are particularly urged to familiarize themselves with the provisions of the Code of Student Behaviour and avoid any behaviour which could potentially result in suspicions of cheating, plagiarism, misrepresentation of facts and/or participation in an offence. Academic dishonesty is a serious offence and can result in suspension or expulsion from the University.

Guidelines for Academic Integrity in This Course

All work submitted for grading must be your own, unless a group of students have arranged with the instructor in advance to complete a given assignment as a group project. Programs that appear to be the same, to have been derived from a common source, or to have been fraudulently obtained or created by any means will be given a failing grade.

Some of the practices which are regarded as inappropriate academic behaviour (academic dishonesty) are:

• submitting someone else's work as your own;
• writing or creating a work in the knowledge that it will be fraudulently submitted by someone else as his or her own (whether or not you receive payment);
• altering someone else's work (e.g., by changing the variable names) to conceal the fact that it was fraudulently obtained and submitted;
• using portions of another person's work (including algorithms or code from textbooks, magazines, or other sources) without acknowledgment.

Students are encouraged to assist one another in completing assignments, especially by explaining concepts to each other, by helping one another to learn the use of system utilities and programming environments, and by assisting each other in locating bugs. However, in order to avoid inadvertently becoming involved in a case of academic dishonesty (for example, when another student submits a program which is suspiciously similar to yours), you are advised to:

• protect your computer account with a secure password, changed frequently;
• ensure that copies of your program or work-in-progress are securely recycled or shredded;
• discuss programming principles and techniques with other students, not particular lines of code.

Course Outline:

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

NOTE: Policy about course outlines can be found in §23.4(2) of the University Calendar.

Links

Course Materials Index

Top of this Document

Instructor Contact Information