Please do 1 or 2 in Combinatorics of Writing Assignments

Writing
 Assignments/Technology
 Assignments
 

You
 will
 complete
 a
 total
 of
 six
 writing/technology
 assignments
 throughout
 the
 semester.
 You
 can
 choose
 
these
 from
 the
 list
 below.
 They
 can
 all
 be
 writing
 assignments,
 or
 they
 could
 all
 be
 technology
 
assignments
 or
 some
 can
 be
 writing
 and
 some
 can
 be
 technology.
 The
 dues
 dates
 are
 listed
 in
 the
 
syllabus.
 
 

Writing
 Assignments
 Requirements
 

Each
 writing
 assignment
 is
 worth
 20
 points
 should
 include
 the
 following
 sections:
 

 
Background
 (3
 points):
 This
 is
 a
 discussion
 of
 how
 the
 non-­‐mathematical
 and
 mathematical
 portions
 of
 your
 topic
 fit
 
together.
 You
 might
 include
 a
 historical
 background
 of
 the
 topic,
 definitions
 of
 terms,
 the
 discrete
 mathematics
 ideas
 
that
 are
 addressed
 (e.g.
 induction,
 logical
 fallacy,
 etc.),
 and
 some
 explanation
 about
 why
 these
 ideas
 were
 useful.
 

Examples
 (10
 points):
 In
 most
 of
 your
 writing
 assignments
 you
 are
 asked
 to
 discuss
 and
 describe
 an
 aspect
 of
 discrete
 
mathematics.
 Give
 two
 of
 three
 examples
 or
 techniques
 of
 the
 topic
 under
 discussion.
 Give
 general
 information
 and
 also
 
specific
 examples
 of
 the
 topic.
 

Bibliography
 (2
 points):
 List
 the
 references
 you
 used
 to
 complete
 this
 report.
 Just
 list
 title
 and
 author
 for
 any
 books
 and
 
articles
 you
 used.
 You
 should
 also
 include
 a
 list
 of
 people
 that
 you
 consulted
 or
 any
 other
 form
 of
 help
 that
 you
 received.
 
For
 example,
 you
 might
 obtain
 some
 of
 your
 information
 from
 the
 internet;
 in
 this
 case,
 you
 could
 include
 the
 
website.
 You’ll
 need
 at
 least
 one
 book
 or
 article
 as
 a
 reference,
 preferably
 two,
 and
 a
 total
 of
 at
 least
 two
 references.
 

You’ll
 notice
 that
 there
 are
 still
 5
 points
 unaccounted
 for.
 The
 remaining
 5
 points
 are
 for
 style:
 clarity,
 neatness,
 flow,
 
design,
 organization
 and
 creativity-­‐-­‐it’s
 important
 to
 be
 able
 to
 communicate
 your
 ideas.
 

Note:
 you
 don’t
 have
 to
 put
 your
 report
 in
 the
 precise
 order
 given
 above.
 You
 may
 prefer
 to
 use
 the
 assigned
 problems
 
to
 illustrate
 how
 the
 ideas
 of
 the
 subject
 fit
 together
 with
 the
 mathematical
 ideas
 that
 you
 will
 be
 using,
 in
 which
 case
 
Background
 and
 Examples
 would
 be
 interwoven.
 Just
 make
 sure
 that
 these
 aspects
 appear
 in
 your
 report.
 

Technology
 Assignments
 Requirements
 

Each
 technology
 assignment
 is
 worth
 20
 points
 should
 include
 the
 following
 sections:
 

 
Background
 (5
 points):
 This
 is
 a
 written
 paragraph
 of
 how
 the
 non-­‐mathematical
 and
 mathematical
 portions
 of
 your
 
topic
 fit
 together.
 In
 other
 words,
 you
 need
 to
 talk
 about
 what
 you
 needed
 to
 know
 about
 your
 topic
 in
 order
 to
 solve
 
the
 problems
 and
 how
 discrete
 mathematics
 fits
 into
 the
 picture.
 So
 you
 might
 include
 the
 definitions
 of
 terms,
 the
 
discrete
 mathematics
 ideas
 you
 used
 (e.g.
 induction,
 logical
 fallacy,
 etc.),
 and
 some
 explanation
 about
 why
 these
 ideas
 
were
 useful.
 

Solution
 (15
 points):
 In
 most
 of
 your
 technology
 assignments
 you
 are
 asked
 to
 write
 a
 program
 to
 solve
 a
 problem.
 Copy
 
and
 paste
 your
 code
 in
 a
 Word
 document
 and
 annotate
 each
 section
 of
 the
 code
 with
 explanation
 of
 what
 are
 you
 doing
 
