CISC

-

213

,

BCCC

Page 1

of

1

Lab

1

Introduction

The process of software engineering always should entail refinement and reuse

. When one is

considering

a large project, perhaps with as many as 100 programmers,

dealing with the complexity

of a multifaceted system installation and keeping track of

what each person on the team

is building

requires a formal approach

. In Object

-

Oriented

(OO)

systems, the practice of encapsulation makes

knowledge of the inner working

of disparate components

almost unnecessary. Never the less

communication skills are essential if one is expected to understand how what they are responsible

for works; what its dependencies are; and perhaps most importantly that what is coded does not have logical errors.

Logical errors can be harder to detect than syntax errors. The class will still compile if it has logical errors , so these sorts of errors can be harder to identify, diagnose and repair

.Each lab this semesteris designed to give you experience working with data structures and

algorithms, by performing analysis and both logical and physical design. Analysis in the OO contextentails identifying classes in the real world, thinking about interdependencies, then finally writing the Java code thatimplements logic using classes;flourished with procedural(sequence, selection,looping & invocation) constructs

.

It is possible to build the physical design first; this exists as a formal

approach known as prototyping. When I help you write code in class; when another student helps you write code; or in thecase that you are tutoring yourself; one is at the face engaging in slight nuances of prototyping.

It is generally suggested, however, to build a logical design of some kind prior to coding. One should

be prepared to write pseudocode. See the last section in each lab document to determine precisely

what is expected to be submitted for grading.

Notice why this is important. It might not seem

important in the world of software engineering. Because as I mentioned above, reuse does not

require refinement, so software engineers might be likely to do as little refinement

as possible. This

is Computer Science. Try to implement things in a way that makes sense. Build incrementally. Test

as you go. But always remember to have UML and pseudocode prior to writing the Java.

Given a sorting or searching algorithm, implemented in a high-level programming language, running on

a specific hardware platform, it is possible to determine a constant K that uniquely represents the

contribution the hardware makes to overall execution time. When thinking about the algorithm

it is

essential

to consider this constant K, but the expressions one makes about performance should not

include K. Big O notation describes performance on the

basis of the number of steps an

algorithm takes

as the

number of elements being processed is increased. By lettin

g the number of elements approach

infinity, one can derive suitable Big O expressions. Performance of the algorithms studied thus far

range from O(1) on the fast side, to O(log N), then O(N) on the slow side. Using this knowledge it is

possible to start wi

th a meaningf ul logical design. Big O is part of the analysis & design phase of the

Software Development Life Cycle (SDLC).

Domain Description

See the instructions on page 76 in the Lafore text

Programming Project 2.4

. The required code

starts on page 5

9,

LISTING 2.4

. Note that only

the

insert

method

does not implement the binary

search. Please describe

a way to determine why binary se

arch

is better for insertion

than linear

search

. Include this description in the processing section of your pseudocode.

What Will I Submit for Grading

?

Pseudocode, UML, code for OrdArray and OrderedApp classes, test documentation (console I/O).

Can someone do this mainly and also explain a bit on how to? i seriously dont get this at all.

This is is a powerpoint he gave us explaining it more which still is confusing:

So

how

do

I

do

Lab1?

Bucks County Community College (

http://bucks.edu

)

CISC213

-

N01

Computer Science III

Mr. John A. Summers, MS

Fundamentals

1

2

7

14

17

This is sample data (an array called a)

a[0] ==

1,

a[1] == 2 ... a[4] == 17 (each of these statements evaluate to Boolean true)

nElems == 5

size == 5

Pseudocode

Purpose

: Insert an integer into a sorted array.

Input

: Array; size of array; number of elements in the array.

Processing

: Find where the integer should go in the array using binary search. Shift existing elements accordingly.

Insert integer in its proper place. Increment number of elements in the array.

Output

: Sorted array with integer inserted. Incremented number of elements in the array.

Details on Processing

Implement recursive binary search to return the

element index of integer thats closest in value to the

integer being inserted;

If the value found is less than the value being inserted

then insert after the index value found;

If the value found in greater than or equal to the value

being inserted then insert before the value found.

Implementation

Illustrated using UML (does not include all class methods, just the

ones implemented to perform the insertion).

DSLab1

-

size: int

-

a[]: long

-

nElems: int

-

middle: int

+ DSLab1()

+ display(): void

+ insert(value:

long): void

-

findInd(value: long, start: int, stop: int):int

-

insert(value: long, ind: int):void

The Application

public class TestBedLab1 {

public static void main(String[] args) {

DSLab1 tiger = new DSLab1();

tiger.display();

tiger.insert(23);

tiger.display();

tiger.insert(4);

tiger.display();

tiger.insert(1000);

tiger.display();

tiger.insert(11

);

tiger.display();

tiger.insert(49);

tiger.display();

}

}

Be sure to comment this code out

when you begin this lab. We are

hardcoding the underlying array at

the outset. This enables us to test

insert as it is built, without having

to rely upon insert to set the

underlying array up with keys in

ascending order.

The DSLab1 Class Attributes

private final int size = 10;

private

long[] a = new long[size];

private

int nElems = 0;

private

int middle = 0;

Constructor

public DSLab1() {

//priming the array to perform testing

//once the insert method is implemented, no longer required

a[0

] = 3;

a[1

] =

45;

a[2

] =

77;

a[3

] = 98;

a[4

] = 101;

a[5

] = 557;

nElems

= 6;

}

d

isplay Method

public void display() {

for(int i = 0; i < nElems; i++) {

System.out.print(a[i] + " ");

}

System.out.println("****End Output****");

}

Public insert Method

public void insert(long value) {

if(nElems == size) {

System.out.println("****OVERFLOW****");

return;

}

int ind = findInd(value, 0, nElems

-

1);

insert(value, ind

);

}

Private findInd Method

private int findInd(long value, int start, int stop) {

middle = (start + stop)/2;

if(a[middle] == value)

return middle;

if(start >= stop)

return start;

else if (a[middle] < value)

return findInd(value, middle + 1, stop);

else

return findInd(value, start, middle

-

1);

}

Note: This is a tail

-

recursive method! See

https://en.wikipedia.org/

wiki/Tail_call

Private insert Method

private void insert(long value, int ind) {

if(a[ind] < value) {

for(int i = nElems; i > ind + 1; i

--

) {

a[i] = a[i

-

1];

}

a[ind+1] = value;

}

else {

for(int i = nElems; i > ind; i

--

) {

a[i] = a[i

-

1];

}

a[ind] = value;

}

nElems

++;

}

We are utilizing simple iteration to

perform the shifting of elements.

This work could also be performed

with recursion

.