CS 315 Data Structures                                              Fall 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 to 10:30 AM, M

 

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

 

Lab Time:  Friday 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, stacks, queues, linked lists, hash tables, priority queues, binary search trees etc.
  • Learn to design and implement solutions to computational problems that use basic data structures (listed above). Learn to design recursively defined structures as well as programs.
  • Compare the performances of different data structures and learn to make appropriate choice of data structures in various situations.
  • Learn the algorithms for fundamental problems such as searching, sorting, representation and manipulation of images, data and image compression etc.
  • Learn basic mathematical techniques for analyzing the performance of various data structures and different problem solving techniques.

Grading

Your grade for this course will be based on some (non-programming) lab assignments, 5 programming projects, two in-class tests and an in-class 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.

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 should 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 may 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 (immediately after the function header) the relationship between the input and output, the side-effects caused by the function (how it changes some data structures) and any pre-conditions that should be satisfied in order for the function to perform as expected.

 

Approximate week by week topics coverage

Week

Topic
Reading

Lab

1

·         Course overview, introduction to recursion

 

·         More on recursion

Sec 1.1 to 1.3

Recursion - introduction

2

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

  • Arrays, insertion and selection sorting
  • Merge sorting

Sec 1.4 to 1.6


Sec 7.2

 

 

Sec 7.6

Project # 1 (recursion and linked list)

3
  • Image representation and processing
  • Algorithm Analysis (Chapter 2)

Sec 2.1 to 2.4

Project # 1 continued

4

·         Linked lists            (Section 3.1 to 3.5)

 

Sec 3.1 to 3.5

Project # 2 image manipulation (array, recursion)

5

·         Stacks and queues                                      

·         Applications of stacks and queues     

Sec 3.6 and 3.7

Project # 2 (continued)

6

·         Hashing – 1 

  • Mid-semester Test # 1

Sec 5.1 – 5.2

Project # 2 (continued)

7
  • Hashing – 2

Sec 5.3 – 5.4

Project # 3 bounding box construction (queue based)

8
  • Priority queues, binary heap (intro.)
  • Binary heap operations

Sec 6.1 – 6.3

Project # 3 (continued)

9
  • Binary heap (continued)
  • Heap applications

Sec 6.3, 6.7

Project # 3 (continued)

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

Sec 4.1 – 4.3

     Project # 4 (spell checker) hash table

11
  • Binary search tree (operations)
  • Mid-semester Test # 2

Sec 4.3              

    Project # 4 (continued)

12
  • AVL trees, balancing
  • Some applications of binary search trees

Sec 4.4

Project # 4 (continued)

13
  • Quick sort

Sec 7.7

    Project # 5 image compression (quad-tree)

14
  • Graph representation
  • BFS and DFS

Sec 9.1, 9.6

cc Project # 5 (continued)

15
  • Shortest path problem

Sec 9.3

 Project # 5 (continued)

 

Final Exam

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