CSC 2431
Data Structures II
Spring 2008
Brief Info Sheet

Instructor: Phil Prins

Phone:  (206) 281-2738 (office)
            (360) 568-9337 (home)

Email: pprins@spu.edu

Fax: (360) 568-9167 

Office Hours: MW 1:30 - 2:30; F 12:30 - 1:30; or by appointment

Office: OMH 239

Meeting Times: MWF 11:00 - 12:30 in OMH 244

Texts:

Important Dates:    April 25            First exam
                                May 21             Second exam
                                June 3               Final exam (10:30 - 12:30)

Computers: Personal Computers are available for your use in the Computer Lab in Otto Miller Hall.  Usually, there will be a lab assistant to help you with minor problems. If you have access to any other computer system and a C++ compiler, you may use it.

Assignments: You will have both programming assignments and written assignments; they will be turned in before the beginning of class on the due date. You may turn in one AND ONLY ONE assignment up to 1 week late and still receive credit for it (you will receive full credit).

You are STRONGLY ENCOURAGED to help each other with your assignments BUT don’t even think of copying someone else’s homework solution!

Grading:

          Homework (assignments and programs)                   200 pts
          Tests (2 1-hour exams @ 100 pts each)                   200 pts
          Final Exam (comprehensive)                                    150 pts
                                                                                         ---------
                                                                                         550 pts

   90% - 100% A
   80% - ~90% B
   70% - ~80% C
   60% - ~70% D
              <60% E

Program Style Requirements

Objectives of this Course:

This course will introduce the student to the design and use of data structures and algorithms, including their implementation in the object-oriented C++ programming language.  Students successfully completing the course (C+ or better) will be able to:

1. Articulate the concept of an abstract data type (ADT) and the object-oriented concepts of

· "encapsulation"              Information hiding. Emphasize Classes and Methods.

· "inheritance"                  Class derivation, modification and reuse.

· "polymorphism"             Dynamic runtime binding and behavior. Base-class pointers. Virtual functions.

2. Design, code, debug and test single- and multi-file C++ programs.

· Pointers. Recursion. Templates. Iterators. Overloaded operators. Design patterns.

3. Study the design and implementation alternatives for several of the following non-linear ADTs:

· trees; binary search trees; tables; priority queues; balanced search trees; hashing; graphs

4. Study the design and implementation of appropriate methods for handling external storage.

5. Articulate the concept of Big O notation; compare the efficiency of searching and sorting algorithms.

· Given the Big O efficiency of an algorithm and the running time for a sample data set, calculate the predicted running time for that algorithm for any size problem. 

· Given a set of frequencies for each of the operations of an ADT, choose an implementation which will give the best overall performance (with respect to execution time or memory usage). 

About the introductory programming sequence:

CSC1230, CSC2430, and CSC2431 can be thought of as a Programming 1,2,3 sequence.

In CSC1230, you learned the basics of the ‘C++’ programming language, problem solving skills and how to correctly program a solution to a complex problem. Good solutions to problems were emphasized. In that class, learning syntax was very important.

In CSC2430, you learned some more advanced ‘C++’ programming and techniques for internal memory management. This includes more complex data structures and algorithms that work efficiently on those data structures. The emphasis in this class will be "correct" choices of data structures and the efficiency (in both time and space) of your algorithms.

CSC2431 continues the study of data structures.  In this class you will study trees, graphs, and other complex data structures.  Object-oriented design and programming will be emphasized and enforced.  You will learn about templates, proper class declaration, inheritance, and polymorphism.

The Computer Science Department Mission Statement:

The Department of Computer Science seeks to educate and prepare students for a variety of careers in business, scientific, and engineering computing by:

• developing their problem solving skills, especially those required to analyze, design and implement solutions involving the use of a computer
• providing a background in the organization and operation of modern computing systems and the theoretical aspects of computer science
• challenging them to consider the ethical and social impacts of technology on modern life, especially as these relate to evangelical Christian faith and values
• preparing them for continued learning in the rapidly changing discipline

Departmental Objectives for this Course

Professional Codes of Ethics:

From the ACM (Association for Computing Machinery)

http://www.acm.org/constitution/code.html

From the IEEE (Institute of Electrical and Electronics Engineers)       

http://www.ieee.org/portal/pages/iportals/aboutus/ethics/code.html