Todo

type: AV

To make students more engaged in the GrowthRates exercise, we may need a tool that allows students to input two growth rate functions. Then the tool should plot the graph of both functions and mark their crossing point. The student also should be allowed to play with the constant values for both functions and see that this only changes the crossing point but doesn’t change which function grows faster than the other.

Todo

type: AV

Fix and return hashAV.html to here.

The following visualization lets you test out different combinations of hash function and collision resolution, on your own input data.

Todo

type: AV

Provide a unified AV that can allow the user to pick which topsort (DFS or Queue), with or without cycles in the graph. The start of this is in AV/Development/TopSort/topSortAV* (for just random DFS), AV/Development/TopSort/qTopSortAV.* (for just random queue-based topsort), and AV/Development/TopSort/topSortAVs* (tries to unify).

Todo

type: AV

Provide an AV that runs on a random graph. An initial version is in AV/Development/TopSort/dijkstraAV.*.

Todo

type: AV

AV here to demonstrate the minVertex implementation.

Todo

type: AV

Add version where you can click to get the node inserted.

Todo

type: AV

Make a proper visualization for perfect hashing, that lets the user specify a set of input keys, computes the hash function, then lets the user input keys to the table. A proper explanation for the process should be part of the visualization.

Todo

type: AV

Practice fft algorithm. Maybe only practice the final for loop since the rest of the algorithm is recursivly dividing the polynomial and performing fft on the smaller polynomials.

Todo

type: BlockPy

Put first BlockPy exercise here.

Todo

type: BlockPy

Put second BlockPy exercise here.

Todo

type: BlockPy

Put third BlockPy exercise here.

Todo

type: Code

Why does the code look for an unvisited value first? Is there an easier way?

Todo

type: Diagrams

Look at Susan’s original notes (sectcomdes) to see what these are supposed to look like (she used cline to help build boxes, but MathJax cannot support it).

Todo

type: Equation cross-reference

Throughout this module, there are references to equations, both on this page and in the Summations module. These should be made into proper cross-references rather than hard-coded equation numbers.

Todo

type: Exercise

This exercise ought to get expanded to a much richer set of variations on the question.

Todo

type: Exercise

Need exercises for inserting to and deleting from doubly linked lists.

Todo

type: Exercise

Battery of MCQs for content.

Todo

type: Exercise

Consider the Quicksort implementation for this module, where the pivot is selected as the middle value of the partition. Give a permutation for the values 0 through 7 that will cause Quicksort to have its worst-case behavior.

There are a number of possible correct answers. To assess the answer, will need to run Quicksort over student’s partition, and verify that at each step it will generate new partitions of size 6, 5, 4, 3, 2, then 1.

Todo

type: Exercise

This is a good question, but its not nearly enough for a chapter summary.

Todo

type: Exercise

Add a battery of questions to test knowledge of the implementations.

Todo

type: Exercise

Summary exercise for graph traversals.

Todo

type: Exercise

Summary battery of questions for Dijkstra’s algorithm

Todo

type: Exercise

Proficiency exercise for Prim’s algorithm.

Todo

type: Exercise

Summary battery of questions for Prim’s and Kruskal’s algorithms.

Todo

type: Exercise

Need an exercise to study lower bound on Colletz function

Todo

type: Explanation

The slideshow should subsume the next paragraph and the caption.

Todo

type: Figure

Replace this figure with an applet that demonstrates the use of handles.

Todo

type: Figure

Put the figure here that was specified in the original document (top of the 3rd page), showing the recursion tree.

Todo

type: Figure

Show figure

Todo

type: Proficiency Exercise

Provide a proficiency exercise that randomly alternates between proficiency for DFS-based and queue-based Topsort. The bare beginnings of an exercise can be found in AV/Development/TopSort/topSortDFSPE.*

Todo

type: Revision

Rewrite along these lines: Here are two measures of “out of order”: inversions and min-swaps. Selection sort (especially w/ optimization) meets min-swaps, but that’s not a useful measure in general. Insertion sort tracks inversions, it is I + n. Now, if we had an exchange sort, what would cost be? Go on to the proof.

Todo

type: Revision

Rewrite along these lines: A classic form of code tuning is “test to save work”. For each of our three sorting algorithms, we have a potential “test to save work” “optimization”. The question is: When is the cost of test worth the work saved? Let’s look at each of the three.

Todo

type: Slideshow

We need to think about a technique for visualizing the running time of some loop constructs. This can be very similar to how we visualize reaching the closed form solution of summations.

Todo

type: Slideshow

The figure above and the following text should all be rolled into a slideshow.

Todo

type: Slideshow

Replace this figure with a slideshow that demonstrates the use of reference counts (including the problem with cycles).

Todo

type: Slideshow

Put here a visualization that demonstrates the use of reference counts.

Todo

type: Slideshow

Replace this figure with an AV that demonstrates DSW.

Todo

type: Slideshow

Replace the above figure with a slideshow that incorporates the following paragraph.

Todo

type: Slideshow

Replace the following paragraph with a slideshow.

Todo

type: Slideshow

Incorporate the following into a slideshow.

Todo

type: Slideshow

Incorporate the following paragraph into a slideshow with the figure below it.

Todo

type: Slideshow

Provide a slideshow to demonstrate the following example.

Todo

type: Slideshow

This slideshow illustrates Dijkstra’s algorithm using the heap. The start vertex is A. All vertices except A have an initial value of \(\infty\). After processing Vertex A, its neighbors have their D estimates updated to be the direct distance from A. After processing C (the closest vertex to A), Vertices B and E are updated to reflect the shortest path through C. The remaining vertices are processed in order B, D, and E. Changes in the D array should be shown along with this.

Todo

type: Slideshow

Slideshow to demonstrate the relative costs of the two algorithms.

Todo

type: Slideshow

Replace the previous diagram with a slideshow illustrating the concept of MCST.

Todo

type: Slideshow

Implement a slideshow demonstrating the Priority Queue version of Prim’s algorithm

Todo

type: Slideshow

Slideshow of Book Figure 6.16: shows full and complete Karytrees for K=3. In practice, most applications of Karytrees limit them to be either full or complete.

Full and complete 3-ary trees. (a)~This tree is full (but not complete). (b)~This tree is complete (but not full).}{ThreeTree}

Todo

type: Summary Questions

Provide a summary battery of questions.

Todo

type: Text

Where did that last claim about the linear probing cost come from?

Todo

type: exercise

We need a proficiency exercise.

Todo

type: text

Give an example of this type of representational change.

Todo

type: text

Explain how Perfect Hashing works.