Goal: Work through a set of paper-and-pencil style problems you might see on the subjects we’ve covered and topics you’ve seen in the past. This should prepare you for in-class tests and technical interviews, while reinforcing the topics.

Activity: Complete the following questions on paper and upload your answers to GradeScope.

Teamwork: None, this is a solo assignment.

Details

See overview of written homework assignments from Homework 2.

New-Item Questions

Graded, but not on correctness. You must show your work for points.

1. [1pts] Showing your scratch work (like we did in class), perform a counting sort where k = 0..6 on the following numbers: 1, 4, 2, 6, 0, 5, 1, 4

2. [1pts] Using the image shown below as a model, illustrate the operation of radix sort on the following English

words (using alphabetical order): TOT, SIT, SAT, SAY, SOY, ROY

3. [2pts] In the analysis of quick sort we did in class, we went from this:

Answer/explain in your own words (typed into GradeScope):

a)   What does the E[] mean?

b)   How do we get from the first equation to the second equation?

At a minimum, please address: Where did the E[] go on the right hand side? And where did the Pr{} come from? And what does zi  and zj  have to do with xij? etc.

Review-Item Questions

Graded based on correctness. You only need to show your work if asked.

We’ve done a lot of graph algorithms in CS483. Below is some review of several non-flow algorithms we’ve learned this semester. As an exercise, try to do these without looking at your notes first.

1. [1pts] Perform a depth first traversal of the graph shown below starting a Node 2 and breaking ties by choosing the lowest ID first. Write the order nodes are visited and finished below. Restart at the

lowest ID node not yet visited until all nodes are visited and finished.

Visiting order:

Finishing order:

2. [1pt] Perform a breadth first traversal of the graph from Review Problem 1 starting a Node 2 and breaking ties by choosing the lowest ID first. Write the order nodes are entered into the queue and their parent ID below that (e.g. if node 0 comes out of the queue first, you write 0 in the for queue order, and write its parent on the immediately below). Restart at the lowest ID node not yet visited until all nodes are visited.

Queue order:

Parent IDs:

3. [1.5pts] If we do Bellman-Ford’s Shortest Path Algorithm on the graph in Review Problem 1 starting a Node 2:

a.   What does the first row of the table look like?

Answer:

b.   What does the last row of the table look like?

Answer:

c.   For the parallelizable algorithm, how many rounds/passes are needed to stop

(initialization does not count as a round/pass in this case)?

Answer: