Computer Science City College of New York
  CSc21200 Section EF Data Structures, Spring 2018
Instructor: 
TA
Class Meets:
Classroom:
Office Hours:
Office:
Email:
 Professor Zhigang  Zhu
n/a
M,W        2:00-3:40PM
Shepard S-209
Monday:  11:30 am - 1:30 pm
NAC 8/211
ds.zhu.ccny@gmail.com
  

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

    Supplements:  The Code for the Book and the Corrections for the Text will be useful and may be found by clicking here.

    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.  You should be familiar with some programming environment--either a PC or a Linux system.

    Schedule

    The following schedule is based on Spring 2018 academic calendar:

    Date Planned Lecture Topics Read/Assign/Exam
    Jan 29 (M)
    Jan 31 (W)    		 Lecture 1. Introduction & Software Development
    Lecture 2. ADT & C++ Classes  (code)       		Ch. 1
    Ch 2.1-2.3;  Assignment 1
    Feb 05 (M )
    Feb 07 (W) 
    		Lecture 3. More Classes and Operator Overloading
    Lecture 4/5.  Container Classes (slides for Lectures 4&5)     		Ch 2.4-2.5
    Ch 3 (code), Assignment 2
    Feb 12 (M)
    Feb 14 (W)     		 Lincoln's Birthday; college is closed - no class!
    Lecture 6. Pointers and Dynamic Arrays (I)   (Slides for Lectures 6 &7) 
    Ch 4.1 - 4.2
    Feb 20 (T)
    Feb 21 (W)    		 Monday Schedule: 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
    Feb 26 (M)
    Feb 28 (W)    		 Exam Review 1   
    First Exam (Chapters 1-4)

    Mar 05 (M)
    Mar 07 (W)     		 Lecture 9.  Linked Lists ( code)  & Exam 1 Discussions
    Lecture 10. Building &Using the Linked List Toolkit  (code) 
    		Ch. 5.1-5.2
    Ch. 5.3 - 5.5, Assignment 4
    Mar 12 (M)
    Mar 14 (W)
    		Lecture 11. Software Development using Templates and Iterators
    Career Workshop by Ms Rhea Faniel (mandatory, class attendance will be taken)
    		Ch. 6,  code (bag4&5, node2)

    Mar 19 (M)
    Mar 21 (W)
    		 Lecture 12. Stacks (code) and Queues (code)  
    Exam Review 2 (no class meet - snow storm)
    		Ch. 7, Ch 8 
     Assignment 5
    Mar 26 (M)
    Mar 28 (W)     		Lecture 13. Introduction to Recursion
    Lecture 14. Using and Reasoning about Recursion      		Ch. 9.1
    Ch. 9.2 - 9.3
    Apr 02 (M)
    Apr 04 (W)     		 
    Spring Recess March 30 - April 08
    Apr 09 (M)
    Apr 11 (W)     		 Second Exam (Chapters 5-9)
    Classes to follow Friday schedule


    Apr 16 (M)
    Apr 18 (W)     		 Lecture 15. Trees and Traversals  (code)
    Lecture 16. Binary Search Trees and the Bag Class with a BST; Exam 2 Discussions    		 Ch. 10.1-10.4
    Ch. 10.5, Assignment 6
    Apr 23 (M)
    Apr 25 (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
    Apr 30 (M)
    May 02 (W)
    		 Lecture 19. Serial Searching and Binary Searching. 
    Lecture 20. Hashing
    		Ch. 12.1-12.3
    Ch. 12.4
    May 07 (M)
    May 09 (W)
    		Lecture 21. Quadratic Sorting
    Lecture 22. Recursive Sorting , Heapsort & the STL Quicksort (code)
    		 Ch. 13.1
    Ch. 13.2-13.4
    May 14 (M)
    May 16(W)
    		 Lecture 23. Graph Basics;   Exam Review 3 - Slides Updated to This Point
    Third Exam     (mainly Ch 10-13, 15)     		Ch. 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 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.

    Copyright @ Zhigang Zhu, City College of New York, Spring 2018