Discount GSP 295 GSP295 GSP/295 - All Lab 1 2 3 4 5 6 7- All Weeks - Week 1 - Week 2 - Week 3 - Week 4 - Week 5 - Week 6 - Week 7 - Grade A!!!
    GSP 295 GSP295 GSP/295 - All Lab 1 2 3 4 5 6 7- All Weeks - Week 1 - Week 2 - Week 3 - Week 4 - Week 5 - Week 6 - Week 7 - Grade A!!! GSP 295 GSP295 GSP/295 - All Lab 1 2 3 4 5 6 7- All Weeks - Week 1 - Week 2 - Week 3 - Week 4 - Week 5 - Week 6 - Week 7 - Grade A!!! GSP 295 GSP295 GSP/295 - All Lab 1 2 3 4 5 6 7- All Weeks - Week 1 - Week 2 - Week 3 - Week 4 - Week 5 - Week 6 - Week 7 - Grade A!!!

GSP 295 GSP295 GSP/295 - All Lab 1 2 3 4 5 6 7- All Weeks - Week 1 - Week 2 - Week 3 - Week 4 - Week 5 - Week 6 - Week 7 - Grade A!!!

$104.95
$139.93

GSP295—Week 1 iLab
A Simple ADT (70 points)

Grading Rubric Points
SquareMatrix Specification 10
SquareMatrix Implementation 25
SquareMatrix Test Driver 14
Test Plan and Lab Write-Up 14
Style 7
TOTAL 70

Deliverables

Create a single zip file including the following.

- A Word document containing your specification for Part 1
- Your Visual Studio Project directory and associated files, including source files for Parts 2–4.
- The results of your testing from Part 5. What tests did you run? Did everything work okay? Are there outstanding issues in your program? A short ½–1-page summary of your results is about the right length.

If you document any issues, it will be easier to isolate any problems, provide detailed help, and could potentially improve your grade.

Summary

For this Lab, create a simple ADT modeled after the mathematical concept of a matrix. Using this ADT, create a test driver that allows a user to perform all matrix operations.

(Note: For this exercise, you may find the Chapter 2 case study very helpful as a reference.)

Defining a SquareMatrix

A SquareMatrix is an NxN matrix. For example, one SquareMatrix of order N = 2 is the following.

3 -1
1 -3

A square matrix can be represented by a two-dimensional array with N rows and N columns. You can assume, for the purposes of this iLab, that the maximum value of N is 50. You can use static memory allocation so you do not have to worry about the details of dynamic memory here. It’s fine to “waste” space by allocating enough space for a 50 x 50 matrix.

Part 1: Specification

Write a specification for the SquareMatrix ADT. Remember, an ADT specification should have function, precondition, postcondition, parameters (with types), and return values (with types) for each method. Include at least the following operations.

• MakeEmpty(n), which sets the first n rows and columns to 0 and can perform other initialization operations as needed
• StoreValue(i,j,value), which stores the given value into the [i,j] position of the matrix
• Add, which adds two matrices together. You should allow a parameter to store the result.
• Subtract, which subtracts one matrix from another. You show allow a parameter to store the result.
• Print, which outputs the matrix to the console. It is fine to use a simple format such as the one given in the SquareMatrix example above.
• Copy, which copies one matrix into another

You may assume integers for parameters (or floats if you prefer, but you do not have to worry about template types; simply choose int or float).

You should use the parameter (n) to MakeEmpty as the given size of the matrix. In other words, in testing, you can assume you will always make a call to MakeEmpty first, which sets the size of the matrix. For all cases where the user tries to perform operations that are invalid on a matrix (such as adding or subtracting matrices of different sizes), it’s fine to output an error and simply refuse to perform the operation. However, you should make sure you check for these cases and output an error!

You may assume that Add and Subtract take a parameter “result” that is a SquareMatrix where the result is stored. For Copy, you may assume that one matrix is copied into the other and overwritten. Make sure you document which one is overwritten!

Part 2: Class Declaration

Convert your specification to a C++ class declaration. Remember to comment it well! It should compile; make sure it does before moving on to Part 3.

Part 3: Implement the Member Functions

Implement the individual member functions from your SquareMatrix ADT. Make sure everything compiles and comments well. You should have class-level comments, member function/method/variable level comments, and in-line comments.

Part 4: Create a Driver

Now that you are done, are you sure it works? Create a Main function that will provide a driver or interface to your program. Your driver should hold three SquareMatrix datatypes referred to below as positions 1, 2, and 3. Hence you can test an add/subtract by creating a matrix in positions 1 and 2 and then adding them with the result in position 3.

The test driver should prompt the user in a simple menu fashion (in text on the console). There’s no need to get fancy here. A simple multiple choice input is fine (type the letter of the command you want). You can ask for parameters separately on a new line with a prompt or simply pass them in one line—it’s your choice. For example, either “a 1” or “a” then “1” is fine for the create process.

You should create three instances of SquareMatrix so you can test all the ADT functions. Your test driver should have at least the following capabilities.

a) Create new SquareMatrix and store in position 1, 2, or 3
b) MakeEmpty ‘n’ rows/columns from matrix position 1, 2, or 3
c) StoreValue i,j,value to the matrix in position 1, 2, or 3
d) Add matrices in one position to another.
e) Subtract matrices in one position from another.
f) Print the matrix in a particular position.
g) Copy one matrix into another.

Think about your Copy command. Should this be a shallow or a deep copy?

Part 5: Testing

Create a test plan and use the driver you created in Part 4 to test your ADT. Make sure you reference the sections in your textbook about test plans and use the examples to help you.

Execute your test plan and write up your results. Does everything work? If not, fix and retest. Submit your final test results, which includes any issues you are having with your program, and explain what tests you ran (describe your test plan).

General iLab Comments

All coding assignments for this class will use Microsoft Visual Studio. This is available through the Software Store, which can be found in Course Home. Contact the Help Desk or your professor if you encounter any issues.

*Please note as a reminder that you may not copy code from any web reference to complete this assignment, even if you correctly give credit. You may, of course, use web references to help you understand, but you must code the assignment yourself. You may use code directly from your textbook where applicable, but do make sure you give credit in your comments if you are doing so.

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

GSP295 - Week 2 iLab

Sorted List Lab (70 points)

Deliverables

A single zip file including the following.

  • A Word document containing your graphs and write-up for Part 1.
  • Your Visual Studio Project directory and associated files, including source files for the Lab.
  • The results of your testing. What tests did you run? Did everything work okay? Are there outstanding issues in your program? A short half-page summary of your results is about the right length.
  • The results from your Part 3 tests. Include a table of results and a brief explanation.

If you document any issues, it will be easier to isolate any problems, provide detailed help, and could potentially improve your grade.

Summary

In this Lab, you will create a sorted ADT list and a test driver in order to verify its correctness.  You will also profile the main ADT list operations in order to see the differences in Big-O run-times.

Part 1: ADT Implementation Overview

Elements in your sorted list should be string elements. The ADT sorted list chapter in your textbook reviews the implementation steps and provides source code to help you. 

Hint: Your textbook uses the itemType structure and template. This is a good way to implement a generic ADT; however, it complicates the implementation, and it is not required for this course. If you are comfortable with the itemType structure and want to use it, you are welcome to. If you are not, you may change all itemType parameters to strings. For all Lab assignments in the course, the focus will be on strings. Notice that if you elect to use strings, you will also need to change the code that refers to item ComparedTo to a set of if/else statements using basic string comparison. You may also need to modify the textbook source code to pass variables by reference. You may use #include <string> to assist you with strings.

Part 2: Test Driver

You will need to create a driver routine to test all of the functionality of the sorted list ADT. This would be similar to what you did with Week 1 using command line instructions. You must implement at least one command for all eight ADT operations listed in your text. In addition, you must include a Print command that outputs the contents of your list (in order) for testing purposes.  Remember that you are implementing a sorted list; as such, your list should be sorted at all times. For the purposes of this assignment you should use strings as the items to hold/sort. 

Example commands might include the following.

Print

Insert <string>

Retrieve <sting>

Delete <string>

IsFull

You may choose the specifics of the input/output as long as your program gives enough information. Menu driven commands are perfectly fine. Make sure you explain your commands and how to interact with your program in your write-up and/or your console user interface. Make sure you check for all error conditions. For example, you can’t insert into a full list or delete from an empty one.

Design and implement a test plan. Write up your results. Does everything work? If not, fix and retest. Submit your final test results, any issues you are having with your program, and explain what tests you ran to determine those issues.  In other words, describe your test plan.

Part 3:  Big-O Run-Times and Profiling

An important part of writing efficient code is being able to profile it by testing its relative speed. You are learning about Big-O run-times in this course for all data structures. However, it is helpful to experience the actual effects of Big-O in terms of milliseconds of run-time.

Be sure to add this include file in your ADT and main drivers.

#include <Windows.h>

Modify your PutItem, DeleteItem, and GetItem operations to take an additional parameter; double and timetaken that will be set to the execution time of these operations. You can profile an operation in this way by adding this code to the very top of the operation.

       double start,end;

       start = GetTickCount();

And this code at the bottom of the operation.

       end = GetTickCount();

       timetaken = (end-start);

Modify the MAX_ITEMS variable in your ADT list to handle at least 1,000,000 list items. Tweak this number as needed based on the instructions below.

You can create a series of random five-character strings very easily to test your sorted list. Create a special test driver command that will do this. To make this easier for you, the basic code you will need to create random strings is provided.

