Although arrays are used extensively in this class, they suffer from a major problem in that you, as the programmer, need to know in advance the number of elements required by your program. There are many situations, where this information is not available (e.g., reading lines from a file, where the number of lines is not given to you in advance) and you have to dynamically increase the size of your arrays. Although there are different ways of achieving this dynamical increase, the most popular is to implement a Linked List. A Linked List is simply a set of nodes, where each node is composed of a value (the value of the element) and a pointer that points to the next node. Using the pointer methodology allows the programmer to create new nodes by using the new keyword. In this lab, we will implement a Linked List as a class (the class declaration (.h file) is given on CatCourses) and make sure it works (using two main files provided on CatCourses). Getting started Create a new directory in your main development directory (probably on Desktop/CSE30) called Lab_8. Try to use the terminal on your own, without getting help from the TA to setup the new directories (try to learn/remember the terminal commands). The g++ syntax to compile classes is slightly different than for a single program comprised of a main (and potential functions): g++ class1.h class1.cpp class2.h class2.cpp mainSource.cpp -o executable where: g++ is the compiler (installed on your Linux system) of C++ source files, mainSource.cpp is the source file for your main program (main function), class1.h is the class declaration for your 1st class, class1.cpp is your 1st class definition, class2.h is the class declaration for your 2nd class, class2.cpp is your 2nd class definition (and so on…), -o tells the compiler that you want to give the executable its own name, and executable is the name you want to give your program. As an example, if we have a main source file called Exercise1.cpp, the class declaration called LinkedList.h, the class definition called LinkedList.cpp, and want to create an executable called aTestProgram, you would type: g++ LinkedList.h LinkedList.cpp Exercise1.cpp -o aTestProgram Assuming that your program compiled successfully (i.e. no errors were found), you can run your program as you normally would by typing “./aTestProgram” in the terminal/console. Good coding practices (worth 2 points!) Writing code that is understandable by humans is as important as being correct for compilers. Writing good code will help you complete the code, debug it and … get good grades. It is very important to learn as soon as possible, because bad habits are hard to get rid of and good habits become effortless. Someone (guess who) reads your code will be in a better mood if it is easy to understand … leading to better grades! This lab will include 2 points (10% for code quality): Explanations with comments Meaningful names Indenting of blocks { } and nesting … Proper use of spaces, parentheses, etc. to Visible, clear logic One / simple statements per line Anything that keeps your style consistent (Exercise 1) In this part of the lab, you will be implementing the basic functions for a Linked List, which are provided in the class declaration LinkedList.h (on CatCourses ). In other words, you have to create and implement the class implementation in a file called LinkedList.cpp. The main file you have to use for this lab is also provided on CatCourses (Exercise1.cpp). DO NOT modify the class declaration (LinkedList.h) or main file (Exercise1.cpp). Looking at the class declaration, you will find that a Node is defined as a structure comprised of a value (val, of type int) and a pointer to the next node (next, of type Node pointer). You will also notice (under private) that you will be keeping track of your Linked List using two Node pointers, first and last. The first pointer should always point to the first element of your Linked List and the last pointer should always point to the last element of your Linked List. If the Linked List is empty, the first and last pointers should both point to NULL. If there is only one element in your Linked List, both first and last will point to that element. In this part of the lab, you will need to implement the following functions for the LinkedList class: Default Constructor: initializes the first and last variables, the list is empty. Destructor: deletes the entire Linked List, if not already empty. insertAtBack(int): inserts a new element (i.e., a new Node) at the end of the list. removeFromBack(): removes the last element of the list. The function should return true if an element was successfully removed and false otherwise. print(): prints the entire list. See the example below for the format when printing the list. isEmpty(): returns whether or not the list is empty (true if it is empty, false otherwise). size(): returns the size of the list. You will need to navigate through the entire list and count how many elements are in the list. clear(): same function as the Destructor, deletes the entire list if not already empty. Note: a pointer does not point to anything unless you 1) use the reference operator (&) in front of a variable, 2) you dynamically allocate memory for it (using the new operator), or 3) you assign it (set its value to) to another pointer every time you want to create a node, you will have to use the new operator every time you allocate memory dynamically for a pointer using the new keyword, you have to make sure that you de-allocate the memory once you do not need the data anymore. This can be done using delete (in the destructor, clear and remove functions). Example: The first list is empty! The second list is empty! The size of the first list is: 0 The size of the second list is: 0 Here is the first list: [1,2,3,4,5] Here is the second list: [] Here is the first list: [1,2,3,4,5] Here is the second list: [25] Here is the first list: [1,2,3,4] Here is the second list: [] Here is the first list: [] Here is the second list: [-5,0,5,10] The size of the first list is: 0 The size of the second list is: 4 The first list is empty! The second list is NOT empty… Here is the second list: [-5,0,5,10] Successfully removed an item from the list… Here is the second list: [-5,0,5] Successfully removed an item from the list… Here is the second list: [-5,0] Successfully removed an item from the list… Here is the second list: [-5] Successfully removed an item from the list… Here is the second list: [] COULD NOT remove an item from the list! Here is the second list: [] COULD NOT remove an item from the list! The size of the first list is: 0 The size of the second list is: 0 The first list is empty! The second list is empty! (Exercise 2) In this part of the lab, you will finish implementing your Linked List by implementing two more functions. You should use a new main file (Exercise2.cpp), which you can find on CatCourses . Again, DO NOT modify the class declaration (LinkedList.h) or main file (Exercise2.cpp). The two new functions are as follows (use your LinkedList.cpp file from Exercise 1, and DO NOT create a new LinkedList.cpp file): insertAtFront(int): inserts a new element (i.e., a new Node) at the beginning of the list. removeFromFront(): removes the first element of the list. The function should return true if an element was successfully removed and false otherwise. Example: The first list is empty! The second list is empty! The size of the first list is: 0 The size of the second list is: 0 Here is the first list: [5,4,3,2,1] Here is the second list: [] Here is the first list: [5,4,3,2,1] Here is the second list: [25] Here is the first list: [4,3,2,1] Here is the second list: [] Here is the first list: [] Here is the second list: [10,5,0,-5] The size of the first list is: 0 The size of the second list is: 4 The first list is empty! The second list is NOT empty… Here is the second list: [10,5,0,-5] Successfully removed an item from the list… Here is the second list: [5,0,-5] Successfully removed an item from the list… Here is the second list: [0,-5] Successfully removed an item from the list… Here is the second list: [-5] Successfully removed an item from the list… Here is the second list: [] COULD NOT remove an item from the list! Here is the second list: [] COULD NOT remove an item from the list! The size of the first list is: 0 The size of the second list is: 0 The first list is empty! The second list is empty! What to hand in When you are done with this lab assignment, you are ready to submit your work. Make sure you have included the following before you press Submit: Your LinkedList.h, LinkedList.cpp, Exercise1.cpp, Exercise2.cpp , and a list of Collaborators. Documentation (in a text file) of code you used from the internet. You may want to cutand-paste the original code as well.
This lab will give you an insight in the power associated with Object Oriented Programming, by exploiting the concept of classes. Classes (much like structures) allow programmers to define their own “data type” by defining objects, which can be comprised of both variables and functions. This lab will re-use the code that you wrote for Lab 6, where you wrote a Time and a Course structure. In this lab, you will modify only the first part of Lab 6 so that you convert your Time structures into Time class. In this lab you will: take advantage of the power of classes by using member functions, constructors and destructors, and implement classes and use .h and .cpp files: .h files for class declarations, and .cpp files for class definitions and the main program. Getting started Create a new directory in your main development directory (probably on Desktop/CSE30) called Lab_08. Try to use the terminal on your own, without getting help from the TA to setup the new directories (try to learn/remember the terminal commands). The g++ syntax to compile classes is slightly different than for a single program comprised of a main (and potential functions): g++ class1.h class1.cpp class2.h class2.cpp mainSource.cpp -o executable where: g++ is the compiler (installed on your Linux system) of C++ source files, mainSource.cpp is the source file for your main program (main function), class1.h is the class declaration for your 1st class, class1.cpp is your 1st class definition, class2.h is the class declaration for your 2nd class, class2.cpp is your 2nd class definition (and so on…), -o tells the compiler that you want to give the executable its own name, and executable is the name you want to give your program. As an example, if we have a main source file called main.cpp, the class declaration called Time.h, the class definition called Time.cpp, and want to create an executable called aTestProgram, you would type: g++ Time.h Time.cpp main.cpp -o aTestProgram Assuming that your program compiled successfully (i.e. no errors were found), you can run your program as you normally would by typing “./aTestProgram” in the terminal/console. Good coding practices (worth 2 points!) Writing code that is understandable by humans is as important as being correct for compilers. Writing good code will help you complete the code, debug it and … get good grades. It is very important to learn as soon as possible, because bad habits are hard to get rid of and good habits become effortless. Someone (guess who) reads your code will be in a better mood if it is easy to understand … leading to better grades! This lab will include 2 points (10% for code quality): Explanations with comments Meaningful names Indenting of blocks { } and nesting … Proper use of spaces, parentheses, etc. to Visible, clear logic One / simple statements per line Anything that keeps your style consistent (Exercise 1) This exercise is exactly the same as Exercise 1 of Lab 6. Instead of creating a Time structure you will create a Time class. The output from your program should be exactly the same as the one for Lab 6, but you will be using a class rather than a structure. In order to receive full credit for this part of the lab, you must create: two files for your class, a Time.h file with your class declaration and a Time.cpp file with your class definition. a main.cpp file for your main, getTimeFromUser, and print24Hour functions. a total of 3 private variables in Time class: hours, minutes, and seconds. a total of 9 public functions in Time class: o Default Constructor (Time()): initializes the three variables to 0 o Extra Constructor (Time(parameters)): takes three parameters and initializes the hours, minutes, and seconds based on them. o Destructor (~Time()): does nothing. o 3 “Accessor” functions: each one returns the current value for the hours, minutes, and seconds respectively. o 3 “Mutator” functions: each one takes a parameter and sets it as the current value for the hours, minutes, or seconds. Inside the getTimeFromUser function, you no longer can set the hours by typing start_time.hours=h because hours is set to be private now. You have to use these mutator functions to set the time. This is an excerpt of the relevant part of Lab 6 Exercise 1: The program sets a start and end time for a lecture at the University. It will ask the user to enter the start time for the lecture, using the 24 hour format (HH:MM:SS). You need to check that the input produces a valid time: 1. Check if the string contains the right characters (i.e. two characters [0-9], a colon, etc.) 2. Check if the time entered makes sense (i.e. HR is 0-23, etc. … for instance, 33:79:99 does NOT make sense). 3. If the time is incorrect, output an error message and exit the program. Follow the same procedure for the end time. Once the user has entered two valid times, your program will output the start and end time in a 24 hour format. Example 1: Enter the start time for the lecture (format is HH:MM:SS): 12:22PM The start time entered is invalid! Example 2: Enter the start time for the lecture (format is HH:MM:SS): 23:59:59 Enter the end time for the lecture (format is HH:MM:SS): 23:85:00 The end time entered is invalid! Example 3: Enter the start time for the lecture (format is HH:MM:SS): 09:05:00 Enter the end time for the lecture (format is HH:MM:SS): 10:15:00 The lecture starts at 09:05:00 and ends at 10:15:00 Example 4: Enter the start time for the lecture (format is HH:MM:SS): 13:00:00 Enter the end time for the lecture (format is HH:MM:SS): 13:15:30 The lecture starts at 13:00:00 and ends at 13:15:30 What to hand in When you are done with this lab assignment, you are ready to submit your work. Make sure you have included the following before you press Submit: Your Time.h, Time.cpp, main.cpp, and a list of Collaborators.
This lab will give you some insight of the power associated with Object Oriented Programming by exploring the concept of structures. In addition, you will have to perform simple string operations, which are essential tools for programmers dealing with text. As will become clear in this lab, structures allow programmers to define their own “data type” by defining objects. In this lab, you will define a Time structure that represents hours, minutes, and seconds of the day, along with a Course structure that represents a course that you can take at a University. Together, the structures can be used to create a schedule of course for students. Note: You need to have a separate program for each part of this lab. When you submit your assignment through CatCourses, make sure that ALL PARTS are included. Getting started Create a new directory in your main development directory (probably on Desktop/CSE30) called Lab_06. Try to use the terminal on your own, without getting help from the TA to setup the new directories (try to learn/remember the terminal commands). Reminder: Once you have created a file and understood its content, you want to compile the source file (ex. main.cpp) into an executable so that you can run it on your computer. Note: EVERYTIME you modify your source file, you MUST re-compile your source file for the changes to take effect. You will compile from the command line by running: g++ -o where g++ is a program (already installed on your Linux system) that compiles C++ source files, source is the source file for your program (main.cpp in this example), -o tells the compiler that you want to give the executable its own name, and executable is the name you want to give your program. In order to compile your first program, you would have to run: g++ main.cpp -o main Assuming that your program compiled successfully (i.e. no errors were found), you can run your program by typing “./main” in the terminal/console. Good coding practices (worth 2 points!) Writing code that is understandable by humans is as important as being correct for compilers. Writing good code will help you complete the code, debug it and … get good grades. It is very important to learn as soon as possible, because bad habits are hard to get rid of and good habits become effortless. Someone (guess who) reads your code will be in a better mood if it is easy to understand … leading to better grades! This lab will include 2 points (10% for code quality): Explanations with comments Meaningful names Indenting of blocks { } and nesting … Proper use of spaces, parentheses, etc. to Visible, clear logic One / simple statements per line Anything that keeps your style consistent (Exercise 1) Create –timeInput.cpp In this part of the lab, you will be creating your own Time structure to keep track of various times of the day. Your Time structure should contain 3 integer variables: one for the hour one for the minutes one for the seconds Your program will setup a start & end time for a lecture at the University. It will ask the user to enter the start time and the end time for the lecture, using the 24 hour format (HH:MM:SS). You need to check that the input produces a valid time: check if the string contains the right characters (i.e. two characters [0-9], a colon, etc.) check if the time entered makes sense (i.e. HR is 0-23, etc. … for instance, 33:79:99 does NOT make sense). If the time is incorrect, output an error message and exit the program. Once the user has entered two valid times, your program will output the start and end times in a 24 hour format. For those who are unfamiliar with 24 hour format, please see http://en.wikipedia.org/wiki/12-hour_clock. Note: in order to receive full credit for this part of the lab, you MUST create a main program that defined the Time structure and the following two functions: getTimeFromUser: takes in a Time structure variable as a parameter, reads a string from user, checks to see if it is a valid 24 hour format, stores it inside the Time structure variable, and return true or false depending on whether or not the time is valid. Since the Time structure is not returned at the end of this function, you need to pass the reference (&) of the Time structure instead of the identifier (name) as the parameter. This way, the contents of the Time structure will be updated after the function is executed and goes back to the main function. o Write a pseudocode of getTimeFromUser function before writing it in C++ code. print24Hour: takes in a Time structure variable as a parameter and prints the time using the 24 hour format. Hints: see the following examples for the output structure use getline with cin for all of the user input i.e. getline(cin, my_line) instead of cin >> my_line in order to read symbols (“:”) from user. you will need to read the entire string for the time (i.e. 12:30:00), and process it to extract the numbers. You should extract the numbers one by one, convert them to integers, and store them in your structure. The string functions substr and find will be especially useful. o my_line.substr(x, n) will return a string of n characters starting at position x of my_line. Find more information about substr function at http://www.cplusplus.com/reference/string/string/substr/ o my_line.find(“ABC”, x) will search for “ABC” starting at the position x of my_line and return the position of the first occurrence of “ABC” (at or after position x). Find more information about find function at http://www.cplusplus.com/reference/string/string/find/ as you have done in previous labs, you will need to convert from strings to integers. The function you can use to do so is atoi, which takes in an array of characters as a parameter (NOT a string). To convert a string to an array of characters, use the function c_str(). i.e. atoi(my_line.c_str()) in some cases, you will need to add a 0 in front of single-digit numbers (e.g. 15:02:00, as opposed to 15:2:0). The functions setw and setfill will allow you to do that. o cout
This lab will explore functions in the C++ programming language, and implement variations of the problems in the previous labs, using functions. The knowledge required to complete this lab will be everything learned so far, either in the lectures or in the labs. Specifically, significant portions of code written for the previous labs can be re-used for this lab. Note: You need to have a separate program for each part of this lab. When you submit your assignment through CatCourses, make sure that ALL PARTS are included. Getting started Create a new directory in your main development directory (probably on Desktop/CSE30) called Lab_04. Try to use the terminal on your own, without getting help from the TA to setup the new directories (try to learn/remember the terminal commands). Reminder: Once you have created a file and understood its content, you want to compile the source file (ex. main.cpp) into an executable so that you can run it on your computer. Note: EVERYTIME you modify your source file, you MUST re-compile your source file for the changes to take effect. You will compile from the command line by running: g++ -o where g++ is a program (already installed on your Linux system) that compiles C++ source files, source is the source file for your program (main.cpp in this example), -o tells the compiler that you want to give the executable its own name, and executable is the name you want to give your program. In order to compile your first program, you would have to run: g++ main.cpp -o main Assuming that your program compiled successfully (i.e. no errors were found), you can run your program by typing “./main” in the terminal/console. Good coding practices (worth 2 points!) Writing code that is understandable by humans is as important as being correct for compilers. Writing good code will help you complete the code, debug it and … get good grades. It is very important to learn as soon as possible, because bad habits are hard to get rid of and good habits become effortless. Someone (guess who) reads your code will be in a better mood if it is easy to understand … leading to better grades! This lab will include 2 points (10% for code quality): Explanations with comments Meaningful names Indenting of blocks { } and nesting … Proper use of spaces, parentheses, etc. to Visible, clear logic One / simple statements per line Anything that keeps your style consistent (Exercise) Create –combineString.cpp In this part of the lab, you will create a function (combineStr) that concatenates a string by a number of times. There should be two functions in this program: main and combineStr. The descriptions of the functions are as follows. The main function will 1. Prompt the user to “Enter a string: ”. 2. Prompt the user to “Enter a number of times: ”. 3. Call the function combineStr. 4. Output “The resulting string is: ” and the resulting string. 5. Start over again. User can terminate the program by entering 0 (zero) for the number of times. The combineStr function will 1. Takes in a string and an integer as arguments. 2. Concatenates the string argument by a number of times according to the integer argument. 3. Return the resulting string. Before starting to write your program, use a piece of paper or a text editor to write the pseudocode of BOTH functions. You will need to submit the pseudocode in order to receive full credit. Again, there is no unique way to write pseudocode. It will be good enough as long as you can understand it and translate it to C++ code. Ask your TA if you are not sure about the structure of the pseudocode. Example runs (input is in italic and bold): Enter a string: 0 Enter a number of times: 7 The resulting string is: 0000000 Enter a string: bla Enter a number of times: 3 The resulting string is: blablabla Enter a string: cse30 Enter a number of times: 0 (Exercise) Create –sortArray1.cpp In this part of the lab you will write a function (sortArr) that sorts an array of integers in either ascending or descending order. This function: Is a procedure with no return value. Takes in a variable of your choice (bool or int) as an argument to indicate ascending or descending order of the sorting array. Takes in an array of integers as an argument. Takes in a number as argument indicating the size of the array. Sorts the array in ascending/descending order. Note: A 1-dimensional array a is passed *by reference* with a[] in the argument list. Reuse the selection sort (both ascending and descending versions) code that you developed in Lab 3 in this function. The main function can reuse the codes from Lab 3 to define and read the array. Specifically, you should ask the user to enter the size of the array, by outputting: “Enter the size of the array: ” to the console. If the user enters an incorrect size, you should output the error message “ERROR: you entered an incorrect value for the array size!” and exit the program. If the input is a valid size for the array, ask the user to enter the data, by outputting “Enter the numbers in the array, separated by a space, and press enter: ” Let the user enter the numbers of the array and store them into a C++ array. Up to now, this should be exactly the same code as Lab 2 and 3. Then, you need to ask the user if the array should be sorted in ascending or descending order. You may choose your criteria to input a selection: “Sort in ascending (0) or descending (1) order? ” Now, call sortArr to sort the array. After the function finishes its operations, print to the console if the output is sorted in ascending or descending order (depending on what the user had input): “This is the sorted array in order: ” and then output the array in a newline. Before starting to write your program, use a piece of paper or a text editor to write the pseudocode of the sortArr function only. Remember to write the pseudocode for both ascending and descending versions. You will need to submit the pseudocode in order to receive full credit. Again, there is no unique way to write pseudocode. It will be good enough as long as you can understand it and translate it to C++ code. Ask your TA if you are not sure about the structure of the pseudocode. Example runs (input is in italic and bold): Enter the size of the array: 5 Enter the numbers in the array, separated by a space, and press enter: 4 6 8 2 5 Sort in ascending (0) or descending (1) order? 1 This is the sorted array in descending order: 8 6 5 4 2 (Exercise) Create –sortArray2.cpp In this part of the lab, your program will run similarly to sortArray1.cpp. However, the sortArr function will use insertion sort algorithm instead of selection sort. Here is the pseudocode of an insertion sort in ascending order, but you need to do both ascending and descending versions. Before starting to write your program, use a piece of paper or a text editor to write the pseudocode of the sortArr function only. Remember to write the pseudocode for both ascending and descending versions. You will need to submit the pseudocode in order to receive full credit. Again, there is no unique way to write pseudocode. It will be good enough as long as you can understand it and translate it to C++ code. Ask your TA if you are not sure about the structure of the pseudocode. Example runs are the same as that of sortArray1.cpp What to hand in When you are done with this lab assignment, you are ready to submit your work. Make sure you have included the following before you press Submit: Your searchArray.cpp, sortArray1.cpp, sortArray2.cpp, and a list of Collaborators. File attachments of the pseudocode you create in this lab. If you write your pseudocode on papers, scan them as images and attached the images. If you write your pseudocode in text editor, same them as text files and attach them in your submission. Documentation (in a text file) of code you used from the internet. You may want to cutand-paste the original code as well.
This lab will explore Binary Search and put together various building blocks covered in previous lectures and labs to implement a binary search in an array. The knowledge required to complete this lab will be everything learned so far, either in lecture or in the lab. Specifically, significant portions of code written for the previous Labs can be reused for this lab. Note: You need to have a separate program for each part of this lab. When you submit your assignment through CatCourses, make sure that ALL PARTS are included. Getting started Create a new directory in your main development directory (probably on Desktop/CSE30) called Lab_05. Try to use the terminal on your own, without getting help from the TA to setup the new directories (try to learn/remember the terminal commands). Reminder: Once you have created a file and understood its content, you want to compile the source file (ex. main.cpp) into an executable so that you can run it on your computer. Note: EVERYTIME you modify your source file, you MUST re-compile your source file for the changes to take effect. You will compile from the command line by running: g++ -o where g++ is a program (already installed on your Linux system) that compiles C++ source files, source is the source file for your program (main.cpp in this example), -o tells the compiler that you want to give the executable its own name, and executable is the name you want to give your program. In order to compile your first program, you would have to run: g++ main.cpp -o main Assuming that your program compiled successfully (i.e. no errors were found), you can run your program by typing “./main” in the terminal/console. Good coding practices (worth 2 points!) Writing code that is understandable by humans is as important as being correct for compilers. Writing good code will help you complete the code, debug it and … get good grades. It is very important to learn as soon as possible, because bad habits are hard to get rid of and good habits become effortless. Someone (guess who) reads your code will be in a better mood if it is easy to understand … leading to better grades! This lab will include 2 points (10% for code quality): Explanations with comments Meaningful names Indenting of blocks { } and nesting … Proper use of spaces, parentheses, etc. to Visible, clear logic One / simple statements per line Anything that keeps your style consistent (Exercise 1) Create –fileIO.cpp In this part of the lab you will write a program that does the following operations: Reads words from a file (words_in.txt), with one word per line. Creates an array, using dynamic memory allocation, large enough to contain those words (one word per array element). Output the words (array elements) to another file (words_out.txt). Before storing the words from a file in an array, you will need to first find out how many lines there are in the file: one way to do it is to check with a counter when you reach the end of the file, by using the function eof(). eof() returns true (1) if the end of file is reached, otherwise a false (0) is returned. You can review the use of eof() at: http://mathbits.com/MathBits/CompSci/Files/End.htm Once you have found out how many lines there are in the file, you can create a dynamically allocated array of strings, which is as large as the number of words contained in the file (as per the counter you have implemented). You can review the syntax to declare arrays with dynamic memory allocation (pointer / new) in the lecture slides or at cplusplus.com. Finally, you will write each word (array element) into the output file, one word per line. Note: You do not need to declare an array with a pre-defined constant size nor ask the user to input the number of elements. Make sure that you create an input file with only one word per line. (Exercise 2) Create –checkArray.cpp In this part of the lab, you will create a function checkArraySort that checks if an array of strings (which was previously defined and initialized) is already sorted, and it is either increasing or decreasing. The function that you create is declared as follows: Input arguments: o A string array A (remember that array is a pointer in this case, so use the * sign) o an integer variable array_size for the number of elements in array A (the counter value from previous exercise) Return in integer value: o -1 if the array is sorted in descending order o 0 if the array is not sorted o 1 if the array is sorted in ascending order You can modify the main program that you developed in fileIO.cpp to call checkArraySort, and to print out one of the following statements: If -1 “The array is sorted in descending order!” If 0 “The array is not sorted!” If 1 “The array is sorted in ascending order!” You can use the same words_in.txt to test your program. Note: In order to check the sorting of strings / words, you can use the comparison operators (=) the same way you would compare numbers. (Exercise 3) Create –searchArray1.cpp In this part of the lab, you will create a recursive function that searches for a key in an array with a binary search algorithm. Revisit lecture# 4 for the concept of the binary search algorithm. All you need to do is to repeat splitting an array by half and compare the key to the value of the middle element. In main program: Input an array from a file. Call function (checkArraySort) to check if the array is sorted. So far, you can use the code you created from the previous exercises. Exit program if the array is not sorted, or continue if it is. Therefore, you can use the code that you built so far (exercise 2), and continue to the next steps if the array is sorted. Prompt the user to input search key (k). Call function (binarySearchR) to search for the key recursively. Output your search result: o “Found key k at index i!” if the key was found. o “The key k was not found in the array!” if the key was not found. Your binarySearchR function will return an integer value i as the index of the array A where the key is found (or -1 in key is not found), and it will take the following arguments: a string array A (again, it is a pointer) the number of elements in the array the key to search for (a string) Before writing your binarySearchR function, think about the algorithm and write it in pseudocode using a piece of paper or a text editor. You need to turn in the pseudocode to receive full credit. (Exercise 4) Create –searchArray2.cpp In this part of the lab, you will create a search function (binarySearchL) that is similar to exercise 3 with the following change: You will implement the binary search algorithm using a loop instead of a recursive function. This time all you need to do is to call a search function you create with the following arguments: a string array A (again, it is a pointer) the number of elements in the array the key to search for (a string) Return: -1 if the key was not found index of the (first) element where you found the key. Your program should behave the same way as searchArray1.cpp in the previous exercise; therefore, you may reuse the main function in searchArray1.cpp Hint: You may use the same logic to find the beginning, end, and mid-point of an array you used for the recursive binary search. You will use a loop to compare the values of the array to the key until the calculated mid-point is the last element. Before writing your binarySearchL function, think about the algorithm and write it in pseudocode using a piece of paper or a text editor. You need to turn in the pseudocode to receive full credit. What to hand in When you are done with this lab assignment, you are ready to submit your work. Make sure you have included the following before you press Submit: Your fileIO.cpp, checkArray.cpp, searchArray1.cpp, searchArray2.cpp, and a list of Collaborators. File attachments of the pseudocode you have created in this lab. If you write your pseudocode on papers, scan them as images and attached the images. If you write your pseudocode in a text editor, save them as text files and attach them with your submission. Documentation (in a text file) of code you used from the internet. You may want to cutand-paste the original code as well.
This lab will explore searching and sorting arrays in the C++ programming language. The goal of this lab is to create searching and sorting programs running on an array of integers. The knowledge required to complete this lab will be everything learned so far, either in lecture or in the lab. Specifically, significant portions of code written for Lab 2 can be re-used for this lab. When you use any code obtained from the Internet, you need to document the source. Note: You need to have a separate program for each part of this lab. When you submit your assignment through CatCourses, make sure that ALL PARTS are included. Getting started Create a new directory in your main development directory (CSE030) called Lab_03. Try to use the terminal on your own, without getting help from the TA to setup the new directories (try to learn/remember the terminal commands). Reminder: Once you have created a file and understood its content, you want to compile the source file (ex. main.cpp) into an executable so that you can run it on your computer. Note: EVERYTIME you modify your source file, you MUST re-compile your source file for the changes to take effect. You will compile from the command line by running: g++ -o where g++ is a program (already installed on your Linux system) that compiles C++ source files, source is the source file for your program (main.cpp in this example), -o tells the compiler that you want to give the executable its own name, and executable is the name you want to give your program. In order to compile your first program, you would have to run: g++ main.cpp -o main Assuming that your program compiled successfully (i.e. no errors were found), you can run your program by typing “./main” in the terminal/console. Good coding practices (worth 2 points!) Writing code that is understandable by humans is as important as being correct for compilers. Writing good code will help you complete the code, debug it and … get good grades. It is very important to learn as soon as possible, because bad habits are hard to get rid of and good habits become effortless. Someone (guess who) reads your code will be in a better mood if it is easy to understand … leading to better grades! This lab will include 2 points (10% for code quality): Explanations with comments Meaningful names Indenting of blocks { } and nesting … Proper use of spaces, parentheses, etc. to Visible, clear logic One / simple statements per line Anything that keeps your style consistent (Exercise) Create –searchArray.cpp As you will solve more complex problems, you will find that searching for values in arrays becomes a crucial operation. In this part of the lab, you will input an array from the user, along with a value to search for. Your job is to write a C++ program that will look for the value, using the linear (sequential) search algorithm. In addition, you should show how many steps it took to find (or not find) the value, and indicate whether this was a best or worst case scenario (… remember the lecture). You may refer to the pseudo-code in the lecture, but remember that the details of the output and error conditions are not specified there. Also, note that in pseudo-code arrays are sometimes defined with indices 1 to N, whereas in C++ the indexes span from 0 to N-1. The program will work as follows. First, you should ask the user to enter the size of the array, by outputting: “Enter the size of the array: ” to the console. If the user enters an incorrect size, you should output the error message: “ERROR: you entered an incorrect value for the array size!” and exit the program. If the input is a valid size for the array, ask the user to enter the data, by outputting “Enter the numbers in the array, separated by a space, and press enter: ” Let the user enter the numbers of the array and store them into a C++ array. Up to now, this should be exactly the same code as Lab#2. Next, ask the user a value v to search for in the array (called the “key”), by outputting: “Enter a number to search for in the array: ” to the screen, and read the key v. Search for v by using the linear search algorithm. If your program finds the key, you should output: “Found value v at index i, which took x checks.” where i is the index of the array where v is found, and x is the number of search operations taken place. Hint: i and x are not the same, think about the starting value of i and starting value of x. If you doesn’t find the key, then output: “The value v was not found in the array!” Then indicate whether you happened to run into a best or worst case scenario. In case you did, output: “We ran into the best case scenario!” or “We ran into the worst case scenario!” otherwise, don’t output anything. Example runs (input is in italic and bold): Enter the size of the array: 5 Enter the numbers in the array, separated by a space, and press enter: 1 5 9 7 3 Enter a number to search for in the array: 9 Found value 9 at index 2 which took 3 checks. Enter the size of the array: -5 ERROR: you entered an incorrect value for the array size! Enter the size of the array: 5 Enter the numbers in the array, separated by a space, and press enter: 9 5 1 7 3 Enter a number to search for in the array: 9 Found value 9 at index 0 which took 1 checks. We ran into the best case scenario! Enter the size of the array: 5 Enter the numbers in the array, separated by a space, and press enter: 4 5 6 8 2 Enter a number to search for in the array: 2 Found value 2 at index 4 which took 5 checks. We ran into the worst case scenario! (Exercise) Create –sortArray1.cpp As you have seen in lecture, it is often necessary to sort an array in order to make searching faster. In this part of the lab, you will implement selection sort. The selection sort algorithm consists of traversing the collection of unsorted elements to find the maximum (or minimum) value so far, and to swap it with the last one that is unsorted, and then to repeat the process. There are multiple ways to implement the selection sort algorithm, in addition to deciding whether to sort the array in an ascending versus descending order. More specifically, you may choose to: Sort the array in an ascending versus descending order, Traverse the array from beginning to end, or vice versa, and Search for the minimum versus the maximum for the traverse. The first part of this program, which reads an array from the user, is exactly the same as what you have done in the previous parts of this lab and lab#2. Specifically, you should ask the user to enter the size of the array, by outputting: “Enter the size of the array: ” to the console. If the user enters an incorrect size, you should output the error message “ERROR: you entered an incorrect value for the array size!” and exit the program. If the input is a valid size for the array, ask the user to enter the data, by outputting “Enter the numbers in the array, separated by a space, and press enter: ” Let the user enter the numbers of the array and store them into a C++ array. Up to now, this should be exactly the same code as Lab#2. Now, sort the array using a selection sort algorithm of your choice. Once the array is sorted, output first to the console if the output is sorted in ascending or descending order (depending on what you decided to use): “This is the sorted array in order:” and then output the array in a newline. Also, write if you chose the max or min for the traverse: “The algorithm selected the for the traverse of the array.” Example runs (input is in italic and bold): Enter the size of the array: 5 Enter the numbers in the array, separated by a space, and press enter: 4 6 8 2 5 This is the sorted array in descending order: 8 6 5 4 2 The algorithm selected the maximum for the traverse of the array. (Exercise) Create – sortArray2.cpp In this part of the lab, you will write a program that uses a different implementation of selection sort from the one you chose before: if you had chosen to search for the minimum for the traverse of the array, now choose the maximum, or if you had chosen to search for the maximum for the traverse of the array, now choose the minimum. You may choose whether to traverse the array forward or backward. Also, this time you are requested to calculate the number of swaps used to complete sorting the array. You can write a program starting from the previous one, and modify it to sort the array using another selection sort implementation. Once the array is sorted, output first to the console if the output is sorted in ascending or descending order (depending on what you decided to use): “This is the sorted array in an order:” and then output the array in a newline. Also, write if you chose the max or min for the traverse (which should be the opposite of sortArray1.cpp): “The algorithm selected the for the traverse of the array.” Finally, write how many swaps were used to sort this array. In the next line, output: “It took x swaps to sort the array…” where x is the number of swaps calculated by the program. Hint: declare a counter that increments whenever a swap takes place. Example runs (input is in italic and bold): Enter the size of the array: 5 Enter the numbers in the array, separated by a space, and press enter: 4 6 8 2 5 This is the sorted array in an ascending order: 2 4 5 6 8 The algorithm selected the minimum for the traverse of the array. It took 3 swaps to sort the array… What to hand in When you are done with this lab assignment, you are ready to submit your work. Make sure you have included the following before you press Submit: Your searchArray.cpp, sortArray1.cpp, sortArray2.cpp. Documentation (in a text file) of code you used from the internet. You may want to cutand-paste the original code as well. A list of collaborators.
Overview This lab will explore arrays in the C++ programming language. The goal of this lab is to create three simple programs. The knowledge required to complete this lab includes output to the console, read input from the user, if statements and for loops, and simple error handling, in addition to programming with arrays and strings with some simple operations. Note: You need to have a separate program for each of the parts of this lab. When you submit your assignment through CatCourses, make sure that ALL PARTS are included. Getting started Create a new directory in your main development directory (CSE030) called Lab_02. Try to use the terminal on your own, without getting help from the TA to setup the new directories (try to learn/remember the terminal commands). Reminder. Once you have created a file and understood its content, you want to compile the source file (ex. main.cpp) into an executable so that you can run it on your computer. Note: EVERYTIME you modify your source file, you MUST re-compile your source file for the changes to take effect. You will compile from the command line by running: g++ -o where g++ is a program (already installed on your Linux system) that compiles C++ source files, source is the source file for your program (main.cpp in this example), -o tells the compiler that you want to give the executable its own name, and executable is the name you want to give your program. In order to compile your first program, you would have to run: g++ main.cpp -o main Assuming that your program compiled successfully (i.e. no errors were found), you can run your program by typing “./main” in the terminal/console. Good coding practices (worth 2 points!) Writing code that is understandable by humans is as important as being correct for compilers. Writing good code will help you complete the code, debug it and … get good grades. It is very important to learn as soon as possible, because bad habits are hard to get rid of and good habits become effortless. Someone (guess who) reads your code will be in a better mood if it is easy to understand … leading to better grades! This lab will include 2 points (10% for code quality): Explanations with comments Meaningful names Indenting of blocks { } and nesting … Proper use of spaces, parentheses, etc. to Visible, clear logic One / simple statements per line Anything that keeps your style consistent (Exercise) Create –array1.cpp In this part of the lab, we want to check if an array of numbers input by the user is increasing. This happens if each element of the array contains a value that is larger than the value contained in previous elements. The program will work as follows: First, you should ask the user to enter the size of the array, by outputting: “Enter the size of the array: ” to the console. If the user enters an incorrect size, you should output the error message “ERROR: you entered an incorrect value for the array size!” and exit the program. If the input is a valid size for the array, ask the user to enter the data, by outputting: “Enter the numbers in the array, separated by a space, and press enter: ” Hints: Think about how to enter individual elements in an array. “cin” can only read one word/number without space. Once the input is complete, check if the array is increasing: If it is, write “This IS an increasing array!” to the console output. If it is not, write “This is NOT an increasing array!”. Print your array in one line with elements separated by a space. Before starting to write your program, use a piece of paper or a text editor to write the pseudocode of this algorithm. You will need to submit the pseudocode in order to receive full credit. Again, there is no unique way to write pseudocode. It will be good enough as long as you can understand it and translate it to C++ code. Ask your TA if you are not sure about the structure of the pseudocode. Example runs (input is in italic and bold): Enter the size of the array: 5 Enter the numbers in the array, separated by a space, and press enter: 1 2 3 4 5 This IS an increasing array! 1 2 3 4 5 Enter the size of the array: 6 Enter the numbers in the array, separated by a space, and press enter: 1 3 5 2 4 6 This is NOT an increasing array! 1 3 5 2 4 6 Enter the size of the array: -5 ERROR: you entered an incorrect value for the array size! (Exercise) Create –array2.cpp In this part of the lab, we want to create and output a string that is the reverse of a string that has been input by the user. Write a program that asks the user to input a string, by writing: “Enter the string to reverse: ” to the console output. Read the string input by the user, create a string that contains the characters in the reverse order, and then output: “The reverse of the string is: ” and the new string. For example: If the input string is “lab2” the new string and output is “2bal” If the input string is “homework” the new string and output is “krowemoh” If the input string is “1” the new string and output is “1” Remember that in C++, a string is simply an array of characters. Consequently, array indexing can be used to get desired characters in the string. (Exercise) Create –array3.cpp In this part of the lab, we want to check how many negative values are in a twodimensional (square) array, if any. Write a program that asks the user to input the dimension (n) of the square (n x n) array, and then asks the user to input the values 1 row at a time. For example: “Enter the size of a 2D array: ” “Enter the values in the array for row 1, separated by a space, and press enter: ” Limit the size of the array to maximum 10 x 10 and check for errors. Once the array is initialized, check if there is any negative element in the array and display the result: If there is no negative value: “All values are non-negative!” If there are # negative values: “There are # negative values!” … where # is the number of negative values found. Example runs (input is in italic and bold): Enter the size of a 2D array: 4 Enter the values in the array for row 1, separated by a space, and press enter: 1 5 6 3 Enter the values in the array for row 2, separated by a space, and press enter: -5 6 -12 5 Enter the values in the array for row 3, separated by a space, and press enter: 9 4 -3 1 Enter the values in the array for row 4, separated by a space, and press enter: 7 5 -3 9 There are 4 negative values! Enter the size of a 2D array: 12 ERROR: your array is too large! Enter 1 to 10. Enter the size of a 2D array: -10 ERROR: you entered an incorrect value for the array size! Enter the size of a 2D array: 3 Enter the values in the array for row 1, separated by a space, and press enter: 5 9 1 Enter the values in the array for row 2, separated by a space, and press enter: 7 5 3 Enter the values in the array for row 3, separated by a space, and press enter: 6 5 4 All values are non-negative! What to hand in When you are done with this lab assignment, you are ready to submit your work. Make sure you have included the following before you press Submit: Your array1.cpp, array2.cpp, array3.cpp, and a list of Collaborators. File attachments of the pseudocode you create in this lab. If you write your pseudocode on papers, scan them as images and attach the images. If you write your pseudocode in text editor, save it as a text file and attach it in your submission.
Overview Welcome to CSE30! This lab will help you be familiar with the C++ programming language and the tools available to you on the Linux systems in the lab. In this exercise, you should do your work on the lab systems directly so to minimize any headaches in the beginning of this semester. After you are comfortable with the system and the language would be a better time for exploring your other options. The goal of this lab is to create simple programs that will display output to the console, read input from the user, use if statements and for loops in C++, and perform some simple error handling. Note: You need to have a separate program for each of the parts of this lab. When you submit your assignment through CatCourses, make sure that ALL PARTS are included. Getting started In this class, we will use the Linux terminal extensively, so you should get familiar with it as much as possible (there is plenty of information online). We recommend setting up a smart directory structure to use throughout the class, but it is up to you how you setup your programs. We would setup a CSE30 directory on the Desktop, a directory for the lab (i.e. Lab_01) inside it, and a directory inside the lab directory for each part of the lab (i.e. part1, part2, etc…). (Exercise) Tutorial in Linux If you are not familiar with the Linux operating system or not sure how to use command lines in a Linux terminal, take a look at the tutorial from the following link during your lab hours. Otherwise, skip to the next exercise. http://linuxcommand.org/lc3_learning_the_shell.php (Exercise) Create – Lab_01 directory Open a terminal and access your Desktop directory. To create a new directory, use mkdir command. Make sure you are in your Desktop directory, type mkdir CSE30 and press enter in the terminal. To verify if the directory is created, type ls (lowercase L, not uppercase i) and press enter. You should see CSE30 among a list of directories and files under your Desktop directory. Go into the newly created CSE30 directory by typing cd CSE30 and press enter. Now, create a new directory named Lab_01 under your current (CSE30) directory. Go into the newly created Lab_01 directory and start working on your lab assignment. (Exercise) Create –main.cpp Make sure you are in your Lab_01 directory, type nano main.cpp and press enter. The nano text editor will be displayed (see the Working from a Windows/an Apple Computer guide on how to use nano). Feel free to use any other text editors (vi, gedit, etc.) of your choice. Note: If you see “bash: nano: command not found” after typing nano main.cpp, it means that nano was not installed in your machine. You will need to install it by typing “sudo apt-get install nano” and wait for the computer to finish the installation. Ask your TA if you are not sure about this. Copy the following code to your file: #include using namespace std; int main() { cout
Introduction We will use an updated version of logic.py that offers additional features. Make sure you download the new version from CatCourses and place it in your working directory. The version from last week will not allow you to solve this exercise. Originally, to create a truth table for the expressions p ∧ q, and p ∨ q, we had to do the following: myTable = TruthTable([’p’, ’q’], [’p and q’, ’p or q’]) We no longer have to provide the first parameter, so now we call: myTable = TruthTable([’p and q’, ’p or q’]) The library goes through the list of propositions and figures out the variable names for us. To solve the questions in this exercise, you have to examine the structure of the truth table built by the object TruthTable. This can be done by accessing the data member table. For example, the following lines extract the truth table and print it to the screen. myTable = TruthTable([’p and q’, ’p or q’]) a = myTable.table print(a) The truth table is represented by a list of lists, with each sublist representing a row in the truth table. To solve the following questions, it will be useful for you to first examine its structure and interact with it from the command line (e.g., to read out its elements). 1 Tautologies, contingencies and contradictions Write a program that reads a logic expression from the keyboard and prints to the screen whether the expressions is a tautology, a contingency, or a contradiction. Your code should work for expressions with an arbitrary number of variables (i.e., do not assume the expression has only two variables and therefore the truth table has just four rows). Optional – Logical Equivalences This question will not give you extra credit, but you are invited to try it out if you finish early. Write a program that reads and arbitrary number of logical expressions and determines if they are all logically equivalent to each other. 2
In this assignment we make use of code written by others. For this lab you are provided with code that generates truth tables, which you can use for other exercises. To start, download the file logic.py from CatCourses and place it in your working directory. Among other things, the file defines a TruthTable object. Start a new project and import the TruthTable object from logic.py, using the following command: from logic import TruthTable You can now generate truth tables for any proposition. All you need to specify is the list of variables that appear in your propositions, and the propositions themselves. Example Generate a truth table for the proposition p ∨ q. Solution We first note that there are two variables, p and q, which will be represented in Python as the list [’p’, ’q’]. We also need to represent the proposition itself, which is the Python string ’p or q’. Since the TruthTable object can generate a truth table with multiple expressions, we will provide the proposition as a list with a single element in it, [’p or q’]. We are now ready to generate the truth table: myTable = TruthTable([’p’, ’q’], [’p or q’]) 1 We can now display the truth table generated above: myTable.display() The command above produces the following text: p q p or q ———————– 0 0 0 0 1 1 1 0 1 1 1 1 You can also generate LATEX code for representing the table: myTable.latex() The above command produces the following text: begin{tabular}{|c|c|c|} hline $p$ & $q$ & $p lor q$ \ hline 0 & 0 & 0 \ 0 & 1 & 1 \ 1 & 0 & 1 \ 1 & 1 & 1 \ hline end{tabular} The TruthTable object can also be called with multiple propositions. myTable = TruthTable([’p’, ’q’], [’p or q’, ’p and q’]) The command above generates one truth table with both propositions side by side: p q p or q p and q ——————————– 0 0 0 0 0 1 1 0 1 0 1 0 1 1 1 1 2 When using TruthTable, we need to specify all propositions and propositional variables as Python strings, as illustrated in the examples here. The TruthTable object supports the following logical connectives: or (∨), and (∧), – (¬), -> (→), (↔). Note that when evaluating compound propositions with multiple operators TruthTable applies the precedence rules we saw in class. As always, if you are in doubt, use parentheses. Warm Up Write a Python program that prints out the truth tables for all logical connectives studied in class. There should be a separate truth table for the following: a ∧ ¬b (a ∧ b) ∨ ¬c Rules of Inference Using the TruthTable object, write a program that verifies the tautologies associated with all the rules of inference we saw in class (repeated in the following for your convenience) Rule Tautology Name p → q p ∴ q ((p → q) ∧ p) → q Modus Ponens ¬q p → q ∴ ¬p (¬q ∧ (p → q)) → ¬p Modus Tollens p → q q → r ∴ p → r ((p → q) ∧ (q → r)) → (p → r) Hypothetical Syllogism p ∨ q ¬p ∴ q ((p ∨ q) ∧ ¬p) → q Disjunctive Syllogism p ∴ p ∨ q p → (p ∨ q) Addition p ∧ q ∴ p (p ∧ q) → p Simplification p q ∴ p ∧ q ((p) ∧ (q)) → (p ∧ q) Conjunction p ∨ q ¬p ∨ r ∴ q ∨ r ((p ∨ q) ∧ (¬p ∨ r)) → (q ∨ r) Resolution 3
Modified Hello World Write a Python program that asks the user for his/her name, and prints out a greeting message of the form “Hello, “, where is the input received from the user. Integer Classification Write a Python program that asks the user to enter an integer. Your program should print ODD if the integer is odd, and EVEN if the integer is even. Reminder: an even integer can be represented as 2x, and an odd integer can be represented as 2x + 1, where x ∈ Z. More Even and Odd Write a Python program that asks the user to enter 10 integers, and outputs the largest odd number among them. If no odd numbers were entered, your program should output a message saying: “No odd numbers were entered”.
Overview In class we have recently covered Dynamic Hashing and Extendible Hashing indices. Both require a directory. In 1980 Witold Litwin introduced Linear Hashing, a directory–free hash–based indexing structure. In this assignment, you’ll implement what we’ll call Linear Hashing Lite1 (LHL) and use it to assist the querying of a binary file. See the last page of this handout for the description of LHL.This assignment is in two parts, both of which have the same due date. Part 1: Write a program named Prog21.java that creates, in a binary file named lhl.idx, a Linear Hashing Lite index for the lunarcraters.bin database file created by your Prog1A.java program. Write your program to store lhl.idx in the current directory (that is, do not add any path information to the index file name), and to accept the complete path to the lunarcrater.bin file as the command–line argument. The index is to be constructed using the ‘Crater Name’ field (the first field) as the key, the values of which should be unique across the data.For this implementation of LHL, the buckets will have a maximum capacity of 25 index records. Initially, the index will consist of two empty buckets, H = 0, and the hash function will be hH(k) = | k.hashCode() | % (2H+1), where | k.hashCode() | is the absolute value of the result of java.lang.String’s hashCode() method executed on k, a crater name string.After the index file has been created, display, labeled clearly and in this order, (a) the number of buckets in the index, (b) the number of records in the lowest–occupancy bucket, (c) the number of records in the highest-occupancy bucket, and (d) the mean of the occupancies across all buckets.Part 2: The second task is to write a program named (you guessed it) Prog22.java that processes a simple variety of query with the help of your LHL index. The complete paths to both the lhl.idx index file and the lunarcrater.bin database file are provided, in that order, as command–line arguments. Use a loop to prompt the user to enter any number of target values, one at a time. If the target matches a ‘Crater Name’ value in the LHL index, display the same four values from the corresponding DB file record in the database file as you displayed in Program #1, and in the same format. Otherwise, display the message “The target value ‘#####’ was not found.” (Of course, display the actual target value, not a bunch of pound signs!)In order to successfully write Prog22.java, you may decide that you need to communicate to it some metadata about the index created by Prog21.java. Program #1 gave you some experience doing that sort of thing (with the max string lengths). You may do the same sort of thing in this assignment. Keep in mind that your index’s size will vary based on the number of records in the DB file (binary file) your Prog1A.java creates, much as your binary file’s size varies based on the CSV file’s content. (Continued…)1One-third fewer headaches than regular Linear Hashing, but the same great idea! Data We will use your own lunarcraters.bin file to test your programs, which means that you will need to submit it using turnin. You may also submit your current Prog1A.java program, if you wish to do so. Why would you want to? If the TAs have a problem with your binary file and also have the current version of the program that generates it, they can try to recreate it themselves.As for dreaming up queries for testing, that’s up to you (but shouldn’t be too hard). We’ll test with a variety of ‘Crater Name’ field values (present in the data and not). Thus, so should you. Control Prog22.java the same way you controlled the execution of Prog1B.java, terminating when a ‘Crater Name’ value of ‘E’ or ‘e’ is entered.Output The basic output expectations of Prog21.java and Prog22.java are given with their descriptions, above. Hand In You are required to submit your completed program files (Prog21.java and Prog22.java), and your lunarcrater.bin file on which those programs operate, using the turnin facility on lectura. The submission folder is cs460p2.Optionally, you may also provide your current Prog1A.java program. Submit all files as–is; that is, do not ‘package’ them into ZIP or TAR files. Because we will be grading your program on lectura, it needs to run on lectura, and so you need to test it on lectura. Name your main program source files as directed above, so that we don’t have to guess which files to compile, but feel free to split up your code over additional files if you feel that doing so is appropriate.Want to Learn More? Remember: What this assignment requires is not the full version of Linear Hashing described in these papers; I’m referencing them to satisfy the curious among you. Lots of copies of Litwin’s original Linear Hashing paper are floating around the internet, because the official source isn’t readily available. Google Scholar can point you to a copy: https://scholar.google.com/scholar?q=”Linear+Hashing+A+New+Tool+for+File+and+Table+Addressing.” A somewhat more approachable description of Linear Hashing can be found as part of the paper “Dynamic hash tables” by Per–Ake (Paul) Larson: http://dl.acm.org/citation.cfm?doid=42404.42410 Other Requirements and Hints Comment your code according to the style guidelines as you write the code (not an hour before class!). Work on just a part of the assignment at a time; don’t try to code it all before you test any of it. Don’t be afraid to do things a little bit backwards; for example, it’s nice to have a basic query program in place to help you test the construction of your index.You can make debugging easier by using only a small amount of data with very small buckets as you develop the code, and switch to the complete data file and full–size buckets when everything seems to be working. As always: Start early! We don’t have an early, first–part due–date on this one; you’ll have to do your own planning. (Continued…)Like Dynamic and Extendible Hashing, Linear Hashing was created for indexing. Unlike them, Linear Hashing does not use a directory as its hash function. Instead, it relies on a characteristic of division–based hash functions, thus so does our simplified version, described on this page.• Insertion Consider two hash buckets, which, for this demonstration, are each capable of holding at most bf = 3 index records, and the simple hash function h(k) = k % 2. The result of hashing the key values 16, 19, 26, 31, and 12 is: 0 1 16 26 12 19 31To store the key value 10, we need to expand the hash table and change the hash function. Specifically, we will change the hash function to be h(k) = k % 4 (double the divisor), and double the number of buckets in the table (to match the range of the new function). We also need to re–distribute (re–hash) the existing key values. Because of our choice of hash functions, this isn’t a typical re–hash: The values currently in bucket 0 will either stay there, or will move to bucket 2. Similarly, those in bucket 1 will stay or move to bucket 3. (Why this happens is left as an exercise for the reader.) After the re–hashing, and after the insertion of 10, the table looks like this: 0 1 2 3 16 12 26 10 19 31Each time we need to insert into a full bucket, the same steps are performed: We double the divisor of the hash function, double the number of buckets in the hash table, re–hashing the existing values, and insert the new key. Each time we re–hash the content of a bucket, the entries either stay in the same bucket, or move to just one of the new buckets. This property helps minimize I/O operations.Performing insertions for this assignment is a bit more involved. We discover the keys to be inserted by sequentially reading the records in the binary file created by Prog1A.java (the ‘Database File’ in the figure below). As we read the records, we also note their locations (here, their record numbers, if you imagine the file to be an array of records). Together, the key and the record number form the index record that is inserted into the hash bucket. It is helpful to parameterize the hash function.That is, instead of h(k), express the hash function as h(k, H) = k % (2H+1), where H = 0 initially and increases by one whenever the hash table grows. (Note that the number of buckets in the hash table is the same as the hash function’s divisor, 2H+1.) • Searching 16 0 12 4 26 2 10 5 19 1 31 3 0 1 2 3 LHL Hash File (H = 1, bf = 3) 16 19 26 31 12 10 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 0 1 2 3 4Database File Searching a Linear Hashing Lite index is straight–forward: Using the given target to be located and the last value of H, locate and read the bucket of the hash file that contains (or would contain) the target. Sequentially search the bucket content to see if the target is there. If it is, use the paired DB file record number to access the DB file fields you need to output.For example, consider the figures to the right (an enhanced version of the above insertion example) and the target value 31. Our last value of H was 1. h(k, H) = h(31, 1) = 31 % (21+1) = 3. Reading and searching bucket 3 locates 31’s index record, which contains the record number of 31’s complete record in the database file (in this example, the record number is 3). Reading that record provides 31’s associated data, allowing the query to be completed.
Overview: Program #2 will create an index on a binary file that this program creates. I could just give you the binary file, or merge the two assignments, but creating the binary file from a formatted text file makes for a nice “shake off the rust” assignment, plus it provides a gentle(?) introduction to binary file processing for those of you who haven’t used it before.A basic binary file contains information in the same format in which the information is held in memory. (In a standard text file, all information is stored as ASCII or UNICODE characters.) As a result, binary files are generally faster and easier for a program (if not always the programmer!) to read and write than are text files.When your data is well–structured, doesn’t need to be read directly by people, and doesn’t need to be ported to a different type of system, binary files are usually the best way to store information.For this program, we have lines of data values that we need to store, and each line’s values need to be stored as a group (in a database, such a group of related fields is called a record). Making this happen in Java requires a bit of effort. Alongside the PDF version of this handout on the class web page, you’ll find a sample Java binary file I/O program that shows the basics of working with binary files.Assignment: To discourage procrastination, this assignment is in two parts, Part A and Part B. Part A Available on lectura is a file named lunarcraters.csv (see the Data section, below, for the location). This is a CSV text file from the Lunar and Planetary Institute consisting of over eight thousand lines of data describing impact craters on Earth’s moon. Each lunar crater is described by ten fields of information, separated by commas (hence the .csv extension — comma–separated values). Using Java 16 or earlier, write a complete, well–documented program named Prog1A.java that creates a binary file version of the provided text file’s content whose records are stored in the same order as provided in the data file (which is sorted alphabetically by the names of the craters).Some initial details (the following pages have many more!): For an input file named file.csv, name the binary file file.bin. (That is, keep the file name, but change the extension.) Do not prepend a path to the file name in your code; just let your program create the binary file in the current directory (which is the default behavior). Field types are limited to double and String. Specifically, if a field seems to contain real #s, it does.When necessary, pad strings on the right with spaces to reach the needed length(s) (see also the next bullet point). For example, “abc “, where ” ” represents the space character. For each column, all values must consume the same quantity of bytes, so that records have a uniform size. This is easy for numeric columns (e.g., a double in Java is always eight bytes), but for alphanumeric columns we don’t want to waste storage by choosing an excessive maximum length. Instead, your program needs to determine the number of characters in each string field’s longest value, and use that as the length of each value in that field. This must be done for each execution of the program. (Why? The data doesn’t define maximum string lengths, so we need to code defensively to accommodate changes in data. You may assume that the data file’s field order, data types, and quantity of fields will not change.) (Continued . . . )Because the maximum lengths of the string fields can be different for different input files, you will need to store these lengths somewhere within the binary file so that your Part B program can use them to successfully read the binary file. How you do this is up to you. One possibility is to store the maximum string field lengths at the end of the binary file (after the last data record). This allows the first data record to begin at offset zero in the binary file, which keeps the record location calculations a bit simpler for Part B’s program. How do you know that your binary file is correctly created? Here’s one way: Write the first part of PartRead the rest of this handout before starting Part A! Remember, Part A is due in just one week; start today! Part B Write a second complete, well–documented Java 16 (or earlier) program named Prog1B.java that performs both of the following tasks: 1. Read directly from the binary file created in Part A (not from the provided .csv file!), and print to the screen the content of the Crater name, Diameter, Apparent depth, and Age fields of the first three records of data, the middle three records (or middle four records, if the quantity of records is even), and the last three records of data. Next, display the total number of records in the binary file, on a new line. Conclude the output with a list, in descending order by depth, of the names and apparent depths of the ten craters having the largest apparent depths. If there are ties, display all of the craters with apparent depths that tie the depth of the tenth–deepest crater (thus, the list may be longer than ten). The TAs will not be doing ‘script grading,’ so you do not need to worry about generating a specific output format, but it should be easily readable by human beings.If the binary file does not contain at least ten records, print as many as exist for each of the four groups of records. For example, if there are only two records, print the fields of both records four times — once as the “first three” records, a second time as the “middle three,” a third time as the “last three,” and a fourth time (in the appropriate order) as the list of “ten.” (And, of course, also display the total quantity of records.)2. Allow the user to provide, one at a time, zero or more crater names, and for each name locate within the binary file using exponential binary search (see below), and display to the screen the same four field values (name, diameter, apparent depth, and age) of the record identified by the given name, or display a polite ‘not found’ message.A few more Part B details: Many craters do not have age strings. For them, display “null” as the age. Output the data one record per line, with each field value surrounded by square brackets (e.g., [Lee M][73.33][2.766][null]). seek() the Java API and ye shall find a method that will help you find the middle and last records of the binary file. (See also the previously–mentioned BinaryIO.java example.) Use a loop to prompt the user for the crater names, one crater name per iteration. Terminate the program when either “e” or “E” is entered as the name.Data: Write your programs to accept the complete data file pathname as a command line argument (for Prog1A, that will be the pathname of the data file, and for Prog1B, the pathname of binary file created by Prog1A). The complete lectura pathname of our data file is /home/cs460/spring24/lunarcraters.csv. Prog1A (when running on lectura, of course) can read the file directly from that directory; just provide that path when you run your program. (There’s no reason to waste disk space by making a copy of the file in your CS account.) (Continued . . . )Each of the lines in the file contains ten fields of information. Here is an example line: Lee M,72.33,-29.83,-39.70,62.20,39.28,2.766,4694.64,0.00, This example demonstrates a few of the data situations that your program(s) will need to handle: The field names can be found in the first line of the file. Because that line contains only metadata, that line must not be stored in the binary file. Code your Part A program to ignore that line. Many .csv files have missing field values (usually represented with adjacent commas (e.g., “,,”), or lines that end with a comma, to show that no data exists for that field). In this data, the only missing data values we know of are many of the ages (the last column), which is why the example line above ends with a comma. Should you find any other fields with missing data, let us know and we’ll tell you how to handle those situations. Finally, be aware that we have not combed through the data to see that it is all formatted perfectly.This is completely intentional! Corrupt and oddly–formatted data is a huge headache in data management and processing. We hope that this file holds a few additional surprises, because we want you to think about how to deal with additional data issues you may find in the CSV file, and to ask us questions about them as necessary.Output: Basic output details for each program are stated in the Assignment section, above. Please ask (preferably in a public post on Piazza) if you need additional details.Hand In: You are required to submit your completed program files using the turnin facility on lectura. The submission folder is cs460p1. Instructions for turnin are available from the document of submission instructions linked to the class web page. In particular, because we will be grading your program on lectura, it needs to run on lectura, so be sure to test it thoroughly on lectura. Feel free to split up your code over additional files if doing so is appropriate to achieve good code modularity. Submit all files as–is, without packaging them into .zip, .jar, .tar, etc., files.Want to Learn More? BinaryIO.java — New to binary file IO, or need a refresher? This example program and its data file are available from the class web page and from the /home/cs460/spring24/ directory on lectura. https://www.lpi.usra.edu/scientific-databases/ — This is the source of our data; scroll down to the “Lunar Impact Crater Database (2015)” link. The full data file has many additional columns that we removed so that you wouldn’t have to worry about them. (You’re welcome!) You don’t need to visit this page; we’re providing it in case you’re interested in learning more.Other Requirements and Hints: Don’t “hard–code” values in your program if you can avoid it. For example, don’t assume a certain number of records in the input file or the binary file. Your program should automatically adapt to simple changes, such as more or fewer lines in a file or changes to the file names or file locations. Another example: We may test your program with a file of just a few data records or even no data records. We expect that your program will handle such situations gracefully. As mentioned above, the characteristics of the fields (types, order, etc.) will not change. Once in a while, a student will think that “create a binary file” means “convert all the data into the characters ‘0’ and ‘1’.” Don’t do that! The binary I/O functions in Java will read/write the data in binary format automatically. (Continued . . . )Not a fan of documenting code? Try this: Comment your code according to the style guidelines handout as you write the code (rather than just before the due date and time!). Explaining in words what your code must accomplish before you write that code is likely to result in better code sooner. The documentation requirements and some examples are available here: https://mccann.cs.arizona.edu/style.html You can make debugging easier by using only a few lines of data from the data file for your initial testing.Try running the program on the complete file only when you can process a few reduced data files. The CSV files are plain text files; you can view them, and create new ones, with any text editor. Late days can be used on each part of the assignment, if necessary, but we are limiting you to at most two late days on Part A. For example, you could burn one late day by turning in Part A 18 hours late, and three more by turning in Part B two and a half days late. Of course, it’s best if you don’t use any late days at all; you may need them later. Finally: Start early! There’s a lot for you to do here, and file processing can be tricky.Exponential Binary Search Exponential Binary Search is an extension of normal binary search originally intended for searching unbounded data, but it works for bounded data, too, such as might be stored in a binary file. The algorithm has two stages: Stage 1 : For i = 0, 1, . . ., probe at index 2(2i − 1) until the index is invalid or an element ≥ the desired target is found. (If the probed element equals the target, the search is complete.) Stage 2 : Perform binary search on the range of indices from 2(2i−1 − 1) + 1 to min(2(2i − 1) − 1, largest index), inclusive.To better understand how this works, sketch an ordered array of 16 integers on a piece of paper, and imagine that you’re searching for an item toward the far end of the array.The algorithm can be extended to have as many repetitions of Stage 1 as desired to further narrow the range that Stage 2 needs to search. For our purposes, this basic version is adequate. Reference: Bentley and Yao, “An Almost Optimal Algorithm for Unbounded Searching,” Information Processing Letters 5(3), 1976, pp. 82-87. https://www.slac.stanford.edu/cgi-bin/getdoc/slac-pub-1679.pdf
Programming Project 3, you will be generating Huffman codes to compress a given string. A Huffman code uses a set of prefix code to compress the string with no loss of data (lossless).David Huffman developed this algorithm in the paper “A Method for the Construction of Minimum-Redundancy Codes” (http://compression.ru/download/articles/huff/ huffman_1952_minimum-redundancy-codes.pdf)A program can generate Huffman codes from a string using the following steps: · Generate a list of the frequency in which characters appear in the string using a map · Inserting the characters and their frequencies into a priority queue (sorted first by the lowest frequency and then lexicographically) · Until there is one element left in the priority queue · Remove two characters/frequencies pairs from the priority queue · Turn them into leaf nodes on a binary tree · Create an intermediate node to be their parent using the sum of the frequencies for those children · Put that intermediate node back in the priority queue ·The last pair in the priority queue is the root node of the tree · Using this new tree, encode the characters in the string using a map with their prefix code by traversing the tree to find where the character’s leaf is. When traversal goes left, add a 0 to the code, when it goes right, add a 1 to the code · With this encoding, replace the characters in the string with their new variable-length prefix codes In addition to the compress string, you will need to be able to serialize the tree. Without the serialized version of the Huffman tree, you will not be able to decompress the Huffman codes. Tree serialization will organize the characters associated with the nodes using post order. During the post order when you visit a node, · if it the node is a leaf (external node) then you add a L plus the character to the serialize tree string · if it is a branch (internal node) then you add a B to the serialize tree stringFor decompression, two input arguments will be needed. The Huffman Code that was generated by your compress method and the serialized tree string from your serializeTree method. Your Huffman tree will have to be built by deserializing the tree string by using the leaves and branches indicators. After you have your tree back, you can decompress the Huffman Code by tracing the tree to figure out what variable length codes represent actual characters from the original string. So, for example, if we are compressing the string “if a machine is expected to be infallible it cannot also be intelligent”: Our compress algorithm would generate the following codes for the characters: Character Frequency Prefix Code (space) 12 00 a 5 1011 b 3 10101 c 3 11000 d 1 010000 e 9 100 f 2 01011 g 1 010001 h 1 010010 i 8 011 l 6 1101 m 1 010011 n 6 1110 o 3 11001 p 1 010100 s 2 10100 t 6 1111 x 1 010101 Our code would be: 011010110010110001001110111100001001001111101000001110100001000101010101001001 1000111110001000000111111001001010110000011111001011101111011101011101011101100 00011111100110001011111011101100111110010111101101001100100101011000001111101111 1001101110101101000110011101111 And our serialize tree would look like: L LdLgBLhLmBBLpLxBLfBBLiBBLeLsLbBLaBBLcLoBLlBLnLtBBBB You will need to create one class for this project: HuffmanTree for the compression, decompression, and serialization that uses a linked binary tree. You are given a Heap-based Priority Queue for the sorting.You are allowed to use the STL map, vector, and stack, but not the STL priority queue. Abstract Class Methods std::string compress(const std::string inputStr) Compress the input string using the method explained above. Note: Typically we would be returning a number of bits to represent the code, but for this project we are returning a string std::string serializeTree() const Serialize the tree using the above method.We do not need the frequency values to rebuild the tree, just the characters on the leaves and where the branches are in the post order. std::string decompress(const std::string inputCode, const std::string serializedTree) Given a string created with the compress method and a serialized version of the tree, return the decompressed original string Other things in Huffman hpp/cpp To simplify the process, I have given the full interface and implementation for a class called HuffmanNode. This class has all the basics for a tree node (leaf, branch, root, data members for linking, accessor) and also includes a comparator class for use with the heap. You should not need to alter any of the code for this node.Examples Below are some examples of how your code will run HuffmanTree t; string test = “It is time to unmask the computing community as a Secret Society for the Creation and Preservation of Artificial Complexity”; /* 1000101011110000101001100110000010111011001110111101111100011001001011 0100100001111001110010011101101111010110010101010111110011000001110000 1011011110101100100010111110001100001111111111001011010011001011101001 1111101111001001110011110100111101111110000111001111111111010101110110 1001100111001001110110100110010011100101011000101100111100101001110000 0111010000000100111010100111001001000110010101100010110011110101110101 1110100010001000110001010110001111000001011001011101001101011001010101 010010111101000111000011111111 */ string code = t.compress(test); /* LiLmLnBBLrLaBLtBBLPLdBLgLkBBLALIBLvLxBBBLhLlBLCLSBBBLsLpLfBBLoBBL LeLcLuLyBBBBBB */string tree = t.serializeTree(); /* It is time to unmask the computing community as a Secret Society for the Creation and Preservation of Artificial Complexity */ string orig = t.decompress(code, tree); Deliverables Please submit complete projects as zipped folders.The zipped folder should contain: · HuffmanTree.cpp (Your written HuffmanTree class) · HuffmanTree.hpp (Your written HuffmanTree class) · HeapQueue.hpp (The given Heap Priority Queue using an array/vector class) · HuffmanBase.cpp (The provided base class and helper class) · HuffmanBase.hpp (The provided base class and helper class) · PP3Test.cpp (Test file) · TestStrings.hpp (Test file) · catch.hpp (Catch2 Header) And any additional source and header files needed for your project. Hints For the encoding step where you translate characters using your Huffman Tree, this is essentially a preordering of the tree and can be done recursively.Remember, when you are deserializing, you are going from post ordering back to the full tree. This is very similar to the postfix to infix conversion you did in PP2, but now building a tree instead of an expression. For decoding the characters, you just follow the tree down the branches until you hit the leaf with the character, adding a zero for a left move and adding a 1 for a right move. I suggest implementing a recursive method to destroy nodes for your destructor. For the branching nodes, I suggest using the null character just to hold a spot since this should not be popping up in text you are compressing. The test cases are based on using the standard library header
For Programming Project 2, you will implement a Deque (Double-Ended Queue) and use that data structure to write a class that can convert between the three common mathematical notation for arithmetic.The three notations are: Postfix (Reverse Polish) Notation: Operators are written after operands A B – C + == (A – B) + C Infix Notation: The standard notation we use where the operator is between the operands.Prefix (Polish) Notation: Operators are written before operands: * – A B C == (A – B) * C The converter will be able to convert from one of those three to any other. The input will be a string written in a single notation, and the output will be the conversion to the specified notation. The input string for the functions will only ever contain the standard four arithmetic operators (* / + -), an operand denoted by a letter (upper or lower case), a left or right parentheses (only round), or spaces. Whitespace (one or more characters of space) separate all operand and operators, while parentheses must have whitespace on the outside (between operators), and inside parentheses whitespace is optional. Parentheses are only used in infix strings. Parentheses must have operators between them, as all operations must be binary and not implied. For example: Valid Postfix: c d / a b * r r * / * Valid Prefix: * + A B – C D Valid Infix: (( X + B ) * ( Y – D ))Invalid Postfix:c d a b * r r * / * (Operators don’t match up with operands) Invalid Prefix: * ^ A B & C D (Invalid Characters) Invalid Infix: ((a / f) ((a * b) / (r * r))) (No operator between parentheses)The output string should always separate all operand and operators by ONLY one space. The interior of a parenthesis should have no whitespace between the letter and the parenthesis or another parenthesis, while the exterior of a parenthesis should be separated by ONLY one space from an operator and none for another parenthesis.For example: Valid Output: ((x / y) – g) Valid Output: ((x / y) – (a * b)) Valid Output: x y * g / h + If your output does not conform to this standard, you will not pass the tests required for this project. Again, there is an abstract class for you to inherit that has you implementing the following methods.Abstract Class Methods std::string postfixToInfix(std::string inStr) This method takes in a string of postfix notation and returns a string in the infix notation std::string postfixToPrefix(std::string inStr) This method takes in a string of postfix notation and returns a string in the prefix notation std::string infixToPostfix(std::string inStr) This method takes in a string of infix notation and returns a string in the postfix notation std::string infixToPrefix(std::string inStr)This method takes in a string of infix notation and returns a string in the prefix notation std::string prefixToInfix(std::string inStr) This method takes in a string of prefix notation and returns a string in the postfix notation std::string prefixToPostfix(std::string inStr)This method takes in a string of prefix notation and returns a string in the postfix notation These methods will all be instance methods of the class NotationConverter (which must be called “NotationConverter”). You will also need to implement a fully function deque using a doubly linked list. When writing the methods to convert between the notations, you can ONLY use your deque and strings for storing data in the algorithms. You may not use any C++ Standard Library containers, such as the STL Deque, Stack, Queue, Vector, or List.This project will be tested using the Catch2 (https://github.com/catchorg/Catch2) test framework. This framework only requires that a program include the header to run the test file. The test file that will be used to grade the project is included and can be used to test your code before submitting. For your convenience, this project contains the Catch2 header. The course documents include a quick tutorial on how to use Catch2 and test files. I require and expect that you keep the Catch2 header in your project directory at that directories base. Examples Below are some examples of how your code should run. The test file can also be used to get an idea of how the code should run. NotationConverter nc; std::string examplePost = “c d / a b * r r * / *”; nc.postfixToInfix(examplePost) // Infix: ((c / d) * ((a * b) / (r * r))) nc.postfixToPrefix(examplePost) // Prefix * / c d / * a b * r r std::string examplePre = “* + A B – C D”; nc.prefixToInfix(examplePre) // Infix: ((A + B) * (C – D)) nc.prefixToPostfix(examplePre) // Postfix A B + C D – * std::string exampleInfix = “((a / f) ((a * b) / (r * r)))”; nc.infixToPostfix(exampleInfix) // Postfix: a f / a b * r r * / nc.infixToPrefix(exampleInfix) // Prefix / a f / * a b * r r Deliverables Please submit complete projects as zipped folders. The zipped folder should contain: NotationConverter.hpp (Your source file for NotationConverter class) NotationConverter.cpp (Your header file for NotationConverter class) PP2Test.cpp catch.hpp NotationConverterInterface.hpp And any additional source and header files needed for your project. Best practice is to put the code for your Deque and Doubly Linked List in their own header/source files and include them using the preprocessor include in the appropriate files.Hints It would be a good idea to decode the input string and place it into a deque to make it easier to read for the various methods In the algorithm header, there is a method that can reverse strings.When dealing with infix notations, remember that operator precedence is very important Remember, a deque can operate like a stack or a queue, queues and stacks can be considered specializations of a deque You may not need to write a separate algorithm for all six methods. For example, when going from postfix to prefix, you can go from postfix to infix and infix to prefix if those methods are already implemented.Rubric Any code that does not compile will receive a zero for this project. Criteria Points Infix notation should convert to prefix notation 4 Infix notation should convert to postfix notation 4 Prefix notation should convert to postfix notation 4 Prefix notation should convert to infix notation 4 Postfix notation should convert to infix notation 4 Postfix notation should convert to prefix notation 4 Checks for invalid characters 2 NotationConverter uses a student implemented Deque 7 Code uses object oriented design principles (Separate headers and sources, where applicable) 3 Code is well documented 4 Total Points 40
For Programming Project 1, the student will implement a linked list based arithmetic calculator. The calculator will be able to perform addition, subtraction, multiplication, and division. The calculator will keep a running total of the operations completed, the number of operations completed, and what those operations were. The calculator will also have an “undo” function for removing the last operation. The calculator will also be able to output a string of the operations completed so far with fixed precision.The calculator (which must be called “CalcList”) has to be implemented using a singly, doubly, or circularly linked list. Any projects that use the C++ Standard Library Lists or other sources to implement the linked list will receive a zero. The calculator has to implement at least four methods: Abstract Class and Files double t o t a l ( ) constThis method returns the current total of the CalcList. Total should run as a constant time operation. The program should not have to iterate through the entire list each time the total is needed. void newOperation(const FUNCTIONS func, const double operand)Adds an operation to the CalcList and creates a new total. The operation alters total by using the function with the operand. Example: newOperation(ADDITION, 10) => adds 10 to the total. void removeLastOperation() Removes the last operation from the calc list and restores the previous total. std: : st r ing toString(unsigned short precision) constReturns a string of the list of operations completed so far formatted with a fixed point precision. The form of the string should strictly be: “(step): (totalAtStep)(Function)(operand) = (newTotal) ”. Example: t o S t r i n g ( 2 ) => ” 3 : 30.00*1.00=30.00 2: 10.00+20.00=30.00 1: 0.00+10.00=10.00 ”This project includes an abstract class for the CalcList from which to inherit. This abstract class (CalcListInterface) contains the pure virtual version of all the required methods. This file also includes a typedef of an enum used for the four arithmetic functions called FUNCTIONS.This project will be tested using the Catch2 (https://github.com/catchorg/Catch2) test framework. This framework only requires that a program include the header to run the test file. The test file that will be used to grade the project is included and can be used to test your code before submitting. For your convenience, this project contains the Catch2 header. The course documents include a quick tutorial on how to use Catch2 and test files.Please submit complete projects as zipped folders. The zipped folder should contain: PP1Test.cpp, catch.hpp, CalcListInterface.hpp, CalcList.hpp (Your Code), CalcList.cpp (Your Code) Examples Below are some examples of how your code should run. The test file can also be used to get an idea of how the code should run. C a l c L i s t c a l c ; calc.newOperation(ADDITION, 1 0) ; / / Total == 0 / / Total == 10 calc.newOperation(MULTIPLICATION, 5 ) ; / / Total == 50 calc.newOperation(SUBTRACTION, 1 5) ; calc.newOperation(DIVISION, 7 ) ; calc.removeLastOperation(); calc.newOperation(SUBTRACTION, 3 0) ; calc.newOperation(ADDITION, 5 ) ; calc.removeLastOperation(); / / Total == 35 / / Total == 5 / / Total == 35 / / Total == 5 / / Total == 10 / / Total == 5 / / Should R eturn: / / 4 : 35.00-30.00=5.00 / / 3 : 50.00-15.00=35.00 / / 2 : 10.00*5.00=50.00 / / 1 : 0.00+10.00=10.00 s t d : : c o u t
ADVANCED SIMULATION METHODS COURSEWORK 1, SPRING 2024-2025 This assignment will be done individually. You should prepare a PDF report written primarily in a in a report/paper format, to be submitted through Blackboard, Coursework 1 container (under Courseworks folder). You can also write this in IPython notebook format, if you like, however, you should export a readable PDF from this. By submitting the coursework,you will be agreeing that this assessed coursework is your own work unless otherwise acknowledged, includes no plagiarism, you have not discussed it with anyone else except when seeking clarifications with the module lecturer, and have not shared any code with anyone else prior to submission. In your answers, you can quote material from the notes and shared IPython notebooks, providing your own original explanations. This course work accounts for approximately 40% of the final grade. The report will be marked from 0 to 40. The deadline is 1PM, 12 March 2025. To enable anonymous marking, please put your CID and not your name into the filename of the submission or into the manuscript. Q1: ESTIMATING A LATENT VARIABLE MODEL Assume that we have the following latent variable model: where Below, we set our observed data to The parameter ∈ is a free parameter which we will use to investigate sampling behaviour. In this question, we aim at sampling from the posterior p(θ|y) using various methods you have seen in Chapters 1 and 2. 1. Provide the expressions of the distributions p(y|θ) and p(θ|y) in closed form using the Gaussian marginalization and conditioning formulas in Chapter 2. You can refer to the lemmas in the lecture notes, but do give a brief explanation of the derivation. (2 marks) 2. Given the parameters in the main part of the question and your derivation in Part 1, compute (on computer) the mean and covariance of p(θ|y) and provide a contour plot (see this Jupyter notebookfor helper code for plotting) for ∈ = 10−3 , 10−2 , 10−1 , 1. Discuss these plots and the effect of ∈ . (1 mark) 3. Fix ∈ = 1. Present and demonstrate the performance of the random-walk Metropolis- Hastings (RWMH) sampler to sample from p(θ|y). Provide a clear explanation of the method, the parameter choice (e.g. proposal variance, denoted σM(2)H ). Draw N = 100000 samples after an appropriate burnin stage (you need to set this) to demonstrate the method. (2 marks) 4. Provide the plots of the autocorrelation functions w.r.t. different proposal variance choices by varying σM(2)H between 10−4 to 4 with an appropriate precision and running RWMH for these variances. Identify the best variance for mixing. Plot your samples for the best choice of your proposal on top of the density contour. (3 marks) 5. Fix the variance σM(2)H of the proposal to the best value you have obtained in the previous part, now try this sampler for ∈ = 10−3 , 10−2 , 10−1 , 1 for N = 100000 samples. Provide the curves of the autocorrelation function for each case in a single plot. Comment on the results, in particular the effect ∈ on mixing, provide a reasoning to explain it. (2 marks) 6. Now suppose that p(y|θ) cannot be computed in closed form. Derive a basic impor- tance sampling (IS) estimator for this quantity. (1 mark) 7. Fix ∈ = 1 for the rest of this question. Let us denote the IS estimator you derived in previous part with We denote the relative absolute error (RAE) as where σIS is the standard deviation of the proposal distribution q = N(0, σI(2)SI) and K is the number of samples used to build this IS estimator. To test this estimator, we will set θ = [0, 0] and use y as above. Compute the ground truth value p(y|θ), tune σI(2)S , and demonstrate the estimator accuracy by computing RAE for K =102 , 103 , 104 , 105 . To demonstrate this, you may need to run, e.g., M = 10 Monte Carlo simulations for each K and plot average relative absolute errors (over Monte Carlo simulations) w.r.t. K. Compare the resulting curve with a curve that decays like 1/√K visually. You do not need to get good relative errors here, but attempt at demonstrating the rate. Due to randomness, this curve may not exactly decay like 1/√K, but it should be close enough. (4 marks) 8. Plug this IS estimator into the MH ratio to obtain a pseudo-marginal Metropolis Hastings (PMMH) method as shown in the lecture notes. Describe the method and the algorithm in detail. (2 marks) 9. For numerical results, you may have to tune σI(2)S and σM(2)H for the best performance (do not assume the values you optimized above will work). Set N = 10000 (set an appropriate burnin stage). Run the PMMH sampler for K = 101 , 102 , 103 , provide autocorrelation functions for each case. Comment on the effect of K on mixing. Visualise the samples drawn for K = 103 case. How do these samples compare to the samples in Part 2? Elaborate. (5 marks) Q2: IMPORTANCE SAMPLING FOR A HIDDEN MARKOV MODEL Assume that we would like to understand the performance of a self-normalised importance sampler (SNIS) for the posterior sampling task p(x0:n|y1:n) in a state-space model. Given a linear-Gaussian hidden Markov model: for n = 1, . . . , T. For fixed T, we assume the following scalar parameterization: m0 = 0, P0 = 1, A = 0.9, Q = 0.01, H = 1, R = 0.1. 1. Describe a procedure to simulate data from this hidden Markov model above and implement it. To demonstrate the implementation, simulate different lenghts of data T = 2, . . . , 20 to demonstrate your function, plot x0:T vs. y1:T (observations, scattered) for each T. Note that each dataset is generated independently, i.e. the dataset with T = 2 is completely different from T = 3. When plotting, pay attention to indexing as states are indexed from 0 and observations are from 1. Store these datasets and do not modify them as they will be used below. (2 marks) 2. Describe a Kalman-based strategy to estimate the mean of the posterior distribution p(x0:T |y1:T), i.e., for each T = 2, . . . , 20 using the datasets generated in Part 1. We denote this mean m0(T:T) for T = 2, . . . , 20 (we index the estimator with T to stress the fact that the datasets used for the estimators are different). (3 marks) 3. Implement this method and obtain the estimate m0(T:T) for T = 2, . . . , 20. Plot them vs. true states you have generated in Part 1 (this would be a separate plot for each T = 2, . . . , 20). Store these estimates m0(T:T) , as they will be used below. (3 marks) 4. Derive a self-normalised importance sampling (SNIS) estimator for the quantity m0:T, i.e., the mean of the posterior p(x0:T |y1:T). Use a proposal of the form. where q(xk ) = N(0, σI(2)S ). Derive the SNIS estimator for the mean, denote it m(¯)0(T:T) . (2 marks) 5. Run the estimator for K = 10000 particles for the dataset for T = 2 and record the SNIS estimate m(¯)0(2:2) . Compare this to the estimate visually to the estimate you obtained in Part 2 for T = 2 namely m0(2:2) . You will have to tune σI(2)S for a good performance. (3 marks) 6. Run the SNIS estimator for T = 2, . . . , 20. Choose an appropriate σI(2)S for a good performance (a good candidate is the one in previous part) and take K = 10000. Provide two plots: (i) The effective sample size (ESS) value vs. T = 2, . . . , 20 and (ii) the normalised mean squared error: vs. T = 2, . . . , 20. Comment on the results. What trend do you observe as T grows? What conclusions can you draw from this for estimating expectations with growing state-space dimension? (5 marks)
FV3201 Individual Assignment Brief (2024 – 2025) The work shall be typed or word-processed in your own words. The deadline for submission is 11:59 p.m. (HKT) on 3 April 2025 (Thursday). Learning Outcomes This piece of assessment will test your ability to meet learning outcomes as described hereunder: • Demonstrate critical thinking and problem solving (learning outcome 1) • Exhibit creativity and innovation in technical design (learning outcome 2) • Critically review and analyse client and user requirements, technical briefs and apply significant knowledge to design scenarios, including relevant technological, engineering, legal,health and safety and development factors (learning outcome 3) Assignment This assignment contains 2 questions. Answer all questions with words not exceeding 3000. The assignment will carry 50% weighting of the total mark of this module. Submission Details (1) The deadline for submission is 11:59 p.m. (HKT) on 3 April 2025 (Thursday). Late submission will be dealt with strictly in accordance with UCLan Regulations. (2) No hard copy is required to be submitted to the SCOPE counter. This assignment should be submitted through Turnitinto CityU SCOPE CANVAS assignment submission folder. (3) In-text citations and referenced publications shall be added to the answer to each question. (4) Using AI-generated text to complete your assignment is prohibited. Citation of Harvard style shall be used for all quoted references. UCLan regards any use of unfair means in an attempt to enhance performance or to influence the standard of award obtained as a serious academic and/or disciplinary offence. (5) Submission of written assignment shall be type-written in .pdfor .docx format. The file name of your submission shall follow the format as the example below: FV3201_CHAN Tai Man_G12345678 (6) Students should do whatever means to make sure the files are duly submitted via the CANVAS system and check whether the work is successfully uploaded (by downloading the file from CANVAS again). All claims on technical problem without strong evidence for unsuccessful uploading shall not be accepted. (7) It should be the students’ responsibility to double-check the readability (pdf or docx format) of the submitted files. (8) Administration team will not remove or replace student’s submitted assignment in CANVAS or help students to upload the soft copy of his/her assignments to CANVAS. FV3201 Individual– Assignment This assignment requires the student to complete following ALL questions. This assessment counts toward 50% of your mark for this module, in assessing situation that concerning ethics, technical, practical issues in Code of Practice and fire engineering. Based on Fire Engineering Approach, please: i. Propose and discuss the Fire Safety Strategy for an Atrium in a shopping mall (section plan is provided in the following); (40 Marks) ii. If there is no full fire barrier between Atrium and connected floors, design the smoke extraction system in the Atrium for both static system and dynamic system based on your assumption of the smoke layer criteria. Two fire locations in the plan should be considered. The length of corridor is assumed to be 10 m. The design should be based on engineering equations. Details of calculation procedures should be included. (60 Marks) Please refer to the following section plan for reference. This assessment counts toward 50% of your mark for this module, in which: • 30% Knowledge • 30% Analysis • 20% Engineering Principle/Calculation • 20% Structure A comprehensive list of references cited should be included. Marking Criteria Marks will be allocated according to the following criteria: Marking Criteria Marks allocation Knowledge of relevant material and grasp of themes: Students to use own words in demonstrating awareness and appreciation of key issues. 30% Analysis, synthesis and depth of argument: Identification of key points and justified put forward clearly and succinctly. 30% Engineering principle/calculation: Correct application of concept/formulae with complete accuracy and correct answer. 20% Structure: Logical structure with introduction, background and executive summary. 20% Total 100
