CS 105 Introduction to Data Structures and Algorithms
2nd Semester, 20072008
Instructors:
Andrei Coronel
Jal De Vera
Sheryl Lim
John Paul Vergara
Syllabus
DISCS Policies on Academic Integrity and Lab Use
Announcements
 Project 2 DRAFT SPECS ON THE BST PROJECT NOW OUT!.
See Projects section below.
 Project 1 DRAFT specs have been posted.
See Projects section below.
 Files (UPDATED December 3, 5pm!)
to be used for your first assignment.
Consult your instructor for instructions and submission details.
 Welcome to this website! Visit this link regularly for
course material, announcements and updates
Homework
 HW 1 (Due Friday, Dec 7, midnight for sections under Vergara;
Section A under Lim: consult your instructor)
Instructions:
 Download PolyEval.java and input.txt .
The program demonstrates polynomial evaluation.
 The method evalPoly1() is an O(n^2) algorithm that evaluates
a polynomial P on a value a.
Fill in the code for evalPoly2() to come up with a better (lineartime)
polynomial evaluation algorithm.

Provide the running times for evalPoly1() and evalPoly2() (your algorithm).
Your answers must be in terms of n (where n is the degree of the polynomial).
You should count assignments, additions, multiplications,
comparisons, array accesses, and return statements.
Note that an increment counts as two operations: an addition and an assignment.
Subtractions and decrements (if applicable) count as additions or increments.
Place your answers in a HW1.doc or HW1.txt file.
Show your solutions.

Submit the revised PolyEval.java and the text or word document in a zip file.
You may work in pairs.
The zip file should contain the names of the members, e.g.,
HW1Lastname1Lastname2.zip.
Submit via moodle .
You will be graded according to how well your algorithm compares
against the current algorithm. Take note of the output of PolyEval.java.
Tips:
 After executing PolyEval, type the following command:
fc output1.txt output2.txt
to check if your polyEval2() method is correct.
Note: PolyEval.java has been updated since class time on Monday
to ensure the outputs matchthe line
out.println( ans );
has been updated with the lines
out.printf( "%.5e", ans ); out.println();
 Research on Horner's rule .
It provides an efficient lineartime polynomial evaluation algorithm.
Projects
Slides
Links