CS 3510: Algorithms

Assignment 0

Assignment

Problems identified by x.y(z) denote the problem “y”, in chapter “x” of the textbook, with part “z”. If “z” is not noted, then the entire problem is required.

Assignment 0a

0.1(a, b, c, d, e, f) In each case show your derivation.
0.2(b) Show your derivation.

Assignment 0b

0.1(g, h, i, j, k, l) In each case show your derivation.
0.2(a) Show your derivation.
Complete the tasks for Programming Assignment fib1.

Assignment 0c

0.1(m, n, o, p, q) In each case show your derivation. Prove o, don’t just quote the known result. Don’t spend too much time on q.
0.2(c,) Show your derivation.
Complete the tasks for Programming Assignment fib2.

Programming Assignment fib1

Create a directory in your repository name 00-fibonacci to store your work for this task.
Implement fib1 from the textbook in fib1.cpp.
Experimentally determine the running time of the fib1. Use best practices for eliminating granularity and fluctuation errors.
Build a table of running times for n=1 through 40.
Add columns for theoretical complexities, log(n), n, n^2, and 2^n.
Make a graph of the running times. The x-axis should be n and the y-axis should be the number of seconds to calculate the number. Use log scale on the y-axis. If the run times do not produce a relatively smooth graph, you may need to improve your error elimination techniques.
Save the table in fib1-table.pdf.

Programming Assignment fib2

Implement fib2 from the textbook.
Experimentally determine the running time of the fib2. Use best practices for eliminating granularity and fluctuation errors.
Add a column to the table of running times for fib2.
Normalize the fib1, fib2 running times, and theoretical complexities for comparison.
Make the graph use the normalized values.
Save the table in fib1-fib2-graph.pdf.

Submission

Submit you solutions by the due date and time. For written problems, your work and answers as a PDF to Canvas. For code, submit the source code and required files to the class git repository.

Last Updated 01/08/2024