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) Appointments: zzhu@ccny.cuny.edu Assignment Submission: ds.zhu.ccny@gmail.com |
Course Update Information
- 01/25/2023. The first day of class.
- 01/25/2023. Grading for Quiz 1.
- 01/30/2023. Assignment 1 online.
- 02/01/2023. Grading for Quizzes 1 & 2.
- 02/06/2023. Grading for Quizzes 1 to 3.
- 02/06/2023. Assignment 2 online.
- 02/07/2023. Grading for Extra Points.
- 02/15/2023. Assignment 3 online.
- 02/09/2023. Grading for Quizzes 1 to 4.
- 02/13/2023. Grading for Assignment 1.
- 02/13/2023. Updated Grading for Extra Points.
- 02/20/2023. Grading for Assignments 1-2.
- 02/22/2023. Grading for Quizzes 1 to 5.
- 03/02/2023. Grading for Exam 1 and Extra Points. We will discuss Exam 1 in class on Monday 03/06/2023. Please do attend the class.
- 03/02/2023. Grading for Quizzes 1 to 6.
- 03/09/2023. Grading for Assignments 1-3.
- 03/21/2023. Grading for Quizzes 1 to 8.
- 03/23/2023. Grading for Quizzes 1 to 9.
- 03/23/2023. Grading for Assignments 1-4.
- 03/29/2023. Grading for Exams 1-2 and Extra Points. We will discuss Exam 2 in class on Monday 04/03/2023. Please do attend the class.
- 04/11/2023. Grading for Assignments 1-5.
- 04/20/2023. Grading for Quizzes 1 to 10.
- 04/27/2023. Grading for Quizzes 1 to 11.
- 05/02/2023. Grading for Assignments 1-6.
- 05/02/2023. Grading for Quizzes 1 to 13.
- 05/03/2023. Grading for Exams 1-2, Bonus and Extra Points. Bonus = (max(0, (E3-E2))+max(0,(E2-E1)))/5: for performance increase between consecutive exams: Every 5-point increase gains 1 bonus point; no penalty if performance is decreased; but you have to take all the three exams.
- 05/03/2023. Grading for Quizzes 1 to 14.
- 05/09/2023. Grading for Quizzes 1 to 15.
- 05/10/2023. Grading for Quizzes 1 to 16.
- 05/18/2023. Final Grading (updated on 5/22) will be submitted on Wednesday May 24 , 2023. Have a great summer!
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:
| Date | Planned Lecture Topics | Readings/Assignments |
| Jan 25 (W) | Lecture 1. Introduction & Software Development | Ch. 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) [recorded video] | Assignment 3 |
| Feb 21 (T) Feb 22 (W) | Lecture 8. Dynamic Classes and the Big Three (code) Exam Review 1 | Ch. 4.2 – 4.5 |
| 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&5, node2) |
| Mar 13 (M) Mar 15 (W) | Lecture 12. Stacks (code) and Queues (code) – No class meet, please view the [recorded video] Lecture 13. Introduction to Recursion – No class meet, please view the [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 (in-person) | Ch. 9.2 – 9.3 |
| Mar 27 (M) Mar 29 (W) | Second Exam (Chapters 5-9) (via Zoom) Lecture 15. Trees and Traversals (code) (via Zoom) | 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. No class meet, please view the [recorded video] 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) |
Assignments and Grading
- 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.