Computer Science 431

Algorithms

Spring 2015, The College of Saint Rose

You may work alone or in groups of size 2 or 3 on this assignment. However, in order to make sure you learn the material and are well-prepared for the exams, you should work through the problems on your own before discussing them with your group members, should you choose to work in a group. Only one submission per group is needed.

There is a significant amount of work to be done here, and you are sure to have questions. It will be difficult if not impossible to complete the problem set if you wait until the last minute. A slow and steady approach will be much more effective.

Getting Set Up

Create a directory/folder for your work on this problem set. As you prepare your solution to the written problems, you are encouraged, but not required to use LaTeX. Ultimately, be sure your solutions are in a single PDF file. Place all code for programming tasks in this folder.

Programming Task

Sometimes an exhaustive search algorithm considers all permutations of
a set. It is not obvious though how to generate these permutations in
a program. Write a program that prints all permutations of integers
1..*n*. Your program should take *n* as an input value, and it should
work for any *n >= 1*. You may write your program in Java, C, or C++.
If you would like to use a different language, ask, and it will likely
be approved. (10 points)

Problem Set Problems

See the PDF version of this document for a more readable version of this part of the assignment, as the HTML rendering of these kinds of equations is poor in some cases and improving it is more trouble than it's worth.

*5n*and^{2}+ 2n + 5*n*^{2}*nlogn*and*n*^{2}*2*and^{logn}*n**2*and^{n}*2*^{2n}*n*and^{r}*n*, where^{s}*r*and*s*are arbitrary fixed constants such that*r > s > 0*.

*n*∈Ω*(logn)**5n + 6*∈Θ*(n)**n logn*∈Ω*(n)**n*∈Θ*(n - n*^{1/2})

*1/n + 12**(sin n)/n*

*762n*^{2}- 56n + 37*(n*^{3}+ 100)^{5}*n logn*, use*g(n)=n*^{2}

*762n*^{2}- 56n + 37*2*^{n}+ n^{2}*n logn*, use*g(n)=n*

*762n*(hint: you've already done this, just bring it all together)^{2}- 56n + 37*n*^{4}+ 50n^{2}- 23

for ( i = 1; i <= n; i++ ) for ( j = 1; j <= n; j++ ) { for ( k = 1; k <= Math.pow(2,j); k++ ) { System.out.println("hello"); } System.out.println("hello"); }

Note: you may test your formula by implementing this code and then
running it for different values of *n*.

Submitting

Before 11:59 PM, Friday, February 6, 2015, submit your problem set for
grading. To complete the
submission, upload an archive (a `.7z` or
`.zip`) file containing all required files using
Submission
Box under assignment "PS2".

Grading

This assignment is worth 50 points, which are distributed as follows:

> Feature | Value | Score |

Permutation Generator Program | 10 | |

Question 1 | 4 | |

Question 2 | 2 | |

Question 3 | 5 | |

Question 4 | 4 | |

Question 5 | 2 | |

Question 6 | 6 | |

Question 7 | 6 | |

Question 8 | 5 | |

Question 9 | 6 | |

Total | 50 | |