CS 105 Introduction to Data Structures and Algorithms
2nd Semester, 2007-2008
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 (linear-time)
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.,
HW1-Lastname1-Lastname2.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 match--the 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 linear-time polynomial evaluation algorithm.
Projects
Slides
Links