Study Guides
(238,096)

Canada
(114,916)

University of Ottawa
(9,484)

Computer Science
(7)

CSI2101
(1)

Najib Zaguia
(1)

# CSI 2101 Summary.pdf

Unlock Document

University of Ottawa

Computer Science

CSI2101

Najib Zaguia

Winter

Description

CSI 2101
Summary
Winter 2013 CSI 2101 Summary, Winter 2013
Propositional Logic
PROPOSITION : a statement with some definite meaning, and has a truth value. You may not know
the actual truth value, and the truth value may depend on the situation or the context.
o Proving propositions are equivalent or consistent: show they yield the same truth values, for
example using a truth table.
TAUTOLOGY : a compound proposition that is true regardless of the truth values of the atomic
propositions
CONTRADICTION : a compound proposition that is false regardless of the truth values of the atomic
propositions
CONTINGENCY : can be true or false, depending on the truth values of the atomic propositions.
Predicate Logic
PREDICATE : modeled as a function from objects to propositions. If you have , is the
variable, and is the property. Alternate definition: a function mapping an objectto proposition
.
o "The dog is sleeping." Same thing as saying is sleeping,where is the dog. is the
property of sleeping. So, we have .
o Convention: lowercase objects, uppercase predicates.
PREDICATES IN CMPUTING
o PRECONDITION : what holds before the code segment. Can be denoted .
o POSTCONDITION : what holds after the code segment. Can be denoted .
To verify a postcondition holds, we must start from the assumption that the
precondition holds and go over every stop of the code and examine what it does to
see whether the postcondition is really true.
Q UANTIFIERS: provide a notation that allows us to count how many objects in the universe of
discourse satisfy a given predicate.
o UNIVERSAL QUANTIFIER : means "for all."
True if allare true.
False if one is false
o EXISTENTIAL QUANTIFIER: means "there exists."
True if there is one that is true
False if allare false
Can define new quantifiers, like means there exists exactly one in the
universe of discourse.
o FREE VARIABLE: a variable that is not defined. Example: in , is a free variable.
o BOUND VARIABLE : when a variable is bounded by or . Example: in , is a bound
variable.
Predicate becomes a proposition when all variables are bound.
Proofs
PROOF : correct/well reasoned/logically valid, and complete/clear/detailed argument that
rigorously and undeniably establishes the truth of a mathematical statement.
o THEOREM : a statement that has been proven true.
o AXIOM , POSTULATE, HYPOTHESIS , PEMISE : assumptions, often unproven defining the
structures about which we are reasoning.
1 | P a g e CSI 2101 Summary, Winter 2013
o RULES OF INFERENCE: patterns of logically valid deductions from hypothesis to conclusions.
o LEMMA : a minor theorem used as a stepping-stone to proving a major theorem.
o OROLLARY
C : a minor theorem proved as an easy consequence of a major theorem.
o CONJECTURE : a statement whose truth value has not been proven. May be widely believed to
be true, regardless.
o THEORY : a set of all theorems that can be proven from a given set of axioms.
o ORMAL PROOF
F : sequence of statements ending in a conclusion. Statements preceding the
conclusion are called premises. Each statement is either an axiom, or is derived from
previous premises using a rule of inference.
o IFORMAL PROOFS : Formal proofs are a pain and really tedious. We don't need that much
detail. Obvious and easy steps are skipped or grouped together. Some axioms may be
skipped (implicitly assumed). Must still be formal and precise to a certain degree.
PROVING EXISTENTIAL STATEMENTS : if in the form , just find one that satisfies .
DISPROVING THE NEGATION OF AN EXISTENTIAL STATEMENT : if in the form , just find one
counterexample that satisfies .
DISPROVING AN EXISTENTIAL STATEMENT : to disprove, you need to prove the negation. In other
words, if you're trying to disprove , then prove ( ) .
PROVING A UNIVERSAL THEOREM : if the theorem is in the form ( ), you can
prove it by:
o EXHAUSTION : works of the domain is finite or the number of for which holds is finite.
Just prove for every in your domain.
o DIRECT PROOF : assume and derive .
o
CONTRADICTION : show that . So assume the negation of the statement to be proven,
and show it leads to some sort of nonsense. The fact that you reached nonsense means an
assumption was wrong, this assumption being that you assumed .
o CONTRAPOSITION : prove the contrapositive directly. The contrapositive is defined as
( ) .
Advantage: don't have to make potentially error-prone negation of the statement,
and you know what you want to prove.
Disadvantage: only usable for statements that are universal and conditional.
CHECKLIST for writing good proofs:
Be clean and complete
State the theorem to be proven
Clearly mark the beginning of the proof
Make the proof self-contained (introduce and identify all the variables)
Write in full sentences
Give reason for each assertion (by hypothesis, by definition, by substitution…)
Use connecting words (the, thus, hence, therefore, observe, note, let…)
STRATEGY : Say you're given if , then . Imagine elementsthat satisfy . Ask yourself,
"Must they satisfy ?" If the answer is:
o "Yes." Use the reasons why you feel this way as a basis for a direct proof.
o "Not really." Think why, you may come up with a counterexample. If you can't find a
counterexample, think of why.
Maybe from assuming , you can derive a contradiction.
Maybe from assuming , you can derive .
2 | P a g e CSI 2101 Summary, Winter 2013
N ORMAL INDUCTION : In order to prove statement by induction, we must first prove the base
case, i.e. prove that is true. Then, we assume is true (induction hypothesis), and prove
that , called the inductive step.
If the base case and inductive step can be proved, then we say is proved by mathematical
induction.
o Is a rule of inference that says:
( )
W ELL-ORDERED : A set is “well-ordered” if every non-empty subset of has a least element.
STRONG INDUCTION : In order to prove statement by strong induction, we must first prove the
base case, i.e. prove that is true. Then, we assume is true (induction
hypothesis), and prove that , called the inductive step.
If the base case and inductive step can be proved, then we say is proved by strong induction.
o Is a rule of inference that says:
TRUCTURAL INDUCTION
S : In order to prove statement by structural induction, we must first
prove the base case, i.e. prove that is true for each element in the base definition of the
set . For the inductive step, for every way to construct , show that
.
Complexity
COMPLEXITY : the number of steps that it takes to transform the input data into the desired output.
It is a function of the size of the input (or size of the instance). In general, we will deal with the
worst case complexity.
The main question is how the complexity behaves asymptotically, i.e. when the problem sizes tend
to infinity.
We’re not interested in the exact time it takes to run, we usually just want to compare two
algorithms. We will choose the right algorithm based on which has the better growth rate.
B -O : We say is "big oh" of if there exists two constants and such that
for . To prove a function is ( ), find these two constants
and
.Only the largest term
matters. It means that an algorithm has the complexity of AT MOST .
B -O MEGA : We say is "omega" of , or if for all
. It means an algorithm has the complexity of AT LEAST .
B -T HETA : We say is "theta" of , or if it is( ) ( ) It
means the complexity IS EXACTLY .
( )
{ ( )
( )
3 | P a g e CSI 2101 Summary, Winter 2013
Recursion
RECURSION : the practice of defining an object in terms of itself, or a part of itself. An inductive
proof establishes the truth of recursively in terms of .
o Can define a recursive function , and prove the explicit value of using induction.
o
Must be careful that it's well-defined
It is defined for each element in the domain
It is defined unambiguously
o An infinite set may be defined recursively by giving:
A small finite set of base elements of
A rule for constructing new elements of from previously established elements
Implicitly, has no other elements but these
FIBONACCI N UMBERS : They are defined by the function
.
o HEOREM
T : where √ . Proof is done by induction.
Recursive definitions can be used to describe algorithms. Typical problem solving approach: solve
the problem for smaller/simpler sub-problems and obtain the result from that.
Program Correctness
CORRECT : a program is correct if it produces the correct output for every input.
PARTIALLY CORRECT : a program is correct if it produces the correct output for every input for which
the program eventually halts.
PRECONDITION : the initial assertiois the condition that the program’s input (its initial state) is
guaranteed (by its user) to satisfy.
POST -ONDITION : the final assertionis the condition that the output produced by the program
(its final state) is required to satisfy.
H OARE TRIPLE NOTATION : the notation { } means that for all inputs such that is true, if
program (giveninput ) halts and produces output , then is true. That is,is
partially correct with respect to specification . Deduction rules for Hoare Triple statements:
o COMPOSITION RULE : if program given condition produces condition , and given
condition produces , then the program followed by if given yields .
{ }
{ }
{ }
o IF STATEMENTS: Let be the condition. Then
{ }
{ }
o I -THEN-ELSE RULE: Let be the condition. Then
{ }
{ }
{ }
o LOOP INVARIANTS : Let be the condition. For a while loop , we say that is a
loop invariant of this loop if { } . So if is true before executing the body, then
remains true after.
{ }
{ }
4 | P a g e CSI 2101 Summary, Winter 2013
PROVING THAT A LOOP HALTS : For each iteration , we associate an integer such that{ }
is a decreasing sequence. Because of the well-ordering principle of any subset of integers, this
sequence of integers { } is finite.
Number Theory
DIVIDES: divides , denoted for if there is an integersuch that .
o FACTOR /DIVISOR: if , then is a factor/divisor of .
o M ULTIPLE: if , then is a multiple of .
o FACTS:
If and , then
If , then
If and , then
If such that and , then when
DIVISION ALGORITHM : Let and . Then there are unique integers and , with
, such that . remainder, dividend, quotient.
CONGRUENCE : If and then is congruent to modulo (denoted
or ) if .
o FACTS:
if and only if such that
If and , then and
We can add or multiply (not divide) the two sides of the congruence by the same
integer.
o ADDITION : the operation is defined by
DDITIVE INVERSE
A : if is the additive inverse ofmodulo .
Note that 0 is its own additive inverse.
ADDITIVE IDENTITY : if , then .
o
M ULTIPLICATION : the operation is defined by
M ULTIPLICATIVE INVERS: if , then is called the multiplicative inverse.
Note that this inverse does not always exist.
M ULTIPLICATIVE IDENTITY : if , then .
PRIME : the number is prime if there are exactly two positive factors: 1 and itself.
o FUNDAMENTAL HETREM OF A RITHMETIC: Every positive integer can be uniquely written
as a prime or as the product of two or more primes, where the primes are written in order
of non-decreasing size. The non-primes are called composite integers.
o THEOREM : If is a composite integer, then has a prime divisor less than or equal to .
√
Can be used to show that a number is prime.
o Primes are the building blocks of the natural numbers.
M ERSENNE NUMBER : a number of the form , .
o ERSENNE PRIME
M : a prime number of the form , where is a prime number.
o THEOREM : If is a Mersenne prime, then is a perfect number (i.e. its divisors
equal itself).
5 | P a g e CSI 2101 Summary, Winter 2013
G REATEST COMMON DIVISOR : denoted where are integers, it is the largest integer
such that and .
o RELATIVELY PRIME : two numbers and are relatively prime if
LEAST COMMON MULTIPLE : denoted where are integers,it is the smallest positive
integer that is divisible both byand
THEOREM : If and are integers, then
EUCLID: ( )
THEOREM : Let be integers. If we have , then .
THEOREM : , such that
LEMMA : , if and , then .
LEMMA : If is prime and , then there exists an such that .
THEOREM : If , and , then .
LINEAR CONGRUENCE : a congruence of the form . Solving the congruence is finding
the 's that satisfy it. You can solve it by findinsuch that , where is the
multiplicative inverse of . The inverse is unique.
o THEOREM : If is prime, then . Note that the converse is not true.
FERMAT ' LTTLE HTOREM : If is prime and is an integer not divisible by , then
. Furthermore, for every integer , .
CARMICHAEL NUMBER : a composite number such that for all relatively prime
to . These numbers are important because they fool the Fermat primarily test; the are "Fermat
liars." They have at least three prime factors.
Hashing Functions
Two functions:
1. Indexing hash tables (data structures which support

More
Less
Related notes for CSI2101