Course Expectations and Tentative Syllabus

 

CSC:162                                               Introduction to Data Structures and Algorithms                                                           Fall 2001

Room 319 Olney Hall                       Time:                 MWF 12:00-12:50pm

                                                                Room: 201 Olney Hall                        Lab                  Tu 2:00-3:50pm

Professor:    Dr Michael Redmond   

                       330 Olney Hall   (215) 951-1096

                       redmond@lasalle.edu

                       http://www.lasalle.edu/~redmond/teach/162

 

Office Hours:                 MWF 11-11:50am, MW 2-2:50pm, T  5:00-6:00pm, And at other times by appointment

 

Text:

                Budd, T.A., Data Structures in C++ Using the Standard Template Library, Addison-Wesley, 1998  ISBN: 0-201-30879-7

 

Course Description:

This course is designed to 1) teach basic data structures including lists, stacks, queues, trees, etc; 2) introduce analysis of simple algorithms; and 3) teach capabilities of C++ that are not found in C (the language used in the first programming course CSC 157). The course meets MWF with a lab on Tuesdays. 

We use the language C++ as a vehicle for teaching data structures, but it really is more than that. The C++ Standard Template Library provides capabilities for several common data structures. Hence, this raises the level of abstraction. Students can first learn about how the data structure works and can be used,  THEN learn about how these could be programmed.

Programming is central to this course. You do not fully understand the concepts until you can use them to solve problems. Hence programming assignments are central to this course. Come to Lab! Come on-time and prepared! Do the assignments! Do them on-time! and Do your own work!

 

Prerequisite: CSC 157. This class directly builds on that foundation; thorough understanding of material from that class is assumed.

 

Grading:

                   Assignments     30%

                Exam 1                           20%

                Exam 2                           20%

                Final                            30%

 

                Final Grades:

A                92-100                                A-                 90-91

B+                88-89                                B                82-87                                B-                80-81

C+                78-79                                C                72-77                                C-                70-71

D+                68-69                                D                60-67                                F                < 60

 

                Students generally do better if they read the section of the textbook BEFORE it is presented in class, since they are prepared to ask questions. Working end-of-chapter exercises is a good test of your understanding.

                 Assignments will typically be assigned on a Mon., possibly with “pre-lab” preparation work to do, hands-on time in the lab on Tue, and “post-lab” work to do, due the following Mon.

                Do your own assignments !!!!  Work that is copied or done with somebody (when not assigned to a group) will be punished. If in a group/pair, your group must do its own work.

 

                Late Assignments  -25% per weekday (NOTE - NOT per CLASS)

                UNLESS SPECIFIED OTHERWISE ASSIGNMENTS ARE DUE AT THE BEGINNING OF CLASS

                -10% if handed in after start of class and before I leave for the day.

 

                Makeup exams only by advance arrangements or for documented real emergencies, such as medical problems. Makeup may involve double-counting your final exam.

 

                The Final Exam is cumulative, though it will focus more on the (previously untested) final third of the course.

 

Open Lab Location:                   Wister Building basement lab is available 8:30am-11pm

                                                Olney 200A is sometimes available as an open lab (but fills up quickly)

 

Objectives

 

0. Introduce basic differences between C and C++, including I/O, Reference Parameters, Overloading.

 

1. Teach concept of abstract data types and their importance.

 

2. Demonstrate use of classes to implement abstract data types.

 

3. Introduce analysis of simple algorithms for execution time.

 

4. Demonstrate advanced C++ capabilities including Templates, and Inheritance.

 

5. Introduce the standard template library (STL) container classes.

 

6. Study the string ADT, how to solve problems using strings, the string STL class, and programming techniques that could be used to develop an implementation of strings.

 

7. Study the vector ADT, how to solve problems using vectors, the vector STL class, and programming techniques that could be used to develop an implementation of vectors.

 

8. Study the list ADT, how to solve problems using lists, the list STL class, and programming techniques that could be used to develop an implementation of lists.

 

9. Study the stack ADT, how to solve problems using stacks, the stack STL class, and programming techniques that could be used to develop an implementation of stacks.

 

10. Study the queue ADT, how to solve problems using queues, the queue STL class, and programming techniques that could be used to develop an implementation of queues.

 

11. Study the tree ADT, how to solve problems using trees, the tree STL class, and programming techniques that could be used to develop an implementation of trees.

 

 

 

 

Tentative Course Plan:

 

Date       Material                                                                                             Reading

 

Aug 27                   Intro to Class

Aug 29                     Going from C to C++                                                       Chapt 1

Aug 31                     Going from C to C++                                                         Chapt 1

 

Sept 3                     LABOR DAY – NO CLASS

Sept 5                     Going from C to C++                                                         Chapt 1

Sept 7                     Abstract Data Types and Classes                                  Chapt 2

 

Sept 10                   Abstract Data Types and Classes                                  Chapt 2

Sept 12                   Abstract Data Types and Classes                                  Chapt 2

Sept 14                   Abstract Data Types and Classes                                 

 

Sept 17                   Abstract Data Types and Classes

Sept 19                   Abstract Data Types and Classes                                 

Sept 21                   Analyzing Algorithm Execution Time                         Chapt 4

 

Sept 24                   Standard Template Library Container Classes                Chapt 6

Sept 26                   TEST 1                                                                                  

Sept 28                   Standard Template Library Container Classes                Chapt 6

 

Oct 1                       Standard Template Library Container Classes                Chapt 6

Oct 3                       String Class                                                                      Sections 7.1, 7.2

Oct 5                       String Class                                                                      Section 7.3

 

Oct 8                       String Class                                                                      Section 7.3

Oct 10                     Vector Class                                                                      Section 8.1

Oct 12                     Templates                                                                            Section 8.2

 

Oct 15                     Templates                                                                            Section 8.2

Oct 17                     Vector Class                                                                      Section 8.3

Oct 19                     Vector Class                                                                        Section 8.4

 

Oct 22                     FALL BREAK – NO CLASS

Oct 24                     Vector Class                                                                      Section 8.4

Oct 26                     List Class                                                                      Section  9.1

 

Oct 29                     TEST 2

Oct 31                     List Class                                                                      Section 9.2

Nov 2                     List Class                                                                      Section 9.3

 

Nov 5                     List Class                                                                      Section 9.4

Nov 7                     List Class                                                                      Section 9.4

Nov 9                     List Class                                                                      Section 9.4

 

Nov 12                   Inheritance                                                                            Section 9.5

Nov 14                   Inheritance                                                                            Section 9.5

Nov 16                   Stack and Queue Classes                                                  Sections 10.1,10.2

 

Nov 19                   Stack Class                                                                     Section 10.3

Nov 21                   THANKSGIVING BREAK – NO CLASS

Nov 23                   THANKSGIVING BREAK – NO CLASS

 

Nov 26                   Stack Class                                                                     Section 10.3

Nov 28                   Queue Class                                                                      Section 10.4

Nov 30                   Queue Class                                                                      Section 10.4

 

Dec 3                      Tree Class                                                                      Section 13.1

Dec 5                      Binary Trees                                                                      Section 13.2

Dec 7                      Binary Trees                                                                      Section 13.2

 

If possible                Tree Iterators and Traversal                                               Section 13.4

 

Final Exam: TBD (Dec 10-14)