Discrete Maths, Lecture-3

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

This lecture introduces the Set theory and how it relates to Logic. It shows how most of the things in Set theory can be proved using the laws relating to AND, OR that we learned in logic. Shai also discusses two nice tricks to do counting that has something to do with sets.

Here are my notes...

Discrete Maths, ProblemSet#1

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

Scheme Programs are typed here, others are scanned...
P3.a-

(define (find-goals-misses score)
  (define (aux goals near-misses)
    (let ((tmp (+ (* 11 goals) (* 7 near-misses))))
      (cond
       ((> score tmp)
 (aux (+ goals 1) near-misses))
       ((< score tmp)
 (aux goals (- near-misses 1)))
       (else 
 `((goals ,goals) (near-misses ,near-misses))))))
  (aux 0 (quotient score 7)))

P8-

;following code is copied from sicp
;changed a lit bit to make it run on plt-r5rs
(define-syntax cons-stream
  (syntax-rules ()
    ((cons-stream a b)
     (cons a (delay b)))))
(define (stream-car stream) (car stream))
(define (stream-cdr stream) (force (cdr stream)))
(define stream-null? null?)
(define the-empty-stream '())
(define (stream-filter pred stream)
  (cond ((stream-null? stream) the-empty-stream)
        ((pred (stream-car stream))
         (cons-stream (stream-car stream)
                      (stream-filter pred
                                     (stream-cdr stream))))
        (else (stream-filter pred (stream-cdr stream)))))
(define (stream-ref s n)
  (if (= n 0)
      (stream-car s)
      (stream-ref (stream-cdr s) (- n 1))))
(define (integers-starting-from n)
  (cons-stream n (integers-starting-from (+ n 1))))
(define primes
  (cons-stream
   2
   (stream-filter prime? (integers-starting-from 3))))
(define (square x) (* x x))
(define (divisible? x y) (= (remainder x y) 0))
(define (prime? n)
  (define (iter ps)
    (cond ((> (square (stream-car ps)) n) #t)
          ((divisible? n (stream-car ps)) #f)
          (else (iter (stream-cdr ps)))))
  (iter primes))

;solution to the problem
(define (multiply-n-primes n)
  (define (iter ps n a)
    (if (= n 0) a
 (iter (stream-cdr ps) (- n 1) (* a (stream-car ps)))))
  (iter primes n 1))
(define (find-p8-n)
  (define (iter i)
    (let ((tmp (+ 1 (multiply-n-primes i))))
    (if (prime? tmp)
 (iter (+ i 1))
 tmp)))
  (iter 1))
;Ans: 30031

Here are the other solutions...

Programming In Scala: Chapter#2,3 notes

I did a quick reading of above mentioned chapters from Programming in Scala by Martin Odersky and noted a few key things...

A scala compiler does not infer function parameter types, it does so only for the function return type.

If function is recursive, you must specify its return type.

If function body has only a single expression then you can optionally leave out the curly braces.

"Unit" type is returned from the functions that don't do anything useful, its like java void.

If a function literal consists of only one expression that takes the argument then we may skip writing the argument explicitly. Let me give an example..

array.forEach(arg => println(arg))

is equivalent to

array.forEach(println)

There are two kinds of variables in scala, var and val. val are final and can't be reassigned. Although the variables defined with val are final. but the object, they are refering to, might very well be mutable.

If a method takes only one parameter then you can call it without using the parenthesis. In reality there are no operators in scala(as in scheme:)) and the op looking variables are actually functions taking advantage of the mentioned fact. For example, "1 + 2" is actually "1.+(2)"
If a method is used in operator notation like a op b, then it means a.op(b) except in the case where method name ends with colon and then "a op: b" mean b.op:(a)

If you say greet("hi") on a variable, it automatically gets converted to greet.apply("hi") that is why array elements can be accessed with array(index) syntax. Similarly greet("hi")=value is transformed into greet.update("hi",value).

Pretty much for every data structure, scala provides both, mutable and immutable implementations.

Tuples can be used for multiple value return from a function.

semicolons are mostly optional.

Scala supports functional as well as imperative programming but encourages to use functional unless its justifiable to use the other one and hence prefer val over var, immutable object over mutable object and functions with no side effects over functions with side effects.

Discrete Maths, Lecture#2

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

This lecture starts with Shai describing how mathematicians "reach" the proof. They start with trying to convince the other person about the new idea they've come up with and asking questions like.. do you get what I mean?... do you believe that its true? And that is how proofs begin... does it seem reasonable?.. does it seem plausible?.. do you believe in it? So basically you think and think and think, you get the idea, you check the idea, if found a hole you plug the the hole.. then check again..iterate this process and once all the holes are filled.. then you write the idea in english or in rigorous mathematical notation.

However when you need to prove something, first you should try to convince yourself that the idea you're trying to prove is indeed true by way of taking particular examples and see its true. Once you've convinced yourself and have a better understanding of the idea then you can think about the proof better.


On a high level this lecture answers following questions..
How to build electric circuits using truth table?
How to do arithmatic(addition in particular) using circuits and logic?
High level notion of NP and NP-complete problems?
Using reduction to prove if a problem is NP-complete or not?

Here are my notes...

Installing Fedora11 from Hard-disk

I have had Fedora-9 installed since long and wanted to move to Fedora-11. I also have windows xp already installed, Here is how I installed Fedora-11 from the hard disk itslef...

• Booted the machine in windows, downloaded the fedora11 dvd iso in one partition(d:\, its FAT32).


• Extracted images/install.img from fedora archive into d:\images\


• Extracted vmlinuz, initrd.img from isolinux directory in the fedora archive into c:\boot\ from the above iso.


• Downloaded grub4dos-0.4.1.zip and extracted folder grub into c:\boot\.


• Edited c:\boot\grub\menu.lst, and appended following..
  title my fedora-11 install
  kernel (hd0,0)/boot/vmlinuz
  initrd (hd0,0)/boot/initrd.img
  


• Extracted file grldr from grub4dos-0.4.1.zip to c:\.


• Edit boot.ini and ..append c:\grldr="Start Linux" at the end with a newline.


• Reboot the machine, select "my fedora-11 install" , on prompt for source of installation select Hard-disk, then select the partition where you saved the fedora iso and then the anaconda installer launches. I like to keep SElinux disabled.

Others...This is the extra stuff I did to start with....

• Added rpmfusion yum repository to get smplayer.


• Installed kdebase package for konsole.

Discrete Maths, Lecture#1

I'm following a course on discrete mathematics available here. This course was taught at arsdigita university by Shai Simonson who is a professor in computer science department at stonehill college.

I thought a little bit through and decided, to best learn from the available video lectures I should use them like the classroom lecture and take notes. I'm going to write blog post with every lecture I watch and post my notes also.

Lecture#1, Introduction

In this lecture, Shai introduces the course as being a course on all the various techniques of "counting". He gives examples of some counting problems such as in how many ways can we chose two students from a class of n students, how many pins are there in a n-lane bowling alley etc. In discrete maths, it is very important to do proofs, so the lecture starts with discussing the basic proof techniques, proof by contradiction and proof by induction. He gives examples for both the techniques. Next part of the lecture introduces basic logic and boolean algebra.

Here are the notes that I took...

JASI v1 is done

JASI - Just Another Scheme Interpreter

code is here.
other posts related to jasi are here.

I'm done writing java implementation of the scheme interpreter that started just to better my understanding of interpreters in general and to learn what it takes to write one.

This implementation of mine doesn't solve any practical purpose(as of now atleast) and not an optimized one, I gave more importance to modularity and easy readability of the code.

It complies to a subset of R4RS and passes a subset of R4RS tests written by Aubrey Jaffrey, that subset is available with the code in the file tests.scm in top level directory.

Code Organization:
It consists of 4 main packages..

1. jasi.parser
This package contains the classes responsible reading the scheme expressions and provide the functionality of "read". Tokenizer.java does the job of lexical analysis and Reader.java gets tokens from it, reads S-expressions.

2. jasi.datatypes
The classes here represent various scheme datatypes.

3. jasi.symantics
This is the engine of the interpreter. Scheme.java has the "eval" to evaluate s-exps and this is where the language behavior is realized. Environment.java contains the code for maintaining environment and also initial global enironment that becomes available to the user in the interactive mode. If one wants to add another primitive procedure(that can't be implemented in scheme using existing primitives), then he needs to add binding for same in the global environment in Environment.initGlobalEnv() method.

4. jasi.symantics.procedure
CompoundProcedure.java contains the behavior of how user defined procedures are evaluated. PrimitiveProcedure.java contains implementation of (almost)all the primitive procedures.

I've tried to implement only the essential functionality in java, other primitives are written in scheme itself in the file src/main/resources/preloadedscm.scm that is loaded at interpreter startup. If one needs to add another primitive that can be written using the existing primitives, this is the place.

For more info, Please read the "readme" included in the code.