Data Structures

Data Structures and Algorithm Design

M 2:30-3:50, W 1:00-2:20, 244 Smith Hall

The final exam will be held 3-6pm, Monday, May 10, in Smith 244. The final will be comprehensive, but will emphasize the material after Test 2 (chapters 10 and 11). Here are some sample problems for the material on Test 1 (solution), on Test 2 (solution), after Test 2 (solution).

Office hour on Wednesday, May 5: 10-11am, 309 Smith.

Program 1 is due Monday, February 8 (it is OK to hand it in via email by 10am the next day, Tuesday, February 9). Program 2 is due Wednesday, February 17. Program 3 is due Monday, March 8 (you may turn this one in by class-time on Wed, Mar 10). Program 4 is due Wednesday, March 31. Program 5 is due Monday, April 19. Program 6 is due Monday, May 3.

Solutions to Quiz 1, Quiz 2, Program 1, Quiz 3, Program 2, Test 1, Quiz 4, Quiz 5, Program 3, Quiz 6, Quiz 7, Program 4, Quiz 8, Test 2, Quiz 9, Quiz 10, Program 5, Program 5 bonus (DequeInterface.java, DequeReferenceBased.java, DoubleNode.java), Quiz 11, Program 6.

Programs discussed in class.

Getting started. Writing and running java programs on pegasus.

Instructor Prof. John Loftin, 309 Smith Hall, Phone: (973)353-3910.

Email loftin@rutgers.edu
Email is the best way to get in touch with me.

Website http://andromeda.rutgers.edu/~loftin (this syllabus is attached to the website)

Department
Website http://math.newark.rutgers.edu

Prerequisite Computer Science 102

Who Should Take
This Course This course is required for the Computer Science and Information Systems majors, and for the Computer Science minor.

Course Material
(more details
are on the
Course Schedule)

Recursion
Abstract Data Types
Linked Lists
Stacks and Queues
Advanced Java Topics
Algorithm Efficiency and Sorting
Trees

Text Carrano & Prichard, Data Abstraction & Problem Solving with Java: Walls and Mirrors, 2nd ed., Addison Wesley

Homework
and Quizzes The homework will be assigned about once a week. It will not be collected, but it will form the basis of the weekly quizzes. Students are encouraged to work together on the homework. Your lowest two quiz grades (including absenses for any reason) will be dropped.

Programs The language for the programs is Java. There will be 6 programming assignments, which will be assigned about a week in advance. You should write your programs using the javac compiler on pegasus.
You are encouraged to discuss the programs with each other, but YOU MAY NOT COPY ANYONE ELSE'S PROGRAM CODE.
The grades for programming assignments will be based mainly on the correctness of the code, but partially on the elegance and proper use of encapsulation in the code. Programs which do not compile will receive no credit.

Exams There will be two exams during the term and a final exam. The first two exams will be held in class, and will test your knowledge of the material covered in the past few weeks' classes. Exam 1 will be held in class on Monday, February 22. Exam 2 will be held on Wednesday, April 7. The final exam will be held according to the university's schedule, Monday, May 10, 3-6pm. The final exam will be comprehensive. (See the Course Schedule.)

Grades Your grade will be determined by your quizzes (10%), your programs (20%), Exam 1 (17.5%), Exam 2 (17.5%), and the Final Exam (35%).

Office Hours M 1:00-2:00, W 11:30-12:30, in 309 Smith Hall. You may see me any time during office hours without an appointment. You may also make an appointment to see me other times.

Course Schedule

John Loftin

2010-01-01

Test 1 is graded. Stats:
Out of 68 points
Average 40
Median 36
Range of scores----Num of students
62-68------------------2
55-61------------------2
48-54------------------0
41-47------------------1
34-40------------------6
28-33------------------2
21-27------------------4

Test 1 will be held in class on Monday, February 22. The material covered will be the material in the book we covered in Chapters 3,4,5.1,5.2. Here are sample questions for the test, with solutions.

Test 2 is graded. Stats:
Out of 52 points
Average 39
Median 37
Range of scores----Num of students
47-52------------------5
42-46------------------2
37-41------------------2
32-36------------------5
26-31------------------2
21-25------------------1

Test 2 will be held on Wednesday, April 7. Here are some sample questions, with solutions.

Bonus problems: In order to earn extra points in the course, write one or more of the following programs:

Ch 2, Programming Problem 2
Write a program to compute the value of the mathematical constant e by using the following formula: e = 1/(0!) + 1/(1!) + 1/(2!) + 1/(3!) + 1/(4!) + ..., where ! signifies the factorial. Write the code to compute e and output the value to the screen, by computing the sum up to the 1/(11!) term. Implement the sum using a loop and a separate factorial function (using either recursion or a loop).
Ch 5, Programming Problem 4b
Ch 6, Exercise 6d (write the actual code, not just pseudocode)

To turn these in, write the code and run and explain your code to me during office hours. These extra credit projects must be completed by WEDNESDAY, APRIL 21 (EXTENSION!).

Instructor	Prof. John Loftin, 309 Smith Hall, Phone: (973)353-3910.
Email	loftin@rutgers.edu Email is the best way to get in touch with me.
Website	http://andromeda.rutgers.edu/~loftin (this syllabus is attached to the website)
Department Website	http://math.newark.rutgers.edu
Prerequisite	Computer Science 102
Who Should Take This Course	This course is required for the Computer Science and Information Systems majors, and for the Computer Science minor.
Course Material (more details are on the Course Schedule)	Recursion Abstract Data Types Linked Lists Stacks and Queues Advanced Java Topics Algorithm Efficiency and Sorting Trees
Text	Carrano & Prichard, Data Abstraction & Problem Solving with Java: Walls and Mirrors, 2nd ed., Addison Wesley
Homework and Quizzes	The homework will be assigned about once a week. It will not be collected, but it will form the basis of the weekly quizzes. Students are encouraged to work together on the homework. Your lowest two quiz grades (including absenses for any reason) will be dropped.
Programs	The language for the programs is Java. There will be 6 programming assignments, which will be assigned about a week in advance. You should write your programs using the `javac` compiler on `pegasus`. You are encouraged to discuss the programs with each other, but YOU MAY NOT COPY ANYONE ELSE'S PROGRAM CODE. The grades for programming assignments will be based mainly on the correctness of the code, but partially on the elegance and proper use of encapsulation in the code. Programs which do not compile will receive no credit.
Exams	There will be two exams during the term and a final exam. The first two exams will be held in class, and will test your knowledge of the material covered in the past few weeks' classes. Exam 1 will be held in class on Monday, February 22. Exam 2 will be held on Wednesday, April 7. The final exam will be held according to the university's schedule, Monday, May 10, 3-6pm. The final exam will be comprehensive. (See the Course Schedule.)
Grades	Your grade will be determined by your quizzes (10%), your programs (20%), Exam 1 (17.5%), Exam 2 (17.5%), and the Final Exam (35%).
Office Hours	M 1:00-2:00, W 11:30-12:30, in 309 Smith Hall. You may see me any time during office hours without an appointment. You may also make an appointment to see me other times.