in
 each
 section.
 Include
 a
 screen
 shot
 of
 the
 output
 of
 the
 program.
 If
 you
 are
 using
 EXCEL,
 include
 the
 excel
 file
 as
 a
 
separate
 attachment.
 

Writing
 and
 Technology
 assignments
 will
 be
 submitted
 in
 Canvas
 and
 checked
 with
 SafeAssign.
 Make
 sure
 to
 submit
 
your
 own
 work
 and
 give
 written
 explanation
 using
 your
 own
 voice.
 Compile
 your
 work
 in
 one
 document
 and
 save
 it
 in
 
pdf
 format
 and
 submit
 it
 by
 clicking
 on
 the
 assignment
 title.
 

Writing
 Assignments:
 
Combinatorics:
 
1.
 Describe
 some
 of
 the
 earliest
 uses
 of
 the
 pigeonhole
 principle
 by
 Dirichlet
 and
 other
 mathematicians
 

 
2.
 Describe
 the
 different
 models
 used
 to
 model
 the
 distribution
 of
 particles
 in
 statistical
 mechanics,
 including
 
Maxwell–Boltzmann,
 Bose–Einstein,
 and
 Fermi–Dirac
 statistics.
 In
 each
 case,
 describe
 the
 counting
 techniques
 
used
 in
 the
 model.
 

 
Logic:
 
 
3.
 Discuss
 logical
 paradoxes,
 including
 the
 paradox
 of
 Epimenides
 the
 Cretan,
 Jourdain’s
 card
 paradox,
 and
 the
 
barber
 paradox,
 and
 how
 they
 are
 resolved.
 

 
4.
 Describe
 how
 fuzzy
 logic
 is
 being
 applied
 to
 practical
 applications.
 
 
 

 
Proofs
 and
 Induction:
 
5.
 Look
 up
 some
 of
 the
 incorrect
 proofs
 of
 famous
 open
 questions
 and
 open
 questions
 that
 were
 solved
 since
 1970
 
and
 describe
 the
 type
 of
 error
 made
 in
 each
 proof.
 

6.
 Describe
 the
 origins
 of
 mathematical
 induction.
 Who
 were
 the
 first
 people
 to
 use
 it
 and
 to
 which
 problems
 did
 
they
 apply
 it?
 

 
Algorithms:
 
7.
 Describe
 six
 different
 NP-­‐complete
 problems.
 

 
8.
 Describe
 the
 historic
 trends
 in
 how
 quickly
 processors
 can
 perform
 operations
 and
 use
 these
 trends
 to
 estimate
 
how
 quickly
 processors
 will
 be
 able
 to
 perform
 operations
 in
 the
 next
 twenty
 years.
 

Relations
 and
 Functions:
 
9.
 Discuss
 the
 concept
 of
 a
 fuzzy
 relation.
 How
 are
 fuzzy
 relations
 used?
 

 
10.
 Describe
 how
 equivalence
 classes
 can
 be
 used
 to
 define
 the
 rational
 numbers
 as
 classes
 of
 pairs
 of
 integers
 and
 
how
 the
 basic
 arithmetic
 operations
 on
 rational
 numbers
 can
 be
 defined
 following
 this
 approach.
 

 
Recursion:
 
 
11.
 Describe
 a
 variety
 of
 different
 applications
 of
 the
 Fibonacci
 numbers
 to
 the
 biological
 and
 the
 physical
 sciences.
 

 
12.
 When
 are
 the
 numbers
 of
 a
 sequence
 truly
 random
 numbers,
 and
 not
 pseudorandom?
 What
 shortcomings
 have
 
been
 observed
 in
 simulations
 and
 experiments
 in
 which
 pseudorandom
 numbers
 have
 been
 used?
 What
 are
 the
 
properties
 that
 pseudorandom
 numbers
 can
 have
 that
 random
 numbers
 should
 not
 have?

 
Number
 Theory:
 
13.
 Describe
 the
 history
 of
 the
 Chinese
 remainder
 theorem.
 Describe
 some
 of
 the
 relevant
 problems
 posed
 in
 
Chinese
 and
 Hindu
 writings
 and
 how
 the
 Chinese
 remainder
 theorem
 applies
 to
 them.
 

 
14.
 Show
 how
 a
 congruence
 can
 be
 used
 to
 tell
 the
 day
 of
 the
 week
 for
 any
 given
 date.
 

 
Graph
 Theory:
 
15.
 Discuss
 the
 applications
 of
 graph
 theory
 to
 the
 study
 of
 ecosystems,
 to
 sociology
 and
 to
 psychology.
 

 
