This assignment is an opportunity for students to learn more about how iterators work in STL by implementing a container and its iterators such that various STL algorithms will *just work* with it.Your task is to provide implementations for all of the methods of the `simple_linked_list` class, which is declared in `simple_linked_list.decl.h`. Your code to implement them will go into the file `simple_linked_list.h`.**NOTE:** This assignment will use some of the algorithms from your previous assignment, so don’t forget to add/commit/push your last assignment’s `assign2-algos.h` to this assignment’s repo.### NotesRemember to continue with our routine of creating a `development` branch and making all changes to that branch, leaving `main` entirely alone. This will be necessary to submit the pull request at the end, signaling completion of your program to the graders.There is one file that you should do your work in, `simple_linked_list.h`. Do not commit/push any changes to the other files, but do add/commit/push a copy of your working `assign2-algos.h` from the previous assignment.You should feel free to create whatever files you want to test things locally, including writing your own simple programs to test small parts on their own, but none of them should end up becoming a part of your remote repo. I actually *encourage* you to write unit test programs for yourself, but they should not be a part of your submission.**DO NOT ADD OR COMMIT THE EXECUTABLE FILES CREATED WHILE COMPILING.** They are big and we will be compiling anyway.### Implementing an STL-style Linked ListAlthough a doubly-linked list is already implemented in the STL in the form of `std::list`, and you should use it in the future when you need a linked list, there is a lot to be learned by writing your own STL-style container and watching iterator-based generic algorithms “just work” on it.Toward that end, you will be implementing the member functions for several classes, which are declared in `simple_linked_list.decl.h`, but that you should define/implement in `simple_linked_list.h`:#### `linked_node`This is the class that handles your individual linked list nodes. It is already complete, and you don’t need to implement anything for it, but a brief explanation of the members follows:– `data` will store the value for the current node – `next` will point to the next node in the list, or be `nullptr` if there is no such node. – The constructor is provided for convenience, and it allows you to construct a node with the value and/or the next node pointer already set.#### `simple_linked_list`This the class that provides the STL-style interface to your linked list. It is also declared in `simple_linked_list.decl.h`, and the important data members are:– `head` – a pointer to the first node in the linked list, or `nullptr` if it’s empty. – `tail` – a pointer to the last node in the linked list, or `nullptr` if it’s empty.The only method that comes implemented is the default constructor. You will need to implement everything else (in `simple_linked_list.h`)– Range constructor: `simple_linked_list(ITERATOR, ITERATOR)` – Initializes the list to a working state, then iterates over the range provided, adding each element to the linked list in order. This will only be called with valid iterator ranges.– `empty()` method – This method should return `true` if, and only if, there are no nodes in the linked list.– `begin()` method – This method should return a `simple_linked_iterator` that points to the head node.– `end()` method – This method should return a `simple_linked_iterator` that would compare `==` an iterator that is off the end of the list.– `front()` method – This should return a reference to the data member of the head node. Although this is obviously invalid when called on an empty list, the responsibility for checking falls upon the person using it, and you’re allowed to crash when they try.– `back()` method – This should return a reference to the data member of the tail node. Once again, although this is obviously invalid when called on an empty list, the responsibility for checking falls upon the person using it, and you’re allowed to crash when they try.– `pop_back()` method – Modify the linked list to remove the last node.– `push_back(T)` method – Add a new node containing the provided value to the end of the linked list.– `size()` method – Returns how many elements are currently in the linked list.– `clear()` method – Remove all of the nodes from the linked list to reset it to an empty state.– Destructor: `~simple_linked_list()` – This is called when your container goes out of scope, and is responsible for making sure to `delete` any `new` objects you created.#### `simple_linked_iterator`This is the class for the iterators exposed by `simple_linked_list` above. The only data member it has is the `pos` value, which is a pointer to one of the `linked_node` linked list nodes used by your linked list.You need to implement the methods so that they work properly as iterators when used in an algorithm. This will mean implementing the following methods (in `simple_linked_list.h`):– Constructor: `simple_linked_iterator(linked_node *)` – This one is actually already implemented, and allows you to construct the iterator already pointing to the given node. – Preincrement: `operator ++ ()` – Called when you increment your iterator with `++` *before* the name, i.e. `++i`. This changes the current iterator so it points to the next node, and returns a reference to the current iterator, which will be at the new position. – Postincrement: `operator ++ (int)` – Called when you increment your iterator with `++` *after* the variable name, i.e. `i++`. This also changes the current iterator so it points to the next node, but it returns another iterator that points to the original node position. – Dereference: `operator * ()` – This should return a reference to the `data` member of the `linked_node` that the current iterator points to. Checking to make sure that it’s okay to dereference is the responsibility of something else, so if someone tries to dereference something invalid, failure here is their fault, not yours. (You won’t hear that often.) – Comparison: `operator == (simple_linked_iterator &)` – This returns `true` if and only if both `simple_linked_iterators` (`*this` and the parameter) are pointing to the same node.### How To SubmitLike the other assignments for this semester, we will be doing submissions through GitHub. Make sure you do all of your development in the `development` branch. You can commit as many times as you need to, but keep in mind that this will grow the size of your repo and you may run up against the quota on turing/hopper if it gets too big.When you are finished implementing everything required and the test program is working properly, make sure you add, commit, and push the working version to the repo. Once that is done, **SUBMIT** a pull request but **DO NOT ACCEPT IT**.### Grading Considerations– Does it compile? Does it run? If it doesn’t compile and run on turing/hopper with the `Makefile` provided, no points will be awarded. – Does the output match? I have provided reference output for the driver program, so you can compare your program’s output to what is expected. This output can be found in `container.refout` – Did you change files you’re not allowed to? There are warning messages at the top of several of the files telling you not to make changes. If you make changes to these, you will receive a grade penalty. You can write your own test programs if you’d like, but do not commit them or push them to the server, and make sure the only modifications that make it to GitHub are the required ones. – Are there any memory leaks? There is a potential, when working with linked lists, to mess things up and leak memory. There is a program called `valgrind` that can/will be used to check for that. – Did you indent your code? – Indentation aids in the readability of source code, and if you’re not indenting your code blocks, the grader will legitimately dislike you for it. I’m authorizing them to mark you off if you subject them to reading that. – Did you document your code? – You need a docbox at the top of every one of the files you’re required to change including: – Your name – Your zid – Your GitHub ID – Your course section – A description of what the program does – You should add a docbox for every function that you implement, explaining what it does and what each parameter is for. – Add other comments inside your code blocks describing what you’re doing and why. – The use of `doxygen` style comments is encouraged, but not required.
Step 1: Get a GitHub AccountIn order to complete this assignment, you will need to have an account at [GitHub (`https://github.com`)](https://github.com). If you do not have one yet, it will be necessary to create one.### Step 2: Accept the Assignment InvitationYour professor will provide you with a link to the GitHub Classroom Assignment. You will need to click that invitation link and accept it. This will create a personalized `git` repo for you on GitHub that you will use to complete the rest of the assignment. GitHub will provide you with a link to that repo that you should keep, as it will be used in the steps below.### Step 3: Clone your Repo to Turing/HopperYou will need to clone the repo from the link that GitHub generates for you after acceptance of the invitation. This creates a local (to the NIU server) copy that can be edited as needed, and you can compile and test your code on this copy.`git clone YOUR_REPO_URL_GOES_HERE`When interacting with the remote (GitHub version) repo, you will be required to log in. GitHub used to accept text username/password authentication, but they made a decision to disable that authentication method, so you will need to choose one of the methods that still works and configure your Turing/Hopper session to use that when talking to GitHub.#### SSH Public Key Authentication (Recommended)One common method of authentication is to use asymmetric encryption. You generate a pair of cryptographic keys; one private (don’t ever share it), and the other public (this is the one you can share). You can use the `ssh-keygen` program on Turing or Hopper to generate your keys, and put the public key information in your GitHub account settings. This is more secure than the other option, and I recommend that you choose this.GitHub has documentation on how to do this: [https://docs.github.com/en/authentication/connecting-to-github-with-ssh/generating-a-new-ssh-key-and-adding-it-to-the-ssh-agent](https://docs.github.com/en/authentication/connecting-to-github-with-ssh/generating-a-new-ssh-key-and-adding-it-to-the-ssh-agent)John Winans recorded a video for a previous section of CSCI 340 where he went through these steps, which can be viewed at [https://www.youtube.com/watch?v=CdZa8MzLtjQ](https://www.youtube.com/watch?v=CdZa8MzLtjQ)#### GitHub Token AuthenticationYou can generate a token (a unique alphanumeric string used for authentication purposes) in the GitHub website’s settings, and make sure that the correct environment variable contains that token when the `git` command looks for it. This involves having your token in an environment variable that could potentially be read by other programs, so it’s not as secure as the SSH method above. There are instructions on the GitHub site if you want to go this route.### Step 4: Create a `development` branchA `git` repo can contain several simultaneous versions of your source code. The default branch is called `master` or `main`.You need to create a new branch, called `development`, and all of your work will be done on that branch.Creating the branch is as simple as typing `git branch development` in the directory you cloned the repo to.Once the branch is created, you can change to the new branch with `git checkout development`. Make sure you are in this branch when adding files and committing changes.**WARNING: YOU WILL LOSE POINTS IF YOU COMMIT ANY CHANGES IN THE `main`/`master` BRANCH.**### Step 5: Add Necessary Comments to the File and CommitWhen you clone the repo from GitHub, there will already be several files present. They implement a simple program that has been intentionally broken. **Before** we worry about fixing the program, we’re going to add some documentation, and commit that documentation to the repo.You must add a documentation box at the top of the `assign1.cc` file, in the following format:~~~~~ {.text} /********************************************************************************************** * NIU CSCI 340 Section YOUR_SECTION * * Assignment 1 * * YOUR FULL NAME – YOUR Z-ID – YOUR GITHUB USERNAME * * * * I certify that everything I am submitting is either provided by the professor for use in * * the assignment, or work done by me personally. I understand that if I am caught submitting * * the work of others (including StackOverflow or ChatGPT) as my own is an act of Academic * * Misconduct and will be punished as such. * * * **********************************************************************************************/ ~~~~~ **Make sure you provide your own name, section number, ZID, and GitHub username in this comment. If the grader cannot find this information, they will not be able to assign you a grade for your work.****DO NOT MAKE ANY OTHER CHANGES TO THE FILE AT THIS STAGE. THERE IS AN INTENTIONAL BUG THAT YOU SHOULD LEAVE UNFIXED FOR NOW**Once you’ve added the comment to your file, save the changes, and use `git` to add the changes to the `development` branch. This can be achieved with `git add assign1.cc`.Having added the file to the list of files whose changes will be committed, you will now be ready to do your first commit. This is as simple as typing `git commit` and typing an appropriate description of the changes you made to the code at the prompt provided.Note that commits are done to the local copy of the repo (on turing or hopper). When you’re ready for those changes to appear on the remote, GitHub repo, you will need to push those changes over.### Step 6: Fix What is BrokenIf you run `make`, you will notice that the current code does not compile. There was an error intentionally left in the C++ file. It is not hard to find, so go ahead and fix it, then repeat the process of adding the file, committing the new change separately from the commit where the comment was added.### Step 7: Push your local commits to the remote serverGraders won’t have access to your local copy of the repo, so you’ll need to make sure that the commits that you have done are present on the remote server. This is done with the command `git push`. When you run this, `git` connects to the remote server (GitHub) in this case, and all of the changes you’ve commmitted are sent to the server, where they will be visible to anyone with access to the remote repo.### Step 8: Signal your completion of the assignment by adding a pull requestWhen you have completed the earlier steps, go to your repo link in your web browser and add a pull request. A pull request is a request to have changes present in a branch merged into the `main`/`master` branch. It allows teams to work separately and have their work safely added in when done.**We** are using pull requests because they’re a good way of signaling that you have completed your assignment. You will not be able to add a pull request if you did all of your changes in the `main` or `master` branch, so it is very important to have followed the instructions to do your work in the `development` branch only.**DO NOT ACCEPT THE PULL REQUEST. JUST CREATE IT AND LEAVE IT THERE FOR THE GRADER TO SEE**### Grading Considerations– The comment inserted in the first commit should match the one provided, with your information inserted in the appropriate locations. – Did you put your name/section/zid in the comments? If we can’t link the repo to your real identity, we can’t give you any points. – You must have created and used the `development` branch. No changes should be committed in the `main` or `master` branch. – The second commit must fix the error in the file, and it must compile. Do not commit before this is the case. – The TA will be checking your repo for the pull request before considering your work to have been submitted. Make sure you make the pull request before the assignment deadline. – Although you can make whatever changes you want to your local repo, no changes other than the ones required should be committed to the repo.
In this assignment, the student will write several algorithms that use iterators to perform some simple computing tasks. They will be implemented using template functions so they will be able to be applied with any type of iterator (forward or better).I have included a `Makefile`, so you can compile this by typing `make` at the command line and hitting enter. Source code for two driver programs is included:– `do_ints` – a program that uses the functions you write to tokenize some sequences of integers and calculate various statistics along the way. You can look at the code in `do_ints.cc`, but do not make changes to that file. – `do_strings` – a program that uses the functions you write to split up some strings. You can see the code in `do_strings.cc`, but do not make changes.Both of these programs are complete **except for** the functions that are declared (but not defined) in `assign2-algos.decl.h`. You are responsible for implementing all of them. Make sure you put those in the `assign2-algos.h` file and nowhere else.### NotesRemember to continue with our routine of creating a `development` branch and making all changes to that branch, leaving `main` entirely alone. This will be necessary to submit the pull request at the end, signaling completion of your program to the graders.You will implement the required functions in the file `assign2-algos.h`. Do not commit/push any changes to the other files.You should feel free to create whatever files you want to test things locally, including writing your own simple programs to test small parts on their own, but none of them should end up becoming a part of your remote repo, and make sure you don’t change the files that have warnings not to change them.**DO NOT ADD OR COMMIT THE EXECUTABLE FILES CREATED WHILE COMPILING.** They are big and we will be compiling anyway.### Iterator Algorithms – Statistics and OutputIn `assign2-algos.h`, you will need to implement **all** of the templated functions that were declared in `assign2-algos.decl.h`.I recommend starting with the algorithms detailed in this section, as they will be slightly easier than the other set, which is described in the next section.#### `range_sum`Iterate over the range provided, add up the elements, and return the sum.#### `range_avg`Iterate over the range provided, add up and count the elements, then calculate and return the average (mean) as a `double`.#### `range_minval` Iterate over the range provided, keeping track of the minimum value found. Return that minimum value.#### `range_maxval` Iterate over the range provided, keeping track of the maximum value found. Return that maximum value.#### `range_count` Iterate over the range provided, counting the number of elements that occur within the range. Return that count.#### `print_range( ost, begin, end, pre, sep, post, width )`– `ost` is the `std::ostream` that the output should be printed to. In general, people will want to use `cout`, but you should use the one passed in so that this function can write to other streams when needed. – `begin` is an iterator to the beginning of the range to be printed – `end` is the iterator just past the last valid element of the range to be printed – `pre` is a string that gets printed one time before anything else – `sep` (separator) is a string that gets printed between each element (but not before the first or after the last) – `post` is a string that gets printed after all of the elements have been printed – `width` is the width, in characters, of the column in which the elements’ values are printed, or 0 (zero) if you do not want to use a fixed size. Set `std::setw` for details.This function should iterate over the range given, and print out the elements with the formatting determined by the other parameters. I’ve called it several times with different parameters in both driver programs, so you can get an idea of what’s expected from the reference output, if it’s not already clear to you.#### `histogram( begin, end, nums, N, divisor )`A histogram is a tool used in statistics where data is subdivided into several sub-ranges, which we will refer to as bins, and the frequency of occurrence of values within each range is measured. This is typically displayed graphically on a bar graph, but we just care about the numbers for this function.The basic description of what you need to do for this function is to iterate over every element in the range `[begin, end)`, find out which bin that element belongs in, and increment the count for the appropriate bin. Make sure the counts are already at zero before you begin.You can assume that any sequence provided for this will contain types that can be ordered (it’d break if you couldn’t).– `begin` – iterator at the beginning of the sequence we’re computing a histogram for – `end` – iterator one past the last element of the sequence we’re computing a histogram for – `nums` – an object supports the subscript `[]` operator to access integers containing the bin counts. The type is templated, so this could easily be an array or a `vector`, but it could also be any object that can be used in the appropriate way. This function will assume that it is already set up so you can read from and write to integers with indices from `nums[0]` to `nums[N-1]` without a problem. – `N` – the total number of bins, and an upper bound on the indices used with `nums` – `divisor` – divide the number by this and use the quotient to decide which bin this fits in. If the quotient is less than zero or greater than `N-1`, then do not increment any of the bins.### Iterator Algorithms for Splitting RangesThese functions, which you will implement using the iterator pattern, are useful for splitting a long sequence into smaller sub-sequences, which we shall call tokens.Although the `do_strings` driver program will use a `std::string` and the `do_ints` driver program will use a `std::vector` or a `std::list` to provide the iterators your functions will be called with, you should make sure that your algorithms are written in such a way that *any* forward iterator (or better) can be used without having to rewrite your function.We have not yet covered *exactly* what that means in lecture, but make sure you follow these rules:– While you can store your iterator’s current position into another iterator to keep track of where you were, you cannot rewind an iterator. Assume there is no `–` available for that. – Do not assume that it’s possible for your iterator to move more than one step at a time. Do not try to use pointer arithmetic or subscript operators, as this needs to be able to work on sequences that don’t support random access.Note that `std::string` can work like any other STL container, in that it has `begin()` and `end()` methods that can be used to iterate over the individual characters in the string. Similarly, you could use these algorithms with character arrays if you pass a pointer to the 0th element as its “begin”, and a pointer to the element after the last valid character (where the null character would be in a null-terminated string) as its “end”.#### `iter_token_info`This a `struct` (If you’re not familiar with structs, think of them as classes but with everything public by default). It will be used by the `get_next_token_*` functions to track where successive calls left off so they can continue until the end.– `b` – Your functions will be responsible for setting this iterator to point to the beginning of the token found. – `e` – Your functions will be responsible for setting this iterator to point right after the last element of the token found. – `n` – Your functions will be responsible for setting this iterator to point the beginning of the next token, or to then actual end of the range if there are no further tokens. – `begin()` – Returns an iterator to the beginning of the token that was found. This is useful because it allows you to use the range-based for loop on this to iterate over the sub-range represented. – `end()` – Returns the iterator representing the end of the half-open range representing the token that was found.#### `get_next_token_strict ( begin, end, delim )`, `get_next_token_greedy ( begin, end, delim )`These functions will start at `begin` and iterate until it either reaches the `end` iterator, or finds an element in the range that has the value `delim`.Your function will be responsible for setting the members of the `iter_token_info` returned appropriately. The `b` will be set to the iterator representing the beginning of the token, and the `e` member will be set to the location immediately past the end of the token, or to `end` if we reach the end of the input range.The `n` member of the `iter_token_info` struct returned must point to the beginning of the next token, or to the end of the range if no more tokens are to be found. How this is determined will be the main difference between the “strict” and “greedy” versions.– `begin` – Where to begin the search for a delimiter. – `end` – The end of the range to search. If we reach this, there are no more elements to form tokens with. – `delim` – the delimiter value, when it is found in the range, it is used to indicate that one token has ended#### Strict vs. GreedyFor the “strict” version, every delimiter begins a new token, and a delimiter found immediately after another delimiter will indicate the presence of a zero-length token. This is useful for situations like tab- or comma-separated values files, where you want the delimiter to start a new field and would actually like to be able to leave fields blank.For the “greedy” version, once a delimiter is found, the next token starts at the next position that is not a delimiter. That means that if we have several delimiters in a row, they are “eaten” and do not indicate empty tokens. One time this can be useful is in handling for whitespace in strings when you don’t want the number of spaces to matter, which is the case when parsing HTML or similar languages.“` // Let’s do an example tokenizing of integers using 0 as the delimiter source sequence: { 100 200 300 0 0 0 5 6 0 7 8 9 }strict token 0: { 100 200 300 } strict token 1: { } // empty strict token 2: { } // empty strict token 3: { 5 6 } strict token 4: { 7 8 9 }greedy token 0: { 100 200 300 } greedy token 1: { 5 6 } greedy token 2: { 7 8 9 }“`### How To SubmitLike the other assignments for this semester, we will be doing submissions through GitHub. Make sure you do all of your development in the `development` branch. You can commit as many times as you need to, but keep in mind that this will grow the size of your repo and you may run up against the quota on turing/hopper if it gets too big.When you are finished implementing everything required and the test programs are working properly, make sure you add, commit, and push the working version to the repo. Once that is done, **SUBMIT** a pull request but **DO NOT ACCEPT IT**.### Grading Considerations– Does it compile? Does it run? If it doesn’t compile and run on turing/hopper with the `Makefile` provided, no points will be awarded. – Does the output match? The output from your implementation will be tested against the output from the reference implementation for both driver programs. I have provided reference output for each of the driver programs, so you can compare your program’s output in advance. This output can be found in `do_ints.refout` and `do_strings.refout`. – Did you change files you’re not allowed to? There are warning messages at the top of several of the files telling you not to make changes. If you make changes to these, you will receive a grade penalty. You can write your own test programs if you’d like, but do not commit them or push them to the server, and make sure the only modifications that make it to GitHub are the required ones. – Did you indent your code? – Indentation aids in the readability of source code, and if you’re not indenting your code blocks, the grader will legitimately dislike you for it. I’m authorizing them to mark you off if you subject them to reading that. – Did you document your code? – You need a docbox at the top of every one of the files you’re required to change including: – Your name – Your zid – Your GitHub ID – Your course section – A description of what the program does – You should add a docbox for every function that you implement, explaining what it does and what each parameter is for. – Add other comments inside your code blocks describing what you’re doing and why. – The use of `doxygen` style comments is encouraged, but not required.
Goal To design databases (E-R diagram and schemas) discussed in chapter 7. Q1 (10 points) Suppose an automobile company (e.g., Toyota) hired you to design a database to assist • Its dealers for maintaining customer records and dealer inventory • Sales staff in ordering cars. The database needs to store information about • Brands (e.g., Toyota, Lexus) • Models (e.g., Camry, Rav4) • Options (e.g., Basic, premium, Prestige) • Individual dealers (e.g., Wilson Motors) • Customers • Vehicles/Cars You need to remember the following information: • Each brand is identified by brand name (e.g., Toyota, Lexus). • Each model has model_id and name. Each model is identified by the model_id. • Each model must be associated with a brand. i.e., there is no model without a brand. • Each vehicle is identified by VIN (vehicle identification number). • Each vehicle must be associated with a model, i.e., there is no vehicle without a model. • Each model may have many options. For instance, the Rav4 model has three options (e.g., LE, XLE, LE Hybrid). • Each option can have option_id and specification. Each option is identified by option_id. • Each dealer has dealer_id, name, and address. Each dealer is identified by dealer_id. • Each customer has customer_id, name, and address. Each customer is identified by customer_id. • Each vehicle may be associated with a dealer. • Each vehicle may be associated with a customer. (7 points) Draw an E-R diagram to represent the database mentioned above. You must keep the following in mind. • There are 6 strong entity sets and NO weak entity sets. Some entity sets might have a single attribute. • There are 12 attributes and all of them are simple and single-valued attributes. • There are 5 binary relationship sets. There are no other types of relationship sets (e.g., ternary). • NO relationship set has any descriptive attributes. • There are 2 total participation. • In your ER diagram, you will also have to do the following: o Identify the attributes for each entity set. Please underline the primary key. o Specify the cardinality (one to one, one to many, many to one, or many-many) of the diagram. (3 points) Determine the Relation Schemas from the E-R diagram. No optimization is required. Q2 (10 points) Suppose a worldwide packet delivery company (e.g., FedEx) hired you to design their database. The database needs to store information about • customer • packet • place You need to remember the following information: • Each customer has a unique customer_id. Each customer also contains their name and address. • Each packet has packet_id and weight. Each packet is identified by its packet_id. • Each place or location has place_id, city, country, and address. Each place can be identified by place_id. • Each packet must be associated with a place, i.e., there is no packet without a place. • Each packet must be associated with a customer, i.e., there is no packet without a customer. The association between customers and packets can be in one of the following ways: o Customer who sends packets. In this case, the customer provides the time_sent information, i.e., when the packet was sent. o Customer who receives packets. In this case, the customer provides the time_recieved information, i.e., when the packet was received). o Some customers may play the role of both sender and receiver. (7 points) Draw an E-R diagram to represent the database mentioned above. You must keep the following in mind: • There are 3 strong entity sets and NO weak entity sets. • There are 9 attributes for the entity sets and all of them are simple and singlevalued attributes. • There are 3 binary relationship sets. There are no other types of relationship sets (e.g., ternary). • Two relationship has two descriptive attributes • Two entity sets may be related by two separate relationship sets. • There are 3 total participation. • In your ER diagram, you will also have to do the following: o Identify the attributes for each entity set. Please underline the primary key. o Specify the cardinality (one to one, one to many, many to one, or many-many) of the diagram. (3 points) Determine the Relation Schemas from the E-R diagram. No optimization is required. What to submit All E-R diagrams and Relation schemas. Submission Instructions • Put all E-R diagrams and Relation schemas in one single doc/docx file. • Convert the file to a pdf file. The file name should be YourLastName-330-HW4.pdf. • Upload the pdf file on canvas. Late Policy • No late work will be accepted
Goal The goal of this homework is to learn and practice more SQL commands (both basic and intermediate) for MySQL. What to do 1. We will use a publically available database named Chinook https://github.com/lerocha/chinook-database Below is the schema of this database: 2. Download the SQL script (Chinook_MySql.sql) available on canvas. We collected this SQL script from the website. Execute this script to create the Chinook database and insert values for the tables. It might take several minutes to finish executing the entire script (~16K lines of SQL code). 3. Write SQL queries for the following. a. Find distinct track names that start with “Z.” Sort the output alphabetically. (3 points) b. Find the first names of the employees who are older than their supervisor. Hint: ReportsTo attribute in Employee table stores the EmployeeId of the supervisor. Sort the output alphabetically. (3 points) c. Find the name of the highest-priced track. If more than one track has the highest price, return the names of all such tracks. Sort the output alphabetically based on the track name. (3 points) d. Find a list containing the total amount spent by a customer. Include the customer’s id and the last names along with the total amount. For customers who did not make any purchase, make sure to include them as well. (3 points) e. Find the title of the highest-priced album. (3 points) f. Find a distinct list containing the titles of albums that are never sold. Consider an album never sold if none of its tracks are sold. Sort the output alphabetically. (3 points) g. Create a view that returns customers’ first and last names along with corresponding sums of all their invoice totals. Name the view as “CustomerInvoices.” (2 points) What to submit You have to submit all the SQL queries and the output of the query. If the output contains more than six tuples, then give the top six tuples. Submission Instructions Put all SQL queries and output in one single doc/docx file. Convert the file to a pdf file. The file name should be YourLastName-330-HW3.pdf. Upload the pdf file on canvas. Late Policy: No late work will be accepted. Questions? If you have any questions, please first check the FAQ page on canvas to see if the question is already answered.
Goals The goals of this homework are as follows: To become familiar with basic SQL commands in MySQL. o To create a database o To insert data into tables o To write basic SQL queries The SQL commands from chapter 3 will be sufficient for this homework. We will use a software called “MySQL Workbench” to write the SQL query in our class. We recommend installing MySQL workbench on your computer. There are numerous online tutorials and YouTube videos available to learn how to install and use MySQL workbench. Some examples: o https://www.youtube.com/watch?v=OM4aZJW_Ojs&ab_channel=WebDevSi mplified (For Windows) o https://www.youtube.com/watch?v=-BDbOOY9jsc&ab_channel=AmitThinks (For Mac) o https://www.youtube.com/watch?v=iLRY-NfXXsA&ab_channel=AmitThinks (for Ubuntu) If you prefer not to install MySQL workbench on your computer, you may use a freely available online editor. Some examples: o https://paiza.io/en/languages/mysql o https://extendsclass.com/mysql-online.html What to do 1. Create a University Database: Use the SQL script (create_university.sql), which is available on canvas, to create the following university database (see figure 1). Figure 1: University database 2. Populate the university database with Data: Use the SQL script (insert_university.sql), which is available on canvas, to populate the seven tables (see below) of the university database department instructor course student section teaches Takes 3. Write SQL queries for the following (2*8 = 16 points) a. Find courses that taught either in Fall 2009 or in Spring 2010. b. Find all instructors earning the highest salary (there may be more than one with the same salary). c. Find names and average salaries of all departments whose average salary > 42000 d. For each department, find the maximum salary of instructors in that department. You may assume that every department has at least one instructor. e. Find the names of all students who have taken any Comp. Sci. course ever (there should be no duplicate names) f. Find the enrollment of each section that was offered in Spring 2009. g. Find the maximum enrollment, across all sections, in Spring 2009. h. Delete all courses that have never been offered (that is, do not occur in the section relation). Submission Instructions Please put all of your SQL queries and their corresponding results (in table format) in one PDF file. The file name should be YourLastName-CSCI330-HW2.pdf. Upload the pdf file on canvas. Late Policy No late work will be accepted.
Description of Input File and Problem Statement The name of the input file is StockmarketInput.txt, which is available in the Assignment section of your Canvas. This input file contains stock information for the last 25 years (1990-2015) for the following seven big technology companies: 1. Apple (AAPL) 2. Facebook (FB) 3. Google (GOOG) 4. International Business Machine (IBM) 5. Intel Corporation (INTC) 6. Microsoft (MSFT) 7. Yahoo (YHOO) This data is publicly available. The data is sorted by ticker symbol and date. Each line of the StockmarketInput.txt file contains the data for a particular stock (ticker symbol) for one day. The values are separated by a tab(‘t’). Here is an example from the data for Microsoft (ticker symbol MSFT): MSFT 8/18/2004 26.93 27.5 26.89 27.46 58844000 19.46 MSFT 8/17/2004 27.22 27.38 26.98 27.05 56879700 19.17 MSFT 8/16/2004 27.03 27.2 26.96 27.09 54347200 19.19 MSFT 8/13/2004 27.01 27.25 26.98 27.02 43333200 19.14 MSFT 8/12/2004 27.23 27.31 26.86 26.88 50279700 19.05 MSFT 8/11/2004 27.39 27.51 27.2 27.41 53097300 19.42 There are eight fields in each line. A description of each value of the first line (yellow marked) is given below. All other lines of this example, as well as the entire StockmarketInput.txt, will have similar meanings. 1. ticker symbol (MSFT), 2. date (8/18/2004), 3. opening price (26.93), 4. high price (27.50), 5. low price (26.89), 6. closing price (27.46), 7. volume or number of shares traded on that day (58844000 shares), and 8. adjusted closing price (19.46). The opening and closing prices are the prices of the first and last trade, respectively, on the given date. The high and low prices are the highest and lowest prices of any trade during the day. The adjusted price includes corrections to the price to make comparisons across days easier. What to do 1. For each company, identify the crazy days in terms of stock price fluctuation. Here is how to calculate the crazy days. Suppose at Date D, the high price of the share of company X is Hx, and Low price is Lx. Then D will be called crazy day if (Hx-Lx)/Hx >= 15% Let’s consider the example below (yellow marked), which is taken from StockmarketInput.txt. YHOO 4/5/2000 162 169.88 158.5 165.56 27371800 82.78 YHOO 4/4/2000 165 171 132.75 167.38 42528400 83.69 YHOO 4/3/2000 168.75 173 159.38 160.13 19322800 80.06 Notice that, for 4/4/200, the high price of the share for Yahoo was $171, and the low price was $132.75. The fluctuation of the stock price is (171-132.75)/171=22.37%, which is more than 15%. Hence, 4/4/2000 is considered as a crazy day for Yahoo. For this assignment, identity all crazy days for each company. Also, identify the craziest day for that particular company, i.e., on which day of the entire history of the stock price, the stock price fluctuated most. 2. Stock split: Occasionally, a stock may split by some ratio, say 2-for-1. This means that every old share is replaced by some number of new shares, in these case two. Each new share is worth some fraction of the value of the old share. In this case, each is worth half the old value. Thus, the value of each person’s holding will remain unchanged. We recognize such a stock split in the data when the closing value of day “x” is twice the opening value on the day “x + 1”, the next trading day. There is a complication at this point because the price of the first trade of the new day does not have to be the same as the price of the last trade of the prior day. The new opening price does not have to be exactly half of the previous day’s closing price. Let’s consider the example below (yellow marked), which is taken from StockmarketInput.txt. AAPL 3/1/2005 44.99 45.11 44.16 44.5 117047000 5.94 AAPL 2/28/2005 44.68 45.14 43.96 44.86 162902600 5.99 AAPL 2/25/2005 89.62 89.91 88.19 88.99 228877600 5.94 AAPL 2/24/2005 88.48 89.31 87.73 88.93 379757000 5.94 Notice that the closing price on 2/25/2005 was $88.99, and the opening price on 2/28/2005 was $44.68, giving a ratio of 88.99/44.68 = 1.991, which is slightly lower than 2. Nevertheless, AAPL stock experienced a 2:1 stock split on 1997.04.02, and the small variation is due to the initial trading activity on 2/28/2005as described above. To accommodate such variations, we use the following definition, where Cx is the closing price on day x and Ox+1 is the opening price on the next trading day x + 1. Definitions: A 2:1 stock split occurs if | Cx / Ox+1 – 2.0| < 0.20 A 3:1 stock split occurs if | Cx / Ox+1 – 3.0| < 0.30 A 3:2 stock split occurs if | Cx / Ox+1 – 1.5| < 0.15 Reminder: |x| represents the absolute value of the number x. For this assignment, you have to detect all splits of ratios 2:1, 3:1, and 3:2 using the above formulas. Note that “next day” when computing the closing/opening ratio is the next trading day, which may not be the next day on the calendar due to weekends, holidays, etc. For this assignment, adjacent lines in StockmarketInput.txt represent adjacent trading days. Output Your java program should read StockmarketInput.txt and output all splits, as defined above, to System.out. The output file named StockmarketOutput.txt is available on canvas. You have to follow the same format, as shown in the output file. Note that the split is attributed to the day with the higher closing price. The two prices are the closing price for the day of the split and the opening price for the next trading day. StockmarketInput.txt is ordered in descending chronological order, which means that the data for tomorrow comes before the data for today. Good Design and Style Although bad design and style will not hurt the performance of your program, it is of utmost importance, especially when you will work in the real world with other professionals, to follow good design and style for coding. It will be helpful not only for your colleagues to understand your code better but also for you as well when you will revisit your code later. Here are some guidelines for good design and style: The program is logically organized so that a reader can quickly and easily understand the program structure. Functions and variables have meaningful names. The program has a proper indentation. The program follows an object-oriented approach. Point Distribution Grading Criteria Points The program gives the correct output 14 The program has good design and style 2 The write up is complete (YourLastName-Assignment1.pdf) 2 The output format is correct 1 The filename format is correct 1 Submission Instructions You have to submit the following on Canvas. 1. Java source code. ▪ The file name containing the main method should be YourLastNameAssignment1.java. ▪ If you have more than one java files: • Please keep all java files in a single folder. • Zip the folder and name it YourLastName-Assignment1.zip. 2. A pdf file (Filename format: YourLastName-Assignment1.pdf) with the following write up (If you have zip file for your java source code in the previous step, please DON’T include PDF file in your zip file): ▪ Your full name ▪ Does your program compile correctly? Yes/No ▪ Does your program run correctly? Yes/No ▪ An acknowledgment and discussion of any parts of the program that are not working. Failure to disclose obvious problems will result in additional penalties. ▪ An acknowledgment and discussion of any parts of the program that appear to be inefficient (in either time or space complexity). ▪ How many hours did you spend on completing this assignment? ▪ Your expected score (please fill out the following table) Grading Criteria Points Possible Your Expected Score The program gives the correct output 14 The program has good design and style 2 The write up is complete (YourLastNameAssignment1.pdf) 2 The output format is correct 1 The filename format is correct 1 Upload the following two files on canvas 1. YourLastNameAssignment1.java or YourLastName-Assignment1.zip 2. YourLastName-Assignment1.pdf Late Policy: No late work will be accepted.
2. Problem Statement Using a database of stock price data, write a Java program that computes the gain or loss from the trading strategy described below (see the section titled “Processing”). 2.1 ConnectionParameters.txt For this assignment, you will need to access the database called johnson330, hosted at mysql.cs.wwu.edu. You should have read-only access to the johnson330 database. We have already provided your credentials to access the database on that server. Section 5.1 of our book discussed how to access the database from java. To connect to the database, you need an external text file named ConnectionParameters.txt. There are two good reasons for moving the connection parameters to an external text file: 1. Security. If you hardcode the connection parameters into your program, the password is vulnerable to some clever person decoding the executable. Also, disassembler programs (translate machine language to assembly language) do all the hard work of doing this for you. 2. Testing. You do not have to change a program to move it from a test environment to an operational environment. Moving the connection parameters to an external file enables this. If you are running your program from a lab computer, ConnectionParameters.txt should look as follows: dburl=jdbc:mysql://mysql.cs.wwu.edu/johnson330 user=your_user_name password=your_password_we_provided Please ensure that this external text file (ConnectionParameters.txt) doesn’t contain any extra lines at the end. 2.2 Remote Database Connection To connect to the remote database server (mysql.cs.wwu.edu) from off-campus computers (e.g., your laptop), first, you will have to install VPN (Virtual Private Network). Here are the details on how to do that: https://atus.wwu.edu/kb/vpn-virtual-private-network Second, you will have to set up SSH Tunneling using the following command in the terminal/command prompt/PowerShell. ssh -N -p922 –L4321:mysql.cs.wwu.edu:3306 [email protected] It will ask for a password; please use your CS password (which you use to log in to any lab computer). Here is a screenshot from Windows Command prompt. Please notice that after you enter the password, the cursor will go to the next line and start blinking. It means that the connection is successful. There will be no additional message. Since you are running your program from an off-campus computer, you need to change ConnectionParameters.txt in the following way: dburl=jdbc:mysql://127.0.0.1:4321/johnson330 user=your_user_name password=your_password_we_provided 3. Database Schema The database schema is as follows: Tables Columns Primary Key Foreign keys company Ticker Name Industry Location Ticker pricevolume Ticker TransDate OpenPrice Ticker TransDate Ticker HighPrice LowPrice ClosePrice Volume AdjustedClose dividend Ticker DivDate Amount Ticker DivDate Ticker We only need to use the first two tables (company and pricevolume) for this assignment. 4. Processing Your program should proceed as described below. 1 Connect to the database. 2 Repeat 2.1 Request a ticker symbol and optional start and end dates from System.in. The loop (step 2) exits, and the program terminates when an empty string, or a string containing only spaces, is submitted as input. 2.2 Retrieve the full company name from the company table and print it on the console. If the company is not found, indicate that the stock is not in the database and start the loop again by requesting user input. 2.3 Retrieve all the pricevolume data in the input data range for the ticker. If no dates were specified, retrieve all pricevolume data. Because the first analysis phase involves adjusting for splits, it is useful to request the data in reverse chronological order. For example, to retrieve the data for all dates for a ticker symbol INTC, you could use the following SQL: select * from pricevolume where Ticker = ‘INTC’ order by TransDate DESC 2.4 To prepare for the investment strategy computation (2.6 and following), scan the data in reverse chronological order, and identify stock splits: • A 2:1 stock split occurs if | Cx / Ox+1 – 2.0| < 0.20 • A 3:1 stock split occurs if | Cx / Ox+1 – 3.0| < 0.30 • A 3:2 stock split occurs if | Cx / Ox+1 – 1.5| < 0.15 Where Cx is the closing price on day x, and Ox+1 is the opening price on the next trading day x + 1. 2.5 To adjust for splits on a given day (meaning the split occurs between that day and the next day), all price data for the given day and earlier must be divided by 2 (or 3 or 1.5 depending on the split ratio). Each row of the pricevolume table represents one trading day, so the open, high, low, and close prices for that day must be adjusted. Note that after adjusting all price data on the given day, the algorithm must continue scanning to detect splits in the adjusted data. If another 2:1 split appears, for example, then earlier data, already adjusted for the first split, would again be divided by 2. You should be able to accomplish all adjustments in one pass over the data by keeping track of the total divisor. Initialize the divisor to one and adjust it upward as you encounter splits. 2.6 From this point forward, all references to price data refer to the adjusted data from the previous step. With the adjusted data stored in your program, scan forward in time to implement the following investment strategy. In the remaining steps, • d will refer to a trading day • (d+1) will refer to the next trading day • (d-1) will refer to the prior trading day • close(d) closing price for day d. • open(d) opening price for day d and so on 2.7 Maintain a moving average of the closing prices over a 50-day window. So for a given trading day d, the 50-day average is the average closing price for the 50 previous trading days (days d-50 to d-1). 2.8 If there are less than 51 days of data, do no trading and report a net gain of zero and repeat from step 2 to get the next user input. 2.9 If there are more than 51 days of data, compute 50-day average for the first fifty days. Proceeding forward from day 51 through the second-to-last trading day in the data set, execute the following strategy: • Track current cash and shares, both of which start at zero. When buying stock, cash decreases, and shares increase. When selling stock, cash increases, and shares decrease. Since cash starts at zero, we must borrow money to buy the initial shares. Disregard this complication. • (Buy criterion) If the close(d) < 50-day average and close(d) is less than open(d) by 3% or more (close(d) / open(d) = 100 and open(d) > 50-day average and open(d) exceeds close(d-1) by 1% or more (open(d) / close(d1) >= 1.01), sell 100 shares at price (open(d) + close(d))/2. • (Transaction Fee) For either a buy or sell transaction, cash is reduced by a transaction fee of $8.00. • If neither the buy nor the sell criterion is met, do not trade on that day. • Regardless of trading activity, update the 50-day average to reflect the average over the last 50 days, and continue with day d+1. 2.10 After having processed the data through the second-to-last day, if there are any shares remaining, on the last day, add open(d) * shares remaining to cash to account for the value of those remaining shares (No transaction fee applies to this). 5. Sample Output Database connection is established. Enter a ticker symbol [start/end dates]: INTC Intel Corp. 2:1 split on 2000.07.28 129.12 –> 65.44 2:1 split on 1999.04.09 130.81 –> 61.62 2:1 split on 1997.07.11 153.81 –> 77.25 2:1 split on 1995.06.16 116.12 –> 58.50 2:1 split on 1993.06.04 112.75 –> 60.12 3:2 split on 1987.10.28 31.75 –> 21.75 6 splits in 7470 trading days Executing investment strategy Transactions executed: 690 Net cash: 14717.72 Enter ticker symbol [start/end dates]: INTC 1980.01.01 1999.12.31 Intel Corp. 2:1 split on 1999.04.09 130.81 –> 61.62 2:1 split on 1997.07.11 153.81 –> 77.25 2:1 split on 1995.06.16 116.12 –> 58.50 2:1 split on 1993.06.04 112.75 –> 60.12 3:2 split on 1987.10.28 31.75 –> 21.75 5 splits in 3791 trading days Executing investment strategy Transactions executed: 358 Net cash: 44953.95 Enter ticker symbol [start/end dates]: T AT&T Inc 2:1 split on 1998.03.19 83.75 –> 42.12 2:1 split on 1993.05.25 74.75 –> 37.62 3:1 split on 1987.05.22 102.50 –> 36.00 3 splits in 7470 trading days Executing investment strategy Transactions executed: 260 Net cash: 2028.67 Enter ticker symbol [start/end dates]: T 2000.01.01 2014.08.18 AT&T Inc 0 splits in 3679 trading days Executing investment strategy Transactions executed: 148 Net cash: -1568.00 Enter ticker symbol [start/end dates]: BAC Bank of America Corp 2:1 split on 2004.08.27 89.01 –> 44.79 2:1 split on 1997.02.27 122.50 –> 61.25 2:1 split on 1986.11.20 42.62 –> 21.50 3 splits in 7116 trading days Executing investment strategy Transactions executed: 534 Net cash: 41846.00 Enter ticker symbol [start/end dates]: XX XX not found in database. Enter ticker symbol [start/end dates]: Database connection closed. 6. Constraints 1. You must use PreparedStatements when you are using SQL statements where values are filled in. This is a good practice for avoiding SQL injection attacks (A HUGE security issue). 2. You will likely need two SQL statements for reading the stock trading data from the database (step 2.3), one for no date range specified and one for a specified date range. You do not need to duplicate any remaining logic (2.4 and following from section 4) to handle those two separate conditions. 3. To help with round-off-error discrepancies, (a) do all computations with doubles, not floats, and (b) use the code in the following table: When the description says: Use the following: value = 1.01 value > 1.00999999 7. Hints 1. If you are having problems getting a connection established, here are some possible problems to check: a) If your program terminates with an SQLException with a message of the form “Access denied for user … (using password: YES),” that is most likely a problem with the userid or password. Check to ensure that these are correctly specified in your connection parameters file. b) If your program terminates with an SQLException with a message of the form “Access denied for user … to database …”, that most likely means that the userid and password are valid, but the database name (johnson330) is wrong, or the given userid doesn’t have permission to access that database. Make sure you’re using your userid. c) If your program terminates with an SQLException with a message of the form “Communications link failure,” that is a problem communicating with the database server. Check to ensure that the server is correctly specified and that you have the needed Internet connectivity. 2. Dates are stored in the database as character strings, not SQL date types. However, the date format (YYYY.MM.DD) means that string comparisons also give the correct answer as date comparisons. Therefore, for this assignment, you don’t need to decompose database dates; just continue to treat them as strings. 8. Good Design and Style Although bad design and style will not hurt the performance of your program, it is of utmost importance, especially when you will work in the real world with other professionals, to follow good design and style for coding. It will be helpful not only for your colleagues to understand your code better but also for you as well when you will revisit your code later. Here are some guidelines for good design and style: • The program is logically organized so that a reader can quickly and easily understand the program structure. • Functions and variables have meaningful names. • The program has a proper indentation. • The program follows an object-oriented approach. 9. Point Distribution Grading Criteria Points The program gives the correct output 48 The program obeys the constraints 5 The program has good design and style 2.5 The write up is complete (YourLastName-Assignment2.pdf) 2.5 The output format is correct 1 The filename format is correct 1 For the correct output (48 points), we will check the output of your program with six separate companies (8 points for each company). Suppose, if we check your program with INTC, then we will distribute the 8 points in the following way: 10. Submission Instructions • You have to submit the following on Canvas. 1. Java source code. ▪ The file name containing the main method should be YourLastNameAssignment2.java. ▪ If you have more than one java file: • Please keep all java files in a single folder. • Zip the folder and name it YourLastName-Assignment2.zip. 2. A pdf file (Filename format: YourLastName-Assignment2.pdf) with the following write-up (If you have a zip file for your java source code in the previous step, please DON’T include the PDF file in your zip file): ▪ Your full name ▪ Does your program compile correctly? Yes/No ▪ Does your program run correctly? Yes/No ▪ An acknowledgment and discussion of any parts of the program that are not working. Failure to disclose obvious problems will result in additional penalties. ▪ An acknowledgment and discussion of any parts of the program that appear to be inefficient (in either time or space complexity). ▪ How many hours did you spend on completing this assignment? ▪ Your expected score (please fill out the following table) Grading Criteria Points Your Expected Score The program gives the correct output 48 The program obeys the constraints 5 The program has good design and style 2.5 The write up is complete (YourLastNameAssignment2.pdf) 2.5 The output format is correct 1 The filename format is correct 1 • Upload the following two files on canvas 1. YourLastNameAssignment2.java or YourLastName-Assignment2.zip 2. YourLastName-Assignment2.pdf 11. Debugging Tips 1. Since this assignment deals with millions of data points, it is tough to determine the cause of the error if you get an incorrect output. Hence, for this assignment (and for the next assignment as well), you need to know how to debug the java code efficiently. Printing messages on the console might not be sufficient to find the problem. There are tons of tutorials and YouTube videos available on the web to learn how to use the debugger for Eclipse, jGrasp, IntelliJ, and jdb. Please feel free to look at the tutorials to learn how to do the debugging using your favorite java editor. 2. There are two log files (in .txt format) available on canvas. Besides using the debugging tool, you may look at these log files to find the problem if your program does not provide the correct output. These two log files are as follows: • transLog-INTC-1980.01.01-1999.12.31.txt • transLog-T-All Dates.txt The first log file contains the stock data for Intel Corporation from Jan 1, 1980 to December 31, 1999 and the second log file contains the stock data for AT&T for all dates available. Each line of these two log files has the following information: 1. date • Example: 1985.01.02 2. opening price • Example: open: 1.1666667 3. high price • Example: high: 1.1770833 4. low price • Example: low: 1.1354167 5. closing price • Example: close: 1.1458333 6. 50-day average [After first fifty days] • Example: average 1.2229167 7. Buy stocks [If buy condition fulfills] • Example: Buy: 1985.03.26 100 shares @ 1.0675000, total shares = 100, cash = -114.7500000 8. Sell stocks [If sell condition fulfills] • Example: Sell: 1999.11.22 100 shares @ 80.6900000, total shares = 0, cash = 44319.9479167 9. Final Sale [At the end of the file] • Example: Final sale: 1999.12.31 0 shares @ 83.8100000, cash = 44953.9479167 (average = 77.8544000) 12. Late Policy No late work will be accepted.
1. Bag-Difference. The operation Bag-Difference when applied to two bags results in a bag where each element appears as many times as it appears in the first bag, minus the number of times it appears in the second bag (but never less than 0 times). For example (bag-difference ‘(a a b a) ‘(b a a)) —>'(a) (bag-difference ‘(a b a a) ‘(a b c)) —>'(a a) (bag-difference ‘(a b c) ‘(a b a a)) —>'(c) (bag-difference ‘(a b c) ‘(a b c)) —>'() (bag-difference ‘() ‘(a b a a)) —>'() (bag-difference ‘(a b a a) ‘())—>'(b a a a) 2. Bag-Union. The operation Bag-Union results in a bag that contains the maximum number elements that are contained in the operands. For example (bag-union ‘(a a b a) ‘(b a a)) —>'(a b a a) (bag-union ‘(a b a a) ‘(a b c)) —>'(a a a b c) (bag-union ‘(a b c) ‘(a b a a)) —>'(c a b a a) (bag-union ‘(a b c) ‘(a b c)) —>'(a b c) (bag-union ‘() ‘(a b a a)) —>'(a b a a) (bag-union ‘(a b a a) ‘())—>'(a b a a) Page 2 of 2 3. Bag-Intersection. The operation Bag-Intersection results in a bag that contains the minimum number of elements that are contained in the bag operands. For example (bag-intersection ‘(a a b a) ‘(b a a)) —> ‘(b a a) (bag-intersection ‘(a b a a) ‘(a b c)) —> ‘(b a) (bag-intersection ‘(a b c) ‘(a b a a)) —>'(a b) (bag-intersection ‘(a b c) ‘(a b c)) —>'(a b c) (bag-intersection ‘() ‘(a b a a)) —>'() (bag-intersection ‘(a b a a) ‘())—>'() The solutions will be turned in by posting a single Racket program (lab07. rkt) containing a definition of all the functions specified.
Implement the following Racket functions: 1. Reflexive-Closure Input: a list of pairs, L and a list S. Interpreting L as a binary relation over the set S, Reflexive-Closure should return the reflexive closure of L. Examples: (Reflexive-Closure ‘((a a) (b b) (c c)) ‘(a b c)) —> ‘((a a) (b b) (c c)) (Reflexive-Closure ‘((a a) (b b)) ‘(a b c)) —> ‘((a a) (b b) (c c)) (Reflexive-Closure ‘((a a) (a b) (b b) (b c)) ‘(a b c)) —> ((a a) (a b) (b b) (b c) (c c)) (Reflexive? ‘() ‘(a b c)) —> ‘((a a) (b b) (c c)) 2. Symmetric-Closure Input: a list of pairs, L. Interpreting L as a binary relation, Symmetric-Closure should return the symmetric closure of L. Examples: (Symmetric-Closure ‘((a a) (a b) (b a) (b c) (c b))) —> ‘((a a) (a b) (b a) (b c) (c b)) (Symmetric-Closure ‘((a a) (a b) (a c))) —> ‘((a a) (a b) (a c) (b a) (c a)) (Symmetric-Closure ‘((a a) (b b))) —> ‘((a a) (b b)) (Symmetric-Closure ‘()) —> ‘() 3. Transitive-Closure Input: a list of pairs, L. Interpreting L as a binary relation, Transitive-Closure should return the transitive closure of L. Examples: (Transitive-Closure ‘((a b) (b c) (a c))) Page 2 of 2 —> ‘((a b) (b c) (a c)) (Transitive-Closure ‘((a a) (b b) (c c))) —> ‘((a a) (b b) (c c)) (Transitive-Closure ‘((a b) (b a))) —> ‘((a b) (b a) (a a) (b b))) (Transitive-Closure ‘((a b) (b a) (a a))) —> ‘((a b) (b a) (a a) (b b)) (Transitive-Closure ‘((a b) (b a) (a a) (b b))) —> ‘((a b) (b a) (a a) (b b)) (Transitive-Closure ‘()) —> ‘() You must use recursion, and not iteration. You may not use side-effects (e.g. set!). The solutions will be turned in by posting a single Racket program (lab06. rkt) containing a definition of all the functions specified.
Implement the following Racket functions: 1. Reflexive? Input: a list of pairs, L and a list S. Interpreting L as a binary relation over the set S, Reflexive? returns #t if L is a reflexive relation over the set S and #f otherwise. Examples: (display “Reflexive? ”) (Reflexive? ‘((a a) (b b) (c c)) ‘(a b c)) —> #t (Reflexive? ‘((a a) (b b)) ‘(a b c)) —> #f (Reflexive? ‘((a a) (a s) (b b) (c c)) ‘(a b c)) —> #f (Reflexive? ‘() ‘()) —> #t 2. Symmetric? Input: a list of pairs, L. Interpreting L as a binary relation, Symmetric? returns #t if L is a symmetric relation and #f otherwise. Examples: (display “Symmetric? ”) (Symmetric? ‘((a a) (a b) (b a) (b c) (c b))) —> #t (Symmetric? ‘((a a) (a b) (a c) (c a))) —> #f (Symmetric? ‘((a a) (b b))) —> #t (Symmetric? ‘()) —> #t 3. Transitive? Input: a list of pairs, L. Interpreting L as a binary relation, Transitive? returns #t if L is a transitive relation and #f otherwise. Examples: (display “Transitive? ”) (Transitive? ‘((a b) (b c) (a c))) —> #t (Transitive? ‘((a a) (b b) (c c))) —> #t (Transitive? ‘((a b) (b a))) —> #f (Transitive? ‘((a b) (b a) (a a))) —> #f (Transitive? ‘((a b) (b a) (a a) (b b))) —> #t (Transitive? ‘())—> #t You must use recursion, and not iteration. You may not use side-effects (e.g. set!). The solutions will be turned in by posting a single Racket program (lab05.rkt) containing a definition of all the functions specified.
1. Enter and load the following function. (define (mystery L) (if (null? L) L (append (mystery (cdr L)) (list (car L))))) 1) Run this function on the following lists (mystery ‘(1 2 3)) (mystery ‘((1 2) (3 4) 5 6)) What does this function do? Explain the logic of the function. Answer:2) As you may have noticed, there is no return statement here. Explain how the return value is determined in the above function. Answer:2. To watch your program in action with the debugger, click the “Debug” button instead of the “Run” button. Then rerun your program by typing (in the definitions window) (mystery ‘(1 2 3)) A series of debugging buttons will appear at the top of the definitions window. Click “Step” repeatedly, and watch the pointer move through your code. Also watch the gray bar to the far left of Page 2 of 3 the debugging buttons. DrRacket will show you the return values for functions when they are called. You can also hover your mouse over variables (hover the mouse over the variable L, for example), and DrRacket will show you those variable values to the right of the debugging buttons. You can also see the stack of function calls and variable values to the right. You will note a green arrow and circle in the body of mystery. These represent the expression that is currently being evaluated. You should also note the red circle. That represents a breakpoint. You can use the “Go” button to resume execution of your program. More instructions on debugging can be found in the Racket documentation: https://docs.racket-lang.org/drracket/debugger.html 3. Modify the program as follows: (define (mystery L) (if (null? L) L (begin (displayln L) (append (mystery (cdr L)) (list (car L)))))) What does begin do? What does displayln do? Answer:Page 3 of 3 4. Write a recursive function (gen-list start end). This function will generate a list of consecutive integers, from start to end. (If start > end then an empty list is generated. See how to compare two numbers: https://docs.racket-lang.org/heresy/math.html). For example: (gen-list 1 5) —> (1 2 3 4 5) 5. Write a recursive function named sum that adds up all the elements in a list. For example: (sum ‘(4 5 0 1)) —> 10 (sum (gen-list 1 5)) —> 15 Do something reasonable if the list is empty. 6. Write a recursive function, retrieve-first-n, that returns a list of the first n elements in a list. Example: > (retrieve-first-n 3 ‘(a b c d e f g h i)) (a b c) Your code should do something appropriate if n is too big or too small (negative). It doesn’t matter to me precisely what it does under these circumstances, so long as it does something reasonable (doesn’t crash or return complete nonsense). Your function should not use any other Racket functions than those which have been introduced in this lab and lab 1. [An exception: if you wish, you may use the functions , =.] 7. Write a recursive function pair-sum? that takes an integer sequence as generated by the genlist function in exercise 4 above. This function tests whether any two adjacent values in the given list sum to the given val. For example, (pair-sum? ‘(1 2 3) 3) —> #t since 1+2=3. Similarly, (pair-sum? (gen-list 1 100) 1000) —> #f since no two adjacent integers in the range 1 to 100 can sum to 1000. You must use recursion, and not iteration. You may not use side-effects (e.g. set!). To turn this assignment in: 1. Exercise 1 and 3: submit a copy of the document with your answers to exercise 1 and 3 on Canvas. 2. Exercise 4 to 7: The solutions will be turned in by posting a single Racket program (lab02. rkt) containing a definition of all the functions specified, (including gen-list, etc.).
1. Write a Racket function (set-equal? L1 L2) that tests whether L1 and L2 are equal. Two sets are equal if they contain exactly the same members, ignoring ordering (or in other words, two sets are equal if they are a subset of each other). For example (set-equal? ‘(1 (2 3)) ‘((3 2) 1)) —> #t (set-equal? ‘(1 2 3) ‘((3 2)1)) —> #f (set-equal? ‘(1 2 3) ‘((1 2 3))) —> #f 2. Two common operations on sets are union and intersection. The union of two sets is the set of all elements that appear in either set (with no repetitions). The intersection of two sets is the set of elements that appear in both sets. Write Racket functions (union S1 S2)and(intersect S1 S2) that implement set union and set intersection. For example (union ‘(1 (2) 3) ‘(3 2 1)) —> (1 2 3 (2)) (union ‘((1 2 3)) ‘((3 4 5))) —> ((1 2 3) (3 4 5)) (union ‘((1 2 3)) ‘((3 2 1))) —> ((1 2 3)) (intersect ‘((1 2 3)) ‘((3 2 1))) —> ((1 2 3)) (intersect ‘((1 2 3)) ‘((4 5 6))) —> () (intersect ‘((1) (2) (3)) ‘((2) (3) (4))) —> ((2) (3)) The ordering of the elements in your answer may differ from the above. You must use recursion, and not iteration. You may not use side-effects (e.g. set!). The solutions will be turned in by posting a single Racket program (lab04. rkt) containing a definition of all the functions specified.
The nefarious Dr. Evil has planted a slew of “binary bombs” on our class machines. A binary bomb is a program that consists of a sequence of phases. Each phase expects you to type a particular string on stdin. If you type the correct string, then the phase is defused and the bomb proceeds to the next phase. Otherwise, the bomb explodes by printing “BOOM!!!” and then terminating. The bomb is defused when every phase has been defused. There are too many bombs for us to deal with, so we are giving each student a bomb to defuse. Your mission, which you have no choice but to accept, is to defuse your bomb before the due date. Good luck, and welcome to the bomb squad! For this lab, you must work on the CS machines. The instructions and commands mentioned here are meant to be issued at the command line while you are logged into a CS machine. That is because the bomb executable communicates with a CS server which tallies progress. As with project 1, you can work in pairs. Indeed highly encouraged! If you work in pairs, you will submit via Canvas both names, and the highest scoring of the created bombs by the two people (phases solved minus fewest deductions) will be the score given to both students. Stage 1: Get Your Bomb(s) While ssh connected to your CS account, create a directory (perhaps call is proj2), and from within that directory, issue the following: curl -G http://systems.cs.wwu.edu:24701/?username=X&[email protected]&submit=Submit > bomb.tar where the X is your CS username. In effect what this does is go to the URL specified (which is ON a machine inside the CS firewall), through port 24701, and provide credentials as if you were accessing that page via a browser. The output (download) is then piped to (sent to) bomb.tar If done correctly, you should now have the file bomb.tar in your directory. Then give the command: tar -xvf bomb.tar. This will untar (which is similar to unzip) and create a directory called bombk, where k is the bomb number that YOU have been given. The directory will have the following files: • README: Identifies the bomb and its owners. • bomb: The executable binary bomb. • bomb.c: Source file with the bomb’s main routine and a friendly greeting from Dr. Evil. If for some reason you request multiple bombs, this is not a problem. Choose one bomb to work on and delete the rest.Step 2: Defuse Your Bomb Your job is to defuse your bomb. You must do the assignment on one of the class machines. In fact, there is a rumor that Dr. Evil really is evil, and the bomb will always blow up if run elsewhere. There are several other tamper-proofing devices built into the bomb as well, or so we hear. You can use many tools to help you defuse your bomb. Please look at the hints section for some tips and ideas. The best way is to use your favorite debugger to step through the disassembled binary. Each time your stage bomb explodes it will notify the server, and you will lose 1/2 point (up to a max of 15 points) in the final score. This is for the purpose of preventing a brute force approach (see the hints). The first explosion doesn’t count towards your tally. So there are consequences to exploding the bomb. You must be careful! The first four phases are worth 10 points each. Phases 5 and 6 are a little more difficult, so they are worth 15 points each. Thus the maximum score you can get is 70 points (assuming no deductions for bomb explosions). Although phases get progressively harder to defuse, the expertise you gain as you move from phase to phase should offset this difficulty. However, the last phase will challenge even the best students, so please don’t wait until the last minute to start. The bomb ignores blank input lines. If you run your bomb with a command line argument, for example, $./bomb psol.txt then it will read the input lines from psol.txt until it reaches EOF (end of file), and then switch over to stdin. In a moment of weakness, Dr. Evil added this feature so you don’t have to keep retyping the solutions to phases you have already defused. To avoid accidentally detonating the bomb, you will need to learn how to single-step through the assembly code and how to set breakpoints. You will also need to learn how to inspect both the registers and the memory states. One of the nice side-effects of this project is that you will get very good at using a debugger. This is a crucial skill that will pay big dividends in the rest of your career. Submission There is no explicit handin. The bomb will notify your instructor automatically about your progress as you work on it. Progress stats will be updated and posted periodically to Canvas and/or announcements during lectures.Hints (Please read this!) There are many ways of defusing your bomb. You can examine it in great detail without ever running the program, and figure out exactly what it does. This is a useful technique, but is not always easy to do. You can also run it under a debugger, watch what it does step by step, and use this information to defuse it. This is probably the fastest way of defusing it. We do make one request, please do not use brute force! You could write a program that will try every possible key to find the right one. But this is no good for several reasons: • You lose 1/2 point (up to a max of 15 points) every time you guess incorrectly and the bomb explodes. • Every time you guess wrong, a message is sent to the bomb server. You could very quickly saturate the network with these messages, and cause the system administrators to revoke your computer access. If you tally far more than 20 explosions (in other words, you are doing a brute force approach) the server will lock you out, and you will get a zero for the assignment. In other words, do not do a brute force approach. • We haven’t told you how long the strings are, nor have we told you what characters are in them. Even if you made the (incorrect) assumptions that they all are less than 80 characters long and only contain letters, then you will have 2680 guesses for each phase. This will take a very long time to run, and you will not get the answer before the assignment is due. There are many tools which are designed to help you figure out both how programs work, and what is wrong when they don’t work. Here is a list of some of the tools you may find useful in analyzing your bomb, and hints on how to use them. • gdb : The GNU debugger. This is a command line debugger tool available on virtually every platform. As you’ve done in previous assignments, you can trace through a program line by line, examine memory and registers, look at both the source code and assembly code (we are not giving you the source code for most of your bomb), set breakpoints, set memory watch points, and write scripts. The following CS:APP web site includes good resources: http://csapp.cs.cmu.edu/public/students.html It includes a very handy single-page gdb summary that you can print out and use as a reference. Here are some other tips for using gdb. – To keep the bomb from blowing up every time you type in a wrong input, you’ll want to learn how to set breakpoints.– For online documentation, type “help” at the gdb command prompt, or type “man gdb”, or “info gdb” at a Unix prompt. Some people also like to run gdb under gdbmode in emacs. – Consider the use of the layout command. For example, layout asm and layout regs will show the assembly and registers in real-time. • objdump -t This will print out the bomb’s symbol table. The symbol table includes the names of all functions and global variables in the bomb, the names of all the functions the bomb calls, and their addresses. You may learn something by looking at the function names! • objdump -d Use this to disassemble all of the code in the bomb. You can also just look at individual functions. Reading the assembler code can tell you how the bomb works. Although objdump -d gives you a lot of information, it doesn’t tell you the whole story. Calls to system-level functions are displayed in a cryptic form. For example, a call to sscanf: 8048c36: e8 99 fc ff ff call 80488d4 To determine that the call was to sscanf, you would need to disassemble within gdb. • strings This utility will display the printable strings in your bomb. Looking for a particular tool? How about documentation? Don’t forget, the commands apropos, man, and info are your friends. In particular, man ascii might come in useful, while info gas will give you more than you ever wanted to know about the GNU Assembler. Also, the web may also be a treasure trove of information. If you get stumped, feel free to ask your instructor for help. Phase 1 Hints • Before even trying to solve the puzzle, figure out where the program blows up the bomb and set a breakpoint there, to prevent explosions. • Definitely try the strings command in gdb • Invest time in learning a lot of different gdb commands…it will pay off!Rubric Item Points Phases 1-4 4 x 10 = 40 points Phase 5 15 points Phase 6 15 points Deductions Points explosions 2 onward 0.5 points per explosion, capped at 15 points deduction
Overview This lab asks you to complete a generic sorting algorithm by adding a third, function parameter to an existing function, and update the two test programs that you are being provided to use your new parameter. The below instructions walk you through the first two parts of this lab: completing the sort_array function and updating sort_strings. Specifics The goal is to develop a general purpose sorting routine, that is capable to sort using any data type. The generalized function is defined in sort.h and implemented in sort.c. Get these functions from /home/jagodzf/public_html/teaching/csci247/labs/lab4 The array to be sorted contains void*s. A void* is simply a pointer to an unknown type. Let’s say that I have an array of strings, for example. The actual array is an array of char*s and would look like: Array: +——–+——+——+ | | | | | | | | | | | +—-+—+–+—+–+—+ | | | +————–+ | | +——————> |Third string| | | +————–+ | | +—————+ | +————————-> |Second string| | +—————+ | +————–+ +——————————–> |First string| +————–+The array has size 3, but each string has a different length. For the most part, we don’t care what the pointers point at. Here is the problem: we care what the pointers point at regarding ordering. The only way I can compare void*s is by where they point in memory. This is not helpful. Pointers into the .text section would sort before .data or the stack. I need a generic way to compare two unknown data types. Consider the example above: an array of strings. I could add a compare-function for strings in sort.c. This function would look something like this: static int ordered_strings (void* left, void* right) { char* left_string = (char*) left; char* right_string= (char*) right; return strcmp (left_string, right_string) < 0; } All this function does is cast the void*s to char*s. We happen to know that this is correct in this example. The actual comparison is performed by the C-library function strcmp. The test in sort_array needs updating. Currently, the test looks like this: if ( Array[i] < Array[i+1] ) { swap(&Array[i], &Array[i+1]); have_swapped = 1; } See how it compares the addresses? For strings, the test would look like this: if ( ordered_strings (Array[i], Array[i+1]) ) { swap(&Array[i], &Array[i+1]); have_swapped = 1; } This will work for strings, but defeats the goal; this is not a generic sorting function. Instead of adding every possible ordering of every data type to sort_array, we can pass a comparison function as an argument. Technically we cannot pass a function as an argument, but we can pass a pointer to a function. This syntax, however, is strange. Right now, sort_array looks like this: void sort_array(void* Array[], unsigned size);We need to add a third parameter, let’s call it ordered. In C, we usually declare the type followed by the name (e.g., void* Array[], unsigned size, etc.). The name of the function pointer is in the middle and has a weird set of parentheses. The new declaration of sort_array looks like this: void sort_array(void* Array[], unsigned size, int (*ordered)(void*,void*)); See what I mean about the strange syntax! The parentheses around the symbol bind the asterisk to the name rather than to the return type. Otherwise, it would be a function that returns an int*. Using the function is straight-forward. The test now looks like this: if ( ordered(Array[i], Array[i+1]) ) { swap(&Array[i], &Array[i+1]); have_swapped = 1; } We can use the function parameter like any other function, but only within sort_array. Now the caller must provide an array, its size, and a function that determines if the two — whateverthey-are – are in the correct order. Let’s fix sort_strings. Right now, it only passes the first two arguments to sort_array. We need to create the third argument, a function that compares two strings, but we have already done this. However, we put it in the wrong file. Move compare_strings from sort.c to sort_strings.c. Now we can correct the call to sort_array in main: sort_array((void**)data, data_size, &ordered_strings); Makefiles and make Provided in the directory named above is the file Makefile. The utility make is the command-line program which issues compilation instructions that are specified in the file Makefile. The use of a Makefile streamlines the compilation process. Since we have only fixed sort_strings, asking make to build everything would create a bunch of errors. There are many details to using make, which we don’t cover in detail here. For the time being, just know that a Makefile includes variables names, and individual instructions for different pieces of code that you want compiled. In the Readme file that you are given, there are multiple compilation instructions, including all, sort.o, check, etc, and including clean. Each of these is accompanied by instructions of what the compiler should do IF the user invokes that compilation option. We can build just sort_strings with the following make command: $make sort_stringsWhat does clean do? And all? Ask your TA! Hint : issue make clean, look at the directory structure, and then issue make sort_strings, and look at the directory. What has changed? And we can use sort_strings to test: $./sort_strings “rodeo” and “reading” are out of order “reading” and “polish” are out of order “polish” and “lima” are out of order “lima” and “job” are out of order Hmm, something went wrong. I think we sorted in the wrong direction. One of your tasks is to fix this. The second set of tests is sort_struct. This one is slightly more complicated. Rather than strings, it is an array of pointers to structures. Create an ordering function such that sort_array orders the cars in ascending order or years. What you must do • Finish implementing the generic sort_arrays function • Update sort_strings to sort in alphabetic order • Update sort_structs to sort in increase model year order. Important: Do not modify the for-loop in the main functions. It is there to ensure that the arrays are sorted in the correct order. Rubric and submission Please upload the following files to canvas • sort.c • sort.h • sort_strings.c • sort_structs.c Submit the asked-for files as the Lab 4 Submission item on Canvas. You must submit your file by the due date/time specified on Canvas. Sorting strings correctly 5 points Sorting cars correctly 7points Coding style 3 points 15 points
The purpose of this assignment is to become more familiar with bit-level representations of integers and floating point numbers. You will solve a series of programming tasks, some of which are quite trivial, but others are indeed implementations of often-used tasks that are part of important applications for network procedures, calculating distances, etc. Outcome The goal is for you to find yourself thinking much more about bits in working your way through the programming tasks. As with the other parts of this class, you can work in groups of two, or solo. However, you are NOT allowed to work in groups of 3 or more, and groups cannot communication solutions nor approaches with other groups. Files Download from the files section of Canvas the project 1 zip file, and move it to your CS account. Use sftp, or an ftp client such as FileZilla. Unzip it via unzip project1_manipulatingBits.zip Implementation Details The only file you will be modifying and turning in is bits.c. The bits.c file contains a skeleton for each of several programming tasks (functions). Your assignment is to complete each function skeleton using only straight-line code for the integer puzzles (i.e., no loops nor conditionals) and a limited number of C arithmetic and logical operators. Specifically, you are only allowed to use the following eight operators: ! ~ & ^ | + > A few of the functions in bits.c further restrict this list, so read closely the comments for each function. Also, you are not allowed to use any constants longer than 8 bits. See the comments in bits.c for detailed rules and a discussion of the desired coding style. Important: Carefully read the instructions in the bits.c file before you start. These give the coding rules that you will need to follow. Hint: The comments for each function also provide a hint, which mentions approximately how many lines of code a good solution might require. That is not to imply that your solution must use that few number of lines of code, but if you find yourself writing far more than that many lines of code, perhaps you are overthinking it and you should step back and brainstorm.The Puzzles (tasks, functions) There are 3 types of puzzles: Bit manipulation, Two’s Complement, and Floating Point Manipulations. This section describes the puzzles that you will be solving in bits.c. Bit Manipulations Table 1 describes a set of functions that manipulate and test bit patterns. The Difficulty field gives the difficulty rating (the number of points) for the puzzle, and the Max ops field gives the maximum number of operators you can use to implement each function. See the comments in bits.c for more details on the desired behavior of the functions. You may also refer to the test functions in tests.c. These are used as reference functions to express the correct behavior of your functions, although they don’t satisfy the coding rules for your functions. Table 1: Bit-Level Manipulation Functions. Function name Description Difficulty Max Ops bitAnd(x,y) x & y using only | and ~ 1 8 getByte(x,n) Get byte n from x 2 6 logicalShift(x,n) Shift right logical 3 20 bitCount(x) Count the number of 1’s in x. 4 40 Two’s Complement Arithmetic Table 2 describes a set of functions that make use of the two’s complement representation of integers. Again, refer to the comments in bits.c and the reference versions in tests.c for more information. Table 2: Arithmetic Functions Function name Description Difficulty Max Ops tmin() Most negative two’s complement integer 1 4 fitsBits(x,n) Does x fit in n bits? 2 15 divpwr2(x,n) Compute x/2n 2 15 negate(x) -x without negation 2 5 isPositive(x) x > 0? 3 8 ilog2(x) Compute log2(x) 4 90 Floating-Point Operations For this part of the assignment, you will implement some common single-precision floating-point operations. You can use standard control structures (conditionals, loops), and you may use both int and unsigned data types, including arbitrary unsigned and integer constants. You may not use any unions, structs, or arrays. Most significantly, you may not use any floating point data types, operations, or constants. Instead, any floating-point operand will be passed to the function as having type unsigned, and any returned floating-point value will be of type unsigned. Your code should perform the bitmanipulations that implement the specified floating point operations. Table 3 describes a set of functions that operate on the bit-level representations of floating-point numbers. Refer to the comments in bits.c and the reference versions in tests.c for more information. Table 3: Floating-Point Functions. Value f is the floating-point number having the same bit representation as the unsigned integer uf. Function name Description Difficulty Max Ops float_neg(uf) Compute -f 2 10 float_twice(uf) Computer 2*f 4 30 Functions float_neg and float_twice must handle the full range of possible argument values, including not-a-number (NaN) and infinity. The IEEE standard does not specify precisely how to handle NaN’s, and the IA32 behavior is a bit obscure. We will follow a convention that for any function returning a NaN value, it will return the one with bit representation 0x7FC00000. The provided program fshow helps you understand the structure of floating point numbers. To compile fshow, type: unix> make You can use fshow to see what an arbitrary pattern represents as a floating-point number: unix> ./fshow 2080374784 Floating point value 2.658455992e+36 Bit Representation 0x7c000000, sign = 0, exponent = f8, fraction = 000000 Normalized. 1.0000000000 X 2^(121) You can also give fshow hexadecimal and floating point values, and it will decipher their bit structure. Auto-grading your work You are being provided some autograding tools — btest, dlc, and driver.pl — to help you check the correctness of your work. btest This program checks the functional correctness of the functions in bits.c. To build and use it, type the following two commands: unix> make unix> ./btestThe make program is an industry/CS standard macro-like approach for compiling and linking programs, which otherwise you’d need to do manually via the command line.You must rebuild btest each time you modify your bits.c file. You’ll find it helpful to work through the functions one at a time, testing each one as you go. You can use the -f flag to instruct btest to test only a single function: unix> ./btest -f bitAnd You can feed it specific function arguments using the option flags -1, -2, and -3: unix> ./btest -f bitAnd -1 7 -2 0xf Check the file README for documentation on running the btest program. dlc This is a modified version of an ANSI C compiler from the MIT CILK group that you can use to check for compliance with the coding rules for each puzzle. The typical usage is: unix> /home/clausoa/bin/dlc bits.c This command will invoke the dlc program, that is in the /home/clausoa/bin directory. The program runs silently unless it detects a problem, such as an illegal operator, too many operators, or non-straight-line code in the integer puzzles. Running with the -e switch: unix> /home/clausoa/bin/dlc -e bits.c causes dlc to print counts of the number of operators used by each function. Type dlc -help for a list of command line options. NOTE: dlc is installed in Dr. Clauson’s personal bin directory. If you want to simplify your life, you can add that bin directory to your PATH variable (google bash PATH) or create an alias (google bash alias). driver.pl This is a driver program that uses btest and dlc to compute the correctness and performance points for your code. It will compile your bits.c file, and test each of your functions. The driver.pl program takes no arguments: unix> ./driver.pl The driver.pl program will be used to evaluate your solution. If you get an execution error, you might need to grant execution rights to the driver.pl program. To do that, you would issue the following (which also gives read and write permissions): unix> chmod u+rwx driver.plTechnical caveats • Don’t include the header file in your bits.c file, as it confuses dlc and results in some non-intuitive error messages. You will still be able to use printf in your bits.c file for debugging without including the header, although gcc will print a warning that you can ignore. • The dlc program enforces a stricter form of C declarations than is the case for C++ or that is enforced by gcc. Any declaration must appear in a block (what you enclose in curly braces) before any statement that is not a declaration. In other words, for each function you must declare all your variables first. For example, it will complain about the following code: int foo(int x) { int a = x; a *= 3;
I. Architecture specifics In this part of the lab, you’ll explore some of the architecture elements of the computer that you are logged into. First, let us inspect if the CS machines are 32-, or 64-bit machines. There are many ways to find this out; only a few are shown here. The uname linux command prints system information. Issue uname, with the -a(ll) falg: $uname -a You’ll see a list of details, including the name of the machine, the processor type, the operating system, etc.Next, let us inspect the hardware and memory attributes of the computer that you’ve logged onto. One such command to get that information is the free command, which can be issued with a variety of flags, including m(egabytes), h(uman readable), g(igabytes), etc. Issue each of the following (they provide the same info, but different formatting) to determine how much memory is available on the linux machine where you are logged on. $free -g $free -m $free -h The program who and htop inform you who else is logged onto the computer, and which processes are currently running – and what resources they are using. Issue who, to see who is logged on. Your username should be among those listed. $who Although not the focus of this class (instead, you’ll learn more about this when you take CSCI 447, Operating Systems), there are a variety of command line programs that you can use to inspect what is running – and what memory resources each program is using – on your computer. Issue htop, to see who is logged on, what the load is on each of the CPUs, how much memory each process is using, etc. The htop program includes help (F1), and a variety of other options.II. The C-program Now that we have a rudimentary understanding what type of computer you are logged into – which is important, if ever you needed to look at the instruction set to get a better understanding of the assembly opcodes that are available – let us start by writing and compiling a simple C program. Save the C program into the file sample.c, shown right. This seems harmless enough … and it is. As mentioned in lecture, there are multiple ways that you can inspect the assembly code that would be generated from the source code file. III. Using gcc to generate the assembly code As was shown in the lecture slides, issue the following, to generate the .s file for the program sample.c: $gcc -S sample.c Let’s inspect the assembly code, which is in the file sample.s. pushq %rbp movq %rsp, %rbp movl $10, -8(%rbp) movl $15, -4(%rbp) movl -4(%rbp), %eax subl -8(%rbp), %eax movl %eax, -8(%rbp) movl -8(%rbp), %eax addl %eax, -4(%rbp) movl $0, %eax popq %rbp ret All lines that begin with a period are not being shown here, because they are annotations for the linker. Become familiar with the syntax and registers. Do a web search and/or ask your TA for the questions to the following: • What does a % refer to? • What does a $ designate • What do rbp, eax, and rsp refer to? • What does a “-8” refer to, as for example -8(%rbp) • What do the opcodes pushq, mov, sub, add, pop, ret specify • What do the single letter suffixes l, q (and are there others?) specify, as for example movq versus movl. int main() { int x, y; x = 10; y = 15; x = y-x; y = x+y; }IV. First use of gdb. GDB is the GNU Debugger, which is a text-only portable debugger that is included with most Linux-ish operating systems. It provides all of the features that you’d find in any IDE debugger, such as setting breakpoints, stepping through functions, stepping into functions, etc. Available in the files section of Canvas is a GDB debugger document. Although the gdb commands needed for this lab are all presented here, you will need to refer to the documentation for (probably) homework 2, and definitely project 2. To use a program with gdb, you must compile the program with the -g flag, to inform the compiler to insert debugger symbols so that the executable can be intercepted by gdb to permit inspecting various elements of the program. $gcc -g -o sample sample.c Now that you have created an executable suitable for use in gdb, start gdb, and “load” the sample executable into gdb: $gdb ./sample You’ll see the (not too stylish – hey I did say text-only!) gdb screen, similar to what is shown below. That is “the” gdb prompt. At the (gdb) prompt, set a breakpoint at the start of the main() function of the program by using the b command. This will make the debugger pause when it starts executing the main() function. (gdb) b main When issued, gdb will inform you that a breakpoint has been set.At the (gdb) prompt, run the program by using the r command: (gdb) r You will see the output similar to what is shown in the following figure: At this point, gdb has reached a breakpoint, and is now waiting for your command. There are a variety of commands (refer to the gdb tutorial). One of these commands is next, which you can use to proceed to the next line of code. Two useful commands are continue, and display, where display allows you to inspect the value of any variable that is in scope. For example, assume you want to inspect the value of the variable x: (gdb) disp x V. Disassembling GDB includes a disassemble option to convert the machine language of the program back to assembly language. Instruct gdb to disassemble the program (machine language) into assembly language, by issuing the disassemble command: (gdb) disassemble The output should be similar to what is shown in the figure on the right. What similarities and differences are there between this disassembled code, and the assembly code that you generated using the gcc -S flag? For starters, notice that gdb is telling you, via the =>, where the program is currently executing. Neat!Note that %rbp (the base pointer) is set to the top of the stack. The local variables x and y are stored on the stack at positions beyond the base pointer. Since x and y are both int, each requires 4 bytes (that’s the C default) so their values are stored at addresses -0x8(%rbp) and -0x4(%rbp), respectively, where the 8 and 4 refer to addresses BEYOND the start of the memory location referred to by rbp. Here’s the assembly instructions again, with annotations: push %rbp # save the old value of %rbp mov %rsp,%rbp # set %rbp to the value of %rsp movl $0xa,-0x8(%rbp) # x = 10 movl $0xf,-0x4(%rbp) # y = 15 mov -0x4(%rbp),%eax # load y into %eax sub -0x8(%rbp),%eax # y – x is now in %eax mov %eax,-0x8(%rbp) # x = y – x mov -0x8(%rbp),%eax # load x into %eax add %eax,-0x4(%rbp) # y = x + y mov $0x0,%eax pop %rbp # restore the old value of %rbp retq # return from main() VI. Disassembling aProgram For this part of the lab, you will retrieve an executable from my (Filip’s) home directory, and disassemble it using gdb. Retrieve the aProgram executable file from the following directory, on the linux CS machines: /home/jagodzf/public_html/teaching/csci247/labs/lab3 Refer to lab 1 on how to copy a file from one directory to another. Your task: Use gdb to set a breakpoint, and disassemble the program. Then, compose the file aProgram.c, which you will upload to Canvas. Rubric and submission Please upload your aProgram.c file to Canvas. The aProgram.c file contains the plain text .c source code that would generate the assembly code for the executable aProgram. 10 points 10 points
In this lab you will gain more experience in manipulating different data types in C, you will revisit the modulus operator (that you have learned in previous CS courses), and you’ll perform a series of bit manipulations. You’ll write a main program that prompts the user for inputs, and which then invokes the functions that you’ll write. I. Modulus by Brute Force to Convert to a Different Base The Objectives of this part of the lab are the following: • Become comfortable with using a char pointer • Perform modular arithmetic • Continue to develop skills at writing C functions As was the case for lab 1, ask the TAs lots of questions. They are there to help. And, you CAN work with peers in completing the labs. This is a bit tricky when everybody is remote; you may use slack, email, discord, etc. Up to you. But, in no circumstances should you SHARE code, which involves emailing code and then submitting it as your own. Submitting your work Submit your C program files as the Lab 2 Submission item on Canvas. You must submit your program by the due date/time specified on Canvas. Create a C source file, compile it, and link it to get an executable Use the nano editor (or any editor of you choice, such as emacs) to create a file called lab2Convert.c, type the following contents and save the file. #include int main() {} Compile this file into an executable by issuing the following from the command line, and then run: $ gcc –o lab2Convert lab2Convert.c $ ./lab2Convert This is a skeleton of a program, so it doesn’t do anything (yet).Implement a Conversion Function Implement a function with the following signature: char* itoa(int num, char* str, int base); where num is an integer that you need to represent as a string in the base specified. The input can be a negative number. In principle, this is VERY similar to the task for homework 1, but here you are tasked to write the function for converting to ANY base, and not just binary nor hexadecimal. For example, assuming char buffer[50]; has been declared, Invocation Output to screen printf(“%s”,itoa(4, buffer, 2)); 100 printf(“%s”,itoa(64, buffer, 8)); 100 printf(“%s”,itoa(72, buffer, 8)); 110 printf(“%s”,itoa(675, buffer, 16)); 2A3 printf(“%s”,itoa(456, buffer, 12)); 320 Hint: To specify the alphabet of a base greater than 10, use the ASCII values of letters starting with A, then B, the C, the D, etc. A typical approach is the following: 1. Get the least significant digit by finding the modulus of the number and the base 2. Depending on the base, represent this digit in ASCII by either adding it to the ASCII ‘a’ or the ASCII ‘0’ and store it in a string 3. Divide the number by the base and repeat steps 1-3 until the number is reduced to zero 4. Reverse the string (the char* str), and display using your method of choice.II. Bit manipulation The Objectives of this part of the lab are the following: • Continue to develop your understanding of binary representation of integers Implement a function with the following signature: int countSetBits(unsigned int var); This function should return the number of set bits (1s) in argument. That means, you must convert the input unsigned int into its binary equivalent, and then count the number of bits. Note: This is in principle the same as the bitCount function of project 1, but here you ARE allowed to use any operator that you want. Also, this function’s input is an unsigned int, which is a bit different than the bitCount function in project 1. Implement a function with the following signature: int reverseBits(int var); This function should return an integer that has all the bits (including the sign bit) of the argument reversed. These functions that perform bit manipulations are meant to force you to THINK about and MANIPULATE the bit representations of different data types. For example, there are many learning points for this task. First you would need to recall that ints in C are 4 bytes and are SIGNED. Thus, invoking reverseBits(1) where the 1 is of type int, the 1 would be saved as 00000 … 00001 Reversing all of those gives 10000 … 00000 Which when assigned to an integer (because that is what the function returns), that integer would have the value -1(231) + 0 + 0 + …. + 0 Thus printing the value of the output of reverseBits should print -2147483648 to the screen.Implement a function with the following signature: bool onlyOneBitSet(int aVar); This function should return true if only one bit is set in the argument passed in, and should return false otherwise. III. The main() Write a main method that • Prompts the user to provide two integers • Invokes itoa using the two inputs • Invokes countSetBits, reverseBits, and onlyOneBitSet, using the first input integer • Prints to the screen the output (char*, int, int, bool) of the 4 functions. Rubric and submission Please upload your .c file to Canvas. itoa correctly implemented 3 points countSetBits correctly implemented 3 points reverseBits correctly implemented 3 points onlyOneBitSet correctly implemented 3 points lab2Convert.c uploaded via Canvas • Program Compiles • Main method prompts for user’s input • The 4 functions are invoked • Output is nicely formatted 3 points 15 points
