LaTeX Features

• XeLaTeX (Unicode) or LaTeX (European Languages)
• Markup Language built on TeX
• Tags: \tag
• Environments: \begin{..} ... \end{..}
• Grouping: {...}
• Math mode: $$d = \sqrt{a_0^2 + a_1^2}$$
• Spacing: \vfil \hfil \bigskip \smallskip

Useful LaTeX markup tags

• Font size: \tiny \small \normalsize \large \huge
• Font families: \bf \tt \sl \it
• Document segments: \section \subsection \subsubsection
• Graphics: \includegraphics{width=\columnwidth}{pic.png}
• Tables: \begin{tabular}{lr} aa & 3.5\\ b & 17.2\\ \end{tabular}
• Footnotes: \footnote{This is a note}
• Citations: \cite{Knuth:1970}
• Cross links: \label{id} .. As seen in \ref{id}

Overleaf Dashboard

Namecards

Overleaf Document Development Platform

Namecards

Namecard Output

Namecards

LaTeX installation

Ex. Some statements

Please note which of these is true

• Given \(A=\{1,2,3\}, X = {\cal P}(A):\)
  \(\qquad\exists y \in X: y \subseteq A, y = A\)
  Hint (What is the value of \(y\) ?)

• Given \(A = \emptyset, X = {\cal P}(A):X = A\)
  Hint: (What is the value of \(X\) ?)

• Given \(A = \emptyset, X = ?\)

Cardinality

Permutations of a set

\[\displaystyle P(n) = \underbrace {n\cdot (n-1)\cdot (n-2)\cdot (n-3) \cdots (1)}_{n\ \mathrm {factors}} = n!\]

Venn Diagrams

LaTeX Venn Diagram

\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{venndiagram}
\usepackage{xcolor}
\begin{document}\Large
\begin{venndiagram3sets}[labelOnlyA={1},
labelOnlyB={2},labelOnlyC={3},
labelOnlyAB={4},labelOnlyAC={5},
labelOnlyBC={6},labelABC={7},
labelNotABC={8},shade=orange]
\fillACapB \fillBCapC \fillACapC
\end{venndiagram3sets}
\end{document}

Another Example

\documentclass{article}
\usepackage[utf8]{inputenc}

\title{VennDiagram}
\author{rbatzing }
\date{November 2018}

\usepackage{venndiagram}
\usepackage{xcolor}
\begin{document}\small
\begin{venndiagram3sets}[labelOnlyA={1138},
labelOnlyB={1183},labelOnlyC={1159},
labelOnlyAB={529},labelOnlyAC={532},
labelOnlyBC={532},labelABC={196},
labelNotABC={5269},shade=orange]
\fillACapB \fillBCapC \fillACapC
\end{venndiagram3sets}
\end{document}

Output

Create Venn Diagram

• Use the Venn.tex to create a PDF that displays the following

  • \(A \cap B \cup C\)
  • \(A \cup B \cup C\)
  • \(\neg(A \cap B \cap C)\)

• Upload the diagram to the Google Classroom

Ruby Set Class

require 'set'

setA = Set.new(1..3); 
setB = Set.new([2,3])
setC = Set.new([2,3,4]); 
setU = Set.new(1..4)

Ruby Set Class Demonstration

puts <<endmsg
A:#{setA.inspect} B:#{setB.inspect} 
C:#{setC.inspect} 
B subset A:    #{setB.subset?(setA)}
A superset B:  #{setA.superset?(setB)}
A union B:     #{setA.union(setC).inspect}
A intersect C: #{setA.intersection(setC).inspect}
A intersect C: #{(setA & setC).inspect}
A intersect C?:#{setA.intersect?(setC)}
A subtract C:  #{setA.difference(setC)}
Complement(B): #{setU.subtract(setB).inspect}
Cardinality(A):#{setA.size}
4 member of C?:#{setC.include?(4)
endmsg

Output

A:#<Set: {1, 2, 3}>  B:#<Set: {2, 3}> 
C:#<Set: {2, 3, 4}> 
B subset A:     true
A superset B:   true
A union B:      #<Set: {1, 2, 3, 4}>
A intersect C:  #<Set: {2, 3}>
A intersect C:  #<Set: {2, 3}>
A intersect C?: true
A subtract C:   #<Set: {1}>
Complement(B):  #<Set: {1, 4}>
Cardinality(A): 3
4 member of C?: true

Ex.3 Relationships between Standard Sets

Create a Venn Diagram in yEd to represent the relationships between these standard sets:

\[\mathbb{N}, \mathbb{P}, \mathbb{Q}, \mathbb{R}, \mathbb{W}, \mathbb{Z}\]

Ex.4 Puzzle

Negation

Research Procedure

1. Use Git to pull the latest copy of the Ruby source: [group.rb]
2. Run the software and verify that all 5 methods produce the same statistics for a Venn diagram.
3. Run the profiler analysis for the fastest and slowest methods.
4. Change the sample size from 2000 to 200,2000,20000, and 200000
5. Repeat the study with a sample size of 20,000 and vary the fractions of 200, 250, 333 and 500

Reporting Procedure

1. Create a 3 factor Venn Diagram and include this in your Introduction with an explanation of what the numbers and regions of a Venn diagram signify.
2. Write the Introduction that includes a description and explanation of the key research question.
3. Describe the differences of the 5 counting methods in your Methodology section.
4. Describe the differences in the profiles of the fastest and slowest methods in the results section.
5. Create a graph to show the effect of sample size on the runtime and put this in your results section
6. Create a graph that shows the effect of fraction size on runtime and put this in your results section
7. In the Conclusion, summarize the key points of your findings and make a recommendation as to what is the most efficient way to determine the counts for a Venn diagram.
8. Add the Abstract and Title.
9. Submit a shared link of the PDF file to the Canvas website

Parts of a LaTeX research report

* Title: Choose an appropriate title that uses less than 250 characters * Author: Add names and student id numbers of both students * Abstract: summarizes the research project in less than 2,500 characters. * Keywords: 3 best words to index this report. * Introduction: Define and describe the research question you are trying to answer

::: :::{.column width=“50%”}

* Methodology: Describe the methods and technology did you use to do this research * Results: Provide tables and graphs of your results and describe the key findings * Conclusion: Summarize your findings and recommend the best answer for your research questions * Bibliography: State works and methods of others that is relevant to this research

Ex.5 - Counting examples

• In a group of 10 people, if everyone shakes hands with everyone else exactly once, how many handshakes took place?

• If there are 10 people and 3 chairs, how many groups of 3 are possible?

• How many ways can you distribute 10 cookies to 7 students?

Additive Principle

The additive principle states that if event \(A\) can occur in \(m\) ways, and event \(B\) can occur in \(n\) disjoint ways, then the event \(A \cup B\) can occur in \(m + n\) ways.

• For 2 sets: \(|A \cup B| = |A| + |B| - |A \cap B|\)

• For 3 sets: \(\small|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| +|A \cap B \cap C|\)

Cartesian Product

For given sets \(A\) and \(B\), the set of all ordered pairs \(\{x,y\}\) where \(x \in A\) and \(y \in B\)

\[\hbox{For}\ A = \{1,2,3\}\ \hbox{and}\ B = \{A,B,C,D\}\]

\[A \times B= \left\{ \begin{array}{ccc} \{1,A\} & \{2,A\} & \{3,A\}\\ \{1,B\} & \{2,B\} & \{3,B\}\\ \{1,C\} & \{2,C\} & \{3,C\}\\ \{1,D\} & \{2,D\} & \{3,D\}\\ \end{array} \right\}\]

Multiplicative Principle

If event \(A\) can occur in \(m\) ways, and each possibility for \(A\) allows for exactly \(n\) ways for event \(B\), then the event \(A \cup B\) can occur in \(m \times n\) ways

For sets: \(|A \times B| = |A| \cdot |B|\)

Pigeonhole Principle

If \(N\) objects are placed in \(K\) boxes, then there is at least one box containing at least \(\lceil N/K \rceil\) objects.

Example:

Among 100 people, there are at least \(\lceil 100 / 12 \rceil = 9\) who were born in the same month.

