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 

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:

DatePlanned Lecture TopicsRead/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 – 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&5node2)
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.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 (slides)
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;  Exam Review 3 (slides)
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.