Data Structures – Spring 2023

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

Instructor: 
TA
Class Meets:
Classroom:

Office Hours:
Office:

Email:
Professor Zhigang  Zhu
n/a
M,W  2:00-3:40PM
Shepard S-204 (Class Zoom Link when needed)
Thursday:  2:00 pm – 4:00 pm
Online Meeting (Office Hour Zoom Link
)
Appointmentszzhu@ccny.cuny.edu
Assignment Submission: ds.zhu.ccny@gmail.com

Course Update Information 

  • 01/25/2023. The first day of class.
  • Grading for Quiz 1.
  • Grading for Quiz 1 & 2.

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 
Trees 
Sorting and searching techniques 
Graphs

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.

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

Assignments and Grading

DatePlanned Lecture TopicsReadings/Assignments
Jan 25 (W)Lecture 1. Introduction & Software DevelopmentCh. 1
Jan 30 (M)
Feb 01 (W)
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 06 (M )
Feb 08 (W) 
Lecture 4/5.  Container Classes (slides for Lectures 4&5)
Lecture 6. Pointers and Dynamic Arrays (I)   (Slides for Lectures 6 &7)
Ch 3 (code), Assignment 2
Ch 4.1 – 4.2
Feb 13 (M)
Feb 15 (W) 
College is closed – no class!
Lecture 7. Pointers and Dynamic Arrays (II) (point code with pointers)
Feb 21 (T)
Feb 22 (W)
Lecture 8. Dynamic Classes and the Big Three (code)  
Exam Review 1
Ch. 4.2 – 4.5, Assignment 3
Feb 27 (M)
Mar 01 (W)
First Exam (Chapters 1-4)
Lecture 9.  Linked Lists ( code

Ch. 5.1-5.2, Assignment 4
Mar 06 (M)
Mar 08 (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 13 (M)
Mar 15 (W)
Lecture 12. Stacks (code) and Queues (code)  [recorded video]
Lecture 13. Introduction to Recursion [recorded video]
Ch. 7, Ch 8 
Ch. 9.1, Assignment 5
Mar 20 (M)
Mar 22 (W)
Lecture 14. Using and Reasoning about Recursion (via Zoom)
Exam Review 2 
Ch. 9.2 – 9.3
Mar 27 (M)
Mar 29 (W)
Second Exam (Chapters 5-9) (via Zoom)
Lecture 15. Trees and Traversals  (code)

Ch. 10.1-10.4
Apr 03 (M)
Apr 05 (W)
Lecture 16. Binary Search Trees and the Bag Class with a BST; Exam 2 Discussions
Spring Recess 04/05-04/13. No classes.
Ch. 10.5, Assignment 6
Apr 10 (M)
Apr 12 (W)
Spring Recess 04/05-04/13. No classes.

Apr 17 (M)
Apr 19 (W)
Lecture 17. B-Trees and Set Class (code)
Lecture 18(I). Heaps and Priority Queues(slides)
Ch. 11.2
Ch. 11.1, 11.3
Apr 24 (M)
Apr 26 (W)
Lecture 18(II) Time Analysis of Trees(slides) (via Zoom)
Lecture 19. Serial Searching and Binary Searching.

Ch. 12.1-12.3
May 01(M)
May 03(W)
Lecture 20.Hashing (via Zoom)
Lecture 21. Quadratic Sorting (via Zoom)
Ch. 12.4
Ch. 13.1
May 08 (M)
May 10(W)
Lecture 22. Recursive Sorting , Heapsort & the STL Quicksort (code)
Lecture 23. Graph Basics;  The Final Quiz (questions); Exam Review 3 (slides) (via Zoom)
Ch. 13.2-13.4
Ch. 15
May 15 (M)Third Exam (mainly Ch 10-13, 15)
  • See syllabus above for the tentative timetable for a schedule. There will be six programming assignments distributed roughly every two weeks (counted 30% of your final grade).  Several in-class small quizzes will add up to at least 10 % of your final grade. There will be three in-class close-book exams (60% of your final grade). Dates of these exams will be determined in due times and announced beforehand.
  • Policies:  For the program assignments, 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. All the three exams will be close-book exams. You will need to clear state that you will neither give nor receive unauthorized assistance on any of the exams.

We fully support CUNY’s policy on Academic Honesty, which states, in part:

Academic dishonesty is unacceptable and will not be tolerated. Cheating, forgery, plagiarism, and collusion in dishonest acts undermine the CUNY’s educational mission and the students’ personal and intellectual growth. Students are expected to bear individual responsibility for their work, to learn the rules and definitions that underlie the practice of academic integrity, and to uphold its ideals. Ignorance of the rules is not an acceptable excuse for disobeying them. Any student who attempts to compromise or devalue the academic process will be sanctioned.

Academic sanctions in this class will range from an F on an assignment to an F in this course.

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