CSc21200 AB Fall 2004

Computer Science City College of New York
CSc21200 Section AB Data Structures, Fall 2004


Instructor: Class Meets: Classroom: Office Hours: Office: Email:	Professor Zhigang Zhu M, W 09:00-10:40 AM R 6/314 Monday 3:00-5:30 pm R 8/203A zhu@cs.ccny.cuny.edu

Course Update Information (Bulletin Board )

August 30. First Day of CSc 21200 AB Class
Aug. 31, Assignment 1 online. Due on Sept 13 (answer)
Sep 20, Assignment 2 online. Due on Sept 29
Sep 27, code (newpoint) for overloading >> operator (in four different ways)
Sep 28, Assignment 3 online
Sep 29, Exam 1 - Oct 06, 2004, in our classroom, 9:00 am - 10:40 am
Sep 29, For those who cannot read PPT slides, please check out the JPEG images for each lecture (link is provided below as "lecture##"). You will need to have WINRAR (free downloadble) installed in your machine to unzip this files.
Oct 13, Grading for Assignments, Quizzes and Exams
Oct 18. Assignment 4 online
Oct 20. Please check out slides of Oct 20 for a homework on Template Classes. Please turn it in on Oct 27.
Oct 25. Grading for Assignments 1-3
Oct 18. Deadline for Assignment 4 has been extended to Nov 2, 2004 (Tuesday) before 5:00 pm
Nov 1, Assignment 5 online
Nov 8, Assignment 6 online
Nov 14, Second Exam on Nov 17 (Wed) @ 9:00 -10:40 am, NAC 6/314, Self-reviews on Monday (no class meet), Office hours as usual in NAC 8/203 (with Mr. Weihong Li). Please check the course schedule below for more information.
Nov 18. Grading for Assignments 1-5
Nov 22, Assignment 7 online
Nov 23, Grading for 5 Assignments, 6 Quizzes and 2 Exams
Nov 23. If you have difficulties in finishing Assignment 6 before Thanksgiving, you may send your work by Nov 26 (Friday) without penalty. You may also submit on Saturday or Sunday with a 5% penalty each day. No submissions will be accepted after Sunday
Nov 30, Answer for Assignment 6; We will discuss Exam 2 on Wed Dec 1.
Dec 06, Grading for Assignments 1-6, Quizzes 1-8 and Exams 1&2
Dec 13, 2004. No class meet on Tuesday (Dec 14)
Dec 14, 2004. Slides for Lecture 22 has been updated to include a more accurate analysis of the Big-O of the heapsort algorithm.
Exam 3: Dec 16 (Thur, 8:00 – 10:20 am, R 6/314 )
Dec 29. Grading for Assignments 1-7 (32%), Quizzes 1-8 (8%) and Exams 1-3 (60%)

Final Score = (A1+...+A6)* 5%+ A7 * 2%+ (Q1+...+Q8 ) 1/10 + (E1+E2+E3) 20% = 100

Break-down: A+ >=90; A> = 80; A- >=75; B+ >= 70; B >=65; B- >=60; C+ >=55; C>=50; C->=45; F <45

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++, 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 Fall 2004 academic calendar:


Date	Planned Lecture Topics	Read/Assign/Exam
Aug 30 (M) Sep 01 (W)	Lecture 1. Introduction & Software Development (lecture01) Lecture 2. ADT & C++ Classes (code) (lecture02)	Ch. 1 Ch 2.1-2.3; Assignment 1
Sep 06 (X) Sep 08 (W)	Labor Day, no class. Lecture 3. More Classes and Operator Overloading (lecture03a) (lecture03)	Ch 2.4-2.5
Sep 13 (M ) Sep 15 (X)	Lecture 4. Container Classes (lecture04) College Open, No Class.	Ch 3 (code)
Sep 20(M) Sep 22 (W)	Lecture 5. Container Classes (cont.) Lecture 6. Pointers and Dynamic Arrays (I) (point code with pointers) (lecture06)	Ch 3, Assignment 2 Ch 4.1 - 4.2
Sep 27 (M) Sep 29 (W)	Lecture 7. Pointers and Dynamic Arrays (II) (lecture07) Lecture 8. Dynamic Classes and the Big Three (code) (lecture08)	Ch. 4.2 - 4.5 Assignment 3
Oct 04 ( M) Oct 06 (W)	Exam review 1 First Exam (Chapters 1-4)
Oct 11 (X) Oct 13 (W)	Columbus Day, No Class. Lecture 9. Linked Lists ( code)	Ch. 5.1-5.2
Oct 18 (M) Oct 20 (W)	Lecture 10. Building &Using the Linked List Toolkit (code) Lecture 11. Software Development using Templates and Iterators	Ch. 5.3 - 5.5, Assignment 4 Ch. 6, code (bag4&5, node2)
Oct 25 (M) Oct 27 (W)	Lecture 11a. Software Development using Templates and Iterators (cont.) Lecture 12. Stacks (code) and Queues (code)	Ch. 7, Ch 8
Nov 01 (M) Nov 03 (W)	Lecture 13. Introduction to Recursion Lecture 14. Using and Reasoning about Recursion	Ch. 9.1 , Assignment 5 Ch. 9.2 - 9.3
Nov 08 (M) Nov 10 (W)	Lecture 15. Trees and Traversals (code) Lecture 16. Binary Search Trees and the Bag Class with a BST	Ch. 10.1-10.4 Ch. 10.5, Assignment 6
Nov 15 (M) Nov 17 (W)	Review for Exam 2 (no class meet) Second Exam (Chapters 5-9)	9:00 -10:40 am, R 6/314
Nov 22(M) Nov 24 (X )	Lecture 17. Heaps and Priority Queues ; ; Time Anaysis of Trees Friday Schedule (before Thanksgiving )	Ch. 11.1, 11.3, Assignment 7
Nov 29 (M) Dec 01 (W)	Lecture 18. B-Trees and Set Class (code) Lecture 19. Searching; Exam 2 Discussions	Ch. 11.2 Ch. 12.1-12.2
Dec 06 (M) Dec 08 (W)	Lecture 20. Hashing Lecture 21. Quadradic Sorting	Ch. 12.2-12.4 Ch. 13.1
Dec 13 (M) Dec 14 (T)	Lecture 22. Recusive Sorting , Heapsort & the STL Quicksort (code) Exam review 3 (no class meet)	Ch. 13.2-13.4
Dec 16 (Th)	Final exam (mainly Ch 10-13, some from Ch 1-9)	8:00 – 10:20 am , R 6/314

Notes:

1: No classes on 09/06(M), 09/15(W), 10/11 (M) and 11/24 (W)
2. 12/14 (Tue) will have Wednesday schedule (last day of classses)
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

We will meet Monday and Wednesday 9:00-10:40 am at NAC R-6/314. 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.