CSc21200 FG Fall 2015

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


Instructor: TA Class Meets: Classroom: Office Hours: Office: Email:	Professor Zhigang Zhu Mr Wai L. Khoo <khoo@cs.ccny.cuny.edu> M,W 04:00-05:40PM Shepard S-308 M/W: 2:00 pm - 3:00 pm NAC 8/211 zhu@cs.ccny.cuny.edu

Course Update Information

August 31, 2015 (Monday). First day of this class.
September 02, 2015. MinGW C++ Installation Tutorial for Windows and Mac users.
September 02, 2015. Assignment 1 online, due on September 16 (Wednesday), 2015. Note: This submission (and the rest) should be submitted via an online Homework Submission Site. For retrieve your grade, please go to the Grade Retrieval Site. Details please visit the instructions of each assignment. We'll be conducting all class-related discussion on Piazza this term. Please login and enroll the class. The quicker you begin asking questions on Piazza (rather than via emails), the quicker you'll benefit from the collective knowledge of your classmates and instructors. We encourage you to ask questions when you're struggling to understand a concept - you can even do so anonymously.
September 02, 2015. Grading for Quiz 1.
September 15, 2015. Assignment 1 due on Sept 16, but there's a submission grace period that last till this Saturday. Note that even though technically, .cxx and .cpp are the same for C++ code, for uniformity in the submission system, we requested .cxx.
September 15, 2015. Grading for Quizzes 1-2.
September 21, 2015. Grading for Assignment 1.
September 21, 2015. Grading for Quizzes 1-3.
September 29, 2015. Grading for Quizzes 1-4.
October 05, 2015. First Exam 4:00 - 5:30 pm.
October 05, 2015. Grading for Assignments 1-2.
October 12, 2015. Grading for Quizzes 1-5.
October 12, 2015. Grading for Assignments 1-2 and Exam 1. We will discuss Exam 1 in class!
October 19, 2015. Grading for Assignments 1-3 and Exam 1.
November 06, 2015. Grading for Quizzes 1-8.
November 06, 2015. Grading for Assignments 1-4 and Exam 1.
November 10, 2015. Assignment 6 online, due Dec 2, 2015.
November 17, 2015. Grading for Assignments 1-5 and Exams 1 & 2. We will discuss Exam 2 on Wednesday Nov 18 in class.
December 08, 2015. Grading for Quizzes 1-12.
December 08, 2015. Grading for Assignments 1-6 (updated and finalized) and Exams 1 & 2. We will have Exam 3 on Dec 14, and review for Exam 3 on Dec 9.
December 24, 2015. Final grading will be posted in a few days - please come back to check. Merry Christmas and Happy New Year!
December 29, 2015. Grading for Quizzes 1-13.
December 29, 2015, Final Grading will be submitted on January 2nd, 2016.

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

CSc103 (Introduction to Computing to CS and CpE Majors) 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 2015 academic calendar:


Date	Planned Lecture Topics	Read/Assign/Exam
Aug 31 (M) Sep 02 (W)	Lecture 1. Introduction & Software Development Lecture 2. ADT & C++ Classes (code)	Ch. 1 Ch 2.1-2.3; Assignment 1
Sep 07 (M ) Sep 09 (W)	Labor Day; college is closed - no class! Lecture 3. More Classes and Operator Overloading	Ch 2.4-2.5
Sep 10 (M) Sep 16 (W)	Lecture 4/5. Container Classes (slides for Lectures 4&5) Note this is a Thursday! Lecture 6. Pointers and Dynamic Arrays (I) (Slides for Lectures 6 &7)	Ch 3 (code), Assignment 2 Ch 4.1 - 4.2
Sep 21 (M) Sep 23 (W)	Lecture 7. Pointers and Dynamic Arrays (II) (point code with pointers) NO CLASSES (College Open)	Ch. 4.2 - 4.5
Sep 28 (M) Sep 30 (W)	Lecture 8 . Dynamic Classes and the Big Three (code) Exam Review 1	Assignment 3
Oct 05 (M) Oct 07 (W)	First Exam (Chapters 1-4) Lecture 9. Linked Lists ( code)	Ch. 5.1-5.2
Oct 12 (M) Oct 14 (W)	Columbus Day: college is closed - no class! Lecture 10. Building &Using the Linked List Toolkit (code) & Exam 1 Discussions	Ch. 5.3 - 5.5, Assignment 4
Oct 19 (M) Oct 21 (W)	Lecture 11. Software Development using Templates and Iterators Lecture 11a. Software Development using Templates and Iterators (cont.)	Ch. 6, code (bag4&5, node2)
Oct 26 (M) Oct 28 (W)	Lecture 12. Stacks (code) and Queues (code) Lecture 13. Introduction to Recursion	Ch. 7, Ch 8 Ch. 9.1, Assignment 5
Nov 02 (M) Nov 04 (W)	Lecture 14. Using and Reasoning about Recursion Exam Review 2	Ch. 9.2 - 9.3
Nov 09 (M) Nov 11 (W)	Second Exam (Chapters 5-9) Lecture 15. Trees and Traversals (code)	Ch. 10.1-10.4
Nov 16 (M) Nov 18 (W)	Lecture 16. Binary Search Trees and the Bag Class with a BST Lecture 17. B-Trees and Set Class (code); Exam 2 Discussions	Ch. 10.5, Assignment 6 Ch. 11.2
Nov 23 (M) Nov 25 (W)	Lecture 18. Heaps and Priority Queues(slides) ; Time Analysis of Trees(slides) Lecture 19. Serial Searching and Binary Searching	Ch. 11.1, 11.3 Ch. 12.1-12.3
Nov 30 (M) Dec 02 (W)	Lecture 20. Hashing; Lecture 21. Quadratic Sorting	Ch. 12.4 Ch. 13.1
Dec 07 (M) Dec 09 (W)	Lecture 22. Recursive Sorting , Heapsort & the STL Quicksort (code) Lecture 23. Graph Basics; Exam Review 3 - Slides Updated to This Point	Ch. 13.2-13.4 Ch. 15
Dec 14 (M)	Third Exam (mainly Ch 10-13, 15), SH-308

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 individually 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.