HOME COMP 3007
代写Network | racket | network代做 | 代做scheme | 作业assignment | database作业 – 本题是一个利用scheme进行练习的代做, 对scheme的流程进行训练解析, 是比较有代表性的Network/racket/network/scheme/database等代写方向, 该题目是值得借鉴的assignment代写的题目
COMP 3007 – TCOMP 3007 – Take-homeake-home
FinalFinal
Take-home Exam RulesTake-home Exam Rules
Ensure that you have read and understood all of the instructions before you begin.
About Grading...
Submissions will be evaluated by a combination of automatic and manual grading.
Your answers to each coding problem must work as described by each question for all
reasonable inputs within the given constraints of each problem.
There will be no part marks awarded to incomplete, incorrect, or partially correct solutions.
(Test your solutions!)
There are no marks explicitly for documentation and testing, but documenting and testing your
work is strongly encouraged.
Programming guidelines...
Ensure that you follow all prescribed file and function naming conventions.
Unless otherwise specified, you may assume inputs supplied are of the correct type.
Solutions must be coded in scheme or Prolog (as specified), no other programming languages
will be graded.
About built-ins and libraries...
You may use any built-in functions/operations/predicates you like, provided that they are not
COMP 3007
Outline
Lectures
Assignments
Final Exam
Schedule
explicitly forbidden by a problem.
You may not use use any unauthorized imports in your solutions (core language features only).
About collaboration...
Absolutely no collaboration is allowed in the completion of this exam.
Any collaboration, sharing, or copying of solutions (whole or partial) from peers or the
internet, will result in (at minimum) a grade of zero on the test, and a citation for academic
misconduct.
If you use concepts from outside of the course in your solutions, you should cite your source.
Code copied from authorized sources (e.g. lecture notes) should be cited (e.g. "From course
lecture notes, chapter 2").
Do not post questions or answers from this test to any public forum, even after you have
finished.
Part APart A
[42 marks total]
The Rules:
You may solve the questions of this Part using Scheme or Prolog (or both!).
Put all Scheme solutions in a file called parta_<yourid#>.scm.
Put all Prolog solutions in a file called parta_<yourid#>.pl.
Each question is denoted with a number of marks.
Correctly working answers will receive full marks.
Incorrect answers will receive zero marks.
Solve as many or as few as you'd like to fulfill the maximum grade above.
Correctly solving every question once will yeild full marks for this Part.
Solving a question in both languages is worth 1.5x the stated marks (total, not each).
If you earn more than the maximum grade for this Part, you will receive the maximum grade.
Tip: Be sure to read the usage examples for both languages (even if you're solving in just one).
The Questions:
1. [5 marks] Write a function/predicate called split that takes a key and a list as arguments and splits
the input list into a list of sublists between each instance of key.
E.g., (split 'c '(a b c d e)) ((a b)(d e))
E.g., (split '0 '(1 0 1 1 0 2 0 0 1)) ((1)(1 1)(2)(1))
E.g., ?-split(x,[1,2,x,4,5],R). R = [[1,2],[4,5]].
2. [4 marks] Write a function/predicate called slice that takes a list and two integer indices as
arguments and returns a sublist of the input list between the indices start (inclusive) and end
(exclusive). If either of the given indices are out of bounds, then the returned sublist should include
any existing values in the given ranges.
E.g., (slice '(0 1 2 3 4 5 6 7 8 9) 3 8) (3 4 5 6 7)
E.g., (slice '(a b c d e f g h i j) 5 25) (f g h i j)
E.g., ?-slice([a,b,c,d,e,f,g],1,3,R). R = [b,c].
E.g., ?-slice([0,1,2,3,4,5],-10,3,R). R = [0,1,2].
3. [5 marks] Write a function/predicate called infuse that takes the following as arguments: an input
list, an integer index, an integer n, and a list of new items. The infuse function should remove n
items from the input list at the given index, and insert all of the new items at that location.
Note: the number of elements removed should be at most the provided number, if fewer target items
are available then fewer will be removed.
Note: Invalid indices should result in the input list being unaltered.
E.g., (infuse '(a b c d e) 2 1 '(x y)) (a b x y d e)
E.g., (infuse '(1 2 3 4 5) 2 0 '(x y)) (1 2 x y 3 4 5)
E.g., (infuse '(a b c d e) 2 1 '()) (a b d e)
E.g., ?-infuse([1,2,3],1,1,[a,b,c],R). R = [1,a,b,c,3].
E.g., ?-infuse([1,2,3],3,1,[a,b],R). R = [1,2,3].
E.g., ?-infuse([0,1,2,3,4,5,6,7],4,2,[],R). R = [0,1,2,3,6,7].
4. [5 marks] Write a function/predicate called fold_once that takes a list of numbers as argument and
returns a list of the following sums: first_element + last_element, second_element +
second_last_element, etc...
If there is a singular middle element, do not add anything to it.
E.g., (fold_once '(6 2.5 9 1 5 7 8 4)) (10 10.5 16 6)
E.g., ?-fold_once([1,2,3.5,4,5],R). R = [6,6,3.5]
5. [3 marks] Write a function/predicate called pos_diffs that takes a list of zero or more numbers as
argument and returns the list of the differences between each successive element in the list, but
without any of the negative differences.
E.g., (pos_diffs '(6 2 9 1 5 7 8)) (-4 7 -8 4 2 1) (7 4 2 1)
E.g., (pos_diffs '(1)) ()
E.g., ?-pos_diffs([1,2,3,4,4,6],R). R = [1,1,1,0,2].
6. [4 marks] Write a function/predicate called globs that takes a list of symbols(/atoms) as argument
and returns a list where sequences of consecutive values from the input list are stored as a pair (2-
element list) of the value and the count of that value.
E.g., (globs '(a a g g a a a a t c)) ((a 2) (g 2) (a 4) (t 1) (c 1))
E.g., globs([t,t,t,a,a,c,g,t],R). R = [[t,3],[a,2],[c,1],[g,1],[t,1]].
7. [6 marks] Write a function/predicate called all_sums that takes two non-negative integers k and n as
arguments, and returns a list of all k-digit integers whose digits sum to n, in ascending order. Note:
leading zeroes should not be considered digits for this problem.
E.g., (all_sums 2 7) (16 25 34 43 52 61 70)
E.g., (all_sums 3 0) ()
E.g., ?-all_sums(3,4,R). R = [103,112,121,130,202,211,220,301,310,400]
8. [5 marks] Write a function/predicate called prune that takes a tree (nested list) as argument and
removes all empty lists from inside the provided tree. The resulting tree should contain all non-
empty-list elements from the input tree in their original order and structure.
E.g., (prune '(1 2 () 3 4)) (1 2 3 4)
E.g., (prune '(a (b () (c () d))()()(()) e)) (a (b (c d)) e)
E.g., (prune '()) ()
E.g., ?-prune([1,2,[],3,4],R). R = [1,2,3,4].
E.g., ?-prune([[],[],[[],1,[[]]]],R). R = [[1]].
9. [5 marks] Write a function/predicate called minima that takes a list of numbers as argument and
returns a list of the indices of all local minima in the list. For the sake of this problem, a local minima
is defined as any element which is smaller than both of its immediately neighbouring elements. Any
indices outside of the input list should be considered to have a value of 0.
E.g., (minima '(1 5 9 3 5 4 8)) (3 5)
E.g., (minima '(-42 25 -1)) (0 2)
E
E.g., ?-minima([0,1,0,0,0,-1,1,1,-1,1,0,1],R). R = [5,8,10].
E.g., ?-minima([6,4,2,1,3,5],R). R = [3].
Part BPart B
Answer all problems from this part in their own (specified) files.
1. [6 marks] In a file called partb1_generator.scm, write a Scheme function called list-generator
that takes two functions (a predicate and a mutator) as argument and returns a list-making function.
The returned list-making function should take three integers (a start value, a stop value, and a step
value) as arguments, and return a list of values based on all of the provided information. The
resulting lists should contain the result of applying the mutator function to all of the integers in the
given range for which the predicate function returns true.
E.g., (define f (list-generator (lambda(x)#t) (lambda(x)x)))
f #<procedure:...>
(f 0 10 2) (0 2 4 6 8 10)
E.g., ((list-generator odd? (lambda(x)(* x 2))) 1 20 3) (2 14 26 38)
E.g., ((list-generator (lambda(x)#t)(lambda(x)x)) 16 0 -4) (16 12 8 4 0)
2. [7 marks] In a file called partb2_contour.scm, write a program that will execute to create the
environment state depicted in the following contour diagram.
Note: there are many possible solutions to this problem, you need only find one.
Note: any lines of code not described by the diagram may be filled as you see fit (i.e., lines of code,
comments, or whitespace can be used to align your solution with the provided line numbers)
Part CPart C
[30 marks total] Solve any 2 of the following 3 problems. If you solve all three, only your best two will be counted towards your grade. Be sure to follow all provided file and function names.
1. Create a file called partc1_infix.scm and place your answers to the following questions in this file.
i. [4 marks] Create a function called eval-prefix that takes a prefix expression tree as argument
with the following form:
tree n mber
tree := number
tree := (operator tree tree)
The function should return the evaluated value of the given prefix expression tree. Your
solution should traverse the given expression and should not call the built-in eval or apply
functions. You may assume that the only operations are: +, -, *, /.
E.g., (eval-prefix '(+ (+ 1 2) 3)) 6
E.g., (eval-prefix '(* (+ 1 2) (* 1 (+ 1 (- 4 2))))) 9
ii. [11 marks] Create a function called parse-infix that takes an infix expression tree as
argument and returns an equivalent prefix expression tree. Infix expression trees will have the
following form:
infix := number
infix := (infix operator infix)
infix := (infix operator infix operator infix)
infix := (infix operator infix operator infix ...)
Operators may be one of the set: {+, -, *, /}. Standard precedence and associativity rules
should be followed.
E.g., (parse-infix '(10 - 5)) (- 10 5)
E.g., (parse-infix '(1 + 2 - 3)) (- (+ 1 2) 3)
E.g., (parse-infix '(1 + 2 * 3 - 4)) (- (+ 1 (* 2 3)) 4)
E.g., (parse-infix '(1 + (2 + 2) * 3)) (+ 1 (* (+ 2 2) 3))
2. Download and extend the following file with your solutions to the problems below:
partc2_mci_letstarpartc2_mci_letstar.scm.scm. (Note: do not rename the file). Be sure to clearly label the changes you make
using a short listing of line numbers at the top of your file.
i. [5 marks] Extend the provided MCI implementation so that it can properly evaluate let
expressions. This means extending the eval function, and building the relevant abstraction
barrier(s).
Hint: a let can be expressed as a lambda, and the MCI can already evaluate lambda
expressions.
An example let expression is: (let ((a 1)(b 2))(+ a b))
ii. [10 marks] Extend the provided MCI implementation further so that it can properly evaluate
let* expressions. This means further extending the eval function, and the relevant abstraction
barrier(s).
Hint: a let* can be expressed as a nested sequence of let expressions.
An example let* expression is: (let* ((a 2)(b (+ a 1))) (* a b))
3. Download and extend the following file with your solutions to the problems below:
partc3_transportation.plpartc3_transportation.pl. (Note: do not rename the file).
The installation of Stations for the new Hyperspeed Vacuum-tube Transportation System was
(regrettably) decided in the fairest way possible, by random draw. The provided knowledgebase
represents the listing of all of the directed edges in our transportation network, in the following
format:
edge(SourceCity, DestinationCity, DistanceInKm). % indicates a directed edge exists
starting in sourceCity and ending DistanceInKm kilometers away at DestinationCity.
Help our commuters get to where they're going by solving the following problems.
i. [3 marks] Firstly, our commuters are reporting difficulty interpreting the provided
knowledgebase. Please help our commuters find out if they can get where they're going by
creating a Prolog predicate connected(A,B) that succeeds if there is a path of 1 or more edges
from city A to city B.
E.g., ?- connected(ottawa,gatineau). True.
E.g., ?- connected(ottawa,toronto). False.
ii. [4 marks] Next, to reduce the disorienting effects of the hypersonic ping-ponging pathways of
our travel network, we would like to provide our commuters with a simple listing of the
stopovers that they will experience along their journey. Create a Prolog predicate
commuterPath(A,B,L) that succeeds if L is the list of cities along the path between city A and
city B (if such a path exists).
E.g., ?- commuterPath(ottawa, gatineau, Path). Path = [ottawa, thunderBay,
kelowna, gatineau].
iii. [4 marks] As an extended feature for our "Platinum Membership" commuters, we would like
to offer a complimentary of the distance they will travel. Create a Prolog predicate
pathLength(A,B,Dist) that succeeds if Dist is the total distance (in Km) of an entire path
between city A and city B.
E.g., ?- pathLength(ottawa,gatineau,Len). Len = 6835.209999999999.
iv. [2 marks] Some of our more discerning critics have pointed out that they're uneasy with the
prospect of being hurtled at hypersonic speeds across the country without any way to get back
home. To help calm concern over these "details", please create a Prolog predicate
getCycle(A,C) that succeeds if C is a non-repeating cycle of existing edges which originates
and ends at city A.
E.g., ?- getCycle(ottawa, Cycle). Cycle = [ottawa,edmonton,ottawa] ; False.
v. [2 marks] It turns out that hypersonic travel for a fixed low-low price has attracted a thrill-
seeking element of the population to our business. These pleasuremongers care less about
where they're going, and more about spending as much time as they possibly can travelling
faster than their worldly problems!
To serve this clientele, create a Prolog predicate longestPath(A,L) that succeeds iff L is the
longest path of edges in our transportation network that originates at city A.
E.g., ?- longestPath(ottawa,L). L = [ottawa, thunderBay, kelowna, gatineau,
saskatoon, barrie, oshawa].
Some notes:
Your implementations of these predicates should handle cycles without getting stuck in infinite
loops.
A path refers to a sequence of vertices connected by edges with no duplicates (except possibly
the first and last vertex).
Your predicates should not assume that the facts in the database are unchangeable (ie. do not
hardcode solutions based on the current state of the transport network).
You may construct any additional helper predicates that you require.
It may be helpful to construct smaller sample transportation networks for testing.
SubmissionSubmission
You must use any and all provided file and function names for your submission. Failure to follow
the prescribed naming conventions will result in a grade of zero for the affected question(s).
Combine all files into a single .zip file called <name>_<id#>_comp3007final.zip for your
submission. Submit your assignment using cuLearncuLearn before the due date. NO LATE SUBMISSIONS will be graded. Do not wait until the last minute of the test to submit your answers! You are responsible for submitting all files and ENSURING that the submission is completed successfully. Any code files that are not runnable/loadable (in Dr racket using R5RS or SWI-prolog under default conditions) will result in a mark of 0 for that question. All Scheme code should be written to run in R5RS. (Do not include a #lang line). All Prolog code should be written to run in SWI-Prolog. If you are having issues with submission, contact me before the due date.