CS 31 Data Structures                                                    Spring 2008

Sonoma State University

Instructor: B. Ravikumar          Office:  116 I, Darwin Hall

Office phone: 664 3335            Email: ravi93@gmail.com

Office hours:  T Th 9:30 – 10:30 AM, W 4 – 5 PM

 

Class Time:   T Th 10:45 to 12 noon, Darwin Hall 37

 

Lab Time:  T 1 – 3:50 PM, Darwin Hall 28

 

Prerequisites for the course: CS 215 and CS 242

Textbook:

Data Structures and Algorithm Analysis in C++, 3rd Edition, by Mark Alan Weiss, Addison-Wesley, ISBN 0-321-44146-X

 

Course Goals

  • Understand the central data structures such as arrays, lists, hash tables, priority queues, binary trees.
  • Implement several projects that use various data structures
  • Compare performance of data structures and learn to make appropriate choices based on the context.
  • Learn to implement data structures as well as to use the provided implementations of data structures to build problem solutions.

Grading

Your grade for this course will be based on some lab assignments, 4 programming projects, two in-class tests and a final exam.

Weights for these components are (approximately) as follows:

·         programming projects                         –   50%

·          Two Mid-term tests                             –   30%

·         Final Exam                                       –   20%

Tips for success

  • Attend all the lectures and the labs.  You should make your best effort to inform me ahead of time if you have to miss a lecture or a lab. 
  • Read the assigned topic before the class and come prepared.
  • If you are not clear about what is covered in class, you should talk to me as soon as possible. This course is challenging and you should expect to work  about 5 to 10 hours per week in addition to the lab and lecture times.

Contacting Me

Please feel free to visit me during my office hours. If you can't make it during the regular hours, send me an e-mail to make an appointment at a more convenient time of your choice. You are strongly encouraged to e-mail your questions. I will respond to your questions as soon as possible. When a question or its response is relevant to the whole class, I will broadcast the dialog to the whole class.

Policy on Collaboration

Active collaboration and discussion of the course material with fellow students is an effective way to learn and can be very helpful in overcoming your difficulties. However, when working on the programming projects, you are to use the following guideline: the actual coding should be done individually, and if you have had significant discussion with others on the programming project, you should list their names in your submission.

Coding style and documentation 

 

Some part of the project work will be assigned for documentation. Precise instructions on how to document your work will be provided for each project. For each function you write, you should try to state at the outset the relationship between the input and output, any side-effects produced by the function (how it changes the internal data structures) and any pre-conditions that should be satisfied so that the function will perform as expected.

 

 

 

 

 

 

 

 

 

 

Class Schedule (tentative)

Week

Date

Topic
Reading

Lab

1

Jan 9, 31

 

·         Course overview, introduction to recursion

·         More on recursion

Sec 1.1 to 1.3

Recursion - introduction

2

Feb 5, 7

·         Review of C++ (Section 1.4 to 1.6)

  • Arrays, insertion and selection sorting

Sec 1.4 to 1.6

Sec 7.2

Project # 1 (recursion and linked list)

3

Feb 12, 14
  • Image representation and processing
  • Algorithm Analysis (Chapter 2)

Sec 2.1 to 2.4

Project # 1 continued

4

Feb 19,21

·         Linked lists            (Section 3.1 to 3.5)

 

Sec 3.1 to 3.5

Project # 2 image manipulation

5

Feb 26, 28

·         Stacks and queues                                      

·         Applications of stacks and queues     

Sec 3.6 and 3.7

Project # 3 (spell checker)

6

Mar 4,6

·         Hashing – 1 

  • Mid-semester Test # 1

Sec 5.1 – 5.2

Project # 3 (continued)

7

Mar 11,13
  • Hashing – 2

Sec 5.3 – 5.4

Project # 3 (continued)

8

Mar 18, 20
  • Priority queues, binary heap (intro.)
  • Binary heap operations

Sec 6.1 – 6.3

Project # 4 (scheduling problem)

 

Mar 25 to 31

                         SPRING BREAK

 

 

9

Apr 1, 3
  • Binary heap (continued)
  • Skew heap

Sec 6.3, 6.7

Project # 4 (continued)

10

Apr 8,10
  • Binary trees, arithmetic expressions
  • Binary search trees (introduction)

Sec 4.1 – 4.3

    Project # 4 (continued)

11

Apr 15, 17
  • Binary search tree (operations)
  • Mid-semester Test # 2

Sec 4.3              

    Project # 5 (geometric computation problem)

12

Apr 22, 24
  • AVL trees, balance property
  • Height balancing

Sec 4.4

Project # 5 (continued)

13

Apr 29, May 1
  • Merge Sort
  • Quick sort

Sec 7.6 – 7.7

    Project # 5 (continued)

14

May 6, 8
  • Graph representation
  • BFS and DFS

Sec 9.1, 9.6

cc

15

May 13,15
  • Shortest path problem

Sec 9.3

 

 

Tuesday, May 20

Final Exam
11:00 – 12:50

Comprehensive, one open-book section and one closed-book section