Discrete Maths, ProblemSet#2

These are my solutions to 2nd problem set of discrete mathematics course taught at Arsdigita university by Shai Simonson. Other posts relating to this are here.

Here they are...

Discrete Maths, Lecture-5

These are my notes from 5th lecture of discrete mathematics course taught at Arsdigita university by Shai Simonson. Other posts relating to this are here.

In this lecture, Shai talks about functions and their types definitions i.e. one-one, onto and one-one onto... about comparison of order of growth of functions that involve exponents and log... and finally calculates sum of a series using the powerful concepts of manipulating known sums, describing the problem in appropriate notation(sigma notation).

Here are my notes...

proof techniques

Proving things is an art, there is no mechanical way to do it. Like any other art one has to practice it to master it. One should get in the habit of asking why something is true/not true and then try to prove/disprove it.However, there are certain tricks/ways that can help shape the thinking when starting to think the proof.

For theorems of type, for All x: P(x)->Q(x)

Direct Proof:
We start with assuming that P(x) holds and then try to reach Q(x).

Proof by Contrapositive:
This proof technique uses the fact that contrapositive of p->q (which is -q->-p) has same truth value as p->q. So we can try to prove the contrapositive of original with direct proof technique.

Vacuous Proof:
If we can prove that P(x) is always false, then the statement p->q automatically becomes true.

Trivial Proof:
If we can prove that Q(x) is always true, no matter what.

For theorems of type, for all x: P(x)

Proof by Cases - Exhaustive Proof:
If x can only have a limited set of values, then we can apply P to *all* those values of x, if they all happens to be true(which has to be the case for theorem to be correct) then we have the proof.

Proof by Cases - Proof with limited Cases:
1. Some times, even though x can have a large(may be infinite) set of values but we can still use case techniue. For example let say P(x) is of the form of Q(sin(x)), then its enough to prove that P(x) holds for x E [0, PI], as sin(x) repeats itself for other values of x.
2. In cases something like x being real number, it is enough to show that P(x) holds for 3 cases which are.. x<0, x>0 and x=0

For theorems of type, there exists x | P(x)
It'll be enough to find just one value of x for which P(x) holds.

General
Proof by Contradiction:
With this technique, we start with the assumption that negation of the theorem statement is true and reach a contradiction.

Try to find counter-example:
For example if we were to prove a theorem of type, for all x:P(x); if we can find one value of x for which P(x) is false then we have disproved the theorem.

Proof by Induction:
Here we prove a base case, Make an inductive assumption and prove the incremental case. Way to increment has to be general enough that all the possible cases are covered.


Reference - Section 1.6 and 1.7 of Discrete Mathematics & Its Applications 6th Edition by Kenneth H Rosen.

Discrete Maths, Lecture-4

These are my notes from 4th lecture of discrete mathematics course taught at Arsdigita university by Shai Simonson. Other posts relating to this are here.

This lecture introduces the formalism to compare functions based on their order of growth. This is important for algorithms because actual running time of an algorithm is very sensitive to the implementation details, hardware its running on, load on the machine etc etc. So they can't be compared based on their actual running time but order of growth.

Here are my notes...

Programming In Scala: Chapter#6,7 notes

Ch6-
Fuctional objects = immutable objects, this chapter basically shows you how to write class for immutable Rational object. Many key concepts of writing classes in scala are covered.

In scala class, Two kind of constructors, primary and auxiliary. Its mandatory that an auxiliary constructor invokes anothe constructor.
Only primary constructor can invoke the constructor of superclass.

In scala class, Getters and setters are "generated" only for the field variables(unless they are declared private)

override keyword needs to be explicitly used when overriding a method of the superclass.

Though scala compiler allows you to use '$' in identifier name, but it *MUST NOT* be used as its reserved for identifiers generated by scala compiler and there may be clashes.

Conventionally, identifiers for constants in java are like X_OFFSET, but in scall its recommended to use only first letter capital for constants and same identifier in scala should be XOffset.

A literal identifier trick can be used if you want to use a reserved word as identifier. A literal identifier is an identifier enclosed in back quotes.

