Algorithms Homework 8 Arrays are useful in that they allow to access elements by an index

Confidential Teaching Materials

Homework 8 Criteria, Page 1 of 9

Homework 8 Grading Criteria

Note: To receive any credit whatsoever, your answers must be legible and readily readable in the

judgment of the grader. Add brief explanatory comments as necessary to make sure your answers

are clear and unambiguous to the grader.

[p1] 80 points

Arrays are useful in that they allow to access elements by an index. The drawback to arrays is that their size

must be fixed. This can cause some problems in software design because it forces the programmer to guess the

maximum number of elements he/she may need.

To get around this limitation, object-oriented languages such as Java allow a programmer to use a Vector class.

Through its public methods, a Vector allows random access to a dynamically-allocated data structure. Elements

in the data structure are accessed by their position. The first element in the structure is position 1, the second is

2, etc.

Your job is to implement a vector class. Since a user should be able to make a vector of any data type, your

class must use a generic parameter. Your vector class should use a linked list as its data structure to store the

elements in the vector, and should implement the following functionality:

function Element_At returnsa DataType (position isoftype in num)

Given a position, returns the element at that position.

You do not have to worry about the position being invalid.

procedure Remove_Element (position isoftype in Num)

Removes the element in the given position in the vector.

You do not have to worry about the the position being invalid.

function Size returnsa Num ()

Returns the number of elements in the vector.

function Contains returnsa Boolean (element isoftype in DataType)

Returns true if element is found in the vector; otherwise,

returns false.

procedure Add_Element (element isoftype in DataType)

Adds the given element to the end of the vector.

procedure Insert_Element_At (element isoftype in DataType,

position isoftype in num)

Adds the given element before the given position.

You do not have to worry about the position begin invalid.

function Is_Empty returnsa Boolean ()

Returns true if the vector has no elements; false is returned

otherwise.

Note that DataType in the above module headers indicates your class’s generic parameter. In modules that have

a position parameter, you may assume that the position will always be passed as a valid integer. Also assume

that the = operator will work on any type of generic parameter.

Feel free to add any “helper” modules in the protected section

Confidential Teaching Materials

Homework 8 Criteria, Page 2 of 9

of your class. The public headers of your class must match those given exactly, i.e. you may not add or remove

any parameters. Also assume that the = operator will work on any type of generic parameter.

[c1] 80 points

Sample Solution:

Again, there are several ways to do this one. This solution uses loops; recursion and

protected

Node definesa record

data isoftype DataType

endfunction

procedure RemoveElement(position isoftype in num)

current isoftype ptr toa Node

if (position = 1) then

listhead <- listhead^.Next

function Size returnsa Num ()

current isoftype ptr toa Node

Confidential Teaching Materials

count isoftype num

Current isoftype ptr toa Node

current <- listhead

loop

exitif (current = nil) or (current^.data = element)

current <- current^.Next

listhead <- temp

listhead^.next <- nil

else

current <- listhead

loop

temp <- new(Node)

temp^.data <- element

if (position = 1) then

// special case, add to front

temp^.next <- Listhead

Confidential Teaching Materials

endif

endprocedure

GRADING: 80 points

Public

~~~~~~

-2 for not having the “class Vector” part (bdc)

-2 for the Node declaration (rec)

-2 for not having tie proper pointer (ptr)

-4 for not having Listhead (nav)

ElementAt:

-1 for not returning the correct element (log)

RemoveElement:

-3 for losing the list in the process (log)

Size:

-2 for not finding the size of the Vector

Confidential Teaching Materials

Homework 8 Criteria, Page 5 of 9

(log)

-2 for not returning the size (ret)

Contains:

-2 for not walking down the list (log)

-2 for not setting up new node correctly (nwp)

-2 for not finding the end (log)

-2 for not setting up the new node correctly (nwp)

-2 for not finding the place to insert (log)

-3 for not returning the correct value (ret)

[p2] 5 points

Searching through a full and balanced binary tree of N elements for a particular element.

[c2] 5 points

CRITERIA FOR ALL BIG-O PROBLEMS:

-2 if they got the Big-O wrong.

Confidential Teaching Materials

Homework 8 Criteria, Page 6 of 9

[p3] 5 points

Searching through a linked list (of P elements) of arrays (of N elements each) for the largest value.

[c3] 5 points

[p4] 5 points

//N and P are constants

i, j isoftype Num

i <- 1

loop

exitif (i > N)

j <- P

loop

j <- j – 1

exitif (j = 1)

endloop

i <- i + 1

j <- N+P

loop

exitif (j > 0)

j <- j – 1

endloop

[c4] 5 points

[p5] 5 points

Popping data off a stack of height N.

[c5] 5 points

[p6] 5 points

Searching through a linked list (of P elements) of ordered arrays (of N elements each) for the smallest value.

[c6] 5 points

[p7] 5 points

Performing a bubblesort on an array of N elements.

[c7] 5 points

Confidential Teaching Materials

Homework 8 Criteria, Page 7 of 9

[p8] 5 points

Searching an ordered array of N elements for a given value if the value being sought is not in the array.

[c8] 5 points

[p9] 5 points

Searching for an element in a linked list (of N elements) of full and balanced binary search trees (of P elements)

for a particular value.

[c9] 5 points

[p10] 5 points

Adding a node to a full and balanced binary search tree of N nodes.

[c10] 5 points

[p11] 5 points

Adding P elements to the beginning of a linked list of N nodes.

[c11] 5 points

[p12] 20 points

Compare and contrast reasonable and unreasonable algorithms. Give an example of a each, and list some

examples of Big-O’s which indicate that an algorithm is reasonable or unreasonable.

GRADING:

[p13] 20 points

Explain the 4 different types of algorithmic errors, and give an example of each.

[c13] 20 points

Confidential Teaching Materials

Homework 8 Criteria, Page 8 of 9

Semantic errors – errors in the meaning of instructions

[p14] 10 points

Compare and contrast a greedy algorithm with an algorithm that employs dynamic planning. What are the

advantages and disadvantages of each?

[c14] 10 points

Greedy algorithms produce a solution by processing the data in the easiest manner, by

[p15] 20 points

Consider the following graph. It represents the graph of several cities and the distances between them.

(A)——14——(B)——-37——(C)

/ | / \ | \

9 | 18 16 | 14

/ | / | | \

(E) |11 (D)-11–(F) 18 (G)

\ | | \ | | /

6 | 14 21 43 | 9

\ | | \ | | /

(H)–12–(I) ——(J)——24—–(K)

You work for the phone company and are responsible for finding the way to connect each of these cities with the

smallest amount of cable possible.

Confidential Teaching Materials

Homework 8 Criteria, Page 9 of 9

Using the greedy algorithm, choose the links that you would use to connect the cities. List these links along with

their distances in the order you selected them. Also, calculate your total distance. Your answer should be in the

following format:

EH 6

JK 24

…

TOTAL: (total goes here)

[c15] 20 points

Sample Solution:

GRADING: