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
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.

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:

DatePlanned Lecture TopicsRead/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    – Slides Updated to This Point
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&5node2)
Mar 16 (M)
Mar 18 (W)
Lecture 11a. Software Development using Templates and Iterators (cont.) 
Lecture 12. Stacks (code) and Queues (code)  

Ch. 7, Ch 8 
Mar 23 (M)
Mar 25 (W)
Lecture 13. Introduction to Recursion
Lecture 14. Using and Reasoning about Recursion
Ch. 9.1, Assignment 5
Ch. 9.2 – 9.3
Mar 30 (M)
Apr 01 (W)
Exam Review 2 
Second Exam 
(Chapters 5-9)

Apr 06 (M)
Apr 07 (T)
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 13 (M)
Apr 15 (W)
Spring Recess: April 08 – April 16 
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
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
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.