Ex.7 - Counting at the Restaurant

Given a restaurant offers 8 appetizers and 14 entrées.

How many choices do you have if:

• You will eat one dish, either an appetizer or an entrée?
• You are extra hungry and want to eat both an appetizer and an entrée?

Ex.8 Counting examples

• A palindrome is a string that is identical to the string in reverse order. How many bit strings of length \(n\) are palindromes?

• How many licence plates can be made using either two letters followed by 4 digits or four letters followed by 2 digit is?

• How many books can be identified using the 12 digit ISBN?

Subsets of A = {1,2,3,4,5}

• Total number of subsets:

\[|{\cal P}(A)| = 2^5 = 32\]

• Total number of subsets of size \(n\) :

\[\left({|A|\over n!\ (|A| - n)!}\right)\]

Subsets of A = {1,2,3,4,5} by size

\[\tiny\begin{array}{|c|c|c|c|c|} \hline n=0 & n=1 & n=2 & n=3 & n=4 & n=5 \\ \hline \left({5\atop 0}\right) & \left({5\atop 1}\right) & \left({5\atop 2}\right) & \left({5\atop 3}\right) & \left({5\atop 4}\right) & \left({5\atop 5}\right) \\ \hline \left({5!\over 0!\ 5!}\right) & \left({5!\over 1!\ 4!}\right) & \left({5!\over 2!\ 3!}\right) & \left({5!\over 3!\ 2!}\right) & \left({5!\over 4!\ 1!}\right) & \left({5!\over 5!\ 0!}\right) \\ \hline {5\cdot4\cdot3\cdot2\cdot1\over (5\cdot4\cdot3\cdot2\cdot1)} & {5\cdot4\cdot3\cdot2\cdot1\over (1)(4\cdot3\cdot2\cdot1)} & {5\cdot4\cdot3\cdot2\cdot1\over (2\cdot1)(3\cdot2\cdot1)} & {5\cdot4\cdot3\cdot2\cdot1\over (3\cdot2\cdot1)(2\cdot1)} & {5\cdot4\cdot3\cdot2\cdot1\over (4\cdot3\cdot2\cdot1)(1)} & {5\cdot4\cdot3\cdot2\cdot1\over (5\cdot4\cdot3\cdot2\cdot1)} \\ \hline {1 \over 1} & {5 \over 1} & {5\cdot4 \over 2\cdot1} = {5\cdot2\over 1} & {5\cdot4\cdot3 \over 3\cdot2\cdot1} = {5\cdot 2\over 1} & {5 \over 1} & {1 \over 1}\\ \hline 1 & 5 & 10 & 10 & 5 & 1 \\ \hline \emptyset & \{1\}, & \{1,2\}, \{2,3\}, &\{1,2,3\}, \{2,3,4\}, & \{1,2,3,4\}, & \{1,2,3,4,5\}\\ & \{2\}, &\{3,4\}, \{4,5\},& \{3,4,5\}, \{1,2,4\}, & \{1,2,3,5\}, & \\ &\{3\}, & \{1,3\}, \{1,4\}, &\{2,3,5\}, \{1,2,5\}, & \{1,2,4,5\}, & \\ &\{4\}, &\{1,5\}, \{1,4\}, &\{1,3,4\}, \{1,3,5\},&\{1,3,4,5\},&\\ &\{5\} &\{2,5\}, \{1,5\} & \{1,4,5\}, \{2,4,5\} & \{2,3,4,5\} & \\ \hline 00000 & 10000, & 11000,01100, & 11100, 01110, & 11110, & 11111 \\ & 01000, & 00110, 00011, & 00111, 11010, & 11101, & \\ & 00100, & 10100, 10010, & 01101, 11001, & 11011, & \\ & 00010, & 10001, 10010, & 10110, 10101, & 10111, &\\ & 00001 & 01001, 10001 & 10011, 01011 & 01111 & \\ \hline \end{array}\]

Bit Strings

• An \(n\) - bit string is a bit string of length n. That is, it is a string containing \(n\) symbols, each of which is a bit, either 0 or 1.
• The weight of a bit string is the number of 1’s in it.
• \(B^n\) is the set of all \(n\) - bit strings, \(B^n_k\) is the set of all \(n\) - bit strings of weight \(k\) .

