CIS300 Syllabus Spring 2005 CIS300 Spring 2005

Algorithms and Data Structures: Syllabus

Lecture: MWF 1:30pm, Thompson Hall, room 101
Instructor: David Schmidt (219A Nichols Hall; phone: 532-6350)
Teaching Assistants: John Homer (jhomer@cis.ksu.edu) and Katherine Meadows (kmeadows@cis.ksu.edu).

Prerequisite: CIS200 or equivalent; experience with Java Version 1.2 or newer.

Textbook: None --- lecture notes will be posted each week at the web page, http://www.cis.ksu.edu/~schmidt/300s05/Lectures. There is an optional course text, Data Structures and Other Objects Using Java, by Michael Main, Addison-Wesley. Publishers.

Course Structure: We meet for lecture three times each week, and you will receive about 6 programming assignments, which must be completed in the Java programming language. There will be about 3 exams. If you want an idea of what to expect, see the materials at http://www.cis.ksu.edu/~schmidt/300f04/

Course web page: http://www.cis.ksu.edu/~schmidt/300s05  Check the site regularly for announcements and assignments.

Support: You may use the University's computing facilities or your own computer. You are responsible for obtaining computer accounts and mastering basic computer usage.

Objectives and Topics

This course is about data structure: how to intelligently organize data so that it can be saved and retrieved quickly. We will learn structures for organizing data that yield elegant solutions to problems that are difficult to solve otherwise. Finally, the course gives us additional practice at building multi-component programs whose subassemblies can be saved and reused.

Topics will be covered in this order:

  1. Review of software design, packages, interfaces, and execution semantics
  2. Review of computer architecture and operating systems
  3. Aspects of a data structure --- specification, interface, implementation
  4. The array as a data structure and its application to sorting and searching; time complexity
  5. Stacks and their array and linked-list implementations
  6. Queues and their linked-list implementations
  7. List variants: doubly-linked lists and cons-lists
  8. Binary trees and their variants: ordered (``search'') trees, n-ary trees, spelling trees
  9. Hash tables and dictionaries
  10. Heaps and priority queues
  11. AVL trees, if time allows
  12. Graphs, if time allows

Course Policies

Prerequisite policy: This course's prerequisite is CIS200, and if you have not taken CIS200, the Engineering College might drop you from the course without notice. Please see Dean Hightower of the Dean's Office in Rathbone Hall if you are uncertain of your status.

Drop policy: It is your responsibility to drop the course if you are enrolled but decide not to complete the course --- there are no ``automatic'' drops due to nonattendance. February 16 is the last day to drop a course without a "W" recorded on your transcript; March 20 is the last day to drop a course (with a "W"). KSU allows a retake of a course with removal of the prior grade, at most once per course, for a maximum of five courses.

Academic honesty policy: The letter grade you receive for the course is meant to reflect your mastery of the course material, and you must read http://www.ksu.edu/Honor for the University's policy regarding academic honesty.

CIS300 is like an English Composition course --- the ``compositions'' (Java programs) you submit must be written by you. Therefore, the inclusion of another person's Java code --- from handwritten, typed, or electronic formats --- into your submissions without express permission of the Instructor is forbidden. It is acceptable to discuss with others the assignments and design of solutions, but such collaboration must cease when you write Java code. Similarly, under no conditions will team-written submissions by multiple students be accepted for course credit. Such ``teamwork'' usually means that one student did most all the work and learning and the other student mostly watched and copied. You will do team projects in your third- and fourth-year courses.

Attendance policy: You are responsible for the material presented and assigned during the lectures. If you miss a lecture, consult a fellow student or the instructor regarding what you missed.

Academic accommodation for disabled students policy: If you have a physical or learning disability that requires special accommodation, please notify the Instructor within the first two weeks of the course.

Other official policies are listed at http://www.cis.ksu.edu/Department/Policies/syllabuspolicy.shtml