Description

CSIS 215 Programming Assignment 1 – Bag-based Dictionary

Implement a dictionary using a Bag—Project 4.7 in the text (modified)

Use the bag ADT provided to create an array-based implementation for bags.  Then use your bag to implement the dictionary ADT provided you.  This means you have to implement your dictionary using the bag functions.

Test your bag and dictionary implementations with the bagtestmain.cpp file I’ve provided for you.  If you are not able to fully implement all the functions of the dictionary and/or bag, you may modify the tests in bagtestmain.cpp to only exercise those functions you were able to complete.

You will only get credit for those methods you test and display, so be sure you don’t leave any out.

Also, you cannot add any public functions to your bag and dictionary implementations beyond those specified in the ADTs, though you may add private functions if you want.

Put the following files into a zip file named student_name_Bag_Assignment and submit them to Blackboard:

• h                 // Your bag-array implementation which must inherit the Bag class
• h // Your Dictionary-bag implementationwhich must inherit the                                                                    // Dictionary class
• cpp // The test driver I have provided for you
• h // The bag ADT I gave you – it should be unchanged
• h // The dictionaryADT I gave you – it should be unchanged
• h // The kvpair class I gave you – it should be unchanged
• Screen Shots                 // Word document with screen shot(s) and integrity statements showing
  // all of your program’s output.
  doc                    // This is a Word document where you explain how you implemented
  // your solution and how you tested each required function.
• Any other .cpp and/or .h files that comprise your project (I need all the .cpp and .h files used in your project).
• exe //Your executable file.***

Note: If your ABag does not inherit Bag and/or BDictionary does not inherit Dictionary, you will not receive any credit for your work. If you use the templates I’ve provided (ABag.h and BDictionary.h) the inheritance is already done for you.

*** If you completed your assignment using Visual Studios you must use Visual Studios 2017 and I would like you to submit your entire VS project directory.

Your test program must exercise every function of the dictionary.  For any function whose functionality is not obvious you must explain in your Word document how your test output demonstrates that function.   See me if you have questions.

See Blackboard for the assignment due date and the syllabus for the late policy.

Rubrics (for the 70% content portion):

• Program must run in order to get any points. By “run” I mean that you must at least get one or more of the bag methods working (and your program must demonstrate that functionality).

Tips for Success

Start by working on your “Approach” first.  Once you are satisfied with your approach, then start building your program incrementally.  Start with the bag and increment one feature at a time (you’ll have to stub out the features the ADT requires that you are not ready to implement yet) starting with the constructors and then working your way down the feature list using common sense to figure out which features need to be implemented first.  Try your bag out with the various parameter combinations I want you to test with (<int, string> and <string, int>).  When you are satisfied the bag is working then move on to the dictionary, again implementing and testing function by function.

Don’t wait until the last minute.  You’ll find that many of your problems you will solve while you are away from your computer and have a chance to think about the error you are seeing.  This takes time.

Note:  KVpair, which uses the == operator for comparing the key values, will only accept objects that have also implemented the == operator.  This class has been tested with the following types:

• string
• int

It specifically does not work with the Int type (at least not in the version of C++ I am working with).

Debugging your code

A big part of this assignment is debugging your code, so do not expect your instructor to do this for you.  Having completed the pre-requisite courses for this class, you should already have some experience finding coding errors and fixing them.  This class will give you plenty of opportunities to further refine those skills and you can only do that by wrestling with the problem.  Here are some debugging tips:

• Build a little, test a little. Don’t write all your code before you start debugging it.  Break your work into logical chunks that can be compiled and debugged and build them one at a time. For this project, I would start by building the Bag class and implementing the addItem() function first.  Once I get that function working properly, then I would move on to another Bag function.  The idea is you build and test a function one function at a time.  That way, if you run into an error, you know where to look.
• Learn to use the debugger if you haven’t already. The debugger allows you to step through your code one step and a time and see what happens in memory while you’re doing it.  When students come to me with problems, I first try to isolate where the problem is logically based on what the program is doing and then I use the debugger to find the actual fault.  Here is an excellent video tutorial on the Visual Studios debugger:  How to DEBUG C++ in VISUAL STUDIO.
• Be willing to walk away from your computer and give your mind a rest. I find that the solution to a problem often comes to me while I am doing something else.  I have never regretted stepping away from my computer to let the problem “percolate” in my mind, but I have often regretted not doing this.  This is one of the reasons you should never wait till the last minute to start working on your program; by doing that you are not giving yourself the time to walk away.