Call your ADT PutItem operation to insert 1,000,000 strings into your ADT sorted list. Adjust the number of strings depending on the speed of your machine and use your best judgment. An appropriate amount of wait time should be in the 5-10 seconds range. Adjust the maximum number of elements to achieve a time in this range. If your code executes instantaneously, increase the amount of strings as needed.

In addition, make approximately 1,000,000 calls to your GetItem operation using both a string you know is in the list, astring[400,000] for example, and one that you know is not, “abcdefghij” for example. Then make approximately 1,000,000 calls to your DeleteItem operation. You should use the same number of calls you used for PutItem in order to obtain results you can compare.

Use cout to output the millisecond times for each of these operations. Now modify the 1,000,000 value, or whichever base value you are using, to be double and triple the size. Also run tests with half and one third the base size.

Make a table of the results for each of the three operations and explain the effect you are seeing. What is the Big-O run-time of your PutItem, GetItem and DeleteItem operations in your implementation? Include these results in your Lab write-up.

Hint: Be careful not to call your ADT operations inside the for loops generating your random strings; this may interfere with your results. Generate the strings first, and then make your ADT operation calls. Make sure to measure each operation separately. For example, measure 1,000,000 PutItems rather than 1,000,000 PutItems followed by GetItems

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

GSP295 - Week 3 iLab

Deliverables

A single zip file including the following:

  • Your Visual Studio Project directory and associated files, including source files for the Lab.
  • The results of your testing. What tests did you run? Did everything work okay? Are there outstanding issues in your program? A short half-page summary of your results is about the right length.
  • You do not need to submit your test plan, but it doesn’t mean you shouldn’t have one! 
  • Remember, for this Lab you must also submit the answers to the Part 5 questions.

If you document any issues, it will be easier to isolate any problems, provide detailed help, and could potentially improve your grade.

Summary

In this Lab, you will use recursion and implement an efficient sorting mechanism to solve common problems dealing with strings.

Part 1:Understanding Plindromes

Palindromes are funny little phrases. They can be words, sentences, or even numbers or other characters. Formally, a palindrome is a string that is the same when its characters are reversed.  For example, classic palindromes are the following.

  • ana
  • civic
  • radar
  • 122221
  • deed
  • toot
  • racecar
  • step on no pets
  • tattarrattat

Further, we will define some specific classification for palindromes for the purpose of this assignment.

Type 1 Palindrome: Every character has the same number of occurrences.

Type 2 Palindrome: Characters may have different numbers of occurrences.

For example:

  • ‘ana’ is a type 2 palindrome because there are 2 ‘a’ characters but only 1 ‘n’ character.
  • ‘civic’ is a type 2 palindrome because there are 2 ‘c’ characters, 2 ‘I’ characters, but only 1 ‘v’ character.
  • ‘tattarrattat’ is a type 2 palindrome – there are 6 ‘t’ characters, 4 ‘a’ characters and 2 ‘r’ characters.
  • ‘deed’ is a type 1 palindrome – there are 2 ‘d’ characters and 2 ‘e’ characters.

Order of a Palindrome: The number of occurrences of the alphabetically first character in a palindrome.

For example:

  • ‘ana’ is of order 2 because there are 2 ‘a’ characters which are alphabetically before ‘n’.
  • ‘deed’ is of order 2 because there are 2 ‘d’ characters and two ‘e’ characters.
  • ‘nopapon’ is of order 1 because there is only 1 ‘a’ character which is alphabetically first. 

Notice that in a type 1 palindrome, the order will be the number of occurrencesfor all characters.

Go through the list of palindrome examples to ensure that you can describe the type and order of each. Do some web research to find fun palindromes of your own for testing and determine their type and order.

Assumptions: For the purposes of this assignment, in the interest of time, we’ll exclude palindromes that are only palindromes by ignoring spaces and punctuation. For example, “A man, a plan, a canal: Panama” would not be a palindrome for our purposes because there is no matching “:” character, and even if the punctuation is removed, spacing differences invalidate this palindrome. You will also not need to worry about capitalization. For example ‘Ana’ is not a valid palindrome in our world because an ‘A’ is different than an ‘a.’

Part 2: Implement a Palindrome Detector

For this assignment, you will create a test driver that asks for a string from the user and processes this string in several ways. The first of these is to determine whether the string is or is not a palindrome. 

First, create a main function that accepts an arbitrary string from the user, makes a call to a recursive palindrome detecting function, and then outputs to the console whether or not the entered string is a palindrome. 

Next create a recursive function that detects whether or not a string is a palindrome. Remember to follow the appropriate steps to create a recursive implementation. What are the base cases? What is the recursive case?

For this assignment, you may use the internal string class to read a string from the user and access the string itself; however, you may not use other string functions. It is good general practice to create a class for all of your programming. Even though we are not creating an ADT this week, you should still create a class to hold your palindrome functions

