Description
COSC2436 hw1: String Manipulation and Filtering
1. Introduction
You will implement a C++ program to decode different string of number from the input file then filtering
out the information requested by the command file. This assignment focusses on array management and
string handling in C++. You will also learn about string manipulation with predefined string utility functions
and basic file operations.
2. Input files
– The input file will contain a list of encoded id number. The input can range anywhere from 0 to 100
entries. Input might contain empty lines and spaces (empty lines and spaces need to be removed to
process each entry correctly).
– Each entry will be on its own line and have 2 different parts, coded characters set and id string.
– The id string will consist of digits, alphabet characters, and the hash sign.
– Alphabet characters in the id string will always have a number representation for it in the characters set,
separated by a colon.
– Semicolon is used to separate characters in the set and id string.
– The id string will always come after the characters set in the entry.
– Valid entry should have all 2 parts, the characters set and the id string.
– Invalid entry should be ignored.
– Example of valid entry:
a:123;b:456;c:789;id:c11ba3#2b#a
*characters set in yellow, id string in green
– Example of invalid entry:
a:123;b:456;c:789 – missing id string
id:c11ba3#2b#a – missing characters set
3. Decoding process
Example input: a:123;b:456;c:789;id:c11ba3#2b#a
o Replace all the alphabet characters in the id string with its number representation in the
characters set.
a:123;b:456;c:789;id:c11ba3#2b#a
789114561233#2456#123
o The hash sign should be replaced by its index in the id string (after replacing all the alphabet).
The first hash sign is at index 12, and the second hash sign is at index 17
789114561233#2456#123
12 17
78911456123312245617123
4. Command files
– The command file will contain different criteria for filtering out id.
– There will be a total of two types (case sensitive): “first4” and “last4”.
o first4: those id that have its first 4 digits match with the value given in the command.
o last4: those id that have its last 4 digits match with the value given in the command.
– The criteria and its value will be separated by a colon. Ex: “first4:1234”, “last4:6789”.
– If multiple value appears for the same criteria in the command file, then as long as the id satisfy one of
those value then it should be printed to the output.
o Ex: “first4:1234”, “first4:6789” => id that have 1234 or 6789 as the first 4 digits should be
printed to the output.
– If both criteria appear in the command file, then the id must satisfy with one of the values of each
criteria in order to be in the output.
o Ex: “first4:1234”, “first4:6789”, “last4:1357”, “last4:2468” = > id that have 1234 or 6789 as the
first 4 digits and 1357 or 2468 as the last 4 digits should be printed to the output.
– Each value in the command will be on its own line, there might be empty lines and spaces.
– If the command is empty, all the valid id should be printed to the output.
5. Output files
– The output file should contain all the valid id filtered out by the command file in the order they appeared
in the input file (empty lines and spaced should be removed).
– Each entry should be on its own line.
– If there are no id that satisfy the criteria in the command file, then the output file should be empty.
6. Requirements
Homework is individual. Your homework will be automatically screened for code plagiarism against code
from the other students and code from external sources. Code that is copied from another student (for
instance, renaming variables, changing for and while loops, changing indentation, etc. will be treated as
copy) will be detected and result in ”0” in this homework. The limit is 50% similarity.
7. Turn in your homework
Homework 1 needs to be turned in to our Linux server, follow the link here
https://rizk.netlify.app/courses/cosc2430/2_resources/
Make sure to create a folder under your root directory, name it “hw1” (case sensitive), copy all your .cpp
and .h file to this folder, “ArgumentManager.h” need to be included as well.
PS: This document may have typos, if you think something illogical, please email TAs for confirmation.
COSC2430 hw2: Sorting Algorithms with Linked List
1. Introduction
Given a list of credentials as input, you will need to implement a C++ program to add these input objects
into a linked list. Within the linked list, your program needs to perform different adding, removing and
sorting operations base on the given commands. This homework will focus on linked list implementation
and simple sorting techniques. When submit your assignment, please name the folder on the server as
“hw2”.
2. Input files
– The input file will contain a list of credentials (ranging from 0 to 100).
– Each credential represents a node in the linked list and should be added one by one to the end of the
linked list.
– Each credential will have four attributes: id, username, score, and grade.
o Note: id will always contain 4 digits ranging from 0 to 9. username will always contain
lowercase alphabet character (a – z), no spaces or special character included. score will range
from 0 to 100. grade is given between A, B, C, D, and F.
– The formatting of each credential is as follow:
[id:value;username:value;score:value;grade:value]
– Valid credential should have all attributes present and appear in this order: id, username, score, grade.
o Example of valid credential:
[id:1234;username:spongebob;score:100;grade:A]
o Example of invalid credential:
[id:1234;username:steve;grade:C] – missing attribute: score
[id:1234;grade:B;score:85;username:batman] – out of order
– Invalid credential should be ignored.
– The input will not contain any empty lines or blank spaces.
– In the case when the input is empty, continue to process the command.
– While reading the input, \n and \r should be removed before processing string.
– Input might contain duplicate id credential or duplicate username credential, please read section 5 below
on how to process duplicate cases.
3. Command files
– There will be three types of command: Add, Remove, and Sort. The commands should be executed in
the order that they appear (latter command should always run based on the former command’s result).
o Add (index) [credential]
▪ The Add command will be followed by an integer inside parenthesis (represent the index
in the linked list to be added) and then followed by a credential.
▪ If index = 0, meaning the credential should be added at the beginning of the linked list.
▪ If the index = size of the linked list, meaning the credential should be added at the end of
the linked list.
▪ If the index > size of the linked list, meaning index out of bound, in this case the
credential should not be added to the linked list.
▪ Ex: Add (0) [id:1234;username:tom;score:50;grade:F]
add this credential at the beginning of the list
▪ Ex: Add (3) [id:1234;username:tom;score:50;grade:F]
add this credential at the third index of the list, if not out of bound
▪ Add command might contain duplicate id credential or duplicate username credential,
please read section 5 below on how to process duplicate cases.
o Remove (attribute:value)
▪ The Remove command will be followed by an attribute and its value (placed inside
parenthesis).
▪ Every credential that contains the attribute with the matching value should be removed
from the linked list.
▪ Ex: Remove [grade:C]
remove every credential that contain value “C” in attribute “grade”.
o Sort (attribute)
▪ Sort the linked list base on the given attribute (placed inside parenthesis).
▪ Sort ascending for id.
▪ Sort alphabetically for username and grade.
▪ Sort descending for score.
▪ When sorting if two values are similar, don’t swap their position.
– The command will not contain any empty lines or blank spaces.
– While reading the command, \n and \r should be removed before processing string.
4. Output files
– The output file should display every credential in your linked list after executing all the command in the
command file.
– Each credential will be on its own line.
5. Adding Operations
– When adding a credential to the linked list, the credential might contain duplicate id or duplicate
username.
– In the case when the credential contains duplicate id, update the previous credential’s attributes with the
new credential’s attributes.
o Ex: If the credential [id:2468;username:onion;score:75;grade:C] is in the
linked list when adding [id:2468;username:lettuce;score:50;grade:F],
since the two credential have matching id, update the username, score, and grade of the
credential in the linked list to the latter credential. The username for id:2468 should be updated
to lettuce, the score should be updated to 50, and the grade should be updated to F.
– In the case when the credential contains duplicate username (but doesn’t have matching id), the
credential should be ignored and not to be added to the linked list.
– When adding from both the input and command files, always check if the credential has all the attributes
present and following the order of id, username, score, grade. Invalid credential should be ignored.
6. Requirements
Homework is individual. Your homework will be automatically screened for code plagiarism against code
from the other students and code from external sources. Code that is copied from another student (for
instance, renaming variables, changing for and while loops, changing indentation, etc. will be treated as
copy) will be detected and result in ”0” in this homework. The limit is 50% similarity.
7. Turn in your homework
Homework 2 needs to be turned in to our Linux server, follow the link here
https://rizk.netlify.app/courses/cosc2430/2_resources/
Make sure to create a folder under your root directory, name it “hw2” (case sensitive), copy all your .cpp
and .h file to this folder, “ArgumentManager.h” need to be included as well.
PS: This document may have typos, if you think something illogical, please email TAs for confirmation.
COSC2430 hw3: Finding the Smallest Sequence
1. Introduction
Given a matrix as input, you will need to implement a C++ program to play a mini game and find the
smallest sequence that will solve the matrix. This homework will focus on stack and queue
implementation. When submit your assignment, please name the folder on the server as “hw3”.
2. Input files
– The first line in the input will contain two integer row and col, indicate the size of the given matrix.
– The rest of the input will contain the matrix that need to be solved.
– Each element will be separated by a space.
– There will be no redundant spaces or empty lines.
– There will be no empty input.
3. Operations
– There are four operation that need to be considered when solving the matrix:
o Shift up: shift all the elements in the matrix upward (corresponding to 1)
o Shift right: shift all the elements in the matrix to the right (corresponding to 2)
o Shift down: shift all the elements in the matrix downward (corresponding to 3)
o Shift left: shift all the elements in the matrix to the left (corresponding to 4)
– Elements in the matrix will either be ‘O’, ‘X’, or ‘B’.
o ‘O’ will represent an open path in the matrix.
o ‘X’ will act as a barrier when shifting the matrix.
o ‘B’ will represent a bomb that need to be detonate.
– In order to solve the matrix, all the bomb (B) in the matrix will need to be detonated.
– To detonate a bomb, they need to collide into another bomb by shifting the matrix up, right, down, or
left. Which two bomb collided first will be detonated.
– The matrix will always have even number of bomb (B).
– When two bomb detonated, a barrier (X) will be created at the index of detonation.
o Ex: Shift up
When shifting up, the bomb (B) marked in red collided and detonated, created two barriers (X).
O B O O
O O B O
O B O O
B B B O
B X X O
O B O O
O O O O
O O O O
– When shifting the matrix, all the barrier (X) will be stationary and will not shift.
– A bomb (B) will stop shifting when it meets a barrier (X).
o Ex: Shift right
4. Output files
– Output the sequence of moves that detonate all the bomb and solve the matrix.
– If there are multiple sequence that solve the matrix (ex: 124, 211, 3214), output the smallest one.
– If the matrix is already solved without any moves, output “0” for the sequence.
5. Example
– Input1: the moves sequence to solve the matrix is 12 (shift up then shift right)
Given
O O O B O
B O O O O
O B O O O
O O O O B
Shift up
B B O B B
O O O O O
O O O O O
O O O O O
Shift right
O O O X X
O O O O O
O O O O O
O O O O O
O O O O
B O X O
B B X O
B O O O
O O O O
O B X O
O X X O
O O O B
– Input2: the moves sequence to solve the matrix is 141 (up, left, up)
Given
O O O B O
X B O O O
O X O O O
B O X O B
O B O O O
O O O O B
Shift up
O B O B X
X O O O O
B X O O O
O B X O O
O O O O O
O O O O O
Shift left
X O O O X
X O O O O
B X O O O
B O X O O
O O O O O
O O O O O
Shift up
X O O O X
X O O O O
X X O O O
O O X O O
O O O O O
O O O O O
– Input3: the moves sequence to solve the matrix is 1341 (up, down, left, up)
Given
O O O B O X X O O O
X B O O O O O O X O
O O O O X O O O B O
B O X O B O O X O B
O O B O X O O O O O
O O X O O O B O B O
O O O O B O X O O X
B O X O O O O B O O
O O O O B O O O X O
O X O O B O O O O X
Shift up
O B O B O X X O O B
X O O O O O B O X O
X O O O X O O O X O
O O X O B O O X O O
O O B O X O O B O O
O O X O X O O O O O
O O O O B O X O O X
O O X O O O O O O O
O O O O O O O O X O
O X O O O O O O O X
Shift down
O O O O O X X O O O
X O O O O O O O X O
X O O O X O O O X O
O O X O B O O X O O
O O B O X O O O O O
O O X O X O B O O B
O O O O O O X O O X
O O X O O O O O O O
O B O O O O O O X O
O X O B B O O B O X
Shift left
O O O O O X X O O O
X O O O O O O O X O
X O O O X O O O X O
O O X B O O O X O O
B O O O X O O O O O
O O X O X X O O O O
O O O O O O X O O X
O O X O O O O O O O
B O O O O O O O X O
O X X B O O O O O X
Shift up
O O O X O X X O O O
X O O O O O O O X O
X O O O X O O O X O
X O X O O O O X O O
O O O O X O O O O O
O O X O X X O O O O
O O O O O O X O O X
O O X O O O O O O O
O O O O O O O O X O
O X X O O O O O O X
6. Requirements
Homework is individual. Your homework will be automatically screened for code plagiarism against code
from the other students and code from external sources. Code that is copied from another student (for
instance, renaming variables, changing for and while loops, changing indentation, etc. will be treated as
copy) will be detected and result in ”0” in this homework. The limit is 50% similarity.
7. Turn in your homework
Homework 3 needs to be turned in to our Linux server, follow the link here
https://rizk.netlify.app/courses/cosc2430/2_resources/
Make sure to create a folder under your root directory, name it “hw3” (case sensitive), copy all your .cpp
and .h file to this folder, “ArgumentManager.h” need to be included as well.
PS: This document may have typos, if you think something illogical, please email TAs for confirmation.
COSC2436 hw4: Priority Queue and BST
1. Introduction
In this homework you will implement a C++ program that can decode messages by taking in
commands and organizing them based on their priority.
Given a few strings containing random characters and a list of instructions for how to decode the
messages. The instructions are out of order and a priority queue must be used to initiate the commands in
the proper order. When every command is put into the priority queue in the correct order and each
command is performed then the program will decode a message.
You will also need to build a binary search tree from the list of messages and traverse them.
2. Input files
The input will contain a series of commands, each command will be put into a priority queue.
Each command is case sensitive. There are 6 possible commands:
● DECODE: which will be followed by an encoded message inside of brackets
○ Ex: DECODE:[dsacd# dsafdw](2)
○ This will add a string to be decoded to a second queue that contains the messages
● REPLACE: which will contain two characters separated by a comma inside of brackets
○ Ex: REPLACE:[s,e](6)
○ Original string: slsphant
○ new string: elephant
○ This will replace all character ‘s’ to character ‘e’ in the front string of the message queue
and then move that message to the end of the message queue
○ Has a priority of 6
● ADD: which will contain two characters separated by a comma inside of brackets
○ Ex: ADD:[n,a](4)
○ original string: bann
○ New string: banana
○ This will add an ‘a’ after every ‘n’ in the front string of the message queue and then move
that message to the end of the message queue
○ And has a priority of 4
● REMOVE: which will contain a single character inside of brackets
○ Ex: REMOVE:[v](5)
○ Original string: mevssvavge
○ New string: message
○ This will remove every ‘v’ in the front string of the message queue and then move that
message to the end of the message queue
○ Has a priority of 5
● SWAP: which will contain two characters separated by a comma inside of brackets
○ Ex: SWAP:[n,a](8)
○ Original string: bnanan
○ New string: banana
○ This will turn every ‘n’ into an ‘a’ and every ‘a’ into an ‘n’; in the front string of the
message queue and then move that message to the end of the message queue
○ Has a priority of 8
● BST:
○ Ex: BST:(4)
○ This will insert the message at the front of the message queue into the BST, and take it out
of the message queue.
○ Left and Right child will be based on the length of the message that is being inserted.
Shorter length will go left, longer length will go right.
○ If the message that is being inserted have equal length to one of the nodes in the tree,
replace that node’s data with the message that is being inserted.
The last line in the input will either be “Preorder”, “Inorder”, or “Postorder” (case sensitive) which
indicate the traversal method for BST.
In this program there are two queues that must be used:
1. A priority queue that takes in every command sorting them based on priority.
If two command share the same priority, then the first one to enqueue goes first.
2. A regular queue that takes in the messages provided by the DECODE command.
Every command besides the DECODE command will affect the front of the regular queue filled with
messages, modify the string, and then move that string to the back of the queue. So if there are two
strings in the normal queue then they will be affected by every other command.
If the message queue is empty and you are given any command other than DECODE then nothing should
happen.
The characters given in the ADD, REPLACE, REMOVE, or SWAP command are case sensitive.
3. Output files
Print the BST base on the traversal method given in the last line of the input.
Each node will be on its own line.
If input is empty, output should be empty.
4. Requirements
Homework is individual. Your homework will be automatically screened for code plagiarism against code
from the other students and code from external sources. Code that is copied from another student (for
instance, renaming variables, changing for and while loops, changing indentation, etc. will be treated as
copy) will be detected and result in ”0” in this homework. The limit is 50% similarity.
5. Turn in your homework
Homework 4 needs to be turned in to our Linux server, follow the link here
https://rizk.netlify.app/courses/cosc2430/2_resources/
Make sure to create a folder under your root directory, name it “hw4” (case sensitive), copy all your .cpp
and .h file to this folder, “ArgumentManager.h” need to be included as well.
PS: This document may have typos, if you think something illogical, please email TAs for confirmation.
COSC2430 Homework 5: Tree
1. Introduction
You will create a C++ program to implement the B-Tree. The purpose of this homework
is to let students be familiar with the B-Tree.
2. Input and Output
a. Input file
All values that will be added to the tree separated by a space, tab, or new line.
Values will be positive.
b. Command file
Degree of the tree: Degree=value
Level to print: Level value
c. Output file
The output is a single text file.
Height of the tree and list of the numbers on the specified levels.
If the level is empty, print Empty.
d. Examples
i. Example 1
input1.txt
55 60 72
command1.txt
Degree=3
Level 2
output1.txt
Height=2
55 72
ii. Example 2
input2.txt
13 28 1 32 81
17 72 70 77 58
51 24 25 5 55
68 24 28 8 19
15 40 91 17 37
10 20 4 33 21
command2.txt
Degree=4
Level 10
Level 9
Level 2
Level 2
Level 1
Level 3
output2.txt
Height=3
Empty
Empty
5 19 21 33 70 77
5 19 21 33 70 77
13 28 51
1 4 8 10 15 17 20 24 25 32 37 40 55 58 68 72 81 91
iii. Example 3
input3.txt
228 72 177 9 284 1 169 263 237 63
22 148 114 183 98 149 232 100 54 236
command3.txt
Degree=4
Level 3
output3.txt
Height=3
1 22 54 63 98 100 148 149 169 183 232 236 263 284
3. Requirements
Please create the BTree manually.
The main C++ problem will become the executable to be tested by the TAs. The result
file should be written to another text file (output file), provided with the command line.
Homework is individual. Your homework will be automatically screened for code
plagiarism against code from the other students and code from external sources. Code
that is copied from another student (for instance, renaming variables, changing for and
while loops, changing indentation, etc, will be treated as copy) will be detected and result
in ”0” in this homework. The limit is 50% similarity. Here are some previous homework
which have been found to copy each other (the main function has been deleted).
4. Turn in your homework
Homework 5 needs to be turned in to our Linux server, follow the link here
https://rizk.netlify.app/courses/cosc2430/2_resources/
Make sure to create a folder under your root directory, name it “hw5” (case sensitive),
copy all your .cpp and .h file to this folder, “ArgumentManager.h” need to be included as
well.
PS: This document may have typos, if you think something illogical, please email TAs for
confirmation.
