Computer Science 385
Design and Analysis of Algorithms

Spring 2017, Siena College

Home     Syllabus     Schedule

You may work alone or with a partnet 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 homework set if you wait until the last minute. A slow and steady approach will be much more effective.

This assignment has 103 points available, but the maximum score is 100. So you can get 3 points off and still earn a "perfect" 100.

Programming Task: Exhaustive Search

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. If you would like to use a language other than Java, ask, and it will likely be approved. (10 points)

Programming Task 2: A New Graph Method

In an undirected graph, such as the HighwayGraph from Lab 2, the degree of a vertex is the number of adjacent (undirected) edges.

1. Download a new copy of the HighwayGraph.java starter you used for Lab 2.
2. Add a new method that computes the degree of the vertex with a given number. So the method call added in main:

     int d = g.degree(12);
   

   would compute and return the degree of vertex 12 and store it in d (4 points).

3. Remove the System.out.println(g); line from the given main method.
4. Add code in main that finds the largest degree of all the waypoints (vertices) in the graph, and then prints out a line containing the name of the input graph file, the largest degree, and the vertex label where you found that largest degree (4 points).

Print and attach or paste into your submission your new degree method, the code you added to the main method, and your program's output on the DC-all.tmg, NY-all.tmg, and tm-master.tmg graphs.

Programming Task: Generating Example Arrays

In future homework sets, you will be asked to perform empirical analysis on the sorting algorithms we will be studying. As part of that task, you will be required to generate input arrays for the sorting algorithms. In order to test the best, worst, and average cases of some of these algorithms, you will need to generate input arrays with various characteristics. For simplicity, we will sort arrays of int.

• an array filled with n random values within a given range
• an array filled with n values sorted in ascending order
• an array filled with n values sorted in descending order
• an array filled with n values "nearly" sorted in ascending order

You may use any programming language. If you use Java, implement it within a class IntArrayGenerator that includes static methods to generate and return arrays of int with each of the above characteristics, and a main method that tests these methods for various values of n and ranges. Be sure you can achieve similar functionality if you choose a different language. It is important that you generate these efficiently - for example, you should not generate sorted input by generating random input then sorting it. Generate it in sorted order right from the start. (10 points)

Homework 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.

b. nlogn and n²

c. 2^logn and n

d. 2ⁿ and 2²ⁿ

e. n^r and n^s, where r and s are arbitrary fixed constants such that r > s > 0.

b. 5n + 6 ∈Θ(n)

c. n logn ∈Ω(n)

d. n ∈Θ(n - n^1/2)

b. (sin  n)/n

b. (n³ + 100)⁵

c. n logn, use g(n)=n²

b. 2ⁿ + n²

c. n logn, use g(n)=n

b. n⁴ + 50n² - 23

for ( i = 1; i <= n; i++ )
    System.out.println("Hello!");
    System.out.println("Hello!");
    for ( j = 1; j <= i; j++ ) {
        System.out.println("Hello!");
    }
}

a. Trace the code to count how many times it prints Hello! for both n=2 and n=3.

b. Write an expression involving two summations that counts the number of times it prints Hello! for any value of n.

c. Simplify your expression to get a closed form formula for the number of times it prints Hello! Show your work.

d. Check your formula from part c by substituting n=2 and n=3 to see if it matches your answers for parts a and b.

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

// A[0..n-1] is an array of n prices.  This algorithm returns true if 
// there are two distinct prices that sum to 1000, and false otherwise.
ALGORITHM GiftCertificate( A[0…n-1] )

a. If you have a graph with 1,000,000 vertices and each vertex has 4 outgoing edges, exactly how much memory in gigabytes is needed to store the graph using each representation? For each representation, can it fit into 16GB of main memory which is typical of a PC today?

b. Graphs that have only a few number of edges per vertex are known as sparse graphs. A graph with a high number of edges per vertex is said to be dense. Suppose you have a complete directed graph of 1,000,000 vertices meaning that every vertex has a directed edge to all the other vertices. This is the "densest" graph there is! Exactly how much memory is needed to store the graph using each representation? Express your answer in gigabytes.