|
|
I will talk about three distinct sorting algorithms. Perhaps, the easiest to implement is the quicksort.
In short, it sorts the input by positioning the input around the first element(pivot) and recursively sorts thepartitions. Here is the implementation:
?View Code SCHEME1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
;;;;;;QUICKSORT;;;;;;;;
;myquicksort: listOfNumbers->listOfNumbers
; Sorts the input by positioning the input around the first element(pivot) and recursively sorts the [...]
This algorithm finds the roots of a quadratic equation in the form ax^2 + bx + c = 0.It tests for several conditions:
-If a = 0 and b = 0, then the equation reduces to c = 0. If this condition occurs we call the equation degenarete.
-If a = 0 and b ~= 0, the [...]
This algorithm creates a guessing program in MATLAB. First, it randomly picks an integer in range 1 to 10. Then, the user should guess the number as soon as possible. A counter keeps track of number of guesses made.
?View Code MATLAB% This is a guessing game
counter=0;
real_number=rand(1);
real_number=10*real_number;
number=ceil(real_number);
fprintf(’I am thinking a number between 1 and 10.\n’);
guess=input(’Guess a [...]
Craps is a popular dice game. The rules are as follows: A player rolls two dice. Each dice has six faces. These faces contain 1, 2, 3, 4, 5, and 6 spots. After dices have come to rest, the sum the spots on the two upward faces are calculated. If the sum is 7 or [...]
Here we give out a procedure where the tree is rotated to the left so that the root becomes the left-most element and the leaves are moved to the right:
?View Code PROLOG1
2
3
4
5
6
7
8
9
10
show(Tree):-
show2(Tree,0).
show2(nil,_).
show2(t(Left,X,Right),Indent):-
Ind2 is Indent + 2,
show2(Right,Ind2),
tab(Indent),write(X),nl,
show2(Left,Ind2).
A way to represent a tree in Prolog could be:
t(t(nil,1,nil), 2, t(t(nil,3,nil),4,nil))
However, a binary tree is the one that is ordered from left to right accoriding to a relation. The general method for searching in the binary dictionary is:
-if X is the root of D then X has been found, otherwise
-if X is less than [...]
A list can be sorted if there is an ordering relation in between the terms. For example, here is an ordering relation:
gt(X,Y):- X > Y.
or for alphabetical order:
gt(X,Y):- X@>Y.
First we examine bubblesort. To sort a list:
- Find two adjacent elements, X and Y,in list such that gt(X,Y) is satisfied and swap X and Y in [...]
Here is a procedure that counts patterns in a sequence of words:
?View Code SCHEME1
2
3
4
5
6
7
8
9
(define match
(lambda (pattern text)
(helper pattern text 0 pattern)))
(define (helper p t c o-p)
(cond ((null? p) (helper o-p t (+ 1 c) o-p))
((null? t) c)
((eq? (car p) (car t)) (helper (cdr p) (cdr t) c o-p))
(else (helper [...]
A number x is called a fixed point of a function if x satisfies the equation f(x)=x. We can locate a fixed point by beginning with an initial guess and applying f repeatedly,
f(x), f(f(x)), f(f(f(x))),…
Note that we need a tolerance to find two succesive values whose difference is less than it.
?View Code SCHEME1
2
3
4
5
6
7
8
9
10
(define tolerance 0.00001)
(define [...]
Half-interval method is used to find roots of an equation given that points a and b are f(a)<0<f(b). Thus, we assume that we are initially given the funtion together with points at which its values are negative and positive. Here is the algorithm:
?View Code SCHEME(define (half-interval-method f a b)
(let ((a-value (f a))
(b-value (f b)))
(cond [...]
|
|