Part 3:Sorting the Input

Next, we want to determine the type and order of the palindrome. Because you’ll need to find out how many characters are present from the alphabetically first character in the string, an efficient sorting mechanism is important.  
Implement a function that performs a recursive Merge Sort on the string of characters read from the user. Your textbook describes the programming details of Merge Sort in detail.
For example, if the user inputs the palindrome ‘racecar’, the output should be ‘aaccerr.’
Adjust your main program to make a call to your Merge Sort function and output the sorted string results to the console window.

Part 4:  Determining the Order and Type

Now that the string is sorted, it will be easy to determine the order and only slightly more difficult to determine the type.
Implement a function or functions to determine the type and order of the palindrome using the sorted string. Make sure you consider the Big-O run-time and space complexity of the function you are creating with respect to n, the size of the string.  
Adjust your main program to make a call to your order/type functions and output the order of the palindrome and whether it is type 1 or type 2.

Part 5:  Questions to Answer in Your Lab Write-Up

Your Labwrite-up should always contain the results of your testing, a brief explanation of how you completed the Lab, and it should detail any components that you may not have gotten working so that problems can be isolated and detailedhelp is provided to assist in your understandingandpotentially improve your grade.
In addition, please give short answers to the following questions about the Lab.
1.    What is the Big-O run-time of each of these components of the lab individually?
       a.    Palindrome detector
       b.    Merge Sort
       c.    Order and type determination
2.    What is the Big-O space complexity (memory) of each of these components of the Lab individually?
       a.    Palindrome detector
       b.    Merge Sort
       c.    Order and type determination
3.    What is the Big-O run-time of a complete program ‘loop’ that performs all functions on a user inputted string?
4.    What is the Big-O space complexity (memory) of a complete program ‘loop’ that performs all functions on a user inputted string?

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

GSP295 - Week 4 iLab

Deliverables

A single zip file including the following.

  • Your Visual Studio Project directory and associated files, including source files for the Lab.
  • The results of your testing. What tests did you run? Did everything work okay? Are there outstanding issues in your program? A short half-page summary of your results is about the right length.
  • Your answers to the Part 4 Lab Questions.

If you document any issues, it will be easier to isolate any problems, provide detailed help, and could potentially improve your grade.

Summary

It is the year 2025 and the new children’s literary masterpiece, Horacious Glump has been a huge entertainment success. You have been contracted to help create the new Horacious Glump theme park ride for a very popular theme park in Florida. You have devised an ingenious new system for park visitors to visit the new ride. In this Lab, you will design a proof of concept system to demonstrate the ingenuity.

Understanding the System

This Lab requires a bit of custom hybrid implementation; taking concepts from the textbook and implementing them but with some modification. Be sure to allocate sufficient time to complete the lab.

The new system envisioned is as follows.

  • Park visitors will register at a kiosk if they want to ride the new theme park ride.
  • Visitors will give their full names.
  • The Horacious Glump system will hash their names to a particular ride number.
  • Visitors will then be placed in the queue for the ride number.
  • At each time interval all rides will run simultaneously.
  • At the end of the ride the first person in each ride queue will be removed.
  • There will be seven rides in the system for the prototype
  • Each ride queue holds a maximum of three people for testing.

Part 1: Mapping Names

The first part of the new ride system involves mapping names to ride numbers. To accomplish this you will use a hash function to convert a string into a numerical value.

Recall that great time and care must be taken to choose a good hashing function; however, because this is merely a prototype system, you may use the simple hash function given below:

  • Implement the hash function within your Horacious Glump ride class. 
  • Create a test driver that asks for a name from the user and outputs the ride number that it maps to. 

Consider “hashValue %= hashSize” line of the hash function. What is the purpose of this line?  What would happen if it were removed?

Note: You do not need to submit this test driver function. It is merely for you to verify Part 1 functionality before moving on.

Part 2: Creating a Queue

A queuing system will be needed to complete the implementation. Using the ADT described in the textbook, implement a FIFO Queue that holds strings. For the purposes of this activity, the maximum queue size should be 3.

You will need to implement one additional operation in your queue to support your test driver:  a display function.

Note: You cannot use already existing stack and queue operations or include files. You must implement the ADT using basic data structures (arrays or linked lists).  You may, however, use your ADT list that you created earlier in the course to help you. However, your insert and delete queue operations should be O(1) so you may need to modify your list ADT.

Important: Be careful with ‘edge’ or ‘border’ cases. For example, what happens when you remove an item and no items are present? What happens if an item is added to a queue that already has the maximum elements? Your program should not break in these conditions!

Part 3: Implementing a Test Driver

Step 1) Initialize the System

Create a test driver with a main function. This driver should automatically setup the system initialization as follows.

  • Create a new hash table of size 7 for the 7 rides.
  • Create a new queue in each of the 7 hash table positions.
  • Each queue should have a maximum size of 3.

