CS 372-Tentative outline for homework assignments
Homework due Sept. 8
.Create graphs in your favorite medium that show growth of n,n log n, and n*n, from 1 to 12
n*n, n*n*n, 2^n from 1 to 11
n*n*n, 2^n, and n! from 1 to 6
p. 8, #5,#4p.17 #1.
Sept. 10
p. 18 #5, #9, p. 25 #8, p. 38 #2#,3
Sept. 15:
On the Unix machine implement the matrix multiplication algorithm on p. 64 as given to form C=AB and time (see website) it on Unix with n=200,400,600. If too big in C++ use the new operator. Revise the algorithm to do C=A(transpose)B and C=AB(transpose) and run on the Unix machine. Note to use A(transpose) in the formulae for a[i][j] use a[j][i].
Repeat the exercise but when compiling use
g++ file.cpp –O2
to turn on the optimizer
The operation count is the same.
a. Are the times the same
b. Does it matter whether one dimensions the array precisely to n or if one imbeds C,A, and B in a larger dimension matrix?
c. What is the order of the operation count?
d. What is the time to compute one column of C?( you may want to put it in a loop run 100 times) to get significant results.
e. What is the order of the operation count?
f. Suggest one way to speed up the computation for the matrix-matrix multiply and try out your idea
p. 51 #2
Sept. 17:
p. 51 #7,#8, p.67-#1
Sept. 22
p69 - 9,10, Worksheet on Recursive functions
Read Appendix B.
\
Sept. 24
76- 1, 4,7,10
Sept. 29- No class
Oct. 1 Review for Quiz
Worksheets on Operation counts
Oct. 6: Quiz1
Oct.8 No class Yom Kippur
Homework for Oct. 13
p.102-4,5,8,9b.
Oct.15-
p.106-5, 8
p.112 – 5,6
p119 1,4
Homework Oct. 20
p. 128 1,5,6
p. 134 1,5
Oct. 22
p.139 4,7
143 2,4,5
Oct. 27
163-4, 10a
170-1,4,9
Oct.29
176-1,5
187-3
Nov.3
p. 201-2
p.212-1,5
p.222 1,4
p. 229 1,3a,5
Nov. 5- Quiz 2
Homework for Nov.12
Programming project: 230-10
Homework for Nov. 17
Worksheet on string matching and 270-1,2, 276 6a
Homework for Nov. 19:
292-1,7
Homework Nov.24:
314 7b, 322 1b, 323 2b
Do either 1 or 2
(1) Solve the n- queens problem in your favorite language and determine the time it takes to solve the problem for n=8,9,10,11,12,13,14 and plot the time as a function of n.
(2) Prepare a 5 minute oral presentation on one of the main problems for one of the fundamental problems in combinatorial algorithms. A good starting point is http://www.cs.sunysb.edu/~algorith/ and click on Graphics gallery and pick one of the problems.
You may do both for extra credit- good job raises midterm by 20 points
Please tell me your choice by Nov. 17
Dec. 1- Read Ch. 11, P. 401-#20