San Jose State University

CS 46B - Introduction to Data Structures

Kathleen O'Brien

Fall 2012

Class times and location: MW 1500 - 1615 in WSQ 109
Office Hours: MW 1430 - 1500 in WSQ 109 and on Piazza
Email: kathleen@laughton.com

Description

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

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 Mechanics

Laptops: You will be required to bring a wireless laptop to all (!) classes and exams.
Homework submission: You will submit your homework and exams in Desire2Learn dropboxes

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 24 hours earlier. Late work is not accepted, and there is no extra credit or makeup work. You will submit your assignments in the appropriate Desire2Learn dropbox
Participation: I expect each student to be present, punctual, and prepared at every scheduled class and lab session. You will be graded on particpation in class and the online discussion in Piazza. You are expected to post regularly either asking or asnwering questions. You can post anonymously, but then you do not receive credit. You also are expected to answer the in class questions that will be asked in Piazza(5%)
Quizzes: There is a quiz due every Sunday and Tuesday on the assigned reading for the next class meeting (5%)
Labs: You must enroll for a lab section and attend all labs. You will fail the course if you don't pass the lab section. Provided you get a passing grade in the labs, it counts as 5% of your total grade.
Time Spent: As per Policy Recommendation S12-3, success in this course is based on the expectation that students will spend, for each unit of credit, a minimum of forty-five hours over the length of the course for instruction or preparation/studying or course related activities.
This is a 4-unit/15-week class, so you should expect to spend at least 180 hours per semester or 12 hours per week on this class: 2.5 hours per week in the lecture, 2.5 hours per week in the lab, and 7 hours per week with preparation and homework assignments.

Grading Policy

You will receive a letter grade for each of the exams, the finals, the total homework performance, labs, paticipation in online discussion, and 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 in an email by 2000 the day of the first class, 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 24 hours and email me to confirm that you added the class, or the add code will be reassigned to someone else. In your email, specify your classification (Freshman, ... Senior 1, Senior 2, Open university. If you contacted me earlier, remind me.

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 these exceptions—you may copy from the textbook, the labs, or anything we do in class. 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.