San Jose State University

CS 46B - Introduction to Data Structures

Cay S. Horstmann

Spring 2012

For meeting times and location, office hours, and contact information, please visit http://www.sjsu.edu/people/cay.horstmann.

The schedule is subject to frequent change; visit it before each class meeting. You submit your work in Desire2Learn.

Description

Stacks and queues, recursion, lists, dynamic arrays, binary search trees. Iteration over collections. Hashing. Searching, elementary sorting. Big-O notation. Standard collection classes. Weekly hands-on activity.

For the official catalog description, please visit http://info.sjsu.edu/web-dbgen/catalog/departments/CS-courses.html.

Prerequisites

Knowledge of Java equivalent to that obtained by completing CS 046A or CS 049J (with grade of "C-" or better). Eligibility for MATH 030 or MATH 030P, or instructor consent. Pre/Corequisite: MATH 42

Textbook

Cay S. Horstmann, Java Concepts 6th Edition. ISBN 978-0-470-50947-0.

Student Learning Outcomes

Upon successful completion of this course, students should be able to:

use and work with basic structures such as linked lists, stacks, queues, binary search trees and iterators
implement from specifications Java classes that embody data structures
use and work with pre-existing implementations such as the Java collections framework
make relative estimates between alternative algorithms of the running time of algorithms using big-O estimates
formulate and test for pre- and post-conditions
distinguish between different types of program defects and understand how testing and debugging are used to correct them
implement simple sorting algorithms such as insertion sort and selection sort
implement the sequential search and binary search algorithms
implement simple recursive algorithms such as binary tree traversals
use hash tables when appropriate
understand the overhead involved in method invocation and return
work competently with commonly used tools for software development

Course Requirements

Exams: Two in-class exams (15% per exam) and a final exam (25%). Exams cannot be made up, except for reasons of illness, as certified by a doctor, or documentable extreme emergency. Makeup exams may be oral.
Programming Assignments: Two assignments per week (30%). Schedule your time well to protect yourself against unexpected problems. I suggest you ignore the official deadlines and complete the assignments 48 hours earlier. Late work is not accepted, and there is no extra credit or makeup work.
Class Attendance, Preparation and Participation (15%): I expect each student to be present, punctual, and prepared at every scheduled class and lab session. You will be graded on particpation in lab work, class and online discussions, and your performance on quizzes that check the assigned pre-class reading.
Laptops: You will be required to bring a wireless laptop to all (!) classes and exams.

Grading Policy

You will receive a letter grade for each of the exams, the finals, the total homework performance, and the total participation in labs/discussions/quizzes. Letter grades are obtained by adding and curving the numeric scores. When determining a curve, the cutoffs are guided by the university definitions for letter grades:

A+, A, A- excellent
B+, B, B- above average
C+, C, C- average
D+, D, D- below average
F failure

Letter grades are converted into number grades, as specified here, except that an A+ is counted as 4.3, and weighted with the percentages given in the Course Requirements section. The weighted average is rounded towards the nearest letter grade, which is your class grade.

Miscellaneous Policies

Add Policy: I will randomly choose among add requests that I receive before the second class meeting time, and in the order of receipt thereafter. If there is space, I will reply to your email with an add code. You must use your add code within 48 hours and email me to confirm that you added the class, or the add code will be reassigned to someone else.

Individual Work: All homework and exams must be your own individual work. It is ok to have general discussions about homework assignments, or read other material for inspiration. You may never copy anything from anyone without attribution, with one exception—you may copy from the textbook. For homeworks and exams, you may not copy anything from any other student at all, and you may not collaboratively produce results in pairs or teams.

Publicly Viewable Work: Your class work (including homework, exam, and project work) may be viewable by other students of this course. Your grades will not be viewable by others.

Copyright of Materials: All materials created by the instructor for this course, including lectures, handouts, homeworks, exams, solutions, projects, and so on, are copyrighted property of the instructor. You may transscribe or record lectures or copy course materials for the use of yourself and other students registered in this course. You may not sell or give transscriptions or recordings of lectures or copies of course materials to others without the prior written consent of the instructor.