CSc212 PR Fall 2003

Computer Science City College of New York
CSc212 Section PR Data Structures, Fall 2003

Instructors


Name: Office: Email: Office Hours:	Professor Zhigang Zhu NAC 8/203A zhu@cs.ccny.cuny.edu Tue 4:00-7:00 pm

Course Update Information (Bulletin Board )

August 26. Course Web site online
Sept. 2, Assignment 1 online. Due on Sept 16
Sept. 2, Assignment 2 online. Due on Oct 2.
Sept. 26, Assignment 3 online. Due on Oct 16.
Sept. 30. Announcement: Exam 1 will be on Oct 02 (Thursday) 2:00 pm - 3:40 pm in NAC 4/129
Sept. 30. Office hours on Tuesday Oct 14 will be moved to 11:30 am - 1:30 pm the same day.
Sept. 30. Answer for Assignment 1
Oct 1, Grading for Quizzes 1 and 2
Oct 12, Grading for Exam 1 - We will discuss Exam 1 and Assignments on Tuesday.
Oct 13, Answer for Assignment 2(header, implementation);
Oct 14. Assingment 4 online. Due Thursday, Oct. 30 before class
Oct 21, Homework in Slide 20 of Lecture 11. Due Oct 28 before class.
Oct 22. Please check the Bulletin Board (CSc 212). Those who want to install the latest GNU software, please send me email or post your reply in the Bulletin Board
Oct 23. Tuesday (Oct 28) Class will be in NAC 8/203.
Oct 29. Assignment 5 online, Due Thursday, Nov 13.
Oct 29, Second Exam is scheduled on Nov 13 (Thursday).
Nov 6, Assignment 6 online
Nov 8. Grading for Assignments 1-4 online. Please bring your work (Assignment 4) to class of Tuesday Nov 11.
Nov 22, Grading for Exams 1 and 2 - We will discuss Exam 2 on Tuesday (Nov 25).
Nov 22. Office Hours on Tuesday (Nov 25) change to 11:00 am - 1:30 pm.
Nov 23. Grading for Assignments 1-5 online.
Final Exam Schedule: TUES DEC 16 8:00 - 10:20 am, NAC R4/129
Dec 10. Grading for Assignments 1-6 online - we will do a review for the final, and discuss Assignment 6 on Thursday.
Dec 11, Grading for Quizzes 1 to 3 and Homework 1, 2

Dec 17. Grading for Exams 1 and 3 .
Dec 18. Final Grading.

Formula:

Score = sum(Exams)* 15/100 + sum(Quizzes) * 2/10 + sum(Assignments)* 7.5/100 + Extra * 5/10

Break-down:

A: Score >=85
B: 75<= Score <= 84
C: 60<= Score <= 74
F: Score < 60

Statistics: Sum(Number (Grade)) = 6 (A) + 7 (B) + 5 (C) + 4 (F) + 3 (W) = 25 students

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 2003 academic calendar:


Date	Planned Lecture Topics	Read/Assign/Exam
Sep 02 (Tu) Sep 04 (Th)	Lecture 1. Introduction & Software Development Lecture 2. ADT & C++ Classes	Ch. 1 Ch 2.1-2.3; Assignment 1
Sep 09 (Tu) Sep 11 (Th)	Lecture 3. More Classes and Operator Overloading Lecture 4. Container Classes	Ch 2.4-2.5 (code) Ch 3 (code)
Sep 16 (Tu ) Sep 18 (Th)	Lecture 5. Container Classes (cont.) Lecture 6. Pointers and Dynamic Arrays (I) (code)	Ch 3, Assignment 2 Ch 4.1 - 4.2
Sep 23 (Tu) Sep 25 (Th)	Lecture 7. Pointers and Dynamic Arrays (II) Lecture 8. Dynamic Classes and the Big Three (code)	Ch. 4.2 - 4.5, Assignment 3
Sep 30 (Tu) Oct 02 (Th)	Exam review 1 First Exam (Chapters 1-4)	NAC 4/129
Oct 07 ( x) Oct 09 (Th)	Monday schedule, no class Lecture 9. Linked Lists ( code)	Ch. 5.1-5.2
Oct 14 (Tu) Oct 16 (Th)	Discussions: Exam 1 and Assignments Lecture 10. Building &Using the Linked List Toolkit (code)	Assignment 4 Ch. 5.3 - 5.5
Oct 21 (Tu) Oct 23 (Th)	Lecture 11. Software Development using Templates and Iterators Lecture 12. Stacks (code) and Queues (code)	Ch. 6, code (bag4&5, node2) Ch. 7, Ch 8
Oct 28 (Tu) Oct 30 (Th)	Lecture 13. Introduction to Recursion (NAC 8/203) Lecture 14. Using and Reasoning about Recursion	Ch. 9.1, Assignment 5 Ch. 9.2 - 9.3
Nov 04 (Tu) Nov 06 (Th)	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 11 (Tu) Nov 13 (Th)	Review for Exam 2 Second Exam (Chapters 5-9)
Nov 18 (Tu) Nov 20 (Th)	Lecture 17. Heaps and Priority Queues (2MB!) Lecture 18. B-Trees and Set Class(code); Time Anaysis of Trees	Ch. 11.1, 11.3 Ch. 11.2
Nov 25(Tu) Nov 27 ( x )	Lecture 19. Searching Thanksgiving Holiday	Ch. 12.1-12.2 Relax !
Dec 02 (Tu) Dec 04 (Th)	Lecture 20. Hashing Lecture 21. Quadradic Sorting	Ch. 12.2-12.4 Ch. 13.1
Dec 09 (Tu) Dec 11 (Th)	Lecture 22. Recusive Sorting , Heapsort & the STL Quicksort (code) Exam review 3	Ch. 13.2-13.4
Dec 16-23	Final exam (mainly Ch 10-13, some from Ch 1-9)	8:00 - 10:20 am, NAC R4/129

Notes:

1: No classes on 10/07 (Tu) and 11/27 (Th).
2. Most of the lectures have reading assignments that you should complete before the lecture
3. The lecture PPT slides are with color background - you'd better print them out in B-W.

Assignments and Grading

We will meet Tue and Thu 2:00-3:40 pm at NAC R-4/129. 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 45% 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 (45% 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.

@Zhigang Zhu (email zhu@cs.ccny.cuny.edu ) August 2003.