You are probably being recorded (and transcribed)
Approximate overview
If you’d like to suggest token events, please let me know in advance of class.
Suppose we have a collection of values. Each value can be red, white, or blue. We want to rearrange them (in place) so they are in the order all the reds, then all the whites, then all the blues.
We’re going to have a section of reds, a section of whites, a section of blues, and an unprocessed section.
RWBU invariant
+------------+-------------+-------------+-------------+
| Red | White | Blue |XUnprocessed |
+------------+-------------+-------------+-------------+
| | | |
r w b n
RWUB invariant
+------------+-------------+-------------+-------------+
| Red | White |XUnprocessed | Blue |
+------------+-------------+-------------+-------------+
| | | |
r w b n
Goal: Get the first remaining unprocessed element into the right section in constant time. If it’s constant time, our DNF algorithm will be \(O(n)\).
What loop does this suggest? That is, what does your loop body look like so that you maintain the invariant?
Loop with RWBU invariant
int r = ...;
int w = ...;
int b = ...;
while (b < n) {
// +------------+-------------+-------------+--------------+
// | Red | White | Blue |X Unprocessed |
// +------------+-------------+-------------+--------------+
// | | | |
// r w b n
if A[b] is Red
// +------------+-------------+-------------+--------------+
// |R Red R|W White W|B Blue B|R Unprocessed |
// +------------+-------------+-------------+--------------+
// | | | |
// r w b n
swap(A, r, w);
// +------------+-------------+-------------+--------------+
// |R Red R|B White W|W Blue B|R Unprocessed |
// +------------+-------------+-------------+--------------+
// | | | |
// r w b n
swap(A, r, b)
// +------------+-------------+-------------+--------------+
// |R Red R|R White W|W Blue B|B Unprocessed |
// +------------+-------------+-------------+--------------+
// | | | |
// r w b n
r++;
w++;
b++;
// +--------------+-------------+-------------+------------+
// |R Red R R| White W W| Blue B B|Unprocessed |
// +--------------+-------------+-------------+------------+
// | | | |
// r w b n
else if A[b] is White
// +------------+-------------+-------------+--------------+
// | Red | White |B Blue |W Unprocessed |
// +------------+-------------+-------------+--------------+
// | | | |
// r w b n
swap(A, w, b);
// +------------+-------------+-------------+--------------+
// | Red | White |W Blue |B Unprocessed |
// +------------+-------------+-------------+--------------+
// | | | |
// r w b n
w++;
b++;
// +------------+---------------+-------------+------------+
// | Red | White W| Blue B|Unprocessed |
// +------------+---------------+-------------+------------+
// | | | |
// r w b n
else // if A[b] is Blue
// +------------+-------------+-------------+--------------+
// | Red | White | Blue |B Unprocessed |
// +------------+-------------+-------------+--------------+
// | | | |
// r w b n
b++
// +------------+-------------+---------------+------------+
// | Red | White | Blue B|Unprocessed |
// +------------+-------------+---------------+------------+
// | | | |
// r w b n
} // while
// +------------------+-------------------+------------------+
// | Red | White | Blue |
// +------------------+-------------------+------------------+
// | | |
// r w b
How should we initialize r, w, and b to ensure the invariant?
// +------------+-------------+-------------+--------------+
// | Red | White | Blue |X Unprocessed |
// +------------+-------------+-------------+--------------+
// | | | |
// r w b n
// +---------------------------------------------------------+
// | Unprocessed |
// +---------------------------------------------------------+
// |
// r,w,b
r = 0;
w = 0;
b = 0;
Nothing before r, so everything before r is red.
Nothing between r and w, so everything between r and w is white.
Etc.
Does the algorithm work correctly if there are not yet any red elements?
// +------------------+-------------------+------------------+
// |W White |B Blue |? Unprocessed |
// +------------------+-------------------+------------------+
// | | | |
// r w b
Yes. Analysis below.
If ? is red
B White W Blue RR White W Blue BIf ? is white
If ? is blue
Does the algorithm work correctly if there are not yet any white elements?
// +------------------+-------------------+------------------+
// |R Red R|B Blue B|? Unprocessed |
// +------------------+-------------------+------------------+
// | | |
// r,w b
Yes. Analysis follows.
If ? is W, swap(w,b) and then increment w and b.
(Alternately, swap(w++,b++).
If ? is B, we just advance the blue pointer.
If ? is R, swap(r,w), which has no effect. And then swap(r,b) which puts a B after b and an R after r (and w). We then increment all three. And we still have the invariant.
Observation: w >= r because whenever we increment r we also increment w.
(There are times we increment w but don’t increment r.)
(And we always increment blue.)
Does the algorithm work correctly if there are not yet any blue elements?
// +------------------+-------------------+------------------+
// |R Red R|W White W|? Unprocessed |
// +------------------+-------------------+------------------+
// | | |
// r w,b
No. Analysis follows.
If ? is B, we just increment B and everything is fine.
// +------------------+-------------------+-+----------------+
// |R Red R|W White W|B| Unprocessed |
// +------------------+-------------------+-+----------------+
// | | | |
// r w b
If ? is W,
// +------------------+-------------------+------------------+
// |R Red R|W White W|W Unprocessed |
// +------------------+-------------------+------------------+
// | | |
// r w,b
we swap elements at w and b, which has no effect, and then increment both.
// +------------------+---------------------+----------------+
// |R Red R|W White W W| Unprocessed |
// +------------------+---------------------+----------------+
// | | |
// r w,b
If ? is R
// +------------------+-------------------+------------------+
// |R Red R|W White W|R Unprocessed |
// +------------------+-------------------+------------------+
// | | |
// r w,b
We swap elements at r and W
// +------------------+-------------------+------------------+
// |R Red R|R White W|W Unprocessed |
// +------------------+-------------------+------------------+
// | | |
// r w,b
We swap elements at r and b.
// +------------------+-------------------+------------------+
// |R Red R|W White W|R Unprocessed |
// +------------------+-------------------+------------------+
// | | |
// r w,b
We increment all three indices.
// +--------------------+-------------------+----------------+
// |R Red R W| White W R| Unprocessed |
// +--------------------+-------------------+----------------+
// | | |
// r w,b
Whoops!
If the answer to any of those is “No”, how do we fix the algorithm?
The algorithm fails if we don’t have any blue elements and the next element is red.
Solutions …
w == b, only do one swap.
swap(w,b) then swap(r,w).
Reminder: Pictorial invariants are our friends.
Question: For the RWBU, is a three-way-rotate better than two swaps?
Merge sort:
Merge algorithm (high level)
The merge algorithm is \(O(n)\) because we are going to go through the whole result array to copy elements into it.
Analyzing Merge sort
Let’s start by writing the recurrence relation. We are defining \(T(n)\), the time merge sort takes on \(n\) elements.
\(T(n)\) =
Recurrence relation
\[T(n) = 2 \times T(n/2) + n + c\] \[T(1) = c\]Yay! We get to solve a recurrence relation.
Our recursion tree plus some extra math show us that merge sort is in \(O(n log_2 n)\).
Can we do better?
Three key ideas:
With a real median.
\[T(n) =\]IF we can find the median in O(1) (or even O(n)), this is an \(O(n log_2 n)\) algorithm.
Traditional way to find the median: Sort the array and look in the middle. Whoops!
Additional key idea in Quicksort: If you pick a random element of the (sub)array, things will usually work out almost as well as if you picked the real median. (Sam does not like to do the statistical analysis.)
A tip: DNF should probably return both the red and white indices (the end of the small section and big section).
public int[] dnf(T[] values, int lb, int ub, Comparator<T> order) {
int r = 0;
int w = 0;
int b = ...;
...
return new int[] {r, w};
} //
public void quicksort(T[] values, int lb, int ub) {
...
int[] bounds = dnf(values, lb, ub, ...);
quicksort(lb, bounds[0]);
quicksort(bounds[1], ub);
} // quicksort
Given that you have not been returning graded MPs promptly, do you anticipate changing the MP requirements for A/B/C?
Yes. However, I’m still figuring that out.
Will you be gracious if we don’t get our token reflections in within 72 hours of the event.
Probably.
Should we work with our partners in resubmitting group MPs
Ideally.
Is there a stable version of Quicksort?
I don’t know of a stable in-place version of Quicksort. The partition routine rearranges things too much.
In merge sort, we’ll need to make helper arrays. Where should we do that?
I would use a helper array for the merge, but just use subarrays (given by
lbandub) for the recursive calls.
If you use this technique, you only need one helper array.
https://www.acm.org/code-of-ethics
We will read these aloud so that we reflect a bit more about each.
Next, we’ll move on TPS questions.
Modified from https://ethics.acm.org/code-of-ethics/using-the-code/case-dark-ux-patterns/. (Please don’t look there for analysis.)
The change request Stewart received was simple enough: replace the web site’s rounded rectangle buttons with arrows and adjust the color palette to one that mixes red and green text. But when Stewart looked at the prototype, he found it confusing. The left arrow suggested that the web site would go back to a previous page or cancel some action; instead, this arrow replaced the button for accepting the company’s default product. The right arrow, on the other hand, upgraded the user to the more expensive category; it also silently added a protection warranty without asking for confirmation. Stewart suggested to his manager that this confusing design would probably trick users into more expensive options that they didn’t want. The response was that these were the changes requested by the client.
Shortly after the updates were released into their production system, Stewart’s team was invited to a celebration. As a result of these changes, revenues at their client had increased significantly over the previous quarter. At the celebration, Stewart overheard some of the client’s managers discussing the small increase for refunds by users who claimed that they didn’t want the protection plan, but there weren’t many. One manager noted several complaints from visually impaired users, who noted that the mixture of red and green text obscured important disclaimers about the product. “So what you’re saying, then, is that the changes worked as planned,” quipped one of the managers.
TPS: What should Stewart do (or have done)? What ACM principles are relevant?
I doubt we’ll have time to cover this one.
Modified from https://ethics.acm.org/code-of-ethics/using-the-code/case-malware-disruption/. Please don’t read the analysis.
Rogue Services advertised its web hosting services as “cheap, guaranteed uptime, no matter what.” While some of Rogue’s clients were independent web-based retailers, the majority were focused on malware and spam. Several botnets used Rogue’s reliability guarantees to protect their command-and-control servers from take-down attempts. Spam and other fraudulent services leveraged Rogue for continuous delivery. Corrupted advertisements often linked to code hosted on Rogue to exploit browser vulnerabilities to infect machines with ransomware.
Despite repeated requests from major ISPs and international organizations, Rogue refused to intervene with these services, citing their “no matter what” pledge to their customers. Furthermore, international pressure from other governments failed to induce national-level intervention, as Rogue was based in a country whose laws did not adequately proscribe such hosting activities.
Ultimately, Rogue was forcibly taken offline through a coordinated effort from multiple security vendors working with several government organizations. This effort consisted of a targeted worm that spread through Rogue’s network. This denial-of-service attack successfully took Rogue’s machines offline, destroying much of the data stored with the ISP in the process. All of Rogue’s clients were affected. No other ISPs reported any impact from the worm, as it included mechanisms to limit its spread. As a result of this action, spam and botnet traffic immediately dropped significantly. In addition, new infections of several forms of ransomware ceased.
TPS: Was the response appropriate? Ethical? What principles would permit the security vendors and government organizations to write such software.