CS 221 Syllabus

Data Structures

Spring 2003

CIS Department

Saint Vincent College

General Information

Description

This course attempts to show the value of an object-oriented approach to data structures and their associated algorithms in the construction of software that is correct, efficient, and easy to maintain. The C++ programming language is used because of its power and widespread use, though not all features of the language will be studied. The course deals with the implementation of abstract data types, their use in creating application software, and the comparison of various approaches in terms of efficiency and value. The Standard Template Library is introduced.

It is assumed that the student already knows how to program in C++ at a level consistent with completion of CS 111 and is familiar with the more basic data structures (such as stacks, queues, and linked lists) and algorithms (such as bubble sort and binary search). Recursion and software design should also be familiar. The course will begin with a review of basic data structures, with an emphasis on the object-oriented approach. Topics covered include list-based tables, inheritance, exceptions, binary trees (especially binary search trees), heaps and heapsort, hash tables, AVL trees, B-trees, the sorting of external files, and the Standard Template Library. Mathematical tools such as loop invariants and algorithm analysis may also be used. If time allows, additional topics such as graphics and the construction of a Windows application, may be included.

Why Take This Course

This is a required course for CIS majors. It provides key tools needed to do serious software development, since software development often requires the use of sophisticated data structures and algorithms. In addition, a considerable amount of professional software development is done using the C++ language.

Course Goals and Means of Assessment

Grading and Course Policies

Letter grades will be assigned according to the scheme found in the current College Bulletin. The nature of the exams may vary. Ask the instructor before each whether or not it will be of the open notes variety. Exams will be announced in advance. Cell phones and pagers should be turned off and put away during exams.

Attendance is expected. Exams and programming assignments are based primarily on material discussed in class. The Associate Academic Dean will be contacted in regard to any student who misses a lot of classes. Normal attendance for a course is to miss a total of at most 1 week's worth of classes during the semester. Student performance is bound to deteriorate when classes are missed. In order to emphasize the importance of attendance, the policies outlined below will be used. Do your best to improve your grade: attend class, do the assignments, ask questions, and try to answer questions in class! If you begin to feel lost, ask the instructor for assistance, see a tutor for help, or work through the difficulties with the help of another student in the course. Do not let yourself get behind!

Make-up exams are strongly discouraged. If possible, take the regularly scheduled exam. For an excused absence for a significant reason, the instructor may agree to give a make-up exam. Whenever possible, see your instructor ahead of time if you know you must miss an exam (e.g. due to sports). If the documentation or reason for the absence is weak, you can count on receiving a significantly more difficult exam! Do ask for a makeup exam, however, if you have a good reason to miss, as it is understood that illnesses and other complications do happen. Students participating in sports teams are required to provide the instructor at the start of the semester with a schedule of games that might conflict with class.

Homework generally consists of programming assignments. Some in-class exercises may be used that count as 1/2 of a regular homework assignment. Students may be assigned to small groups for the purpose of doing some of the in-class exercises and homework assignments. Other homework assignments will be given that must be done separately by each individual. The group homework is given to allow students to learn from each other, to enable the creation of larger and more complex software products, and to provide practice at a cooperative project like those demanded by many job situations. Further information about the group assignments will be provided during the course.

Every programming assignment should list all sources that contributed to the solution. This would include the individual student (on an individual assignment) or the students assigned to a group (in a group assignment). It may also include the instructor, a tutor that was consulted, a reference book, a web site, etc. You may consult other students who are not part of your group as long as your question is small in scope and that you list the name of the student consulted at the top of your program. "Small in scope" excludes showing another student your entire program, or seeing that person's program, or working out the design of the whole program together. Sharing on that larger scale often amounts to one person copying the mistakes of another or getting a free ride on the efforts of another. A good rule of thumb is not to look at more than 1 screen of another person's code. Anyone who needs help on problems of larger scope should consult the tutors and/or the instructor. Further discussion of collaboration versus copying will be done in class to clarify the matter.

Intellectual honesty is important. If homework solutions show work that is largely copied, it is program plagiarism and is not acceptable. All instances of academic dishonesty, whether program plagiarism or cheating on an exam, will be referred to the administration for appropriate action.

Late assignments received within 48 hours of the deadline will be graded, but with a penalty of 15 percent. After 48 hours, any late assignment will receive a grade of zero. Since partial credit is given, it is usually best to turn in what you have at the original deadline. Assignments are due anytime on the date given and are normally turned in electronically by placing a copy in the HW221 mapped network drive. Exceptions to these deadlines are only granted for serious reasons and normally require written documentation of the reasons.

Be sure to read and follow the CIS Department Policies statement, available under the CIS Department Web Page. (This statement covers especially the proper use of departmental computing facilities and department-wide course policies.) In addition, read the Regulations section of the College Bulletin (which covers such things as grading and academic honesty) and the Student Handbook (especially concerning academic honesty as well as the misuse of technology).

Students with documented disabilities should meet with the college's disability counselor and the course instructor at the beginning of the semester to find reasonable accommodations.