CSci 433: Algorithm and Data Structure Analysis
Spring Semester 1999
Syllabus

Locations

The spring semester 1999 class meets in 351 Weir Hall at 11:00 a.m. to 12:15 p.m. on Tuesdays and Thursdays.

The class is taught by Prof. Conrad Cunningham, whose office is in 312 Weir Hall. The official office hours for this class are 10:00 a.m. until Noon on Mondays and Wednesdays and by appointment at other times.

Prof. Cunningham's voice telephone number is (601) 232-5358 and fax number is (601) 232-5623. His WWW home page is http://www.cs.olemiss.edu/~hcc/ and his email address is cunningham@cs.olemiss.edu.

The WWW home page for this class is http://www.cs.olemiss.edu/~hcc/csci433/ and the anonymous FTP site is http://ftp.cs.olemiss.edu/pub/cunningham/csci433/99spr/.

The final examination for this class is scheduled for 8:00 a.m. on Thursday, 6 May 1999.

Course Goals

The goals of this course are to extend and deepen the student's knowledge and understanding of algorithms and data structures and the associated design and analysis techniques. It examines previously studied algorithms and data structures more rigorously and introduces the student to "new" algorithms and data structures. It focuses the student's attention on the design of program structures that are correct, efficient in both time and space utilization, and defined in terms of appropriate abstractions.

New Course Description for 1999 Catalog

Study of the design and analysis of algorithms and data structures. The topics include analysis techniques, sorting, searching, advanced data structures, graphs, string matching, and NP-completeness.

New Prerequisites for 1999 Catalog

Successful completion of CSci 211 and Math 301. (CSci 112 is a prerequisite for CSci 211.)

Source Materials

Required textbook:

Michael T. Goodrich and Roberto Tamassia. Data Structures and Algorithms in Java. Wiley, 1998. ISBN: 0-471-19308-9.

Optional textbook:

Any good introductory book on Java programming.

Judy Bishop. Java Gently: Programming Principles Explained, Second Edition, Addison-Wesley, 1998. ISBN: 0-201-34297-9.

Readings:

Various journal, conference, or WWW materials as appropriate.

Software:

Sun's Java Development Kit (JDK) and other software defined later

Course Topics

1. Design principles
2. Analysis tools
3. Sequence ADT
4. Priority queue ADT (used, but not covered in class)
5. Dictionary ADT
6. Sorting, sets, and selection
7. Graphs
8. Strings (not covered in class)
9. Fundamental techniques
10. NP-completeness

Graduate Students

Several students in the class are computer science graduate students who taking this class as a condition for full admission. In accordance with current departmental policy, such students will be assigned work beyond that assigned to undergraduate students.

Graduate students in other fields should not be enrolled in this class without the explicit permission of their home department. Any students in this category are expected to provide the instructor with a note from their advisor or department chair indicating such permission.

Professional Conduct

As a student in CSci 433, you are expected to conduct yourself in a professional manner according to the Honor Code of the School of Engineering, the Information Technology Appropriate Use Policy, the M Book, and any other relevant policies.

Limited Collaboration Policy. Unless otherwise indicated, any homework assignment or programming exercise given in this class will be an individual assignment. The work you submit is to reflect the knowledge, understanding, and skill that you have attained as an individual. However, the instructor does want to encourage the development of a community of scholars who are actively engaged in discussion of the ideas related to this course. With this in mind, you are allowed to discuss solutions of the homework and programming problems with other students if done so according to the following guidelines:

• You may discuss ideas for homework and programming assignments with your classmates. However, you cannot collaborate on writing the solution or the program code. That is, you can talk about the problems and ideas for solving them, but you cannot write things down with anyone else. You are, of course, prohibited from copying or seeing another student's written solution, and you are not allowed to show your work to anyone else.

• You should accept help with care. If you work too closely with another student, you might mislead yourself into believing that you understand the concepts and techniques better than you actually do. Don't forget that the instructor has office hours and can probably give you hints or suggestions to get you started.

• You should give help with care. Do not help anyone too much. When you have solved a problem, it is tempting to just tell other students how you solved it. Instead, try to allow them to come to the solution on their own. Maybe give them a hint to help them get "over a hump." Remember that helping someone too much will hurt them in the long term if they can't work through problems on the exams by themselves. So avoid the temptation to do so. If you can't help other students without giving away the whole solution, direct them to see the instructor (who may or may not have a way to "edge" them toward the solution).

• You are not obligated to help anyone. If you feel uncomfortable helping another student for any reason, please direct them to see the instructor.

• Except as described above, all work in this class is covered by the School of Engineering's Honor Code statement on plagiarism. It is plagiarism "to knowingly deceive, copy, paraphrase, or otherwise misrepresent your work in a manner inconsistent with professional conduct".