Data Structures    CSCI 106, Spring 2017

 

To the Bottom of the Page

 

Instructor:  Professor Grace Lew

Class:  MW at LIB 141, Section #1: 10:30-11:45am, Section #2: 12:00-1:15pm

Professor Lew Office Hours: M~TH 2:00-4:00pm

 

TA hours (MATH/CS lab in Grove 10):

Jarvis Flores - T&R 10:30-11:30AM         Willy Hung - W 1:30-3:30PM

 

Course Syllabus: compact version

 

*************************************************************************************************

About programming:

·       New and Important: Read the new CSCI 106 integrity rules and grading policies for programming assignments about test cases and peer review required in the self-evaluation report for each programming assignment.

·       More about test cases and peer review: See these notes from the TAs last year.

·       Useful links: See how to compile your C++ programs and a sample compressed Visual C++ project folder from CSCI 105. You can download, install, and register Microsoft Visual C++ 2013 Express Edition for free.

 

About the reading reports:

·    Effort (2 points): How much time have you spent for the reading? What percentage of the contents in the reading do you think you understand? Have you come to the class this week?  Assessment: The student is expected to (i) have attended the class this week at least once (0.5 point), and(ii) have either gained a good understanding of 80% or more of the contents or have spent at least three hours in the reading (1.5 points).

·    Reflection on the reading (2 points): Put down 1~2 paragraphs of your thoughts such as notes of new insight you gained, interesting things encountered, questions of things you don’t understand,  and so forth.  Assessment: the student is expected to show substantial evidence of understanding or effort of trying to understand the contents in the reading.

 

**************************************************************

 

Week 1: Intro to the very basics of object-oriented programming

 

Reading #1: Reading report due Wednesday Feb. 8

·       Read Sections 13.1~13.8 in Starting out with C++ on the basics of objects and classes.

·       Send in your reading report through Biola Canvas.

 

Programming#1A Submission due Wednesday Feb. 8

·       Highlight: Create your own user-defined DateType class.

·       Very important notes: (i) CSCI 106 integrity rules and grading policy for programming assignments, (ii) self-evaluation report, and (ii) TAs’ note on testing last year.

·       Submission: (i) Compress your entire Program 1A folder into a zip file and upload it through Biola Canvas. (ii) Carefully fill out this self-evaluation report and upload it through Biola Canvas. Note that you will receive no point for missing the self-evaluation report or missing the integrity review in the report.

 

**************************************************************

 

Week 2: More about the basics of object-oriented programming

 

Reading #2: Reading report due Wednesday Feb.15

·       Review Sections 13.1~13.8 in Starting out with C++ as needed.

·       Read 13.9~13.16 (the section on UML is optional) in Starting out with C++ on the basics of objects and classes.

·       Send in your reading report through Biola Canvas.

 

Programming#1B (Enhance your own user-defined DateType class and make it robust):  Submission due Wednesday Feb.15

·       Highlight: Enhance your own user-defined DateType class.

·       Very important notes: (i) CSCI 106 integrity rules and grading policy for programming assignments, (ii) self-evaluation report, and (ii) TAs’ note on testing last year.

·       Submission: (i) Compress your entire Program 1B folder into a zip file and upload it through Biola Canvas. (ii) Carefully fill out this self-evaluation report and upload it through Biola Canvas. Note that you will receive no point for missing the self-evaluation report or missing the integrity review in the report.

 

**************************************************************

 

Week 3: More about C++ classes: operator overloading and friends

Reading #3: due Wednesday Feb.22

·       Read Sections 14.1-14.5 in Starting out with C++, especially Section 14.2 on friends of a class, and Section 14.5 on operator overloading.

·       Review Reading #1 and #2, especially Section 13.10 on constructor overloading and Section 13.11 on private member functions in Starting out with C++.

 

**************************************************************

 

Week 4: Reference types, reference parameters, and the const quantifier

Reading #4: Due: Wednesday March 1

·       Read the following sections in C++ Primer: (i) Section 2.3.1 on reference types, (ii) Section 2.4 from page 59 up to the end of Section 2.4.1 on const, and (iii) Sections 6.2.1~6.2.3 on argument passing mechanisms (passing by value vs passing by reference) in C++.

 

Programming#2: Submission due Wednesday March 1

·       Highlight: Enhance the DateType class to support relational operators, arithmetic operators, and input/output operators.

·       Very important notes: (i) CSCI 106 integrity rules and grading policy for programming assignments, (ii) self-evaluation report, and (ii) TAs’ note on testing last year.

·       Submission: (i) Compress your entire Program 2 folder into a zip file and upload it through Biola Canvas. (ii) Carefully fill out this self-evaluation report and upload it through Biola Canvas. Note that you will receive no point for missing the self-evaluation report or missing the integrity review in the report.

 

**************************************************************

 

Week 5: Recursion and merge sort using vectors

 

Reading#5, Due: Wednesday, Mar. 8

·       Very carefully read the description of mergeTwoSortedVectors and mergeSort in Programming#3.

·       Read Chapter 19 on recursion in Starting out with C++.

·       Read Section 7.12 on the STL vector class and Section 10.7 on the C++ string class in Starting out with C++.

·       Read the MSDN sample code regarding the non-iterator member functions of the STL vector class through the links embedded here.

 

Programming#3 Due date Wednesday March 8: Using the vector class to implement merge sort.

