You are probably being recorded (and transcribed)
Approximate overview
update thingy.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?
r = 0;
w = 0;
b = 0;
// +------------+-------------+-------------+--------------+
// | Red | White | Blue |X Unprocessed |
// +------------+-------------+-------------+--------------+
// | | | |
// r w b n
// +---------------------------------------------------------+
// | Unprocessed |
// +---------------------------------------------------------+
// |
// r,w,b
It works. Everything to the left of r is red (since there are no such
elements). Everything between r and w is white (since there are no
such elements). Etc.
Does the algorithm work correctly if there are not yet any red elements?
// +------------------+-------------------+------------------+
// | White | Blue |? Unprocessed |
// +------------------+-------------------+------------------+
// | | | |
// r w b
r, so we’re fine.r, so we’re fine.Does the algorithm work correctly if there are not yet any white elements?
// +------------------+-------------------+------------------+
// | Red | Blue | Unprocessed |
// +------------------+-------------------+------------------+
// | | |
// r,w b
Does the algorithm work correctly if there are not yet any blue elements?
// +------------------+-------------------+------------------+
// | Red | White |? Unprocessed |
// +------------------+-------------------+------------------+
// | | |
// r w,b
If the ? is R, we swap the red with the white
// +------------------+-------------------+------------------+
// | Red |R White |W Unprocessed |
// +------------------+-------------------+------------------+
// | | |
// r w,b
and then we swap the r and the b.
// +------------------+-------------------+------------------+
// | Red |W White |R Unprocessed |
// +------------------+-------------------+------------------+
// | | |
// r w,b
and then we increment all the indices.
// +--------------------+-------------------+----------------+
// | Red W| White R| Unprocessed |
// +--------------------+-------------------+----------------+
// | |
// r w,b
Whoops! Nope, it doesn’t work if there are not currently any blue elements.
If the answer to any of those is “No”, how do we fix the algorithm?
Suggestion.
if the next value is red,
swap(w,b)
swap(r,w)
Other option
Merge sort:
Merge algorithm (high level)
Since at each step, we’re adding one element to the merged array and we add \(n\) elements to the merged array, this is an \(O(n)\) algorithm.
Let’s start by writing the recurrence relation. We are defining \(T(n)\), the time merge sort takes on \(n\) elements.
\(T(n) = 2 \times T(n/2) + n + c\) \(T(1) = c\)
Three key ideas:
If we know the median, we can divide the (sub)array into three parts using DNF (things smaller than the median, things equal to the median, and things greater than the median) in O(n) time.
After recursively sorting the left half and the right half, our whole array is sorted.
Analysis: Exactly the same as merge sort. Instead of merging in O(n) steps, we rearrange in O(n) steps. Instead of splitting in O(1) time, we find the median in O(1) time.
Except … How do we find the median?
Solution: Pick a random element and cross your fingers. This is not the median, so we give it a different name. Generally, we call it the pivot.
In the best case, all of the elements are equal. Everything is in the middle section and we don’t need to recurse, so it’s O(n).
In the best case where all the elements are different, we always pick the median and our analysis shows us this is O(nlogn).
In the worst case, we always pick the largest or smallest element as a median and our recurrence relation becomes \(T(n) = T(n-1) + n + c\), which is going to be \(O(n^2)\).
This is better than, say, merge sort because we don’t need an additional array, thereby saving memory (and saving the cost of moving things back and forth from that additional memory).
In practice, it seems to behave better.
Merge sort can’t be done in place, but you can write a merge sort that mutates the original array into a sorted array by copying back from the helper array.
Note: If you use DNF to partition, you’ll probably want to return a two-element array with the end of the reds and the ends of the whites as contents.
public int[] dnf(T[] values, int lb, int ub, Comparator<T>) {
int r = 0;
int w = 0;
int b = 0;
...
return new int[] {r, w};
} // dnf
Then, the recursive calls in Quicksort will look something like
int[] bounds = dnf(...);
sort(vals, lb, bounds[0]);
sort(vals, bounds[1], ub);
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 parition 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.
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.