CS 310: Data Structures

George Mason University
Fall 2013
3 Credits

1 Basic Course Information

Prerequisites
C or better in CS 211.
Course Meeting Time and Location
SectionDaysTimeProfessorLocation
002M/W12:00-1:15KauffmanNguyen Engineering Building 1103
003M/W3:00-4:15KauffmanRobinson Hall A111
Instructors
NameChris Kauffman
Sections002, 003
Office HoursT/R 3-4pm
OfficeEngineering 5341
Emailkauffman@cs.gmu.edu
Phone703-993-5194
Teaching Assistants
NameEmailOffice HoursRoom
Anudeep Madamshettyamadamsh@gmu.eduT 1-3pmEngineering 4456
Jianchao Tanjtan8@gmu.eduW 2-4pmEngineering 4456
Chaoran Luclu3@gmu.eduW 1-2pmEngineering 5321
Text
Mark Allen Weiss, Data Structures & Problem Solving Using Java, 4th ed., Addison-Wesley, 2010. A copy of the text is on 2-hour reserve in the Johnson Center Library.
Web Sites
Piazza
The central site course site. CS 310 shares a Piazza site amongst all 3 sections (001-Carver, 002-Kauffman, 003-Kauffman). The announcements, discussion board, and documents posted there are part of the required reading for the course.
  • All instructors and TAs can view all material on Piazza
  • Use public posts on Piazza to discuss programming assignments, HW, and other material related to the course.
  • Use private messages on Piazza for personal questions involving your own code or situation.
  • Refer to the Piazza main page for etiquette on what should be posted publicly versus privately
BlackBoard
Used for assignment submission and to disseminate grades on assignment. Each section submits to their own Blackboard section site.
Office Hours
Listed for all Instructors and TAs on Piazza (Course Page –> Staff).

2 Course Description

2.1 Goals

CS 310 continues the study of data structures from CS 211. Students will learn how to approach larger and more challenging programming problems than the projects in CS 211. Programming is a significant part of this course and students should expect to spend a good deal of time on the programming projects. The course also introduces a variety of data structures and illustrates the types of problems for which they are useful.

Topics to be covered include.

  • Generics and Collections
  • Basic Complexity Analysis
  • Linked Lists
  • Stacks and Queues
  • Simple and Balanced Binary Search Trees
  • B-Trees and File Organization
  • Hash Tables
  • Priority Queues
  • Splay Trees

2.2 Learning Outcomes

By the end of the semester, a passing student will be able to carry out the following types of activities:

  • Reinforce what they have learned about elementary data structures from CS 211
  • Extend their knowledge of data structures to more sophisticated data structures. This includes balanced binary search trees, B-trees and B+-trees, hashing, and basic graphs.
  • Use generic types in their data structures.
  • Do more demanding programming than they had in CS 211. All programming is done in Java. This involves more program design and debugging techniques.

3 Coursework

3.1 Lectures

During lectures we will discuss programming concepts and instructors will provide demos of programming relevant to assignments. In addition to attending the regular meeting times, you are strongly encouraged to visit the professor and teaching assistant(s) during office hours to further your understanding of the material: we are here to help you learn.

3.2 Reading

Readings from the textbook relevant to each lecture are listed in the schedule. You will increase your understanding of lectures by reading associated textbook sections ahead of time, though this is not assumed. Additional reading material may be provided to supplement the textbook which will be posted on the course web page.

3.3 Programming Assignments

Students will receive a number of programming assignments during the semester. Each assignment will involve writing programs and answering questions about them to illustrate an understanding of course material. The programming assignments will be electronically submitted to Blackboard on dates specified in the assignment by 11:59 p.m. Students may submit assignments as many times as needed up to the deadline.

3.4 Exams

There will be one midterm exam during the course during the regularly scheduled lecture time. There will also be a comprehensive final exam at the end semester. Refer to the schedule for dates of the exams.

4 Grading Policy

4.1 Components

Final grades will be determined by scores obtained on homework assignments, quizzes, projects, the two midterm exams, and final exams. If circumstances require it, the grading scale may be adjusted, generally in the students' favor.

ComponentWeight
Programming Assignments35%
Midterm Exam30%
Final Exam35%

4.2 Final Grade Determination

Final grades will be assigned without rounding according to the following criteria. It is a 10-point scale per letter grade, with the upper and lower 2% of each 10% earning a + or -.

PercentGradePercentGradePercentGradePercentGrade
>= 98A+90-88B+80-78C+70-60D
98-92A88-82B78-72C<60F
92-90A-82-80B-72-70C-

