CSE 1729代做、代做Programming、c/c++，Python，Java程序语言代写

日期：2020-04-14 10:49

CSE 1729 - Introduction to Principles of Programming April, 2020

Laboratory Assignment 9

Objectives

• Work with symbol frequencies in lists

• Work with heaps

• Learn a new way to sort

Activities

1. Define a Scheme function (num-occurs sym lst), that takes two parameters: a symbol sym

and a list lst; it evaluates to the number of times the symbol appears in the list. The list might

be nested, but you do not count any symbols within nested lists. For example> ( num-occurs ’ uh-huh ’( thats the way uh-huh uh-huh i like it uh-huh uh-huh ))4> ( num-occurs ’a ’(a b c ( not (c b a ))))

1

2. Define a Scheme function, named freq-list, which takes a list of symbols as a parameter and

returns a list of symbol-frequency pairs. That is, the function will produce a list of pairs where

the first value in the pair is a symbol and the second value in the pair is the frequency (i.e. the

number of times) that symbol appears in the list. There will be only one pair for each distinct

symbol in the list.

There are multiple approaches possible, but you should only count the number of occurences of

each symbol once (Hint: you can use num-occurs.)

Example:

> ( freq-list

’( thats the way uh-huh uh-huh i like it uh-huh uh-huh

thats the way uh-huh uh-huh i like it uh-huh uh-huh

thats the way uh-huh uh-huh i like it uh-huh uh-huh

thats the way uh-huh uh-huh i like it uh-huh uh-huh ))

(( it . 4)( like . 4)( i . 4)( uh-huh . 16)( way . 4)( the . 4)( thats . 4))

The order of the elements in what freq-list returns is unimportant – it will depend on your

implementation.

3. Build the logic for a heap structure that stores symbol-frequency-pairs, making it easy to find

the least frequent symbols stored in the heap. Most commonly, heaps are used to store pairs

consisting of one items of any type, and one number to be used to compare with other pairs

when looking for the minimum value. As an example, consider pairs that contain tasks and

1

their deadlines; we would like to store them so we access the earliest deadline first – we want

to extract the pair with the minimum deadline value.

Specifically, you should write Scheme procedures for heap as in lecture: create-heap, h-min,

left, right, insert,insert-list, and remove-min. The difference between these and the code

we discussed in lecture is that each entry consists of a pair, and the second element of the pair

is a number that is used in ordering the heap. It will make your code clearer if you define two

functions for the pairs that you put in the heap, value and weight. Given these, the heap

characteristic is that for each heap, the weight of all of the nodes in the left and right subtrees

will be greater than or equal to than the weight at the root, i.e. if H is a heap with non-null

subtrees,

>(> (weight (h-min H))(weight (h-min (left H))))

#f

>(> (weight (h-min H))(weight (h-min (right H))))

#f

Note that more than one node in the tree can have the same weight.

The specific functions you need to write and test are:

(a) (create-heap vw-pair left right) evaluates to the heap with vw-pair a pair consisting

of a value (anything) and a weight, which must be a number.

(b) (h-min heap) evaluates to the value-weight pair at the root, that is, the pair with the

smallest weight in the heap,

(c) (left heap) evaluates to the left child of the heap,

(d) (right heap) evaluates to the right child of the heap,

(e) (insert vw-pair heap) evaluates to the heap resulting from inserting the value-weight

pair vw-pair,

(f) (insert-list-of-pairs vw-pair-list heap) evaluates to the heap resulting from inserting

all of the value-weight pairs from the list vw-pair-list into the heap.

(g) (remove-min heap) evaluates to the heap resulting when the value-weight pair with minimum

weight (at the root) is removed.

Remember that the results of insert and remove-min are heaps, which means that the weight

in the value-weight pair at the root is less than or equal to the weights of all of the value-weight

pairs in its subheaps. Also, remember to alternate which subtree gets inserted into (see lecture

slides) to maintain balance.

4. Today’s discussion questions have to do with testing, which has become more difficult lately.

When you are coding and debugging, how do you generate test cases? And how can you tell if

your answers from these tests are correct? Your answer should be a single paragraph, embedded

as a series of strings in your submitted .rkt file, and should be based on a reflective discussion

with your peers that will take place about halfway through the lab. When considering this

question, think about what you have done on recent assignments, not just on today’s lab.

5. Heaps can also be used to sort sequences of pairs by weight! Suppose I have a list of value-weight

pairs in any order, I can use my heap code to sort them by

2

1. Insert each of the list of pairs in the heap,

2. Successively add the minimum to a list, and remove the minimum from the heap, until the

heap is empty.

You have a function above insert-list-of-pairs that can do the first part. So what you need

to do is write a Scheme function (get-in-order heap) that uses h-min and remove-min to get

the list of pairs sorted by weight. Once this works, you can implement heapsort as

( define ( heapsort pair-list )

( get-in-order ( insert-list-of-pairs pair-list ’())))

6. Combine the results from questions 2 and 5 by doing the following. Given a list of symbols, use

freq-list to generate the associated list of symbol-frequency pairs. Use heapsort to sort that list.

Be sure and generate interesting examples (lists of symbols with repeats so that not all have the

same frequencies, eg.), and show what (freq-list your-list) and (heapsort (freq-list

your-list)) evaluate to.

For example:

> ( freq-list ’( row row your boat boat boat row your boat boat boat ))

(( boat . 6) ( your . 2) ( row . 3))

> ( heapsort

( freq-list ’( row row your boat boat boat row your boat boat boat )))

(( your . 2) ( row . 3) ( boat . 6))

3