This exercise looks at sorting in Prolog.
1. Write Prolog clauses that define the predicate sorted(L), which is true if and only if list L is sorted in ascending order.
2. Write a Prolog definition for the predicate perm(L,M), which is true if and only if L is a permutation of M.
3. Define sort(L,M) (M is a sorted version of L) using perm and sorted.
4. Run sort on longer and longer lists until you lose patience. What is the time complexity of your program?
5. Write a faster sorting algorithm, such as insertion sort or quicksort, in Prolog.
1. Write Prolog clauses that define the predicate sorted(L), which is true if and only if list L is sorted in ascending order.
2. Write a Prolog definition for the predicate perm(L,M), which is true if and only if L is a permutation of M.
3. Define sort(L,M) (M is a sorted version of L) using perm and sorted.
4. Run sort on longer and longer lists until you lose patience. What is the time complexity of your program?
5. Write a faster sorting algorithm, such as insertion sort or quicksort, in Prolog.
This exercise looks at sorting in Prolog.
1. Write Prolog clauses that define the predicate
sorted(L), which is true if and only if list
L is sorted in ascending order.
2. Write a Prolog definition for the predicate perm(L,M),
which is true if and only if L is a permutation of
M.
3. Define sort(L,M) (M is a sorted version of
L) using perm and sorted.
4. Run sort on longer and longer lists until you lose
patience. What is the time complexity of your program?
5. Write a faster sorting algorithm, such as insertion sort or
quicksort, in Prolog.