Step 2) Basic Test Commands

Create a test driver menu system similar to those for the Week 1 and Week 2 Labs. You are welcome to implement any test commands to help you verify your queue and hash table system. In addition to any of these, you are required to have the following commands.

  • Add Person
  • Prompts for person’s name
  • Hashes their name to a queue #
  • Inserts the person into the queue
  • Print a confirmation to the user
  • Be sure to output a message if the queue is full
  • Run System
  • Prints a confirmation to the user (“Ride Running…..”)
  • Removes the first person in the queue in each queue.
  • Displays the name of each rider and their queue #.
  • Be sure to output a message if a queue is empty
  • Find Length of Wait
  • Prompts for a person’s name
  • Hashes the name to a queue #
  • Outputs the current size of the queue this person would be placed in
  • Display System
  • Outputs all 7 queues in the system and for each queue the exact order that each person is within the queue
  • A simple format is sufficient, for example:

Queue #0

  • Marty Smith

Queue #1

  • Frank Jacobson
  • Roy Laop
  • Tony Ramno

Queue #2

<empty>

Queue #3

<empty>

Queue #4

  • Julie Frank
  • Bob Goldson

etc…

Part 4: Lab Questions

Consider and answer the following questions in brief in your Lab write-up.

  • Consider the last line of the hash function from Part 1. What is the purpose of this line? 
  • What would happen if it were removed?
  • Assuming it was possible to add a very large number of rides (increase the hash table size higher than the number of visitors to the park), what would be the average Big-O run-time complexity of adding a person to the system? 
  • In the large rides condition of question 2, what is the average Big-O run-time of finding the wait time for a person? 

All rides are run in parallel rather than one ride at a time (despite the opposite being true in your simulator). On a parallel system, what is the Big-O run-time in the large rides condition of question 2?

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

GSP295 - Week 5 iLab

Deliverables

A single zip file including the following.

  • Your Visual Studio Project directory and associated files, including source files for the Lab.
  • The results of your testing. What tests did you run? Did everything work okay? Are there outstanding issues in your program? A short half-page summary of your results is about the right length.
  • Your answers to the Part 6 Lab Questions.

If you document any issues, it will be easier to isolate any problems, provide detailed help, and could potentially improve your grade.

Summary

In this Lab, you will create a simple encryption scheme, also called a cipher, using the binary tree ADT. In the process of implementing binary tree operations, you will also be exposed to a common use for binary trees: encryption and data compression.

Part 1: Understanding the Problem—Encrypting a Sentence

Imagine that you are writing a secret code to your best friend that you want only the two of you to be able to understand. As luck would have it, your best friend has also taken GSP295 and has a good understanding of binary trees. You devise a scheme to encode and decode a message based on the creation of a binary tree of its letters.

To encode a sentence, insert each successive letter into a binary tree using the alphabet as a comparative measure; ‘a’ is the smallest character and ‘z’ is the largest. 

Take a simple example. To encode the sentence “meet me,” start by inserting the letters ‘m’ followed by ‘e’ followed by ‘t’ into a binary tree. In the first insertion, the binary tree is empty, so ‘m’ becomes the root node of the tree. Second, ‘e’ is inserted. Because ‘e’ is less than ‘m,’ it is placed on the left node of the ‘m’ node and becomes a leaf node. Third, a second ‘e’ is discovered. Because ‘e’ has already been inserted, the second ‘e’ does not result in any change. Lastly, ‘t’ is inserted by first comparing to ‘m’ and then placing it in the right node of the ‘m’ root node since it is greater. 

After ‘meet’ the simple binary tree looks like this:

Continue inserting all other letters of the sentence in this fashion. A ‘space’ character (and other punctuation) is considered less than the ‘a’ character. The ‘space’ character is indicated by a simple empty box. When all characters are inserted, the binary tree will look like this:

To encode the message, use a standard convention involving traversing the tree. By convention, simply assign the root node of the tree a ‘*’ character. Every other character in the tree, assign a character string based on how many ‘lefts’ and how many ‘rights’ are involved in the tree traversal. For ‘left’ traversals, use a ‘<‘, for ‘right’ traversals use a ‘>’.  In the above example, ‘e’ will be represented as ‘<‘ and ‘t’ will become ‘>’. The space character will become ‘<<’. To complete the code, every character must be separated by a marker called the delimiter. Use ‘!’ (an explanation point) as a delimiter for the code.

Using these conventions, “meet me” becomes “*!<!<!>!<<!*!<.”

Extend this example further by drawing the binary tree out on paper for “meet me at the window.” What is the full encoding for this statement?