4.3 Grading Disputes

Address grading issues with the grader (usually a graduate TA) first. This should be done respectfully either in person or via e-mail. If it is not possible to reach a resolution, the professor may be contacted by the grader to resolve the dispute.

If you have not initiated contact within 1 week after receiving a grade, the chance to contest the grade has closed.

4.4 Homework

Homework is due via electronic submission by 11:59 p.m. on the dates specified. You can submit work to BlackBoard as many times as desired. Only the last submission will be graded.

It is at the sole discretion of the instructor whether to accept late homework assignments. Health or family emergencies are usually legitimate reasons for lateness but forgetfulness and procrastination are not. Notify the instructor via e-mail (preferred) or phone if you know you will miss a HW. In the case of an emergency, notify the instructor as soon as possible. Reductions in credit may be given in any case for late homework at the discretion of the instructor. Typically this will be on the order of 10% reduction in credit per day late.

On-time submissions will generally be graded and available a week from submission. Late submissions will be graded in as timely a fashion as schedules allow.

4.5 Exams

Missing an exam results in a zero score and make-up exams will be considered only in situations involving death and near death.

Students are required to take the final exam though performance on it impacts the overall grade only according to the weight table. The same criteria for missing exams will be applied for a making up a missed final. The final exam will consist of a comprehensive set of questions covering all material covered in the course. Problems will be similar to those encountered on homework and exams.

A valid mason ID is required when taking exams to verify student identity.

Final exams are scheduled for the below dates.

SectionProfessorLecture Day/TimeFinal Exam Day/Time
002KauffmanM/W 12:00-1:15M 12/16 10:30am-1:15pm
003KauffmanM/W 3:00-4:15M 12/16 1:30pm-4:15pm

5 Academic Integrity

PRIME DIRECTIVE: Be able to explain your own work including homework code and exam solutions.

Nearly all cheating in programming can be averted by adhering to the PRIME DIRECTIVE. Students may be asked at any time to explain code or exam solutions they submit. Inability to do so will be construed as evidence of misconduct. More specific guidelines are given below.

5.1 Thou Shalt Not

For the purposes of this course, the following actions constitute scholastic misconduct (cheating):

  • Directly copying someone else's solution to a homework problem, including student solutions from a previous semester
  • Directly copying an answer from some outside source such as the Internet or friend for a homework problem
  • Making use of an Instructor Solution manual to complete homework problems
  • Paying someone for a homework solution
  • Posting solutions to our discussion board or any other web site
  • Collaborating or copying someone else's answer during an exam
  • Aiding or abetting any of the above
  • Witnessing any of the above and failing to report it the instructor immediately

Refer to the following links for additional information.

5.2 Penalties

Any instance of misconduct that is detected will be referred to the honor board and will likely result in failing the course. Be advised that the teaching team will be employing electronic means to detect plagiarism. This is extremely easy with computer code so keep your nose clean.

5.3 Fair Collaboration

The purpose of this course is to learn about programming and learning from one another is a great help. To that end, the following actions will NOT be considered cheating in this course.

  • Talking to other students in the course about HW problems and informally describing how a problem may be solved.
    • Be very careful as you do this that you do not share any sort of code as this will be detected and referred to the honor committee.
  • Getting or giving help fixing a small bug or two: a second set of eyes is a great boon to finding that misplaced semicolon that is preventing your code from compiling.
  • Searching the Internet for alternative presentations of a programming concept.
  • When unsure whether collaboration is fair or not, stop the activity until it can be cleared with instructor.

At all times keep the PRIME DIRECTIVE in mind when studying with another student. The above collaborations should be limited to getting someone over a hurdle, not carrying them across the finish line.

A significant portion of your grade will depend on programming assignments. Doing them individually prepares you for the exams in which no collaboration of any kind is allowed.

6 Additional Policies

6.1 Programming Assignments

Since this is a programming course, some special policies will be in effect.

  • Programming assignments will be submitted to Blackboard at the specified dates. You may submit assignments to Blackboard as many times as you like: only the most recent submission will be graded (up to the deadline).
  • Back up your program regularly. This is usually as simple as making a copy of the assignment folder. Submitting occasional early versions to Blackboard is also extremely helpful. Should last-minute problems happen such as accidental deletion, you will at least have some of your work to show. No code to submit means no credit.
  • Submitted code that does not compile will receive little to no credit.
  • When test cases are provided by the instructor use them and make sure your code passes all tests.
  • Familiarize yourself with how plagiarism works with programming as described in other parts of the syllabus.
  • Keep an untouched copy of your final code submission. It is important that you not touch your programs once you have made your final submission. If there are any submission problems, consideration for credit will only be given if it can be verified that the programs were not changed after being submitted.
  • You may develop programs using any computer system available. However, submitted assignments must run under the Java environment available on either Zeus or Mason. No extensions will be given due to compiler/runtime incompatibilities.

