Computer Science 431
Algorithms

Spring 2015, The College of Saint Rose

Home     Syllabus     Schedule

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.

1. 5n² + 2n + 5 and n²
2. nlogn and n²
3. 2^logn and n
4. 2ⁿ and 2²ⁿ
5. n^r and n^s, where r and s are arbitrary fixed constants such that r > s > 0.

1. n ∈Ω(logn)
2. 5n + 6 ∈Θ(n)
3. n logn ∈Ω(n)
4. n ∈Θ(n - n^1/2)

1. 1/n + 12
2. (sin  n)/n

1. 762n² - 56n + 37
2. (n³ + 100)⁵
3. n logn, use g(n)=n²

1. 762n² - 56n + 37
2. 2ⁿ + n²
3. n logn, use g(n)=n

1. 762n² - 56n + 37 (hint: you've already done this, just bring it all together)
2. n⁴ + 50n² - 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: