Data Structures    CSCI 106, Spring 2008

To the Bottom of the Page

 

Instructor:  Dr. Shieu-Hong Lin

Class:  11:30AM-12:20  MW: at LIB 141  F: at Rood 52

Office Hours: Monday & Wednesday 2:30-4:20PM, Math & CS department

 

Course Syllabus

 

About programming:

1.      Intro to how to compile your C++ programs (with a sample Visual C++ project for a sample C++ program)

2.      Grading policy on programming assignments

3.      For each programming assignment, you should have someone else in the class testing your code for at least 10 minutes before email your source code files (all related .cpp and .h files) and this self-evaluation report to Dr. Lin.

 

About cumulative weekly reading & progress report:

1.      See the template report here as a word document or a web page.

2.      By Wednesday each week, you should spend around 5 minutes to write a progress report, and email it to Dr. Lin.

 

 

Weeks 1~2: Basics of object-oriented programming

·        Reading#1 Due: Wednesday, Feb. 6: Review Sections 13.1~13.8 on the basics of objects and classes in Starting out with C++.

·        Reading#2 Due: Wednesday, Feb. 13: Read Sections 13.9~13.12 on the basics of object-oriented programming in Starting out with C++.

 

Weeks 3~4: Intro to the STL vector class

·        Reading#3 Due: Wednesday, Feb. 20:  (i) Section 7.12 on the STL vector class; Section 10.7 the C++ string Class; and Section 14.5 on operator overloading in Starting out with C++. (ii) Sample code of the methods of the STL vector class listed here.

·        Reading#4 Due: Wednesday, Feb. 27: (i) Section 16.5 on STL (the standard template library) in Starting out with C++. (ii) Sections 9.1~9.10 on pointers and dynamic memory allocation in Starting out with C++.

 

Weeks 5~6: More on the C++ Standard Template Library (STL)

·        Reading#5 Due: Wednesday, March. 5:  Sections 3.3~3.4, and sections 9.1~9.3 on the very basics of STL in C++ Primer.

·        Reading#6 Due: Wednesday, March. 12:  Sections 2.2~2.5, and sections 2.8~2.9 on the basics of classes and objects in C++ Primer.

 

Weeks 7~8: Pointers, arrays, and types of function parameters; Strings, character arrays, and the IO library

·        Reading#7 Due: Wednesday, March. 19:  Sections 4.1~4.2 on arrays and pointers, sections 7.1~7.2 on functions and parameter passing in C++ Primer.

·        Reading#8 Due: Wednesday, April 2:  Section 3.2 on the library string class, Section 4.3 on C-style character arrays as strings, Section 5.6 on the arrow operator, and Chapter 8 on the IO library in C++ Primer.

 

Week 9: Spring break, review, and midterm

        Reading#9: Review of text covered in the previous reading assignments.

Midterm written test (in-class open-book test on all the subjects covered): Monday, April 7. 

 

Weeks 10~11: Linked lists and binary search trees and the use of pointers and dynamic memory allocation in the implementation.

·        Reading#10 Due: Wednesday, April 16:  (i) Sections 11.9~11.10 on pointers to structures (objects) and dereference operations * and -->. (ii) Sections 20.1 and 20.2 on binary search trees in Starting out with C++. (iii) Examine the code and play with this sample binary search tree C++ project regarding the implementation of a simple binary search tree class for managing integer contents.

·        Reading#11 Due: Wednesday, April 23:  (i) Sections 17.1~17.2.and Sections 17.4~17.5 on linked lists in Starting out with C++. (ii) Examine the code and play with this sample linked list C++ project regarding the implementation of a simple linked list class for managing integer contents.

 

Week 12: Examine C++ Classes

        Reading#12: Section 11.1 of C++ Primer on generic algorithms and Chapter 12 of C++ Primer on classes. Due: Wednesday, April 30. 

 

Week 13: STL map container as associative arrays

        Reading#13: Due: Wednesday, May 7.

·    (i) Section 10.1~10.3 of C++ Primer on STL maps. And the following examples on using maps: mapAsAssociativeArray.cpp (click View -> Source) and map.cpp (click View -> Source).

 

Week 14: Stacks and queues:

·          Reading#14: Read Chapter 18 in Starting out with C++ on the basics of stacks and queues.  Due: Wednesday, May 14.

 

Final Exam (Open-book test): 10:00am~12:00, Wednesday May 21.

 

Programming#1: Creating your own user-defined DateType class: Due: Wednesday, Feb 13.

Programming#2: Using the vector class to implement merge sort: Due: Wednesday, Mar. 5.

Programming#3: Enhancing the DateType class to include operator overloading: Due: Wednesday, Mar. 19.

Programming#4: Implementing a simple date information management program using vector<DateType>: Due: Wednesday, April 2.

Programming#5: Implementing a user-defined personal contact information class ContactInfo for contact information management: Due: Wednesday, April 23.

Programming#6: An experiment to measure the performance of unsorted linked lists, sorted linked list, and binary search trees. Due: Wednesday, April 30.

Programming#7: An experiment to measure the average height of random binary search trees. Due: Wednesday, May 7.

Programming#8: Finding Euler circuits in graph represented by STL vectors and maps. Due: Friday, May 23.

Optional Programming#9: Implementing an expression evaluator using vectors and stacks

 

 

Useful online references to C++ and C libraries

 

 

 

To the Top of the Page