Updates on your Grading System

Please take note the following changes of your grading system.

Homework/Quizzes    20%

Exams                      50%

Laboratory MPs          20%

Final Project              10% 

Notes on Recursion

Download the notes on recursion.

Homework: Recursive Function in Erlang

1. Fibonacci

For this part you will create several implementations of the Fibonacci function fib(N), which returns the N^th value in the Fibonacci sequence.
Make sure to follow this specification for fib(N):

• fib(0) = 0
• fib(1) = 1
• fib(N) = fib(N - 1) + fib(N - 2)     (N > 2)

Your Tasks

1. Create a module named "fib", in the file "fib.erl".
   
2. Create a non-tail-recursive function fib_p that takes a single argument N, and returns the N^th value in the Fibonacci sequence. Use pattern matching on the arguments to specify the various cases for this function.
   Add fib_p to your module's export-list, and test it to make sure it works properly.
   
3. Create another non-tail-recursive function fib_g with the same specification as before, but use guards (i.e. when clauses) to specify the various cases for this function.
   Add fib_g to your module's export-list, and test it to make sure it works properly.
   (There should be no difference in performance between fib_p and fib_g; implementing both of them will just give you practice with the syntax.)
   
4. Create a third function tail_fib with the same specification as before, but implement it to be tail-recursive. (You will need a helper function to implement this to be tail-recursive.)
   Add tail_fib to your module's export-list, and test it to make sure it works properly.
   
5. Start an Erlang interpreter, compile your module, and perform these simple experiments. Write your answers to the following questions in a file named "answers.txt".
   
   1. Starting with N = 20, and increasing by steps of 5, how far do you get before fib_p(N) takes more than five seconds to run? Why does it behave this way?
   2. How long does it take to compute tail_fib(10000)? Why?

2. Square-Multiples and the Möbius Function

The Möbius Function is a simple classifier of positive integers, devised by (surprise) August Möbius. Given a positive integer n, the Möbius function μ(n) returns:

• 0 if the number is a multiple of a square
• -1 if the number has an odd number of distinct prime factors
• 1 if the number has an even number of distinct prime factors

The n = 1 case is a special case; μ(1) is defined to return 1.
You can probably see right away that this function is all about generating and then analyzing the list of prime factors for the input value. A number is a multiple of a square if it has any duplicate prime factors; for example, 12 = 2 × 2 × 3, so it is a multiple of a square, and therefore μ(12) = 0.
(If you want to learn about some of the more esoteric qualities of this function then you can look at this page.)
For this section we will focus on one interesting detail about the Möbius Function; runs of square-multiples. We want to write a program that finds the first run of square-multiples of length N. For example, the first run of three square-multiples starts with 48; 48, 49 and 50 are all multiples of squares.
All of your recursive functions for this section should be tail-recursive! Tail recursion is an extremely important aspect of Erlang, so it is important for you to be familiar with it. This section will give you plenty of opportunities to practice implementing tail-recursive functions.

Your Tasks

1. Create a module named "mobius", in the file "mobius.erl".
   
2. Create a function is_prime that takes a single argument N, and returns true if the number is prime, or false if the number is not prime.
   Your implementation doesn't need to be particularly fast or clever. For example, you can create a helper function that iterates over integers from 2 to sqrt(N), checking whether N is evenly divisible by each value. If N is not evenly divisible by any value then it is prime; otherwise, it is not prime.
   
   • Hint 1: You can use the remainder operator rem to check if N is evenly divisible by a particular value. A rem B returns the remainder from dividing A by B.
   • Hint 2: Computing square-roots is costly. A better approach is to take the test value, which we will call Divisor, and if Divisor × Divisor > N then you are done. (Could be a good when-guard...)
   Add is_prime to your module's export-list, and test it to make sure it works properly.
   
3. Create a function prime_factors that takes a single argument N, and returns a list of all prime factors of N. The result doesn't have to be in any particular order. Add this function to your module's export-list.
   
4. Create a function is_square_multiple that takes a single argument N, and returns true if the argument is a multiple of some square, or false if it is not.
   
   • Hint 1: A number is a multiple of a square if it has any prime-factors that appear more than once.
   • Hint 2: You might find some of the functions in the lists and/or sets modules to be of use! The online erlang documentation is available here. For example, you might sort the list of prime-factors, then search the sorted list for the same prime-factor appearing twice in sequence.
