COMP282: Advanced Data Structures

Spring 2004 Syllabus

Contact Information:

Instructor: Jeff Wiegley Office: EA1407 (Fourth Floor, South-West Corner)
Email: jeffw “at” csun “dot” edu Office Phone: 818.677.2038
Web Page: http://www.csun.edu/~jeffw Office Hours: M: 1400 – 1500
W: 1845 – 1945
Th: 1700 – 1800

Prerequisites:

COMP182, COMP182/L, MATH150B. Prerequisites for this class (and all other Computer Science classes) are strictly enforced. If you are deficient in a prerequisite for this class you will be required to drop this course.

Required Textbooks:

Advanced Data Structures: COMP282 (A compilation of sections from Data Structures and the Java Collections Framework, Collins and Database System Concepts, Fourth Edition, Silberschatz-Korth-Sudarshan)

Course Objectives:

An introduction to advanced data structures (particularly persistent structures) using object-oriented design. Main memory structures: hash tables, trees. Architectural foundations for files. Large-scale sorting. Hash-based persistent structures. Graphs and Searching. Indexed files. Introduction to databases.

Lectures:

Course	Ticket Number	Days	Time [Begin-End]	Room
COMP 282	14790	MW	1730 - 1845	EN2126

Topics:

1. Linked Lists, Stacks and Queues (review of COMP182)

2. Graphs

3. Balanced Trees

4. File Structures

5. External Sorting

6. External Hashing

7. B-Trees

8. Introduction to DBMS

9. ER-modeling

10. Normalizing

11. Introduction to SQL

Programming Projects:

Students will be responsible for completing five programming projects. Projects are graded on a scale of 0 to 20 points. The projects must be implemented using JAVA. Programming does not have to be done on campus but submitted projects must compile and execute without errors on University standard equipment and software. If you do not have the necessary software for developing programming projects off-campus you can visit the Computer Science department Office and obtain a CD-ROM containing software applications and utilities that should provide you with a minimal set of what you need. Suitable JAVA SDK software can be downloaded for free from http://java.sun.com/j2se/1.4.2/download.html Please note that these tools do NOT self-install themselves or have any installation/removal features or support other than that which is outlined in the various README files and documentation that is distributed with the product itself.

Grading Criteria:

Assignments, Projects, Quizzes and Exams will be evaluated and graded individually.

Final grades will be computed according to the weighted average of all assignments, projects and tests as follows:

Participation: 5%
Projects: 20%
Exam 1: 25%
Exam 2: 25%
Final Exam: 25%

Exam 1, Exam 2 and the Final Exam will be “Open book” and “Open notes”. Collaboration on assignments, exams, quizzes and projects is not permitted.

Participation is a subjective evaluation given by the instructor and is almost always less favorable than the student believes is fair. Perfect attendance is not participating; it is simply supplying a reliable, temporary thermal source for the lecture room.

Final grades will be reported to the Office of Admissions and Records using the “plus/minus” format. Letter grades will be assigned according to the weighted average grade as follows (These limits may be lowered at the discretion of the instructor):

	A: 93	A-: 90
B+: 87	B: 83	B-: 80
C+: 77	C: 73	C-: 70
D+: 67	D: 63	D-: 60
	F: 0

Best efforts will be made to return graded materials during the second lecture following the date the materials were due.

Final Exam Schedule:

(This information is also available in your CSUN Course Schedule. Information published in the course schedule supersedes information published by the intructor. Any discrepenacies in times or locations should be brought to the attention of the intructor as soon as possible.)

Ticket Number	Days	Date	Time [Begin-End]	Room
14790	MW	Monday 05/24/2003	1730 - 1930	EN2126

Late Assignments, Projects and Tests:

Assignments submitted late will NOT be accepted. no exceptions.

”Make-up” exams and Quizzes will not be given.

All projects are to be submitted by e-mailing all source code, as e-mail attachments (do not cut and paste text), to the professor's e-mail address. All submissions MUST contain the Subject text: COMP282 submit project n where n is the number of the project being submitted.

Projects submitted late will be accepted within 14 calendar days following the due date. Late projects will be penalized 1+floor(N/2) points; where N is the number of calendar days late. Late submissions must be presented to the instructor in person or by arrangement. Projects are graded out of 20 points.

