CPSC2108 - Data Structures

 

Instructor(s): Dr. Wayne Summers
Office: CCT 455                                                          Office phone: (706) 568-5037
Department phone: (706) 568-2410                             Department FAX: (706) 565-3529
Office Hours: MWF 10:00a.m. - noon, TR 11-noon,  2:00-3:00p.m.; via e-mail, WebCT discussions and by appointment
e-mail address: summers_wayne@ColumbusState.edu
homepage: http://csc.ColumbusState.edu/summers

Class Meets: TR 9:30-10:45 a.m. in Center for Commerce and Technology 408

CATALOG DESCRIPTION OF COURSE

Prerequisite: CPSC 1302 with a C or better. This course extends the concepts of primitive data types by teaching the student a set of data structures that pervades both the theoretical and practical domains of computer science. (3 credits).

ACADEMIC OBJECTIVES

·         Students will learn to understand the principles of efficiency of algorithms

o  Strategies and Actions used to produce the outcome:

§  Introduction to the Big-O Analysis

o  ABET Criteria covered: B, C, D, and I.

o  Program Objectives covered: 2 and 3.

o  Assessment Methods: Programming Assignments, Quizzes, Midterm Test and Final Exam.

·         Students will learn to understand how to specify, design and implement Abstract Data Types

o  Strategies and Actions used to produce the outcome:

§  Study of the definition of Abstract Data Types

§  Study of the implementation of ADTs in Java

o  ABET Criteria covered: B, C, D, and I.

o  Program Objectives covered: 2 and 3.

o  Assessment Methods: Programming Assignments, Quizzes, Midterm Test and Final Exam.

·         Students will learn to be able to implement and use data structures such as Lists, Stacks and Queues Data Structures.

o  Strategies and Actions used to produce the outcome:

§  Study of specification of Lists, Stacks and Queues among others

§  Study of the implementation of Lists, Stacks, and Queues in Java among others

o  ABET Criteria covered: B, C, D, and I.

o  Program Objectives covered: 2 and 3.

o  Assessment Methods: Programming Assignments, Quizzes, Midterm Test and Final Exam.

·         Students will learn about and learn to use the concept of Recursion.

o  Strategies and Actions used to produce the outcome:

§  Study of Recursion

§  Study of the uses of Recursion

o  ABET Criteria covered: B, C, and D.

o  Program Objectives covered: 2 and 3.

o  Assessment Methods: Programming Assignments, Quizzes, Midterm Test and Final Exam.

·         Students will learn to implement and use Binary Search Trees.

o  Strategies and Actions used to produce the outcome:

§  Study of the concept of Binary Search Trees

§  Study of the implementation and use of Binary Search Trees

o  ABET Criteria covered: B, C, and D.

o  Program Objectives covered: 2 and 3.

o  Assessment Methods: Programming Assignments, Quizzes, Midterm Test and Final Exam.

·         Students will learn to implement and use Priority Queues, Heaps, and Graphs.

o  Strategies and Actions used to produce the outcome:

§  Study of the concept of Priority Queues, Heaps, and Graphs

§  Study of the implementation and use of Priority Queues, Heaps, and Graphs

o  ABET Criteria covered: B, C, and D.

o  Program Objectives covered: 2 and 3.

o  Assessment Methods: Programming Assignments, Quizzes, Midterm Test and Final Exam.

·         Students will learn to implement and use Sorting and Searching Algorithms.

o  Strategies and Actions used to produce the outcome:

§  Study of the concept of Sorting and Searching Algorithms

§  Study of the use of Sorting and Searching Algorithms

o  ABET Criteria covered: B, C, and D.

o  Program Objectives covered: 2 and 3.

o  Assessment Methods: Quizzes, Midterm Test and Final Exam.

MAJOR TOPICS

·         Big-O Analysis.

·         Abstract Data Types.

·         Stacks.

·         Recursion.

·         Queues.

·         Lists.

·         Binary Search Trees.

·         Priority Queue, Heaps, and Graphs.

·         Sorting and Searching Algorithms.

 

TEXTBOOKS

Required Text

Authors Nell Dale, Daniel T. Joyce, and Chip Weems Title Object-Oriented Data Structures Using Java, Second Edition Publisher Jones & Bartlett Pub Year 2006 ISBN 0-763-73746-1

 

Supplementary Books and Materials

• WebCT materials
• Class handouts & notes
• Software and manuals found in the computer labs and on the Internet

Assignments for Course

• Readings from the textbooks
• Online materials available through WebCT
• Outside reading from popular computing periodicals is expected to enhance your knowledge of Computer Science
• Readings from documents found on the Internet
• Programming and non-programming assignments

Assessment Criteria

• Assignments (360 pts.) [lowest one will be dropped] – due before class starts

