CSc21200 RS Spring 2011

Computer Science City College of New York
CSc21200 Section RS Data Structures, Spring 2011


Instructor: TA: Class Meets: Classroom: Office Hours: Office: Email:	Professor Zhigang Zhu Mr. Wai L. Khoo T,TH 04:00-05:40PM NAC-6/114 Tuesday 6:00 pm – 7:00 pm, Thursday 2:30 pm – 3:30 pm NAC-8/210 zhu@cs.ccny.cuny.edu

Course Update Information

January 28, 2011. First Day of Classes (Our first class is on Feb 01). Welcome all!
Feb 01, 2011, C++ Installation Tutorial for Windows and Mac users.
Feb 10, 2011, Grading for Quiz 1.
Feb 10. 2011. Wai Khoo will send emails to you for joining our CSc212 Google group.You can find the link to the respective Google group in his homepage. You may also send emails to him.
Feb 12, 2011, Grading for Quizzes 1 & 2.
Feb 21, 2011, Grading for Assignment 1(updated).
Feb 21, 2011, Grading for Quizzes 1 to 3.
Feb 25, 2011, Grading for Quizzes 1 to 5.
Feb 28, 2011, Grading for Assignments 1 & 2
Mar 05, 2011, Grading for Exam 1. We will discuss Exam 1 in the class of March 08 (Tuesday)
Mar 16, 2011, Grading for Quizzes 1 to 6.
Mar 18, 2011, Grading for Assignments 1 to 3
April 4, 2011, Second Exam April 05, 2011, NAC 6/114, 4:00 pm - 5:40 pm
April 4, 2011, Grading for Assignments 1 to 4
April 4, 2011, Grading for Quizzes 1 to 9.
April 06, 2011, Grading for Exams 1 & 2. We will discuss Exam 2 in the class of April 07 (Thursday)
May 14, 2011, Grading for Assignments 1 to 6
May 14, 2011, Grading for Quizzes 1 to 14.
May 14, 2011, Third Exam May 17, 2011, NAC 6/114, 4:00 pm - 5:40 pm
May 18, 2011, Grading for Exams 1 to 3. No make-up homework will be accepted after midnight on Wednesday May 18, 2011.
May 19, 2011, Final Grading

Course Objectives

This course teaches the basic techniques to orgranize data in running programs. 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 are 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 Graphs

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 guideline, 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 2011 academic calendar :


Date	Planned Lecture Topics	Readings/Assignments
Feb 01 (T) Feb 03 (Th)	Lecture 1. Introduction & Software Development Lecture 2. ADT & C++ Classes (code)	Ch. 1 Ch 2.1-2.3; Assignment 1
Feb 08 (T ) Feb 10 (Th)	Lecture 3. More Classes and Operator Overloading Lecture 4. Container Classes (slides for Lectures 4&5)	Ch 2.4-2.5 Ch 3 (code)
Feb 15 (T) Feb 17 (Th)	Lecture 5. Container Classes (cont.) Lecture 6. Pointers and Dynamic Arrays (I) (slides for Lectures 6 &7)	Ch 3, Assignment 2 Ch 4.1 - 4.2
Feb 22 (T) Feb 24 (Th)	Lecture 7. Pointers and Dynamic Arrays (II) (point code with pointers) Lecture 8. Dynamic Classes and the Big Three (code)	Ch. 4.2 - 4.5 Assignment 3
Mar 01 (T) Mar 03 (Th)	Exam Review 1 First Exam (Chapters 1-4)
Mar 08 (T) Mar 10 (Th)	Lecture 9. Linked Lists ( code) & Exam Discussions Lecture 10. Building &Using the Linked List Toolkit (code)	Ch. 5.1-5.2, Assignment 4 Ch. 5.3 - 5.5
Mar 15 (T) Mar 17 (Th)	Lecture 11. Software Development using Templates and Iterators Lecture 11a. Software Development using Templates and Iterators (cont.)	Ch. 6, code (bag4&5, node2)
Mar 22 (T) Mar 24 (Th)	Lecture 12. Stacks (code) and Queues (code) Lecture 13. Introduction to Recursion	Ch. 7, Ch 8 Ch. 9.1 , Assignment 5
Mar 29 (T) Mar 31 (Th)	Lecture 14. Using and Reasoning about Recursion Exam Review 2 ; Assignment Discussions	Ch. 9.2 - 9.3
Apr 05 (T) Apr 07 (Th)	Second Exam (Chapters 5-9) Lecture 15. Trees and Traversals (code); Exam 2 discussions	Ch. 10.1-10.4
Apr 12 (T) Apr 14 (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
Apr 17 -26 Apr 28 (Th)	Spring Recess Lecture 18. Heaps and Priority Queues ; Lecture 18a Time Anaysis of Trees	Ch. 11.1, 11.3
May 03 (T) May 05 (Th)	Lecture 19. Searching & Lecture 20. Hashing Lecture 21. Quadradic Sorting	Ch. 12.1-12.4 Ch. 13.1
May 10 (T) May 12 (Th)	Lecture 22. Recusive Sorting , Heapsort & the STL Quicksort (code) Lecture 23. Graphs; Exam Review 3	Ch. 13.2-13.4 Ch. 15
May 17 (T)	Final Exam (mainly Ch 10-13, 15)

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 determined in due times and 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 (both Windows and Linux) C++ compilers are available, also publicly accessible at our Student Computer Labs.