EECS 233 Assignment #3 (100 points)

Due June 25, 2021 before 11:59pm

Writing Exercises (50 points)

1. Suppose we use a linear probing hashing scheme: h(x) = 2x+3. (10 points)

a) Add the following keys into an empty table of size 11: 8, 14, 12, 7, 15, 11, 23, 17, 6, 2. Show the final table.

b) If we remove 12 and then add 0 to the above table, show the final table.

2. Sort the array [10, 5, 23, 15, 11, 12, 25, 13] using selection sort, insertion sort, and bubble sort, respectively. Show your work step by step. (20 points)

3. Consider a connected undirected graph with N nodes. (20 points)

a) If this graph has the smallest possible number of edges,

i. How many edges does it have with respect to N?

ii. Draw an example of such a graph with N = 6 nodes.

iii. What are such graphs called? (Check the lecture notes for terminology)

b) If this graph has the largest possible number of edges,

i. How many edges does it have with respect to N?

ii. Draw an example of such a graph with N = 6 nodes.

iii. What are such graphs called? (Check the lecture notes for terminology)

Programming Exercises (50 points)

Implement the Sort class with the following static methods:

int[] quicksort(int[] unsortedArray): sort the input array in ascending order using the quicksort algorithm and return the sorted array. Make sure that the algorithm has a O(nlogn) running time in the average case.

int[] mergesort(int[] unsortedArray) sort the input array in ascending order using the mergesort algorithm and return the sorted array. Make sure that the algorithm has a Θ(nlogn) complexity.

Notes regarding the implementation of Sort:

● Using built-in Java classes, is not allowed.

● For debugging purpose, there is a simple test case in main() function, but it does not reflect your scores.

The submissions will be evaluated on completeness, correctness, and clarity. Please provide sufficient comments in your source code to help the TAs read it. Please generate a single zip file containing all your *.java files needed for this assignment and optionally a README.txt file with explanation about added classes and other extra changes you may have done.

Grading:

• Quicksort() and mergesort() implementation: 20 points each

• Design and style: 10 points

o Style: 3 points. Are variable names descriptive and convey their purpose? Of course, simple concepts like a loop variable do not require descriptive names; e.g., it is perfectly fine, even preferable, to use i for a loop variable. Is formatting clear and consistent?

o Comments: 4 points. Comments should aid the reader to understand the code. Comments that restate what is already clear from the code are redundant and not helpful. Nor are comments that are not consistent with the code. For each method implementation, state in the comments its worst-case running time.

o Design: 3 points. Are there lines that never execute? Inelegant constructions? Convoluted or unnecessarily inefficient ways to achieve some result?

Submission Guidelines

Written part: submit all your solutions in the form of a PDF file to Canvas. You can either type them up or write on a piece of paper and scan them. If you choose the latter, please make sure that your handwriting is clear and readable. Name your file as W3_YourCaseID_YourLastName.pdf

Programming part: Please generate a single zip file containing all your *.java files needed for this assignment and optionally a README.txt file with explanation about added classes and other extra changes you may have done. Name your file as P3_YourCaseID_YourLastName.zip

Notice: Please do not zip W3 and P3 together, since it will prevent TAs from grading online.