| Due Date |
Assignment |
| Thursday, April 9
|
- Write a nonrecursive implementation in C++ of the partition based
algorithm for the selection problem (see #3a on page 194). Your
program should implement the Partition algorithm for Quicksort (page 131)
as a function and use it in the selection program. Your algorithm
for the selection problem should take an array of integers and
a positive integer k and return the kth smallest element. Write the
program so that it reads in the number of integers followed
by each integer in the list, then the value of k.
- Be sure to properly document your program.
- Tar your program up with at least 3 test files you used to test
the program. Send the tar file as an attachment in an email.
|
| Wednesday, April 8
|
- Redo #3 on page 187. Be sure your algorithm clearly indicates
what you are weighing.
- Section 8.2 (page 292) Do #1, 6, 7
|
Tuesday, April 7
by 4:00 pm
|
- Re-write your program for the partition problem (#6 page 119).
Your program should not generate an excessive number of sets.
Write your program so that it first reads the number of integers
in the set then reads in each integer.
- Write a separate document (or include this in the documentation
of the program) that clearly explains your algorithm in English.
It should make clear what your set generating strategy is and it
should make clear how that strategy helps minimize the number of
subsets you generate.
|
| Friday, April 3
| Page 264, #1, 2, 3, 4, 6
|
| Wednesday, April 1
| Page 187 #3, page 194 # 1, 2, 3, 5
|
Thursday, Mar. 26
by 4:00 p.m.
| Write a C++ program that implements the Quickhull algorithm.
Click here for details.
|
| Monday, Mar. 30
| Re-writes on #4 & 6 on page 176,
|
| Friday, Mar. 13
|
Do Lab #3. Everyone must do
the starred exercises. Note that you are to send a tar file
of your work in an email. There are some questions in the
lab you must answer.
|
| Wednesday, Mar. 11
|
- Problems # 7 & 8 on page 154.
- Think about classes needed to implement quickhull.
|
| Friday, Feb. 27
|
- Mathematical Analysis Problems (handed out in class) - posted
on Blackboard if you need a new copy.
- C++ program to implement the convex hull algorithm discussed
in Section 3.3 of the text (this is problem #9 on page 113). Your
program should read in a set of points from a file (assume the
points will have nonnegative integer coordinates). Read until the
end of the file. The program should output a list of endpoints
for the line segments making up the boundary of the convex hull.
- C++ program solve the partition problem (problem #6 on page 119).
|
| Friday, Feb. 20
|
- Write a C++ program to compute the variance using the two
different formulas given in problem #3 on page 67. As described
in the problem, count the number of additions/subtractions, number
of multiplications, and the number of subtractions for each.
Compare!
The files varianceData1.in and
varianceData2.in can be used to
test your program. The variance for the first data file is
36345.1 and the variance for the second is 0.727204.
- Complete the solutions to the recurrence relation
exercises.
|
| Monday, Feb. 16
| Find the characteristic roots for the second order linear
homogeneous recurrence relations on the
exercise sheet.
|
| Friday, Feb. 13
|
|
| Friday, Jan. 16
|
Read Sections 1.1 - 1.3;
Hand in problems #4, 5, 7, 9, 11 on pages 8-9;
#2 (describe your thinking process in addition to
giving a solution), #7, 9
|