6.2 Behavior and Accommodations

Students are expected to maintain a high level of civility for all participants in and out of class meetings. This includes respecting the beliefs of participants of all genders, ethnicities, and social backgrounds. Harassment of any type will not be tolerated and failure to behave in a respectful manner will result in referrals to University Counseling or the Office of Student Judicial Affairs. Any instances of sexual harassment will be reported to the Office of Equal Opportunity according the following policy: http://universitypolicy.gmu.edu/1202gen.html

Observance of religious events will be accommodated for students of any faith.

All possible accommodations will be made for students with disabilities. Please contact Disability Services (http://ods.gmu.edu/) and the instructor for further information.

6.3 Additional Policies for Prof. Kauffman's Sections

Bonus credit will be awarded based on participation in class discussions in lecture. Before each lecture, I will announce a range of the alphabet. Students with last names in that range may elect to sit in the first 3 rows of the room and answer questions (hot seats). Reasonable effort on answering questions in class will garner class participation credit. Participation points may also be earned for involvement in the class discussion board such as giving suggestions to students with questions (but not revealing answers wholesale). Effort during lab sections generates one participation credit.

The highest participation point winner at the end of the semester will receive a 3% bonus to their overall score in the course. All other students will receive a bonus proportional to the highest point winner. For example, someone tied with the highest point scorer will also receive a 3% bonus while someone with half the participation points will receive a 1.5% bonus.

7 Guidelines for Success

  • Most homework problems have analogs that are (1) discussed in lecture or (2) described in an example problem in the textbook. This should encourage you to
    • Attend lecture and take notes
    • Read the content of each section of the textbook carefully
    • Analyze the example code distributed by the instructor

    Most successful students do all of these.

  • Seek help from the instructor or teaching assistant when a concept is unclear. If you blow a problem on a HW or exam and don't see why, attend office hours to ask about it. We are here to aid your learning process.
  • Form good habits early on. We have a large amount of material to cover which means you will need to spend time outside of lecture reading and experimenting. Things will move fast so don't fall behind.
  • There is a wealth of information on data structures online. Don't be afraid to consult online tutorials if a particular topic is troublesome for you. However, do not misuse to the Internet to obtain solutions that you don't understand. Follow the PRIME DIRECTIVE at all times.

8 Schedule of Events

This is an approximate schedule that may be adjusted as we go forward. Check Piazza for the most up-to-date version.

WeekDateTopic/DeliverableReadings
108/26-08/30Syllabus, Review, GenericsCh 1-4
Basic Complexity AnalysisCh 5
09/02Labor day no class
209/03-09/06Cache and Architecture Concerns
Inner Classes, Array ListsCh 15
309/09-09/13StacksCh 16
Queues
HW 1 Due - Generics
409/16-09/20General Linked ListsCh 17
Doubly Linked Lists
509/23-09/27RecursionCh 7
TreesCh 18
HW 2 Due - Lists
609/30-09/34Binary TreesCh 19.1-3
710/07-10/11Balanced Binary TreesCh 19.4-7
10/14Columbus day
Monday classes meet Tuesday
Tuesday classes do not meet
810/15-10/18Balanced Binary TreesCh 19.4-7
Huffman Coding11.2
HW 3 Due - Trees
910/22-10/26B-Trees, File Organization19.8
Midterm Exam
1010/28-11/01Hash FunctionsCh 20.1-2
Hash Tables
1111/04-11/08Hashing StrategiesCh 20.3-7
1211/11-11/15Binary Heaps and Priority QueuesCh 21
HW 4 Due - Hashing
1311/18-11/22Splay TreesCh 22
1411/25-11/26Garbage Collection
11/27-29Thanksgiving Break
No Classes
Final Week of Classes
1512/02-12/06Disjoint SetsCh 24
Review
12/10-12/19Exam Period
12/12Section 001 Final 10:30am-1:15pm
12/16Section 002 Final 10:30am-1:15pm
12/16Section 003 Final 1:30pm-4:30pm

Date: 2013-08-28 11:11:23 EDT

Author: Chris Kauffman and Richard Carver

Org version 7.8.02 with Emacs version 24

Validate XHTML 1.0