CSIS 215 Programming Assignment 2 Double-Threaded Binary Tree

Implement a Double-Threaded Binary Tree and add in-order and reverse-order printing without resorting to recursion—Project 5.2 in the text

Using the following supplied C++ files implement a right and left threaded binary search tree(see https://algorithms.tutorialhorizon.com/double-threaded-binary-tree-complete-implementation/ for more information on doubly threaded BSTs).  The files provided to you come from our text, with some minor modifications, and implement a BST based dictionary.  You must modify this BST-based dictionary to implement a threaded BST.  Specifically, you will need to make the following modifications:

• h
  • Add Boolean instance variables to indicate whether a node pointer is a thread or regular pointer.You may not add any additional pointers to BSTNode. The whole idea of threads is that they take advantage of unused BSTNode pointers and thereby reduce the binary tree’s wasted overhead.
  • Add setter/getter methods to access the Boolean instance variables or modify existing setters/getters as necessary.
• h
  • Rewrite method inserthelp() to take advantage of the modified BSTNode in which a pointer can be either a regular pointer or a thread.
  • Modify method printhelp() to work with threaded nodes.
  • Add method printInorder() to do an inorder printing of your tree without the use of recursion.
  • Add printReverse() to do a reverse order printing of your tree without resorting to recursion.
  • You may add private helper methods as needed to make modifying or creating the methods above easier.
  • Note: I’ve commented out the destructor since the destructor relies on clearhelp() and clearhelp(), as currently written, won’t work with threaded trees.
  • Note: You do not have to implement any of the functions I’ve removed or deleted. Only the functions I’ve specified above, along with any private helper functions you need, must be implemented.
• Approach – in a Word document explain your implementation approach. Tell me how you plan to accomplish this assignment. Tell me where in your source files (source file names and method/function names) I can look to see your implementation.  Use methods printhelp, printInorder, andprintReverseto demonstrate your program in action.  Include screen shots of your program’s output.
• Since the BST node takes a key value pair I want you to insert the following <int, string> values (in the order provided) to build your tree.
  • 77, “seventy-seven”
  • 70, “seventy”
  • 75, “seventy-five”
  • 66, “sixty-six”
  • 79, “seventy-nine”
  • 68, “sixty-eight”
  • 67, “sixty-seven”
  • 69, “sixty-nine”
  • 90, “ninety”
  • 85, “eighty-five”
  • 83, “eighty-three”
  • 87, “eighty-seven”
  • 65, “sixty-five”

Files provided:

• h
• h
• h
• h

Assignment Submission:

Put the following files into a zip file and submit your assignment to the assignment link in Blackboard:

• Your Visual Studios entire project file. At the absolute minimum I need all your .cpp and .h files.  If I cannot build your project with the files you give me, you will not receive any credit for your work.
• Word document describing your approach to solving this problem.
• Word document with screen shots (of your entire test run) with integrity statements. You only get credit for the functions you have demonstrated work.  Be sure that the output in your screen shots is clear enough that I know exactly which functions are being tested, and that you explain the results in such a way that the test results are clear.  This BST uses templates <Key, E>.  For your test run use the following key/value pair type combination: <int, string>.

Here is an example of my test run showing both printhelp, printInorder, and printReverse:

Put all your files into a single zip file and submit it to Blackboard.

Rubrics:

• Program must run in order to get any points. By run I mean you must at minimum:
  • Implement successor threads, and demonstrate them.
  • In-order printing without using recursion.

If you look at the standard rubrics, the content portion is worth 70% or 87.5 points out of 125.  The rubrics for the content portion of this assignment are:

Tips

This is a deceptively challenging project.  Do not wait until the last minute to start working on it or you will go crazy (and probably not succeed in finishing your project).  I recommend that you start with your Word document and describe your implementation approach and then use that to guide your actual implementation.

Break the project into pieces and think about how you are going to accomplish each piece.  Start by getting the BST files I’ve given you running before making any changes to themand be sure you understand how the author has implemented his BST.  Then add your Booleaninstance variables to the BSTNode.hfile and implement your setter/getter methods for your threads.

Next start thinking about inserthelp.  You pretty much have to gut the entire method and start from scratch.  Think about node states and how each state affects the insert operation.  For example the state of root when it is the only node in the tree is left and right child equal NULL.  How will you add a node to root and implement your successor and predecessor pointers?  Now look at the state of the second node.  How is it different from the state root was in, and how does that change future insertions?  For me it helps drawing the tree out as I build it, so that I can visualize what it is I am attempting to do.

Debugging your code

A big part of this assignment is debugging your code, so do not expect your instructor to do this for you.  Having completed the pre-requisite courses for this class, you should already have some experience finding coding errors and fixing them.  This class will give you plenty of opportunities to further refine those skills and you can only do that by wrestling with the problem.  Here are some debugging tips:

• Build a little, test a little. Don’t write all your code before you start debugging it.  Break your work into logical chunks that can be compiled and debugged and build them one at a time. For this project, I would start by compiling and running the files I’ve given you before you make any changes.  Then build your threaded tree a node at a time by modifying inserthelp and BinNode as necessary and use the debugger to determine whether or not your pointers and threads are being correctly applied.
• Learn to use the debugger if you haven’t already. The debugger allows you to step through your code one step and a time and see what happens in memory while you’re doing it.  When students come to me with problems, I first try to isolate where the problem is logically based on what the program is doing and then I use the debugger to find the actual fault.  Here is an excellent video tutorial on the Visual Studios debugger:  How to DEBUG C++ in VISUAL STUDIO.
• Be willing to walk away from your computer and give your mind a rest. I find that the solution to a problem often comes to me while I am doing something else.  I have never regretted stepping away from my computer to let the problem “percolate” in my mind, but I have often regretted not doing this.  This is one of the reasons you should never wait till the last minute to start working on your program; by doing that you are not giving yourself the time to walk away.

Make sure you take full advantage of the debugger in your development environment.  Debuggers are invaluable for examining the state of pointers and variables as they make their way through the program.

CSIS 215 Programming Assignment 3 LRU Buffer Pool

Implement a disk-based buffer pool class based on the LRU buffer pool replacement strategy.

Implement and demonstrate a disk-based buffer pool class based on the LRU buffer pool replacement strategy. Disk blocks are numbered consecutively from the beginning of the file with the first block numbered as 0. Assume that blocks are 4096 bytes in size. Use the supplied C++ files to implement your LRU Buffer Pool based on the instructions below.

• Implement a BufferBlock class using the supplied BufferBlockADT.h
  • Your Buffer Block must inherit BufferBlockADT or you will not get credit for your work.
  • All BufferBlockADT virtual functions must be implemented in BufferBlock

• Block Size: 4096 bytes
• Add an instance variable to your buffer block implementation to store the block id; i.e., “int blockID.”

• Implement a Buffer Pool by inheriting BufferPoolADT (BufferPoolADT.h) – implement all of BufferPoolADT’s functions (if you do not inherit BufferPoolADT you will not get credit for your work).

• Your buffer pool should consist of 5 buffer blocks
• Your buffer pool should manage the buffers using the LRU strategy
• Your buffer pool should be named LRUBufferPool and the file containing the LRUBufferPool class should be named LRUBufferPool.h

• Use the provided main.cpp and the included test file mydatafile.txt to test your program.

File Provided:

• BufferBlockADT.h
• BufferPoolADT.h
• constants.h  (contains both constants and test function definitions)
• main.cpp  (test program driver)
• mydatafile.txt (input file for the test run)
• Buffer Pool Output.txt – if your program is correct your output should look like this

Note:  You must open the input file in binary mode for the read() and seekg() methods to work properly.  See example code below.

Testing

Use main.cpp as the test driver and mydatafile.txt as the input file.

Assignment Submission:

Put the following files into a zip file and submit your assignment to the assignment link in Blackboard:

• All your source code files (.cpp and .h files), including the files provided for the assignment.  Note that none of the files that have been provided can be changed (depending on how you created your project in Visual Studios you may need to add #include “stdafx.h” to main.cpp to get it to compile, which is a permitted change).
• If you used Visual Studios to build your project, please give me your entire project folder.
• Word document describing your approach to solving this problem.
• Word document with screen shots showing results of your test run (I need to see the entire run, so give me as many screen shots as necessary) and integrity statements.
• Executable file (.exe file).

Put all your source files, test files, executable, and Word document(s) into a zip file and submit it to Blackboard.

Rubrics:

• Your program must run and correctly implement and demonstrate getData() in order to get any points at all. The rubric below constitutes the 70% content portion of LU’s standard rubrics.

CSIS 215 Programming Assignment 4.Self-Organizing Lists Assignment

Implement the three self-organizing list heuristics:

• Count – Whenever a record is accessed it may move toward the front of the list if its number of accesses becomes greater than the record(s) in front of it.
• Move-to-front – Whenever a record is accessed it is moved to the front of the list. This heuristic only works well with linked-lists; because, in arrays the cost of shifting all the records down one spot every time you move a record to the front is too expensive.
• Transpose – whenever the record is accessed swap it with the record immediately in front of it.

Compare the cost of each heuristic by keeping track of the number of compares required when searching the list.

Additional Instructions

Use the SelfOrderedListADT abstract data type and the linked-list files I have provided to implement your self-ordered lists. You may incorporate the author’s linked list implementation via inheritance or composition, which ever makes the most sense to you (I will not evaluate that aspect of your implementation).  You are allowed to make changes to any of the files I have provided, except SelfOrderedListADT and test.txt, to make your implementation of SelfOrderedListADT cleaner.  The same applies to the link.h (the link node implementation).  You may not change SelfOrderedListADT or test.txt files.

I want you to run two tests

1. The first test is with char types. Use the add() function to build a list in the following order: A B C D E F G H (do not add ‘I’ here).  After you have built that initial list I want you to use the find function to input the following characters:  F D F G E G F A D F G E H I (note that ‘I’ is not in the initial list; I want to see what your program does when it searches for an item that is not already in the list).  For each heuristic display the order of the final list and the number of compares.
2. The second test is using the test.txt file I have provided using the data type string. Do not modify the test text file; because, I am going to compare your results with my own and modifying the test file will throw your results off.  For this test I want you to do the following for each heuristic:
   1. Read into your program the test.txt fileadding words to your list using your find() function, and then
   2. Print out
      1. the total number of words in your list,
      2. the total number of compares, and

• the first 10 words in your list along with their frequency.

Here is a sample of a test run using strings (this sample was not run using the test file I’ve assigned you, so the values you see are not the same as those you should be seeing):

Make sure that you give me enough screen shots so that I can see your entire run. You will be penalized if you do not.

SelfOrderedListADT Functions:

1. find() – finds a value in the list and, if found, increments the frequency. If not found then find() calls add() to append the value to the end of the list (initial frequency of an item added this way is 0).  In either case find() calls your reorder function (see below) to reorder the list in accordance to the heuristic being used and find() increments the number of compares made (whereas add() (see below) does not).
2. add – appends the value to the end of the list without doing any compares or adjusting frequencies.
3. getCompares – returns the total number of compares done by find when searching for values in the list.
4. Size – returns the size of the list.
5. printlist – prints the list in the following format: value-## where “value” is the actual value of the node (either a char or a string) and ## is the frequency of that value. You will need a printlist() and a printlist(n) method because for your char tests you will print the entire list but for the string test I only want the first 10 nodes printed.
6. reorder – you can call this method whatever you want but what I am looking for is a method or methods that reorders your list as appropriate based on the heuristic you are using. This method is typically called by find().

Submit

To receive credit for this assignment you must submit the following files in a zip file to Blackboard:

• Word document describing your approach and calling out changes you made to any of the files I have given you.
• All project .cpp and .h files
• Your executable file
• Word document with screen shots and integrity statements

Rubrics

To earn any credit at all you must submit a working program that implements and demonstrates at least one of the heuristics.  You must also include all the files I asked for above or you will not receive any credit.  You must also use the SelfOrderedListADT I have provided (unchanged) by establishing an inheritance relationship between your self-ordered list(s) and the ADT.  Failure to do so will disqualify your project and you will not receive any credit for it.

The rubrics below reflect just the content portion of the assignment rubrics (70% of the total point value of 125 points).