CS 2005 D Term 2004
Data Structures and Programming Techniques

---

What this course is about

The goal of CS 2005 is to provide the student with an introduction to Abstract Data Types (ADTs). The emphasis is on the specification, design, implementation, and use of data types. The foundations of Object-Oriented Programming are covered; projects are completed using the programming language C++. Recommended background and course topics are listed in the WPI undergraduate catalog course description

Course Objectives

• Understand and be able to implement the following abstract data types: sets, multisets, sequential lists, ordered lists, stacks, queues, tables, and trees
• Analyze each ADT implementation for efficiency (using big-O analysis)
• Develop and test reasonably large programs in C++ that use ADTs
• Write recursive functions and reason about recursion
• Understand various quadratic and O(n log n) sorting algorithms and be able to demonstrate the effect of these algorithms on specific data
• Analyze each of the sorting algorithms studied using big-O analysis
• Understand sequential search, binary search, and open and closed hashing
• Analyze sequential and binary search using big-O analysis and be able to explain the big-O results obtained for open and closed hashing
• Gain further experience with the Unix operating system and its tools

---

Staff

Instructor: Glynis Hamel

Teaching Assistants: Matt Jarvis, Wei (Debbie) Peng, Fan Wu

Senior Assistants: Seth Hunter, Kevin Menard, Kevin Monahan, Russell Souza

Office Hour Schedule

