For this assignment, I’d like you to make two 2-D drawings, one 3-D scene, and a simple animation, all using the opengl.js library we used in Project 1. You will modify scene.js, the code provided at a link on this page, so that it displays each of these four scenes. The scenes should consist of shapes you create using GL_TRIANGLE vertex layout requests. The shapes should be placed in the scene by applying transformations to the coordinate frame using glScalef, glTranslatef, glRotatef. These scenes will typically be hierarchical, so you will want to issue glMatrixPush and glMatrixPop commands to save and restore coordinate frames as you lay them out.Here is the starter code for this assignment.Modify (or completely rewrite) scene.js so that it generates each of these scenes: Make it so that the program user can select which scene is displayed by pressing a button on the page. You can also add controls so that the user can play with each scene.The first thing you must make is a 2-D drawing of your design. That drawing can be of anything, except it must be in the spirit of my house drawing, and have similar complexity (or more). That house drawing uses only a few graphics primitives—a “unit” right triangle, a unit disk, a unit square, and a 1×2 rectangle—but scales, rotates, and translates the coordinate system so that, when these figures are drawn, they get placed all over the screen to form the drawing.The whole point of you completing this task is for you to get practice using the OpenGL transformation stack by making glPushMatrix, glRotate, glScale, glTranslate, and glPopMatrix calls.To do this, you will replace the call to drawHouse within the function draw in scene.js so that it calls a function that draws your 2-D scene. The coordinate frame set up by draw is a 5.0 unit wide by 4.0 unit tall rectangle with the origin sitting in the center of the scene. This means that the xx coordinates should live in the range [−5/2,5/2] and the yy coordinates live in the range [−2,2]. You can layer the drawing so that some elements get drawn above or behind other elements. The range of zz coordinates you can use for this layering should also lie between −2 and 2. Negative zz coordinates sit further away than positive ones, so the positive zz axis is pointed out of the screen. I described my procedure that draws a Sierpinski carpet in class. This is the purple square depicted by the starting code when you select (r)ecursive. I’d like you to generate a similar recursive fractal figure with a procedure. You have several options: I describe each of these options just below.To do this work, you’ll want to replace the call to drawSquareSierpinski within the code for draw in scene.js. The coordinate frame used by draw for the recursive figure is the same as the one used for the house scene, but there is a call to glScalef(3.0,3.0,3.0) just before the call to drawSquareSierpinski. The Sierpinski square code draws its recusrive figure with coordinates within ±1/2, but that scale call makes it a 3×3 unit figure within that 5×4 unit region.. Sierpinski triangle. For this figure, you’ll want to write a recursive function that produces it, parameterized by a levels parameter. This parameter will be used to drive the recursion. When levels == 0 you just draw the base geometric shape of the figure (an equilateral triangle). When levels > 0 you’ll instead recursively call this function several times. My carpet code calls drawSquarepinski 8 times. For the triangle yours would call its own procedure 3 times. Each call is made after a scaling and translation of the coordinate frame. For example, for the triangle figure you’ll scale the frame by 1/2rd, then call the function with no translation, then with a unit translation along the one side, and then a unit translation along the other side. You’ll need glPushMatrix and glPopMatrix to enter, then back out of the (transformations made by these) recursive calls. Note that each of these recursive calls should be made with the parameter levels - 1. . Koch snowflake. After an initial triangle is drawn, you’ll want to draw the three “toothed” sides of the triangle. You’ll do this with a function def KochSide(levels). This function acts similarly to the drawSquarepinski function of the starter code. It should act recursively. For levels > 0, you’ll make four recursive calls to KochSide(levels - 1), to lay out the four smaller toothed edges that form the toothed edge at this level. These are shown below as the green triangles.For levels == 0 you just draw a single triangular tooth, centered on the edge. Note that at the highest level, you’ll be calling KochSide three times, at three different locations and orientations, to make the three sides of the snowflake. Done right, because of the tooth layout, the three sides around the top-level triangle will appear as a 6-pointed snow flake. . Branched leafing. This figure is generated similarly as the other two just described, but has more flexibility in how it can be designed. This Wiki entry and this page explain figures similar to what I’m requesting.The branched leafing figure procedure is also parameterized by levels and is depicted below. In its layout, we think of it as having a “spine” of a vector ray, of a certain length, emanating from some branch point. This spine gives the overall scale and direction of the figure. The figure itself is self-similar: part way up the spine are three branch points. One at the tip of the ray, and one on each side of the ray. Emanating from these three branch points is a figure, just like the one we are describing, shooting off in three directions, each at an angle off the spine, and each at a smaller scale.To draw this, you draw the spine ray as a thin brown rectangle. You then draw two shoots off the spine for the other two branches, also as thin brown rectangles. You then recursively draw the figure with levels - 1 emanating from these branch points at their reduced scale. At the base case levels == 0 you draw, say, a green leaf instead of the branched spine. You can make it so that the user to controls the shape of the “frond” produced, say, by allowing them to control the angle of the shoots, etc. I’ve added two sliders to the demo that control the angle of the branches in the main scene for the house. You could instead have these control your branched figure.A trickier means to control the shape would be to have the user drag the figure. You can take a look at my handling of the mouse clicks and drags that place the sun in the main scene of the house.If you click on the still (l)ife button within the starter application, the display will switch to a depiction of an empty cubical room, one that is reminiscent of a Cornell Box. It has a red wall on the left, a blue wall on the right, and the back wall, the floor, and the ceiling are white. For this part of the assignnment you are to stage the room so that it has a table with a few 3-D objects from Program 1 sitting on it. The image below shows a possible solution for this. You’ll want to add your code to the function drawStillLife which already contains a call drawRoom that draws the room. Within that code, the origin is centered in the middle of the room. And the room has coordinates ranging within −1.0 and 1.0. The room’s dimensions are thus 2 × 2 × 2. Any object you place in the room that has parts that sit closer than +2.0 will be trimmed away by the graphics system.The table that you invent must be made of repeated calls to glBeginEnd("Cube"), but with glScalef and glTranslatef calls elongating or flattening the cube to make the table elements. The table should be square with a top that is 1.5 units wide and deep. The table legs and the table top should be 0.1 units thick. The table should be 0.65 units high.Place at least three objects on top of the table: one should be a sphere, one should be your platonic solid from Program 1, and one should be one of your surfaces of revolution from Program 1.I’ve added two features of the application to help you debug your still life creation. If you click on the still (l)ife button while viewing the still life, a swinging light bulb will appear and illuminate the scene. This will give you a better sense of the three dimensional qualities of your layout. Also, if you press the v key, the view will switch from a perspective view to an orthographic one. You can use this other mode to see whether your objects are properly placed on the surface on the table.I shared a demo that draws a 3-D wireframe diagram of an arm with a hand and fingers. This articulated figure changes the angles of several joints over time (the shoulder, the elbow, the wrist), with one incremental change per frame of the animation that runs at roughly 60x a second.Make your own animation of a jointed figure made up of rigid components, whatever you like, and have its positions and angles change over time. It could be something like Pixar’s Luxo Jr. jumping around in a circle, a simple animal running, whatever you like. It should have at least three rigid components at angles, and move in some way, both its angle and its position.This does not have to be phenomenal or too detailed. Just, like the arm code, get some practice drawing a limbed or jointed figure and use the transformation stack to place it and to wiggle it.You write this code by replacing the call to drawWavingArm with a call to your function. My code uses three global variables gShoulder, gElbow, and gWrist that control the animation of the waving arm. These update every time a frame of the animation is rendered. You will want to invent your own global state for your animation similarly.Just as in Project 1, use Gradescope to submit the individual files that make up your working program. Submit every file that’s needed. That way I can download it from Gradescope (it gets packaged as a folder) and run it in my browser. Should you want to included happy accidents or bloopers you can also include, say, a ZIPped folder of snapshots that you want to share of your pretty mistakes.Please hand in what you have completed by the deadline, even if you haven’t completed everything or the code isn’t working. You can always submit revisions later for some possible credit.Include a text file named submitted.md, or submitted.txt, that tells me, briefly, everything you completed for the assignment, and some of the choices you made. Document your code, as well. The documentation should be richer if there was some non-standard or particularly tricky technical problem you had to solve. Your notes on this will help me evaluate the work. Cite any sources you rely upon. Also, let me know about any bugs you have, or what does/doesn’t work.For all parts of this assignment I am open to you taking some liberty in what you produce, just so long as you are mimicking the techniques I’m suggesting. The key thing I want is for you to work by transforming the coordinate system while pushing and popping the transformation stack, and thus for you to generate scenes that have a hierarchical specification.
This assignment has you invent several geometric models of surfaces so that they can be displayed in a WebGL application. We model surfaces as collections of triangular facets that sit in 3-space. Each of the three corners of each facet are specified by an (x,y,z) coordinate, and the coloring of the facets are given as (red, green, blue) triples. Having describing all the vertices and facets of the surface, and its material properties, the surface description is then sent to the graphics hardware to be displayed on a WebGL canvas embedded in a web page.The starting code for this assignment can be downloaded here. It includes a web page showcase.html that relies on the Javascript file showcase.js and a few other supporting files. When that web page is loaded into the browser, it can already display one of three objects: These models are generated and displayed by these functions: The actual names are makeTetrahedron, makeCube, and makeCylinder. We describe this code in more detail below. You will extend the code to describe a few more models and render them as additions to the object showcase app.
This assignment has you get a taste for Javascript programming that runs in a web browser. It is a low impact assignment that is meant as a warm-up Make an attempt this weekend and come to class with questions on Monday. I’ll set up a gradescope course with a Project 0 assignment where you can submit your code and documentation.The starting code for this assignment can be downloaded here. It includes a web page primes.html that relies on the Javascript file primes.js, is-prime.html that relies on the Javascript file is-prime.js, and a web page triangle.html that relies on triangle.js and gl-matrix-min.js.Mimicking what you see in the primes and is-prime code, create a web application that allows its user to input a positive integer and to then produce an alert that outputs the positive divisors of that integer.The alert should output text like:in the case the input is prime andin the case that the input is composite.Mimicking what you see in the triangle code, create a web application that has a button populate that places an additional randomly placed triangle onto the canvas. All of the placed triangles should be displayed (so you’ll want to keep them in a Javascript array), but only the last placed one should get edited by the other buttons of the application.Upload your source files (including all supporting files) up to gradescope by Tuesday. Please include every file that is needed to run each application. I’ll want to download these files and run your demo, and if you hand in all the individual files, they get packaged as a folder for me by Gradescope. By handing in the files individually (rather than as an archive file or a ZIP), I can comment on individual lines of your code within Gradescope.You should also include a brief text file, either named submitted.md or submitted.txt, that describes the work that you did, how you did it, whether it is working, what isn’t working, and any extra things that you want to tell me about that you did or had planned to do.Please hand in what you have completed by the deadline, even if you haven’t completed everything or the code isn’t working. We’ll go through solutions in class in lecture on Tuesday.
There is no VM for this project; you can complete it on your regular machine.## Task 1 (Warmup: Cracking hashes)Say you know the result of a hash from a password using the md5 hash function, for example:`56207fe91845a32a95b83409fd063715``c78a25d0720594169769fd7d2baebc1c``7e9e3c392a3143b6d0dea01adc0c389e``427ff3c70c42e5a0be09b6307054d8c7`You also know each hash has been produced like this: `const salt = “likes”;` `const password = [unknown];` `const hash = md5(salt + password);` “+” here means concatenationYou need to find a password from *any* of the above four hashes. Note that each password is a string of 4 characters, and the characters are all lowercase letters or numbers. You can consider to use brute force to find the password using tools like [Hashcat](https://hashcat.net/hashcat/) or [John the Ripper](https://www.openwall.com/john/).Note that to reduce the search space, you can use the fact that the salt is a fixed string.**Grading:** We will need your cracked password stored in `task1_password.txt`.## General Description (Task 2-5)In the rest of the project, you will be attacking a weak ciphersuite in an online bank. The bank is using a secure **128-bit block cipher**, with a *unique key* per session. To make a streaming cipher from this, the bank is using the cipher in electronic codebook (ECB) mode. (Hmm…)As an attacker, you were able to inspect the ciphertext stream sent by you to the bank’s server. Due to some technical limitations, you were unable to capture the server’s responses, and you were only able to do this once. However, you know exactly what operations you performed, and in what order, so you should be able to figure out the encrypted message formats, despite *not knowing the format of the plaintext*. That is, the *only* things you have are what you entered into the bank’s website, and the corresponding ciphertext stream.From this, you will need to do the following:– Learn the format of the messages – Write a program to parse these messages and generate new messages – Perform a number of passive- and active-wiretapping attacks on the session of *another* customer (the target), which uses a *different* key**Please note that you will _not_ be decrypting the streams!** Assume the cryptosystem (in this case, the block cipher) itself is unbreakable. You will be exploiting the shoddy way the bank is using the block cipher, rather than trying to break the block cipher itself.## The Reference StreamsCiphertext streams can be found on under `task2` folder. The file `reference.in` contains the following sequence of requests, in the order given:1. A balance request for your checking account 1. A $100 transfer from your checking account to your savings account, to be executed immediately 1. A balance request for your checking account 1. A balance request for your savings account 1. A $1000 transfer from your savings account to your checking account, to be executed immediately 1. A $1000 transfer from your savings account to your checking account, to be executed tomorrow 1. A balance request for your savings account 1. An invoice request issued by your checking account for payment of $1000 from your savings account 1. A balance request for your checking accountYou are also given additional ciphertext streams, which are from *different* sessions, so they are not encrypted with the same key. In addition, you do *not* know what requests were used to generate this. This will allow you to test your code against an unknown request sequence.Take a look at `reference.in` by running `xxd reference.in`; this will format the output so that each line corresponds to 16 bytes of data (128-bits: i.e., one line per block in the block cipher). Each of the above request types (balance, transfer, and invoice) might require different numbers of blocks (for instance, a transfer request clearly has to take more arguments than a balance request). See if, using `xxd`, you can visually match up the blocks in `reference.in` to the above 9 separate requests. A big part of this project involves creating a program that will *automatically* figure out which blocks correspond to which commands.A good use of encryption would reveal nothing about which requests were being made. However, because the system that generated these ciphertexts used ECB, you can detect (and exploit) patterns.## Tasks 2-5Now there are four tasks (tasks 2-5) under this online bank system, and each will require a separate executable. For instance, the executable for task 2 will be named `task2`. Note, this should ***not*** be `task2.x`, `task2.exe`, `task2.sh`, `task2.py`, or any other file extension. If this executable must be compiled, you must provide a `Makefile` to do the compilation, which will be called *without arguments* in the directory for that task. E.g., during grading, I will simply run `make` in the `task2` directory; don’t expect I will run `make task2`.Each task will operate on a *separate session*. That is, they will all be encrypted with different keys. You will have limited information about each session. We will guarantee the following about sessions:– **No transaction will have the same source and destination account.** – **Except where noted in the task description, all account numbers will appear at least twice.** – **All three transaction types will appear.** – **At a minimum, there will be one repeated BALANCE request transaction.** – **There are no partial transactions, so every transaction that begins in the session will be complete.**See the Implementation Notes below for formatting of output and other requirements.### Task 2For this task, you will provide an executable named `task2` that reads the ciphertext for a session and outputs– The types of messages, in order, with each on a separate lineThe ciphertext will be provided as the only command-line argument to your executable, and will be in the same format as the reference stream. That is, we will call it as (for an input file `task2.in`)“` ./task2 task2.in “`#### My Notes– For `reference.in`, we have that the requests to the checking account both begin with the same 16-bit signature: `07ef`. – The checking account requests are composed of 2 blocks each; we can use this to orient ourself in the task and find the rest of the requests. – This means that the $100 transfer to the checking account is 5 blocks starting with `be54`. – This leads me to believe that the first block is just the “request” syntax because it is shared with the savings account request. – Similarly, the “transfer” request starts with `be54` regardless of if it is to checking or savings. – I think that the blocks starting with `c501` denote the checking account. – Meanwhile, the block starting with `c461` denotes the savings account. – I think that the syntax of a transfer request looks like this: 1. Transfer request signature. 1. Source account. 1. Destination account. 1. Time the request is to be executed. 1. Amount of money in the request. – An invoice account looks like this: 1. Invoice request signature 1. Account requesting money. 1. Account sending money. 1. Time the request is to be executed. – The transfer request signature is: `be54 1528 f397 89ef 8749 6921 7b0a 7caa .T.(…..Ii!{.|.` – For a request to be executed immediately, its signature is: `be51 fa0d e2fb 7cef e6bd 16bc b6c1 74f3 .Q….|…….t.` – For a request to transfer $1000, its signature is: `ca26 370d 5788 6584 a78e 36f8 203d dd83 .&7.W.e…6. =..` – I tried the DP solution but I don’t actually think it works because it while it does pick out repeated substrings, it can erroneously pick out substrings that consist of requests that look similar chained together. – I don’t really know how to fix this? – We can perhaps do a thing where we orient based on know that the first line is always guaranteed to be a request signature and not anything else? – Perhaps search for similar substrings from there? The problem with this is that we aren’t guaranteed that the first request is ever repeated. – Perhaps what we can do instead is exhaustively check all of the ways that we can divide our string’s length into blocks of 2, 4 and 5 and make conjectures about how many of a given request type there are. – This would work (kinda we’d have to do prime factorization which is not fast) if 4 wasn’t a multiple of 2. – This can still allow us to know how many transfer requests those are if we perform repeated division by 2. – One piece of information we have is that the first block will always be the header of some request. – From there maybe we can find out what is different? – For instance, with `task2.in`, we have the first request header begins with `4846`. – We can then ripgrep to find that there are 4 instances of a line beginning with the digits `4846`. – From there, we know that the second line of the text file is always going to be an address of some sort. – In this instance of `task2.in`, we can also infer that the `4846` command is a transfer because it appears 5 lines from the end. – Maybe we can check for the distance between two instances of the first line? Then that’ll give us a smaller number that can tell us what kinds of requests are between it. – We can also try to figure out what the last request is. – Because `4846` is a transfer request, it certainly contains at least two addresses; the source and the target addresses. – If there are two instances of a single line and they’re separated by only one line, then we know that that’s a repeated balance request. – Based on the fact that we now (probably) have at least two account numbers because of `find_accs`, what does this let us do next? – Analyze the end of the trace because we know that there will be a last request that may or may not contain one of the request headers we have seen so far – From here, we have one of the three request headers and a bunch of account numbers. We can then try brute force to find the other two request headers? Not the most elegant solution in the world but it might yield something nice. – We can also perform modular arithmetic on the differences between the requests. – What I mean by this is that if we have two instances of our initial request that are separated by 5 blocks, then we know that the initial request is a transfer request. – Alternatively, if any two instances of our initial request are separated by 2 blocks, then we know that the initial request is a balance request. – For instance, we know that the initial request in `task2.in` is a transfer request because it has one instance at line 26 and one instance at line 31. – Alternatively, if we have that the minimum distance between any two of the initial requests is 7, then we know that either the initial request is a transfer or it is a balance. Whichever request type the initial request is not, there must be another one immediately following it.### Task 3For this task, you will provide an executable named `task3` that reads the ciphertext for a session and outputs– The types of messages, in order, with each on a separate line – A replay (unmodified copy) of a message that transfers money into your account, written to a file named `task3.out`For this session, you know that *exactly one* message includes your account, and it is transferring money to you. The file `task3.out` should include the **entire** stream, with your replay added to it. That is, there should be exactly one more message in `task3.out` than the input stream.As before, the input ciphertext stream will be provided as the only command-line argument to your executable, and will be in the same format as other streams.“` ./task3 task3.in “`### Task 4For this task, you will provide an executable named `task4` that reads the ciphertext for a session and outputs– The types of messages, in order, with each on a separate line – A modified money transfer to your account, where the amount in the transfer is changed to a valid new value, written to a file `task4.out`For this session, you know that the target sent a money transfer to your account for $10. No other requests involving your account are in this session. In addition, the target requested payments (invoices) from at least one other account.Your executable should produce a file `task4.out` containing the input ciphertext with the modified message. That is, `task4.out` should contain the same messages as the input, but with the amount changed in the payment to your account, so the target is sending you a different amount of money.As before, the input ciphertext stream will be provided as the only command-line argument to your executable, and will be in the same format as other streams.“` ./task4 task4.in “`### Task 5For this task, you will provide an executable named `task5` that reads the ciphertext for a session and outputs– The types of messages, in order, with each on a separate line – A money transfer to your account *instead of* a payment request from your account, written to a file `task5.out`For this session, you know that the target requested payment from your account, and this is the only request involving your account. You must convert this payment request *from* your account into a money transfer *to* your account.Your executable should produce a file `task5.out` containing the input ciphertext with the modified message. That is, `task5.out` should contain the same messages as the input, but with the request for payment from you changed to a transfer to you.As before, the input ciphertext stream will be provided as the only command-line argument to your executable, and will be in the same format as other streams.“` ./task5 task5.in “`## Implementation NotesThe required output must match what we have asked for **exactly**. In particular, anything not part of the required output should be printed to standard error, not standard output.The following table shows the expected way to print message types:| **Message Type** | **Value to Print** | | ——————- | —————— | | balance request | BALANCE | | money transfer | TRANSFER | | request for payment | INVOICE |## SubmissionSubmit your project to Gradescope. Please leave the structure of the directories as-is, so files for task 1 go in the `task1` directory, and so on. Do not include compiled files, only scripts, source code, and (if needed) a `Makefile`.## Grading– Correctly cracking an md5 hash in task 1 is worth 5 points. (Note: you don’t need to crack all 4, just 1!) – Identifying all messages correctly will cumulatively be worth 20 points (tasks 2-5). – Producing valid messages will cumulatively be worth 15 points (tasks 3-5). – Correctly modifying messages will cumulatively be worth 10 points (tasks 4 and 5). – Correctly changing the type of a message will be worth 5 points (task 5).## Tips### Parsing the Session StructureThere is no limit on the number of accounts showing up in a session. It might be useful to think of each account as a principal in the system (which it is). You can consider all of the accounts originating transactions as being principals that share a single identity. The attacker, in contrast, is a separate identity, and will not be initiating a transaction in tasks 2-4.You should be able to start by assuming the first transaction is of a particular type, and see what that implies for the next transaction, which will either be the same type or one of the other two. You can do this iteratively, and ultimately you’ll see one of the following:1. You have consumed the entire session, with only three transaction types appearing. 1. You have found some number of transaction types other than three. 1. You either have bytes left in the session that cannot form a new transaction, or your final transaction is incomplete.The first of these should indicate successful parsing. Either of the others means you have made an incorrect assumption/guess during your parsing, and you need to unwind. Make sure you keep track of what ciphertext corresponds to what type of field as you parse — no two fields of different types will encrypt to the same ciphertext.You should be able to enumerate all of the possibilities in your code, since there are only six ways to order three message types by the order in which they *first* occur.### Examining Binary FilesYou are strongly encouraged to view the ciphertext streams through a hex-formatting program like `xxd` or `hexdump`.### Common CodeWhile you must provide four separate executables, you will probably want to have some code in common between them. This might be an additional `.c` and `.h` file, a python file to import, or something else. You might even have a single binary, and bash scripts to call it with appropriate arguments for the individual tasks.### Using CC is a good language for working with binary data, though you are free to use any language already installed in the `baseline` image. We *will not* install additional packages for you, and you *should not* assume Internet access when building or running your code.If you would like to use C, here are some things you might find useful.#### Writing to STDERRSince we’re expecting very specific output in STDOUT, all of your debugging output should go to STDERR. You can do this with:“`C fprintf(stderr,”This is an error message ”); “`You might also find the following useful:“`C fprintf(stderr,”%s: %d ”,__FILE__,__LINE__); “`The preprocessor will replace `__FILE__` with the current file name, and `__LINE__` with the current line of the file. That means you can add this exact line anywhere you like in your code to trace the program flow. This can be extremely helpful when you’re trying to track down where a segfault is occurring.#### Working with Binary DataBe careful when working with ciphertext that you *do not* use string functions. Instead, you should use `memcpy` to copy data from one binary array to another, and `memcmp` to compare arrays. See the documentation for both of these.#### Linked ListsC does not have a library of basic data structures. Rather than creating overly-large arrays or reallocating memory and copying as you need more space, it is easy to write a simple linked list. We generally do this structure-by-structure.Consider a structure:“`C struct foo { int a; double b; } “`There are two approaches to creating a linked list of `struct foo`. One is to define a new enclosing structure:“`C struct foo_list { struct foo item; struct foo_list* next; }struct foo_list foo_HEAD; struct foo_list* foo_TAIL = &foo_HEAD; “`The global (or file-static) `foo_HEAD` is a dummy entry, and we add to the list by allocating a new `struct foo_list` (with `malloc`), assigning it to `foo_TAIL->next`, and updating `foo_TAIL` to this new pointer.The other way is to combine everything into a single `struct`:“`C struct foo { int a; double b; struct foo* next; }struct foo foo_HEAD; struct foo* foo_TAIL = &foo_HEAD; “`Which you use is largely a matter of style and preference. (It is also possible to define a generic linked list with a `void*` item, but you lose any type information when you do this.)### Using Python#### Writing to STDERRSince we’re expecting very specific output in STDOUT, all of your debugging output should go to STDERR. You can do this with:“`python print(“This is an error message”, file=sys.stderr) “`You might also find the following useful:“`python import sys_lno = lambda: print(__file__,sys._getframe().f_back.f_lineno,file=sys.stderr) “`Put this after your other imports. This grabs the current stack frame, and extracts the current line number. The `__file__` variable is replaced with the current file name. To use this, call `_lno()` anywhere in your code, so that you can trace the program flow. This can be extremely helpful when you’re trying to track down where an error is occurring.#### Working with Binary DataBinary data in python is a little more cumbersome than in C, but it is otherwise generally easier to write code in, and has useful structures like `list` and `dict`.Section 7.3 of *A General Systems Handbook* briefly discusses files, but this is from the perspective of text files. For binary files, you need to add the specifier `b` when opening the file:“`python with open(‘input_file.bin’, ‘rb’) as in_file: data = in_file.read(nbytes) # data is of type “bytes” hexdata = data.hex() # hexdata is a string of hex digits “`If you want to convert a string of hexadecimal digits back to bytes, you can do this with:“`python bindata = bytes.fromhex(hexdata) # bindata should be the same as data “`Writing is similar:“`python with open(‘output_file.bin’, ‘wb’) as out_file: out_file.write(bindata) # the bytes object above “`Python also makes it easy to tell if an item is in a list:“`python l = [‘a’ , ‘b’, ‘c’] ‘a’ in l # evaluates to True ‘d’ in l # evaluates to False “`This also works for dictionary keys:“`python d = dict() d[‘a’] = 1 d[‘b’] = 2 d[‘c’] = 3 ‘a’ in d # evaluates to True ‘d’ in d # evaluates to False “`
5/5 - (1 vote) This assignment will explore three different web-based attacks: SQL Injection,Cross-Site Scripting (XSS), and Cross-Site Request Forgery (CSRF).# Getting up and running: QEMU and Docker## New options to the QEMU commandYou will be using the same QEMU VM that you used for Project 1, but this time we will need to set up a bit more port forwarding, so the command has changed somewhat to the following: “` qemu-system-x86_64 -accel tcg -m 4G -drive if=virtio,format=qcow2,file=csci368.qcow2 -nic user,model=virtio,hostfwd=tcp:127.0.0.1:41422-:22,hostfwd=tcp:127.0.0.1:41481-:41481,hostfwd=tcp:127.0.0.1:41482-:41482,hostfwd=tcp:127.0.0.1:41483-:41483 “`The difference is that we added more `hostfwd=…` (port forwarding) options at the end. This will help make it much easier to work outside of your VM.## DockerThe tasks will all use docker images that have fully-configured servers that are vulnerable to the various attacks. While this might sound somewhat complicated (docker inside of a VM), when it’s all set up right, you’ll be able to do the project through your normal browser, outside the VM altogether!First, make sure there is no service on your host machine that is already listening on ports 41481, 41482, or 41483. (It is unlikely that there is.) How to check this differs a bit between operating systems, and there are various tools/utilities you can use, but Googling “list listening ports ” should point you in the right direction for your operating system. Common utilities include `lsof` on Mac and Linux, and `netstat` on Windows.This document will step you through the key commands to get docker running, but for more information, please see [this Docker tutorial](https://gitlab.cs.umd.edu/mmarsh/docker-tutorial).### Getting and loading docker imagesAll docker images are available on Moodle in the form of tar files; there’s one for each of the three attacks (sqli.tar, xss.tar, and csrf.tar).Download these to your computer and then copy them into your QEMU VM using `scp` (or a shared directory, if you set that up for Project 1). Assuming the VM is running, then from your host OS (outside the VM), you can simply run the following to copy the .tar file over: “` scp -P41422 sqli.tar csci368@localhost: “`(This example shows it for the SQL injection docker image, `sqli.tar`; just change the filename to copy the other ones.)Next, ssh into the QEMU VM and load each docker image individually with the `docker image load` command, which can sometimes take up to a couple minutes in the VM. For instance, to load the SQL injection docker image, run the following from within the QEMU VM: “` docker image load -i sqli.tar “`In testing, we sometimes found that running shell commands (like this one) from within VS Code could be extremely slow. For that reason, it’s *highly* recommended that you run these commands outside of VS Code, via a plain ssh session.**Please note!** I will have no access to the server containers that you are running locally, so you will need to include *everything* necessary to demonstrate your attacks in the files you submit. Pay close attention to the submission instructions in each section.## More project compatibility notesFor the Java code you will be writing, please ensure that it is compliant with **Java 1.8**.For the task `.txt` files you submit, make sure that your editor does not insert “smart” quotes; our auto-grader will be using good old-fashioned single quotes (ASCII character 0x27) and double quotes (ASCII character 0x22).For all tasks, pay close attention to the formatting specified. There’s a difference between single and double quotes, and the automated grading will be very unhappy if you use single quotes where you should have used double quotes. Not following the formatting properly is *the major reason* for missing points on task 2. In particular, the initial lines for the first 2 tasks represent the fields the auto-grader will enter into the relevant HTML forms, so please include **all** of the needed fields **exactly** as you would *enter* them manually. For tasks 3 and 5, the files you provide will be used verbatim and in their entirety, so please do not include additional information. For task 5, you may include HTML comments, but for task 3, if you feel the need to include additional information, please place it in a separate file.# Task 1: SQL Injection Attack## SetupYour goal in this task is to find and exploit a SQL-Injection vulnerability.To run the docker image:1. Start the server by running the following command from within your QEMU VM: “` docker run -d -p 41481:80 –name sql_server sqli “`(It may take a moment for the server to start up — if step 2 or 3 below doesn’t work at first, give it a minute and try again.)2. To test that the web server is running inside the VM, you can run `curl localhost:41481`; if the web server is running, you will see HTML printed to stdout.3. You can access the server in your own browser — outside the VM altogether! — at http://localhost:41481/You will not have to modify any of the files inside of the docker container or QEMU VM; all of your work for this task will be taking place strictly by interacting with the vulnerable webpage through your browser. However, it will be very helpful for you to examine some of the files in the docker image.If you want to examine files in the docker container, you have several options, all of which you have to run from within your QEMU VM: 1. `docker exec -ti sql_server bash` 2. `docker exec sql_server cat ` 3. `docker cp sql_server: `The first option gives you a shell on the running container. The commands available to you via this option are somewhat limited, but enough to navigate the file system and look at the contents of files. The second will simply dump the contents of the file (replace `` with the full path to the file) to STDOUT. The third will copy a file from the container to a local destination, and behaves very similarly to the normal `cp` command.For this task, the server you are attacking is called Collabtive, which is a web-based project management system. It has several user accounts configured. To see all the users’ account information, first log in as the admin using the password below; other users’ account information can be obtained from the post on the front page (“Users’ Account Information”; then click on the “Description” drop-down toggle near the top of the page). “` username: admin password: admin “`## SQL Injection on UPDATE StatementsIn this task, you need to make an unauthorized modification to the database. Your goal is to modify another user’s profile using SQL injections. In Collabtive, if users want to update their profiles, they can go to “My account”, click the “Edit” link, and then fill out a form to update the profile information. After the user sends the update request to the server, an `UPDATE` statement will be constructed in `include/class.user.php`. (There are several `UPDATE` statements in this file; inspect the file to determine which one is used when editing a user’s profile.)The objective of this statement is to modify the current user’s profile information in the users table. There is a SQL injection vulnerability in this SQL statement. Please find the vulnerability, and then use it to change Bob’s profile without knowing their password. For example, if you are logged in as Alice, your goal is to use the vulnerability to modify Bob’s profile information, including Bob’s password. After the attack, you should be able to log into Bob’s account with this new password.Note that passwords are not stored in their raw form in the database. If you examine the `include/class.user.php` file, you will see how passwords are stored and checked.### My Notes– They store passwords as SHA-1 hash values instead of their plaintext.– The `edit` function is the thing you’re looking for. You can find it by searching `/function edit` in Vi.– There’s something called `$mylog` which is an event log for the current session maybe? – the `class mylog` is stored in `class.mylog.php` under the same directory. – It seems that the `add` function takes four arguments: `$name`, `$type`, `$action` and `$project`. – `$action` can be in the range [1,7]. The most important one is that 2 denotes “edited”. – These all get added to a table called `log`.– This is also used to store transactions.– Almost everything in here is wrapped in `class user`– There is another function `function editpass` which I think is the one that is sent when we try to edit a user’s password. – This function takes four arguments: `$id`, `$oldpass`, `$newpass`, `$repeatpass`. – The `$pass` variables are all wrapped in a function called `mysql_real_escape_string`.– Presumably this sanitizes them?– It actually just prepends backslashes to the following characters: x00, , r, , ‘, ” and x1a. – Ohhh okay wer’re getting somewhere.– There’s a variable `$chk` which performs an unsanitized SQL query and is the thing that checkswhether you are allowed to change a user’s password.– It has the structure `$chk = mysql_query(“SELECT ID, name FROM user WHERE ID = $id AND pass = ‘$oldpass'”)`– First they set `$oldpass = sha1($oldpass)`.– They do the same for `$newpass`.– If `$newpass != $oldpass`, the function returns before the SQL query.– `$id` is an integer that presumably corresponds to the user we’re looking for. – We need some way to find Bob’s `$id`.– If it’s in the same order as they appear in the user data and they’re zero-indexed, bobwould have $id = 5.– Turns out I was wrong. The function we’re looking for is `function edit`. – In this function, almost everything is sanitized with an exception: the state name.– However, the state name removed the `=` character. – The telephone name is also unsanitized.– However, the telephone removes the `-` character. – This means that we have to do all sorts of assignment in the telephone and then comment out all the undesirable SQL stuff in the state name. – Attempt #1:– Phone: “` x’, pass=’1abedcd9967cc42ea624432d356a5f0bce7ae3a9“`– State: “ x’ WHERE name LIKE ‘bob'” —“### SubmissionYour task is to change Bob’s password by modifying a different user’s profile. Please submit a file called `task1.txt` with the following format: * line 1: Bob’s new password after your injection, wrapped in double quotes. * line 2: User whose profile you are modifying in order to carry out the attack (*not* Bob or Admin), without quotes. * lines 3-n: One line for each profile parameter you changed, like so: “` “param”=”new value” “` Please note that both the parameter name and new value should be wrapped in double quotes, so that we can clearly see any spaces you might have added. Also, the parameter name should be exactly as it appears in the HTML source code, *not* what you see on the webpage. You will have to examine the HTML or network traffic for these. (Hint: If your parameters begin with capital letters or dollar signs, you have the wrong parameter names.) The new value should be *exactly* what you type into the corresponding field of the form, including the injection. If you don’t do this, the automated grading will mark this task as failing. *All* parameters that you need to set must be included here for the automated grading to succeed. * line n+1: A blank line * lines n+2 to end: The remaining lines should contain a short write up explaining the steps you used to create a working SQL injection attack that updates Bob’s password to a new value. This is especially important if you mis-format the parameter lines, since it’s the most likely way we’ll be able to figure out what you actually should have entered during manual regrading, if needed.For example: “newpasswd” alice “foo”=”bar” … “baz”=”blah” Other explanatory stuff.When you upload your completed submission, include task1.txt.# Tasks 2 & 3: XSS AttacksYour goal in these tasks is to find ways to exploit Cross-Site Scripting vulnerabilities and demonstrate the damage that can be achieved by the attacks.To run the docker image:1. (The first time you run the image, if you haven’t already loaded the image by running “`docker image load -i sqli.tar“` inside the VM, do that first.)2. Inside the VM, start the server by running “` docker run -d -p 41482:80 –name xss_server xss “`3. You can access the server in your browser at http://localhost:41482/For these tasks, the server you are attacking is called Elgg, which is a social networking application. It has several user accounts configured, with the following credentials: USER USERNAME PASSWORD ======= ======== =========== Admin admin seedelgg Alice alice seedalice Boby boby seedboby Charlie charlie seedcharlie Samy samy seedsamy## Warmup – No submission NecessaryThe objective of this task is to embed a JavaScript program in your Elgg profile, such that when another user views your profile, the JavaScript program will be executed and an alert window will be displayed. The following JavaScript program will display an alert window: alert(‘XSS’)If you embed the above JavaScript code in your profile (e.g. in the brief description field), then any user who views your profile will see the alert window.Our next objective is to embed a JavaScript program in your Elgg profile, such that when another user views your profile, the user’s cookies will be displayed in the alert window. This can be done by adding some additional code to the JavaScript program in the previous example: alert(document.cookie);## Task 2: Stealing Cookies from the Victim’s MachineIn the warmup task, the malicious JavaScript code written by the attacker can print out the user’s cookies, but only the user can see the cookies, not the attacker. In this task, the attacker wants the JavaScript code to send the cookies to themselves. To achieve this, the malicious JavaScript code needs to send an HTTP request to the attacker, with the cookies appended to the request.We can do this by having the malicious JavaScript insert an `` tag with `src` attribute set to the attacker’s machine. When the JavaScript inserts the `img` tag, the browser tries to load the image from the URL in the `src` field; this results in an HTTP GET request sent to the attacker’s machine. Your JavaScript code should send the cookies to the port 41485 of the attacker’s machine, where the attacker has a TCP server listening to the same port. The server can print out whatever it receives. The TCP server program is included as `echoserv.py`, which is a python script, and can be run outside the VM.### SubmissionPlease submit a file called `task2.txt`. The grading will be done as follows:1. We will run the echo server on localhost on port 41485.2. We will edit the brief description field acting as the user Alice using the message contents as specified by your `task2.txt`. We will use the *entire* contents of this file, so if you need to provide additional details, please do so in a separate file.1. Then, when Boby opens this message, Boby’s cookie should be printed by the echo server.If for whatever reason you needed to test on a port other than 41485, don’t forget to change it back to 41485 once it’s working! That’s the port we’ll be using when grading.## Task 3: Session Hijacking using the Stolen CookiesAfter stealing the victim’s cookies, the attacker can do whatever the victim can do to the Elgg web server, including adding and deleting friends on behalf of the victim, deleting the victim’s posts, etc. Essentially, the attacker has hijacked the victim’s session. In this task, we will launch this session hijacking attack, and write a program to remove one of the victim’s friends.To remove one of the victim’s friends, we should first find out how a legitimate user removes a friend in Elgg. More specifically, we need to figure out what HTTP headers are sent to the server when a user removes a friend. Here is a screenshot: For this project, it may be helpful to observe HTTP requests and responses directly — a quick Google should tell you how to see requests and responses in the browser of your choice. (For instance, in Chrome and Firefox, simply right-click on a webpage and choose “Inspect”, then the “Network” tab. Now, if you make a request to remove a friend, you should see a resource named `remove?friend…` that you can click on to see headers and data. From the contents, you can identify all the parameters in the request.)Once we have understood what the HTTP request for removing friends looks like, we can write a Java program to send out the same HTTP request. The Elgg server cannot distinguish whether the request is sent out by the user’s browser or by the attacker’s Java program. As long as we set all the parameters correctly, and the session cookie is attached, the server will accept and process the HTTP request. To simplify your task, we provide you with a starter Java program, `HTTPSimpleForge.java`, that does the following:1. Open a connection to web server.2. Set the necessary HTTP header information.3. Send the request to web server.4. Get the response from web server.**Note 1:** Elgg uses two parameters `__elgg_ts` and `__elgg_token`. Make sure that you set these parameters correctly for your attack to succeed. Also, please note down the correct guid of the friend who needs to be added to the friend list. You need to use that guid in the program code for the attack to succeed.**Note 2:** You can compile a Java program into bytecode for **Java 1.8** by running javac –release=8 HTTPSimpleForge.javaon the console. You can then run the bytecode by running java HTTPSimpleForge### SubmissionPlease submit a file called `HTTPSimpleForge.java`.### GradingYour java file will be compiled into byte code and executed (from outside the VM). Before running your compiled code, we will login as Alice and add Boby as a friend to Alice. Then, we will try to remove Boby as Alice’s friend by running your compiled code. Make sure you include the correct guid and parameters in the code so that the above scenario executes properly!**Input:** Your java program should read from an input file called `HTTPSimpleForge.txt`. This filename should be hard-coded into your program; it *will not* be passed on the command line. The first line of the input file contains the `__elgg_ts` token (absolute value), the second line contains the `__elgg_token` (absolute value) and the third line would contain the Cookie HTTP header value: Elgg=As an example: 1402467511 80923e114f5d6c5606b7efaa389213b3 Elgg=7pgvml3vh04m9k99qj5r7ceho4You can create a text file locally for testing out your code; however, you do not need to submit this file as part of your submission. We will use our own `HTTPSimpleForge.txt` file for checking.### My Notes– Adding a friend produces the following GET request:“`http://localhost:41482/action/friends/add?friend=40&__elgg_ts=1741283347&__elgg_token=b678b7df613f4943fa24f5e32fcb58f3“`– This was what happened when I added Boby as a friend from Alice’s account.– Removing a friend produces the following GET request:“`http://localhost:41482/action/friends/remove?friend=40&__elgg_ts=1741283351&__elgg_token=27f3598550554619312600a42ebc20f1“`– This was similarly what happened when I tried to remove Boby as a friend from Alice’s account.– I can’t find the rhyme or reason to the `elgg_token` or the `elgg_ts` variables. – The `elgg_ts` variable always seems to go up–presumably by a number of seconds–but I don’t know how I’d hard-code a variable like this. – Meanwhile, the `elgg_token` variable seems entirely random. Probably a SHA-1 hash.– I think that the `guid = 40` for Boby.# CSRF AttackYour goal in this task is to find ways to exploit a Cross-Site Request Forgery vulnerability.Steps for running docker image:1. Start the server by running the following from within the QEMU VM: “` docker run -d -p 41483:80 -v “$(pwd):/var/www/CSRF/Attacker” –name csrf_server csrf “`2. You can access the server in your browser (outside the VM) at http://localhost:41483/This is running a slightly different version of Elgg, but has the same users and credentials as in the XSS tasks.## Task 4: CSRF Attack using GET RequestIn this task, we need two people in the Elgg social network: Alice and Boby. Alice wants to become a friend to Boby, but Boby refuses to add Alice to his Elgg friend list. Alice decides to use the CSRF attack to achieve her goal. Shesends Boby a URL (via an email or a posting in Elgg); Boby, curious about it, clicks on the URL. Pretend that you are Alice, and think about how you can construct the contents of the web page, so as soon as Boby visits the web page, Alice is added to the friend list of Boby (assuming Boby has an active session with Elgg).To add a friend to the victim, we need to identify the Add Friend HTTP request, which is a GET request. In this task, you are not allowed to write JavaScript code to launch the CSRF attack. Your job is to make the attack successful as soon as Boby visits the web page, without even clicking on the page (hint: one good solution involves using the `img` tag, which automatically triggers an `HTTP GET` request).Whenever the victim user visits the crafted web page in the malicious site, the web browser automatically issues an `HTTP GET` request for the URL contained in the `img` tag. Because the web browser automatically attaches the session cookie to the request, the trusted site cannot distinguish the malicious request from the genuine request and ends up processing the request, compromising the victim user’s session integrity.Observe the request structure for adding a new friend and then use this to forge a new request to the application. When the victim user visits the malicious web page, a malicious request for adding a friend should be injected into the victim’s active session with Elgg.### SubmissionYou are required to submit a file named `task4.html`. When a victim user named Boby is logged in, and visits the attacker website `localhost:41483/task4.html` in another tab, Alice should be added as a friend to Boby’s Friend List.To test this, you will need to place the `task4.html` file under the directory `/var/www/CSRF/elgg/` in the docker container. You can do this by running the following from within the QEMU VM (assuming `task4.html` has already been copied into the VM): docker cp task5.html csrf_server:/var/www/CSRF/elgg**Tip:** Your browser may not refresh on its own. You might need to press the reload/refresh button to reload the page, to see if Alice is added as a friend to Boby’s account.**Remember:** I cannot access your docker containers directly! You will need to include `task4.html` in your submission.# Submission checklistWhen you’re finished, you should have one file per task:* task1.txt – SQL injection attack* task2.txt – first XSS attack* HTTPSimpleForge.Java – second XSS attack* task4.txt – CSRF attack
Task 0: Off to a malicious start!To start things off, you’ve been provided a program that you get to write part of.The program we provide: – Takes as a command-line argument the name of a file, which it opens. – The program then asks your function (`your_fcn()`) for a string, writes that string to the file, and closes the file. – It then re-opens the file, and attempts to “sanitize” the string you provided by removing all instances of the substring “`368`” from it. – Finally, it overwrites the file with this “sanitized” version of the string.For example, if your function generated the string “I love CSCI 368!” then we would get the following output:“` csci368@csci368:~$ ./task0a.x file.txt csci368@csci368:~$ cat file.txt I love CSCI ! “`**Your goal is to write `your_fcn()` in such a way that the file whose name is provided on the command-line still has the substring “`368`” in it.**A simple way to test whether your solution correct is with the command `grep 368`. You can use it to return lines containing the string “`368`” as follows:“` csci368@csci368:~$ grep 368 file.txt “`If this returns nothing (as the above case would), then that means the file does not have “`368`” in it.We provide three copies of this program: `task0a.c`, `task0b.c`, and `task0c.c`. All of them have the same goal, but **you must provide a *functionally unique* solution in each of the three**; they cannot simply be slight variations of one another (e.g., if one of your solutions was `printf(x)` then another cannot be `puts(x)` as those are functionally the same thing).There are many different ways to solve this! Some might involve buffer overflows, and some might not. We are not requiring any one particular solution; just like with any attack, what matters is whether it achieves the goal, even if it’s not a method we anticipated. *Be creative* and have fun with it!Please note that your solution is *only* allowed to modify `your_fcn()` in these files. (You may change other parts of the files for testing, but keep in mind that when I grade your project, I will paste your `your_fcn()` into a fresh copy of the starter code.)## Task 1: Attacking a vulnerable program with malicious inputsIn Task 1, you will be exploiting programs that have a buffer overflow vulnerability. Unlike Task 0, you are not allowed to modify the program itself; instead, you will be attacking it by cleverly constructing malicious inputs to the program.The vulnerable programs are `vulnerable1.c` through `vulnerable3.c`; your solutions cannot involve modifying those programs (when I grade your project, I will use unmodified versions of the vulnerable programs). Rather, you will be modifying the corresponding exploit programs, `exploit1.c` through `exploit3.c`.Each of the vulnerable programs is a little different. They’ve been designed so that they increase in difficulty; you’ll apply what you learn in solving `vulnerable1` to inform how to do `vulnerable2`, which will in turn inform you how to do `vulnerable3`, where you will be injecting code that will reveal a secret!**In `vulnerable1` and `vulnerable2`, your goal is to get `sensitive_function` to run. In `vulnerable3`, your goal is to run the provided shellcode as root.**The way these programs interact with one another is through some networking code that has been provide for you in `comms.h` and `comms.c`; you do not have to concern yourself with the networking code. Just focus on constructing the right `greeting` (when appropriate), analyzing the vulnerable program’s `response` (when appropriate), and constructing the correct `buffer` to solve the given challenge.### Building and running the programsThere is a provided Makefile for compiling the files in Task 1. Your solutions cannot involve modifying the Makefile (when I grade your projects, I will use the unmodified version of the Makefile).To run, first build using `make`. Then, run the `vulnerable` program first, followed by the corresponding `exploit` program. For example:“` csci368@csci368:~$ ./vulnerable1.x & csci368@csci368:~$ ./exploit1.x “`The first command’s use of `&` means to run the vulnerable program in the background; this means that it will immediately return us to the terminal but it will keep running. Alternatively, you could run `vulnerable` in one terminal and `exploit` in another (this is especially helpful if you want to run the `vulnerable` programs in `gdb`, and trust us, you do!).In `exploit3.c`, you will see that you have been provided with the shell code. In fact, there are two examples of shell code: one (commented out) is traditional shell code that actually launches a shell (`/bin/sh`). The other “shell code” provided executes a different command: `/bin/cat /var/secret/token`; this is a file created by the Makefile that only root has access to read. Because `vulnerable3.x` is compiled as root, when injected with this shell code, it will be able to read the token—even if the user running `vulnerable3.x` is not root! This shows the power of privilege escalation.## Task 2: Writing secure codeIn the last task, your job is to patch `vulnerable3.c` to defend against exactly the sort of exploits you wrote in part 1. `task2a_vulnerable3.c` and `task2b_vulnerable3.c` contain the same `main` function as `vulnerable3.c`. Each of those files contains the beginnings of a defense. In 2a, you’ll write more secure versions of `strcpy` and `sprintf`; in 2b, you’ll write a filtering function that checks user input against a file (`allowlist`). Replace the `TODO`s with your own code (leaving other parts alone, as before); for part 2b, you may also edit the `allowlist` file.**Your goal for both `task2a_vulnerable3.c` and `task2b_vulnerable3.c` is to ensure that `main` exits normally, despite an attacker’s best efforts to craft clever responses.** (To receive full credit, your defense should be robust, in the sense that it should defend against an attacker able to apply the general techniques you leveraged in Part 1, rather than any single specific implementation of an attack you may have written for in Part 1.)## Submission ChecklistA finished project will consist of the following (completed) files: – task0a.c – task0b.c – task0c.c – exploit1.c – exploit2.c – exploit3.c – allowlist – task2a_vulnerable3.c – task2b_vulnerable3.cYou don’t need to upload any other files (and your solutions shouldn’t rely on any additional files beyond the (unmodified) starter code).Submissions that are missing some of these files will still be graded, but you won’t earn any points for the missing parts.## Grading CriteriaA solution is correct if running the program results in the goal behavior (while abiding by any restrictions or limitations mentioned above). Correct solutions will receive full credit. Incorrect code that shows evidence of progress towards a correct solution may receive a limited amount of partial credit.* Task 0 [30 points] – 10 points awarded per distinct correct implementation of `your_fnc` across `task0a.c`, `task0a.c`, and `task0a.c`. * Task 1 [40 points] – 15 points for each of `vulnerable1.c` and `vulnerable2.c`; 10 points for `vulnerable3.c` * Task 2 [30 points] – 15 points for each of `task2a_vulnerable3.c` and `task2a_vulnerable3.c`Total: 100 points## Miscellaneous helpful tips### Not all character arrays are “C strings”Recall: `strlen()` only works for null-terminated ASCII strings; if you are sending binary data then you either want to compute the length of the data you’re sending or at least use `sizeof(buffer)`.### gdb is your friend!Here are some useful commands for running and stepping through a running program: – `b `: Set a breakpoint at `` (pause execution whenever that function is reached). – `r`: Run the program from the beginning. – `s`: (Used after you’ve hit a breakpoint.) Step to the next line of code. – `c`: (Used after you’ve hit a breakpoint.) Continue: let the program execute until it hits another breakpoint.Here are some useful commands for inspecting the memory of the running process: – `i f` (short for `info frame`): Shows info about the current stack frame, including the addresses where the saved %eip and %ebp are. – `x/32xw `: Print 32 words (`w`) in hex format (`x`) starting at address ``. The `` can either be a raw address (e.g., `0x12345678`) or a function name (e.g., `main`). – `p `: Print the result of the expression, which could be a variable (`p var`), the address of a variable (`p &var`), or a more complicated C expression (`p (int) strlen(var)`).
1. Kleinberg, Jon. Algorithm Design (p. 782, q. 1). 3-Coloring is a yes/no question, but we can phrase it as an optimization problem as follows. Suppose we are given a graph G = (V, E), and we want to color each node with one of three colors, even if we aren’t necessarily able to give different colors to every pair of adjacent nodes. Rather, we say that an edge (u, v) is satisfied if the colors assigned to u and v are different. Consider a 3-coloring that maximizes the number of satisfied edges, and let c ∗ denote this number. Give a polynomial-time algorithm that produces a 3-coloring that satisfies at least 2 3 c ∗ edges. If you want, your algorithm can be randomized; in this case, the expected number of edges it satisfies should be at least 2 3 c ∗ . CS 577 Assignment 13 – Randomization 2. Kleinberg, Jon. Algorithm Design (p. 787, q. 7). In lecture, we designed an approximation algorithm to within a factor of 7/8 for the MAX 3-SAT Problem, where we assumed that each clause has terms associated with three different variables. In this problem, we will consider the analogous MAX SAT Problem: Given a set of clauses C1, · · · , Ck over a set of variables X = {x1, · · · , xn}, find a truth assignment satisfying as many of the clauses as possible. Each clause has at least one term in it, and all the variables in a single clause are distinct, but otherwise we do not make any assumptions on the length of the clauses: There may be clauses that have a lot of variables, and others may have just a single variable. (a) First consider the randomized approximation algorithm we used for MAX 3-SAT, setting each variable independently to true or false with probability 1/2 each. Show that in the MAX SAT, the expected number of clauses satisfied by this random assignment is at least k/2, that is, at least half of the clauses are satisfied in expectation. (b) Give an example to show that there are MAX SAT instances such that no assignment satisfies more than half of the clauses. Page 2 of 7 CS 577 Assignment 13 – Randomization (c) If we have a clause that consists only of a single term (e.g., a clause consisting just of x1, or just of x2), then there is only a single way to satisfy it: We need to set the corresponding variable in the appropriate way. If we have two clauses such that one consists of just the term xi , and the other consists of just the negated term xi , then this is a pretty direct contradiction. Assume that our instance has no such pair of “conflicting clauses”; that is, for no variable xi do we have both a clause C = {xi} and a clause C ′ = {xi}. Modify the randomized procedure above to improve the approximation factor from 1/2 to at least 0.6. That is, change the algorithm so that the expected number of clauses satisfied by the process is at least 0.6k. Page 3 of 7 CS 577 Assignment 13 – Randomization (d) Give a randomized polynomial-time algorithm for the general MAX SAT Problem, so that the expected number of clauses satisfied by the algorithm is at least a 0.6 fraction of the maximum possible. (Note that, by the example in part (a), there are instances where one cannot satisfy more than k/2 clauses; the point here is that we’d still like an efficient algorithm that, in expectation, can satisfy a 0.6 fraction of the maximum that can be satisfied by an optimal assignment.) Page 4 of 7 CS 577 Assignment 13 – Randomization 3. Kleinberg, Jon. Algorithm Design (p. 789, q. 10). Consider a very simple online auction system that works as follows. There are n bidding agents; agent i has a bid bi , which is a positive natural number. We will assume that all bids bi are distinct from one another. The bidding agents appear in an order chosen uniformly at random, each proposes its bid bi in turn, and at all times the system maintains a variable b ∗ equal to the highest bid seen so far. (Initially b ∗ is set to 0.) What is the expected number of times that b ∗ is updated when this process is executed, as a function of the parameters in the problem? Page 5 of 7 CS 577 Assignment 13 – Randomization 4. Recall that in an undirected and unweighted graph G = (V, E), a cut is a partition of the vertices (S, V S) (where S ⊆ V ). The size of a cut is the number of edges which cross the cut (the number of edges (u, v) such that u ∈ S and v ∈ V S). In the MAXCUT problem, we try to find the cut which has the largest value. (The decision version of MAXCUT is NP-complete, but we will not prove that here.) Give a randomized algorithm to find a cut which, in expectation, has value at least 1/2 of the maximum value cut. Page 6 of 7 CS 577 Assignment 13 – Randomization 5. Implement an algorithm which, given a MAX 3-SAT instance, produces an assignment which satisfies at least 7/8 of the clauses, in either C, C++, C#, Java, or Python. The input will start with a positive integer n giving the number of variables, then a positive integer m giving the number of clauses, and then m lines describing each clause. The description of the clause will have three integers x y z, where |x| encodes the variable number appearing in the first literal in the clause, the sign of x will be negative if and only if the literal is negated, and likewise for y and z to describe the two remaining literals in the clause. For example, 3 − 1 − 4 corresponds to the clause x3 ∧ x1 ∧ x4. A sample input is the following: 10 5 -1 -2 -5 6 9 4 -9 -7 -8 2 -7 10 -1 3 -6 Your program should output an assignment which satisfies at least ⌊7/8⌋m clauses. Return n numbers in a line, using a ±1 encoding for each variable (the ith number should be 1 if xi is assigned TRUE, and −1 otherwise). The maximum possible number of satisfied clauses is 3, so your assignment should satisfy at least ⌊ 7 8 × 3⌋ = 2 clauses. One possible correct output to the sample input would be: -1 1 1 1 1 1 -1 1 1 1
1. Kleinberg, Jon. Algorithm Design (p. 506, q. 4). A system has a set of n processes and a set of m resources. At any point in time, each process specifies a set of resources that it requests to use. Each resource might be requested by many processes at once; but it can only be used by a single process at a time. If a process is allocated all the resources it requests, then it is active; otherwise it is blocked. Thus we phrase the Resource Reservation Problem as follows: Given a set of processes and resources, the set of requested resources for each process, and a number k, is it possible to allocate resources to processes so that at least k processes will be active? For the following problems, either give a polynomial-time algorithm or prove the problem is NP-complete. (a) The general Resource Reservation Problem defined above. Solution: CS 577 Assignment 11 – Intractability (b) The special case of the problem when k = 2. Solution: (c) The special case of the problem when there are two types of resources–say, people and equipment– and each process requires at most one resource of each type (In other words, each process requires one specific person and one specific piece of equipment.) Solution: (d) The special case of the problem when each resource is requested by at most two processes. Solution: Page 2 of 6 CS 577 Assignment 11 – Intractability 2. Kleinberg, Jon. Algorithm Design (p. 506, q. 7). The 3-Dimensional Matching Problem is an NPcomplete problem defined as follows: Given disjoint sets X, Y , and Z, each of size n, and given a set T ⊆ X × Y × Z of ordered triples, does there exist a set of n triples in T that each element of X ∪ Y ∪ Z is contained in exactly one of these triples? Since 3-Dimensional Matching is NP-complete, it is natural to expect that the 4-Dimensional Problem is at least as hard. Let us define 4-Dimensional Matching as follows. Given sets W, X, Y , and Z, each of size n, and a collection C of ordered 4-tuples of the form (wi , xj , yk, zℓ), do there exist n 4-tuples from C such that each element of W ∪ Y ∪ X ∪ Z appears in exactly one of these 4-tuples? Prove that 4-Dimensional Matching is NP-complete. Hint: use a reduction from 3-Dimensional Matching. Solution: Page 3 of 6 CS 577 Assignment 11 – Intractability 3. Kleinberg, Jon. Algorithm Design (p. 507, q. 6). Consider an instance of the Satisfiability Problem, specified by clauses C1, …, Cm over a set of Boolean variables x1, …, xn. We say that the instance is monotone if each term in each clause consists of a nonnegated variable; that is, each term is equal to xi , for some i, rather than xi . Monotone instances of Satisfiability are very easy to solve: They are always satisfiable, by setting each variable equal to 1. For example, suppose we have the three clauses (x1 ∨ x2),(x1 ∨ x3),(x2 ∨ x3). This is monotone, and the assignment that sets all three variables to 1 satisfies all the clauses. But we can observe that this is not the only satisfying assignment; we could also have set x1 and x2 to 1, and x3 to 0. Indeed, for any monotone instance, it is natural to ask how few variables we need to set to 1 in order to satisfy it. Given a monotone instance of Satisfiability, together with a number k, the problem of Monotone Satisfiability with Few True Variables asks: Is there a satisfying assignment for the instance in which at most k variables are set to 1? Prove this problem is NP-complete. Solution: Page 4 of 6 CS 577 Assignment 11 – Intractability 4. Kleinberg, Jon. Algorithm Design (p. 509, q. 10). Your friends at WebExodus have recently been doing some consulting work for companies that maintain large, publicly accessible Web sites and they’ve come across the following Strategic Advertising Problem. A company comes to them with the map of a Web site, which we’ll model as a directed graph G = (V, E). The company also provides a set of t trails typically followed by users of the site; we’ll model these trails as directed paths P1, P2, …, Pt in the graph G (i.e., each Pi is a path in G). The company wants WebExodus to answer the following question for them: Given G, the paths {Pi}, and a number k, is it possible to place advertisements on at most k of the nodes in G, so that each path Pi includes at least one node containing an advertisement? We’ll call this the Strategic Advertising Problem, with input G, {Pi : i = 1, …, t}, and k. Your friends figure that a good algorithm for this will make them all rich; unfortunately, things are never quite this simple. (a) Prove that Strategic Advertising is NP-Complete. Solution: Page 5 of 6 CS 577 Assignment 11 – Intractability (b) Your friends at WebExodus forge ahead and write a pretty fast algorithm S that produces yes/no answers to arbitrary instances of the Strategic Advertising Problem. You may assume that the algorithm S is always correct. Using the algorithm S as a black box, design an algorithm that takes input G, {Pi : i = 1, …, t}, and k as in part (a), and does one of the following two things: • Outputs a set of at most k nodes in G so that each path Pi includes at least one of these nodes. • Outputs (correctly) that no such set of at most k nodes exists. Your algorithm should use at most polynomial number of steps, together with at most polynomial number of calls to the algorithm S. Solution:
1. Kleinberg, Jon. Algorithm Design (p. 512, q. 14) We’ve seen the Interval Scheduling Problem several times now, in dierent variations. Here we’ll consider a computationally much harder version we’ll call Multiple Interval Scheduling. As before, you have a processor that is available to run jobs over some period of time. People submit jobs to run on the processor. The processor can only work on one job at any single point in time. Jobs in this model, however, are more complicated than we’ve seen before. Each job requires a set of intervals of time during which it needs to use the processor. For example, a single job could require the processor from 10am to 11am and again from 2pm to 3pm. If you accept the job, it ties up your processor during those two hours, but you could still accept jobs that need time between 11am and 2pm. You are given a set of n jobs, each speci ed by a set of time intervals. For a given number k, is it possible to accept at least k of the jobs so that no two accepted jobs overlap in time? Show that Multiple Interval Scheduling is NP-Complete. CS 577 Assignment 12 More Intractability 2. Kleinberg, Jon. Algorithm Design (p. 519, q. 28) Consider this version of the Independent Set Problem. You are given an undirected graph G and an integer k. We will call a set of nodes I strongly independent if, for any two nodes v, u ∈ I, the edge (v, u) is not present in G, and neither is there a path of two edges from u to v, that is, there is no node w such that both (v, w) and (u, w) are present in G. The Strongly Independent Set problem is to decide whether G has a strongly independent set of size at least k. Show that the Strongly Independent Set Problem is NP-Complete. Page 2 of 4 CS 577 Assignment 12 More Intractability 3. Kleinberg, Jon. Algorithm Design (p. 527, q. 39) The Directed Disjoint Paths Problem is de ned as follows: We are given a directed graph G and k pairs of nodes (s1, t1), . . . ,(sk, tk). The problem is to decide whether there exist node-disjoint paths P1, . . . , Pk so that Pi goes from si to ti . Show that Directed Disjoint Paths is NP-Complete. Page 3 of 4 CS 577 Assignment 12 More Intractability 4. Kleinberg, Jon. Algorithm Design (p. 508, q. 9) The Path Selection Problem may look initially similar to the problem from the question 3. Pay attention to the dierences between them! Consider the following situation: You are managing a communications network, modeled by a directed graph G. There are c users who are interested in making use of this network. User i issues a request to reserve a speci c path Pi in G on which to transmit data. You are interested in accepting as many path requests as possible, but if you accept both Pi and Pj , the two paths cannot share any nodes. Thus, the Path Selection Problem asks, given a graph G and a set of requested paths P1, . . . , Pc (each of which must be a path in G), and given a number k, is it possible to select at least k of the paths such that no two paths selected share any nodes? Show that Path Selection is also NP-Complete.
1. Kleinberg, Jon. Algorithm Design (p.416 q.6). Suppose you’re a consultant for the Ergonomic Architecture Commission, and they come to you with the following problem. They’re really concerned about designing houses that are “user-friendly”, and they’ve been having a lot of trouble with the setup of light fixtures and switches in newly designed houses. Consider, for example, a one-floor house with n light fixtures and n locations for light switches mounted in the wall. You’d like to be able to wire up one switch to control each light fixture, in such a way that a person at the switch can see the light fixture being controlled. Figure 1: The floor plan in (a) is ergonomic, because we can wire switches to fixtures in such a way that each fixture is visible from the switch that controls it. (This can be done by wiring switch 1 to a, switch 2 to b, and switch 3 to c.) The floor plan in (b) is not ergonomic, because no such wiring is possible. Sometimes this is possible and sometimes it isn’t. Consider the two simple floor plans for houses in Figure 1. There are three light fixtures (labelled a, b, c) and three switches (labelled 1, 2, 3). It is possible to wire switches to fixtures in Figure 1(a) so that every switch has a line of sight to the fixture, but this is not possible in Figure 1(b). Let’s call a floor plan, together with n light fixture locations and n switch locations, ergonomic if it’s possible to wire one switch to each fixture so that every fixture is visible from the switch that controls it. A floor plan will be represented by a set of m horizontal or vertical line segments in the plane (the walls), where the i-th wall has endpoints (xi , yi),(x ′ i , y′ i ). Each of the n switches and each of the n fixtures is given by its coordinates in the plane. A fixture is visible from a switch if the line segment joining them does not cross any of the walls. Give an algorithm to decide if a given floor plan is ergonomic. The running time should be polynomial in m and n. You may assume that you have a subroutine with O(1) running time that takes two line segments as input and decides whether or not they cross in the plane. CS 577 Assignment 10 – More Network Flow Solution: Page 2 of 7 CS 577 Assignment 10 – More Network Flow 2. Kleinberg, Jon. Algorithm Design (p.426 q.20). Your friends are involved in a large-scale atmospheric science experiment. They need to get good measurements on a set S of n different conditions in the atmosphere (such as the ozone level at various places), and they have a set of m balloons that they plan to send up to make these measurements. Each balloon can make at most two measurements. Unfortunately, not all balloons are capable of measuring all conditions, so for each balloon i = 1, . . . , m, they have a set Si of conditions that balloon i can measure. Finally, to make the results more reliable, they plan to take each measurement from at least k different balloons. (Note that a single balloon should not measure the same condition twice.) They are having trouble figuring out which conditions to measure on which balloon. Example. Suppose that k = 2, there are n = 4 conditions labelled c1, c2, c3, c4, and there are m = 4 balloons that can measure conditions, subject to the limitation that S1 = S2 = c1, c2, c3, and S3 = S4 = c1, c3, c4. Then one possible way to make sure that each condition is measured at least k = 2 times is to have • balloon 1 measure conditions c1, c2, • balloon 2 measure conditions c2, c3, • balloon 3 measure conditions c3, c4, and • balloon 4 measure conditions c1, c4. (a) Give a polynomial-time algorithm that takes the input to an instance of this problem (the n conditions, the sets Si for each of the m balloons, and the parameter k) and decides whether there is a way to measure each condition by k different balloons, while each balloon only measures at most two conditions. Solution: Page 3 of 7 CS 577 Assignment 10 – More Network Flow (b) You show your friends a solution computed by your algorithm from (a), and to your surprise they reply, “This won’t do at all—one of the conditions is only being measured by balloons from a single subcontractor.” You hadn’t heard anything about subcontractors before; it turns out there’s an extra wrinkle they forgot to mention… Each of the balloons is produced by one of three different subcontractors involved in the experiment. A requirement of the experiment is that there be no condition for which all k measurements come from balloons produced by a single subcontractor. Explain how to modify your polynomial-time algorithm for part (a) into a new algorithm that decides whether there exists a solution satisfying all the conditions from (a), plus the new requirement about subcontractors. Solution: Page 4 of 7 CS 577 Assignment 10 – More Network Flow 3. Kleinberg, Jon. Algorithm Design (p.442, q.41). Suppose you’re managing a collection of k processors and must schedule a sequence of m jobs over n time steps. The jobs have the following characteristics. Each job j has an arrival time aj when it is first available for processing, a length ℓj which indicates how much processing time it needs, and a deadline dj by which it must be finished. (We’ll assume 0 < ℓj ≤ dj − aj .) Each job can be run on any of the processors, but only on one at a time; it can also be preempted and resumed from where it left off (possibly after a delay) on another processor. Moreover, the collection of processors is not entirely static either: You have an overall pool of k possible processors; but for each processor i, there is an interval of time [ti , t′ i ] during which it is available; it is unavailable at all other times. Given all this data about job requirements and processor availability, you’d like to decide whether the jobs can all be completed or not. Give a polynomial-time (in k, m, and n) algorithm that either produces a schedule completing all jobs by their deadlines or reports (correctly) that no such schedule exists. You may assume that all the parameters associated with the problem are integers. Example. Suppose we have two jobs J1 and J2. J1 arrives at time 0, is due at time 4, and has length 3. J2 arrives at time 1, is due at time 3, and has length 2. We also have two processors P1 and P2. P1 is available between times 0 and 4; P2 is available between times 2 and 3. In this case, there is a schedule that gets both jobs done. • At time 0, we start job J1 on processor P1. • At time 1, we preempt J1 to start J2 on P1. • At time 2, we resume J1 on P2. (J2 continues processing on P1.) • At time 3, J2 completes by its deadline. P2 ceases to be available, so we move J1 back to P1 to finish its remaining one unit of processing there. • At time 4, J1 completes its processing on P1. Notice that there is no solution that does not involve preemption and moving of jobs. Solution: Page 5 of 7 CS 577 Assignment 10 – More Network Flow 4. Kleinberg, Jon. Algorithm Design (p.444, q.45). Consider the following definition. We are given a set of n countries that are engaged in trade with one another. For each country i, we have the value si of its budget surplus; this number may be positive or negative, with a negative number indicating a deficit. For each pair of countries i, j, we have the total value eij of all exports from i to j; this number is always nonnegative. We say that a subset S of the countries is free-standing if the sum of the budget surpluses of the countries in S, minus the total value of all exports from countries in S to countries not in S, is nonnegative. Give a polynomial-time algorithm that takes this data for a set of n countries and decides whether it contains a nonempty free-standing subset that is not equal to the full set. Solution: Page 6 of 7 CS 577 Assignment 10 – More Network Flow 5. Implement an algorithm to determine the maximum matching in a bipartite graph and if that matching is perfect (all nodes are matched) in either C, C++, C#, Java, Python, or Rust. Be efficient and use your max-flow implementation from the previous week. The input will start with an positive integer, giving the number of instances that follow. For each instance, there will be 3 positive integers m, n, and q. Numbers m and n are the number of nodes in node set A and node set B. Number q is the number of edges in the bipartite graph. For each edge, there will be 2 more positive integers i, and j representing an edge between node 1 ≤ i ≤ m in A and node 1 ≤ i ≤ n in B. A sample input is the following: 3 2 2 4 1 1 1 2 2 1 2 2 2 3 4 2 3 2 1 1 2 2 2 5 5 10 1 1 1 3 2 1 2 2 2 3 2 4 3 4 4 4 5 4 5 5 The sample input has 3 instances. For each instance, your program should output the size of the maximum matching, followed by a space, followed by an N if the matching is not perfect and a Y if the matching is perfect. Each output line should be terminated by a newline. The correct output to the sample input would be: 2 Y 2 N 4 N
1. Kleinberg, Jon. Algorithm Design (p. 415, q. 3a) The figure below shows a flow network on which an s − t flow has been computed. The capacity of each edge appears as a label next to the edge, and the flow is shown in boxes next to each edge. An edge with no box has no flow being sent down it. (a) What is the value of this flow? Solution: (b) Please draw the residual graph associated with this flow. Solution: (c) Is this a maximum s−t flow in this graph? If not, describe an augmenting path that would increase the total flow. Solution: CS 577 Assignment 9 – Network Flow 2. Kleinberg, Jon. Algorithm Design (p. 419, q. 10) Suppose you are given a directed graph G = (V, E). This graph has a positive integer capacity ce on each edge, a source s ∈ V , a sink t ∈ V . You are also given a maximum s − t flow through G: f. You know that this flow is acyclic (no cycles with positive flow all the way around the cycle), and every flow fe ∈ f has an integer value. Now suppose we pick an edge e ∗ and reduce its capacity by 1 unit. Show how to find a maximum flow in the resulting graph G∗ in time O(m + n), where n = |V | and m = |E|. Solution: 3. Kleinberg, Jon. Algorithm Design (p. 420, q. 11) A friend of yours has written a very fast piece of code to calculate the maximum flow based on repeatedly finding augmenting paths. However, you realize that it’s not always finding the maximum flow. Your friend never wrote the part of the algorithm that uses backward edges! So their program finds only augmenting paths that include all forward edges, and halts when no more such augmenting paths remain. (Note: We haven’t specified how the algorithm selects forward-only augmenting paths.) When confronted, your friend claims that their algorithm may not produce the maximum flow every time, but it is guaranteed to produce flow which is within a factor of b of maximum. That is, there is some constant b such that no matter what input you come up with, their algorithm will produce flow at least 1/b times the maximum possible on that input. Is your friend right? Provide a proof supporting your choice. Solution: Page 2 of 4 CS 577 Assignment 9 – Network Flow 4. Kleinberg, Jon. Algorithm Design (p. 418, q. 8) Consider this problem faced by a hospital that is trying to evaluate whether its blood supply is sufficient: In a (simplified) model, the patients each have blood of one of four types: A, B, AB, or O. Blood type A has the A antigen, type B has the B antigen, AB has both, and O has neither. Patients with blood type A can receive either A or O blood. Likewise patients with type B can receive either B or O type blood. Patients with type O can only receive type O blood, and patients with type AB can receive any of the four types. (a) Let integers sO, sA, sB, sAB denote the hospital’s blood supply on hand, and let integers dA, dB, dO, dAB denote their projected demand for the coming week. Give a polynomial time algorithm to evaluate whether the blood supply is enough to cover the projected need. Solution: (b) Network flow is one of the most powerful and versatile tools in the algorithms toolbox, but it can be difficult to explain to people who don’t know algorithms. Consider the following instance. Show that the supply is insufficient in this case, and provide an explanation for this fact that would be understandable to a non-computer scientist. (For example: to a hospital administrator.) Your explanation should not involve the words flow, cut, or graph. blood type supply demand O 50 45 A 36 42 B 11 8 AB 8 3 Solution: Page 3 of 4 CS 577 Assignment 9 – Network Flow 5. Implement the Ford-Fulkerson method for finding maximum flow in graphs with only integer edge capacities, in either C, C++, C#, Java, or Python. Be efficient and implement it in O(mF) time, where m is the number of edges in the graph and F is the value of the maximum flow in the graph. We suggest using BFS or DFS to find augmenting paths. (You may be able to do better than this.) The input will start with a positive integer, giving the number of instances that follow. For each instance, there will be two positive integers, indicating the number of nodes n = |V | in the graph and the number of edges |E| in the graph. Following this, there will be |E| additional lines describing the edges. Each edge line consists of a number indicating the source node, a number indicating the destination node, and a capacity. The nodes are not listed separately, but are numbered {1 . . . n}. Your program should compute the maximum flow value from node 1 to node n in each given graph. A sample input is the following: 2 3 2 2 3 4 1 2 5 6 9 1 2 9 1 3 4 2 4 1 2 5 6 3 4 4 3 5 5 4 6 8 5 6 5 5 6 3 The sample input has two instances. For each instance, your program should output the maximum flow on a separate line. Each output line should be terminated by a newline. The correct output for the sample input would be: 4 11
Do NOT write pseudocode when describing your dynamic programs. Rather give the Bellman Equation, describe the matrix, its axis and how to derive the desired solution from it. 1. Kleinberg, Jon. Algorithm Design (p. 327, q. 16). In a hierarchical organization, each person (except the ranking officer) reports to a unique superior officer. The reporting hierarchy can be described by a tree T, rooted at the ranking officer, in which each other node v has a parent node u equal to his or her superior officer. Conversely, we will call v a direct subordinate of u. Consider the following method of spreading news through the organization. • The ranking officer first calls each of her direct subordinates, one at a time. • As soon as each subordinate gets the phone call, he or she must notify each of his or her direct subordinates, one at a time. • The process continues this way until everyone has been notified. Note that each person in this process can only call direct subordinates on the phone. We can picture this process as being divided into rounds. In one round, each person who has already heard the news can call one of his or her direct subordinates on the phone. The number of rounds it takes for everyone to be notified depends on the sequence in which each person calls their direct subordinates. Figure 1: A hierarchy with four people. The fastest broadcast scheme is for A to call B in the first round. In the second round, A calls D and B calls C. If A were to call D first, then C could not learn the news until the third round. The questions are on the next page. CS 577 Assignment 8 – Dynamic Programming 2 Give an efficient algorithm that determines the minimum number of rounds needed for everyone to be notified, and outputs a sequence of phone calls that achieves this minimum number of rounds by answering the following: (a) Give a recursive algorithm. (The algorithm does not need to be efficient) Solution: (b) Give an efficient dynamic programming algorithm. Solution: (c) Prove that the algorithm in part (b) is correct. Solution: Page 2 of 6 CS 577 Assignment 8 – Dynamic Programming 2 2. Consider the following problem: you are provided with a two dimensional matrix M (dimensions, say, m × n). Each entry of the matrix is either a 1 or a 0. You are tasked with finding the total number of square sub-matrices of M with all 1s. Give an O(mn) algorithm to arrive at this total count by answering the following: (a) Give a recursive algorithm. (The algorithm does not need to be efficient) Solution: (b) Give an efficient dynamic programming algorithm. Solution: (c) Prove that the algorithm in part (b) is correct. Solution: (d) Furthermore, how would you count the total number of square sub-matrices of M with all 0s? Solution: Page 3 of 6 CS 577 Assignment 8 – Dynamic Programming 2 3. Kleinberg, Jon. Algorithm Design (p. 329, q. 19). String x ′ is a repetition of x if it is a prefix of x k (k copies of x concatenated together) for some integer k. So x ′ = 10110110110 is a repetition of x = 101. We say that a string s is an interleaving of x and y if its symbols can be partitioned into two (not necessarily contiguous) subsequences x ′ and y ′ , so that x ′ is a repetition of x and y ′ is a repetition of y. For example, if x = 101 and y = 00, then s = 100010010 is an interleaving of x and y, since characters 1, 2, 5, 8, 9 form 10110a repetition of xand the remaining characters 3, 4, 6, 7 form 0000a repetition of y. Give an efficient algorithm that takes strings s, x, and y and decides if s is an interleaving of x and y by answering the following: (a) Give a recursive algorithm. (The algorithm does not need to be efficient) Solution: (b) Give an efficient dynamic programming algorithm. Solution: (c) Prove that the algorithm in part (b) is correct. Solution: Page 4 of 6 CS 577 Assignment 8 – Dynamic Programming 2 4. Kleinberg, Jon. Algorithm Design (p. 330, q. 22). To assess how well-connected two nodes in a directed graph are, one can not only look at the length of the shortest path between them, but can also count the number of shortest paths. This turns out to be a problem that can be solved efficiently, subject to some restrictions on the edge costs. Suppose we are given a directed graph G = (V, E), with costs on the edges; the costs may be positive or negative, but every cycle in the graph has strictly positive cost. We are also given two nodes v, w ∈ V . Give an efficient algorithm that computes the number of shortest v − w paths in G. (The algorithm should not list all the paths; just the number suffices.) Solution: Page 5 of 6 CS 577 Assignment 8 – Dynamic Programming 2 5. The following is an instance of the Knapsack Problem. Before implementing the algorithm, run through the algorithm by hand on this instance. To answer this question, generate the table, indicate the maximum value, and recreate the subset of items. item weight value 1 4 5 2 3 3 3 1 12 4 2 4 Capacity: 6 Solution: 6. Implement the algorithm for the Knapsack Problem in either C, C++, C#, Java, or Python. Be efficient and implement it in O(nW) time, where n is the number of items and W is the capacity. The input will start with an positive integer, giving the number of instances that follow. For each instance, there will two positive integers, representing the number of items and the capacity, followed by a list describing the items. For each item, there will be two nonnegative integers, representing the weight and value, respectively. A sample input is the following: 2 1 3 4 100 3 4 1 2 3 3 2 4 The sample input has two instances. The first instance has one item and a capacity of 3. The item has weight 4 and value 100. The second instance has three items and a capacity of 4. For each instance, your program should output the maximum possible value. The correct output to the sample input would be: 0 6
Do NOT write pseudocode when describing your dynamic programs. Rather give the Bellman Equation, describe the matrix, its axis and how to derive the desired solution from it. 1. Kleinberg, Jon. Algorithm Design (p.313 q.2). Suppose you are managing a consulting team and each week you have to choose one of two jobs for your team to undertake. The two jobs available to you each week are a low-stress job and a high-stress job. For week i, if you choose the low-stress job, you get paid `i dollars and, if you choose the high-stress job, you get paid hi dollars. The dierence with a high-stress job is that you can only schedule a high-stress job in week i if you have no job scheduled in week i − 1. Given a sequence of n weeks, determine the schedule of maximum pro t. The input is two sequences: L := h`1, `2, . . . , `ni and H := hh1, h2, . . . , hni containing the (positive) value of the low and high jobs for each week. For Week 1, assume that you are able to schedule a high-stress job. (a) Show that the following algorithm does not correctly solve this problem. Algorithm: JobSequence Input : The low (L) and high (H) stress jobs. Output: The jobs to schedule for the n weeks for Each week i do if hi+1 > `i + `i+1 then Output “Week i: no job” Output “Week i+1: high-stress job” Continue with week i+2 else Output “Week i: low-stress job” Continue with week i+1 end end CS 577 Assignment 7 Dynamic Programming (b) Give an e cient algorithm that takes in the sequences L and H and outputs the greatest possible pro t. (c) Prove that your algorithm in part (c) is correct. Page 2 of 8 CS 577 Assignment 7 Dynamic Programming 2. Kleinberg, Jon. Algorithm Design (p.315 q.4). Suppose you’re running a small consulting company. You have clients in New York and clients in San Francisco. Each month you can be physically located in either New York or San Francisco, and the overall operating costs depend on the demands of your clients in a given month. Given a sequence of n months, determine the work schedule that minimizes the operating costs, knowing that moving between locations from month i to month i + 1 incurs a xed moving cost of M. The input consists of two sequences N and S consisting of the operating costs when based in New York and San Francisco, respectively. For month 1, you can start in either city without a moving cost. (a) Give an example of an instance where it is optimal to move at least 3 times. Explain where and why the optimal must move. (b) Show that the following algorithm does not correctly solve this problem. Algorithm: WorkLocSeq Input : The NY (N) and SF (S) operating costs. Output: The locations to work the n months for Each month i do if Ni < Si then Output “Month i: NY” else Output “Month i: SF” end end Page 3 of 8 CS 577 Assignment 7 Dynamic Programming (c) Give an e cient algorithm that takes in the sequences N and S and outputs the value of the optimal solution. (d) Prove that your algorithm in part (c) is correct. Page 4 of 8 CS 577 Assignment 7 Dynamic Programming 3. Kleinberg, Jon. Algorithm Design (p.333, q.26). Consider the following inventory problem. You are running a company that sells trucks and predictions tell you the quantity of sales to expect over the next n months. Let di denote the number of sales you expect in month i. We’ll assume that all sales happen at the beginning of the month, and trucks that are not sold are stored until the beginning of the next month. You can store at most s trucks, and it costs c to store a single truck for a month. You receive shipments of trucks by placing orders for them, and there is a xed ordering fee k each time you place an order (regardless of the number of trucks you order). You start out with no trucks. The problem is to design an algorithm that decides how to place orders so that you satisfy all the demands {di}, and minimize the costs. In summary: • There are two parts to the cost: (1) storage cost of c for every truck on hand; and (2) ordering fees of k for every order placed. • In each month, you need enough trucks to satisfy the demand di , but the number left over after satisfying the demand for the month should not exceed the inventory limit s. (a) Give a recursive algorithm that takes in s, c, k, and the sequence {di}, and outputs the minimum cost. (The algorithm does not need to be e cient.) (b) Give an algorithm in time that is polynomial in n and s for the same problem. Page 5 of 8 CS 577 Assignment 7 Dynamic Programming (c) Prove that your algorithm in part (b) is correct. Page 6 of 8 CS 577 Assignment 7 Dynamic Programming 4. Alice and Bob are playing another coin game. This time, there are three stacks of n coins: A, B, C. Starting with Alice, each player takes turns taking a coin from the top of a stack they may choose any nonempty stack, but they must only take the top coin in that stack. The coins have dierent values. From bottom to top, the coins in stack A have values a1, . . . , an. Similarly, the coins in stack B have values b1, . . . , bn, and the coins in stack C have values c1, . . . , cn. Both players try to play optimally in order to maximize the total value of their coins. (a) Give an algorithm that takes the sequences a1, . . . , an, b1, . . . , bn, c1, . . . , cn, and outputs the maximum total value of coins that Alice can take. The runtime should be polynomial in n. (b) Prove the correctness of your algorithm in part (a). Page 7 of 8 CS 577 Assignment 7 Dynamic Programming 5. Implement the optimal algorithm for Weighted Interval Scheduling (for a de nition of the problem, see the slides on Canvas) in either C, C++, C#, Java, Python, or Rust. Be e cient and implement it in O(n 2 ) time, where n is the number of jobs. We saw this problem previously in HW3 Q2a, where we saw that there was no optimal greedy heuristic. The input will start with an positive integer, giving the number of instances that follow. For each instance, there will be a positive integer, giving the number of jobs. For each job, there will be a trio of positive integers i, j and k, where i < j, and i is the start time, j is the end time, and k is the weight. A sample input is the following: 2 1 1 4 5 3 1 2 1 3 4 2 2 6 4 The sample input has two instances. The rst instance has one job to schedule with a start time of 1, an end time of 4, and a weight of 5. The second instance has 3 jobs. The objective of the problem is to determine a schedule of non-overlapping intervals with maximum weight and to return this maximum weight. For each instance, your program should output the total weight of the intervals scheduled on a separate line. Each output line should be terminated by exactly one newline. The correct output to the sample input would be: 5 5 or, written with more explicit whitespace, “5 5 ” Notes: • Endpoints are exclusive, so it is okay to include a job ending at time t and a job starting at time t in the same schedule. • In the third set of tests, some outputs will cause over ow on 32-bit signed integers.
1. Kleinberg, Jon. Algorithm Design (p. 248, q. 5) Hidden surface removal is a problem in computer graphics where you identify objects that are completely hidden behind other objects, so that your renderer can skip over them. This is a common graphical optimization. In a clean geometric version of the problem, you are given n non-vertical, infinitely long lines in a plane labeled L1 . . . Ln. You may assume that no three lines ever meet at the same point. (See the figure for an example.) We call Li “uppermost” at a given x coordinate x0 if its y coordinate at x0 is greater than that of all other lines. We call Li “visible” if it is uppermost for at least one x coordinate. x y (a) Give an algorithm that takes n lines as input and in O(n log n) time returns all the ones that are visible. Solution: CS 577 Assignment 6 – Divide and Conquer 2 (b) Write the recurrence relation for your algorithm. Solution: (c) Prove the correctness of your algorithm. Solution: Page 2 of 7 CS 577 Assignment 6 – Divide and Conquer 2 2. In class, we considered a divide and conquer algorithm for finding the closest pair of points in a plane. Recall that this algorithm runs in O(n log n) time. Let’s consider two variations on this problem: (a) First consider the problem of searching for the closest pair of points in 3-dimensional space. Show how you could extend the single plane closest pairs algorithm to find closest pairs in 3D space. Your solution should still achieve O(n log n) run time. Solution: (b) Now consider the problem of searching for the closest pair of points on the surface of a sphere (distances measured by the shortest path across the surface). Explain how your algorithm from part a can be used to find the closest pair of points on the sphere as well. Solution: (c) Finally, consider the problem of searching for the closest pair of points on the surface of a torus (the shape of a donut). A torus can be thought of taking a plane and “wrap” at the edges, so a point with y coordinate MAX is the same as the point with the same x coordinate and y coordinate MIN. Similarly, the left and right edges of the plane wrap around. Show how you could extend the single plane closest pairs algorithm to find closest pairs in this space. Solution: Page 3 of 7 CS 577 Assignment 6 – Divide and Conquer 2 3. Erickson, Jeff. Algorithms (p. 58, q. 25 d and e) Prove that the following algorithm computes gcd(x, y) the greatest common divisor of x and y, and show its worst-case running time. BINARYGCD(x,y): if x = y: return x else if x and y are both even: return 2*BINARYGCD(x/2,y/2) else if x is even: return BINARYGCD(x/2,y) else if y is even: return BINARYGCD(x,y/2) else if x > y: return BINARYGCD( (x-y)/2,y ) else return BINARYGCD( x, (y-x)/2 ) Solution: 4. Here we explore the structure of some different recursion trees than the previous homework. (a) Asymptotically solve the following recurrence for A(n) for n ≥ 1. A(n) = A(n/6) + 1 with base case A(1) = 1 Solution: Page 4 of 7 CS 577 Assignment 6 – Divide and Conquer 2 (b) Asymptotically solve the following recurrence for B(n) for n ≥ 1. B(n) = B(n/6) + n with base case B(1) = 1 Solution: (c) Asymptotically solve the following recurrence for C(n) for n ≥ 0. C(n) = C(n/6) + C(3n/5) + n with base case C(0) = 0 Solution: (d) Let d > 3 be some arbitrary constant. Then solve the following recurrence for D(x) where x ≥ 0. D(x) = Dx d + D (d−2)x d + x with base case D(0) = 0 Solution: Page 5 of CS 577 Assignment 6 – Divide and Conquer 2 5. Implement a solution in either C, C++, C#, Java, Python, or Rust to the following problem. Suppose you are given two sets of n points, one set {p1, p2, . . . , pn} on the line y = 0 and the other set {q1, q2, . . . , qn} on the line y = 1. Create a set of n line segments by connecting each point pi to the corresponding point qi . Your goal is to develop an algorithm to determine how many pairs of these line segments intersect. Your algorithm should take the 2n points as input, and return the number of intersections. Using divide-and-conquer, you should be able to develop an algorithm that runs in O(n log n) time. Hint: What does this problem have in common with the problem of counting inversions in a list? Input should be read in from stdin. The first line will be the number of instances. For each instance, the first line will contain the number of pairs of points (n). The next n lines each contain the location x of a point qi on the top line. Followed by the final n lines of the instance each containing the location x of the corresponding point pi on the bottom line. For the example shown in Fig 1, the input is properly formatted in the first test case below. Figure 1: An example for the line intersection problem where the answer is 4 Constraints: • 1 ≤ n ≤ 106 • For each point, its location x is a positive integer such that 1 ≤ x ≤ 106 • No two points are placed at the same location on the top line, and no two points are placed at the same location on the bottom line. • Note that in CC++, the results of some of the test cases may not fit in a 32-bit integer. If you are using CC++, make sure you use a ‘long long’ to store your final answer. Page 6 of 7 CS 577 Assignment 6 – Divide and Conquer 2 Sample Test Cases: input: 2 4 1 10 8 6 6 2 5 1 5 9 21 1 5 18 2 4 6 10 1 expected output: 4 7
1. Erickson, Jeff. Algorithms (p.49, q. 6). Use recursion trees to solve each of the following recurrences. (a) C(n) = 2C(n/4) + n 2 ; C(1) = 1. (b) E(n) = 3E(n/3) + n; E(1) = 1. CS 577 Assignment 5 – Divide and Conquer 2. Kleinberg, Jon. Algorithm Design (p. 246, q. 1). You are interested in analyzing some hard-to-obtain data from two separate databases. Each database contains n numerical values—so there are 2n values total—and you may assume that no two values are the same. You’d like to determine the median of this set of 2n values, which we will define here to be the nth smallest value. However, the only way you can access these values is through queries to the databases. In a single query, you can specify a value k to one of the two databases, and the chosen database will return the kth smallest value that it contains. Since queries are expensive, you would like to compute the median using as few queries as possible. (a) Give an algorithm that finds the median value using at most O(log n) queries. (b) Give a recurrence for the runtime of your algorithm in part (a), and give an asymptotic solution to this recurrence. Page 2 of 6 CS 577 Assignment 5 – Divide and Conquer (c) Prove correctness of your algorithm in part (a). 3. Kleinberg, Jon. Algorithm Design (p. 246, q. 2). Recall the problem of finding the number of inversions. As in the text, we are given a sequence of n numbers a1, …, an, which we assume are all distinct, and we define an inversion to be a pair i < j such that ai > aj . We motivated the problem of counting inversions as a good measure of how different two orderings are. However, this measure is very sensitive. Let’s call a pair a significant inversion if i < j and ai > 2aj . (a) Give an O(n log n) algorithm to count the number of significant inversions between two orderings. Page 3 of 6 CS 577 Assignment 5 – Divide and Conquer (b) Give a recurrence for the runtime of your algorithm in part (a), and give an asymptotic solution to this recurrence. (c) Prove correctness of your algorithm in part (a). Page 4 of 6 CS 577 Assignment 5 – Divide and Conquer 4. Kleinberg, Jon. Algorithm Design (p. 246, q. 3). You’re consulting for a bank that’s concerned about fraud detection. They have a collection of n bank cards that they’ve confiscated, suspecting them of being used in fraud. It’s difficult to read the account number off a bank card directly, but the bank has an “equivalence tester” that takes two bank cards and determines whether they correspond to the same account. Their question is the following: among the collection of n cards, is there a set of more than n 2 of them that all correspond to the same account? Assume that the only feasible operations you can do with the cards are to pick two of them and plug them in to the equivalence tester. (a) Give an algorithm to decide the answer to their question with only O(n log n) invocations of the equivalence tester. (b) Give a recurrence for the runtime of your algorithm in part (a), and give an asymptotic solution to this recurrence. Page 5 of 6 CS 577 Assignment 5 – Divide and Conquer (c) Prove correctness of your algorithm in part (a). 5. Implement the optimal algorithm for inversion counting in either C, C++, C#, Java, Python, or Rust. Be efficient and implement it in O(n log n) time, where n is the number of elements in the ranking. The input will start with an positive integer, giving the number of instances that follow. For each instance, there will be a positive integer, giving the number of elements in the ranking. A sample input is the following: 2 5 5 4 3 2 1 4 1 5 9 8 The sample input has two instances. The first instance has 5 elements and the second has 4. For each instance, your program should output the number of inversions on a separate line. Each output line should be terminated by a newline. The correct output to the sample input would be: 10
1. Kleinberg, Jon. Algorithm Design (p. 189, q. 3). You are consulting for a trucking company that does a large amount of business shipping packages between New York and Boston. The volume is high enough that they have to send a number of trucks each day between the two locations. Trucks have a fixed limit W on the maximum amount of weight they are allowed to carry. Boxes arrive at the New York station one by one, and each package i has a weight wi . The trucking station is quite small, so at most one truck can be at the station at any time. Company policy requires that boxes are shipped in the order they arrive; otherwise, a customer might get upset upon seeing a box that arrived after his make it to Boston faster. At the moment, the company is using a simple greedy algorithm for packing: they pack boxes in the order they arrive, and whenever the next box does not fit, they send the truck on its way. Prove that, for a given set of boxes with specified weights, the greedy algorithm currently in use actually minimizes the number of trucks that are needed. Hint: Use the stay ahead method. Solution: CS 577 Assignment 4 – More Greedy 2. Kleinberg, Jon. Algorithm Design (p. 192, q. 8). Suppose you are given a connected graph G with edge costs that are all distinct. Prove that G has a unique minimum spanning tree. Solution: Page 2 of 5 CS 577 Assignment 4 – More Greedy 3. Kleinberg, Jon. Algorithm Design (p. 193, q. 10). Let G = (V, E) be an (undirected) graph with costs ce ≥ 0 on the edges e ∈ E. Assume you are given a minimum-cost spanning tree T in G. Now assume that a new edge is added to G, connecting two nodes v, w ∈ V with cost c. (a) Give an efficient (O(|E|)) algorithm to test if T remains the minimum-cost spanning tree with the new edge added to G (but not to the tree T). Please note any assumptions you make about what data structure is used to represent the tree T and the graph G, and prove that its runtime is O(|E|). Solution: (b) Suppose T is no longer the minimum-cost spanning tree. Give a linear-time algorithm (time O(|E|)) to update the tree T to the new minimum-cost spanning tree. Prove that its runtime is O(|E|). Solution: Page 3 of 5 CS 577 Assignment 4 – More Greedy 4. In class, we saw that an optimal greedy strategy for the paging problem was to reject the page the furthest in the future (ff). The paging problem is a classic online problem, meaning that algorithms do not have access to future requests. Consider the following online eviction strategies for the paging problem, and provide counter-examples that show that they are not optimal offline strategies.1 (a) fwf is a strategy that, on a page fault, if the cache is full, it evicts all the pages. Solution: (b) lru is a strategy that, if the cache is full, evicts the least recently used page when there is a page fault. Solution: 1An interesting note is that both of these strategies are k-competitive, meaning that they are equivalent under the standard theoretical measure of online algorithms. However, fwf really makes no sense in practice, whereas lru is used in practice. Page 4 of 5 CS 577 Assignment 4 – More Greedy 5. Coding problem For this question you will implement Furthest in the future paging in either C, C++, C#, Java, or Python. The input will start with an positive integer, giving the number of instances that follow. For each instance, the first line will be a positive integer, giving the number of pages in the cache. The second line of the instance will be a positive integer giving the number of page requests. The third and final line of each instance will be space delimited positive integers which will be the request sequence. A sample input is the following: 3 2 7 1 2 3 2 3 1 2 4 12 12 3 33 14 12 20 12 3 14 33 12 20 3 20 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 The sample input has three instances. The first has a cache which holds 2 pages. It then has a request sequence of 7 pages. The second has a cache which holds 4 pages and a request sequence of 12 pages. The third has a cache which holds 3 pages and a request sequence of 15 pages. For each instance, your program should output the number of page faults achieved by furthest in the future paging assuming the cache is initially empty at the start of processing the page request sequence. One output should be given per line. The correct output for the sample input is 4 6 12
1. In one or two sentences, describe what a greedy algorithm is. Your definition should be informal, something you could share with a non computer scientist. 2. There are many different problems all described as “scheduling” problems. In the following questions, pay attention to the details of the problem setup, as they will change each time! (a) Let each job have a start time, an end time, and a value. We want to schedule as much value of non-conflicting jobs as possible. Use a counterexample to show that Earliest Finish First (the greedy algorithm we used for jobs with all equal value) does NOT work in this case. (b) Kleinberg, Jon. Algorithm Design (p. 191, q. 7) Now let each job consist of two durations. A job i must be preprocessed for pi time on a supercomputer, and then finished for fi time on a standard PC. There are enough PCs available to run all jobs at the same time, but there is only one supercomputer (which can only run a single job at a time). The completion time of a schedule is defined as the earliest time when all jobs are done running on both the supercomputer and the PCs. Give a polynomial time algorithm that finds a schedule with the earliest completion time possible. CS 577 Assignment 3: Greedy Algorithms (c) Prove the correctness and efficiency of your algorithm from part (c). Page 2 of 6 CS 577 Assignment 3: Greedy Algorithms 3. Kleinberg, Jon. Algorithm Design (p. 190, q. 5) (a) Consider a long straight road with houses scattered along it. We want to place cell phone towers along the road so that every house is within four miles of at least one tower. Give an efficient algorithm that achieves this goal using the minimum possible number of towers. (b) Prove the correctness of your algorithm. Page 3 of 6 CS 577 Assignment 3: Greedy Algorithms 4. Kleinberg, Jon. Algorithm Design (p. 197, q. 18) Your friends are planning to drive north from Madison to the town of Superior, Wisconsin over winter break. They have drawn a directed graph with nodes representing potential stops and edges representing the roads between them. They have also found a weather forecasting site that can accurately predict how long it will take to traverse one of the edges on their graph, given the starting time t. This is important because some of the roads on their graph are affected strongly by the seasons and by extreme weather. It’s guaranteed that it never takes negative time to traverse an edge, and that you can never arrive earlier by starting later. (a) Design an algorithm your friends can use to plot the quickest route. You may assume that they start at time t = 0, and that the predictions made by the weather forecasting site are accurate. Page 4 of 6 CS 577 Assignment 3: Greedy Algorithms (b) Demonstrate how your algorithm works using a small example with 6 nodes. Your demonstration should include any data structures you maintain during the execution of your algorithm and any queries you make to the weather forecasting site. For example, if your algorithm maintains a “current path” that grows from (M)adison to (S)uperior, you might show something like the following table: Path Total time M 0 M,A 2 M,A,E 5 M,A,E,F 6 M,A,E 5 M,A,E,H 10 M,A,E,H,S 13 Page 5 of 6 CS 577 Assignment 3: Greedy Algorithms Coding Question 5. Implement the optimal algorithm for interval scheduling (for a definition of the problem, see the Greedy slides on Canvas) in either C, C++, C#, Java, or Python. Be efficient and implement it in O(n log n) time, where n is the number of jobs. The input will start with an positive integer, giving the number of instances that follow. For each instance, there will be a positive integer, giving the number of jobs. For each job, there will be a pair of positive integers i and j, where i < j, and i is the start time, and j is the end time. A sample input is the following: 2 1 1 4 3 1 2 3 4 2 6 The sample input has two instances. The first instance has one job to schedule with a start time of 1 and an end time of 4. The second instance has 3 jobs. For each instance, your program should output the number of intervals scheduled on a separate line. Each output line should be terminated by a newline. The correct output to the sample input would be: 1 2
1. Kleinberg, Jon. Algorithm Design (p. 67, q. 3, 4). Take the following list of functions and arrange them in ascending order of growth rate. That is, if function g(n) immediately follows function f(n) in your list, then it should be the case that f(n) is O(g(n)). (a) f1(n) = n 2.5 f2(n) = √ 2n f3(n) = n + 10 f4(n) = 10n f5(n) = 100n f6(n) = n 2 log n (b) g1(n) = 2log n g2(n) = 2n g3(n) = n(log n) g4(n) = n 4/3 g5(n) = n log n g6(n) = 2(2n) g7(n) = 2(n 2 ) CS 577 Assignment 2 – Asymptotic Analysis & Graphs 2. Kleinberg, Jon. Algorithm Design (p. 68, q. 5). Assume you have a positive, non-decreasing function f and a positive, increasing function g such that g(n) ≥ 2 and f(n) is O(g(n)). For each of the following statements, decide whether you think it is true or false and give a proof or counterexample. (a) log2 f(n) is O(log2 g(n)) (b) 2 f(n) is O(2g(n) ) (c) f(n) 2 is O(g(n) 2 ) Page 2 of 7 CS 577 Assignment 2 – Asymptotic Analysis & Graphs 3. Kleinberg, Jon. Algorithm Design (p. 68, q. 6). You’re given an array A consisting of n integers. You’d like to output a two-dimensional n-by-n array B in which B[i, j] (for i < j) contains the sum of array entries A[i] through A[j] — that is, the sum A[i] + A[i + 1] + … + A[j]. (Whenever i ≥ j, it doesn’t matter what is output for B[i, j].) Here’s a simple algorithm to solve this problem. f o r i = 1 to n f o r j = i + 1 to n add up a r ra y e n t r i e s A[ i ] through A[ j ] s t o r e the r e s u l t i n B[ i , j ] e n d fo r e n d fo r (a) For some function f that you should choose, give a bound of the form O(f(n)) on the running time of this algorithm on an input of size n (i.e., a bound on the number of operations performed by the algorithm). (b) For this same function f, show that the running time of the algorithm on an input of size n is also Ω(f(n)). (This shows an asympto tically tight bound of Θ(f(n)) on the running time.) (c) Although the algorithm provided is the most natural way to solve the problem, it contains some highly unnecessary sources of inefficiency. Give a different algorithm to solve this problem, with an asymptotically better running time. In other words, you should design an algorithm with running time O(g(n)), where limn→∞ g(n) f(n) = 0. Page 3 of 7 CS 577 Assignment 2 – Asymptotic Analysis & Graphs Graphs 4. Given the following graph, list a possible order of traversal of nodes by breadth-first search and by depth-first search. Consider node 1 to be the starting node. 5 4 3 2 1 9 8 7 6 5. Kleinberg, Jon. Algorithm Design (p. 108, q. 5). A binary tree is a rooted tree in which each node has at most two children. Show by induction that in any binary tree the number of nodes with two children is exactly one less than the number of leaves. Page 4 of 7 CS 577 Assignment 2 – Asymptotic Analysis & Graphs 6. Kleinberg, Jon. Algorithm Design (p. 108, q. 7). Some friends of yours work on wireless networks, and they’re currently studying the properties of a network of n mobile devices. As the devices move around, they define a graph at any point in time as follows: There is a node representing each of the n devices, and there is an edge between device i and device j if the physical locations of i and j are no more than 500 meters apart. (If so, we say that i and j are “in range” of each other.) They’d like it to be the case that the network of devices is connected at all times, and so they’ve constrained the motion of the devices to satisfy the following property: at all times, each device i is within 500 meters of at least n 2 of the other devices. (We’ll assume n is an even number.) What they’d like to know is: Does this property by itself guarantee that the network will remain connected? Here’s a concrete way to formulate the question as a claim about graphs. Claim: Let G be a graph on n nodes, where n is an even number. If every node of G has degree at least n 2 , then G is connected. Decide whether you think the claim is true or false, and give a proof of either the claim or its negation. Page 5 of 7 CS 577 Assignment 2 – Asymptotic Analysis & Graphs Coding Question 7. Implement depth-first search in either C, C++, C#, Java, or Python. Given an undirected graph with n nodes and m edges, your code should run in O(n + m) time. Remember to submit a makefile along with your code, just as with week 1’s coding question. Input: the first line contains an integer t, indicating the number of instances that follows. For each instance, the first line contains an integer n, indicating the number of nodes in the graph. Each of the following n lines contains several space-separated strings, where the first string s represents the name of a node, and the following strings represent the names of nodes that are adjacent to node s. You can assume that the nodes are listed line-by-line in lexicographic order (0-9, then A-Z, then a-z), and the adjacent nodes of a node are listed in lexicographic order. For example, consider two consecutive lines of an instance: 0, F B, C, a Note that 0 < B and C < a. Input constraints: • 1 ≤ t ≤ 1000 • 1 ≤ n ≤ 100 • Strings only contain alphanumeric characters • Strings are guaranteed to be the names of the nodes in the graph. Output: for each instance, print the names of nodes visited in depth-first traversal of the graph, with ties between nodes visiting the first node in input order. Start your traversal with the first node in input order. The names of nodes should be space-separated, and each line should be terminated by a newline. Sample: Input: 2 3 A B B A C 9 1 2 9 2 1 6 5 3 4 6 6 2 4 5 2 3 2 7 7 3 8 9 9 1 8 Output: A B C 1 2 6 4 5 3 7 9 8 The sample input has two instances. The first instance corresponds to the graph below on the left. The second instance corresponds to the graph below on the right. Page 6 of 7 CS 577 Assignment 2 – Asymptotic Analysis & Graphs A B C 5 4 3 2 1 9 8 7 6