16.
 Explain
 how
 graph
 theory
 can
 help
 uncover
 networks
 of
 criminals
 or
 terrorists
 by
 studying
 relevant
 social
 and
 
communication
 networks.
 

Programming
 Assignments:
 
Sets:
 
17.
 a)
 Given
 two
 finite
 sets,
 list
 all
 elements
 in
 the
 Cartesian
 product
 of
 these
 two
 sets.
 b)
 Given
 a
 finite
 set,
 list
 all
 
elements
 of
 its
 power
 set.
 

 
Combinatorics:
 
18.
 Given
 an
 equation
 ?! + ?! + ⋯+ ?! = ?,
 where
 C
 is
 a
 constant,
 and
 ?!,?!,… ,?!
 are
 nonnegative
 integers,
 list
 
all
 the
 solutions.
 

 
19.
 Input
 the
 English
 alphabet
 (a
 string
 of
 26
 letters):
 

a) Generate
 all
 the
 permutations
 of
 a
 set
 with
 four
 elements
 
b) Generate
 all
 the
 combinations
 of
 a
 set
 with
 four
 elements
 

 
Logic:
 
 
20.
 Given
 the
 truth
 values
 of
 the
 propositions
 p
 and
 q,
 find
 he
 truth
 values
 of
 the
 conjunction,
 disjunction,
 exclusive
 
or,
 conditional
 statement,
 and
 biconditional
 statement
 of
 these
 prepositions.
 

 
21.
 Find
 as
 many
 positive
 integers
 as
 you
 can
 that
 can
 be
 written
 as
 the
 sum
 of
 cubes
 of
 positive
 integers,
 in
 two
 
different
 ways,
 sharing
 this
 property
 with
 the
 number
 1729
 

 
Algorithms:
 
22.
 Given
 an
 ordered
 list
 of
 n
 distinct
 integer,
 determine
 the
 position
 of
 a
 specific
 integer
 on
 the
 list
 using:
 

a) A
 linear
 search
 algorithm
 
b) A
 binary
 search
 algorithm
 
c) A
 tertiary
 search
 algorithm
 

 
23.
 Given
 a
 list
 on
 n
 integers,
 use
 the
 greedy
 algorithm
 to
 find
 the
 change
 for
 n
 cents
 using
 quarters,
 dimes,
 nickels
 
and
 pennies.
 

 
 
Relations
 and
 Functions:
 
24.
 Display
 all
 the
 different
 reflexive,
 symmetric
 and
 transitive
 relations
 on
 a
 set
 with
 six
 elements.
 

Recursion:
 
 
25.
 Given
 a
 nonnegative
 integer
 n,
 find
 the
 nth
 Fibonacci
 number
 using
 recursion.
 

 
26.
 Determine
 which
 Fibonacci
 numbers
 are
 divisible
 by
 5,
 which
 are
 divisible
 by
 7,
 and
 which
 are
 divisible
 by
 11.
 
Prove
 that
 your
 conjectures
 are
 correct.
 

 
Number
 Theory:
 
27.
 Given
 integers
 n
 and
 b,
 each
 greater
 than
 1,
 find
 the
 base
 b
 expansion
 of
 this
 integer.
 

 
28.
 Given
 a
 positive
 integer,
 determine
 whether
 it
 is
 a
 prime
 number
 or
 a
 composite
 number
 using
 trial
 division.
 If
 
the
 number
 is
 composite,
 find
 the
 prime
 factorization
 of
 the
 number.
 
 

 
29.
 Given
 two
 positive
 integers,
 find
 their
 least
 common
 multiple.
 

 
Graph
 Theory:
 
30.
 Given
 the
 vertex
 pairs
 associated
 to
 the
 edges
 of
 a
 graph,
 construct
 an
 adjacency
 matrix
 for
 the
 graph.
 (Produce
 
a
 version
 that
 works
 when
 loops,
 multiple
 edges,
 or
 directed
 edges
 are
 present.)
 

 
31.
 Given
 the
 vertex
 pairs
 associated
 to
 the
 edges
 of
 a
 multigraph,
 determine
 whether
 it
 has
 an
 Euler
 circuit
 and,
 if
 
not,
 whether
 it
 has
 an
 Euler
 path.
 Construct
 an
 Euler
 path
 or
 circuit
 if
 it
 exists.
 

 
32.
 Given
 the
 list
 of
 edges
 and
 weights
 of
 these
 edges
 of
 a
 weighted
 connected
 simple
 graph
 and
 two
 vertices
 in
 this
 
graph,
 find
 the
 length
 of
 a
 shortest
 path
 between
 them
 using
 Dijkstra’s
 algorithm.
 Also,
 find
 a
 shortest
 path.