CS 2005 B 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 and binary search
• Analyze sequential and binary search using big-O analysis
• Gain further experience with the Unix operating system and its tools

---

Staff

Instructor: Glynis Hamel

Teaching Assistant: Ashish Samant

Senior Assistant: Paul Ruggieri

Office Hour Schedule

(Note: Except where noted, TA/SA office hours are held in AK 120d. Glynis Hamel's office hours are held in FL 132.)




Day/Time	10:00	11:00	12:00	1:00	2:00	3:00	4:00	5:00	6:00	7:00	8:00
Monday		Mrs. Hamel				Ashish (3:30...	...5:00) Ashish			Paul	Paul
Tuesday					Mrs. Hamel	Mrs. Hamel	Ashish (FL A22)			Paul	Paul
Wednesday
Thursday	Mrs. Hamel						Ashish(4:00...	...5:30)Ashish
Friday




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 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 B-term from 9am - 10am. 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 will be given in FL AUD (Perreault Lecture Hall) on MTRF at 1pm. Labs meet on Wednesdays according to the following schedule:

Section	Lab Time	Lab Location
B01	9-9:50	AK 120d
B02	10-10:50	AK 120d
B03	11:00-11: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 (51%)

Three exams will be given. 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 (40%)

Five 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 (9%)

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 9 lab grades/group assignment grades will be added to your final average to account for 9% 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.

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% 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
Oct 26 - 29	Chapter 1 Chapter 9.1, 9.3 Powerpoint 1 Lecture 1 objectives Lecture 2 objectives Prof. Wong's Lecture 2 slides Lecture 3 objectives Prof. Wong's Lecture 3 slides	Course overview C++ review recursion	Lab 1 Wed 10/27 Homework 1 Notes for students transitioning from CS 1101 to CS 2005
Nov 1 - 5	Chapter 13.1, 13.2 Chapter 2 Powerpoint 2 Lecture 4 objectives Lecture 5 objectives Lecture 6 objectives Lecture 7 objectives	recursion (cont) quadratic sorting algorithms recursive sorting algorithms introduction to classes	Lab 2 Wed 11/3 HW1 due Thursday, 11/4 Homework 2
Nov 8 - 12	Chapter 3.1, 3.3 Powerpoint 3 Lecture 8 objectives Lecture 9 objectives Prof. Wong's Lecture 9 slides Lecture 10 objectives Lecture 11 - Exam Exam 1 Answers	bag ADT overloaded operators friend function	Lab 3 Wed 11/10 HW2 Part 1 due Thursday, 11/11 Exam 1 Friday, November 12
Nov 15 - 19	Chapter 4.1 - 4.4 Chapter 5.1 Lecture 12 objectives Lecture 13 objectives Lecture 14 objectives Lecture 15 objectives	pointers dynamically-allocated arrays copy constructor overloaded assignment introduction to linked lists	HW2 Part 2 due Tuesday, 11/16 Lab 4 Wed 11/17 Homework 3
Nov 22 - 23	Chapter 5.2, 5.3 Lecture 16 objectives Lecture 17 objectives	linked lists (cont)	HW3 due Tuesday, 11/23 Homework 4
Nov 29 - Dec 3	Chapter 6.1 Chapter 10.1 Chapter 11.1 Powerpoint 6 Lecture 18 objectives Lecture 19 objectives Lecture 20 - Exam Answers to Exam 2 Lecture 21 objectives	template functions introduction to trees heaps priority queues	Lab 5 Wed 12/1 Exam 2 Thursday, December 2
Dec 6 - 10	Chapter 13.3 Chapter 6.2 Chapter 7 Chapter 8 Chapter 10.2 - 10.4 Lecture 22 objectives Lecture 23 objectives Algorithm for palindrome program Lecture 24 objectives Lecture 25 objectives	heapsort template classes stack queue binary tree traversals	HW4 due Tuesday, 12/7 Homework 5
Dec 13 - 16	Chapter 10.5 Powerpoint 10, 11 Lecture 26 objectives Lecture 27 objectives Lecture 28 - Exam	binary search trees	HW5 due Tuesday, 12/14 Exam 3 Thursday, December 16


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