Data Structures – Spring 2021
CSc21200 Section EF Data Structures, Spring 2021, 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 Online (Class Zoom Link) Wednesday: 4:00 pm – 5:00 pm Online Meeting (Office Hour Zoom Link) Appointments: zzhu@ccny.cuny.edu Assignment Submission: ds.zhu.ccny@gmail.com |
Course Update Information
- 02/01/2021. The first day of class
- 02/01/2021. Grading for Quiz 1.
- 02/08/2021. Grading for Quizzes 1-2.
- 02/11/2021. Updated Grading for Quizzes 1-3.
- 02/16/2021. Grading for Assignment 1.
- 02/07/2021. Grading for Quizzes 1-4.
- 03/01/2021. Grading for Assignments 1-2.
- 03/06/2021. Grading for Exam 1. We will discuss this exam on Wed 03/10 in class.
- 03/09/2021. Grading for Quizzes 1-6.
- 03/18/2021. Grading for Assignments 1-3.
- 03/18/2021. Grading for Exam 1 and Bonus .
- 03/18/2021. Grading for Quizzes 1-7.
- 03/23/2021. Grading for Quizzes 1-8.
- 03/30/2021. Grading for Assignments 1-4.
- 03/30/2021. Grading for Exam 1 and Updated Bonus .
- 04/13/2021. Grading for Assignments 1-5 (updated).
- 04/15/2021. Grading for Exams 1-2 and Bonus .
- 04/21/2021. Grading for Quizzes 1-9.
- 05/03/2021. Grading for Quizzes 1-11.
- 05/06/2021. Grading for Assignments 1-6.
- 05/06/2021. Grading for Quizzes 1-12.
- 05/09/2021. Grading for Exams 1-2, Quiz Total So Far, Bonus and Extra Points. See comments by clicking the link. We will have two more quizzes (with a total of 14).
- 05/12/2021. Grading for Quizzes 1-14.
- 05/12/2021. Grading for Exams 1-2, Quiz Total So Far, Bonus and Extra Points Updated.
- 05/21/2021. Final Grading The grades will be uploaded to CUNYFirst on Tuesday 05/25/2021.
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 2021 academic calendar:
| Date | Planned Lecture Topics | Read/Assign/Exam |
| Feb 01 (M) Feb 03 (W) | Lecture 1. Introduction & Software Development Lecture 2. ADT & C++ Classes (code) | Ch. 1 Ch 2.1-2.3; Assignment 1 |
| Feb 08 (M ) Feb 10 (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 15 (M) Feb 17 (W) | College is closed – no class! Lecture 6. Pointers and Dynamic Arrays (I) (Slides for Lectures 6 &7) | Ch 4.1 – 4.2 |
| Feb 22 (M) Feb 24 (W) | 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 01 (M) Mar 03 (W) | Exam Review 1 First Exam (Chapters 1-4) | |
| Mar 08 (M) Mar 10 (W) | Lecture 9. Linked Lists ( code) Lecture 10. Building &Using the Linked List Toolkit (code) & Exam 1 Discussion | Ch. 5.1-5.2, Assignment 4 Ch. 5.3 – 5.5 |
| Mar 15 (M) Mar 17 (W) | Lecture 11. Software Development using Templates and Iterators Lecture 12. Stacks (code) and Queues (code) | Ch. 6, code (bag4&5, node2) Ch. 7, Ch 8 |
| Mar 22 (M) Mar 24 (W) | Lecture 13. Introduction to Recursion Lecture 14. Using and Reasoning about Recursion | Ch. 9.1, Assignment 5 Ch. 9.2 – 9.3 |
| Mar 29 (M) Mar 31 (W) | Spring Recess 03/27-04/04. No classes. You may use this time to do Assignment 5 and the Review for Exam 2. You are strongly encouraged to work through the problems before the second exam on April 07, 2020 | |
| Apr 05 (M) Apr 07 (W) | Exam Review 2 Second Exam (Chapters 5-9) | |
| Apr 12 (M) Apr 14 (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 19 (M) Apr 21 (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 26 (M) Apr 28 (W) | Lecture 18 (II). Time Analysis of Trees(slides); Exam 2 Discussions Lecture 19. Serial Searching and Binary Searching. | Ch. 12.1-12.3 |
| May 03(M) May 05(W) | Lecture 20.Hashing Lecture 21. Quadratic Sorting | Ch. 12.4 Ch. 13.1 |
| May 10 (M) May 12(W) | Lecture 22. Recursive Sorting , Heapsort & the STL Quicksort (code) Lecture 23. Graph Basics; The Final Quiz (questions); Exam Review 3 (slides) – Slides only updated to this point | Ch. 13.2-13.4 Ch. 15 |
| May 17 (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.