cs2102
Discrete Mathematics
This is a preserved file from cs2102 Fall 2016. An updated version may exist at https://uvacs2102.github.io/

Class 7: Sets


Schedule

Everyone should have received their comments and grade on PS1 yesterday. Please make sure to read the comments posted on the website about how PS1 was graded.

Problem Set 3 is due Friday at 6:29pm.

I will have “make-up” office hours tomorrow (Wednesday) 3:30-4:30pm (in addition to my usual Wednesday 1-2pm office hours). There have been some adjustments to the office hours schedule, please check the calendar.

See PDF Version for Notes and Questions.

Tom Leighton’s Remarks on Danny Lewin

A Lost Spirit Still Inspires, Boston Globe, 4 September 2011.

No Better Time: The Brief, Remarkable Life of Danny Lewin, the Genius Who Transformed the Internet by Molly Knight Raskin.

Akamai’s Algorithms Technology Review, Interview with Tom Leighton, 1 September 2000.

David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin, Rina Panigrah. Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. (Note: tradition in theory papers is to list all authors alphabetically). 29th ACM Symposium on Theory of Computing, 1997.

The SAT solver I demo’d in class today was from the Class 6 notes: Sahand Saba’s Understanding SAT by Implementing a Simple SAT Solver in Python [Code with my modifications: https://github.com/evansuva/simple-sat]. You should, of course, feel free to use this (or any other SAT solver you want) to help with solving and checking your answers for Problem Set 3 (and any other assignment in this class).

Notes and Questions

What is a data type? What are the differences between a mathematical data type and a data type in your favorite programming language?

#

A set is an unordered colection of objects. A set is defined by its membership operation: $x \in S$ is true if $x$ is in the set $S$.

Set Operations

Subset: $\subseteq$ (note that this does not mean strict subset) $$A \subseteq B \iff \forall x \in A. \fillin \in \fillin.$$

Set Equality: $=$ $$A = B \iff A \fillin B \wedge B \fillin A.$$

Set Union: $\cup$ $$\forall x. x \in A \cup B \iff x \in A \fillin x \in B.$$

Set Intersection: $\cap$ $$\forall x. x \in A \cap B \iff x \in A \fillin x \in B.$$

Set Difference: $-$ $$\forall x. x \in A - B \iff x \in A \wedge x \notin B.$$

Set Complement: $\overline{S}$ $$ \forall x. x \in D. x \in \overline{A} \iff x \notin A.$$

($D$ is the ``domain of discourse”, the universe of all objects under discussion.)

Russell’s Paradox

$$ S_{R} = \textrm{ the set of all sets that are not members of themselves} $$

Is $S{R} \in S{R}$?

#

Set Practice

Here are some practice problems involving sets. We won’t go through these in class, but you should ask questions about any are unclear. (At least a few of these will be on Exam 1.)

  1. Define $A \subset B$ (strict subset).

#

  1. Prove $A \cup B \equiv B \cup A$.

#

  1. Prove $A - B = \emptyset \iff A \subseteq B$.

#

  1. Prove $A = B \iff (\forall a \in A \ldotp a \in B) \wedge (\forall b \in B \ldotp b \in A).$

#

Danny Lewin

See the web version for links to articles on Danny Lewin.

\begin{quote} {\em In true Danny form, he fought back against the terrorists in an effort to defend the stewardesses and the cockpit. To this day, those of us who knew him well can’t figure out how only five terrorists managed to overpower him. During his short life, Danny made extraordinary contributions to the internet and to computer science through his work in algorithms and complexity theory. The impact of his work will be felt throughout the hi-tech industry for many years to come.} (from Tom Leigthon’s \hyperlink{http://www.egr.unlv.edu/~bein/SIGACT/lewin.html}{remarks to commemorate naming of the STOC Best Student Paper Award in honor of Daniel Lewin}, 19 May 2002. \end{quote}