Held: Wednesday, 7 December 2005
Summary:
Today we discuss possible solutions to examination 3.
Related Pages:
Overview:
- Exercise in documentation reading.
- Problem 1: Recurrence relations.
- Problem 3: Sets and BSTs.
- Problem 4: Heaps.
- Problem 4: Removing elements from linear-probe hash tables.
- Email protocols written in a much different setting
- Multiple networks
- Not many (no?) malicious participants
- SMTP and the Internet Message format come from a period of trust.
- No mechanism for verifying sender. (Expected to be external.)
- Routing information normally hidden from user.
- Routing expected.
- Surprisingly, trust remains in current email systems.
- You can give Thunderbird any name and email address and it will happily report it when you send email.
- Most languages (including Java) include a mail sending library with no verification.
- Even when systems try to limit fraud, some trust remains
- Our mail servers do not simply accept mail that seems to be from someone at Grinnell. (That's good; spammers love that technique.)
- Our mail servers generally accept mail that is sent from any machine in our domain.
- Our mail servers generally accept mail that is sent to anyone with a grinnel address. (That's probably necessary.)
- What goes on behind the scenes in these systems? It's fairly straightforward.
- Two aspects
- Transferring email from system to system: SMTP (RFC 821)
- Message format (RFC 822)
- What can we glean from those documents?
- RFC 821 tells us that we normally connect to port 25 to transfer email.
- RFC 821 tells us the normal dialog (see appendix F): HELO, MAIL from:, RCPT To:, Data, a period, QUIT
- RFC 822 tells us the basic format of a header (which is in the data): Date, From, To, Subject
- RFC 822 tells us to put a space between the header and body.
- That's about it.
- Some confusion on what it means to recursively expand. I'll
try to clarify.
- My goals:
- Do you understand the bst code?
- Help you discover actual performance.
- My goals:
- Understand details of heap data structure
- Convert from abstract idea to implementation
- Prepare you to study sorting
- Some key issues:
- Comparators return "negative", zero, or "positive", not -1, 0, +1.
- Relying on exceptions for special cases can be dangerous.
- My goals:
- Think about a complex problem
- Understand complexities
- Your problems:
- Using Vector.remove
- Assuming only values that hash to the location should move (sometimes we can just improve the position)
- Difficulty describing what values should move (if you didn't have the prior problem)
- Too many nested loops; O(n^2) rather than O(#places until next null)
;
Check with Bobby