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

Instructors
Name:
Office:
Email:
Office Hours:		 Prof  Zhigang  Zhu 
NAC 8/203
zhu@cs.ccny.cuny.edu
Tue  4:00-6:00 pm		    


NOTE: THIS IS THE OLD PAGE for FALL 2002.


Course Update Information  (Bulletin Board )

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

    Date Planned Lecture Topics Read/Assign/Exam
    Sep 3 (Tu) 
    Sep 5 (Th)     		 Lecture 1. Introduction & Software Development (printable handout ) 
    Lecture 2. ADT & C++ Classes ( printable handout )    		 Ch. 1
    Ch 2.1-2.3;  Assignment 1
    Sep 10 (Tu)
    Sep 12 (Th)     		 Lecture 3. More Classes and Operator Overloading(printable handout )
    Lecture 4. Container Classes (printable handout)    		 Ch 2.4-2.5 (code)
    Ch 3 (code)
    Sep 17 ( x )
    Sep 19 (Th)     		 Monday schedule
    Lecture 5.  Container Classes (cont.), A Quiz
    Ch 3,  Assignment 2
    Sep 24 (Tu)
    Sep 26 (Th)     		 Lecture 6. Reviews; Pointers and Dynamic Arrays (I) (printable handout)
    Lecture 7. Pointers and Dynamic Arrays (II)
    Ch 4.1 - 4.2
    Oct 1 (Tu)
    Oct 3 (Th)     		 Lecture 8. Dynamic Classes and the Big Three (printable handout)  (code)
    Exam review 1
    Ch. 4.2 - 4.5, Assignment 3
    Oct 8 (Tu)
    Oct 10 (Th)     		 First Exam (Chapters 1-4) 
    Lecture 9.  Linked Lists ( notes and code)
    Ch. 5.1-5.2
    Oct 15 (Tu)
    Oct 17 (Th)     		 Lecture 10. Building &Using the Linked List Toolkit  (notes and code)
    Lecture 11. Software Development using Templates and Iterators (notes)    		 Ch. 5.3 - 5.5 , Assignment 4
    Ch. 6,  code (bag4&5, node2)
    Oct 22 (Tu)
    Oct 24 (Th)     		 Lecture 12. Stacks (code) and Queues (code) 
     Lab: Template, Compiling, Inlcude, Link, etc    		  Ch. 7, Ch 8 
    Oct 29 (Tu)
    Oct 31 (Th)     		 Lecture 13. Introduction to Recursion (notes) 
    Lecture 14. Using and Reasoning about Recursion (notes)    		 Ch. 9.1
    Ch. 9.2 - 9.3, Assignment 5
    Nov 5 (Tu)
    Nov 7 (Th)     		 Review for Exam 2 (notes) and Discussions for Exam 1
    Second Exam (Chapters 5-9)
    Nov 12 (Tu)
    Nov 14 (Th)     		 Lecture 15. Trees and Traversals (notes)  (code)
    Lecture 16. Binary Search Trees and the Bag Class with a BST  (notes)    		 Ch. 10.1-10.4 
    Ch. 10.5, Assignment 6
    Nov 19 (Tu)
    Nov 21 (Th)     		 Lecture 17. Heaps and Priority Queues (notes) 
    Lecture 18. B-Trees and Set Class(notes)(code);  Time Anaysis of Trees(notes)    		 Ch. 11.1, 11.3
    Ch. 11.2 
    Nov 26(Tu)
    Nov 28 ( x )     		 Lecture 19. Searching (notes)
    Thanksgiving Holiday    		 Ch. 12.1-12.2
    Relax !
    Dec 3 (Tu)
    Dec 5 (Th)    		 Lecture 20. Hashing (1.1M PPT file!)
    Lecture 21. Quadradic Sorting     		 Ch. 12.2-12.4
    Ch. 13.1 
    Dec 10 (Tu)
    Dec 12 (Th)     		 Lecture 22. Recusive Sorting , Heapsort & the STL Quicksort (notes) (code)
    Exam review 3    		 Ch. 13.2-13.4
    Dec 18 (Wed) Final exam (mainly Chap 10-13)  NAC 6/111, 1:10 - 3:30 pm
    Notes:
    1: No classes on 9/17 (Tu) and 11/28 (Th).
    2. Most of the lectures have reading assignments that you should complete before the lecture
    3. Warning: The lecture handouts are in both B_W (link at printable handout) and in color with a blue background (link Lecture ##). It may be very problematic when you try to print out the color versions.

    Assignments and Grading

    We will meet Tue and Thu 2:00-3:40 pm at NAC 6/327. See syllabus below for the tentative timetable for a schedule. There will be six to seven programming assignments distributed roughly every two weeks (counted roughly 60% 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 (30% 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: This is my first time to teach this course but 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 CCNY's Steinman 405,  NAC 7/118 and NAC 7/105 labs. The labs have the following schedule:

    T 405 and NAC 7/105 lab
        Monday through Thursday - 11:00 am - 9:00 pm
        Friday through Sunday   - 11.00 am - 7:00 pm

    NAC 7/118
        Monday through Friday   - 11.00 am - 7:00 pm

    The computer labs will open from September 4, 2002 to December 20, 2002.


    @Zhigang Zhu (email zhu@cs.ccny.cuny.edu ) August 2002. This page was mainly adapted from the Data Structures course web page of Prof. Akira Kawaguchi at CCNY (2001), and partly from those of Prof. Sam Fenster at CCNY (2001) and Prof. Michael Main at University of Colorado at Boulder (2000).