Data Structures – Spring 2020

CSc21200 Section EF Data Structures, Spring 2020, The City College of New York

Class Meets:

Office Hours:

Professor Zhigang  Zhu
M,W  2:00-3:40PM
Shepard S-209
Wednesday:  4:00 pm – 5:30 pm
8/211 (Online meeting Zoom Link)
Assignment Submission:

Course Update Information 

  • 01/27/2020. The first day of class
  • 02/12/2020. Grading for quizzes 1 and 2.
  • 02/20/2020. Grading for Assignment 1.
  • 02/25/2020. Grading for quizzes 1 to 3.
  • 02/27/2020. Grading for Assignments 1 and 2.
  • 03/06/2020. Grading for quizzes 1 to 3.
  • 03/06/2020. Grading for Exam 1. We will discuss the exam on Monday
  • 03/18/2020. Grading for quizzes 1 to 5.
  • 03/18/2020. Grading for Assignments 1 to 3.
  • 03/25/2020. Grading for quizzes 1 to 6.
  • 03/26/2020. Note that we will enter the recalibration period 03/27 – 04/01 and distance learning will resume on 04/02, and we will use Zoom (a Google calendar reminder with the meeting link has sent to every student. Please let me know if you haven’t received it). As a result of this, the second exam will be pushed to 04/07. Hope this is good news for some of you. Note this is a Tuesday running Wednesday schedules. The spring break will be cut short to three days from 04/08 to 04/10. See the following for the updated schedule of the class.
  • 03/27/2020.Grading for Assignments 1 to 4.
  • 04/15/2020. Grading for quizzes 1 to 7.
  • 04/15/2020. Grading for Exams 1 and 2. We will discuss Exam 2 on Monday April 20.
  • 04/22/2020. Grading for quizzes 1 to 8.
  • 04/24/2020.Grading for Assignments 1 to 5.
  • 04/29/2020. Grading for quizzes 1 to 9.
  • 05/08/2020.Grading for Assignments 1 to 6.
  • 05/12/2020. Grading for quizzes 1 to 12.
  • 05/23/2020. Final Grading will be submitted to CUNYFirst on Monday 05/25/2020.

Course Objectives

This course teaches the basic techniques to organize data in running programs.  You will know about well-known data structures as listed in the Quick Syllabus:

To become a Data Structures Expert 
start by learning…
Pre-condition/Post-condition specifications 
Time analysis techniques 
Container classes 
Pointers and dynamic arrays 
Linked lists 
Templates and iterators 
Stacks & Queues 
Recursive thinking 
Sorting and searching techniques 

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.

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.


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.


The following schedule is based on Spring 2020 academic calendar:

DatePlanned Lecture TopicsRead/Assign/Exam
Jan 27 (M)
Jan 29 (W)
Lecture 1. Introduction & Software Development
Lecture 2. ADT & C++ Classes (code)  
Ch. 1
Ch 2.1-2.3;  Assignment 1
Feb 03 (M )
Feb 05 (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 10 (M)
Feb 12 (W) 
Lecture 6. Pointers and Dynamic Arrays (I)   (Slides for Lectures 6 &7)
College is closed – no class!
Ch 4.1 – 4.2
Feb 17 (W)
Feb 19 (W)
College is closed – no class!
Lecture 7. Pointers and Dynamic Arrays (II) (point code with pointers)

Ch. 4.2 – 4.5
Feb 24 (M)
Feb 26 (W)
Lecture 8. Dynamic Classes and the Big Three (code)  
Exam Review 1   
Assignment 3
Mar 02 (M)
Mar 04 (W)
First Exam (Chapters 1-4)
Lecture 9.  Linked Lists ( code

Ch. 5.1-5.2, Assignment 4
Mar 09 (M)
Mar 11 (W)
Lecture 10. Building &Using the Linked List Toolkit  (code)  & Exam 1 Discussion
Lecture 11. Software Development using Templates and Iterators   
Ch. 5.3 – 5.5
Ch. 6,  code (bag4&5node2)
Mar 16 (M)
Mar 18 (W)
Instruction recess week so no class meets.
But we will try out the online learning tools 03/16.
Please study the iterators of Lecture 11 at home.

Mar 23 (M)
Mar 25 (W)
Lecture 12. Stacks (code) and Queues (code)  
Lecture 13. Introduction to Recursion
Ch. 7, Ch 8 
Ch. 9.1, Assignment 5
Mar 30 (M)
Apr 01 (W)
CUNY Recalibration Period. No classes.
You may use this time to do Assignment 5 and the review for Exam 2.

Apr 06 (M)
Apr 07 (T)
Lecture 14. Using and Reasoning about Recursion & Exam Review 2 
Second Exam 
(Chapters 5-9)
(Spring Recess: April 08 – April 10 only)
Ch. 9.2 – 9.3
Apr 13 (M)
Apr 15 (W)
 Lecture 15. Trees and Traversals  (code)
Lecture 16. Binary Search Trees and the Bag Class with a BST
Ch. 10.1-10.4
Ch. 10.5, Assignment 6
Apr 20 (M)
Apr 22 (W)
Lecture 17. B-Trees and Set Class (code); Exam 2 Discussions
Lecture 18. Heaps and Priority Queues(slides) ; Time Analysis of Trees(slides)
Ch. 11.2
Ch. 11.1, 11.3
Apr 27 (M)
Apr 29 (W)
Lecture 19. Serial Searching and Binary Searching.
Lecture 20. Hashing / Course and Intern Reflection by Naman Pujari (CpE) (slides)
Ch. 12.1-12.3
Ch. 12.4
May 04(M)
May 06(W)
Lecture 21. Quadratic Sorting
Lecture 22. Recursive Sorting , Heapsort & the STL Quicksort (code)
Ch. 13.1
Ch. 13.2-13.4
May 11 (M)
May 13(W)
Lecture 23. Graph Basics;  Exam Review 3 (slides) – Slides Updated to This Point
Third Exam
 (mainly Ch 10-13, 15) [Following a Monday Schedule]
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.