Note: you need to be comfortable with lists before you get stuck into some of the algorithms we will be looking at shortly. So it is important to complete these exercises.
Implement the following functions in Haskell
- member - check if a value is in a listor not
- count - count the number of occurrences of a value in a list
- delete - delete a value from a list
- deleteAll - delete all occurrences of a value from a list
- findMin - which finds the minimum value of a list
- implement and test selection sort in Haskell as shown in class. Will need the auxiliary functions findMin and delete.
- try to implement selection sort in C as shown in class. Use the skeleton code provided as a starting point..
4
- Implement insert sort in Haskell, you will need the two functions
isort :: [Int] -> [Int]
insert :: Int -> [Int] -> [Int]
- With the help of pseudocode, implement insert sort in C using the skeleton code as a starting point.
5
Feb 28
rl 100
will generate a random list of size 100. Put the resulting sorting data into a spreadsheet and draw a line chart.
6
Mar 7
Write a polymorphic function duplicate :: [a] -> [a] which duplicates each value in a list. The value in the list are of type a (a is a type variable which could be an Int or Char etc) For example:
duplicate [2, 6, 1] = [2, 2, 6, 6, 1, 1]
duplicate "dog" = "ddoogg"
7
Mar 14
- Complete the sorting assignment and if possible include bubble sort. You are expected to finish assignment today and hand up during class on Tue 22.
- Here is a sample lab test 3 for you to practice on.
8
Mar 21
Pascal's Triangle
Write a function, pascal n, which computes the nth row of the Pascal triangle.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
and so on.
Try an old lab test 3.
9
Mar 28
Start work on eight_puzzle, see week 11 below.
Lab Test 3 on today
11.00 - 12.00 Group A in A116, Group B in A306
12.00 - 1.00 Group C in A116, Group D in A306
Have a look at the eight-puzzle program eight_puzzle.hs. It has some predefined starting states such as s1 and s2; and the goal state goal. In Hugs try:
s1 // show how state s1 is represaented (as a list)
toString s1 // converts state s1 to a string
putStr (toString s1) // displays the string created from state s1
go s1 // solve the puzzle starting with state s1.
Satisfy yourself that you understand or get the gist of the core parts of the Haskell implementation of the Eight Puzzle.
Open the eight-puzzle code and define a new state, s3 say, which represents the following state of the puzzle.
1. Then in Hugs run:
go s2
go s1
s3
toString s3
putStr (toString s3)
showState s3
moves s3
length (moves s3) -- should be 2 as only 2 possible moves
putStr (toStr (moves s3) -- what does this do?
go s3
2. With pen and paper, draw state s1, then work backwards 4 moves from it to get a state 8 moves away from the goal stste. Next using Texpad, represent this state and call it s0. In Hugs try
showState s0
go s0
Does Hugs find a solution path? If so work backwards a few more moves and try out another state.
Easter Break
Easter Break
Review week
Exams
Exams
|
|
(i) |
Write a function addList which computes the sum of all the numbers in a list of numbers. |
|
|
(ii) |
Write a function delete which deletes a given value from a list. You can assume that the list is of type [Int]. |
|
|
(iii) |
Write a function isMemeber which decides if an number is in a list or not. |
|
|
(iv) |
Write a function countMemeber which returns the number of times that a value occurs in a list. |
Finally, implement selection sort in C and from the pseudocode.
As shown in the tutorial, use MS Excel to draw line charts so that the performance differences between fib and efficFib can be clearly seen. The line chart will show the number of reductions versus n (n could vary from 0, 2, 4, 6, 8, .. 20)