For encryption of simple English messages, cases and punctuation do not matter. You can assume that the user will be typing letters and spaces and don’t need to worry about punctuation and special characters. The ‘space’ character will evaluate to < ‘a’. This is perfectly normal. Simply make the assumption that your alphabet has 27 characters starting with ‘space’ and ending with ‘z.’

In order to treat all letters equally, assume that capital letters and lowercase letters are the same. To do this, you can convert a user inputted string into lowercase by using the following code segment example

You can also use this code segment as a basis for understanding how to process characters individually from a string, which involves the same basic loop.

Part 2: Creating a Binary Encryption Tree ADT

Step 1: Create the ADT

A binary search tree ADT will be needed in order to complete the Lab. Using the ADT described in the textbook, implement a binary tree structure that holds characters (the key value). For the purposes of this Lab, you will not need to implement the entire ADT. You will need the following operations.

  • MakeEmpty
  • IsEmpty
  • GetItem
  • PutItem
  • DeleteItem
  • CountNodes

For all binary tree ADT operations, ensure that the binary search tree property is maintained.  The key value of any node is greater than the key value of its left child and any of its children and less than the key value of its right child and any of its children.

Further properties are not required. PutItem and DeleteItem operations do not need to ensure the binary tree is balanced. Please also note that you cannot use already existing binary tree include files or APIs. You must implement the ADT using basic data structures as outlined in your textbook in the Binary Search Trees chapter.  

Important: Be careful with ‘edge’ or ‘border’ cases. For example, what happens when you delete an item that isn’t in the tree? What happens if you get an item that isn’t in your tree? Your program should not break in these conditions!

Step 2: Modify the GetItem Operation

Now that you’ve created the binary tree ADT you need to make one critical adjustment. Change your ‘GetItem’ operation to return a string of characters consistent with the tree traversal character creation of ‘left’ and ‘right’ from Part 1. Every time GetItem traverses the tree to the right, the “>” character should be appended to the string. Every time that GetItem traverses the tree to the left, the “<” character should be appended to the string. In the end, a call to GetItem should return the complete code for the character being searched for. This can be done by changing the return type or by passing a parameter by reference. Either is sufficient.

Remember that you will need to create a special case for the root node which should return “*”.

Step 3: Add a Traverse Operation

Add a custom Traverse operation to your ADT. This operation should take a string code as a parameter and return the letter stored at the corresponding location in the binary tree.

For example, passing the Traverse operation a string of “<<<” will cause it to traverse the binary tree from the root, down the left node, down the left node of that node, and then down the left node of the resulting node. The traverse operation will then return the letter stored at that node.

Remember that you will need to create a special case for the “*” string which is the root node.

Part 3: Implementing a Test Driver

Now you are ready to create a test driver to test your new encryption and decryption program.

In order to test your system fully, please implement the following test driver commands.

  • Create Encryption Tree

The ‘Create Encryption Tree’ command forms the encryption tree from a string of characters known as the ‘key.’ Both the sender and receiver have to know the encryption key in order to both encode and decode a message. This menu command should do the following.

  • Prompt the user for a string (the encryption key)
  • Convert the string to all lowercase letters
  • Add each character in the string to the binary tree
  • Output success to the user, along with the number of nodes in the binary tree:

“Encryption Tree created successfully with 14 nodes”

You must use the CountNotes ADT operation in this command.

  • Encrypt Message

Encrypt message performs the actual message encryption by making calls to GetItem. This menu command should do the following.

  • Prompt the user for a string (the message to encrypt)
  • Convert the string to all lower case letters
  • Call GetItem from the binary tree ADT on each character in the string
  • Concatenate the codes for each character along with the delimiter
  • Output success to the user along with the encrypted message
  • For example, with the encryption key “meet me”, the message “meet me” becomes:

“Encoded String: *!<!<!>!<<!*!<”

If you are not familiar with string concatenation in C++, you can return the concatenation of two strings by simply ‘adding them’ together. For example

  • Remove Characters From a Key

One way to compress a message is to remove characters that aren’t required for its understanding. Vowels are wonderful inventions, but most of the time a message can be understood without them. Create a menu command to remove a character from the encryption key:

  • Prompt a user for a string of characters to remove
  • Convert the string to all lower case letters
  • Call DeleteItem from your binary tree ADT to remove the letters.
  • Output success to the user, along with the number of nodes in the binary tree:

“Encryption Tree modified successfully, total nodes: 12”

You must use the CountNotes ADT operation in this command.

  • Decrypt a Message

Using the binary tree and a code entered from the user, decrypt a message and output it to the user.

  • Prompt a user for an encoded message.
  • Call Traverse from your binary tree ADT on each code in the string
  • Concatenate the letters for each code character.
  • Output success to the user along with the decrypted message.
  • For example, with the encryption key “meet me” the code *!<!<!>!<<!*!< becomes:

“Decryption complete:  meet me”