• For each assignment, students will be expected to analyze requirements of the problem, develop UML class diagrams, design the algorithm and implement the algorithm by coding it into a Java program. Assignments will focus on one or more of the learning objectives. Assignments are due at the beginning of the class period of the due date. Assignments turned in after those times are considered late and will be penalized 25% for each day they are late. Programs should be submitted through the WebCT dropbox.  Include your program source code and ancillary files as an attachment.

• Chapter Quizzes (180 pts.) [lowest of ten quizzes will be dropped]
• One midterm test (100 pts.)
• One comprehensive FINAL EXAM (200 pts)

• Quizzes and exams will assess whether students have an understanding of data structures and how they work. Students will be expected to analyze the requirements of a problem, design the algorithm and code the solution in Java on the exam.  Midterm and final exams test material from the lectures, readings and programming exercises. The exams may include multiple choice, fill in the blanks, short answer questions and programming questions (you will be asked to write code). All exams are closed book, closed notes, no calculators. If you miss any quiz or exam or are absent for that class, it will not be made up.

• CLASS PARTICIPATION – will be considered for students who are on the borderline between two grades

 A (90-100): The student fulfills or exceeds all of the assigned content requirements. The student’s knowledge of the subject is accurate throughout. The student exhibits convincing range and quality of knowledge, having done appropriate research, if applicable.

B (80-89): The student fulfills all of the important assigned content requirements. The student’s knowledge of the subject is accurate throughout except in minor details. The student seems informed on the subject, having done appropriate research, if applicable

C (70-79): The student fulfills most of the important assigned content requirements. The student’s knowledge of the subject is generally accurate, though flawed. The student exhibits limited range or quality of knowledge, having done limited appropriate research, if applicable.

D (60-69): The student fulfills some of the important assigned content requirements. The student’s knowledge of the subject is generally accurate, though flawed. The student exhibits limited range or quality of knowledge, having done minimal appropriate research, if applicable.

F (0-59): The student fails to address the important requirements of the course.
The student’s knowledge of the subject is generally inaccurate. The student’s knowledge of the subject lacks range or quality

Class Attendance: Class attendance is the responsibility of the student, and it is the student's responsibility to independently cover any materials missed. Class attendance and participation may also be used in determining grades. It is your responsibility to sign a roll sheet for every class meeting. At my discretion, I may drop you from the course for more than six (6) absences. Missing an exam or quiz is considered an absence. Missed classes caused by participation in documented, formal, University-sponsored events will not count as absences provided you notify me of such anticipated absences in advance and as soon as possible.

