COMP1100/1130 [2020 S1]:
PROGRAMMING AS PROBLEM SOLVING Research School of Computer Science
Menu
menu
» Labs » Week 12: Exam Prep
In this lab we recap the course, and provide lots of exercises for you to work on with
your peers to help prepare for the Qnal exam.
Table of Contents
Pre-Lab Checklist Intro
Warm-Up Warm-Up (maths) Recursion
Lists
Code Analysis Types
Higher Order
Trees
Advanced Exercises
Pre-Lab Checklist
You have made a solid attempt at all other labs in this course.
You should have read back through the other labs, and have any problems that you struggled with or questions that you have at the ready.
Getting Started
1. Go to the project’s dashboard under the Project tab and click on the Fork button. The gitlab url for this lab is https://gitlab.cecs.anu.edu.au/comp1100/2020s1studentQles/lab12
2. You will be asked where to fork the repository. Click on the user or group to where you’d like to add the forked project. You should see your own name here. Once you have successfully forked a project, you will be redirected to a new webpage where you will notice your name before > project-name. This means you are now the owner of this repository. The url in your browser should re_ect the change: https://gitlab.cecs.anu.edu.au/uXXXXXXX/lab12
3. Finally, clone your forked repository to your computer according to the instructions in the Week 2 Lab.
4. There will be a collection of exercises, sorted into Qles based on different topics covered in this course. Spend your time on the topics you have most dibculty with.
The Last Lab
Congratulations on making it this far! We hope you’ve picked up a lot during this course. This lab will not cover any new content, but will provide you with an opportunity to work on some more exercises, and prep for the exam.
There are too many exercises in this lab for you to do all of them. Concentrate on the exercises that are related to the material that you think you need the most practice with.
You could Qnd other people in your lab who wish to work on the same problems as you, and work together. We highly encourage the use of writing code together on whiteboards in this lab, rather than at a computer by yourself.
You may also wish to spend this time revisiting a previous lab that you struggled with if you prefer.
Warm-Up
Put your work in Warmup.hs
For some of these functions, the types are not provided. You’ll have to work them out
yourself.
bigThree: Takes three arguments, and returns the biggest.
middle: Take as input a tuple of three elements, and returns the middle element. isVowel : Takes in a character, and checks if the character is a vowel. A vowel is one of the following letters: a,e,i,o,u.
xor : Takes two booleans, and returns true if one and only one of the inputs was True. Try to deQne it in a single line without guards.
threeDiff : Returns true if all three inputs are different.
Warm-Up (for those that like math)
Put your work in Warmup.hs
discriminate : Takes in three arguments, a,b,c and returns the discriminate D of thequadraticequationax2 +bx+c=0,deQnedasD=b2 −4ac
rootsQuad : Takes in three arguments a,b,c and will return any real roots of the equation ax2 + bx + c = 0. You must not throw an error if only one or zero real roots exist. It should be possible to use your function to Qgure out how many roots there are, and then also obtain those root(s) (if they exist.) As a reminder,
the quadratic formula is −b±√b2−4ac You may assume that this is a non- 2a
degenerate quadratic (that is, that a ≠ 0.) (Hint: Consider using discriminate to Qgure out how many real roots there are.)
Recursion
Put your work in Recursion.hs Tribonacci
Write a⎧⎪function that computes the tribonacci sequence Tn, deQned as 0 n=0
T n = ⎨⎪⎩⎪ 0 n = 1 1 n=2
Tn−1 +Tn−2 +Tn−3 n≥3
Check that the Qrst few terms are 0,0,1,1,2,4,7,13,24,44,81,…
Your solution should be ebcient, and you should have no trouble computing T100 in under a second.
Chessboard
chessboard : Write a function that takes in a tuple (n,m), and returns a list of all cells from (1,1) to (n,m). The order is not critical.
Square Roots by Bisection
There are many ways to compute square roots, and here we investigate the method of bisection. Given a number n, it’s obvious that that 0 ≤ √n ≤ n. As an initial guess, we suppose that the square root of n is n/2. We square the result, and if it’s too big, then we know that the square root lies in the interval [0, n/2]. Otherwise, it lies in the interval [n/2, n]. We take the mid-point of our interval as our next guess, and repeat.
For example, to compute √2. Our initial interval is [0, 2].
Weguess√2≈1,but12 =1<2,soweguessedtoolow. New interval is [1, 2].
Guess √2 ≈ 1.5, but 1.52 = 2.25 > 2, so we guessed too high. New interval is [1, 1.5].
Guess √2 ≈ 1.25, etc.
Using this algorithm, try to write a function that computes the square roots of functions in this manner. Terminate when the interval is subciently small, and we have computed √n to subciently high precision.
Lists
Put your work in Lists.hs
You may use higher order functions like map,foldr,filter,zipWith, but do not use predeQned functions if it makes the question trivial to solve (implementing a sort using sort, for instance).
isSorted : Checks if a list is sorted from smallest to biggest.
insertSorted : Assuming that the input list is sorted, takes an element and inserts it into the list in the correct place, so that the list is still sorted. removeDup : Takes a list, and deletes any elements that have already appeared in the list so far.
(Don’t use nub to help you.)
continuous : Takes a list of integers, and checks that each element in the list is at
most one away from the previous element
rotate : Takes a list of a, and an Int, and rotates the elements of the list around by the number indicated.
insertAt : Takes a list of a, an element of type a, an index Int, and inserts that element into the list at that element.
runLengthEncoding : Takes a list, and returns a list of tuples, counting how many times that element was duplicated consecutively.
runLengthDecoding : Take the output from runLengthEncoding, and reconstruct the original string.
transpose : Take a list of lists of a as input, and transpose it (swap rows with columns).
Types
Put your work in Types.hs Sum
I’ve deQned a new data type to try and emulate the sum of two sets you’ve see in lectures before.
b’
Note that this lab does not require a submission via git. The participation marks for this lab are earned by your tutor observing you working on lab exercises. What this lab isn’t is a place for you to work on your assignment. These are to be done in your own time, as your tutors usually cannot help you with your assignment code anyway.
>chessboard (2,3) [(1,1),(2,1),(1,2),(2,2),(1,3),(2,3)]
>removeDup [2,5,2,4,4,1,7,8,2,4,6,3] [2,5,4,1,7,8,6,3]
> continuous [1,2,3,3,2,3,4,3,2]
True
> continuous [3,4,3,5,4] — jumps from 3 to 5 False
>rotate [1,2,3,4] 1 [2,3,4,1]
>rotate [5,6,7,8,9,10] 3 [8,9,10,5,6,7]
>rotate “abcdefg” (-2) “fgabcde”
>insertAt “abcdef” ‘$’ 0 “$abcdef”
>insertAt “abcdef” ‘$’ 3 “abc$def”
>insertAt “abcdef” ‘$’ (-1) “abcdef$”
>insertAt “abcdef” ‘$’ (-2) “abcde$f”
>runLengthEncoding “aaabbccccddcccaaaab” [(‘a’,3),(‘b’,2),(‘c’,4),(‘d’,2),(‘c’,3),(‘a’,4),(‘b’,1)] >runLengthEncoding [2,2,1,4,4,2,3,2,2,3] [(2,2),(1,1),(4,2),(2,1),(3,1),(2,2),(3,1)]
>runLengthEncoding [(‘a’,3),(‘b’,2),(‘c’,4),(‘d’,2),(‘c’,3),(‘a’,4),(‘ “aaabbccccddcccaaaab”
>runLengthEncoding [(2,2),(1,1),(4,2),(2,1),(3,1),(2,2),(3,1)] [2,2,1,4,4,2,3,2,2,3]
>transpose [[1,2,3],[4,5,6],[7,8,9]] [[1,4,7],[2,5,8],[3,6,9]]
data Sum a b = Left a | Right b deriving Show
This data types takes two type variables a and b, and can be either Left a or Right b. Work out the types of the following functions, and then implement them.
sumApply: Takes two functions, the Qrst can take type a as input, and the second can take type b as input. Also takes an element of the sum of a and b as input. If the input was of the form Left a, extract the variable of type a and apple the Qrst function. Else, apply the second function to the argument in Right b.
(Hint: What must the output types of both functions be?)
fromLeft : Takes an element of a sum, and extracts the a from Left a. If the input was Right b, throw an error.
fromRight : Same as above, but return the second.
lefts : Takes a list of elements of a sum, and returns a list containing only the left elements. rights : Same as lefts, but returns only the right elements.
sumMap : Takes a list of elements of a sum, and two functions, and maps the appropriate function onto each element. (Hint: This function should be easy once you’ve written sumApply)
sumExtract : Takes a list of elements of a sum, and returns a tuple of two lists as shown.
What could be some useful applications of this new datatype?
Higher Order
Put your work in HigherOrder.hs Using Higher Order functions
Implement the following functions using higher order functions. Your solutions should be very succinct, and should not use recursion (other than the recursion provided by a higher order function).
The below functions all take a list of numbers as their input; for our deQnitions we will refer to this list as x1, x2, … , xn.
arithMean : Computes the average of a list of numbers. x1+x2+…+xn n
geoMean : Computes the geometric mean of a list of numbers.√n x1x2 … xn
l1Norm : Takes a list of numbers, and computes the sum of the absolute values of each
term. |x1| + |x2| + … + |xn|
l2Norm : Takes a list of numbers, and computes the Eucledian norm, deQned to be the
square root of the sum of the squares of each element. √x21 + x2 + … + x2n cesaroSum : Given a list x1, x2, … , xn, computes the Ces\’aro summation, given by
returning a new list a1, a2, … an, where ak = k1 ∑ki=1 xi That is, ak is the average of the Qrst k terms of the input list.
DeQning higher order functions
revMap : Takes an element, and feeds that element to each function in a list
superMap : Takes a list of elements, and a list of functions, and applies each element to each function. Your output should be a list of lists.
Trees
Put your work in Trees.hs
If you haven’t completed Lab 09 or Lab 10, then you should go do that Qrst, before doing
these exercises.
Recall the deQnition of a binary search tree.
data BSTree a = Null | Node (BSTree a) a (BSTree a)
Recall that a binary tree satisQes the binary search ordering constraint, if either:
It is a Null tree
Every element in the left hand subtree is strictly less than the root, and every element in the right hand subtree is strictly more than the root. Furthermore, both subtrees also satisfy the binary search ordering constraint.
You may Qnd your functions you wrote in labs 9 and 10 helpful here. What does the following function do?
Family Trees
We’d like to encode a family tree as a binary tree, with a person at the top root node, and their father on the left sub tree, and their mother on the right subtree. We repeat this process all the way up, fathers on left, mothers on right.
We also create a new data type to encode the ancestor of a person:
So a person is either Me (the person at the top of the family tree), or that person’s ancestor.
I’ve included my family tree (or, at least as much of it that I could Qnd out) and the family tree of Prince George, the youngest Qrst born child of the British royal family. (You’ll note that royal family trees usually only bother to keep track of the royal bloodline, those with a direct lineage to William I, the “Qrst” king of England. Our data structure is actually insubcient for messy family trees like this one, but it will subce.)
Your goal is to write some functions that operate on family trees.
ancestors :: Person -> FamilyTree -> [Name]
Given a family tree and the description of an ancestor (e.g. grand mother) return all of
those ancestors.
kindAncestor :: FamilyTree -> Name -> Maybe Person
Given a family tree and a name, return what kind of ancestor they are, if they can be
found.
The second test veriQes that one of George’s great grandmothers (on his father’s father’s side) is the current British monarch, Queen Elizabeth II.
Advanced Exercises
Put your work in Advanced.hs Polynomial Evaluation
polyEval : Takes a list of doubles representing coebcients of a polynomial sorted from lowest to highest degree, and a double x. Evaluates the polynomial at that point x. The result should be that
polyEval [a0, a1, a2, …, an] x = a0 + a1*x + a2*x^2 + … an*x^n
hornerEval : Same as polyEval, but use the following identity (called Horner’s Rule) to evaluate the result ebciently):
a0 +a1x+a2x2 +a3x3 =a0 +x(a1 +x(a2 +a3x)).Thisidentitygeneralisesto a polynomial of any degree.
Primes
isPrime : Takes in an integer, and checks if it is prime. As a reminder, a prime number is a positive number that has two unique divisors, itself and one. The Qrst few primes are: 2,3,5,7,11,13,17,19,23…
How can this function be written ebciently?
factor : Takes in an integer, and returns a list of its prime factors (counting primes more than once if necessary).
Travelling Salesman Problem
Given a collection of cities in a country, a travelling salesman would like to visit all the cities, and get back to the start, while travelling the least total distance (as the cost of fuel eats into his budget).
Each city is represented by a point on a 2d grid describing where the city is.
Given three cities at (0,0), (1,0), (0,1), they form a triangle, and it’s obvious that the best solution is to start at one city, visit the second, visit the third, and then go back to the Qrst city. But for many cities, there might be many possibly routes to take, and some will be quicker than others.
We measure the cost to travel between two cities via Eucledian straight-line distance. So the cost to travel from city (0,0) to city (1,1) is √12 + 12 = √2.
travellingSalesman : Takes in a list of cities, represented by tuples (Double,Double), and returns the coordinates rearranged in the order the travelling salesman should visit them to minimise travel cost.
You may Qnd it useful to write the following helper functions.
cost :: [City] -> Distance
cost returns the total distance travelled along a particular route.
distance :: City -> City -> Distance distance returns the distance betwen two cities
>sumApply length (*2) (Left “hello”) 5
>sumApply length (*2) (Right 10)
20
>fromLeft (Left “hello”) “hello”
>fromLeft (Right 9)
— an error is thrown
>fromRight (Left “hello”) — an error is thrown >fromRight (Right 9)
9
> lefts [Left “hello”, Right 5, Left “world”, Right 10] [“hello”, “world”]
> rights [Left “hello”, Right 5, Left “world”, Right 10] [5, 10]
>sumMap length (*2) [Left “yes”, Right 7, Left “no”, Right 9] [3,14,2,18]
>sumExtract [Left “yes”, Right 7, Left “no”, Right 9] ([“yes”, “no”],[7,9])
> revMap 3 [(+1), (*2), (^2)] [4,6,9]
> revMap 5 [(>3), (==4), (==5)] [True, False, True]
> superMap [3,5] [(+1), (*7), (^2)] [[4,21,9],[6,35,25]]
treeMystery :: BTree a -> BTree a treeMystery tree = case tree of
Null -> Null
Node left x right -> Node (treeMystery right) x (treeMystery left)
data Person = Me | My Ancestor
data Ancestor = Father | Mother | Grand Ancestor type FamilyTree = BinaryTree Name
type Name = String
> ancestors Me david
[“David Quarel”]
> ancestors (My Mother) david
[“Helen Corcoran”]
> ancestors (My (Grand Father)) david
[“Luigi Quarel”, “Mark Corcoran”]
> ancestors (My (Grand (Grand Mother))) david
[“Rosa Randazzo”,”Assunta Karsun”,”Mary O’Sullivan”,”Charlotte Ohlin”]
> kindAncestor david “David Quarel” Just Me
> kindAncestor david “Helen Corcoran” Just (My Mother)
> kindAncestor david “Luigi Quarel” Just (My (Grand Father))
> kindAncestor david “Alan Turing” Nothing
> kindAncestor george “Elizabeth II” Just (My (Grand (Grand Mother)))
>factor 60
[2,2,3,5]
>factor 1050
[2,3,5,5,7]
>factor 391
[17,23]
>factor 83
[83]
type City = (Double, Double) type Route = [City]
> cost [(0,0),(1,1),(2,1)] 2.414213562373095
> distance (0,0) (1,1) 1.4142135623730951
> travellingSalesman [(0,0),(2,3),(1,4),(2,2),(1,5),(1,3),(3,3),(2,4)] [(0.0,0.0),(1.0,3.0),(1.0,4.0),(1.0,5.0),(2.0,4.0),(2.0,3.0),(3.0,3.0),(2.0,
Your answer may vary from the above, depending on which city you start and end at. But the total distance over the route should be the same as mine.
> cost (travellingSalesman [(0,0),(2,3),(1,4),(2,2),(1,5),(1,3),(3,3),(2,4) 12.81913190966076
])
If you’re taking or have taken MATH1005, you might recognise this problem as a special case of Qnding a Hamilton circuit for a graph.
Updated: 06 Jun 2020
Responsible Obcer: Director, RSCS
Page Contact:
Course Convenor
Contact ANU
Copyright
Disclaimer
Privacy
Freedom of Information
+61 2 6125 5111
The Australian National University, Canberra CRICOS Provider : 00120C ABN : 52 234 063 906