Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • 120 views

    Lab 13

    Uploaded by

    Balls Mahoney
    This document provides instructions for Laboratory Assignment 13 in CSE1729 - Introduction to Programming. The objectives are to work with priority queues and mutations in objects. The assignment is due on April 19, 2016 and is worth a maximum of 3 points. Students are asked to construct a priority queue object that maintains a heap, uses a generic order relation, and exposes methods for empty?, insert, extract min, and size. The assignment also involves writing a destructive append function called nconc! and demonstrating how it differs from regular append.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Lab 13

    Uploaded by

    Balls Mahoney
    120 views3 pages
    This document provides instructions for Laboratory Assignment 13 in CSE1729 - Introduction to Programming. The objectives are to work with priority queues and mutations in objects. The assignment is due on April 19, 2016 and is worth a maximum of 3 points. Students are asked to construct a priority queue object that maintains a heap, uses a generic order relation, and exposes methods for empty?, insert, extract min, and size. The assignment also involves writing a destructive append function called nconc! and demonstrating how it differs from regular append.

    Original Description:

    Lab 13

    Original Title

    lab13

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document provides instructions for Laboratory Assignment 13 in CSE1729 - Introduction to Programming. The objectives are to work with priority queues and mutations in objects. The assignment is due on April 19, 2016 and is worth a maximum of 3 points. Students are asked to construct a priority queue object that maintains a heap, uses a generic order relation, and exposes methods for empty?, insert, extract min, and size. The assignment also involves writing a destructive append function called nconc! and demonstrating how it differs from regular append.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    120 views3 pages

    Lab 13

    Uploaded by

    Balls Mahoney
    This document provides instructions for Laboratory Assignment 13 in CSE1729 - Introduction to Programming. The objectives are to work with priority queues and mutations in objects. The assignment is due on April 19, 2016 and is worth a maximum of 3 points. Students are asked to construct a priority queue object that maintains a heap, uses a generic order relation, and exposes methods for empty?, insert, extract min, and size. The assignment also involves writing a destructive append function called nconc! and demonstrating how it differs from regular append.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 3

    CSE1729 - Introduction to Programming

    April 19, 2016

    Laboratory Assignment 13

    Objectives
    Work with Priority Queues
    Work with mutations and objects

    Due Date
    This assignment is due on Tuesday evening, April 19, 2016. (The actual deadline is Wednesday
    morning at 4am.) No late work will be accepted, but your lowest two lab assignment grades will be
    dropped in particular, you can omit completion of two lab assignments without penalty.

    Value
    This assignment is worth a maximum of 3 points. The assignment will be graded based on these
    criteria:
    (0 point) No attempt.
    (1 point) Some work.
    (2 points) All functions work but test cases are missing, the source code is not commented or
    formatted neatly.
    (3 points) All functions work, there are at least 2 test cases for each function, the source code
    is commented, formatted neatly and correctly, and the racket (.rkt) file is named according to
    the instructions.

    Activities
    1. The next problem set (Problem Set 10) describes and guides you in constructing a Huffman tree.
    The algorithm in the problem set is described in terms of a priority queue, and the intention
    is for you to use (essentially) the priority queue developed in Problem Set 8 (for heap sort) as
    a building block for this assignment. One challenge is that you will need to put weighted trees
    into the priority queue, using the order relation given by the weights. Also, as the algorithm
    is described in the homework, it would be convenient if you had a way to easily determine the
    number of elements in a given priority queue.
    So, to ramp up for the homework, the objective for this lab is to construct a priority queue
    object which:
    (a) maintains the priority queue as a heap,
    (b) uses a generic (first order) order relation, and
    1

    (c) exposes methods empty?, insert, extract min, and size.


    Thus, the object constructor for the priority queue should take one argument (the order relation), and return a dispatcher yielding 4 methods.
    Hint: Of course it is possible to implement size by actually traversing the heap every time it
    is called, but you can do something smarter by maintaining a private variable q-size, which is
    destructively updated every time something is inserted or extracted from the heap.
    2. You have seen set!: there are other destructive operators that work on pairs:
    (set-car!

    lst val) changes lst so that (car lst) refers to val

    (set-cdr!

    lst val) changes lst so that (cdr lst) refers to val

    The interesting thing about these is that if you use them to change a list, the list changes, and
    any variable referring to that list changes. Consider the following:
    >( define a (1 2 3 4))
    >a
    >(1 2 3 4)
    >( set-car ! a fish )
    >a
    >( fish 2 3 4)
    >( set-cdr ! ( cdr a ) eat )
    >a
    >( fish 2 . eat )
    The set-cdr! in the example illustrates that changing a part of a list destructively changes
    the whole list. Lets try it and see what happens.
    (a) Write a Scheme function called nconc! that does append destructively.
    Remember how append works:
    ( define ( append x y )
    ( if ( null ? x )
    y
    ( cons ( car x )( append ( cdr x ) y ))))
    On each recursive call for which x is not empty, we build a new list using cons.
    Here is an alternative:
    1. Recursively cdr down list x until you reach the last element
    2. Set the cdr of that last element to be y
    Write the scheme function (nconc! x y) that implements the above alternative. It should
    return a list that looks just like what you would get from append.
    (b) Demonstrate that append and nconc! behave differently. Try the following:

    ( define
    ( define
    ( append
    a
    b
    ( nconc !
    a
    b

    a (1 2 3))
    b (4 5 6))
    a b)

    a b)

    How do you explain the differences? What do you think would happen if you evaluated
    (nconc! a a)?
    Hint: Try drawing some box-and-pointer diagrams.
    Once you have finished:
    1. Save your work to a file using an appropriate filename (using the following convention:
    Lastname-Firstname-CSE1729-Lab13.rkt) and preserving the .rkt file extension.
    2. Submit your lab solution file for grading via the courses.engr.uconn.edu site.
    If for some reason you are not able to submit your files on courses.engr.uconn.edu, email
    your files to your TA before the deadline.

    You might also like