CSc21200 AB Spring 2006

Computer Science City College of New York
CSc21200 Section AB Data Structures, Spring 2006


Instructor: Class Meets: Classroom: Office Hours: Office: Email:	Professor Zhigang Zhu M, W 09:00-10:40 AM NAC 7227 Monday 11:00 am - 1:00 pm R 8/210 zhu@cs.ccny.cuny.edu

Course Update Information

January 30, 2006. First Day of Class. Welcome all and Happy Chinese New Year!
January 31, 2006. Assignment 1 online
February 01, 2006, Grading for Quiz 1
Feb 08, 2006. Assignment 2 online
February 16, 2006, Grading for Quizzes 1~3
Feb 22, 2006, Grading for Quizzes 1~4
Feb 23, 2006, Changes of Office Hours on Feb 27, 2006 (Monday): 4:00 - 6:00 pm
Feb 28, 2006, Grading for Quizzes 1~5
Feb 28, 2006, Grading for Assignment 1----here is my solution for your reference
March 4, 2006, Answer for Assignment 2 (implementation file, header file)- no submissions will be accepted after 11:30 pm of March 4.
Exam 1: Monday, March 06, 2006, 9:00 am - 10:40 am, NAC 7227 (our classroom)
March 8, 2006, Grading for Quizzes 1~6 (Press "Refresh" in your browser if you cannot see the latest one)
March 8, 2006, Grading for Exam 1. We will discuss Exam 1 in the class of March 13, 2006.
March 19, 2006, Grading for Assignments 1&2. We will discuss Assignments 1,2 and 3 in class.
March 22, 2006, Grading for Quizzes 1~7
April 02, 2006, Grading for Assignments 1 to 4. We will discuss Assignment 3 (solution) and Assignment 4 (solution) in the class of April 03.
April 03, 2006, Office hours today moved to 5:00 - 7:00 pm at NAC 8/210.
April 06, 2006, Grading for Exam 2. We will discuss Exam 2 in the class of April 10, 2006.
May 02, 2006, Grading for Assignments 1 to 5.
March 22, 2006, Grading for Quizzes 1~11.
Final Exam: NA 7227, TUESDAY MAY 23 3:45-5:30 PM
May 25, 2006, Grading for Exams 1-3.
May 25, 2006, Grading for Assignments 1 to 6.
May 25, 2006, Grading for Quizzes 1~14.
May 31, 2006, Final Grading

Course Objectives

This course teaches the basic techniques to organize data in a running program You will know about well-known data structures as listed in the Quick Syllabus. You will be able to

(1) implement these structures as classes in C++;
(2) determine which structures are appropriate in various situations;
(3) confidently learn new structures beyond what's presented in this class.

You will also learn part of object-oriented programming and software development methodology.

**Quick Syllabus**
To become a Data Structures Expert start by learning... Precondition/Postcondition specifications Time analysis techniques Container classes Pointers and dynamic arrays Linked lists Templates and iterators Stacks Queues Recursive thinking Trees Sorting and searching techniques

Textbook and References

Textbook: Data Structures and Other Objects Using C++, Second Edition, by Michael Main and Walter Savitch , ISBN 0-201-70297-5, Addison Wesley, softcover, 816 pages. Textbook can be found in CCNY bookstore.

Supplements: The Code for the Book and the Corrections for the Text will be useful and can be found by clicking here.

References: Lots of good sample codes are found in CSc102's C++ How to Program by Dietel & Dietel, 3rd Ed., Prentice Hall 2001, QA76.73.C153D45, ISBN 0-13-089571-7. This course involves some of C++ language details that could be found in this book.

Prerequisites

CSc102 (Introduction to Computing) and CSc104 (Discrete Mathematical Structure I). You should feel confident in your ability to design and implement simple programs using arrays and functions: as a rough guide line, all the materials before Chapter 5 (Pointers and Strings) of C++ How to Program by Dietel & Dietel are assumed to be understood. You should be familiar with some programming environment--either a PC or a Unix system.

Schedule

The following schedule is based on Spring 2006 academic calendar:


Date	Planned Lecture Topics	Read/Assign/Exam
Jan 30 (M) Feb 01 (W)	Lecture 1. Introduction & Software Development Lecture 2. ADT & C++ Classes (code)	Ch. 1 Ch 2.1-2.3; Assignment 1
Feb 06 (M) Feb 08 (W)	Lecture 3. More Classes and Operator Overloading Lecture 4. Container Classes (code)	Ch 2.4-2.5 Ch 3, Assignment 2
Feb 13 (X ) Feb 15 (W)	College Closed (Lincoln's Birthday) Lecture 5. Container Classes (cont.)	Ch 3
Feb 21 (T) Feb 22 (W)	Lecture 6. Pointers and Dynamic Arrays (I) (point code with pointers) Lecture 7. Pointers and Dynamic Arrays (II)	Ch 4.1 - 4.2 Ch. 4.2 - 4.5
Feb 27 (M) Mar 01 (W)	Lecture 8. Dynamic Classes and the Big Three (code) Exam Review 1	Assignment 3
Mar 06 (M) Mar 08 (W)	First Exam (Chapters 1-4) Lecture 9. Linked Lists ( code)	Ch. 5.1-5.2, Assignment 4
Mar 13 (M) Mar 15 (W)	Lecture 10. Building &Using the Linked List Toolkit (code) Lecture 11. Software Development using Templates and Iterators	Ch. 5.3 - 5.5 Ch. 6, code (bag4&5, node2)
Mar 20 (M) Mar 22 (W)	Lecture 11a. Software Development using Templates and Iterators (cont.) Lecture 12. Stacks (code) and Queues (code)	Assignments Discussions Ch. 7, Ch 8
Mar 27 (M) Mar 29 (W)	Lecture 13. Introduction to Recursion Lecture 14. Using and Reasoning about Recursion	Ch. 9.1 , Assignment 5 Ch. 9.2 - 9.3
Apr 03 (M) Apr 05 (W)	Exam Review 2 Second Exam (Chapters 5-9)
Apr 10 (M) Apr 12 (X)	Lecture 15. Trees and Traversals (code) Spring Recess	Ch. 10.1-10.4
Apr 17 (X) Apr 19 (X)	Spring Recess
Apr 24(M) Apr 26 (W )	Lecture 16. Binary Search Trees and the Bag Class with a BST Lecture 17. B-Trees and Set Class (code)	Ch. 10.5, Assignment 6 Ch. 11.2
May 01 (M) May 03 (W)	Lecture 18. Heaps and Priority Queues;Time Anaysis of Trees Lecture 19. Searching	Ch. 11.1, 11.3,Assignment 7 Ch. 12.1-12.2
May 08 (M) May 10 (W)	Lecture 20. Hashing Lecture 21. Quadradic Sorting	Ch. 12.2-12.4 Ch. 13.1
May 15 (M) May 17 (W)	Lecture 22. Recusive Sorting , Heapsort & the STL Quicksort (code) Exam Review 3 , Assignment Discussions	Ch. 13.2-13.4
MAY 23	Final exam (mainly Ch 10-13, some from Ch 1-9)	3:45-5:30 PM, NAC 7227

Notes:

1: No classes on 02/13(M), 02/20(M), 04/12 - 04/23 (Spring Recess)
2. 02/21 (Tue) will have Monday schedule
3. Most of the lectures have reading assignments that you should complete before the lecture
4. The lecture PPT slides will have color background s - you'd better print them out in B-W.

Assignments and Grading

See syllabus above for the tentative timetable for a schedule. There will be six to seven programming assignments distributed roughly every two weeks (counted roughly 30% of your final grade). Several in-class small quizzes will add up to 10 % of your final grade. There will be three in-class exams (60% of your final grade). Dates of these exams will be announced beforehand.

Policies: Students may discuss ideas together. But since each student get credits for his or her submissions, all actual program code and written answers must be done separately by each student, and must not be shared.

Communications: I would like the course to run smoothly and enjoyably. Feel free to let me know what you find good and interesting about the course. Let me know as soon as possible about the reverse. You may see me in my office during my hours or send me messages by e-mail.

Computing Facilities

The language used for this class is ANSI Standard C++ as supported by today's available compilers. Variety of PC based C++ compilers are available such as Borland C++ and Microsoft Visual C++, also publicly accessible at our Student Computer Labs.