Anything slipped under office doors or otherwise not delivered properly will be disposed of and ignored entirely and will receive a grade of 0. Projects submitted more than 14 days late will not be accepted and will receive a grade of 0.

Contesting Grades

Any student who believes that an error was made regarding grading of any Exam, Project, Assignment or Quiz may contest the grade during office hours. Any evidence and arguments must be presented within 7 calendar days following the availability of the graded material in question. Request for a grading correction will subject the entire work for re-evaluation. This may result in an overall lower grade even if the original arguments are valid as any other mistakes, oversights or omissions will also be corrected, possibly to the disadvantage of the student.

Student Evaluations:

At some point, to be determined, during the end of the semester all enrolled students will be given the opportunity to fill out and return an evaluation of the Course and Instructor’s abilities and effectiveness. Your evaluation is important. These evaluations help the University tailor programs to better suit your needs and are used to provide the best instructors possible to serve you. These evaluations really do have a strong impact on the department and are the primary tool for the evaluation of the instructors. It is strongly encouraged that you participate in this process and provide your honest opinions.

Add/Drop Policies:

Class size is limited to 30 students per lecture. No students will be added to any lecture unless a seat in that lecture becomes available. Seats can become available by:

• Students voluntarily electing to drop the class.

• Students who are deficient in prerequisites will lose their seats for administrative reasons.

• Students who have their seat given away as outlined in the Initial Absence Policy section.

If you intend to drop the class please notify the instructor so that actions can be taken to fill the seat.

A sign-up sheet is provided for tracking those students who wish to add should seats become available. In the presence of empty seats students will be added with the following priority:

1. Students graduating this semester will be given the highest priority.

2. Regular students in the Computer Science or Computer Engineering department.

3. Regular Students NOT in Computer Science and “PBU” students.

4. Open University Students will be given the lowest priority and will not be considered until the third week of classes.

Procedures and requirements for dropping or withdrawing from the course are dependent on the academic calender. Students should consult with the Computer Science department personnel to determine the proper procedures for dropping the course if they wish to do so. It is easier and more economical to drop or withdraw from the class the earlier it is attempted.

Initial Absence Policy:

Students who miss the first AND second lecture of class without sufficient reason and prior notification to the instructor will have their seats given away if there are students waiting to add the class. Students who lose their seat will be asked to voluntarily drop the class; failure to drop the class will result in a grade of “F” or “U” being reported to the Office of Admission and Records at the end of the semester regardless of continued attendance or performance.

Academic Integrity

Instances of plagiarism, copying, cheating or any other acts of academic dishonesty will not be tolerated. Soliciting others for assistance with academic dishonesty or facilitating the academic dishonesty of others are in themselves forms of academic dishonesty. Students who are found to have committed such will automatically receive a grade of “F” for the course and will also be prosecuted according to the disciplinary regulations as provided for in the Student Conduct Code. Rules, definitions and procedures concerning academic dishonesty are documented in the Course Catalog under the index heading “Academic Dishonesty”. Do not test this policy; it is not worth it.

Disturbance Policy:

Disruptive or Threatening Behavior during Lecture will not be tolerated. This includes issues of harassment and hazing (which is a violation of the Student Conduct Code.) Anyone attempting to engage in such behavior will be removed from the classroom and may face further disciplinary action as provided for in the Student Conduct Code as stated in Section 41301 of Title 5 of the California Code of Regulations.

Examples of unacceptable conduct include, but are not limited to, the following:

• Inappropriate, disrespectful or uncivil responses to other students.

• Challenging the instructor’s authority.

• Excessive talking.

• Use of personal electronic devices such as pagers or cell phones.

• Improper use of equipment, materials or resources.

The purpose of this University is to provide the highest quality of education possible. All measures will be taken to insure that you are provided with a safe environment that best promotes learning.

Auditing Policy:

In order to best serve the students enrolled in the class it is not permitted to audit the class.

Feedback:

It is very important to your instructor that you receive the highest quality teaching. If at any time you have suggestions as to how the course, subject, instructor or any other aspect of your experience this fall can be improved please let the instructor know by any means your wish.

Seeking Help:

If you find that you are having trouble succeeding in the coursework you should immediately seek help and assistance. Many resources are available and provided to you by the University. These include, but are not limited to:

• Office hours: These periods are provided for you so that you may seek individual help and clarification from the instructor. If you are having trouble and you aren’t going to office hours you are missing out on a very useful resource.

