ANUC 1100 – Introduction to Programming and Algorithms Semester 1, 2019
Assignment 2
Question 1 Prime Number List (50%)
A prime number is an integer number greater than 1 whose only factors are 1 and itself. Your task is to find out all prime numbers between 1 and 100,000. And save all those prime numbers in a list using the name myPlist. So myPlist should have type definition “myPlist :: [Int]”
Your myPlist must be generated through calculation/checking. Not by pre-calculated list assignment like:
myPlist = [2,3,5,7,11,13,17 …]
You need to think ways to make your list generation process as fast as possible. The execution time will be evaluated by calling the length function (screenshot below, which suggesting there are 9592 prime numbers in the list and takes 0.88 seconds)
Please note:
1. The numbers in myPlist will be checked. If the list of numbers in myPlist are wrong or the execution time is more than 10 minutes, you will not receive any grades for this question.
2. In GHCI, you can type in “:set +s” in the prompt, and then you can see the execution time of anything you run.
3. The faster your program runs, the higher the mark your will get for this question. I will use a computer with i7-7700 CPU @3.60GHz to run your code.
4. The student with least time spending for list generation will get full mark. Other student’s mark will be based on respective execution time according to that benchmark. But if your code execution time is within 1 second, full mark is guaranteed.
5. You may notice that if you call “length myPlist” for the second time, Haskell will give you the answer instantly. Simply because myPlist has been evaluated previously. So you will need to reload your code into Haskell GHCI right before you’d like to check the actual running time of “length myPlist”.
6. You cannot rely on any pre-defined Haskell modules or packages.
7. Your code will be assessed by correctness and the actual running time only. So no need to
worry about comment, layout, easy-to-read, etc. But to receive any marks in question 1, the correctness of your code and answer are necessary.
Question 2 Complexity (30%)
i) (5%) What is the big O notation for F(n). You need to show the steps F(n) = n log(n!) = O(?)
ii) (25%) Consider the following functions and loops. Give their running time in big-Oh. Briefly justify your answer.
The for-loop syntax is for (initialization; condition; increment/decrement) If you are unsure, refer to https://en.wikipedia.org/wiki/For_loop
int algorithm1(int n) {
int sum = 0;
for (int i=0; i < n*n; i = i + 1)
for (int j=1; j < n; j = j + 1) sum=sum + 1;
return sum; }
int algorithm2(int n) {
int sum = 0;
for (int i=0; i < n/2; i = i + 1)
sum=sum+1; return sum;
}
int algorithm3(int n) {
int sum = 0;
for (int i=n; i > 2; i = i – 2)
sum = sum + algorithm2(i); return sum;
}
int algorithm4(int n) {
int sum=0;
for (int i=n; i > 2; i = i/2)
sum = sum + algorithm1(n); return sum;
}
(a)
int sum = algorithm1(n) / n;
(b)
int sum = algorithm2(n) + 1;
(c)
int sum =0;
for (int i=1, i< n; i = i*2)
sum = sum + algorithm3(i);
(d)
int sum =0;
for (int i=0; i < 30; i = i+1)
for(int j=0; j < i; j = j+1) for(int s=0; s < j; s = s+1)
for(int t=0; t < n; t = t+1) sum=sum+1;
(e) algorithm4(n*n);
Question 3 Tree (20%)
i) (8%) Show that in a binary tree of N nodes, there are N + 1 NULL links. A brief proof or reasoning
required.
ii) (6%) Show the result of inserting 2, 1, 4, 5, 9, 3, 6, 7 into an initially empty binary search tree. (Just need to draw out the result tree)
iii) (6%) Show the result of deleting 2 from binary search tree you get from (ii). (Just need to draw out the result tree)
This assignment contains 3 questions in total. You need to submit 2 files: one .hs file contains the code to Question 1. And one .pdf file contains your solutions to question 2 and question 3. You can zip all files into a single archive Assignment_2_
Same as assignment 1, you will need to present your assignment 2 solutions in one of the lab sessions (4th June, 2019) to show that it is your own work. Unless medical certificate or other supporting documents provided, students who fail to attend that lab session will lose 20% of assignment 2 grades.