Data Structures – Spring 2020
CSc21200 Section EF Data Structures, Spring 2020, 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-209 Wednesday: 4:00 pm – 5:30 pm NAC 8/211 (Online meeting Zoom Link) Appointments: zzhu@ccny.cuny.edu Assignment Submission: ds.zhu.ccny@gmail.com |
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 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 2020 academic calendar:
| Date | Planned Lecture Topics | Read/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&5, node2) |
| 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.