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.
Write a game. Use a matrix as the board. Use good OO-design. Make it configurable. Don’t spend too much time. Work with a partner.
Your partner is your partner from today’s class. (Yes, we will eventually partner up.)
Can you go over the running time/analysis for the linear and binary searches again?
Linear search, really informal. Linear search looks at the elements one by one until it finds one that matches some criteria. We will assume that looking at the next element is a contant-time operation (for arrays, array indexing is a constant-time operation; for most iterators, we pretend that getting the next element is a constant-time operation). At worst, we look at every element. So we spend \(O(nc)\) where \(c\) is the constant-time per “look at element” and \(n\) is the number of elements. Big-O says “throw away constant multipliers (and lower-order terms), so this is just \(O(n)\).
Binary search, a bit more formal. At worst, each time through binary the main loop (recursion), the middle element doesn’t match, so we throw away exactly half the elements.
Tne time to search an array of N elements is a constant (to compute and look at the middle elements) plus the time to search one half.
When there’s only one element left, it’s also constant time. We’ll pretend it’s the same constant.
\[T(n) = c + T(n/2)\]
\[T(1) = c\]
We want to put the two equations in closed form (not recursive). We should now about four techniques for doing so.
- Bottom-up. We start with the \(T(1)\), then figure \(T(2)\), etc.
\(T(1) = c\) [1 is \(2^0\)]
\(T(2) = c + T(2/2) = c + T(1) = c + c = 2c\) [2 is \(2^1\)]
\(T(3) = c + T(3/2) = c + T(2) = c + 2c = 3c\) (or maybe 2c; optional)
\(T(4) = c + T(4/2) = c + T(2) = c + 2c = 3c\) [4 is \(2^2\)]
\(T(8) = c + T(8/2) = c + T(4) = c + 3c = 4c\) [8 is \(2^3\)]
\[T(16) = c + T(16/2) = c + T(8) = c + 4c = 5c\]
We should see a patten (I hope).
\[T(2^k) = c + kc = (k + 1)c\]
Let \(n = 2^k\), which means \(k = log2(n)\)
\[T(n) = (log2(n) + 1)c\]
\(T(n) \in O(log2(n))\) (throw away constant multipliers and lower-order terms)
- Top-down
\[T(n) = c + T(n/2)\]
\[T(n) = c + c + T((n/2)/2) = 2c + T(n/4)\]
\[T(n) = 2c + c + T((n/4)/2) = 3c + T(n/8)\]
\[T(n) = 3c + c + T((n/8)/2) = 4c + T(n/16)\]
\(T(n) = ic + T(n/2^i)\) “It’s so obvious” - BS
Let n = 2^k.
\[T(n) = kc + T(n/n) = kc + c = (k + 1)c.\]
\[T(n) = (log2(n) + 1)c\]
\[T(n) \in O(log2(n))\]
- Draw a recursion tree
- Use the master theorem.
When is it worth the time spent sorting the array in order to make binary search possible vs when should we just use linear search?
If we’re only doing a few searches, linear search wins. But if we’re doing a lot of searches (say, more than the number of elements in the array), sorting first wins.
If we build the array so that it ends up sorted, does that make it any quicker?
Building a sorted array bit by bit is effectively the same as out-of-place sorting. Hence, it won’t be better than a good sorting algorithm.
**Why does Sam write \(T(n) \in O(f(n))\) instead of \(T(n) = O(f(n))\)?
\(T(n)\) is a function. \(O(f(n))\) is a set of functions. Rarely is a function equal to a set of functions.
Most computer scientists (and even mathematicians) are nonetheless casual about big-O notation and write things like \(T(n) = O(f(n))\).
Should we understand the formal definition of Big-O?
Yes. The formal definition lets us reason about various aspects of Big-O, such as “we can ignore constant multiplers” and “we can ignore lower-order terms”.
Is it better to be able to analyze algorithms or should we memorize?
It’s better to be able to analyze. However, if you are going to job interviews (or just don’t want to embarrass yourself in front of your faculty) you should memorize the running times of key algorithms.
Should we be able to do space analysis?
It would be nice. But it’s the same concept.
Can you go over tight Big-O again?
Suppose \(f(n) = 3n + 17\).
\(f(n) \in O(n)\).
We also know that \(f(n) \in O(3n^3 + 17)\)
We also know that \(f(n) \in O(n^100)\) (as long as n is bigger than 1.2 or so)
The first is the only useful one, because the curves “match”, as it were.
That’s what we mean by a tight bound.
Why not to use \($=\)$ revisited. \($f(n) = O(n)\)$. \($f(n) = O(n^3)\)$. If we believe in transitivity of equality, \(O(n) = O(n^3)\). Whoops.
Can we use the master theorm in the SoLA because it was in the textbook?
Only if you can prove the master theorem. (So probably not.)
You can use it to check your work, but I’d prefer that you show another mechanism (practice is good and develops intuition).
I’m not sure that I understand what a loop invariant is.
We’ll go over loop invariants today.
In short, a loop invariant is a logical statement about the state of the system.
We expect it to be true at the start of each trip through the body of the loop.
We should ensure that it is true again at the end of each trip through the body of the loop.
We also want it to say something useful (related to our goals).
In real-world programming, how often do developers formally define loop invariants? Are they mainly a teaching tool, or do they find use in practical coding?
Loop invariants regularly find use in situations in which people need to ensure that their code is correct, such as when writing mission-critical software.
Should it always be the case for our Comparator objects that if A precedes B and B precedes C, then A precedes C?
Yes, we must be able to assume that our
Comparatorobjects are transitive. In fact, the specification ofjava.util.function.Comparatorrequires it.
What can we do if this is not the case?
We may not be able to tell. But sorting is not necessarily meaningful if you have a non-transitive comparator.
Since Comparable<T> is used with objects that have an implied
natural order, do integers and characters implement that Comparable
interface?
Yes,
IntegerimplementsComparable<Integer>andCharacterimplementsComparable<Character>
Is there a way to add an order to existing classes, thereby having them
implement Comparable?
Unless we have access to the code for the underlying class, we can’t directly make them implement
Comparable. In such cases, we are better off writing aComparatorfor those objects. We could potentially subclass the objects and make the subclass implementComparable, but that is likely to be less elegant.
If one sorting algorithm is known to be more efficient than another, then why do we learn multiple different algorithms?
Different sorting algorithms work better or worse in different conditions. For example, insertion sort works very well on a mostly-sorted array.
There’s also the experience of thinking about different ways to solve the same problem.
What is an ideal use case for insertion sort and selection sort?
Insertion sort works well with mostly-sorted arrays.
Selection sort can be useful when you only need part of a sorted array.
In which situations would selection sort be preferred over insertion sort, given their similar time complexities?
Having the same theoretical complexity does not mean that the running time is the same. Remember that Big-O ignores constant multipliers. So a particular implementation of selection sort might be faster than a particular implementation of insertion sort, even though both have the same Big-O.
In situations in which we want to start processing the “smaller” elements before the sorting is complete, selection sort is preferred.
When implementing a sorting algorithm, what are some specific strategies to ensure stability?
That’s a great question. Pay attention to the locations when you’re swapping elements and make sure that you never swap equal elements.
Can insertion sort be done not ‘in place’ since you’re always comparing and swapping elements?
Insertion sort can be done in place if you’re just swapping elements. Swapping only pulls one element out of the array at a time. You can also do it out-of-place by building a new array bit by bit.
In Scheme,
(define insertion-sort (lambda (lst) (if (null? lst) null (insert (car lst) (insertion-sort (cdr lst))))))
I’m a little confused on selection sort, mainly on how we know what the smallest remaining element is. Are we just running another loop during which we iterate the array checking what the smalles element is? (This seems wrong and very inneficient.)
Yes, finding the smallest remaining element requires iterating the remaining elements. It’s not particularly efficient, but it’s not horrible.
What are some real-world examples where stability in sorting algorithms is crucial?
The basic Excel sort mechanism has to be stable since there’s an assumption that if you sort by column B and then by column A, things are effectively sorted by A+B.
Are there specific guidelines or best practices for choosing between in-place vs. out-of-place sorting implementations in Java?
Nope. It depends on the problem you’re working with. Functional programmers prefer out-of-place sorting algorithms because they are referentially pure. But in-place sorting algorithms save space.
Concept: Think carefully about the state of the system
Benefits: More likely to write correct code. More likely to find an algorithm.
Methodology: Try to find a correct and useful statement about the state of the system, try to ensure that it remains correct. Ensure that the loop terminates.
We had an exponentiation algorithm using repeated multiplication. We did \(n\) multiplications. Each multiplication is a constant-time operation. So that algorithm is in \(O(n)\).
Can we do better?
If \(n\) is even, \(x^n = (x^2)^(n/2)\). For example, $3^8 = 9^4 = 81^2 = 6561^1$
Repeated division of the exponent by 2 can make a very fast algorithm.
/**
* Compute x^n.
*/
public static BigInteger expt(BigInteger x, int n) {
BigInteger base = x;
int exponent = n;
BigInteger muliplier = BigInteger.one;
// Intended to hold the multiplication from the odd exponents
// Let's try to write an invariant that relates base, exponent,
// x, and n.
// multiplier * (base^exponent) = x^n
while (exponent > 0) {
if ((exponent % 2) == 0) {
// b^e = (b^2)^(e/2) if e is even.
base = base.multiply(base);
exponent = exponent / 2;
} else {
// b^e = b*(b^(e-1)) if e is odd.
multipler = multiplier.multiply(base);
exponent = exponent - 1;
} // while
} //
return muliplier;
} // expt
To compute \(x^n\), that algorithm required \(O(logn)\)
A computer scientist should always ask “Can we do better?”