. CSCI 330 Data Structures Fall 2002

More information is in the Generic Syllabus (over) and

.See http://www.csci.csusb.edu/dick/syllabus.html

and on the World Wide Web (WWW) site for this class

.See http://www.csci.csusb.edu/dick/cs330

You need to find the above sites for links to news, updates, grading, work, and resources.

. Description

CSci330 is the third course in the core computer science sequence. It completes the Association for Computing Machinery’s CS1 + CS2 sequence. It teaches vital skills and knowledge known to all good programmers. It is about ways of organizing data in computer memory to achieve various programming needs. This class is central to the CSci BS degree: all other classes depend on the skills you learn here. It is required by several other B.S. degrees.

. Prerequisites

All tests, lectures, and work assume you have passed a class equivalent to our CSCI202(CSci II) and MATH172 (Discrete Mathematics). Skill with C++ and UNIX will help you get the work done quicker.

. Goals

You will master the use and implementation of standard data structures using C++ and the UML. A data structure is a way of organizing, representing, and manipulating a collection of data in computer memory. Examples include arrays, vectors, stacks, lists, trees, heaps, and hash tables. One master programmer and computer scientist put it:

           Program = data structure + algorithms.

You will learn how to choose, use, and implement many standard data structures and algorithms for solving problems in this class.

You will learn how to choose the best data structure for a problem. You will learn how to predict the consequences of your choices of data structure and algorithms. You will learn how to be sure that your ideas are good ones: they work correctly and efficiently. You should develop a mature sense of elegance and brevity.

As part the course you learn more about object-oriented programming, analysis, and design. You will use Standard C++ and learning to code using its Standard Library (STL) of data structures. You will also become better at using the Unified Modeling Language (UML).

. Reading

TEXT: Required: Timothy Budd, Data Structures in C++ using the Standard Template Library, Addison-Wesley, 1998 (In the book store for CSci330)

RECOMMENDED: John Mongan & Noah Suojanen, Programming Interviews Exposed (secrets to landing your next job), Wiley 2000 ISBN0-471-38356-2. Did you know that CSci330 helps you with programming job interviews? (In the book store for CSci330)

REFERENCE: The library has many fine books on data structures, C++ (QA76.73.C153 ), the UML, and UNIX. Here are two that are specially useful for this class

             Bjarne Stroustroup, The C++ Programming Language, Addison-Wesley 1997.

             Scott Meyer, Effective STL: 50 specific ways to improve your use of the standard Template Library, Addison Wesley 2001, QA76.73.C153.M49

. Work

You will study the text, handouts, and references in your own time. See the schedule below. You need to correct the errors in the text as soon as you can. See the appended errata sheet below. You will do independent programming. You will need to think and do some math. Part of what you do will be submitted for grading.

. Meetings

Attend all class meetings from beginning to end or make up the work yourself. Exception - medical and other documented emergencies. *Note: mobile phones -- Turn off audio alarms. Do not use phones during class time.

I expect you to have studied the assigned reading before the class. The classes are set up to embarrass people who don't.

. Quizzes(200pts=40%, 240 pts Max)

There will be three quizzes each worth about 80 points each. Points adding above 200 will be used to make up points lost elsewhere. See the schedule (below) for topics. A typical quiz will have three parts: Part 1 is based on your programming projects and is worth 20 points. Part 2 will be a set of multiple guess, fill in the blanks and short answer questions from the textbook. This is worth 40 points. In the last part you chose a problem from a list and outline a solution to it using the UML and algorithms covered in the course (20 points).

. Comprehensive Final(200pts, 40%)

The final exam will be on December 5th from 2pm to 4pm. It will cover material in quizzes, labs, lecture/discussions, assigned work, and notes.

. Rules for Quizzes and Exams

Exams will test: (1) your ability to describe your software, (2) your understanding of the book, and (3)your understanding of UML and C++ data structures, and (4) solving programming problems by using data structures. You will also be expected to reason about the behavior of objects and programs in rigorous (mathematical) ways.

Tests will be closed-book and supervised. No wireless communication! You may use a calculator, but not a programable computer -- even if it fits in the palm of your hand. You may refer to a 11.5><8 sheet of notes. The quizzes and final will require you to (1) read, interpret, correct, and complete pieces of C++ programs, and (2) write correct C++ code. The tests will be integrated with and will complete your project work.

. Project Work(100pts, 20%)

I will assign four(4) programming projects. More details on the WWW site.

You will be assigned to a study/work group to tackle the first project only. The team hands in one piece of work and will share the same score. The later projects should be your own work and unlike anybody else's.

It is better to give me something on time than give me a perfect project late. Partial credit will be given for on time work that has compilation errors, missing features, problems, or bugs, if you document them in the code. All borrowed code must be documented in the code. After handing in a project, the following quiz will ask for information on the project you just handed in. The project grading will be based on practical and academic qualities. The work must be (1) on time, (2) correct, (3) understandable, (4) your own work, and (5) demonstrate ideas covered in the course at the time. Mistakes lose points -- especially if covered up. Anything I can't understand loses points.

What to hand in: Hand in the code. No cover sheets. No folders. No test runs. We want to read your code and know that it will run. Your code must have comments that identify you, the project in the book, and what you are doing! Comments should explain anything complicated or buggy. 20% of the grade for a project is for including comments.

Print out, staple and hand it in! Add any graphs of timing. In the quiz that follows you will be asked to document parts of your code using the UML, algorithms, math, and logic.

Schedule

Study before class

Topics

Assessment

1 Sep 19 - Intro, C++, OOP, UML -
2 Sep 24 Ch1,2,3 A Algorithms, Recursion -
3 Sep 26 Ch5 Proofs -
4 Oct 1 Ch4 Timing and O() Mock Q0(ch1,2,3,5,A)
5 Oct 3 Ch6, B C++ STL -
6 Oct 8 Ch7 Strings Q1 (Ch1,6,A,B)
- Oct 9 LAST DAY TO DROP    
7 Oct 10 Ch8.1-8.4 Vectors -
8 Oct 15 Ch8.4... Generic Algorithms -
9 Oct 17 Ch9.1-9.3 Using Lists -
10 Oct 22 Ch9.4... Impementing Lists -
11 Oct 24 Ch10.1-10.3 Stacks Q2 (Ch6..9.3)
12 Oct 29 Ch10.4... Queues -
13 Oct 31 Ch11 Deques -
14 Nov 5 Ch13 Trees -
15 Nov 7 Ch12 Sets  
16 Nov 12 Ch14 Divide & Conquer Q3 (Ch9.4..13)
17 Nov 14 Ch15.1,.2 Priority Queues & Heaps -
18 Nov 19 Ch15.4... OO Simulation -
19 Nov 21 Ch16.1..16.3+hash_map Maps -
20 Nov 27 Ch20.5.1..20.5.2, Ch17.1..17.3 Hashing -
- Nov 28&29 HOLIDAY    
Dec 5 2pm-4pm All of the above Comprehensive Final