You will have to pre-process the string in order to break it into string codes. Remember that each code is separated by the character “!.”

Remember to remove the “!” or ignore it from your Traverse ADT operation.

Part 4: Testing

In order for your encryption to be useful, the encrypted must be sent to someone with the same encryption key. 

Test your program by creating test cases for encryption keys and messages to encode and decode. An excellent test case to use for your encryption key is “the quick brown fox jumps over the lazy dog”. This sentence contains all the letters of the alphabet, therefore, you can test encode and decode any English sentence with it. For the purposes of exchanging encrypted messages this week, use this sentence as the encryption key.

It would be an excellent idea to test your program by communicating with your classmates via secret code on the discussion boards. Post a message to the discussion boards. Try to decrypt a code that someone else posts. Does the message make sense? 

In order to communicate with your classmates, use the encryption key: “the quick brown fox jumps over the lazy dog.”

Part 5: (Optional, Not Graded) Compression Further Study

The simple cipher is a poor example of compression because each letter converts into several characters. However, consider if instead of encoding letters, the encoding was done on words. In common conversation, only a few thousand words are commonly used in the English language. If instead of using “<” and “>,” 0 and 1 are used, and the corresponding code is converted to bit strings and a 5,000 word vocabulary can be represented in 13 bits. This is a huge savings over the average string length of a word which even at five characters is at least 10 bytes of storage. 

There are additional problems that arise with compression and placing encrypted/compressed codes adjacent to one another in storage. A common compression scheme that is easy to implement by using basic knowledge about binary trees is called Huffman Coding. C++ code is freely available in many places to implement Huffman Coding compression.  

Part 6: Lab Questions

Consider and answer the following questions in your Lab write-up.

  • Draw the binary encryption tree created for the encryption key: “meet me at the window.”
  • How many levels are in the binary encryption tree for an encryption key that contains all 26 letters of the alphabet and the ‘space’ character in the best case?
  • How many levels are in the binary encryption tree for an encryption key that contains all 26 letters of the alphabet and the ‘space’ character in the worst case?
  • What is the Big-O run-time of your program to decrypt a message in the average case in terms of the length of the encoded message? Assume the binary encryption tree is already built, the worst case scenario of binary encryption tree has not occurred, and the length of the encoded message is ‘n.’

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

GSP295 - Week 6 iLab

Deliverables

A single zip file including the following.

  • Your Visual Studio Project directory and associated files, including source files for the Lab.
  • The results of your testing. What tests did you run? Did everything work okay? Are there outstanding issues in your program?  A short half-page summary of your results is about the right length.

If you document any issues, it will be easier to isolate any problems, provide detailed help, and could potentially improve your grade.

Summary

The purpose of this week’s iLab is to implement and test a graph ADT as described in your textbook. 

Implement a Graph ADT

Implement a complete graph ADT as described in your textbook. You must have methods for all seven ADT operations described in your textbook to receive full credit. You may choose to represent your vertices as an adjacency list or an adjacency matrix.

This week’s code accesses the queue ADT that you implemented in previous weeks. When you implemented the queue ADT, you may have used string types instead of generic templates. As such, with this week’s assignments, you may again use string types instead of a generic template. This should save you some time. If for any reason you are unhappy with the state of your Queue ADT from earlier in the course, you may use the standard queue data structure referenced here:

http://www.cplusplus.com/reference/stl/queue/queue/

Hint: Your textbook uses templates and a generic VertexType structure. This is a good way to implement a generic ADT; however, it complicates the implementation and it is not required for this course. If you are comfortable with the VertexType structure and want to use it, you are welcome to. If you are not, you may change all VertextType parameters and return values to strings because the graph implementations you will test all involve strings.  

Build a Test Driver

As in previous assignments, you should create a command line menu driven test driver that allows testing of all ADT functions. You are welcome to decide how to input and output data. 

There is one addition. You must have a special command that will automatically create a graph with edges and vertices corresponding to the following example.

Design a test plan with at least two test cases and implement the test plan. One test case should be the example above. The second test case should be of your own design. You do not have to submit your test plan, but it would be a good idea to create a command or a test sequence in code to run a test sequence on your ADT similar to the requirement for test case 1.

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

GSP295 - Week 7 iLab

Deliverables

A single zip file including the following.

  • Your Visual Studio Project directory and associated files, including source files for the Lab.
  • The results of your testing. What tests did you run? Did everything work okay? Are there outstanding issues in your program? A short half-page summary of your results is about the right length.
  • Your answers to Part 5 Lab Questions.

If you document any issues, it will be easier to isolate any problems, provide detailed help, and could potentially improve your grade.

Summary

The purpose of this week’s iLab is to extend your Week 6 iLab and implement Dijkstra’s algorithm to find the shortest path and distance to all destinations from a source node in an arbitrary graph. 

Part 1:  Priority Queues

