首页 >
> 详细

CSCI 104 - Spring 2020

CSCI 104 - Spring 2020

Data Structures and

Object Oriented Design

HOMEWORK 5

Due: (See assignments page )

Directory name in your github

repository for this homework (case

sensitive): hw5

Any skeleton code for this

assignment will be available in

homework_resources/hw5 .

Do a git pull in your

homework-resources repo.

Then copy the homeworkresources/hw5

folder into your

hw-username repo and use the

skeletons provided to start work

in that hw5 folder.

Objective

In this assignment we will review recursion,

traversals, and heaps.

Introductory Notes

In this assignment you will need to submit:

Your completed tree traversal

(expression solver)

files/implementations in

hw5/traversal/ folder as well as a

Makefile in that folder to compile

your code to an executable exprtester

by running make in that folder.

Your heap operations answers in a file

named hw5.pdf in your hwusername/hw5

folder

Your completed heap files in the

hw5/heaps/ folder. You should have

some test file and a Makefile that

can be used to compile a test

program named heap-test by

running make in that folder.

Your completed eventsim

files/implementations in

hw5/eventsim/ as well as a Makefile

in that folder to compile your code to

an executable eventsim by running

make in that folder.

1. Binary Tree Traversals

(30%)

It is common to represent expressions (e.g.

arithmetic) as a tree where internal nodes

(non-leafs) are operators and leaf nodes are

values (literals (constants) or variables). In

this problem you will use a tree to represent

arithmetic expressions and perform several

operations on the tree that require recursive

traversals of the tree.

We will provide an expression reader that

will construct the tree so that you can focus

on the various processing operations.

Expression Format

This problem will process expressions that

contain the 4 basic arithmetic operations:

+ , - , * , / , integer literals, and

parentheses: ( , ) .

As an early example, consider ( ( 4 / 3 )

+ 96 + 104 ) would produce a tree:

Every unique operation (+,-,,/) must be

enclosed by parenthesis () (i.e. there is no

implicit order of operations allowed). So we

cannot write ( 2 * 4 + 3 ) , but instead

must write ( ( 2 * 4 ) + 3 ) . In addition,

every operator, parenthesis, or literal **must

be separated by spaces*.

So that the tree will contain nodes of the

same same type, each node will store a

string. That string will contain the operator

(e.g. "+") or the integer literal (e.g. "96") but

as a string. (You will convert to an integer

when you validate and/or solve the

expressions.)

Our reader roughly implements the following

rules/grammar for expressions:

op := '+' | '-' | '*' | '/'

literal := string

expr := literal | '(' expr ')' | expr op

expr

root-expr := '(' expr ')'

Each internal node of the tree should be an

operator and each leaf should be a numeric

string literal (string representing a valid

integer including negative numbers). The

provided reader will read in an expression

from any provided input stream (our test

program uses stdin by default but you can

use I/O redirection to redirect the contents

of a file as input) and return a pointer to the

root node or throw std::runtime_error if

the grammar is not met.

Expression Operations

You will implement three operations on the

expression tree that require recursive

traversals:

Validating the Expression: While our

expression reader detects most

syntax errors, it does not validate the

each leaf node contains a string that

can be converted to a valid integer.

Your task is to write a recursive

traversal of the tree that will return a

bool indicating that entire expression

contains valid integers as leaves. That

is all it needs to check for (no other

forms of errors). Consider which form

of traversal is most appropriate for

this task (pre-, in-, post-order). A

prototype for this function is provided

in the skeleton and you may not

change it. However, you may add

helper function(s), if necessary.

Printing the Expression: You should

implement a recursive traversal of the

tree that converts the internal tree

representation back to a correct/valid

text based representation and output

it to a provided std::ostream .

Assuming the tree represents a valid

expression, the text expression you

output should be correct, such that it

could be provided as input in a

subsequent run and generate the

same tree. Consider which form of

traversal is most appropriate for this

task (pre-, in-, post-order). A

prototype for this function is provided

in the skeleton and you may not

change it. However, you may add

helper function(s), if necessary.

Evaluating the Expression: You

should implement a recursive

traversal of the tree that evaluates the

expression and returns the integer

result. You may assume the tree

represents a valid expression.

Consider which form of traversal is

most appropriate for this task (pre-,

in-, post-order). A prototype for this

function is provided in the skeleton

and you may not change it. However,

you may add helper function(s), if

necessary. (Note: If the expression

contains a divide-by-0, you do not

have to handle it specially. Just let it

fault.)

Testing

We have provided a test-driver application

that you can use to verify your functions. It

will call our reader function and return the

pointer to the root of the tree or throw

std::runtime_error . It will then call your

functions to validate, print, and solve the

expression.

Other Requirements

You must use recursion to process

each node but can use a loop to

iterate through children.

You may not modify the signatures of

the functions we provide but may add

helper functions.

You should only edit expr-ops.cpp .

2. Heap Operations (10%)

You will answer several questions about

Heaps in this problem.

For this problem, you can choose to draw

this by hand and scan it (and submit as a

JPG or PDF), or to use some graphics

software (and produce a JPG or PDF), or

draw it using ASCII art (this may be a lot of

work). Name your file hw5.pdf .

Part a (3%)

Indicate whether the following arrays are

valid binary Min Heaps (assuming the root is

at index 0 of the array). For each array

which is not, indicate which child(ren)

violate the heap property (i.e. are out of

place).

[6, 2, 26, 24, 22, 20, 48, 46, 44]

[2, 16, 4, 50, 18, 5, 28, 71]

[2, 16, 4, 10, 18, 26, 28, 11]

Part b (5%)

Draw the tree representation of the following

binary Min Heap in its initial configuration,

and after each operation. Make sure to

clearly indicate each of your final answers.

This is a sequence of operations, meaning

one affects the next.

Initial Configuration: [2, 4, 6, 8, 10, 12,

14, 16]

Insert 3

Pop (top element)

Pop (top element)

Insert 5

Part c (2%)

Given the following array, perform the build

heap (make heap process) to convert the

array into a valid min-heap. Show the array

contents after each step. More specifically,

show what index you are calling

heapify/trickle-down on (e.g. heapify(8) )

and the entire array contents after each call.

[38, 8, 29, 15, 53, 20, 24, 18, 7 ]

3. Heaps (25%)

Build your own m-ary Heap class whose

public definition and skeleton code are

provided in the hw5 folder of the homeworkresources

with the interface given below.

Rather than specifying a specific type of

heap (Min- or Max-Heap) we will pass in a

PComparator (P for Priority) object so that if

the comparator object functor implements a

less-than check then we will have a minheap.

If the PComparator object functor

implements a greater-than check we will

have a max-heap.

template template

class class Heap Heap

{

public public:

/// Constructs an m-ary heap for any m >= 2

Heap(int m, PComparator c = PComparator() );

// other stuff

};

You may use the STL vector

if you wish. You should of course NOT use

the STL priority_queue class or

make_heap , push_heap , etc. algorithms.

You may add private helpers, if you like.

As you implement the heapify() process

when popping the heap, recall that a parent

would swap with its best child if the best

child is "better" than the parent. However,

what if we have a tie for the best child?

Choosing either to swap with is technically

fine, but for the sake of the next homework

problem where you will use the heap, let us

choose the left-most of the children tied for

the "best" (first one encountered if you are

iterating in order).

Notice we can provide a default template

type for the Comparator so that the client

doesn't have to specify it if they are happy

with the std::less (i.e. which assumes a

built-in operator< is available for type T

and calls it).

Notice the constructor also provides a

default value for the Comparator which is a

default-constructed Comparator. Default

parameter values will be used if the client

does not supply them. Also if a default

parameter is used then all parameters after

it must also have default values (i.e. default

parameters must be at the end of the

declaration). The last thing to note is you

only supply the default value in the

declaration of the function. When you

define the function (i.e. write the

implementation below) you would not

specify the default value again but just

leave the argument types/names. For

example, when implementing the function

you'd just define:

template template

Heap

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp2

- 代写r留学生作业、代做data课程作业、代写r编程语言作业代做r语言编程|调 2020-05-25
- Cosc473作业代做、Systems作业代写、Python编程设计作业调试 2020-05-25
- Data留学生作业代做、R编程设计作业调试、R语言作业代写、Program课 2020-05-25
- Comp 250 Assignment 3 2020-05-24
- Macm 316 – Computing Assignment 7 2020-05-24
- Sta457 Assignment 2020-05-24
- Homework 10 2020-05-24
- Lab 2 Msc: Time Series Prediction With... 2020-05-24
- Comp2011作业代做、Data Analysis作业代写、C++编程语言 2020-05-24
- 代做compsys201作业、Python，Java，C/C++编程语言作业 2020-05-24
- Program留学生作业代做、Python编程设计作业调试、Data作业代写 2020-05-24
- 代写 Practical 3 Covid-19程序作业，代写... 2020-05-23
- 代写comp3059作业、代做programming作业、Java语言作业代 2020-05-23
- Coit12206作业代写、Program课程作业代做、Java、Pytho 2020-05-23
- Data2001作业代做、Data Science作业代做、Sql语言作业代 2020-05-23
- 代写comp2017作业、代写c/C++语言作业、代写data作业、C/C+ 2020-05-23
- Data留学生作业代做、Python编程设计作业调试、代写program课程 2020-05-22
- Mkan1-Uc 5103作业代写、代做analytics作业、Java，P 2020-05-22
- Pols 512作业代写、R编程设计作业调试、Data留学生作业代做、代写r 2020-05-21
- Econ 6070作业代做、Data课程作业代写、代做java，Python 2020-05-21