·       Submission: (i) Compress your entire Program 3 folder into a zip file and upload it through Biola Canvas. (ii) Carefully fill out this self-evaluation report and upload it through Biola Canvas. Note that you will receive no point for missing the self-evaluation report or missing the integrity review in the report.

 

**************************************************************

 

Week 6: Basics of pointers and dynamic memory allocation

 

Reading#6, Due: Monday, Mar. 20

·       In Starting out with C++, read Sections 9.1~9.9 on pointers and dynamic memory allocation. You can skip the section on smart pointers in the 8th edition.

·       In C++ Primer, carefully read Section 2.3.2 on pointers.

 

**************************************************************

 

Week 7: More on pointers and dynamic memory allocation

 

Reading#7, Due: Wednesday March 22

·       In Starting out with C++, review Sections 9.1~9.9 one more time on pointers and dynamic memory allocation. You can skip the section on smart pointers in the 8th edition.

·       In C++ Primer, read section 3.5.3 and review Section 2.3.2 one more time on pointers.

 

 

Programming#4: Due date Wednesday March 22: Using pointers and dynamic memory allocation to implement merge sort.

·       Submission: (i) Compress your entire Program 4 folder into a zip file and upload it through Biola Canvas. (ii) Carefully fill out this self-evaluation report and upload it through Biola Canvas. Note that you will receive no point for missing the self-evaluation report or missing the integrity review in the report.

 

**************************************************************

 

Week 8: Vectors (as Containers) and Iterators + More on Pointers

 

Reading#8, Due: Wednesday March 29:

(i) Follow the related links here to carefully read the sample code on MSDN so that you can fully understand the purposes of four iterator member functions (begin, end, erase, and insert) of the STL vector class. (ii) Read 3.3~3.4 in C++ Primer on vectors and iterators. (iii) Read Sections 11.9~11.10 in Starting out with C++. on pointers to structures (objects), the dereference operators * and -> in Starting out with C++, 8th edition.

 

 

Midterm Exam (in-class open-book written test) Wednesday March 29

 

**************************************************************

 

Week 9: Linked lists as Data Structures + Implementation Using Pointers and Dynamic Memory Allocation

 

Reading#9: Due: Wednesday April 5

(i) Browse the introduction in beginning of this Wikipedia article on linked lists and the following sections in the article on the advantages, disadvantages, and basic concepts and nomenclature of linked lists. (ii) Read Sections 17.1~17.2.and Sections 17.4~17.5 on linked lists in Starting out with C++. (iii) Carefully examine the code and play with this sample linked list C++ project regarding the implementation of a simple linked list class for managing integer.

 

Programming#5A: implementing a simple date management program using vector<DateType>

·       Due date: Wednesday April 5

·       Submission: (i) Compress your entire Program 2 folder into a zip file and upload it through Biola Canvas. (ii) Carefully fill out this self-evaluation report and upload it through Biola Canvas. Note that you will receive no point for missing the self-evaluation report or missing the integrity review in the report.

 

****************************************************************

 

Week 10: Linked Lists

 

Reading#10: Due: Wednesday April 12

·       Go over Reading#9 one more time. In particular, carefully re-examine the code in the sample linked list C++ project regarding the implementation of a simple linked list class for managing integer. There will be a future test examining your understanding of the code.

 

Programming#5B:

·       Implement a simple date information management program using a liked list of DateType objects: Due: Wednesday, April 12.

 

**************************************************************

 

Week 11: Binary Search Trees.

 

Reading#11, Due: Wednesday, April 26  

i)      Chapter 20 on binary search trees in Starting out with C++.

ii)    Carefully examine the code in this sample binary search tree C++ project regarding the implementation of a simple binary search tree class for managing integer contents.

 

Homework #1: Testing the performance of the linked lists Due: Wednesday, April 26  

Submission of your work:

·   Record all your experimental findings in Step 2 and your thoughts in Step 3 in the homework into a WORD document. Submit the WORD document under Canvas.

·   Compress your entire Program folder into a zip file and upload it through Biola Canvas.

·   Carefully fill out this self-evaluation report and upload it through Biola Canvas. Note that you will receive no point for missing the self-evaluation report or missing the integrity review in the report.

 

**************************************************************

 

Week 12: More on Binary Search Trees and their Variants

 

Reading#12 Due: Wednesday, May 3  

i)      Carefully re-examine the code in this sample binary search tree C++ project regarding the implementation of a simple binary search tree class for managing integer contents.

ii)    Browse the following Wekipedia introductory articles on B-trees and self-balancing binary search trees.

 

Homework #2: Testing the performance of binary search trees Due: Wednesday, May 3  

Submission of your work:

·       Record all your experimental findings in Step 3 and your thoughts in Step 4 in the homework into a WORD document. Submit the WORD document under Canvas.

·       Compress your entire Program folder into a zip file and upload it through Biola Canvas.

·       Carefully fill out this self-evaluation report and upload it through Biola Canvas. Note that you will receive no point for missing the self-evaluation report or missing the integrity review in the report.

 

************************************************************

Keep the textbook “C++ Primer”:

For those who are going to take CSCI 230 Programming Languages next semester,

“C++ Primer” will continue to be a required textbook in CSCI 230.

**************************************************************

TA hours (MATH/CS lab in Grove 10):

Jarvis - T&R 10:30-11:30AM             Willy - W 1:30-3:30PM

**************************************************************

 

To the Top of the Page