The shortest path algorithm you will implement requires selecting the smallest distance from a set of distances between two nodes that have recently been inserted. Because you are now an algorithms and data structure expert, you immediately recognize the best solution for this problem: a priority queue.

However, it is unlikely you have a Priority Queue C++ implementation laying around as none of the iLabs has asked for this implementation. In order to adding functionality for selecting the smallest path from a set of pathsm you may do any of the following. 

Please select and perform ONE of the following implementation options.

  • Implement a priority queue ADT that uses integer distances as keys and stores strings as its data item. 
  • Reuse your binary tree ADT but modify it to place items based on an integer key. Then add an ADT function to select the minimum item by recursively following the left node of the tree.
  • Reuse your ADT sorted list but modify it to sort items based on an integer key. The first element in the ADT list will then be the smallest distance.
  • Reuse your Queue ADT but modify it to insert items based on an integer key. The first element in the queue will then be the smallest distance. Notice this will have a worse run-time than 1.
  • Create a custom function to traverse a list of vertices and find the one with the smallest distance.

Think about the run-time for the Dijkstra algorithm in each of the cases listed above.

Option 1 will require significant additional implementation time, but is the best solution because it results in the lowest run-time. Options 2, 3, and 4 are best for you if you’ve written your ADTs well and are comfortable with extending them but still may require moderate additional time.

Option 5 will be the easiest to implement in most cases as you can simply do a linear search; however, option 5 results in the worst run-time performance of Dijkstra.

Any option you select will be worth full credit, providing the functionality is correct.

Part 2: Dijkstra

Implement Dijkstra’s algorithm based on the pseudo code given in lecture or your web research to find all paths and weight totals from an arbitrary graph source node. Your Dijkstra algorithm should output the shortest distance from a source node to each other node as well as output the shortest path to each node.

Part 3: Output Shortest Paths

Because you will need to output the shortest path as well as distance you will need to keep track of each node’s previous node. Note that this means you will need to return two arrays from Dijkstra—a distance array and a previous array. Therefore, you will need to create a small function that outputs values from the previous array “backwards.” 

For example, if your source node is Austin and your array positions are as indicated in the city example problem from iLab 6, the shortest path to Atlanta will be Austin->Houston->Atlanta. If in the previous array, Atlanta is at position 0, Houston at position 5, and Austin at position 1, then to output the shortest path to Atlanta you will need to output Atlanta, then previous[0], which will be 5 (Houston) and then output previous[5] which will be 1 (Austin).

Part 4: Test Driver

Your test driver should be extended from Week 6 and contain all the same commands to create a graph ADT and a command to setup the city test problem given in iLab 6. In addition, you must create a command to run Dijkstra’s algorithm on a user specified source node. You can choose the input method of the source code.

Your program must output each node’s name, the complete shortest path to that node from the source node, and the shortest path distance

For example, if the source is Austin, the first few lines of output should be of the form (order is not significant):

Houston (160):  Austin->Houston

Atlanta (960):  Austin->Houston->Atlanta

Design a test plan with at least a few test cases and implement your test plan. At least one test case should use the city example below. You do not have to submit your test plan, but it would be a good idea to verify your algorithm by testing at least a few different problems and source nodes in various graphs.

Part 5: Lab Questions

Consider and answer the following questions in your Lab write-up. Big-O of Dijkstra is calculated using V (vertices) and E (edges) rather than N.

  • Which implementation option did you select for Part 1? Why did you choose this implementation?
  • For each of the implementation options 1, 2, 3, 4, and 5 in Part 1, what is the average Big-O run-time of Dijkstra? 

General iLab Comments

All oding assignments for this class will be using Microsoft Visual Studio. This is available through the Software Store, which can be found in Course Home. Contact the help desk if you encounter any issues or contact your professor. 

*Please note as a reminder that you may not copy code from any web reference to complete this assignment, even if you correctly give credit. You may of course use web references to help you understand, but you must code the assignment yourself. You may use code directly from your textbook where applicable, but do make sure you give credit in your comments if you are doing so. 

Here is 100% correct solution for GSP295 - Week 1 2 3 4 5 6 7, All iLab 1 2 3 4 5 6 7

Solution contain Visual Studio C++ project and document answer all questions.

If you have more questions, please contact me via email support@extutorials.com

I will help you any time

Thank you very much

Attached Files

Move over [ preview ] file name to preview content in it!

Write a review

Your Name:


Your Review: Note: HTML is not translated!

Rating: Bad           Good

Enter the code in the box below:



PURCHASE SAVE
2 Tutorials 10%
3 Tutorials 13%
4 Tutorials 16%
5 Tutorials 19%
6 Tutorials 22%
7 Tutorials 25%
8 Tutorials 28%
9 Tutorials 31%
10 Tutorials 34%
add url more

9MZQASHWN73B