CSc21200 KL Fall 2006

Computer Science City College of New York
CSc21200 Section KL Data Structures, Fall 2006


Instructor: Class Meets: Classroom: Office Hours: Office: Email:	Professor Zhigang Zhu T, Th 09:00-10:40 AM NAC -6/268 Tuesday 1:30-4:00 pm NAC 8/210 zhu@cs.ccny.cuny.edu

Course Update Information

August 31. First Day of Class. Welcome all!
September 20, We are going to meet in NAC -6/268, starting on Sep 21(Thursday), 2006
September 20, Assignment submissions: please also send the results of your program using the exam program for each assignment. You may cut and paste the display on your Screen into a text file and send it with your submissions.
September 27, Grading for Quizzes.
September 27, Grading for Assignment 1.
September 27, Assignment 3 online
October 02, Grading for Assignments 1 & 2.
Exam 1: Oct 05, 2006, Thursday, 9:00 am - 10:40 am, NAC 6/268. You can only use your textbook.
October 10, Grading for Exam 1. We are going to discuss exam questions on Thursday in class.
October 17, Grading for Assignments 1, 2 & 3.
October 17, Grading for Quizzes 1-4.
November 01, Grading for Assignments 1, 2, 3 & 4.
November 06, Grading for Quizzes 1-6.
November 08, Grading for Exams 1 & 2.
Novemeber 14, Grading for Exam 2 was updated
November 14, The 3rd Exam is scheduled on Thursday, Dec 14, 2006, in the class time (9:00 -10:30 am) at NAC 6/268 (same classroom).
December 06, Grading for all the six assignments. On Dec 12, we are going to do a review for Exam 3, and to discuss assignment and quiz questions related to Exam 3.
December 18, 2006. Grading for Exam 3, and Final Grading ( = Eaxm*64%+ Assignment *18% + Quizzes*18%)

Course Objectives

This course teaches the basic techniques to orgranize 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++, Third Edition, by Michael Main and Walter Savitch , ISBN 0-201-70297-5, Addison Wesley, softcover. 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 Fall 2006 academic calendar:


Date	Planned Lecture Topics	Read/Assign/Exam
Aug 29 (X) Aug 31 (Th)	Last day for 100% refund Lecture 1. Introduction & Software Development	Ch. 1
Sep 05 (T) Sep 07 (Th)	Lecture 2. ADT & C++ Classes (code) Lecture 3. More Classes and Operator Overloading	Ch 2.1-2.3; Assignment 1 Ch 2.4-2.5
Sep 12 (T ) Sep 14 (Th)	Lecture 4. Container Classes Lecture 5. Container Classes (cont.)	Ch 3 (code) Ch 3, Assignment 2
Sep 19(T) Sep 21 (Th)	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
Sep 26 (T) Sep 28 (Th)	Lecture 8. Dynamic Classes and the Big Three (code) Exam Review 1	Assignment 3
Oct 03 (T) Oct 05 (Th)	Monday schedule; no class! First Exam (Chapters 1-4)
Oct 10 (T) Oct 12 (Th)	Lecture 9. Linked Lists ( code) Lecture 10. Building &Using the Linked List Toolkit (code)	Ch. 5.1-5.2, Assignment 4 Ch. 5.3 - 5.5
Oct 17 (T) Oct 19 (Th)	Lecture 11. Software Development using Templates and Iterators Lecture 11a. Software Development using Templates and Iterators (cont.)	Ch. 6, code (bag4&5, node2)
Oct 24 (T) Oct 26 (Th)	Lecture 12. Stacks (code) and Queues (code) Lecture 13. Introduction to Recursion	Ch. 7, Ch 8 Ch. 9.1 , Assignment 5
Oct 31 (T) Nov 02 (Th)	Lecture 14. Using and Reasoning about Recursion Exam Review 2 ; Assignment Discussions	Ch. 9.2 - 9.3
Nov 07 (T) Nov 09 (Th)	Second Exam (Chapters 5-9) Lecture 15. Trees and Traversals (code)	Ch. 10.1-10.4
Nov 14 (T) Nov 16 (Th)	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
Nov 21(T) Nov 23 (X )	Lecture 18. Heaps and Priority Queues ; Time Anaysis of Trees Thanksgiving Holiday	Ch. 11.1, 11.3
Nov 28 (T) Nov 30 (Th)	Lecture 19. Searching Lecture 20. Hashing	Ch. 12.1-12.2 Ch. 12.2-12.4
Dec 05 (T) Dec 07 (Th)	Lecture 21. Quadradic Sorting Lecture 22. Recusive Sorting , Heapsort & the STL Quicksort (code)	Ch. 13.1 Ch. 13.2-13.4
Dec 12 (T) Dec 14 (Th)	Exam 3 Review , Assignment and Quiz Discussions Third Exam (Ch 10-13) , 9:00 - 10:30 am, NAC 6/268

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.