\[\small\begin{array}{|l|c|c|c|c|c|} \hline weight: & k=0 & k=1 & k=2 & k=3 & k=4 & k=5 \\ \hline B^5_k & 00000 & 10000, & 11000, 01100, & 11100, 01110, & 11110,& 11111 \\ & & 01000, & 00110, 00011, & 00111, 10110, & 11101, & \\ & & 00100, & 10100, 01010, & 01011, 10011, & 11011, & \\ & & 00010, & 00101, 10010, & 10101, 11001, & 10111, & \\ & & 00001 & 01001, 10001 & 11010, 01101 & 01111 & \\ \hline B^5_k& 1 & 5 & 10 & 10 & 5 & 1 \\ \hline \end{array}\]

Recursive Relationship in Bit Strings

• Recursively break the problem down by imposing a value of the first digit of the unknown set and solving the problem for the resulting subsets:

\[\{?????\}_{k=3} = 0\{????\}_{k=3} + 1\{????\}_{k=2}\]

• Once the problem has been reduced to a simple subset, the values are back substituted.

\[\begin{array}{rcccccl} |B^5_3| & = & |B^4_3| + |B^4_2| &=& 4 + 6 & = & 10 \\ |B^4_3| & = & |B^3_3| + |B^3_2| &=& 1 + 3 & = & 4 \\ |B^4_2| & = & |B^3_2| + |B^3_1| &=& 3 + 3 & = & 6 \\ \end{array}\]

Lattice Points

• Movement through a lattice is like Bitstrings
• Shortest paths are restricted to 2 moves: Up or Right
• Thus all possible paths (0,0) to (3,2) must go through points \(A\) or \(B\)
• \(B\) can be reached via \(\{RRRU, RRUR, RURR, URRR\}\)
• \(A\) can be reached via \(\{RRUU, RURU,RUUR,URRU,UURR\}\)
• Recursive relationships also apply

::: :::{.column width=“50%”}

lattice

Binomial Coefficients

\[\begin{array}{c} (x + y)^1 = x + y\\ (x + y)^2 = x^2 + 2xy + y^2\\ (x + y)^3 = x^3 + 3x^2y + 3xy^2 + y^3\\ (x + y)^4 = x^4 + +4x^3y + 6x^2y^2 + 4xy^3 + y^4\\ (x + y)^5 = x^5 + 5x^4y + 10x^3y^2 + 10x^2y^3 + 5xy^4 + y^5\\ \end{array}\]

Binomial Coefficients

\[\begin{array}{c} \exists n,k: n \ge 0, 0 \le k \le n \Rightarrow\\ \left({n \atop k}\right)\\ \end{array}\]

• Read as n choose k.
• Equals \(|B^n_k|\) the number of \(n\) - bit strings of weight \(k\)
• Equals the number of subsets of size \(n\) with cardinality \(k\)
• Equals the number of lattice paths of length \(n\) with \(k\) steps to the right.
• Equals the coefficient of \(x^k y^{n−k}\) in the expansion of \((x + y)^n\)
• Equals the number of ways to select \(k\) objects from a total of \(n\) objects

Recurrence Relationship

\[\left({n \atop k}\right) =\left({n-1 \atop k-1}\right) + \left({n-1 \atop k}\right)\]

Pascal Triangle

Ex. 9: TERMS

Define these terms:

• Principles:
  • Additive Principle
  • Multiplicative Principle
  • Pigeonhole Principle
• Operators:

1. \(A \subseteq B\), 2) \(A\cap B\), 3) \(A \cup B\),
   
2. \(A\backslash B\), 5) \(\bar{A}\), 6) \(|A|\)

::: :::{.column width=“50%”}

• Function
  • Cartesian Product
  • Inverse Function
  • Bijections
  • Injections
  • Surjection

::: ::::

Definition

A function is a rule that assigns each input exactly one output.

Domain is the set of all possible inputs.

Range is the set of all possible outputs.

Ex.4 Identify the functions

Given the following mappings, which would qualify as functions?

