Challenge

Quick Index

Description
Tips
Challenge Rules
Challenge Problems
Project Files
Submitting
References

It will be helpful to do a quick review of a fixed array....

This challenge project will be about writing algorithms for our first data structure MyArray

The purpose of "MyArray" is to provide the functionality to support common collection behaviors. Our algorithms will provide the logic needed for these behaviors.

Definition of MyArray:

It is a fixed array
It is a sequential structure of length N
N may be 0 or may be very large
The array will have indexes starting at [0] and ending on [N-1]
We can change elements, e.g., if the first element is "foo" (index 0) we could change it to "moo", "boo", or whatever we like

Limitations of "MyArray":

Because it is a fixed array, this means we can not change its size -- we cannot add or remove elements to it after it has been constructed

Objectives

To begin to learn how to apply an object (oo) approach to algorithms
To become handy with "functions" (because functional programming opens up an entire new world to us)

Tips

Getting Started

Start early on this one -- you'll enjoy it much more
Read this first: Do We Worry about Errors in Pseudocode?
It is next suggested step is to get familiar with the "object universe" for this challenge (see below)
You will use this a lot: -- MyArray Method Summary...

Examples - Tips

Strong suggestion: do not start any challenge problems until you have worked through the examples
Here is the Examples page... -- The challenge problems will be similar to the examples
Do the examples somewhat on your own and somewhat peeking at the solutions (this will help your pseudocode skills but will also be a good "object-oriented refresher")

Challenge Problem - Tips

When doing the challenge problems, try doing one algorithm at a time followed by an "algorithm walk through" as we learned previously.
You could try the "Algorithm Studio" if you like (provided along with the challenge) -- just be careful not spend time fixing bugs (it's not needed in pseudocode)
Use helper algorithms to simplify your logic
Use "equals" over "==", and "!equals" over "!=" for objects, as described here...
Try: Walking the Array
Visit the discussion board to browse ideas and always feel free to create posts with any questions (and feel free not to -- either way)

Problem Context (Object Universe)

The object universe for this challenge is the MyArray object. As mentioned elsewhere, you will use this a lot: -- MyArray Method Summary...
Don't forget the Examples -- MyArray has a number of methods already completed that should be used for your algorithms as demonstrated in Examples.
All of our work will be inside "MyArray". That means that the context for our algorithms will be a MyArray object
This is helpful, because many methods are already completed in MyArray, and they are in your algorithm scope

Equality Gotcha

Most of our examples in this chapter use primitives for simplicity, but in reality our structures will contain proper objects like customers, employees, students, ... Thus we need to support objects.

This means we must do the following:

Use "a.equals(b)" in your algorithms, not "a == b". The latter ("==") is limited and will give the wrong answer for objects.
Similarily, use "!a.equals(b)" and not "a != b"

See more info here....

Getting Stumped

I hope we get "stumped" a little bit on some of these! That's how we'll learn. I would guess there would be a grading "curve" (that's a guess). Just do your best and fire questions to all avenues (discussion board, emails instructor/tutors, tutoring sessions, ...). And also step back and re-try an example, or try another if really stumped on one.

Challenge Rules

These rules are driving us towards an object approach. And that basically means one thing: message sends.

Here is the small set of rules for this challenge which apply to the algorithms to be written:

Can not use code libraries (classes, methods, functions, ...)
Must be written in pseudocode following this syntax...
Must use static factory constructors (many examples provided)
Must not access ivars and also not any methods starting with the prefix "priv"

Note -- in rare cases, the challenge write-up may include explicit notes that would override a rule

We may use any of the tasty menu of algorithms (methods) described and listed above in "Object Universe".

Challenge Problems

Here are the problems to complete: Challenge Problems

As mentioned, "MyArray" will be a practical structure. We need to write algorithms that will give the structure its brains.

These public methods need to have algorithms written:

indexOf*
join*
findIndex*
findLastIndex*
occurrences*
reversed
map
includes
findClosestToEnd
lastIndexOf
filter
reject

* - indicates a completed algorithm provided for you -- see Examples...

Project Files

Provided Files

Here are the provided files for this challenge: a3-project.zip.

Extract (copy) the "a3-project" directory from the ZIP archive into a working directory of your computer.

The directory "a3-project" will be our "project directory".

Contents of extracted project directory:

Directory Path	Description
a3-project	project root directory
a3-project\A3	Contains your "algorithm files"
a3-project\lib	No changes needed
a3-project\model	No changes needed
a3-project\algo-studio	See "Algorithm Studio" below

Algorithm Studio

An algorithm studio is available for this challenge. It is optional but could help with "proving" (testing) algorithms.

See Algorithm Studio Instructions....

File Management

The files are simple for this challenge. They have already been setup for you (see "Provided Files" above).

Each algorithm has its own corresponding file in the "a3-project/A3" directory.

For example, the algorithm for the method "lastIndexOf" should be put in the file "A3/lastIndexOf.js".

In each file, simply replace the text "//ALGORITHM HERE (Pseudocode)" with your algorithm written in pseudocode per these syntax rules.

About half of the files are already completed. They make up the Examples for this chapter. The completed files will also provide good reference for you to help you get started on your own. You do not need to make any changes on the files that are already completed.

Submitting

Create a ZIP file
Be sure to create a "ZIP" archive type and not other archive types
Name your ZIP file in the usual way ("Assignment XX -- FirstName LastName.zip" where "XX" is the assignment D2L drop box name and FirstName and LastName are your corresponding names in D2L). E.g., "A3 -- Suni Lee.zip"
Add the "A3" directory into the ZIP file (note that the "A3" dir is located in your project root directory)
Please do not nest .zip files -- do not put other .zip files into the one ZIP archive file
Your submit should be one ZIP file

References

This listing is a consolidation of the references (links) from above:

Data Structures And Algorithms (DSA) (Chapter 103 - OO Algorithms I)

Chapter 103 - OO Algorithms I Challenge

Contents Intro How-To Examples Recap Lessons Learned Challenge

Chapter Top Search TOC