Data Structures – Spring 2021
CSc21200 Section EF Data Structures, Spring 2021, The City College of New York
|Professor Zhigang Zhu|
Online (Class Zoom Link)
Wednesday: 4:00 pm – 5:00 pm
Online Meeting (Office Hour Zoom Link)
Assignment Submission: firstname.lastname@example.org
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.
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…
Time analysis techniques
Pointers and dynamic arrays
Templates and iterators
Stacks & Queues
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 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 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 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
|Mar 01 (M)|
Mar 03 (W)
|Exam Review 1 – Slides only updated to this point|
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)
|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 & Exam 1 Discussion |
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.
|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.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.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.
|Lecture 20.Hashing (slides)|
Lecture 21. Quadratic Sorting
|May 10 (M)|
|Lecture 22. Recursive Sorting , Heapsort & the STL Quicksort (code)|
Lecture 23. Graph Basics; Exam Review 3 (slides)
|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.
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.