Computer Science City College of New York
  CSc21200 Section RS Data Structures, Spring 2010
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
TH        02:00-03:30 PM
NAC-8/210
zhu@cs.ccny.cuny.edu
  

Course Update Information 

 

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

    Date Planned Lecture Topics Readings/Assignments
    Jan 28 (Th)
    		 Lecture 1. Introduction & Software Development
    		Ch. 1
    Feb 02 (T)
    Feb 04 (Th)     		 Lecture 2. ADT & C++ Classes  (code) 
    Lecture 3. More Classes and Operator Overloading  
    		Ch 2.1-2.3;  Assignment 1
    Ch 2.4-2.5
    Feb 09 (T )
    Feb 11 (Th)     		 Lecture 4.  Container Classes (slides for Lectures 4&5)
    Lecture 5. Container Classes (cont.)
    		Ch 3 (code)
    Ch 3, Assignment 2
    Feb 16 (T)
    Feb 18 (M)     		 Lecture 6. Pointers and Dynamic Arrays (I)   (slides for Lectures 6 &7)
     Monday schedule    		 Ch 4.1 - 4.2

    Feb 23 (T)
    Feb 25 (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 02 (T)
    Mar 04 (Th)     		 Exam Review 1
    First Exam (Chapters 1-4)


    Mar 09 (T)
    Mar 11 (Th)     		 Lecture 9.  Linked Lists ( code)  & Exam Discussions
    Lecture 10. Building &Using the Linked List Toolkit  (code)
    		Ch. 5.1-5.2
    Ch. 5.3 - 5.5, Assignment 4
    Mar 16 (T)
    Mar 18 (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 23 (T)
    Mar 25 (Th)     		 Lecture 12. Stacks (code) and Queues (code)
    Lecture 13. Introduction to Recursion 
    		Ch. 7, Ch 8
    Ch. 9.1 , Assignment 5   
    Mar 29 -
    Apr 05
    		Spring Recess

    Apr 06 (T)
    Apr 08 (Th)     		 Lecture 14. Using and Reasoning about Recursion
    Exam Review 2 ; Assignment Discussions
         		Ch. 9.2 - 9.3
    Apr 13 (T)
    Apr 15 (Th)     		 Second Exam (Chapters 5-9)
    Lecture 15. Trees and Traversals  (code); Exam 2 discussions
    Ch. 10.1-10.4
    Apr 20 (T)
    Apr 22 (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 27 (T)
    Apr 29 (Th)    		 Lecture 18. Heaps and Priority Queues ; Lecture 18a Time Anaysis of Trees
    Lecture 19. Searching  & Lecture 20. Hashing
    		 Ch. 11.1, 11.3
    Ch. 12.1-12.4
    May 04 (T)
    May 06 (Th) 
    		 Lecture 21. Quadradic Sorting
    Lecture 22. Recusive Sorting , Heapsort & the STL Quicksort (code)
    		 Ch. 13.1
    Ch. 13.2-13.4
    May11 (T)
    May 13 (Th)
    		 Lecture 23. Graphs; Exam Review 3
    Final Exam (mainly Ch 10-13)





    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.

    Copyright @ Zhigang Zhu, City College of New York, Spring 2010.