Surjections

Surjection where the elements of the domain cover the full range of value in the range.

\[ f : \{1, 2, 3, 4, 5, 6\} \Rightarrow \{a,b,c\}\]

\[\begin{array}{|c|c|c|c|c|c|c|} \hline Original\ domain & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline Outcomes\ value & a & a & b & b & b & c \\ \hline \end{array}\]

Injections

Injection where the elements of the domain map to unique values in the range (No duplicates).

\[ f : \{1, 2, 3, 4, 5\} \Rightarrow \{a,b,c, d, e, f\}\]

\[\begin{array}{|c|c|c|c|c|c|c|} \hline Original\ domain & 1 & 2 & 3 & 4 & 5 \\ \hline Outcomes\ value & e & c & b & d & a \\ \hline \end{array}\]

Bijections

Bijection where the all elements of the domain map to unique values which cover the entire range.

\[ f : \{1, 2, 3, 4, 5, 6\} \Rightarrow \{a,b,c, d, e, f\}\]

\[\begin{array}{|c|c|c|c|c|c|c|} \hline Original\ domain & 1 & 2 & 3 & 4 & 5 & 6\\ \hline Outcomes\ value & f & c & b & d & a & e\\ \hline \end{array}\]

Inverse Function

inverse

\[ f : \{1, 2, 3, 4, 5, 6\} \Rightarrow \{a,b,c, d, e, f\}\]

\[ f : \{a,b,c, d, e, f\} \Rightarrow \{1, 2, 3, 4, 5, 6\}\]

yEd Work Space

yEd installation

Applications to programming

# MULTIPLICATIVE
x = 0
for i in 1..10
  for j in 1..10
    for k in 1..10
      x = x + 1
    end
  end
end
puts x

1000

::: :::{.column width=“50%”}

# ADDITIVE
x = 0
for i in 1..10
  x = x + 1
end
for j in 1..10
  x = x + 1
end
for k in 1..10
  x = x + 1
end
puts x

30

Applications to programming

def try(n)
  x = 0
  for i in 1..n
    for j in 1..i
      for k in 1..j
        x = x + 1
      end
    end
  end
  puts x
end

::: :::{.column width=“50%”}

Sums of arithmetic series

\[\small\begin{array}{cccc} \textbf{n} & \textbf{Sequence} &\textbf{Sum} &\textbf{Equiv}\\ \hline 1 & \small 1 & 1 & 1{(1+1)\over 2} \\ 2 & \small 1+2 & 3 & 2{(1+2)\over 2} \\ 3 & \small 1+2+3 & 6 & 3{(1+3)\over 2} \\ 4 & \small 1+2+3+4 & 10 & 4{(1+4)\over 2} \\ 5 & \small 1+2+3+4+5 & 15 & 5{(1+5)\over 2} \\ 6 & \small 1+2+3+4+5+6 & 21 & 6{(1+6)\over 2} \\ 7 & \small 1+2+3+4+5+6+7 & 28 & 7{(1+7)\over 2} \\ 8 & \small 1+2+3+4+5+6+7+8 & 36 & 8{(1+8)\over 2} \\ \hline \end{array}\]

Formula for this function

\[\begin{array}{rcc} count & = & \sum{\{1 .. n\}} + \sum{\{1 .. (n-1)\}} + ... + \{1\} \\ & = & {x(x+1)\over 2} + {(x-1)((x-1)+1)\over 2} + ... + 1 \\ & = & {x_n + x_n^2\over 2} + {x_{n-1} + x_{n-1}^2\over 2} + ... + {x_{1} + x_{1}^2\over 2}\\ & = & {\sum_{i=1}^{n}\ x_i + \sum_{i=1}^{n}\ x_i^2\over 2} \\ \end{array}\]

Ex. Determine the value of x

x = 0
for i in 1..10
  for j in 1..10
      x = x + 1
  end
  for k in 1..10
      x = x + 1
  end
end
puts x

::: :::{.column width=“50%”}

x = 0
for i in 1..10
  for j in 1..10
    for k in 1..10
      x = x + 1
    end
  end  
  x = x + 1
end
puts x