• Other Students: You are not alone at this University. Other students may be able to help you and benefit from you by engaging in study sessions in the library, or at home. Colleagues are an excellent resource because of the shared perspectives and level of abilities. You may not collaborate on assignments or tests but you are encouraged to get together and discuss problematic conceptual areas or discuss sections and topics present in the book in order to increase your understanding of the material being presented in lecture and required for projects and exams.

• WebCT: Students can engage in persistent discussions through the use of the http://webteach.csun.edu/ message board. Please self register for the course titled “COMP282 Advanced Data Structures Wiegley” You are free to discuss topics on the discussion board but you may not provide significant code examples that would constitute academic dishonesty. If you aren't sure whether or not a code fragment would be permissible to post email the instructor to obtain approval before posting.

• Department Office and Chair. These individuals will know the best course of action for you to take in times of trouble. Especially if your trouble exceeds the scope of class material or are of a personal nature.

• If you are suffering from medical or health problems you should contact one of:

  • Student Health Center. Location: SHC
    Phone: 818.677.3493 or 818.677.3692(TDD)

  • Center on Disabilities. Location: SU 110
    Phone: 818.677.2684

  • University Counseling Services Location: SU 520
    Phone: 818.677.2366 or 818.677.7834(TDD)

Tentative Course Itinerary:

The tentative schedule for the material being covered and exams is as follows (Dates and Material Subject to change without notice):

Monday, Feb. 02: Intro. Introduction

Wednesday, Feb. 04: Lecture 01 Linked List, Stack

Monday, Feb. 09: Lecture 02 Graphs: Introduction and terminology

Wednesday, Feb. 11: Lecture 03 Graphs: traversal; Depth first and Breadth First

Monday, Feb. 16: Lecture 04 Graphs: Spanning Trees

Wednesday, Feb. 18: Lecture 05 Graphs: Minimum Spanning Trees; Prim's algorithm

Friday, Feb. 22: Project 01 Project #1 due. Topic: ACM contest example fairplay.

Monday, Feb. 23: Lecture 06 Graphs: Shortest Path; Dijkstra's algorithm

Wednesday, Feb. 25: Lecture 07 Graphs: Examples and algorithm traces

Monday, Mar. 01: Lecture 08 File structures: External storage topology

Wednesday, Mar. 03: Lecture 09 External Sorting: Mergesort using external storage

Monday, Mar. 08: Lecture 10 Balanced Binary Search Trees; Introduction

Wednesday, Mar. 10: Exam Midterm Exam #1

Friday, Mar. 12: Project 02 Project #2 due. Topic: Dynamic Shortest Path ACM Problem.

Monday, Mar. 15: Postmortem Midterm Exam #1 Postmortem

Wednesday, Mar. 17: Lecture 11 BST Rotations

Monday, Mar. 22: Lecture 12 AVL Trees: Insertion and Deletion

Wednesday, Mar. 24: Lecture 13 AVL Trees: Code and examples

Monday, Mar. 29: Lecture 14 Red Black Trees: Introduction

Wednesday, Mar. 31: Holiday Cesar Chavez Day

Friday, Apr. 02: Project 03 Project #3 Due. Topic : SBS Tree analysis.

Monday, Apr. 05: Holiday Spring Recess

Wednesday, Apr. 07: Holiday Spring Recess

Monday, Apr. 12: Lecture 15 Red Black Tree Insertion

Wednesday, Apr. 14: Lecture 16 Red Black Tree Deletion

Monday, Apr. 19: Lecture 17 Red Black Trees code and examples

Wednesday, Apr. 21: Exam Midterm Exam #2

Monday, Apr. 26: Postmortem Exam #2 Postmortem

Wednesday, Apr. 28: Lecture 18 ER-modeling

Friday, Apr. 30: Project 04 Project #4 Due. Topic : Red Black Trees.

Monday, May. 03: Lecture 19 Introduction to SQL

Wednesday, May. 05: Lecture 20 Normalizing

Monday, May. 10: Lecture 21 Database Design

Wednesday, May. 12: Lecture 22 JDBC

Monday, May. 17: Lecture 23 UML/XML

Wednesday, May. 19: Review Review for Final

Friday, May. 21: Project 05 Project #5 Due. Topic : Database Design

Monday, May. 24: Exam Final Exam