Method overloading is supported that is same method name can be used for two different methods as long as there is some difference in method signature.

There is an implicit conversion trick that allows you to convert any type into any other type. Its very powerful but highly recommended not to be used and hence I'm not even mentioning here how its done :)

Ch7-
if, while, do-while, for, try, match - all return some value

Scala assignment always returns the unit value, ().

It recommends to use recursion rather than while loops to achieve the same effect.

for loop is swiss army knife in scala(seems inspired from loop macro in lisp), it can be used to do many different iteration tasks. Please see section 7.3 for its usage.


Scala's exceptions behave like same in java, thrown using throw keyword.Catching exception syntax is different a little bit and seems to less the code needed in handling multiple exceptions.

If a method throws an exception, its not mandatory for it to declare it using the throws as in java.

finally keyword is also available whose behavior is exactly as that in java.

"Match" is "switch" of java. However switch allows only matching of integers and enums whereas "Match" lets you select using arbitrary patterns.

Programming In Scala: Chapter#4,5 notes

Ch4-
public is scala's default access level.

Method parameters in scala are val, they can't be reassigned.

In the absence of any returned statement, scala returns the last expression value computed by the method. The recommeded or the functional way is not to have explicit return statements and to definitely avoid multiple return statements. This philosophy encourages you to make small methods that just do one thing and not many.

Braces around the method definition are optional if there is only one expression inside the method body.

If you have a method whose return type is Unit, you can write it like following(removing the = sign) so that it looks like a procedure and clarifies the intention that its there for side effects only..
def add(a:Int) {sum+=a}

One thing to notice here is that whenever you write a function in procedural style(that is without equal sign), its infered return type is definitely going to be Unit no matter what the body contains.
A semicolon is *must* if you write multiple statements on a single line.

The rules of semicolon inference:
1. The line in question ends in a word that would not be legal as the end of a statement, such as a period or as an infix operator.
2. The next line begins with a word that cannot start with a statement.
3. The line ends while inside parentheses(...) or brackets [...], because these cannot contain multiple statements anyway.

Sigleton Objects: Scala classes can't have static fields or method, instead there can be singleton object whose definition looks exactly like scala classes with class replaced with keyword object. If there is a class with same name then singleton object is called companion object of that class, similarly that class is called companion class of this singleton object. Companion class/object can access private members of each other. A singleton object and the companion class *MUST* be defined in the same source file.


Ch5-
Other than the value types(corresponding to every primitive type in java) such as Byte, Short, Int, Long, Float, Double and Boolean, scala has a type called symbol which is like scheme symbols and literal representation is same as scheme symbols, they start with single quote e.f.'symbol

Symbols are interned, if you write the same symbol twice, they both refer to the same symbol object.

unary_x, where x = +/-/!/~ can be used in prefix notation that is 2.unary_- is same as -2.

If a method takes no arguments, it can be written in postfix notation, that is s.toStrin() can be written as "s toString".

A == B in scala first checks to see if A is null, if its not then it checks
A.equals(B). In java '==' compares referential equality which here is done with method eq(this only applies to the objects which can be directly mapped into java objects)

Scala doesn't have operators, so how does 2+2*7 return 16. The answer is that precedence is based on the first letter of the method name and method starting with * have higher precedence than methods starting with +.

The associativity(when there are multiple methods with same precendence) is determined by the last character of the method name.

For every basic scala type, there is a rich wrapper that provides more utility methods on it.

p->q <=> p only if q <=> q unless -p

Note: '-p' represents NOT p.

As an student whenever I learned above, I always used to be confused if the three were equivalent. Here is how I can remember them now.

Let say p = I'll eat banana.
q = Its not evening.

p only if q
The sentence, "I'll eat banana ONLY if Its not evening." is equivalent to "If I eat banana that means its not evening" which is p->q

q unless -p
The sentence, "Its not evening unless I'm not eating banana." is equivalent to "Its not evening if I'm eating banana" which is "If I'm eating banana then It's not evening" which p->q

One more important thing I learned is that mathematical logic statements have nothing to do with same in natural languages such as english, we draw this parallel just to remember them better. Natural language statements are often ambiguous but logic statements always have a precise meaning.