You are responsible for all class work missed, regardless of the reason for the absence(s). Late assignments will not be accepted, so if you are absent on the day an assignment is due, it is your responsibility to make alternate arrangements. No makeup exams or quizzes will be given, so please make sure you are present for all exams/quizzes. Refer to the CSU Catalog (http://aa.ColumbusState.edu/advising/a.asp#AbsencePolicy) for more information on class attendance and withdrawal.  

Academic dishonesty Academic dishonesty includes, but is not limited to, activities such as cheating and plagiarism. It is a basis for disciplinary action. Collaboration is not permitted on assignments or exams/quizzes in this course. Any work turned in for individual credit must be entirely the work of the student submitting the work. All work must be your own. You may share ideas but submitting identical assignments (for example) will be considered cheating. You may discuss the material in the course and help one another with debugging, however, I expect any work you hand in for a grade to be your own. . A simple way to avoid inadvertent plagiarism is to talk about the assignments, but don't read each other's work or write solutions together. Keep scratch paper and old versions of assignments until after the assignment has been graded and returned to you. If you have any questions about this, please see me immediately. For assignments, access to notes, textbook, books and other publications is allowed. Stealing, giving or receiving any code, diagrams, drawings, text or designs from another person (CSU or non-CSU) is not allowed. Having access to another person’s work on the system or giving access to your work to another person is not allowed. It is your responsibility to keep your work confidential. No cheating in any form will be tolerated. The penalty for the first occurrence of academic dishonesty is a zero grade on the assignment or exam/quiz; the penalty for the second occurrence is a failing grade for the course. For exams/quizzes, access to any type of written material or discussion of any kind (except with me) is not allowed. (http://aa.ColumbusState.edu/advising/a.asp#Academic Dishonesty/Academic Misconduct) Getting help Student assistants in the Computer Center can help you with basic computer-related problems such as logging on to the network, saving your work, etc., but they are not obligated to help you with your assignments. There are several tutors at the Department of Computer Science who can help you with the assignments. Their schedule is posted in the Computer Science department. You can always contact me during my posted office hours, by e-mail, or by appointment.

Software
To complete all lessons, assignments, labs, and tests, you will need to access a computer with:

• Windows XP/Vista, Linux, or Macintosh, Firefox or Internet Explorer, and PowerPoint
• Java 2 Platform, Standard Edition (J2SE)
• Java IDE (DrJava/BlueJ/Crimson Editor/Borland JBuilder/Eclipse)
• Java Source Code and Program Files from the textbook materials

The class material will be available via WebCT Vista at http://colstate.view.usg.edu/. This Web Site will contain class notes, class announcements, exam summaries, the course syllabus, test dates, and additional links. 

Course Material Downloads

To download Java SDK: http://java.sun.com/

To download Dr. Java: http://www.drjava.org/
To download Crimson Editor: http://crimsoneditor.com
To download Blue J: http://www.bluej.org/download/download.html
To download Text Pad: http://www.textpad.com/download/index.html
To download Eclipse: http://www.eclipse.org/downloads/
To download Netbeans: http://netbeans.org/

 Instructional Methods and Techniques

1. The class will meet for two one-hour and fifteen minute lecture / discussion periods each week.
2. Each student is expected to attend all class lectures, to read the textbook chapters and to make notes. Students will be expected to participate in classroom discussions, both in class and online.
3. Students must have access to computers for doing assignments.
4. The ACM recommends the following: “As a general guideline, the amount of out-of-class work is approximately three times the in-class time. Thus, a unit that is listed as requiring 3 hours typically entails a total of 12 hours (3 in class and 9 outside).” Students will be expected to spend this time outside class reading the book, online materials and other materials; writing solutions to homework exercises and programming projects.

How to Access the Course

This course includes WebCT Vista. You can access WebCT Vista at: https://colstate.view.usg.edu 

At this page, select the "Log on to" WebCT Vista link to activate the WebCT Vista logon dialog box, which will ask for your WebCT Vista username and password. Your Vista WebCT username and password are:

Username: lastname_firstname
Password: XXXX

Default password is your birthday in the format of DDMMYY.

If you try the above and WebCT Vista will not let you in, please use the "Comments/Problems" link on the WebCT Vista home page to request help. If you are still having problems gaining access a day or so after the class begins, please e-mail me immediately.

Once you've entered WebCT Vista, you will see a list of courses you have access to. The CPSC 108 course is listed as "Data Structures". Next to this, you should see my name as the instructor. You may also see new discussion postings, new calendar postings, and new mail messages. Clicking on the name of the course will take you to the course's home page. If you do not see the "Data Structures" course in the list, please e-mail me immediately.

Once you have clicked on the course's name and accessed the particular course itself, you will find a home page with links to other sections and tools, and a menu on the left-hand side. Feel free to explore the areas in the course.

Website
It is your responsibility to frequently look at the course website to keep your knowledge of class activities current. For this course, the website is at http://csc.ColumbusState.edu/summers. I may occasionally forget to announce details in class, but they may have been already posted on the site and/or in WebCT. If so, you will still be held responsible for them. For example, assignment due dates, corrections of errors, announcements, exam dates, changes to policies, and so on. 

 Discussion Etiquette

CSU is committed to open, frank, and insightful dialogue in all of its courses. Diversity has many manifestations, including diversity of thought, opinion, and values. Students are encouraged to be respectful of that diversity and to refrain from inappropriate commentary. Should such inappropriate comments occur, I will intervene as I monitor the dialogue in the discussions. I will request that inappropriate content be removed from the discussion and will recommend university disciplinary action if deemed appropriate. Students as well as faculty should be guided by common sense and basic etiquette. The following are good guidelines to follow:

• Never post, transmit, promote, or distribute content that is known to be illegal.
• Never post harassing, threatening, or embarrassing comments.
• If you disagree with someone, respond to the subject, not the person.

Never post content that is harmful, abusive; racially, ethnically, or religiously offensive; vulgar; sexually explicit; or otherwise potentially offensive.

 Student Responsibilities

As a student in this course, you are responsible to:

• manage your time and maintain the discipline required to meet the course requirements,
• come to class prepared to ask questions to maximize your understanding of the material,
• complete all readings,
• complete all assignments,
• complete all quizzes and exams,
• actively participate in discussions,
• submit the “one-minute paper” after each class, and
• read any e-mail sent by the instructor and respond accordingly.

“I didn’t know” is NOT an acceptable excuse for failing to meet the course requirements. If you fail to meet your responsibilities, you do so at your own risk.

Instructor Responsibilities

As your instructor in this course, I am responsible to:

• lead the class discussion and answer students’ questions,
• post weekly lessons outlining the assignments for the week,
• read all responses to discussion questions and comments to responses,
• actively participate in discussions when necessary,
• respond to students questions and concerns expressed in the “one-minute paper”, 
• grade assignments, quizzes, and exams, and post scores within one week of the end of the week in which they are submitted, and
• read any e-mail sent by the you and respond accordingly within 48 hours.

Although I will read every posted discussion question and response, I will not necessarily respond to every post.