(Note: TA/SA office hours are held in FL A22 (Fuller basement). Glynis Hamel's office hours are held in FL 132.)




Day/Time	11:00	12:00	1:00	2:00	3:00	4:00	5:00	6:00	7:00	8:00	9:00
Monday	Wei	Wei	Fan	Mrs. Hamel	Mrs. Hamel		K. Monahan	K. Monahan	Russ	Russ	K. Menard
Tuesday	Seth		Matt
Wednesday	Wei		Matt	Matt				Fan	Fan
Thursday	Seth		Mrs. Hamel	K. Menard				Russ		K. Monahan	K. Menard
Friday	Seth




Class Discussion Board and Email

A discussion board for CS 2005 has been set up on myWPI . All students enrolled in the course have access to this discussion board. You may post questions about the course, and see the answers to questions posed by other students in the course. You should visit the discussion board on a daily basis.

If you have a question regarding your grades in the course, please send email to cs2005-staff *at* cs.wpi.edu. Mail sent to this address goes to the instructor and to the TAs. Include your section number in all correspondence.

The instructor's email address is ghamel *at* cs.wpi.edu. Please restrict your use of my personal email address to issues of a confidential nature. You will get a quicker response if you post your questions to the class discussion board.

"Coffee with Mrs. Hamel"

I will have my morning cup of coffee in the Campus Center Lounge every Friday morning during D-term from 8am - 9am. Please join me! We can use this time
• as an informal office hour, or
• to discuss any general concerns or suggestions you have for the course, or
• as a time to relax at the end of the week
I hope to see you there.

---

Lecture and Lab Times

Lectures (MTThF) and Labs (Wed) meet according to the following schedule:

Section	Lecture Time	Lecture Location	Lab Time	Lab Location
D01	9:00	AK116	8-8:50	AK 120d
D02	9:00	AK 116	9-9:50	AK 120d
D03	9:00	AK 116	10:00-10:50	AK 120d
D04	9:00	AK 116	12:00-12:50	AK 120d
D05	10:00	SL 104	1:00-1:50	AK 120d
D06	10:00	SL 104	11:00-11:50	AK 120d
D07	10:00	SL 104	2:00-2:50	AK 120d
D08	10:00	SL 104	3:00-3:50	AK 120d

---

Textbook and Authors' Website

Textbook (required): Main, Michael, and Walter Savitch, "Data Structures and Other Objects Using C++", 2nd edition, Addison-Wesley, 2001 (ISBN 0-201-70297-5)

A website for the text is available here .

Powerpoint slides for most of the chapters in the book are available here.

Source code for all classes defined in the text is available here . We will refer to the source code often during lectures.

The author maintains a list of sample test questions, some of which will be used on the exams for this course.

---

Grading

Exams (60%)

Three exams will be given. Exams are tentatively scheduled for April 1, April 16, and May 4. You must have a passing average on the exams in order to pass the course. (A passing average on the exams is usually around 65%. We may lower this threshold if the exam averages are low; the threshold will not be raised).

Exams are closed-book, closed-notes. You may bring in one sheet of notes (one paper, 8.5" x 11.5", both sides) to each exam. You may not use any computers, calculators, cellphones, or other electronic devices during the exams.

There are no makeups for exams. Please note that you are expected to take all three exams - no exam grades will be dropped. Absence from an exam will be excused only for medical or emergency reasons. A note from your doctor or from the Office of Academic Advising will be required. In such cases your final grade will be calculated without taking the missed exam into account.

Homework (32%)

Four homework assignments will be given. Assignments will be due at 11:59pm on the due date. No extra credit or makeup assignments will be given.

Labs and In-class Group Work (8%)

Labs will be given during conference sections on Wednesdays. To get credit for a lab you must attend at your scheduled time, actively work on the assignment during the lab period, and use turnin to turn in your work at the end of the lab period. Each lab will be graded as either credit (1) or no credit (0). You will not get credit for a lab unless you attend the section for which you are registered. There are no makeups for labs.

Several times during the term we will take a few minutes of class time for in-class group work. This will consist of one or two questions related to recently-covered lecture material or homework problems. Each group assignment will be graded as either credit (1) or no credit (0). There are no makeups for group assignments.

The total of your best 8 lab grades/group assignment grades will be added to your final average to account for 8% of your final grade.

---

Academic Honesty Policy

Please read WPI's Academic Honesty Policy.

Labs and In-class group work

Collaboration is encouraged for in-class group work, and for lab assignments that are not directly related to homework.

Exams and Homework

Exams and homework are to be done individually. You are encouraged to talk with others in a general way about homework assignments (what approach to take, for example), but any work you submit for grading must be your own. Some examples of situations that would be considered academically dishonest are
• two or more students write the solution or part of the solution to a homework assignment together
• all or part of a solution to a homework assignment is copied from another student (with or without that other student's consent)
• all or part of a solution to a homework assignment is copied from a book, journal, or website
• providing all or part of a solution to a homework assignment to another student

If you receive help from another student or an outside source, that student or source must be acknowledged in the documentation accompanying your submitted work.

Cheating will not be tolerated. If you are unsure whether a given activity would constitute cheating, ask the instructor. Violations of the Academic Honesty Policy can result in an NR for the course, and violators will be subject to the procedures outlined in section 5 of the WPI Judicial Policy.

Late Policy

Late homework will be accepted within 24 hours of the due date; late homework will incur a 25 point (out of 100 points) penalty. Any homework turned in after the 24-hour grace period will receive a grade of zero. No extra credit or makeup homework assignments will be given.

Homework Submission Policy

Homework must be submitted using the Unix turnin program. Homework submitted by any other means (paper, CD, email, etc.) will receive a grade of zero.

You are encouraged to do your program development on a Unix platform. If you choose to do your development on a non-Unix platform, it is your responsibility to transfer files to the WPI Unix machine and to ensure that your programs compile with the GNU Project C++ Compiler (g++), and run on the Unix system.

Students with Disabilities

Students with disabilities who believe that they may need accomodations in this class are encouraged to contact the Disability Services Office (DSO) as soon as possible to ensure that such accomodations are implemented in a timely fashion. The DSO is located in Daniels Hall.

---

Schedule

Note: the instructor reserves the right to change the order of topics or the dates of the exams, if necessary.

Week	Reading	Topics	Assignments
Mar 16 - 19	Chapter 1 Chapter 2 Section 13.1 Powerpoint 1, 2, 13 Lecture 1 objectives Lecture 2 objectives Lecture 3 objectives	Course overview O(n^^2) sorts Introduction to classes	Pre-Lab for Lab 0 Lab 0 (optional), Wed 3/17 Homework 1
Mar 22 - 26	Chapter 3 (skip 3.2) Sections 4.1 - 4.4 Lecture 4 objectives Lecture 5 objectives Lecture 6 objectives Lecture 7 objectives	Bag ADT Friend functions Pointers	Lab 1, Wed 3/24 HW1 Part 1 due Thursday, 3/25
Mar 29 - Apr 2	Chapter 5 (skip 5.4) My " pointer" handout from CS 1005 Lecture 8 objectives Lecture 9 objectives Lecture 10 - Exam date Lecture 11 objectives	Copy constructor Assignment operator Linked lists	HW1 Part 2 due Monday, 3/29 Homework 2 Lab 2, Wed 3/31 Exam 1 Thursday, April 1 Solutions for Exam 1
Apr 5 - 9	Chapter 5 (cont.) Sections 6.1, 6.2 Powerpoint 6, 7 Chapter 7 Sections 8.1 - 8.3 Lecture 12 objectives Lecture 13 objectives Lecture 14 objectives Lecture 15 objectives	Linked lists (cont) Template functions Template classes Stacks Queues	HW2 Part 1 due Monday, 4/5 HW2 Part 2 due Thursday, 4/8 Homework 3 Lab 3, Wed 4/7
Apr 12 - 16	Chapter 9 Lecture 16 objectives Lecture 17 objectives palindrome algorithm Lecture 18 objectives Lecture 19 - Exam date	Recursion	Lab 4, Wed 4/14 Exam 2, Friday, April 16 Answers to Exam 2
Apr 19 - 23	Section 13.2 Powerpoint 9 Chapter 10 Powerpoint 10 Lecture 20 objectives Lecture 21 objectives Non-recursive inorder traversal algorithm Lecture 22 objectives	O(nlogn) sorts Binary trees Binary search trees	HW3 due Monday, 4/19 (No lab this week) Homework 4
Apr 26 - 30	Sections 11.1, 11.3 Powerpoint 11 Section 8.4 Section 13.3 Lecture 23 objectives Lecture 24 objectives Lecture 25 objectives Lecture 26 objectives	Binary search trees (cont) Heaps Priority queues Heapsort Searching	Lab 5, Wed 4/28
May 3 - 4	Chapter 12 Lecture 27 objectives Lecture 28 - Exam date	Searching (cont)	HW4 due Monday, 5/3 Exam 3, Tuesday, May 4


http://www.cs.wpi.edu/~cs2005/d04/index.html