5. Finally, create a function find_square_multiples(Count, MaxN). This function takes a count of how many square-multiples in a row there should be, and also a maximum value of where to stop searching.
   
   • If the function finds a series of Count square-multiples in the range [2, MaxN], it should return the first number in the run.
   • If the function doesn't find any series of Count square-multiples in this range, it should return the atom fail.
   So, for example, you might have this interaction:
   

   1> c(mobius.erl).
       {ok,mobius}
       2> mobius:find_square_multiples(3, 50).
       48
       3> mobius:find_square_multiples(3, 20).
       fail
       4>

   Note that the start of the run must be no larger than MaxN; the entire run itself may extend beyond MaxN.
   This function should also be exported by your mobius module.
   
6. Once you have finished this function, find the first square-multiple runs of length 4, length 5, and length 6. You will need to choose a MaxN of 30000. Your program should definitely complete in under 1 minute; if it takes longer then you may have non-tail-recursive code in your implementation, and you need to fix this. (In fact, a good implementation shouldn't take very long to find the answers, but you will have up to a minute to compute the answer.)
   
   

What to submit?

Upon submitting your work, prepare a print-out source codes written in Erlang with test cases at the end of each problem.  It should be in a short bond paper, using a courier new font, with 10 points in size.  Duplicated work will be marked as 0.

NO LATE SUBMISSION WILL BE ACCEPTED.

Class Syllabus

Download Class Syllabus

• CSc 102 Syllabus

Erlang Cheat Sheet

Download the Erlang Cheat Sheet, print it, and always bring it on class.

• Erlang Cheat Sheet

Reading Assignment

Please read Chapters 1 and 2 of the Erlang Progrmaming E-book.

On Functional Programming

The objective of this course is to introduce the theory and practice of functional programming (FP). The characteristic feature of FP is the emphasis on computing by calculation. The traditional distinction between program and data characteristic of imperative programming (IP) is replaced by an emphasis on classifying expressions by types (see Erlang Data Types) that specify their behavior. Execution of imperative programs is generalized to evaluation of well-typed expressions by a smooth extension of mathematical experience to programming practice.


The advantages of FP are significant:

• Verification: There is a close correspondence between the reasoning that justifies the correctness of a program and the program itself. Principles of proof by induction go hand-in-hand with the programming technique of recursion.
• Parallelism: Evaluation of compound expressions is naturally parallel in that the values of sub-expressions may be determined simultaneously without fear of interference or conflict among them. This gives rise to the central concepts of the work (sequential) and span (idealized parallel) complexity of a program, and allows programs to exploit available parallelism without fear of disrupting their correctness.
• Abstraction: FP stresses data-centric computation, with operations that act on compound data structures as whole, rather than via item-by-item processing. More generally, FP emphasizes the isolation of abstract types that clearly separate implementation from interface. Types are used to express and enforce abstraction boundaries, greatly enhancing maintainability of programs, and facilitating team development.

Moreover, FP generalizes IP by treating commands as forms of data that may be executed for their effects on the environment in which they occur.


Source: http://www.cs.cmu.edu/~15150/

Class Materials

Development Tools

For Windows

• Erlang Runtime Environment
• Notepad++ Editor

How to enable Erlang syntax-highlighting in Notepad++? (Windows Only)

1. Install Notepad++ if you have not done so.
2. Download the Erlang language definition file, userDefineLang.xml (Right-click, Save link as...).
3. Click Start, then Run (or go to the Search box in Vista or Win7), then type, %appdata% and then press ENTER.
4. Place userDefineLang.xml inside the Notepad++ folder (listed when you did Step 3) and then restart Notepad++.

After doing this, your Notepad++ should be able to do syntax-highlighting in your Erlang source code once you save it with a .erl extension.

For Linux Users: Download and install the Erlang runtime environment via your distro's package manager. Or better yet, install it from source. 

Here's how:

1. Download the latest source tarball (http://www.erlang.org/download/otp_src_R14B03.tar.gz)
2. Copy your source tarball into your /usr/local/src folder (you must be root to write into this folder).
3. Uncompress it by tar xvzf otp_src_R14B03.tar.gz
4. Then cd otp_src_R14B03
5. Issue the command, ./configure
6. Then,  make
7. And finally, make install

To start the Erlang runtime environment, issue the following command (as non-root) at the command prompt,

$ erl 

You can use gEdit as your source code editor. 

Textbook / References:

• Erlang Programming
• Erlang User's Manual

Online Tutorial:

• Erlang: Give it a try!

Erlang Users/Apps:

•  Who uses Erlang for research and teaching?
•  Who uses Erlang for product development?

Announcement: Class Facebook

I would like to inform everybody that the class has a Facebook account. We could use Facebook to raise questions and other matter regarding about the course. Please add if you are interested.

Click HERE to visit the group.

Class Schedule

CSC 102 IS21
03:00AM-05:00AM, Saturday
SCS-LR2

Class Calendar