Difference between revisions of "SKE Algo II (Winter 2019)/Homework 0/Problem set"

From srakrn | Wiki
Jump to navigation Jump to search
(Created page with "= Introduction = == Grading policy == * '''Intuition based, not solution based:''' This homework will be graded based on your attempt and not your solution. Giving a complet...")
 
Line 1: Line 1:
−
= Introduction =
 
−
 
−
== Grading policy ==
 
−
 
−
* '''Intuition based, not solution based:''' This homework will be graded based on your attempt and not your solution. Giving a completely wrong answer will '''not''', and never make your score zero.
 
−
* '''Think of them as an long-term brain teaser:''' Don’t complete them in one day, or you’ll missed the chances of perfecting your understandings and perspective of the problems little by little.
 
−
 
−
== Ethics and Code of Conduct ==
 
−
 
−
* '''Zero tolerance on plagiarism:''' This course enforces a zero tolerance policy on plagiarism.
 
−
* '''Wrong answer is better than correct but copied answer:''' The scoring criteria is designed to heavily penalise copied answers.
 
−
* '''No submission is better than turning in copied submission:''' The scoring criteria is designed to motivate students to submit their original work.
 
−
* '''Feel free to discuss:''' Discussion among friends and colleagues are completely normal, and we encourage that. However, please '''indicate your collaborators''', as it will be used to track works’ originality.
 
−
 
 
= Revisiting proofs 1 =
 
= Revisiting proofs 1 =
  

Revision as of 23:49, 4 February 2020

Revisiting proofs 1

These assignments were adapted from Discrete Mathematics, Douglas E. Ensley and J. Winston Crawley, Wiley.

Implication A

Prove or disprove that for every integer Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \geq 1} , if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} is odd then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^2 + 4} is a prime number.

Implication B

Prove or disprove that for every positive integer Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2n^3} is divisible by 3.

Revisiting proofs 2

These assignments were adapted from Discrete Mathematics, Douglas E. Ensley and J. Winston Crawley, Wiley.

Implication C

Prove or disprove that for every positive integer Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} , if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} is odd then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^3-n} is divisible by 4.

Implication D

Prove or disprove that for all integers Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n > 4} , if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} can be expressed in the term of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z^2} for any integers Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z} , then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-1} is not a prime number.

Implication E

Prove or disprove that for all integers Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} , if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^2} is even then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} is even. Hint: Use contrapositive.

Revisiting proofs 3

Parts of these assignments were adapted from Discrete Mathematics, Douglas E. Ensley and J. Winston Crawley, Wiley.

Exhaust A

Proof that if an integer Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} can be written in the form of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z^3} for any integers Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z} , then it must satisfy one of the following critera:

  • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} must be a multiple of 9,
  • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} must be 1 more than a multiple of 9, or
  • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} must be 1 less than a multiple of 9.

Exhaust B

Prove or disprove that for any integer Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^2 + 2 } is even.

Exhaust C

Prove or disprove that every integer not divisible by 3 had a square that is of the form Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 3k + 1} .

Revisiting proofs 4

In this section, use proof by induction to prove the given statement. Make sure to clearly indicate your steps of induction along with the induction hypothesis (I.H.).

Induction A

Prove that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^2 + n} is even for any positive integers Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} .

Induction B

Prove that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{i=1}^{N} i = \frac{(n)(n+1)}{2}} for any positive integers Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} .

Induction C

Prove that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{i=1}^{N} i = \frac{(n)(n+1)(2n+1)}{6}} for any positive integers Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} .

Retrieved from "https://srakrn.me/mediawiki/index.php?title=SKE_Algo_II_(Winter_2019)/Homework_0/Problem_set&oldid=68"