CSc21200 FG Fall 2012

Computer Science City College of New York
CSc21200 Section FG Data Structures, Fall 2012


Instructor: Class Meets: Classroom: Office Hours: Office: Email:	Professor Zhigang Zhu M,W 04:00-05:40PM NAC-4/121B Wed:11:00 am - 12:00 pm; 2:00 pm - 3:00 pm NAC 8/210 or 8/211 zhu@cs.ccny.cuny.edu

Course Update Information

August 27, 2012 (Monday). First day of this class.
August 27, 2012. MinGW C++ Installation Tutorial for Windows and Mac users.
August 29, 2012. Assignment 1 online, due Sept 12, 2012
September 04, 2012, Grading for Quiz 1.
September 05, 2012, Assignment 2 online, due Sept 26, 2012.
September 11, 2012, Grading for Quizzes 1-2.
September 18, 2012, Grading for Assignment 1.
September 27, 2012, Grading for Quizzes 1-4.
October 02, 2012, Grading for Assignments 1-2.
October 09, 2012, Grading for Exam 1. We will discuss Exam 1 in the class of Wednesday Oct 10, 2012.
October 16, 2012, Grading for Quizzes 1-6.
October 02, 2012, Grading for Assignments 1-3.
October 31, 2012. I hope everyone stay safe during the storm. We will still have our 2nd exam on Nov 7, so I hope everyone can use this storm "break" to do a review for the exam and a preview for Lectures 13 &14. We will go over them on Monday Nov 5 as a make-up class meet.
November 07, 2012, Grading for Quizzes 1-7.
November 08, 2012,Grading for Assignments 1-4. Due date for Assignment 5 has been extended for a week due to the storm.
November 09, 2012,Grading for Exams 1 & 2. We will discuss Exam 2 in the class of Monday November 12, 2012.
November 18, 2012, Grading for Quizzes 1-9.
November 29, 2012,Grading for Assignments 1-5
November 29, 2012,Grading for Quizzes 1-10.
November 30, 2012,Makeup Class on Lecture 21 Quadratic Sorting. Please review the slides before I post the online quiz question at 4:00 pm as well sending it to you via email. I will answer your questions via email during 4:00 - 5:00 pm. Please return your answer (the source code) back to me via email by 5:00 pm.
December 13, 2012,Grading for Quizzes 1-13 (Q11 was the online quiz).
December 13, 2012,Grading for Assignments 1-6
December 13, 2012,Grading for Exams 1, 2 & 3. We will discuss Exam 3 in the class of Friday December 14, 2012. We will have a quiz (2% of your final grade) too!
December 19, 2012, Grading for Quizzes 1-14
December 19, 2012, Final Grading. Happy New Year to ALL!

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 , Addison Wesley, softcover.

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. 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 Fall 2012 academic calendar:


Date	Planned Lecture Topics	Read/Assign/Exam
Aug 27 (M) Aug 29 (W)	Lecture 1. Introduction & Software Development Lecture 2. ADT & C++ Classes (code)	Ch. 1 Ch 2.1-2.3; Assignment 1
Sep 03 (M) Sep 05 (W)	Labor Day; college is closed - no class! Lecture 3. More Classes and Operator Overloading	Ch 2.4-2.5
Sep 10 (M ) Sep 12 (W)	Lecture 4/5. Container Classes (slides for Lectures 4&5) Lecture 6. Pointers and Dynamic Arrays (I) (Slides for Lectures 6 &7)	Ch 3 (code), Assignment 2 Ch 4.1 - 4.2
Sep 17 (M) Sep 19 (W)	NO CLASSES (College Open) Lecture 7. Pointers and Dynamic Arrays (II) (point code with pointers)	Ch. 4.2 - 4.5
Sep 24 (M) Sep 26 (W)	Lecture 8 . Dynamic Classes and the Big Three (code) NO CLASSES (College Open)	Assignment 3
Oct 01 (M) Oct 03 (W)	Exam Review 1 First Exam (Chapters 1-4)
Oct 08 (M) Oct 10 (W)	Columbus Day: college is closed - no class! Lecture 9. Linked Lists ( code) & Exam 1 Discussions (Monday schedule)	Ch. 5.1-5.2, Assignment 4
Oct 15 (M) Oct 17 (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)
Oct 22 (M) Oct 24 (W)	Lecture 11a. Software Development using Templates and Iterators (cont.) Lecture 12. Stacks (code) and Queues (code)	Ch. 7, Ch 8
Oct 29 (M) Oct 31 (W)	Lecture 13. Introduction to Recursion Lecture 14. Using and Reasoning about Recursion	Ch. 9.1 , Assignment 5 Ch. 9.2 - 9.3
Nov 05 (M) Nov 07 (W)	Exam Review 2 Second Exam (Chapters 5-9)
Nov 12 (M) Nov 14 (W)	Lecture 15. Trees and Traversals (code) and Exam 2 Discussions Lecture 16. Binary Search Trees and the Bag Class with a BST	Ch. 10.1-10.4 Ch. 10.5, Assignment 6
Nov 19 (M) Nov 21 (W )	Lecture 17. B-Trees and Set Class (code) Lecture 18. Heaps and Priority Queues(slides) ; Time Analysis of Trees(slides)	Ch. 11.2 Ch. 11.1, 11.3
Nov 26 (M) Nov 28 (W)	Lecture 19. Serial Searching and Binary Searching Lecture 20. Hashing & Nov 30 (F): Lecture 21. Quadratic Sorting	Ch. 12.1-12.3 Ch. 12.4, Ch. 13.1
Dec 03 (M) Dec 05 (W)	Lecture 22. Recursive Sorting , Heapsort & the STL Quicksort (code) Lecture 23. Graph Basics	Ch. 13.2-13.4 Ch. 15
Dec 10 (M) Dec 12 (W)	Exam Review 3 ; work-together coding, and a quiz Third Exam (mainly Ch 10-13, 15), NAC 4/121B
Dec 14 (F)	Discussion of the Third Exam and Assignments; an in-class quiz

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.