CS 46B Syllabus

CS 46B Course Syllabus

General information
- CS 46B, Introduction to Data Structures
- Department of Computer Science
- San Jose State University
- Fall 2008 semester
Instructor information
1. Name: Mark Stamp
2. Office: MQH 216
3. Office hours: Monday 10:30am--noon and 1:00-3:30pm, or by appointment
4. Phone: 408-924-5094
5. email: stamp@cs.sjsu.edu
  - Email is the best way to contact me
  - Please put "CS46B" at the beginning of the subject line
6. Greensheet: http://www.cs.sjsu.edu/faculty/stamp/CS46B/syllabus/syllabusFall08.html
7. Who am I?

Textbook: Objects, Abstraction, Data Structures and Design Using Java 5.0, by Koffman and Wolfgang, Wiley 2005, ISBN 978-0-471-69264-5.

Student companion site for the textbook is here.

We will cover the following material:

Chapter	Weeks
Introduction to software design (1.1 ~ 1.7)	1.5
Program correctness and efficiency (2.1 ~ 2.8)	1.5
Working with key object-oriented concepts (3.1 ~ 3.7)	1
Interfaces (4.1 ~ 4.3)	1
Linked lists and iteration (4.4 ~4.7)	2
Stacks (5.1 ~ 5.4)	1
Queues (6.1 ~ 6.4)	1
Recursion (7.1 ~ 7.6)	1.2
Binary trees, including BST's (8.1 ~ 8.4)	1.3
Sets and maps (9.1 ~ 9.6)	1
Simple sorting methods (10.1 ~ 10.6)	1

Prerequisite: CS 46A (or CS 49J) with a grade of C- or better and MATH 42.
Student Learning Objectives:
- To give students an understanding of the concept of Abstract Data Types, especially the concept of separation between interface and implementation.
- To give students an understanding of the standard collections interfaces and classes such as lists, stacks, queues, hash tables, binary trees and iterators, together with elementary implementations, and how to use them in applications.
- To give students exposure to the reasons for choices made in the implementation of these data structures; especially relating to issues of efficiency.
- To introduce students to assertions, pre- and post-conditions, and loop invariants.
- To introduce basic concepts pertaining to software testing and debugging.
- To introduce students to simple searching and sorting algorithms.
- To acquaint students with the concept of recursion.
- To familiarize students with the usual mechanism for implementing method invocation and return.
- To introduce students to the Unix OS and to give them experience with the use of Unix.
Java Programming Environment
- Programming Language: JDK 6 (also known as J2SE 6.0)
  - Available on all Department machines.
  - Download JDK 6.0 (does not include Java EE, NetBeans 5.5)
- Text Editor: TextPad (trial version)
- IDEs
  - Eclipse (recommended)
  - BlueJ
- I encourage you to use an IDE. The lectures do not cover how to use an IDE---here are some useful IDE resources:
PowerPoint slides used in class are available here.
Lab greensheet is here.
Grading:
1. Test 1, 100 points. Date: Thursday, October 9.
2. Test 2, 100 points. Date: Thursday, November 13.
3. Homework, programs, quizzes, lab assignments, class participation, and other work as assigned, 100 points.
4. Final, 100 points. Date: Monday, December 15, 12:15pm-2:30pm. The official finals schedule is here: http://info.sjsu.edu/web-dbgen/narr/soc-fall/rec-232.html
5. Semester grade will be computed as a weighted average of the 4 major scores listed above.
6. No make-up tests or quizzes will be given and no late homework (or other work) will be accepted.
7. Nominal Grading Scale:
  
  Percentage Grade
  92 and above A
  90 - 91 A-
  88 - 89 B+
  82 - 87 B
  80 - 81 B-
  78 - 79 C+
  72 - 77 C
  70 - 71 C-
  68 - 69 D+
  62 - 67 D
  60 - 61 D-
  59 and below F
Homework: Note that a subset of the assigned problems will be graded.
- Assignment 1: Due Thursday, September 4
  Chapter 1: Review Questions 3, 4, 6 and Programming Project 3
- Assignment 2: Due Thursday, September 11
  Chapter 2: Review Questions 3, 4, 9 and Programming Projects 1, 2
- Assignment 3: Due Thursday, September 18
  Chapter 3: Review Questions 2, 3, 8 and Programming Project 5. For the programming project, feel free to modify the class hierarchy (see Figures 3.18 and 3.19) so that it is actually useful for you. For example, under Audio, you might want to eliminate the Cassette class and include an MP3 class, and so on.
- Assignment 4: Due Thursday, September 25
  Chapter 4: Review Questions 1, 2, 3 and Programming Project 1.
- Assignment 5: Due Thursday, October 2
  Chapter 4: Review Questions 5, 6, 7 and Programming Project 3 (use a linked list).
- Assignment 6: Due Thursday, October 16
  Chapter 4: Review Question 9 and Programming Project 4.
- Assignment 7: Due Thursday, October 23
  Chapter 5: Review Questions 1, 7 and Programming Project 4.
- Assignment 8: Due Thursday, October 30
  Chapter 6: Review Questions 2, 4 and Programming Project 6.
- Assignment 9: Due Thursday, November 13
  Chapter 7: Review Questions 1, 2 and Programming Project 5.
- Assignment 10: Due Tuesday, November 25
  Chapter 7: Review Questions 3, 5 and Programming Project 6.
  Chapter 8: Review Questions 1, 2 and Self-Check exercise 2 on p. 408.
- Assignment 11: Due Thursday, December 4
  Chapter 8: Review Question 3 and Programming Project 5.
- Assignment 12: Due Monday, December 15
  Chapter 9: Review Questions 1, 2 and Programming Project 2.
  Chapter 10: Review Questions 2, 4 and Programming Project 1. For the programming project, you only need to use the sort methods we discussed, namely, selection sort, bubble sort, and insertion sort).
Submitting Homework Assignments
- Write all of your answers to questions in one text file (.txt). To submit java programs, zip all your .java files (not .class files) to a file named hmk.zip.
- Email your work to grader.cs46b@gmail.com. The subject line of your email must be of the form:
```
     CS46BHMK assignmentnumber yourlastname last4digitofyourstudentnumber 
```
  That is, the subject line must consist of four identifiers. There is no space within an identifier and each identifier is separated by a space.
- Be sure to attach your .txt and/or .zip file(s) to your email before sending it.
Keys to success: Do the homework and attend class
Wireless laptop is required. Your laptop must remain closed (preferably in your backpack and, in any case, not on your desk) until I inform you that it is needed for a particular activity
Cheating will not be tolerated...
- ...but working together is encouraged
Student must be respectful of the teacher and other students; for example
- No talking
- Turn off cell phones
- Class begins on time
- Class is over when I say it's over
Disability information and policies can be found here
Valid picture ID required at all times
Note that the last day to drop is Friday, September 5, and the last day to add is Friday, September 12
An interesting and relevant quote.
Other Stuff

Percentage	Grade
92 and above	A
90 - 91	A-
88 - 89	B+
82 - 87	B
80 - 81	B-
78 - 79	C+
72 - 77	C
70 - 71	C-
68 - 69	D+
62 - 67	D
60 - 61	D-
59 and below	F