[pdf-embedder url="https://assignmentchef.com/wp-content/uploads/2025/04/CSE430S25_Project3-3.pdf" title="CSE430S25_Project3 (3)"] CSE340 Spring 2025 – Project 3 Due on Thursday May 2, 2025 by 11:59 pm on Gradescope Abstract The goal of this project is to give you some hands-on experience with implementing a small compiler. You will write a compiler for a simple language. You will not be generating assembly code. Instead, you will generate an intermediate representation (a data structure that represents the program). The execution of the program will be done after compilation by interpreting the generated intermediate representation using an interpreter that we provide. 1 Introduction You will write a small compiler that will read an input program and represent it as a linked list. A node of the linked list represents one instruction. An instruction node specifies: (1) the type of the instruction, (2) the operand(s) of the instruction (if any) and, for jump instructions, the next instruction to be executed (the default is to execute instructions consecutively in the list order). After the list of instructions is generated by your compiler, your compiler will execute the generated list of instructions by interpreting it. This means that the program will traverse the data structure and, at every node it visits, it will “execute” the node by changing the content of memory locations corresponding to operands and then proceeds to execute the next instruction after determining what that instruction should be. This process continues until there is no next instruction to execute. We have provided the code to execute the intermediate representation, so you don’t have to worry about writing it, but you should understand what the provided code expects from your intermediate representation. These steps are illustrated in the following figure The remainder of this document is organized into the following sections: 1. Grammar. Defines the programming language syntax by providing a grammar for it. The terminals for the grammar are not described in this section, but are provided in the provided lexer files. 1 2. Execution Semantics. Describe the semantics of statements for the assignment, input, if, while, switch, for and output statements. 3. How to generate the linked list of instructions. Explains how to generate the intermediate representation (data structure) for assignment, input, if, while output statements. It does not describe whow to generate intermediate representation for switch and for statements. You should figure that on your own. You should read this section sequentially and not skip around because it is explained in an incremental manner. 4. Requirements Lists other requirements. 5. Grading Describes the grading scheme. 2 Grammar The grammar for this project is the following: program → var section body inputs var section → id list SEMICOLON id list → ID COMMA id list | ID body → LBRACE stmt list RBRACE stmt list → stmt stmt list | stmt stmt → assign stmt | while stmt | if stmt | switch stmt | for stmt stmt → output stmt | input stmt assign stmt → ID EQUAL primary SEMICOLON assign stmt → ID EQUAL expr SEMICOLON expr → primary op primary primary → ID | NUM op → PLUS | MINUS | MULT | DIV output stmt → output ID SEMICOLON input stmt → input ID SEMICOLON while stmt → WHILE condition body if stmt → IF condition body condition → primary relop primary relop → GREATER | LESS | NOTEQUAL switch stmt → SWITCH ID LBRACE case list RBRACE switch stmt → SWITCH ID LBRACE case list default case RBRACE for stmt → FOR LPAREN assign stmt condition SEMICOLON assign stmt RPAREN body case list → case case list | case case → CASE NUM COLON body default case → DEFAULT COLON body inputs → num list num list → NUM num list → NUM num list 2 Some highlights of the grammar: 1. The if stmt does not have else. 2. The for stmt has a very general syntax similar to that of the for loop in the C language 3. The input and output keywords are lowercase, but other keywords are all uppercase. 4. condition has no parentheses. 3 Variables and Locations The var section contains a list of all variable names that can be used by the program. There is no type specified for variables. All variables are int by default. For each variable name, we associate a unique locations that will hold the value of the variable. This association between a variable name and its location is assumed to be implemented using a function location() that takes a variable name (string) as input and returns an integer value. The locations where variables will be stored is called mem which is an array of integers. Each variable in the program should have a unique entry (index) in the mem array. This association between variable names and locations can be implemented with a location table. As your parser parses the input program, it allocates locations to variables that are listed in the var section. You can assume that all variable names listed in the var section are unique. For each variable name, a new location needs to be associated with it and the mapping from the variable name to the location needs to be added to the location table. To associate a location with a variable, you can simply keep a counter that tells you how many locations have been used (associated with variable names). Initially the counter is 0. The first variable to be allocated a location will get the location whose index is 0 (mem[0]) and the counter will be incremented to become 1. The next variable to be associated a location will get the location whose index is 1 and the counter will be incremented to become 2 and so on. 4 Inputs The list of input values is called inputs and appears as the last section of the input to your compiler. This list must be read by your compiler and stored in an inputs array, which is simply a vector of integers. 5 Execution Semantics All statements in a statement list are executed sequentially according to the order in which they appear. Exception is made for some statements in the bodies of if stmt, while stmt, switch stmt, and for stmt as explained below. In what follows, I will assume that all values of variables as well as constants are stored in locations. This assumption is used by the execution procedure that we provide. This is not a restrictive assumption. For variables, you will have locations associated with them. For constants, you can reserve a location in which you store the constant (this is like having an unnamed immutable variable). 3 5.0.1 Input statements Input statements get their input from the sequence of inputs. We refer to i’th value that appears in inputs as thte i’th input. The execution of the i’th input statement in the program of the form ‘input a’ is equivalent to: mem[location("a")] = inputs[input_index] input_index = input_index + 1 where location("a") is an integer index value that is calculated at compile time as we have seen above. Note that the execution of an input statement advances an input index which keeps track (at runtime) of the next value to read. 5.1 Output statement The statement output a; prints the value of variable a at the time of the execution of the output statement. That value is stored in mem[location("a")]. 5.2 Assignment Statement To execute an assignment statement, the expression on the righthand side of the equal sign is evaluated and the result is stored in the location associated with the lefthand side of the expression. 5.3 Expression To evaluate an expression, the values in the locations associated with the two operands are obtained and the expression operator is applied to these values resulting in a value for the expression. 5.4 Boolean Condition A boolean condition takes two operands as parameters and returns a boolean value. It is used to control the execution of while, if and for statements. To evaluate a condition, the values in the locations associated with the operands are obtained and the relational operator is applied to these values resulting in a true or false value. For example, if the values of the two operands a and b are 3 and 4 respectively, a < b evaluates to true. 5.5 If statement if stmt has the standard semantics: 1. The condition is evaluated. 2. If the condition evaluates to true, the body of the if stmt is executed, then the next statement (if any) following the if stmt in the stmt list is executed. 3. If the condition evaluates to false, the statement following the if stmt in the stmt list is executed. 4 5.6 While statement while stmt has the standard semantics. 1. The condition is evaluated. 2. If the condition evaluates to true, the body of the while stmt is executed. The next statement to execute is the while stmt itself. 3. If the condition evaluates to false, the body of the while stmt is not executed. The next statement to execute is the next statement (if any) following the while stmt in the stmt list. The code block: WHILE condition { stmt list } is equivalent to: label: IF condition { stmt list goto label } Jump: In the code above, a goto statement is similar to the goto statement in the C language. Note that goto statements are not part of the grammar and cannot appear in a program (input to your compiler), but our intermediate representation includes jump which is used in the implementation of if, while, for, and switch statements (jump is discussed later in this document). 5.7 For statement The for stmt is very similar to the for statement in the C language. The semantics are defined by giving an equivalent construct. FOR ( assign stmt 1 condition ; assign stmt 2 ) { stmt list } is equivalent to: 5 assign stmt 1 WHILE condition { stmt list assign stmt 2 } For example, the following snippet of code: FOR ( a = 0; a < 10; a = a + 1; ) { output a; } is equivalent to: a = 0; WHILE a < 10 { output a; a = a + 1; } 5.8 Switch statement switch stmt has the following semantics: 1. The value of the switch variable is checked against each case number in order. 2. If the value matches the number, the body of the case is executed, then the statement following the switch stmt in the stmt list is executed. 3. If the value does not match the number, the next case number is checked. 4. If a default case is provided and the value does not match any of the case numbers, then the body of the default case is executed and then the statement following the switch stmt in the stmt list is executed. 5. If there is no default case and the value does not match any of the case numbers, then the statement following the switch stmt in the stmt list is executed. The code block: 6 SWITCH var { CASE n1 : { stmt list 1 } ... CASE nk : { stmt list k } } is equivalent to: IF var == n1 { stmt list 1 goto label } ... IF var == nk { stmt list k goto label } label: And for switch statements with default case, the code block: SWITCH var { CASE n1 : { stmt list 1 } ... CASE nk : { stmt list k } DEFAULT : { stmt list default } } is equivalent to: IF var == n1 { stmt list 1 goto label } ... IF var == nk { stmt list k goto label } stmt list default label: The provided intermediate representation does not have a test for equality. You are supposed to implement the switch statement with the provided intermediate representation. 7 Note that the switch statement in the C language has different syntax and semantics. It is also dangerous! 6 How to generate the code The intermediate code will be a data structure (a graph) that is easy to interpret and execute. I will start by describing how this graph looks for simple assignments then I will explain how to deal with while statements. Note that, in the explanation below, I start with incomplete data structures then I explain what is missing and make them more complete. You should read the whole explanation. 6.1 Handling simple assignments A simple assignment is fully determined by: the operator (if any), the id on the left-hand side, and the operand(s). A simple assignment can be represented as a node: struct AssignmentInstruction { int lhs_loc; int op1_loc; int op2_loc; ArithmeticOperatorType op; // operator } For assignment without an operator on the right-hand side, the operator is set to OPERATOR NONE and there is only one operand. To execute an assignment, you need calculate the value of the righthand-side and assign it to the left-hand-side. If there is an operator, the value of the right-hand-side is calculated by applying the operator to the values of the operands. If there is no operator, the value of the right-hand-side is the value of the single operand: for literals (NUM), the value is the value of the number; for variables, the value is the last value stored in the location associated with the variable. Initially, all variables are initialized to 0. In this representation, the locations associated with variables as well as the locations in which constants are stored are in the mem[] array mentioned above. In the statement, the index (address) of the location where the value of the variable or the value of the constant is stored is given. The actual values in mem[] can be fetched or modified (for variables) at runtime. Multiple assignments are executed one after another. So, we need to allow multiple assignment nodes to be linked together. This can be achieved as follows: struct AssignmentInstruction { int lhs_loc; int op1_loc; int op2_loc; ArithmeticOperatorType op; // operator struct AssignmentStatement* next; } 8 Remember that the data structure represents operands with their indices. So, you should make sure that you store constant values (NUM) in mem[] at compile time and use the index of the constant as the operand. You cannot use the constant value directly in the data structure. This data structure will now allow us to execute a sequence of assignment statements represented as a linked-list of assignment instructions: we start with the head of the list, then we execute every assignment in the list one after the other. Begin Note It is important to distinguish between compile-time initialization and runtime execution. For example, consider the program a, b; { a = 3; b = 5; } 1 2 3 4 The intermediate representation for this program will have have two assignment instructions: one to copy the value in the location that contains the value 3 to the location associated with a and one to copy the value in the location that contains the value 5 to the location associated with b (also, your program should read the inputs and store them in the inputs vector, but this is not the point of this example). The values 3 and 5 will not be copied to the locations of a and b at compile-time. The values 3 and 5 will be copied during execution by the interpreter that we provided. I highly recommend that you read the code of the interpreter that we provided as well as the code in demo.cc. In demo.cc, a hardcoded data structure is shown for an example input program, which can be very useful in understanding what the data structure your program will generate will look like. End Note This is simple enough, but does not help with executing other kinds of statements. We consider them one at a time. 6.2 Handling output statements The output statement is straightforward. It can be represented as struct OutputInstruction { int var_loc; } where the operand is the index of the location of the variable to be printed. Now, we ask: how can we execute a sequence of statements that are either assign or output statement (or other types of statements)? We need to put the instructions for both kinds of statements in a list. So, we introduce a new kind of node: an instruction node. The instruction node has a field that indicates which type of instruction it is. It also has fields to accommodate instructions for the remaining types of statements. It looks like this: 9 struct InstructionNode { InstructionType type; // NOOP, ASSIGN, JMP, CJMP (conditional jump), IN, OUT union { struct { int lhs_loc; int op1_loc; int op2_loc; ArithmeticOperatorType op; } assign_inst; struct { // details below } jmp_inst; struct { // details below } cjmp_inst; struct { int var_loc; } input_inst ; struct { int var_loc; } output_inst; }; struct InstructionNode* next; } This way we can go through a list of instructions and execute one after the other or, if an instruction is a jump instruction, execute the target of the jump after the instruction. To execute a particular instruction node, we check its type. Depending on its type, we can access the appropriate fields in one of the structures of the union. If the type is OUT (output), for example, we access the field var index in the output inst struct to execute the instruction. Similarly for the IN (input) instruction. if the type is ASSIGN, we access the appropriate fields in the assign inst struct to execute the instruction and so on. With this combination of various instructions types in one struct, the next field is now part of the InstructionNode to line up all instructions in a sequence one after another. This is all fine, but we do not yet know how to generate the list of instructions to execute later. The idea is to have the functions that parses non-terminals return the code that corresponds to the non-terminals, the code being a sequence of instructions. For example for a statement list, we have the following pseudocode (missing many checks): 10 struct InstructionNode* parse_stmt_list() { struct InstructionNode* inst; // instruction for one statement struct InstructionNode* instList; // instruction list for statement list inst = parse_stmt(); if (nextToken == start of a statement list) { instList = parse_stmt_list(); append instList to inst; // this is pseudocode } return inst; } And to parse body we have the following pseudocode: struct InstructionNode* parse_body() { struct InstructionNode* instl; expect LBRACE instList = parse_stmt_list(); expect RBRACE return instList; } 6.3 Handling if and while statements More complications occur with if and while statements. These statements would need to be implemented using the conditional jump (CJMP) and the jump (JMP) instructions. The conditional jump struct would have the following fields struct CJMP { ConditionalOperatorType condition_op; int op1_loc; int op2_loc; struct InstructionNode * target; } The condition op, opernd1 index and opernd2 index fields are the operator and operands of the condition of the conditional jump (CJMP) instruction. The target field is the next instruction to execute if the condition evaluate to false. If the condition evaluates to true, the next instruction to execute will be the next instruction in the sequence of instructions. To generate code for the while and if statements, we need to put a few things together. The outline given above for stmt list, needs to be modified as follows (this is missing details and shows only the main steps): 11 struct InstructionNode* parse_stmt() { ... InstructionNode * inst = new InstructionNode; if next token is IF { inst->type = CJMP; parse the condition and set inst->cjmp_inst.condition_op, inst->cjmp_inst.op1_loc and inst->cjmp_inst.op2_loc inst->next = parse_body(); // parse_body returns a pointer to a sequence of instructions create no-op node // this is a node that does not result // in any action being taken. // make sure to set the next field to nullptr append no-op node to the body of the if // this requires a loop to get to the end of // true_branch by following the next field // you know you reached the end when next is nullptr // it is very important that you always appropriately // initialize fields of any data structures // do not use uninitialized pointers set inst->cjmp_inst.target to point to no-op node ... return inst; } else ... } The following diagram shows the desired structure for the if statement: The stmt list code should be modified because the code presented above for a stmt list assumed that each statement is represented with one instruction but we have just seen that parsing an if list 12 returns a sequence of instructions. The modification is as follows: struct InstructionNode* parse_stmt_list() { struct InstructionNode* instl1; // instruction list for stmt struct InstructionNode* instl2; // instruction list for stmt list instl1 = parse_stmt(); if (nextToken == start of a statement list) { instl2 = parse_stmt_list(); append instl2 to instl1 // instl1 // | // V // . // . // . // last node in // sequence staring // with instl1 // | // V // instl2 } return instl1; } Handling while statement is similar. Here is the outline for parsing a while statement and creating the data structure for it: ... create instruction node inst if next token is WHILE { inst->type = CJMP; // handling WHILE using if and goto nodes parse the condition and set inst->cjmp_inst.condition_op, inst->cjmp_inst.opernd1 and inst->cjmp_inst.condition_opernd2 inst->next = parse_body(); // when condition is true the next instruction // is the first instruction of the body of while create jmp node of type JMP // do not forget to set next field to nullptr set jmp->jmp_inst.target to inst append jmp node to end of body of while create no-op node and attach it to the list of instruction after the jmp node set inst->cjmp_target.target to point to no-op node return inst; } ... The following diagram shows the desired structure for the while statement: 13 6.4 Handling switch and for statements You can handle the switch and for statements similarly, but you should figure that yourself. Use a combination of JMP and CJMP to support the semantics of the switch and for statements. See sections 5.8 and 5.7 for the semantics of the switch and for statements. 7 Executing the intermediate representation After the graph data structure is built, it needs to be executed. Execution starts with the first node in the list. Depending on the type of the node, the next node to execute is determined. The general form for execution is illustrated in the following pseudo-code. pc = first node while (pc != nullptr) { switch (pc->type) { case ASSIGN: // code to execute pc->assign_stmt ... pc = pc->next case CJMP: // code to evaluate condition ... // depending on the result // pc = pc->cjmp_inst.target (if condition is false) // or // pc = pc->next (if condition is true) case NOOP: pc = pc->next 14 case JMP: pc = pc->jmp_inst.target case OUT: // code to print mem[pc->output_inst.var_loc] ... pc = pc->next case IN: // code to read next input value into // mem[pc->input_inst.var_loc] and updating // counter for how many values have been read pc = pc->next } } I have provided you with the data structures that represent instruction nodes and the code to execute the graph that your code will generate and you must use it. When you submit your code, you will not submit execute.cc and execute.h, we will provide them automatically for your submission, so if you modify them, your submission will not compile and run. You should include execute.h in your code. The entry point of your code is a function declared in execute.h: struct InstructionNode* parse_Generate_Intermediate_Representation(); You need to implement this function. In the file demo.cc that we provide, we show a hardcoded example of the function parse Generate Intermediate Representation() for a given example input program. I strongly recommend that you draw the data structure that is generated by this hardcoded function to gain a better understanding. If you come to office hours for help, I expect that you will have a drawing of that data structure. The main() function is provided in execute.cc: int main() { struct InstructionNode * program; program = parse_Generate_Intermediate_Representation(); execute_program(program); return 0; } It calls the function that you will implement which is supposed to parse the program and generate the intermediate representation, then it calls the execute program function to execute the program. You should not modify any of the given code. In fact, you should not submit execute.cc and execute.h; we will provide them when you submit your code. 8 Requirements 1. Write a compiler that generates intermediate representation for the code. The interpreter (execute function) is provided. 2. Language: You can only use C++ for this assignment. 3. You can assume that there are no syntax or semantic errors in the input program. 15 9 Grading The test cases provided with the assignment, do not contain any test case for switch and for statements. However, test cases with switch and for statements will be added for grading the project. Make sure you test your code extensively with input programs that contain switch and for statements. Also, remember that the provided test cases are only provided as examples and they are not meant to be exhaustive in any way. The grade of the project will be the sum of the scores on various categories. Each category will have multiple test cases, each with equal weight. The test cases will be broken down in the following way (out of 130 points): • Assignment statements: 15 • If statements: 20 • While statements: 20 • Switch: 30 • For statement: 15 • All statements: 30 • Total: 130 16
Assessment 3 – “Annotated Bibliography and Final Essay” Assignment Part 1: Annotated Bibliography for Research Essay (5%) Instructions: 1. Choose a topic for your final assignment. You may choose any essay topics that is relevant to the themes we have studied in class. Make sure your topic is specific and clear. Example topics might be • “The idea of revenge and the legal themes in Five Deadly Venoms” • “Challenges in the languages of the law in Hong Kong” • “Legal messages for children in Mo Willem’s Don’t Let the Pigeon Drive the Bus!” Your topic must be discussed with your tutor prior to beginning your research! 2. Research and gather information: Use reliable sources such as academic journals, books and book chapters, legal cases, government websites, and other credible sources to gather information on your topic. Try to find at least 5–6 sources in total. 3. Select some sources: Choose 4 sources related to your essay topic, including at least 3 academic sources: journal articles/books/book chapters/legal cases. 4. Write annotations: Write a brief annotation (50-80 words) for each of your 4 sources. You should summarize the main argument and its relevance to your essay topic. 5. Proper citation: Properly cite all sources in your annotated bibliography using the citation style. that you will use in your final essay. Example ofentry: of Society." In dExperience ulfstan’s legal and homiletic writings as part of a broader visionof adivinely orderedsociety. He argues that Wulfstan’s legal thought wasdeeply infused withecclesias ly forgovernancebutforthemoralandspiritualdisciplineoftherealm.Thisis relevant to my argument that religious andlegalconcerns wereoftenlinkedint 6. Submit the final version via Moodle. Due: Sunday, 6 April, 11.59pm Assignment Part 2: Research Essay – 1400 words (25%) In this assignment, you will research your chosen topic, and present your argument in the form of a 1400-word essay. You may choose any topic that interests you from the topics we covered in the course. You should write your essay on the topic you developed in Part 1 of the assignment. Here are some steps to help you complete the assignment. 1. Think about your topic as you research and gather information: Use reliable sources such as academic journals, legal cases, government websites, and other credible sources to gather information on your topic. It is recommended that you cite 5 or more sources for your final essay. 2. Develop a central claim: Your thesis statement should be clear, concise and arguable. It should state the main argument you will be making in your essay. 3. Write a draft: Write a draft of your essay that includes an introduction, body paragraphs, and conclusion. In the introduction, provide background information on your topic and state your thesis statement. In the body paragraphs, support your thesis statement with evidence from your sources. In the conclusion, summarize your main arguments and restate your thesis statement. 4. Revise and edit: Revise and edit your draft for clarity, coherence, and overall organization. Ensure that your arguments are well-supported and logically presented. 5. Proper citation: Properly cite all sources in your essay using the citation style that you have chosen (e.g. MLA, APA, Chicago, etc.). 6. Submit the final version: Submit the final version of your essay via Moodle. Due: Sunday, 4 May, 11.59pm
1. After assembly and wiring of the individual keys, computer keyboards are tested by an automated test station that pushes each key several times. Daily records are kept of the number of keyboards inspected and the number that fail the inspection. Data from 25 successive manufacturing days is in the file hw6q1.csv. keys
1. Efficient design of certain types of municipal waste incinerators requires that information about energy content of the waste be available. Data are given on y = energy content (kcal/kg); the three physical composition variables x1 = % plastics by weight, x2 = % paper by weight, and x3 = % garbage by weight; and the proximate analysis variable x4 = % moisture by weight for waste specimens obtained from a certain region. energy
1. In 1609 Galileo proved mathematically that the trajectory of a body falling with a horizontal velocity component is a parabola. His search for an experimental setting in which horizontal motion was not affected appreciably (to study inertia) let him to construct a certain apparatus. The data come from one of his experiments. Location
1. Consider the following stem-and-leaf plot. Provide the 5-number summary for the data. The decimal point is 1 digit(s) to the left of the | 3 | 1 3 | 56678 4 | 000112222234 4 | 5667888 5 | 144 5 | 58 6 | 2 6 | 6678 7 | 7 | 5 2. In the article below, researchers concluded that physical exercise can keep the brain sharp into old age. After reading the study, answer the following questions: (a) Do you think the conclusions derived from studying rats would be valid for humans? (b) What factors other than exercise might influence the results of the study? 2 Building Biceps CouldBoostBrainpower, Too By Ellen Hale, Gannett News Service Exercise can keep the brain sharp into old age and might help prevent Alzheimer’s disease and other mental disorders that accompany aging, says a newstudy that provides some ofthe first direct evidence linking physical activity and mental ability. The study, reported in the journal Nature, is the first to show that growth factors in the brain compounds responsible for the brain’s health can be controlled by exercise. Combined with previous research that shows exercisers live longer and score higher on tests of mental function, the new findings add hard proof of the importance of physical activity in the aging process. “Here is another argument for getting active and staying active,” says Dr. Carl Cotman ofthe University of California at Irvine. Cotman’s research was on rodents, but the effects of exercise are nearly identical in humans and rats, and rats have “surprisingly similar” exercise habits, Cotman says. In his study, which promises to be controversial, rats were permitted to choose how much they wanted to exercise, and each had its own activity habits, just like humans. Some were ‘couch’ rats, Cotman says, rarely getting on the treadmill; otherswere ‘runaholics’,with oneobsessivelylogging fivemiles every night on thewheel. “Those little feet must have been paddling away like crazy,’ ’ Cotman says. The rats that exercised had much higher levels of BDNF (brain-derived neurotrophic factor), the most widely distributed growth factor in the brain and one reported to decline with the onset of Alzheimer’s. Cotman predicts there is a minimum level of exercise that provides the maximum benefit. The rat that ran five miles nightly, for example, did not raise its level of growth factor much more than those that ran a mile or two. Source : USA Today, Jan. 12, 1995. 3. Temperature transducers of a certain type are shipped in batches of 50. Asample of 60 batches was selected, and the numberofdefective transducers ineach batchwasdetermined. Thedata are givenin the fileTransducers.csv. (a) What proportion of batches in the sample have at most 5 defective transducers? (b) Draw a histogram of the data using density on the vertical scale, and comment on its features (copy and paste from Rstudio).
In this assignment, you are going to design a Real-Time Motion Detection System using the ESP32 Feather board and the Adafruit MPU-6050 Sensor Board. In addition, you will be using ThingSpeak IoT platform and IFTTT service (If-This-Then-That) and integrate with ESP32- Sensor Assembly to build this motion detection system. One application of this system is bag theft detection. Consider that you have put the system inside your bag, kept the bag in a stationary place and you are going to workout/gym. You put the system in Armed state via Google Assistant voice commands, and the ESP32 starts detecting motion using the accleromenter sensor. As soon as any motion is detected, the system sends an IFTTT notification to your phone (on the IFTTT app), thereby alerting you of possible theft. On the other hand, you might want to disarm the system using Google Assistant when you are ready to take the bag yourself or when you are at home, as you might not want to receive unnecessary notifications. Fig. 1 shows a high-level overview of this system. Fig 1. High level overview of Motion Detection System ThingSpeak (Server) Motion Detector (Client) Voice Command: • Motion Sensor ACTIVATE • Motion Sensor DEACTIVATE Check last updated Channel Value every 30s Channel Value VALUE = ACTIVATE VALUE = DEACTIVATE if ANY of these conditions meet Accel ±X > X m/s2 Accel ±Y > y m/s2 Accel ±Z > Z m/s2 Turn ON Red LED Notification Text Motion Detected Accel X, Y, Z = xxx, yyy, zzz Measure Sensor Data Acceleration x, Acceleration y, Acceleration z, System is Armed Turn on Green LED System is Disarmed IFTTT APPLET 2 Action Trigger Send Notification to IFTTT app IFTTT APPLET 1 Trigger Action Use Command phrase ACTIVATE/DEACTIVATE to Update ThingSpeak Channel2. Hardware Assembly The MPU-6050 6-DoF Accel and Gyro Sensor board consists of an accelerometer and gyro sensor (and an additional temperature sensor) from Invensense: MPU-6050. Both sensors are connected over the shared I2 C bus. The board already has pull-up resistors attached to the I2 C pins (SCL and SDA), so you do not need to attach separate resistors to communicate with ESP32. You can use the STEMMA QT cable to connect this board to your ESP32 board. This link will give you a good understanding of how to connect the sensors to your board and start getting data out of the MPU-6050. In addition to the sensor board, you will use the onboard red LED and the onboard NeoPixel as you have done in previous labs. 3. ESP32 and Sensor Initialization 3.1.Software Initialization At the most basic level, you can use the I2 C driver in MicroPython (machine.I2C) to communicate with the accelerometer from your ESP32 (you do not need to use the gyro sensor at all in this lab). However, for this lab, you are allowed to use the adafruit-circuitpythonmpu6050 library, which makes interactions with the sensor far easier. 3.1.1.1. Initializing and Calibrating the Accelerometer and Gyroscope Initializing the sensor can be done as below: (This is only an example. You are welcome to use any other library other than adafruit_6050.) Show an appropriate message after this. (Source: https://circuitpython.readthedocs.io/projects/mpu6050/en/latest/) 3.1.2. Calibrate the Accelerometer The accelerometer data needs to be calibrated before use. For instance, if your sensor board remains flat and stands still, output data for X and Y should be 0 m/s2 or 0 g and for Z should be 9.8 m/s2 or 1 g which is the default acceleration of gravity. Check datasheet for more details on calibration. Your program should display a message on the terminal after completion of the calibration. import board import busio import adafruit_mpu6050 i2c = busio.I2C(board.SCL, board.SDA) mpu = adafruit_mpu6050.MPU6050(i2c)4. Setup ThingSpeak and IFTTT 4.1. IFTTT Applets Setup IFTTT stands for “If This Than That”, and it is a free web-based service to create chains of simple conditional statements called applets. This means you can trigger an event when something happens. In this lab, you need to create two different applets. 4.1.1. Create IFTTT Account The first step is to setup an account in IFTTT. You can easily do this by signing up at www.ifttt.com using your email address (it’s free). You also need to install the IFTTT app on your phone and login, for the applets to work. 4.1.2. Applet 1 The purpose of the 1st applet is to arm and disarm (activate and deactivate) your motion detection system, as shown in Fig. 1. Creating an IFTTT applet is simple: You simply pick a trigger, or an “if this,” then pick a “then that” action. For the 1st applet, you should use ‘Google Assistant’ as the trigger and write a phrase to control your motion detection system. For example, you can use ‘Motion sensor $’ as the phrase, where $ can be either Activate or Deactivate. For the action, you should use ‘Webhooks’ to send data (in this case $) to ThingSpeak channel. 4.1.3. Applet 2 The purpose of the 2nd applet is to receive a web request from your ESP32 if any motion is detected and send a notification to your phone. In this case, you should use ‘Webhooks’ as the trigger and Notifications as the action. Whenever any motion is detected, the ESP32 should make a web request to Webhooks and pass on the accelerometer sensor values (X, Y, Z axis), which in turn should send a notification to the IFTTT app on your phone. Fig. 3 shows examples of these two applets. NOTE: You must find out how you can use Webhooks to send data to ThingSpeak (applet 1) and receive data from ESP32 (applet 2). Webhooks is used as an action in applet 1 while as a trigger Fig 3. Example of (a) IFTTT Applet 1 (b) IFTTT Applet 2. Once you build the applets, they appear under ‘My Applets’ on the IFTTT website.Fig 2. Notification received on IFTTT app on the phonein applet 2. Create the IFTTT applets accordingly. You can use the following tutorial as a guidance. Make sure to keep things simple! 4.2. ThingSpeak Setup The purpose of ThingSpeak is to act as the server, a medium of communication between ESP32 and your Google Assistant. You have used ThingSpeak previously and should already have an account. Login into the account and create a new channel “Google Assistant Data” and enable one field “sensor_state” to receive data from Webhooks you create in IFTTT applet 1. Unlike lab4 where you posted data to channel using ESP32, here you will read data from channel using ESP32 every 30 seconds (use a Hardware Timer). You need to use your specific Read API Key to read data from your channel. You can use any MicroPython package to read data from ThingSpeak server. 4.3. Google Assistant Setup Generally, android phones have Google Assistant installed, however, if your phone doesn’t have it preinstalled (e.g., in iPhone), you need to download it from your App/Play store, install it and login with your Google account. 5. Overall Application Workflow (Fig. 1) The overall flow of tasks executed by your motion detection system is described here. These steps can be only performed after you have completed Section 3 and Section 4. Before proceeding forward, ensure that ESP32 has been properly interfaced with the sensor and you are able to read the accelerometer readings in all 3 axes. It is highly recommended that you test each of the individual components of your system, viz., ESP32 and sensor assembly, IFTTT applets and ThingSpeak server separately before integrating everything together. 1. Give the voice command to Google Assistant to activate the motion sensor. The IFTTT applet 1 gets triggered and sends the value ‘ACTIVATE’ to the ThingSpeak channel. 2. ESP32 is working as a client and reads the last updated channel value from ThingSpeak server. As the last value is ‘ACTIVATE’, turn on the onboard NeoPixel to GREEN to indicate that system is in armed state. You can consider that your system has detected MOTION if any of the following conditions occur. Also turn on RED Led to indicate motion. • Acceleration in ±X direction > X m/s2 i.e., back and front • Acceleration in ±Y direction > Y m/s2 i.e., left and right • Acceleration in ±Z direction > Z m/s2 i.e., up and down. 3. Move the sensor board. The ESP32 should now trigger IFTTT applet 2 and send a notification to your phone (IFTTT app). 4. ESP32 should check ThingSpeak channel every 30 seconds. If channel value is ‘ACTIVATE’, continue detecting motion and send notifications for around 1 minute. 5. You should show that you are receiving notifications in your video.6. Give the voice command to Google Assistant to deactivate the motion sensor. The IFTTT applet 1 gets triggered and sends the value ‘DEACTIVATE’ to the ThingSpeak channel. 7. ESP32 now sees that the channel value is ‘DEACTIVATE’. Stop measuring sensor values and turn OFF the NeoPixel to indicate that system is disarmed now. Moving the sensor SHOULD NOT SEND any notification to your phone. You also have to show this in your video. NOTE: You need to move the ESP32 and sensor board by hand. You are free to choose the values for X, Y, Z m/s2 as the threshold acceleration in 3 axes to decide if there is any motion or not. You are also free to choose the Time Interval between two consecutive readings from the sensor. However, make sure to choose values such that you do not end up getting hundreds of notifications on your phone every minute. 6. Submission Make sure you follow these instructions precisely. Points will be deducted for any deviations. You need to turn in your code on Brightspace. Please create a directory named username_lab5, where username is your CAREER account login ID. This directory should contain the following files, i.e., no executables, no temporary files, no sub-directories, etc. 1. motion_detector.py: your main program for the motion detection system. 2. README.txt: Please include a brief description of your system in this text file (any assumptions, any special conditions needed for your system to work, any limitations, etc.) 3. Additional python files used by the motion_detector.py file (if any) Zip the files and name it as username_lab5.zip and upload the .zip file to Brightspace. NOTE: In this lab, you can break up your code in multiple python files if you need. For reference, the directory and file structure of your submission should look something like this. Note the spellings, spaces, etc. in the file/directory names. username_lab5.zip |—username_lab5 (directory) |—motion_detector.py |—misc1.py |—misc2.py |—README.txt 7. Video Submission Create a short video that shows you demonstrating your working solution (you can show your ThingSpeak channel and IFTTT applets before proceeding to actual demo). Please do not upload video files directly on Brightspace. Instead, upload the video to YouTube (or other such video hosting platform) and include the link to the video in your README file above.8. Grading We will use a combination of manual code inspection and your submitted video for evaluation. If your code is unusually complex or different from expected solutions, you may be asked to attend an office hour and explain your code. NOTE: Follow the lab document strictly when using different peripherals/modules/packages. Points will be deducted if you fail to follow the lab instructions. If anything is NOT mentioned explicitly, you can use package/module to write your program. REFERENCES [1] Getting started with MicroPython on the ESP32 https://docs.micropython.org/en/latest/esp32/tutorial/intro.html [2] ESP32 WROOM-32 Datasheet https://www.espressif.com/sites/default/files/documentation/esp32-wroom32_datasheet_en.pdf [3] ESP32 Technical Reference Manual https://www.espressif.com/sites/default/files/documentation/esp32_technical_reference _manual_en.pdf [4] Adafruit HUZZAH32 – ESP32 Feather Online Manual https://learn.adafruit.com/adafruit-huzzah32-esp32-feather [5] Adafruit ESP32 Feather Schematics https://cdnlearn.adafruit.com/assets/assets/000/041/630/original/feather_schem.png?1494449413 [6] MicroPython GitHub https://github.com/micropython/micropython [7] ESP32 specific functionalities in MicroPython http://docs.micropython.org/en/latest/library/esp32.html [8] Learn how to talk to I2 C devices with MicroPython: https://learn.adafruit.com/micropython-hardware-i2c-devices/i2c-master [9] ThingSpeak: https://thingspeak.com/ [10] IFTTT: https://ifttt.com/
The goal of this assignment is to familiarize you writing simple Internet of Things (IoT) applications by using your ESP32 as an IoT device communicating with the Internet. The assignment is divided into three sections. In the first section, you will connect your ESP32 board to the Internet using Wi-Fi. In the subsequent sections, you will implement client-server communication using socket APIs and the HTTP protocol. To review, network socket APIs are used to transfer messages between two software processes over a network. HTTP is an application layer protocol that defines different parameters of these messages, viz., type, format, length, authentication, error handling, etc. 1.1. ESP32 Device as Client A typical IoT system has a cloud server and multiple client devices. Data flows from the IoTdevices to the cloud-server, as shown in this image. First, you will configure the ESP32 as an HTTP client, measure the onboard temperature sensor data and hall sensor data, and send them periodically to an IoT Application Platform hosted on the Internet. Specifically, you will use the ThingSpeak IoT Platform as the server to collect sensor data transmitted by the ESP32. 1.2. ESP32 Device as Server In some scenarios/configurations, the IoT device can also be setup as a server. In the second section of the assignment, you will configure the ESP32 as a HTTP web server, measure the onboard temperature sensor data and hall sensor data, monitor the status of an LED, and send these data to the client on-demand, only when the client requests it. You will be using your local PC or phone’s web browser (e.g., Chrome, Firefox, Safari, etc.) as the client. Additionally, you will also receive input from the client (i.e., the web browser) and control a GPIO pin on the board based on this input.2. Programming Exercises 2.1. Hardware Interfacing You will use the onboard red LED, configured as a GPIO ouput. 2.2.Software Implementation – Connect to the Internet over Wi-Fi Use the network module in MicroPython to connect your ESP32 to a Wi-Fi network using the ‘SSID’ and ‘Password’ for that network. To avoid issues related to complex wireless security configurations, you can just create a Wi-Fi hotspot on your phone/laptop and connect your ESP32 to the hotspot. Refer to the example given in the MicroPython documentation for the network module Error! Reference source not found. e.g., if your mobile hotspot has an SSID: ‘Lenovo-SSID’ and Password: ‘12345678’, then use this SSID and password for connecting the ESP32 to the Internet. NOTE: You can also connect to any other Wi-Fi network which works directly with an SSID and password. However, enterprise networks such as PAL3.0 which require SSID, username, password, certificates, etc., are unfortunately not supported in MicroPython. Each time the board successfully connects to Wi-Fi, the program should print the SSID it has connected to and the interface’s IP address. Connected to Lenovo-SSID IP Address: 192.168.0.107 2.3. Software Implementation – ESP32 HTTP Client 2.3.1. Setup ThingSpeak ThingSpeak (https://thingspeak.com) is an IoT Application Platform for collecting, analyzing, and visualizing data from IoT devices. ThingSpeak allows you to publish your sensor readings to their website and display them in a plot with time stamps. It provides a RESTful API for IoT devices (don’t worry if you don’t know what that means, it’s not important for this lab). You need to perform the following steps to configure ThingSpeak as your cloud server before you can start sending data from the ESP32. Create a free account on the ThingSpeak website. You only need the free tier for this lab and do not need any of the paid upgrades. Create a new channel and enable two fields to receive data from the ESP32. o Field1: Temperature Sensor o Field2: Hall Sensor You’ll get an API key for posting data to your channel. This API key should be used for sending data to ThingSpeak from your ESP32. 2.3.2. ESP32 Program (espclient.py) Implement the following functionality in your program. Connect to the Internet and print out the local IP address (same as Section 2.2). Initialize a hardware timer with a period of 30 seconds. When the timer fires, perform the following operations: o Measure the onboard temperature sensor data and hall sensor data. o Print both the measured data onto the terminal. o Send these data to ThingSpeak cloud server using a socket API and HTTP GET request. You need to use your specific Write API Key to upload data to your channel in your ThingSpeak account. Run your program for 5 minutes. 2.3.3. Sample Result Your ThingSpeak account should show the visualization for both sensor data, as shown in Fig. 1. Since the timer fires every 30 seconds, a maximum of 10 data points (for each sensor) will be uploaded by your client over a duration of 5 minutes. Fig. 1 shows a sample screenshot from the ThingSpeak website showing only 4 data points. Run your program for 5 minutes and take a screenshot (similar to Fig. 1) from the ThingSpeak website showing ~10 data points. Figure 1. Screenshot from ThingSpeak showing Temperature and Hall Senor data 2.4. Software Implementation – ESP32 HTTP Server 2.4.1. ESP32 Program (espserver.py) Implement the following functionality in your program. You can just update the espserver.py file that has been provided to you. Connect to the Internet and print out the local IP address (same as Section 2.2). Measure the onboard temperature sensor data and hall sensor data. Measure the state of the red LED. Use the function web_page (present in the provided file) to create simple HTML text to build the webpage with the sensor data and the LED pin values. The HTML text has already been provided in the espserver.py. You can use the 3 variables defined in the file (temp, hall, red_led_state) to measure the sensor and pin values. Create a HTTP server using the socket API to listen for incoming requests from any client (browser on your local PC or phone connected to same Wi-Fi network). Use an infinite loop: Whenever your ESP server receives a client request (e.g., pressing any button on the webpage), it should use the function web_page to update the HTML text with the current sensor values and LED state, send necessary HTTP headers and finally send the updated HTML text as the response to the client. 2.4.2. Sample Result Open a web browser on your PC or phone and type in the IP Address of your ESP32 server. You should be able to access the web page with the latest sensor readings and GPIO state. Pressing any button on the webpage counts as one client request. So, every time you press any button, the temperature, hall, and LED state should update. e.g., if you press the RED ON button, the red LED connected to your board should light up, and the RED LED Current State should display ON as shown in Fig. 2. Figure 2. Webpage on pressing RED ON button 3. Video Create a short video that shows you demonstrating your working solution (explain your hardware connections briefly before demonstrating the working solution). Please do not upload video files directly on Brightspace to save space. Instead, please upload the video to YouTube (or other such video hosting platform) and include the link to the video in your README file mentioned below. 4. Submission You need to turn in your code on Brightspace. Please create a directory named username_lab4, where username is your CAREER account login ID. This directory should contain only the following files, i.e., no executables, no temporary files, no sub-directories, etc. 1. espclient.py: your program for ESP32 HTTP Client 2. screenshot.jpg (or .png or .gif): Screenshot obtained from the ThingSpeak website showing Temperature and Hall Senor data, each with ~10 entries, as shown in Fig. 1. 3. espserver.py: your program for ESP32 HTTP Web ServerZip the files and name it as username_lab4.zip and upload the .zip file to Brightspace. Note: For reference, the directory and file structure of your submission should look something like this. Note the spellings, spaces, etc. in the file/directory names. username_lab4.zip |—username_lab4 (directory) |—espclient.py |—screenshot.jpg |—espserver.py REFERENCES [1] Getting started with MicroPython on the ESP32 https://docs.micropython.org/en/latest/esp32/tutorial/intro.html [2] ESP32 PICO MINI 02 Datasheet https://www.espressif.com/sites/default/files/documentation/esp32-pico-mini-02_datasheet_en.pdf [3] ESP32 Technical Reference Manual https://www.espressif.com/sites/default/files/documentation/esp32_technical_reference_manual_en.pdf [4] Adafruit HUZZAH32 – ESP32 V2 Feather Online Manual https://learn.adafruit.com/adafruit-esp32-feather-v2 [5] Adafruit ESP32 Feather Pinouts: https://learn.adafruit.com/adafruit-esp32-feather-v2/pinouts [6] MicroPython GitHub https://github.com/micropython/micropython [7] ESP32 specific functionalities in MicroPython http://docs.micropython.org/en/latest/library/esp32.html [8] ThingSpeak: https://thingspeak.com/ [9] MicroPython socket module: https://docs.micropython.org/en/latest/library/socket.html
This assignment deals with connecting your ESP32 V2 board to the Internet over WiFi and exploring sleep modes and wake up sources in the ESP32. You will also be using the RTC module and the on-board touch sensor in this lab. The hardware and software implementation details for this assignment are described in the following sections. 2. Programming Exercise 2.1. Hardware Interfacing You will use the following hardware components: • The on-board red LED and on-board Neo Pixel o The red LED should indicate if the board is awake (ON) or in sleep mode (OFF). o The Neo Pixel should be controlled by touch-based input (see Table 1). • One external push button as a GPIO input to use as a wake-up source. • One external Male-Male jumper wire connected to a Touch-enabled pin. Insert the wire into the header on the board. This page gives information about the Touch-enabled pins: http://docs.micropython.org/en/latest/esp32/quickref.html#capacitive-touch. You can select any of the 10 capacitive-touch enabled pins on the board with the following caveat. The pins indicated on the webpage above are for the ESP32 microcontroller itself. On your board however, only 6 out of the 10 touch-enabled pins are available for use. You can figure out the 6 pins by trial and error (HINT: you will get a ‘ValueError’ if you try to assign an unavailable pin as a TouchPad input). 2.2. Software Implementation (main.py) Your program should implement the following functionality.2.2.1.Connect to the Internet over WiFi • The program should use the network module in MicroPython to connect your ESP32 to a WiFi network using the ‘SSID’ and ‘Password’ for that network. You can create a WiFi hotspot on your mobile/laptop and connect your ESP32 to the hotspot. Refer to the example given in the MicroPython documentation for the network module. e.g., if your mobile hotspot has an SSID: ‘Lenovo-SSID’ and Password: ‘12345678’, then use this SSID and password for connecting the ESP32 to the Internet. NOTE: You can also connect to any other WiFi network which works directly with an SSID and password. However, be aware that enterprise networks such as PAL3.0 which require SSID, username, password, certificates, etc., are unfortunately not supported in MicroPython. • Each time the board successfully connects to Wi-Fi, the program should print the SSID it has connected to and the interface’s IP address. Connected to Lenovo-SSID IP Address: 192.168.0.107 2.2.2. Display Current Date and Time using Network Time Protocol (NTP) • Get the current time from the Internet using NTP. The program should fetch the current date and time from the NTP server ‘pool.ntp.org’ and use it to set the RTC (real time clock). HINT: on the micropython-lib github, check module ntptime. Then, manually adjust the RTC to convert UTC (Coordinated Universal Time) to the current local time zone in West Lafayette. • Similar to lab 2, initialize a hardware timer and display the current date & time every 15 seconds. Do not use time.sleep(). Instead, use the RTC and Timer interrupt/callback like you did in Lab 2. Format the date and time as shown in the example below: Date: 09/29/2021 Time: 10:00:00 HRS 2.2.3. NeoPixel Control by Touch Input • Initialize the Touchpad-enabled pin connected to the jumper wire and calibrate it by observing how the touchpad pin values change when you physically touch the jumper wire. • Initialize a second hardware timer and read the touch pin values every 50 milliseconds using a Timer interrupt/callback and implement the following pattern. Use calibrated values to detect whether the wire is touched or not. o Touch Pin not touched: Neo Pixel should be OFF o Touch Pin touched: Neo Pixel should be ON and lit GREEN 2.2.4. Red LED, Deep Sleep, and Different Wake Up Sources • The red LED should be ON whenever the ESP32 is awake and OFF when it is in sleep mode.• Use a third hardware timer to put the ESP32 into deep sleep every 30 seconds for a duration of 1 minute. Print out a message on the terminal before going to sleep like: I am going to sleep for 1 minute. AWAKE duration: 30 seconds (this will be the duration of the third hardware timer) SLEEP duration: 1 minute (do not need a timer for this, check this link for details on deep sleep: https://docs.micropython.org/en/latest/esp32/quickref.html#deep-sleep-mode) • You will be using two different sources of waking up from deep sleep. Your program should check for both sources and the board should be able to wake up from either source. 2.2.4.1. Wake up Sources • Timer Wake Up: Wake up the ESP32 after the predefined sleep duration (1 minute) and print that it’s a timer wake-up. • External Wake Up Mode 0: Configure the switch as an external wake-up source. Pressing the switch within the 1-minute sleep duration should wake up the board and print out it’s an EXT0 wake-up. If one-minute passes and no touch is detected, then your board should wake up due to the Timer Wake Up above. 2.3. Overall Program Flow and Sample Output The board is powered on for the first time. It connects to the Wi-Fi network, fetches the current time from NTP server, displays them after 15s, and turns on the Neo Pixel to green whenever the touch pin wire is touched. It again displays the date and time at 30s and then goes to deep sleep. The program now checks for the push button wake-up signal. If you press the switch or if 1 minute expires, the board wakes up and starts the overall process again. Table 1 shows the LED status functionality. A sample output is also provided here for your understanding. For this sample, we assume that the program started at 10:00:00 hrs. EST. Table 1. Sleep and Wake Up Program Flow Mode Touch Pin Switch Red Led Neo Pixel Sleep Not Pressed: No Effect Not Pressed: No Effect Off Off Sleep Pressed: No Effect Pressed: Wake-Up Off Off Awake Not Pressed: Neo Pixel off Not Pressed: No Effect On Off Awake Pressed: Neo Pixel green Pressed: No Effect On Green Sample Output I (200) wifi: wifi driver task: 3ffe2c34, prio:23, stack:3584, core=0 ……… ……… ……… I (22233) network: CONNECTED I (22883) event: sta ip: 192.168.0.107, mask: 255.255.255.0, gw: 192.168.0.1 I (22883) network: GOT_IP Connected to Lenovo-SSID IP Address: 192.168.0.107 Wi-Fi connection messages posted by ESPDate: 09/11/2019 Time: 10:00:15 HRS Date: 09/11/2019 Time: 10:00:30 HRS I am going to sleep for 1 minute. ets Jun 8 2016 00:22:57 rst:0x5 (DEEPSLEEP_RESET),boot:0x13 (SPI_FAST_FLASH_BOOT) configsip: 0, SPIWP:0xee…………… ………………… ………………… I (0) cpu_start: Starting scheduler on APP CPU. Woke up due to EXT0 wakeup. I (200) wifi: wifi driver task: 3ffe2c34, prio:23, stack:3584, core=0 ///continues 3. Submission Make sure you follow these instructions precisely. You need to turn in your code on Brightspace. Please create a directory named username_lab3, where username is your CAREER account login ID. This directory should contain only the following files, i.e., no executables, no temporary files, etc. 1. main.py: your program (2.2) 2. A README file named username_lab3_README.txt that contains a description of your hardware connections (which pins you used, exactly what they were connected to, etc.). Zip the directory and name it as username_lab3.zip and upload the .zip file to Brightspace. BONUS CREDIT: You will receive 20% bonus credit on the lab for creating a short video that shows you demonstrating your working solution (explain your hardware connections briefly before demonstrating the working solution). Please do not upload video files directly on Brightspace. Instead, upload the video to YouTube (or other such video hosting platform) and include the link to the video in your README file above. 4. Grading We will use a combination of automatic grading scripts and manual code inspection for evaluation. If your code is unusually complex or substantially different from expected solutions, you may be asked to attend an office hour and explain your code. Default Messages by ESP on Wakeup and ResetREFERENCES [1] Getting started with MicroPython on the ESP32 https://docs.micropython.org/en/latest/esp32/tutorial/intro.html [2] ESP32 PICO MINI 02 Datasheet https://www.espressif.com/sites/default/files/documentation/esp32-pico-mini02_datasheet_en.pdf [3] ESP32 Technical Reference Manual https://www.espressif.com/sites/default/files/documentation/esp32_technical_reference _manual_en.pdf [4] Adafruit HUZZAH32 – ESP32 V2 Feather Online Manual https://learn.adafruit.com/adafruit-esp32-feather-v2 [5] Adafruit ESP32 Feather Pinouts: https://learn.adafruit.com/adafruit-esp32-featherv2/pinouts [6] MicroPython GitHub https://github.com/micropython/micropython [7] REPL http://docs.micropython.org/en/latest/esp8266/tutorial/repl.html [8] Thonny IDE https://thonny.org [9] Rshell GitHub https://github.com/dhylands/rshell [10] Sleep Modes API in C https://docs.espressif.com/projects/esp-idf/en/latest/apireference/system/sleep_modes.html [11] Touch Sensor API in C https://docs.espressif.com/projects/esp-idf/en/latest/apireference/peripherals/touch_pad.html [12] ESP32 specific functionalities in MicroPython http://docs.micropython.org/en/latest/library/esp32.html
This assignment deals with 3 different peripherals, namely the PWM, ADC, and RTC on the ESP32 V2 Feather Board. In addition to these peripherals, you will also be using timers and interrupts to implement LED control using a potentiometer and switch. The hardware and software implementation details for this assignment are described in the following sections. 2. Programming Exercise 2.1. Hardware Interfacing Interface the following components to the board: • The on-board push button switch as a GPIO (digital) input (nothing to interface here!) • An external potentiometer as an analog input. • One external LED as a PWM (Pulse Width Modulation) output. 2.2. Software Implementation Your program should implement the following functionalities. • The program should start by asking the user to input the current date and time as shown in the following format. Use the user inputs to initialize the RTC (real time clock). Use the current time in the EDT time zone for entering the time. NOTE: Weekdays: Enter 0 for Monday, 1 for Tuesday, …. 6 for Sunday. >>> python ghosh37_lab2.py Year? 2022 Month? 9 Day? 27 Weekday? 2 Hour? 7 Minute? 30Second? 00 Microsecond? 000000 • Use the real-time clock (RTC) and a hardware timer to display the current date and time every 30 seconds. Display these times on 2 separate lines and ensure that both dates and times are immediately recognizable with a formatted print statement. Do not use time.sleep(). Use the RTC and a timer interrupt/callback instead. See this URL for more information on callbacks & interrupts in MicroPython. https://docs.micropython.org/en/latest/library/machine.html#machine-callbacks • Initialize another hardware timer and read the analog input (potentiometer/pot values) every 100ms using the timer interrupt/callback and ADC. IMPORTANT: Connect the potentiometer only to a pin associated with ADC1 and not ADC2. • Initialize and start a PWM signal on the external LED using a frequency of 10 Hz and a duty cycle of 512 (50%). The LED should start blinking at the defined frequency. • In the beginning, rotating the pot should have no effect on the LED. The LED should continue blinking at predefined intensity and frequency. • Detect a switch press using an interrupt/callback. Implement switch debouncing using another timer-based interrupt/callback. o Alternate switch presses should direct control towards either the frequency or the duty cycle of the LED. o The LED’s PWM signal frequency and duty cycle should be controlled by the pot readings. o When you press the switch for the first time, the pot should control the LED’s PWM frequency. Now, if you rotate the pot, your LED should blink faster or slower, as the frequency of PWM changes. No change should occur in the LED’s intensity. o When you press the switch for the second time, the pot should control the LED’s PWM duty cycle. Now, if you rotate the pot, your LED’s intensity should be higher or lower, as the duty cycle of PWM changes. No change in the LED’s blinking frequency. o The third switch press should revert the control back to the frequency, the fourth press should give control to the duty cycle and the process should continue forever. 3. Submission Make sure you follow these submission instructions precisely. You need to turn in your code on Brightspace. Upload your source code as username_lab2.py where username is your CAREER account login ID. Do not ZIP the file. In addition, upload a README file named username_lab2_README.txt that contains a description of your hardware connections (which pins you used, exactly what they were connected to, etc.). For this lab, you have to create a short video that shows you demonstrating your working solution (explain your hardware connections briefly before demonstrating the working solution). Please do not upload video files directly on Brightspace. Instead, upload the video toYouTube (or other such video hosting platform) and include the link to the video in your README file above. 4. Grading We will use manual code inspection for evaluation. If your code is unusually complex or different from expected solutions, you may be asked to attend an office hour and explain your code. REFERENCES [1] Getting started with MicroPython on the ESP32 https://docs.micropython.org/en/latest/esp32/tutorial/intro.html [2] ESP32 PICO MINI 02 Datasheet https://www.espressif.com/sites/default/files/documentation/esp32-pico-mini-02_datasheet_en.pdf [3] ESP32 Technical Reference Manual https://www.espressif.com/sites/default/files/documentation/esp32_technical_reference_manual_en.pdf [4] Adafruit HUZZAH32 – ESP32 V2 Feather Online Manual https://learn.adafruit.com/adafruit-esp32-feather-v2 [5] Adafruit ESP32 Feather Pinouts: https://learn.adafruit.com/adafruit-esp32-feather-v2/pinouts
1. Overview This assignment will familiarize you with the Python programming language and the Thonny Python IDE editor, which we will use throughout the semester. Python is an easy-to-learn but powerful programming language and is one of the fastest growing programming languages for embedded systems. In this course, we will use MicroPython to program the ESP32 board. MicroPython is a lean and efficient implementation of the Python3 programming language. Before working with MicroPython on your board, you should acquaint yourself with Python. 2. Getting started with Python and MicroPython The following sections describe various software installation procedures. 2.1. Install Thonny IDE on your own PC Thonny is a Python IDE meant for learning programming. You can find more details about this IDE and download it at https://thonny.org. Install the latest version (4.1.4). Installation instructions for Windows, Linux, and Mac OS are provided on the above webpage. By default, Thonny comes with Python 3.10 built in, so a separate installation of Python is not needed. 2.2. Install USB-Serial Driver on your host PC (Windows and Mac only) Follow the guide available at https://learn.adafruit.com/how-to-install-drivers-for-wch-usb-toserial-chips to install the drivers for the USB to serial converter chip that the board uses to communicate with your host PC. There are drivers for Windows and Mac computers available. If you’re on Linux, the drivers are built in. 2.3. Flashing MicroPython on ESP32 (using Thonny) The latest version of Thonny (4.1.4) comes preinstalled with the package ‘esptool’, which is a Python-based, open source, platform independent, utility to communicate with the ROM bootloader in ESP32. Esptool can be used to load MicroPython on your ESP32 board.2.3.1. Acquiring MicroPython Firmware The esptool utility will help you download the latest ESP32 firmware. 2.3.2. Thonny Setup and Flashing • Plug in your ESP32 board to your computer using a USB-C cable, launch Thonny and navigate to “Run > Configure Interpreter”. • Under the “Which interpreter or device should Thonny use for running your code?” label, select “MicroPython (ESP32)”. • Select the COM port to which your ESP32 is connected under “Port” (see Figure 1). Figure 1. Set the interpreter and port • After setting the interpreter and the port, click on the link at the bottom right: “Install or Update MicroPython”. Select your device’s port again, then select ESP32 as the MicroPython family, Espressif – ESP32 / WROOM as the variant, and 1.23.0 as the version. If you selected the options correctly, the information field should show https://micropython.org/download/ESP32_GENERIC/ corresponding to the v1.23.0 (2024-06-02) .bin firmware. If you are flashing MicroPython on your ESP32 board forthe first time, then make sure that “Erase flash before installing” is checked, then click “Install”, as shown in Figure 2. Figure 2. Select the port and downloaded MicroPython firmware Thonny will now erase any existing firmware, and then flash the new MicroPython firmware on your ESP32, as you can see in Figure 3 and 4. This may take a few minutes. After the firmware has finished installing, you may close all the open dialogs. Figure 3. Flashing progress Figure 4. Thonny has completed flashing the firmware on the microcontroller. • At the bottom of the Thonny window in the tab labeled “Shell”, you should see text that resembles Figure 5. Figure 5. MicroPython REPL ready for input Your ESP32 board is now ready for programming. 3. Python warm up programming exercises You DO NOT need to use ESP32 for this part. You can use the default python interpreter. 3.1. Character Input (Upload as program1.py) Write a program that asks the user to enter name and age. Print out a message that tells the year the user will turn 100 years old.Hint: Use input command to get user input >>> python program1.py What is your name? Xavier How old are you? 25 Xavier will be 100 years old in the year 2094 3.2. Lists and Conditional Statements (Upload as program2.py) Write a program to initiate a list of 10 numbers, print the list, and ask the user for a number and return a list that contains only elements from the original list that are smaller than the number given by the user. >>> python program2.py a = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55] Enter number: 25 The new list is [1, 1, 2, 3, 5, 8, 13, 21] 3.3. Loops 3.3.1. While loop: (Upload as program3a.py) Write a program to get the Fibonacci sequence between 0 to a user input number using a while loop. >>> python program3a.py How many Fibonacci numbers would you like to generate? 10 The Fibonacci Sequence is: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 3.3.2. For loop: (Upload as program3b.py) Write a program that generates a random number (0-10) and asks the user to guess it within three chances. If user guesses correctly, print ‘You win!’, otherwise print ‘You lose!’ >>> python program3b.py Enter your guess:3 Enter your guess:2 Enter your guess:10 You win! 3.4. Dictionary (Upload as program4.py) Write a program to create a dictionary of 5 names and birthdays. Upon execution, it should ask the user to enter a name, and return the birthday of that person back to them. >>> python program4.py Welcome to the birthday dictionary. We know the birthdays of: Albert Einstein Benjamin Franklin Ada Lovelace Whose birthday do you want to look up? Benjamin Franklin Benjamin Franklin’s birthday is 01/17/1706.3.5. Class and Functions (Upload as program5.py) Write a program to create a Python class to find a pair of elements (indices of the two numbers) from a given list of numbers whose sum equals a specific target number. Use this list in your program: [10, 20, 10, 40, 50, 60, 70] Hint: You might create dictionaries of array index as keys and array item as values as you scan through the array. Use conditional statements, loops, etc. >>> python program5.py What is your target number? 60 index1=1, index2=3 4. Digital input/output using GPIOs This section explains how to get started with the Adafruit HUZZAH32 – ESP32 V2 Feather board and how to program the board using MicroPython and Thonny IDE. The goal of this experiment is to walk you through the embedded software development flow for the ESP32, where you will learn how to use microcontroller I/O, the inputs and outputs, to sense and actuate devices in the world outside the board. The assignment is subdivided into two sections. In the first section, you will learn to implement a simple LED blink program that will give you a high-level idea of how you can accomplish the remaining labs. In the second section, you will interface two LEDs (Red and Green) and 2 Push Button Switches with the board and implement a simple pattern function using them. The ESP32-PICO-MINI-02 module on the V2 Feather Board has 53 pins, many of which are GPIO (general-purpose input/output) pins. However, the feather board has only 28 pins and has its own ad-hoc pin numbering (marked e.g., A0, A1…) with many peripheral pins (like TX, RX, SCL, SDA…) indicated on the board itself. You need to explore the ESP32-PICO-MINI02 datasheet and ESP32 Feather V2 board manuals and the board’s Pinouts to figure out the mapping between physical chip pins and board logical pins. 4.1. Programming ESP32 using Thonny IDE Before proceeding further, you should have completed installing any necessary software (explained in Section 2) and flashed MicroPython on the ESP32 board. The implementation procedure explained in this section demonstrates a typical procedure to run any program on the board. 4.2. Connect the Board to PC Connect the board to your PC using the USB-C cable (just plug into the jack) and the Feather will regulate the 5V USB down to 3.3V which will power the board. You can get more information on starting MicroPython on your ESP32 board on this webpage: http://docs.micropython.org/en/latest/esp32/tutorial/intro.html#esp32-intro.4.3. Testing Thonny IDE Installation Important: Before testing the installation, your ESP32 board needs to be flashed with MicroPython firmware. Connect the board to your PC and open Thonny IDE. To test the installation, you need to tell Thonny that you want to run MicroPython Interpreter and select the board you are using. 1. Go to Tools > Options and select the Interpreter tab. Select MicroPython (ESP32). 2. Select the device serial port Figure 6. Thonny Interpreter and Port selection Thonny IDE should now be connected to your board. The board will start and run the files ‘boot.py’ and ‘main.py’ (if any) automatically and provide you a MicroPython REPL shell. A read–eval–print-loop (REPL), also termed interactive top-level or language shell, is a simple, interactive computer programming environment that takes single user inputs (i.e., single expressions), evaluates (executes) them, and returns the result to the user, shown in Figure 8. Figure 7. MicroPython startup on ESP32 in Thonny IDE 4.4. Using the REPL Once you have a prompt, you can start experimenting! Anything you type at the prompt will be executed after you press the Enter key. MicroPython will run the code on the board that you enter and print the result (if there is one). If there is an error with the text that you enter, then an error message is printed. You can find more information on REPL at http://docs.micropython.org/en/latest/esp8266/tutorial/repl.html (MicroPython execution is similar in ESP8266 and ESP32).Figure 8. Experimenting with REPL Type the command help() in the Shell and see if it responds back. If it responded back, everything is working fine. Figure 9. Testing the REPL 4.5. First Program on the ESP32 In the EDITOR of the Thonny IDE, write your first ‘Hello World’ program and save it on the board as main.py. The IDE asks for location to save the file, Select MicroPython device to save the file on the flash memory on the board, as shown in Figure 11. Pressing Ctrl+D or selecting Run > Send EOF/Soft Reboot in Thonny will perform a soft reboot of the board and as mentioned earlier, it will run main.py and you will see the output on the MicroPython shell. You can also run the program main.py from the shell by calling the following command, which will run the code inside main.py and give you output on the shell, both of which are shown in Figure 12. Similarly, any code you write for your labs, you can save them on the board and import your program module in MicroPython shell to run the code. import mainFigure 10. Saving file on ESP32 board Figure 11. Reboot and Running main.py 4.6. The internal filesystem Since ESP32 Feather has 8MB flash memory, a default filesystem will be generated upon first boot, which uses the FAT format and is stored in the flash after the MicroPython firmware. You can open any file already stored inside the board using Thonny IDE, modify it and save it back on the board. More details on working with the internal filesystem are available at this webpage: http://docs.micropython.org/en/latest/esp8266/tutorial/filesystem.html. 5. ESP32 Programming Exercises 5.1. Simple Blink Program (main.py) The example source code below blinks the Red LED on the ESP32 V2 Feather board 5 times with the interval of roughly 0.5 seconds. Use this source code and save as main.py file on your board and perform a soft reboot. Use the Feather V2 board Pinouts to figure out the pin X connected to the red LED on the board. EDITOR SHELL5.2. NeoPixel Color Changes based on Switch Presses (switchpress.py) Now that you have gone through the warm-up program above, you can finally get to the actual problem statement for Lab 1. You will use the onboard user push button and the onboard NeoPixel LED for this lab. The switch is considered to be ON when it is pushed down and OFF when it is released. Start your program by lighting up the NeoPixel to red. When the switch is ON (pressed), the NeoPixel should turn green. When the switch is OFF (released), the NeoPixel should go back to being red. In addition, you must determine the number of times the switch is pressed from the start of the program. If the switch is pressed 5 times, when it is released, the NeoPixel should turn OFF and your program should exit with a message on the MicroPython shell ‘You have successfully implemented LAB1!’ and exit to the shell. 6. Submission Make sure you follow these instructions precisely. Points will be deducted for any deviations. You need to turn in your code on Brightspace. Please create a directory named username_lab1, where username is your CAREER account login ID. Inside this directory, create two more directories, part1 and part2. • Put all the files created in section 3 (Python programming exercise) in part1. • Put all the files created in section 5 in part2. NOTE: These directories should contain only the source code files, i.e., no executables, no temporary files, etc. • Zip the parent directory (i.e., username_lab1) and name it as username_lab1.zip and upload the .zip file to Brightspace. REFERENCES [1] Getting started with MicroPython on the ESP32 https://docs.micropython.org/en/latest/esp32/tutorial/intro.html[2] ESP32 PICO MINI 02 Datasheet https://www.espressif.com/sites/default/files/documentation/esp32-pico-mini02_datasheet_en.pdf [3] ESP32 Technical Reference Manual https://www.espressif.com/sites/default/files/documentation/esp32_technical_reference_ manual_en.pdf [4] Adafruit HUZZAH32 – ESP32 V2 Feather Online Manual https://learn.adafruit.com/adafruit-esp32-feather-v2 [5] Adafruit ESP32 Feather Pinouts: https://learn.adafruit.com/adafruit-esp32-featherv2/pinouts [6] MicroPython GitHub https://github.com/micropython/micropython [7] REPL http://docs.micropython.org/en/latest/esp8266/tutorial/repl.html [8] Thonny IDE https://thonny.org
River crossing This assignment is adapted from a problem made available by Prof. Martin Henz from the Computer Science Department of the National University of Singapore. Jane wants to cross a river. The river is dotted with M × N poles to which boards can latch on. Some of the poles already have boards latched on such that the boards all point in the same direction of the river flow (from top to bottom). For M = 3 and N = 3, the configuration of the boards may look like this. Jane Board Pole River We number the poles from top to bottom 0 to 2 and from left to right 0 to 2, and associate each pole with row-column coordinates. In this example, a board is latched between poles (1,0) and (2,0), and another board is latched between poles (0,2) and (1,2). River River (1) (2) On her side of the river (the left river bank), Jane has a board. In Figure (1), she latches one end of the board on pole (1,0) and keeps the other end of the board on the river bank. She then uses the board as a bridge to reach the board that is latched between poles (1,0) and (2,0), as shown in Figure (2). 1 River River (3) (4) River River (5) (6) River (7) When Jane is on a board, she can un-latch any of the two ends of the board and turn the board 90 degrees (clockwise or counter-clockwise) such that the board latches on another pole. As shown in Figures (2) and (3), Jane un-latches the board from pole (2,0), turns the board 90 degrees counter-clockwise, and latches the board between poles (1,0) and (1,1). She then un-latches the board from pole from (1,0), turns the board 90 degrees counterclockwise, and latches the board between poles (1,1) and (2,1), as shown in Figure (4). Now, she un-latches the board from pole (2,1), turns the board 90 degrees counter-clockwise, and latches the board between poles (1,1) and (1,2), as shown in Figure (5). She then moves onto the pre-existing board that is latched between poles (0,2) and (1,2), shown in Figure (6). She un-latches the board from pole (1,2), turns it 90 degrees counter-clockwise, such that one end of the board is at pole (0,2) and the other end is on the right river bank. She is now able to reach the right river bank, as shown in Figure (7). Since turning a board is quite tiresome, she wants to cross the river in such a way that she has to turn boards by 90 degrees (clockwise or counter-clockwise) as few times as possible. In this particular configuration of poles and boards, Jane requires a minimum of 4 board turns to cross the river. While this example shows that Jane only has to move from left to right, it is possible that Jane may have to move from right to left in order to minimize the number of board turns required to cross the river. 2 Solution representation We can describe Jane’s solution (to cross the river with the fewest board turns) as a sequence of board positions. We assume that the left bank is at column −1 and the right bank is at column N. Moreover, we assume the left bank has M imaginary poles and the right bank also has M imaginary poles. We represent a board position by the two poles the board is latched to. Moreover, a vertical board is represented by (r, c)(r + 1, c), with 0 ≤ r ≤ M − 1, and 0 ≤ c ≤ N − 1. Note that the first row-coordinate is always 1 less than the second row-coordinate. Jane could be moving from bottom to top or top to bottom on the board. A horizontal board is represented by (r, c)(r, c+1), with 0 ≤ r ≤ M −1, −1 ≤ c ≤ N −1. Note that the first column-coordinate is always 1 less than the second column-coordinate. Jane could be moving from left to right or right to left on the board. Given this representation, the following shows the solution presented in Figures (1)–(7): (1,-1)(1,0) (1,0)(2,0) (1,0)(1,1) (1,1)(2,1) (1,1)(1,2) (0,2)(1,2) (0,2)(0,3) Each of the lines tells us a board position, printed with the format “(%d,%d)(%d,%d) ” The first board position must be a horizontal board that starts at column −1 (the left bank). No other board positions in a solution (with the fewest turns) should start at column −1. The board positions in two adjacent lines must have one and only one common pair of coordinates. The last board position must be a horizontal board that ends at column N (the right bank). No other board positions in a solution (with the fewest turns) should end at column N. It is possible that Jane can visit a board position many times without making any turns. For example, in Figure (6), Jane could move between board positions (1,1)(1,2) and (0,2)(1,2) many times without making any turns. However, for this assignment, we require that every board position appears at most once in a solution. Of course, there are other ways Jane can reach the right bank with the same number of 4 board turns. For example, we list three other possible solutions as follows: (2,-1)(2,0) (1,0)(2,0) (1,0)(1,1) (1,1)(2,1) (1,1)(1,2) 3 (0,2)(1,2) (0,2)(0,3) (1,-1)(1,0) (1,0)(2,0) (1,0)(1,1) (1,1)(2,1) (1,1)(1,2) (0,2)(1,2) (1,2)(1,3) (2,-1)(2,0) (1,0)(2,0) (1,0)(1,1) (1,1)(2,1) (1,1)(1,2) (0,2)(1,2) (1,2)(1,3) Note that we did not list all possible solutions. Deliverables In this assignment, you have to develop your own include file and source files, which can be compiled with the following command: gcc -std=c99 -pedantic -Wvla -Wall -Wshadow -O3 *.c -o pa5 All declarations and definition of data structures and functions must reside in the include file or source file. The executable pa5 would be invoked as follows: ./pa5 input file output file1 output file2 The executable loads the configuration of the poles and boards from input file and produces two output files. The first output file corresponds to a solution that allows Jane to cross the river with the fewest number of board turns. The second output file stores the number of board turns required when Jane starts the crossing at different rows. As shown earlier, there are different ways to achieve the the same fewest number of turns. All you have to do is produce one of those for the first output file. Input file format The input file, in text form, has the following format. The first line contains two numbers printed with the following format: “%d %d ” 4 Two integers are separated by a space and the line is terminated with a newline character. The first number is the number of rows of poles, and the second number is the number of columns of poles. Let M be the number of rows and N be the number of columns of poles. Subsequently, the input file has M −1 lines. Each of the M −1 lines contains N characters (not counting the newline character at the end of the line), which are 0 or 1, and these N characters describe the board configuration between two adjacent rows of poles. The character 1 means there is a board and the character 0 means there is no board. Thus the second line of the input file describes the board configuration between the top two rows of poles, and so on, and the last input line describes the board configuration between the bottom two rows of poles. The first of the N characters in a line describes the leftmost board configuration between the leftmost two poles of two adjacent rows of poles. The rightmost character in a line describes the rightmost board configuration between the rightmost two poles of the same two rows of poles. The input file for the starting configuration of the given example contains: 3 3 001 100 For the purpose of this programming assignment, you may assume that M ≥ 2 and N ≥ 1. Moreover, you may assume that both M and N are no greater than SHRT MAX. Format of first output file Please see the description on the solution representation. Although there could be many possible solutions, you should print only one of those solutions. Format of second output file To produce the second output file, you have to know the number of board turns required for Jane to cross the river when she starts at row 0, row 1, …, and row M − 1, respectively. For the example described earlier, when Jane starts at row 0, the number of board turns required for river crossing is 5. When Jane starts at row 1, the number of board turns required for river crossing is 4. When Jane starts at row 2, the number of board turns required for river crossing is also 4. The following shows the second output file that stores these information: 5 4 4 There are M lines, with each line being printed with the format “%d ” 5 Starting from row 0 until row M − 1, we print the number of board turns required for river crossing when Jane starts at the respective row. Electronic Submission The assignment requires the submission (electronically) of the C-code (source and include files) through Brightspace. You should create and submit a zip file called pa5.zip, which contains the .h and .c files. Your zip file should not contain a folder. zip pa5.zip *.c *.h You should submit pa5.zip to Brightspace. If you want to use a Makefile for your assignment, please include the Makefile in the zip file. In that case, you can create the zip file as follows: zip pa5.zip *.c *.h Makefile If the zip file that you submit contains a Makefile, we use that file to make your executable (by typing “make pa5” at the command line to create the executable called pa5). Grading The assignment will be graded based on the two output files produced by your program. The first output file accounts for 100 points and the second output file accounts for 50 bonus points. Even if you do not wish to earn the bonus points, your program should still account for two output files. With the bonus points, you can earn a maximum of 550 points from all programming assignments. The base points of the PA component (500 points) account for 45 points in the HW+PA score and the HW+PA+EX score. With the bonus points, you can earn a maximum of 49.5 points for the PA component for both the HW+PA score and HW+PA+EX score. It is important that all the files that have been opened are closed and all the memory that have been allocated are freed before the program exits. Memory leaks or memory errors reported by valgrind will result in a 50-point penalty. Be aware that we set a time-limit for each test case based on the size of the test case. If your program does not complete its execution before the time limit for a test case, it is deemed to have failed the test case. What you are given You are given some sample input files (in pa5 examples.zip) for you to partially test your program. The input files are river.in[0-3], and output files are river.in[0-3].out1 and river.in[0-3].out2. The example provided in this description can be found in river.in0, and the corresponding output files are river.in0.out1 and river.in0.out2.
You are required to implement a program to construct a height-balanced binary search tree (BST), starting from an empty tree, based on a sequence of insertion and deletion operations. You may have to perform rotation(s) to maintain the height-balanceness of the tree after each insertion or deletion. Note that heightbalanceness is defined as we covered in the class. Given a node, its balance is the height of its left subtree minus the height of its right subtree. A tree is height-balanced when every node in the tree has a balance that is −1, 0, or 1. As in the class, we will define the height of a tree recursively. An empty tree has a height of −1. The height of a tree is 1 plus the maximum of the height of the left sub-tree and the height of the right sub-tree. It is fine for you to use the code provided in the lecture notes for this assignment. However, you should re-organize the code. For example, you may want to write separate functions for clockwise rotation and counter-clockwise rotation, and the insertion function will call the appropriate rotation functions. Insertion In the lecture notes, we do not allow duplicate keys in a tree. In this assignment, we allow the insertion of a duplicate key. In other words, the resulting height-balanced may have multiple nodes storing the same key value. Recall that insertion of a key requires you to search for a suitable location to insert a leaf node. To handle nodes storing the same key value, when you search for a leaf node location to insert the key, you should always go left when you encounter a node storing the same key. This requirement is imposed for the grading purpose of this assignment. Deletion When you are asked to delete a key, the tree should stay intact if the key is currently not in the tree. There may be multiple nodes containing the key that you want to delete. You should delete the first such node that you encounter in the search process. If the node you want to delete has two children, you should replace that node with its immediate predecessor (in an in-order traversal of the tree). Again, this requirement is imposed for the grading purpose of this assignment. Tree node structure The tree node structure (Tnode) is defined in the file hbt.h. typedef struct _Tnode { int key: 29, balance: 3; struct _Tnode *left; struct _Tnode *right; } Tnode; The left and right fields store the left and right child nodes of a Tnode, respectively.An int, which has 32 bits, is used to store two bit fields: The bit field key uses 29 bits to store a signed integer value between HBT MIN and HBT MAX (inclusive), and the bit field balance uses 3 bits to store the difference in the height of the left sub-tree (left) and the height of the right sub-tree (right). A 29-bit signed integer can be as large as 228 − 1 = 268435455 (= HBT MAX) and as small as −2 28 = −268435456 (= HBT MIN). Both HBT MAX and HBT MIN are defined in hbt.h as follows: #define HBT_MAX 268435455 #define HBT_MIN -268435456 A 3-bit (signed) field can be as large as 22 −1 = 3 and as small as −4. Therefore, the bit field balance can store the balance of a height-balanced tree properly. Moreover, it can also store an (in)balance of 2 or −2 at a node when the tree becomes temporarily unbalanced. A correctly implemented height-balanced tree insertion or deletion routine should not allow the balance of a node to go below −2 or above 2. You should include this file in your other .h and .c files that you will develop for this assignment. This file will be provided when we compile your submission. You do not have to submit this file. In your other .h and .c, you should not define other structures. No other user-defined structures are allowed in this assignment. If you have other user-defined structure(s) in your .h and/or .c files, your submission will not be graded. Deliverables In this assignment, you are required to develop other include file(s) (in addition to the provided hbt.h) and source file(s), which can be compiled with the following command: gcc -std=c99 -pedantic -Wvla -Wall -Wshadow -O3 *.c -o pa4 It is recommended that while you are developing your program, you use the “-g” flag instead of the “-O3” flag for compilation so that you can use a debugger if necessary. There are two options that the executable pa4 can accept. The main function should simply return EXIT FAILURE if the argument count is incorrect or the options are invalid (see further details below). Option “-b”: Building a height-balanced BST ./pa4 -b operations input file tree output file The option “-b” means that you are building a height-balanced BST (starting from an empty tree) based on the operations specified in operations input file. Input file format The operations input file is an input file in binary format. Every operation is specifed by (sizeof(int) + sizeof(char)) bytes, with the first sizeof(int) bytes being an int and the next sizeof(char) byte being a char. The int is the key. The value stored in an int is guaranteed to be in the range of HBT MIN and HBT MAX (inclusive). In other words, the bit field key in a Tnode can always store the given int properly even though the bit field key has only 29 bits, whereas an int stored in a file has 32 bits. If it is an insertion of the specified key, the char is an ASCII character ’i’. If it is a deletion of the specified key, the char is an ASCII character ’d’.If there are n keys to be inserted or deleted, the file size is n×(sizeof(int)+sizeof(char)) bytes. Output file format The tree output file is an output file in binary format. This file stores the pre-order traversal of the constructed height-balanced BST. Each non-NULL node is represented by an int and a char. The int is of course the key stored in the node. We cannot just write into a file 29 bits stored in the bit field key. So, we store the 29-bit key as an int in the output file. The char is a binary pattern, with the least significant two bits capturing the types of branches that node has. At bit position 0 (the least significant bit position), a 0-bit means that the right branch of the node is NULL. A 1-bit means that the right branch of the node is a non-NULL node. At bit position 1 (the second least significant bit position), a 0-bit means that the left branch of the node is NULL. A 1-bit means that the left branch of the node is a non-NULL. All other more significant bits in the char should be 0. Therefore, a numerical value of 2 or 3 (in decimal) for the binary pattern stored in the char means there is a left child. A numerical value of 1 or 3 (in decimal) means that there is a right child. A numerical value of 0 means that there are no child nodes. Output and return value of main function If the given input file can be opened, your program should attempt to build a height-balanced BST. If the given input file cannot be opened, the program should print to the stdout the value -1 using the format “%d ” and return EXIT FAILURE. Now, suppose the given input file can be opened. If in the process of building the height-balanced BST, your program encounters a problem in the input file (wrong format, for example) or a failure in memory allocation, you should still write to the output file the tree that has been contructed so far. You should print to the stdout the value 0 using the format “%d ” and return EXIT FAILURE. We will test your program with valid input files of reasonable sizes. Therefore, it is unlikely that you will have to print the value 0 to the stdout. If you can successfully read the entire input file to build a tree, you should print to the stdout the value 1 using the format “%d ” and return EXIT SUCCESS; your program should return EXIT FAILURE otherwise. We are not asking you to check whether you can write to the output file. We will use the option “-e” to evaluate that. Option “-e”: Evaluating a height-balanced BST ./pa4 -e tree input file The option “-e” means that you are evaluating a tree specified in the tree input file. The tree input file is actually of the same format as the output produced using the “-b” option. For the given tree input file, your program should print three integers to stdout using the format “%d,%d,%d ” The first integer indicates the validity of the input file, the second integer indicates whether the tree is a BST, and the third integer indicates whether the tree is a height-balanced tree.If the input file cannot be opened, the first integer should be -1. If it can be opened, but of the wrong format, the first integer should be 0. If it can be opened and is of the correct format, the first integer should be 1. If the input file is a valid tree, the second and third integers are meaningful (otherwise, their values are not important). If the tree is a BST, the second integer is 1; otherwise, it is 0. If the tree is height-balanced, the third integer is 1; otherwise, it is 0. The main function should return EXIT SUCCESS only if the input file is valid (i.e., the first integer of the terminal output is 1); your program should return EXIT FAILURE otherwise. Electronic Submission The project requires the submission (electronically) of the C-code (source and include files) through Brightspace. You should create and submit a zip file called pa4.zip, which contains the .h and .c files. Your zip file should not contain a folder. zip pa4.zip *.c *.h You should submit pa4.zip to Brightspace. If you want to use a Makefile for your assignment, please include the Makefile in the zip file. In that case, you create the zip file as follows: zip pa4.zip *.c *.h Makefile If the zip file that you submit contains a Makefile, we use that file to make your executable (by typing “make pa4” at the command line to create the executable called pa4). Again, the file hbt.h will be provided by us. You do not have to include the file in the zip file. Grading The assignment will be graded based on the two tasks performed by your program. The first task of constructing a height-balanced BST accounts for 70% and the second task of evaluating a height-balanced BST accounts for 30%. It is important all the files that have been opened are closed and all the memory that have been allocated are freed before the program exits. Memory leaks or memory errors reported by valgrind will result in a 50-point penalty. Be aware that we set a time-limit for each test case based on the size of the test case. If your program does not complete its execution before the time limit for a test case, it is deemed to have failed the test case. As we are relying on some expected output printed to stdout for the evaluation of your submission, it is important that you do not use the stream stdout to print other messages. If you are relying on printing for the purpose of debugging, please print to the stream stderr. Moreover, we expect your program to print to stdout using the formats provided (one format for the -b option and one format for the -e option). If we cannot parse the output printed to stdout based on the formats provided in this assignment, your program is deemed to have failed the test case. What you are given You are given hbt.h, which defines the only structure you would use in this assignment. Moreover, you are given 4 sample input files (ops0.b, ops1.b, ops2.b, ops3.b) and the corresponding output files for the trees constructed (tree0.b, tree1.b, tree2.b, and tree3.b).The ops0.b file inserts 10 ascending keys -5, -4, …, 3, 4. The following figure shows the corresponding height-balanced BST in tree0.b. -2 -4 -5 -3 2 0 3 -1 1 4 The files ops1.b and ops2.b contain the same insertion operations and a deletion operation: delete 2. In ops1.b, the “delete 2” operation occurs after the insertion of 2. Therefore, the final tree contains only 9 keys. In ops2.b, the “delete 2” operation occurs before the insertion of 2. Therefore, the tree2.b and tree0.b are the same. While ops0.b, ops1.b, and ops2.b involve the insertion of distinct keys, ops3.b file involves the insertion and deletion of duplicate keys. Besides these height-balanced BSTs, we also provide you three invalid height-balanced BSTs (invalidtree0.b, invalidtree1.b, and invalidtree2.b). For invalidtree0.b, it is neither a BST nor a height-balanced tree (the corresponding print out to the screen should be 1,0,0 when evaluated with the “-e” option). For invalidtree1.b, it is not a BST, but it is a height-balanced tree (the corresponding screen dump is 1,0,1). For invalidtree2.b, it is a BST, but it is not a height-balanced tree (the corresponding screen dump is 1,1,0). To help you interpret these binary files, we also provide you the “equivalent” text files (ops0–3.txt, tree0–3.txt, and invalidtree0–2.txt). For an operations input file, each (int) key is printed with “%d” format. The key is followed by a space, and then the (char) operation (’i’ for insertion and ’d’ for deletion). For a tree file, each (int) key is again printed with “%d” format. The key is followed by a space, and then char ’0’ (the node has no children), ’1’ (the node has a right child and it has no left child), ’2’ (the node has no right child and it has a left child), or ’3’ (the node has a right child and a left child). Suggestions You may want to write a program that allows you to convert from tree0.b to tree0.txt and a program that allows you to convert from ops0.b to ops0.txt (in fact, the two programs can be combined into one). Similarly, you may want to write a program that converts from tree0.txt (or ops0.txt) to tree0.b (or ops0.b). This way, you can easily create other examples (operations input files and tree files) to test your programs. You should write the evaluation part first. This part allows you to test your construction part. (As a good practice, you think of how to evaluate/test your program before you write your program). There are two components of the evaluation (BST and height-balanceness), I recommend that you write the two components separately. For the construction part, I suggest that you write the insertion routine (with rotations) first. However, try to write rotation operations as functions (that could be used by the deletion routine later on). Then, you write the deletion routine. It is easier to write the deletion as a recursive function because you may have to perform rotations all the way to the root node. A recursive routine makes it easier to keep track of all thenodes encountered in the process of searching for the deleted node. Otherwise, you should use a stack to keep track of the nodes encountered in the search process. You should also write the deletion routine in such a way that the height-balancing part can be easily isolated such that if necessary, you could comment out the height-balancing part and the routine is simply doing a regular deletion of a key from a BST (without worrying about height-balancing). This could be helpful when it comes to debugging. Moreover, in the worst case scenario, you can also comment out this part and still have a somewhat functioning deletion routine in your final submission should you encounter problems in maintaining a height-balanced tree. As you write the program, use the evaluation part to test your insertion and deletion routines. Bit fields A bit field in a struct can be accessed just like a regular field in a struct. Assume that we have a variable Tnode nd, we can access the bit field key in nd as nd.key. Similarly, assume that we have a variable Tnode *nd ptr that stores the address of a Tnode, we can access the bit field balance as nd ptr->balance. However, there is a major distinction between a bit field in a struct and a “regular” field in a textttstruct. We cannot get the address of a bit field in a struct. For example, we cannot find the address of the bit field key or balance using the ampersand operator. Using the examples of nd and nd ptr in the preceding paragraph, we cannot use &(nd.key) or &(nd ptr->balance) to find the addresses of the corresponding bit fields. Therefore, for this assignment, if you want to write the contents of nd.key into a file using fwrite, you would have to first assign the value to an int variable, and then use that variable to write to a file. Similarly, you also cannot use fread to read an int from a file into nd ptr->key directly. You have to first read from a file into an int variable, and then assign the value to nd ptr->key. On the other hand, for a “regular” field such as left or right, we can find the addresses of the corresponding fields in a Tnode with the ampersand operator, e.g., &(nd.left) or &(nd ptr->right).
In programming assignment #2 (PA2), you implemented a program involving tree traversal(s) to compute the packing of rectangles, represented by a strictly binary tree. In that assignment, you assume that the given binary tree represents only one possible packing. H 3 V 1 2 (a) A binary tree (b) The corresponding packing 1 V 2 3 H H 3 V 1 2 (c) Re-rooting at V1 V V 1 H 3 2 1 V 2 3 H (5,4) (7,7) (3,3) (12,10) This assignment is a continuation of PA2 in some sense. However, this assignment is also different from PA2. In PA2, you assume that the given binary tree represents only one possible packing. In this assignment, you will learn that for a given binary tree with n leaf nodes (i.e., n rectangles), it can simultaneously represent 2n− 3 possible packing solutions, one of which is the solution you computed in PA2. Let us consider the 3-rectangle example shown in PA2 and redrawn here. Recall that the dimensions (width, height) of the three rectangles 1, 2, and 3 are (4,5), (7,7), and (3,3), respectively. The smallest room (shown in (b)) containing the three rectangles is of dimensions (12,10). (c) shows another binary tree representation that can be obtained from the representation in (a). This representation in (c) is obtained by re-locating the root node of the tree in (a) on the edge V1. We call the re-location of the root node as re-rooting. When we re-root V1, 1 is kept as the left node of V, as in the original tree. The parent node of V would now be the right child node of V in the re-rooted representation, and the original right child node of V now becomes the right child node of H, the original parent node of V. H 3 V 1 2 (d) Re-rooting at V2 V V H 2 3 1 1 V 2 3 H Essentially, we kept the V1 edge. Hence, we made the original parent node of V the new right child of V. As V is the right child of the original parent node, we made the original right child of V the new right child of the original parent node. (d) shows the binary tree representation obtained by re-rooting the edge V2. Here, we kept the V2 edge. Therefore, we madethe original parent node of V the new left child of V. As V is the right child of the original parent node, we made the original left child of V the new right child of the original parent node. The representation in (c) still requires a room of dimensions (12,10) to pack all rectangles. However, the representation in (d) requires a smaller room of dimensions (12,7). In other words, the representation is (d) is more optimal than the representations in (a) and (c). Note that while this re-rooting operation may look similar, it is actually different from the rotation operations that are used to balance the height of a binary search tree. The preceding example demonstrates how you may re-root a strictly binary tree representation at edges that are separated from the original root node by just one edge. Now, we shall show you how to re-root at edges that are farther away from the original root node. H H H V V V V 1 2 3 4 5 6 8 7 (a) (b) (c) (d) V H H V H V V 1 2 3 4 5 6 8 7 (a) Re-rooting at VV V H H V H V V 1 2 3 4 5 6 7 8 (b) Re-rooting at VH H H V V H V V 1 2 3 4 5 6 8 7 (c) Re-rooting at HV V H V V H V 4 1 2 3 5 6 8 7 (d) Re-rooting at V4 H Consider the second example in PA2, as shown in the upper left corner of the preceding figure. We want to re-position at the root node on the edge V4 (d). First, note that the path from the V4 to the root node includes the edge HV (c), V H (b), and VV (a). Here, we do not consider the right branch of the root node. Let Re-Root(T, e) denote the new tree obtained by re-rooting at edge e of a given tree T, where e is one edge away from the root node of T. Let T be the tree representation in the upper left corner of the preceding figure. The following new tree representation corresponding to the operation of re-rooting at V4: Re-Root(Re-Root(Re-Root(Re-Root(T,VV) | {z } (a) ,V H) | {z } (b) ,HV) | {z } (c) ,V4) | {z } (d)The binary tree in (a) is re-rooted to form the binary tree in (b), which is re-rooted to form the binary tree in (c), which is then re-rooted to form the binary tree in (d). In other words, to re-root at an edge, it is necessary to first re-root at the edges from the root node (except for the edge immediately after the root node) to the edge of interest. Given a strictly binary tree of n > 1 leaf nodes (i.e., rectangles), there are 2n − 1 nodes altogether. Therefore, there are 2n − 2 edges altogether. Among these edges, we do not re-root the two edges right below the root nodes (as the re-rooting operation cannot be applied when there is no parent node). Therefore, other than the given representation, there are 2n − 4 representations that can be derived from re-rooting. Altogether, there are 2n−3 strictly binary tree representations for a given strictly binary tree representation. Therefore, there are 3 representations in the first example and 13 representations in the second example. When there are n = 2 leaf nodes, there is only one representation available. When there is n = 1 leaf node, there is only one representation available; no re-rooting is possible because there are no edges. Since you may have already found the solution of the explicit representation of a given strictly binary tree, this assignment asks you to find the solutions of the representations that can be derived from re-rooting as defined earlier. Given a binary tree representation of n ≥ 1 leaf nodes, you will write a program to find for each of the available re-rooted representations, the width and height of the smallest rectangular room to enclose all rectangles for that re-rooted representation. Again, when n = 1 or 2, there are no re-rooted representations available. When n > 2, there are 2n−4 re-rooted representations. H H H V V V V 1 2 3 4 5 6 8 7 (a) (e) V H H V H V V 1 2 3 4 5 6 8 7 (a) Re-rooting at VV (e) Re-rooting at V8 V H H V H V V 1 2 3 4 5 6 8 7 The key to this assignment is to again recognize that it takes tree traversal to perform the computation. Take a look at the preceding figure, where (a) is re-rooting at VV (as in the earlier example) and (e) is re-rooting at V8. In both cases, the smallest rectangular rooms for the root node V and its child node H can be computed with the rectangular rooms computed in the original tree on the left. It is not necessary to really re-root the tree, i.e., updates the pointers to construct different trees. What is again important is to figure out the necessary information to pass along as you traverse the tree. Deliverables: In this assignment, you are to develop your own include files and source files, gcc -O3 -std=c99 -Wall -Wshadow -Wvla -pedantic *.c -o pa3Again, if you supply a Makefile, we will use the command ‘‘make pa3’’ to generate the executable pa3. The executable pa3 would be invoked as follows: ./pa3 in file out file1 out file2 out file3 As in PA2, the executable loads the binary tree from in file and produces three output files out file1, out file2, and out file2. You should model your main function after the main function in PA2. However, the input file in file is of the same format as the first output file of PA2. In other words, the input file is obtained by performing a post-order traversal of the strictly binary tree. Therefore, given a post-order traversal, you have to re-construct the corresponding strictly binary tree. (In PA2, you have to re-construct the corresponding strictly binary tree when you are given its pre-order traversal.) The first two output files are of the same format as the input file of PA2, a pre-order traversal of a strictly binary tree representing a packing. Please refer to the description file of PA2 for a description of the formats of in file, out file1, and out file2. Again, the format of in file of PA3 is the same as the format of out file1 of PA2. The format of out file1 and out file2 of PA3 is the same as the format of in file of PA2. The strictly binary tree of the packing for the first output file out file1 is obtained as follows: Starting from the root node, you alternately visit the left and right edges down the tree until you come to a leaf node. The first output file should contain the strictly binary tree of the packing that is obtained by re-rooting at the last edge of this path. Of course, to re-root at this last edge, it is necessary to perform re-rooting at corresponding edges along the way (except for the left edge of the root node). As a result, for the 3-rectangle example shown earlier, the corresponding re-rooted strictly binary tree is the same as the given strictly binary tree, as no re-rooting can be performed. On the other hand, for the 8-rectangle example, the given strictly binary tree should be re-rooted at the edge H1. The pre-order printing of the re-rooted strictly binary tree for the these two examples are in 3lr.pr and 8lr.pr. The strictly binary tree of the packing for the second output file out file2 is obtained as follows: Starting from the root node, you alternately visit the right and left edges down the tree until you come to a leaf node. The second output file should contain the strictly binary tree of the packing that is obtained by re-rooting at the last edge of this path. Again, to re-root at this last edge, it is necessary to perform re-rooting at corresponding edges along the way (except for the right edge of the root node). As a result, for the 3-rectangle example shown earlier, the corresponding re-rooted strictly binary tree is obtained by re-rooting at the edge V1. For the 8-rectangle example, the given strictly binary tree should be re-rooted at the edge V6. Of course, to obtain this, we have to re-root at edge VV and then V6. The pre-order printing of the re-rooted strictly binary tree for the these two examples are in 3rl.pr and 8rl.pr. We now provide the details of the output file out file3. Format of third output fileargv[4] out file3 contains the name of the file that pa3 would use to store the dimensions of the smallest rectangular room that encloses all rectangular blocks for each re-rooted representation. The file is divided into lines, and each line corresponds to a node in the given strictly binary tree, and the nodes are printed in a pre-order traversal fashion. Recall that the re-rooting is defined based on an edge in the given strictly binary tree. Therefore, each node, except the root node, can uniquely identify the edge that connects the node to its parent node in the given strictly binary tree. There are therefore at most three nodes that each does not correspond to an edge that could be re-rooted. The root node does not have a parent edge. If the given strictly binary tree has n ≥ 2 leaf nodes, the left child node or right child node also does not correspond to an edge that could be re-rooted. If such a node is a leaf node, which is a rectangular block, we print to the output file with the format “%d ”, where the int is the label of the rectangular block. If it is a non-leaf node, we print a character (followed by a newline character): “%c ”. The character is either ’V’ or ’H’, representing either a vertical cutline or a horizontal cutline, respectively. For the other lines in the output file, each of them corresponds to an edge (connecting the node to its parent node) that could represent a re-rooted topology. If the node is a leaf node, we print to the output file with the format “%d(%d,%d) ”, where the first int is the label of the rectangular block, the second int and the third int are respectively the width and height of the smallest rectangular room enclosing all rectangular blocks for this re-rooted representation. If the node is a non-leaf node, we print to the output file with the format “%c(%d,%d) ”, where the first char is either ’V’ or ’H’ representing the cutline of the non-leaf node, and the two int’s are respectively the width and height of the smallest rectangular room enclosing all rectangular blocks for this re-rooted representation. For the 3-rectangle example, the following is the expected third output file (3.rdim): H 3 V 1(12,10) 2(12,7) Note that the first three lines correspond to the root node, left of root node, and the right of root node, all of which do not have re-rooted representations. For the 8-rectangle example, the following is the expected third output file (8.rdim):H H V(11,15) 2(12,14) 5(14,15) 1(11,15) V V(13,11) H(13,11) 3(13,14) V(12,16) 7(13,16) 4(15,13) 6(13,11) 8(11,15) The first, second, and the seventh lines correspond to the root node, left of root node, and right of root node, all of which do not have re-rooted representations. Submission: The assignment requires the submission (through Brightspace) of a zip file called pa3.zip that contains the source code (.c and .h files). You can create your zip file as follows: zip pa3.zip *.c *.h Your zip file should not contain a folder. You may also include a Makefile in the zip file. In that case, you can create your zip as follows: zip pa3.zip *.c *.h Makefile Grading The grade depends on the correctness of your program and the efficiency of your program. The first output file accounts for 25 points, and the second output file accounts for 25 points, and the third output file accounts for 50 points of the entire grade. Any output files that do not follow the formats specified in this assignment will be considered to be wrong. It is important that your program can accept any legitimate filenames as input or output files. Even if you cannot produce all output files correctly, you should still write the main function such that it produces as many correct output files as possible. If you do not the algorithm to produce the necessary information required to generate an output file, you should leave the output file as an empty file.It is important all the files that have been opened are closed and all the memory that have been allocated are freed before the program exits. Any memory leaks or errors will result in 50% penalty. What you are given We provide the post-order traversals of the 3-rectangle and 8-rectangle examples in 3.po and 8.po, respectively. We also provide the three output files of the 3-rectangle (3lr.pr, 3rl.pr, and 3.rdim, respectively) and 8-rectangle examples (8lr.pr, 8rl.pr, and 8.rdim, respectively. We also provide the post-order traversals of 100-rectangle, 500-rectangle, and 1000-rectangle examples in 100.po, 500.po, and 1K.po, respectively.
You will implement a program to compute the “2D packing” of rectangular blocks. The “packing” of the rectangular blocks must follow a topology described using a strictly binary tree. A strictly binary tree is a binary tree where a node has either 0 or 2 child nodes. A node with 0 child nodes is a leaf node and a node with 2 child nodes is an internal (non-leaf) node. “Packing” In this strictly binary tree, each leaf node represents a rectangular block. Each internal node of the binary tree represents a partitioning of two groups of rectangular blocks by a horizontal cutline or a vertical cutline. Let xHy (xV y) denote a (sub)tree, whose root node is a horizontal cut H (a vertical cut V). The left and right subtrees of H (V) are x and y, respectively. Assume that xHy means x is above and y is below the horizontal cut, and xV y means x is to the left of and y is to the right of the vertical cut. In the following figure, we show a “packing” of three rectangular blocks based on a given strictly binary tree representation. Assume that the dimensions (width, height) of the three rectangular blocks 1, 2, and 3 are respectively (5,4), (7,7), and (3,3). H 3 V 1 2 (a) A binary tree (b) The corresponding packing 1 V 2 3 H (5,4) (7,7) (3,3) (12,10) Each subtree (whose root node is an internal node) is enclosed by a smallest rectangular room. The smallest room containing the subtree 1V2, for example, is of dimensions (12,7). The smallest room containing the tree 3H(1V2) is of dimensions (12,10). This room is partitioned into two smaller rooms: The top room is of dimensions (12,3) and it contains the rectangular block 3. The bottom room is of dimensions (12,7) and it contains the rectangular blocks 1 and 2. We place the lower left corner of each rectangular block at the lower left corner of its room.Assume that the lower left corner of the smallest room containing all rectangular blocks is at coordinates (0,0) (x- and y-coordinates). As mentioned earlier, this room of dimensions (12,10) is partitioned into a top room of dimensions (12,3) and a bottom room of dimensins (12,7) because the root node has a horizontal cut. Note that the smallest rectangular room containing rectangular block 3 is of dimensions (3,3), and it can be contained in the top room of dimensions (12,3). The smallest rectangular room containing the V node is of dimensions (12,7) and it can be contained in the bottom room of dimensions (12,7). The bottom room, should also have its lower left corner at coordinates (0,0). As the bottom room is of height 7, the top room should have its lower left corner at coordinates (0,7). The bottom room is partitioned into a left room of dimensions (5,7) and a right room of dimensions (7,7) because the corresponding non-leaf node has a vertical cut. Note that the smallest rectangular room containing rectangular block 1 is of dimensions (5,4), and it can be contained in the bottom-left room of dimensions (5,7). Of course, the smallest rangular room containing rectangular block 2 is of dimensions (7,7), and it can also be contained in the bottom-right room of dimensions (7,7). As the bottom room has its lower left corner at coordinates (0,0), the bottom-left room should have its lower left corner at coordinates (0,0). Because the bottom-left room is of width 5, the bottom-right room should have its lower left corner at coordinates (5,0). Rectangular block 1, which is contained in the bottom-left room, should therefore have its lower left corner at coordinates (0,0). Rectangular block 2, which is contained in the bottomright room, should have its lower left corner at corrdinates (5,0). Rectangular block 3, which is contained in the top room, should have its lower left corner at coordinates (0,7). Note that even though there is space directly above block 1 to accommodate block 3, block 3 has to stay above the horizontal cutline in the “packing,” as shown in the figure. That is the reason we use “packing” instead of packing in this document. We do not really pack the rectangular blocks tightly. For this programming assignment, you are given a strictly binary tree representation of a “packing” of rectangular blocks. You have to determine the smallest room to enclose all rectangular blocks and their coordinates, under the conditions that the cutlines are respected and that the lower left corner of a rectangular black coincides with the lower left corner of its room. Deliverables In this assignment, you are to develop your own include files that define the structures you want to use and declare the functions you need to manipulate the structures. You should define these functions in your source files. Your programs should be compiled with the following command: gcc -O3 -std=c99 -Wall -Wshadow -Wvla -pedantic *.c -o pa2 Again, if you supply a Makefile, we will use the command ‘‘make pa2’’ to generate the executable pa2. The executable pa2 would be invoked as follows: ./pa2 in file out file1 out file2 out file3The executable loads the strictly binary tree from in file and saves the results into three output files: out file1, out file2, and out file3. The input file in file contains the strictly binary tree and the dimensions of the rectangular blocks. The in file corresponds to a pre-order traversal of the strictly binary tree. The executable should construct the corresponding strictly binary tree and output to out file1 a post-order traversal of the strictly binary tree. The output files out file2 and out file3 store the “packing” of these rectangular implementation, with out file2 storing the dimensions of the rectangular rooms containing the rectangular blocks and out file3 storing the coordinates of the rectangular blocks. The main function should return EXIT SUCCESS when the correct number of arguments are provided, a strictly binary tree can be built successfully from the given input file, and all output files can be produced; otherwise, the main function should return EXIT FAILURE. Format of input file argv[1] in file contains the name of the file that stores the strictly binary tree representation of a “packing” of rectangular blocks. The file is divided into lines, and each line corresponds to a node in the strictly binary tree. If it is a leaf node, which is a rectangular block, it has been printed with the format “%d(%d,%d) ”, where the first int (specified by %d) is the label of the rectangular block, followed by the dimensions (width, height) of the rectangular block, with the second int in the line being the width of the rectangular block and the third int in the line being the height. Except for the newline character, there are no white-space characters in the line. If there are n rectangular blocks in the “packing,” the labels are from 1 through n. If it is a non-leaf node, it is simply a character (followed by a newline character). The character is either ’V’ or ’H’, representing either a vertical cutline or a horizontal cutline, respectively. These nodes are printed in a pre-order traversal of the strictly binary tree. Except for the newline character, there are no other white-space characters in each line. For the example of three rectangular blocks, the input file is in 3.pr as follows: H 3(3,3) V 1(5,4) 2(7,7) Format of first output file argv[2] out file1 contains the name of the file that pa2 would use to store the strictly binary tree in a post-order traversal fashion. The format of this file should be similar to that of the input file except the order in which you print the nodes. The file is divided into lines, and each line corresponds to a node in the strictly binary tree. If it is a leaf node, which is a rectangular block, it should be printed with the format“%d(%d,%d) ”, where the first int is the label of the rectangular block, the second int is the width of the rectangular block and the third int is the height of the rectangular block. If it is a non-leaf node, it is simply a character (followed by a newline character). The character is either ’V’ or ’H’, representing either a vertical cutline or a horizontal cutline, respectively. Except for the newline character, there are no other white-space characters in each line. For the example of three rectangular blocks, the first output file is in 3.po as follows: 3(3,3) 1(5,4) 2(7,7) V H Format of second output file argv[3] out file2 contains the name of the file that pa2 would use to store the dimensions of all rectangular blocks (leaf nodes) and smallest rectangular rooms (non-leaf nodes or internal nodes) of a “packing.” As in the first output file, the nodes are printed in a post-order traversal of the strictly binary tree. As before, if it is a leaf node, which is a rectangular block, it should be printed with the format “%d(%d,%d) ”, where the first int is the label of the rectangular block, the second int is the width of the rectangular block and the third int is the height of the rectangular block. If it is a non-leaf node, it should be printed with the format “%c(%d,%d) ”, where the char is either ’V’ or ’H’, representing either a vertical cutline or a horizontal cutline, respectively. The first and second int’s are the width and height, respectively, of the smallest rectangular room to enclose all rectangular blocks in the subtree whose root is the non-leaf node. Except for the newline character, there are no other white-space characters in each line. For the example of three rectangular blocks, the second output file is in 3.dim as follows: 3(3,3) 1(5,4) 2(7,7) V(12,7) H(12,10) Format of third output file argv[4] out file4 contains the name of the file that pa2 would use to store the coordinates of all rectangular blocks (leaf nodes) of a “packing.”The file should contain a line for each rectangular block. The ordering of the blocks in the output file should be the same as the ordering of blocks in the input file. Every line is of the format “%d((%d,%d)(%d,%d)) ”, where the first int specifies the label of the rectangular block. The first (%d,%d) corresponds to the dimensions (width, height) of the rectangular block. The second (%d,%d) corresponds to the x- and y-coordinates of the bottom left corner of the rectangular block in the “packing.” Except for the newline character, there are no other white-space characters in each line. For example, 3.pck stores this output as follows: 3((3,3)(0,7)) 1((5,4)(0,0)) 2((7,7)(5,0)) Submission The assignment requires the submission (through Brightspace) of a zip file called pa2.zip that contains the source code (.c and .h files). You could create pa2.zip as follows: zip pa2.zip *.c *.h Your zip file should not contain a folder. You may also include a Makefile in the zip file. In that case, you can create pa2.zip as follows: zip pa2.zip *.c *.h Makefile Grading The grade depends on the correctness of your program and the efficiency of your program. The first output file accounts for 30 points, and the second output file accounts for 30 points, and the third output file accounts for 40 points of the entire grade. Any output files that do not follow the formats specified in this assignment will be considered to be wrong. It is important that your program can accept any legitimate filenames as input or output files. Even if you cannot produce all output files correctly, you should still write the main function such that it produces as many correct output files as possible. If you do not have a working algorithm to generate the necessary information of an output file, you should leave the output file as an empty file. Up to 5 points will be deducted if your main function does not return the correct value. It is important all the files that have been opened are closed and all the memory that have been allocated are freed before the program exits. Any memory issues (memory leaks or memory errors reported by valgrind) will result in 50% penalty. Be aware that we set a time-limit for each test case based on the size of the test case. If your program does not complete its execution before the time limit for a test case, it is deemed to have failed the test case.What you are given We provide two sample input files (3.pr and 8.pr) for you. The corresponding first, second, and third output files for 3.pr are 3.po, 3.dim, and 3.pck, and those for 8.pr are 8.po, 8.dim, 8.pck. The figure in the next page shows the topology and “packing” of the 8-block example. H H V V H V V 2 5 1 8 6 3 7 4 1 2 3 4 5 6 7 8 Three more input files are provided (100.pr, 500.pr, 1K.pr). However, we do not provide you the corresponding output files.
This assignment is to be completed on your own. You will implement Shell sort on an array and Shell sort on a linked list. In both cases, you will use the following sequence for Shell sort: {1,2,3,4,6,…,2 p 3 q ,…}, where every integer in the sequence is of the form 2p3 q and is smaller than the size of the array to be sorted. Note that most of the integers in this sequence, except perhaps for some, can always be used to form a triangle, as shown in Lecture slides on insertion sort and Shell sort. There may be incomplete rows of integers in the sequence below the triangle. For example, if there are 15 integers to be sorted, the corresponding sequence {1,2,3,4,6,9,8,12} would be organized as follows, with an incomplete row containing the integers 8 and 12 in the sequence: 1 2 3 4 6 9 8 12 You are not allowed to pre-compute the sequence and store them in your program. The sequence has to be generated as part of your Shell sort functions. Moreover, you have to generate the sequence such that the numbers in the sequence are sorted. For the sequence generated for sorting 15 numbers, the sorted sequence is {1,2,3,4,6,8,9,12}. Your Shell sort will perform 12-sorting, 9-sorting, 8-sorting, …, 2-sorting, and 1-sorting. Functions to be written We provide you three .h files: sequence.h, shell array.h, and shell list.h. You will develop the functions declared in these .h files in the corresponding .c files: sequence.c, shell array.c, and shell list.c. These .c files and pa1.c are the only files you will submit for this assignment. For this assignment, you are not allowed to define additional structures (struct). If your submission contains additional structures, your submission will receive a grade of 0. You are also not allowed to use mathematical functions declared in math.h and defined in the math library. If your submission includes math.h or calls math functions declared in math.h and defined in the math library, your submission will receive a grade of 0.However, you are allowed to define additional helper functions. These helper functions should be declared as static so that the scope of each helper function stays within that of the .c file that contains the helper function. Do not modify the provided .h files because you are not submitting them. Any modifications you have made to the provided .h will not be reflected in the .h files that we use to evaluate your submission. Function you will write for sequence.c: long *Generate 2p3q Seq(int n, int *seq size) Here, n is the number of long integers to be sorted. You should determine the number of elements in the sequence and store that number in *seq size. For example, if n is 0 or 1, the sequence should contain 0 elements. Therefore, *seq size should store 0. For n = 16, the sequence should contain 8 elements. Therefore, *seq size should store 8. The function should allocate space to store the elements of the sequence as long integers. Even when the sequence is empty, you should allocate a space of 0 elements. Moreover, these elements must be stored in ascending order. The address of the long array is returned. If malloc fails, you should return NULL and store 0 in *seq size. This function will be called by the Array Shellsort and List Shellsort functions. It is important that the caller function, e.g., Array Shellsort or List Shellsort function, has an integer variable to store the size of the sequence, and pass the address of this variable into long *Generate 2p3q Seq(int n, int *seq size) using the seq size parameter. Any helper functions for Generate 2p3q Seq, if any, must reside in sequence.c. These helper functions should be declared as static. Functions you will write for shell array.c: There are three functions that deal with performing Shell sort on an array. The first two functions Array Load From File and Array Save To File, are not for sorting, but are needed to transfer the long integers to be sorted from and to a file in binary form to and from an array, respectively. long *Array Load From File(char *filename, int *size) The size of the binary file whose name is stored in the char array pointed to by filename should determine the number of long integers in the file. The size of the binary file should be a multiple of sizeof(long). You should allocate sufficient memory to store all long integers in the file into an array and assign to *size the number of integers you have in the array. The function should return the address of the memory allocated for the long integers. You may assume that all input files that we will use to evaluate your code will be of the correct format. Note that we will not give you an input file that stores more than INT MAX long integers (see limits.h for INT MAX). If the input file is empty, an array of size 0 should still be created and *size be assigned 0. You should return a NULL address and assign 0 to *size only if you could not open the file or fail to allocate sufficient memory. It is important that the caller function, e.g., the main function, has an int variable to store the size of the array, and pass the address of this variable into long *Array Load From File(char *filename, int *size) using the size parameter. int Array Save To File(char *filename, long *array, int size)The function saves array to an external file specified by filename in binary format. The output file and the input file have the same format. The integer returned should be the number of long integers in the array that have been successfully saved into the file. If array is NULL or size is 0, an empty output file should be created. Note that this function asks you to save an array to a file. It does not ask you to free the array. void Array Shellsort(long *array, int size, long *n comp) The function takes in an array of long integers and sort them (using the Shell sorting algorithm). size specifies the number of integers to be sorted, and *n comp should store the number of comparisons involving items in array throughout the entire process of sorting. This function will have to call Generate 2p3q Seq to obtain the sequence of numbers to be used for Shell sort. You may choose to use insertion sort or bubble sort to sort each sub-array. (If you use selection sort to sort each sub-array, your program may have high run-time complexity if you do not take advantage of the properties of the sequence.) A comparison that involves an item in array, e.g., temp < array[i] or array[i] < temp, corresponds to one comparison. A comparison that involves two items in array, e.g., array[i] < array[i-1], also corresponds to one comparison. Comparisons such as i < j where i or j are indices are not considered as comparisons for this programming assignment. It is important that the caller function, e.g., the main function, has a long integer variable to store the number of comparisons, and pass the address of this variable into void Array Shellsort(long *array, int size, long *n comp) using the n comp parameter. Any support functions for these three functions, if any, must reside in shell array.c. These helper functions should be declared as static. Functions you will have to write for shell list.c: There are also three functions that deal with performing Shell sort on a linked list. In this assignment, you will use the following user-defined type to store long integers in a linked list: typedef struct Node { long value; struct Node *next; } Node; This structure has been defined in shell list.h. Given the definition of the structure Node, these are the three functions you have to write to deal with performing Shell sort on a linked list: Node *List Load From File(char *filename) The load function should read all (long) integers in the input file into a linked list and return the address pointing to the first node in the linked list. The linked list must contain as many Nodes as the number of long integers in the file. You should not have additional nodes in the linked list. Moreover, the long integers should be stored in the same order in the linked list as they are stored in the file. In other words, the first (last) long integer in the input file is the long integer stored in the first (last) node of the list. You should return an empty list if you could not open the file or fail to allocate sufficient memory. int List Save To File(char *filename, Node *list) The save function should write all (long) integers in a linked list into the output file in the order in which they are stored in the linked list. This function returns the number of integers successfully written into the file.Note that this function asks you to save a list to a file. It does not ask you to free the list. Node *List Shellsort(Node *list, long *n comp) The Shell sort function takes in a list of long integers and sort them. To correctly apply Shell sort, you would have to know the number of elements in the list and generate the sequence used for sorting accordingly (by calling Generate 2p3q Seq). The address pointing to the first node of the sorted list is returned by the function. Similar to the case of an array, a comparison here is defined to be any comparison that involves the field value in the structure Node. Note that if you are given a list of n Nodes, you should return a sorted list of n Nodes. 100 addr: 30 104 addr: 40 12 addr: 50 99 addr: 20 9 addr: 10 NULL (a) Original list (b) Sorting by manipulating addresses of Nodes 100 addr: 30 104 addr: 40 12 addr: 50 99 addr: 20 9 addr: 10 NULL 40 value next 50 20 10 0 40 0 20 30 50 The List Shellsort function must perform sorting by manipulating the next fields of the Nodes. Figure (a) shows an original list that is unsorted. Figure (b) shows how the list is sorted by storing the correct addresses in the next fields. The long integers stored in the value fields remain in the original Nodes. For example, the integer 99 is stored in a Node with an address 20 in the original list. The field of the same Node stores the address 10, allowing it to point to the Node storing the value 9. After sorting, 99 is still stored in the value field of the Node with address 20. However, the next field of the Node now stores 30, allowing it to point to the Node storing the value 100. In other words, each long integer must reside in the same Node in the original list before and after sorting. The only array that appears in this function is the sequence generated by Generate 2p3q Seq. You are not allowed to have other arrays (of any types) in this file. Therefore, you cannot divide a list into sub-lists and use an array to store these sub-lists. This restriction also applies to all helper functions of List Shellsort. Any additional helper functions should be defined in shell list.c file. These helper functions should be declared as static. It is important that the linked list returned from and/or passed into these three functions in shell list.c contain only nodes that store valid values. main function you will write in pa1.c: You have to write another file called pa1.c that would contain the main function to invoke the functions in shell array.c and shell list.c. Note that the function in sequence.c is invoked indirectly by the two Shellsort functions in shell array.c and shell list.c.You should be able to obtain the executable pa1 with the following command: gcc -O3 -std=c99 -Wall -Wshadow -Wvla -pedantic sequence.c shell array.c shell list.c pa1.c -o pa1 The flags used are a subset of the flags used in ECE26400. Note that the -Werror flag has been taken out. Also, the optimization flag -O3 is used. It is recommended that while you are developing your program, you use the “-g” flag instead of the “-O3” flag for compilation so that you can use a debugger if necessary. It is your responsibility to make sure that your submission can be complied successfully on eceprog. Just to be sure, you should type in alias gcc at the command line and check whether your gcc uses the correct set of flags. When the following command is issued, ./pa1 -a input.b output.b the program should load from input.b the long integers to be sorted and store them in an array, run Shell sort on the array, and save the sorted long integers in output.b. The program should also print the number of comparisons performed to the standard output with the following format: “%ld ” ./pa1 -l input.b output.b the program should load from input.b the long integers to be sorted and store them in a linked list, run Shell sort on the linked list, and save the sorted long integers in output.b. The program should also print the number of comparisons performed to the standard output with the following format: “%ld ” What should the main function do when an empty file or an invalid file is given? For the -a option, the load function (Array Load From File) returns a NULL address if you could not open the file or fail to allocate sufficient memory. The main function should exit with EXIT FAILURE when the returned address of the load function is NULL. For an empty input file, the load function should return a valid array of size 0. Therefore, an empty output file should be created. For the -l option, the current setup does not allow you to distinguish between an empty file, an invalid input filename, or failure in memory allocation (they all result in an empty linked list from the load function (List Load From File) for linked lists). Therefore, you should always continue to perform sorting and writing (an empty output file). You may declare and define other static help functions in pa1.c. Submission and Grading: The assignment requires the submission (electronically) of a zip file called pa1.zip through Brightspace. The zip file should contain sequence.c, shell array.c, shell list.c, and pa1.c. We do not expect you to turn in a Makefile because we are going to evaluate your functions individually. Any other files in the zip file will be discarded. Your zip file should not contain a folder (that contains the source files). Assuming that your folder contains sequence.c, shell array.c, shell list.c, and pa1.c (and no other .c files), you can create pa1.zip as follows: zip pa1.zip sequence.c shell_array.c shell_list.c pa1.cIt is important that if the instructor has a working version of pa1.c, it should be compilable with your sequence.c, shell array.c and shell list.c to produce an executable. Similarly, if the instructor has a working version of sequence.c, it should be compilable with your pa1.c, shell array.c and shell list.c to produce an executable. For evaluation purpose, we will use different combinations of your submitted .c files and our .h and .c files to generate different executables. If a particular combination does not allow an executable to be generated, you do not get any credit for the function(s) that the executable is supposed to evaluate. The loading and saving functions will account for 20%. The sequence generation function will account for 20%. The Shell sort function for arrays will account for 20%. The Shell sort function for lists will account for 40%. The main function does not account for any points. However, if your main function does not work properly, we will deduct up to 5 points. Be aware that we set a time-limit for each test case based on the size of the test case. If your program does not complete its execution before the time limit for a test case, it is deemed to have failed the test case. We will not announce the time-limits that we will use. You should instead analyze whether your implementation has the expected time complexity through the numbers of comparisons or the runtimes for various test cases. You can obtain the runtime using the command time, e.g., time ./pa1 -l input.b output.b. It is important all the files that have been opened are closed and all the memory that have been allocated are freed before the program exits. A caller function that receives heap memory should be responsible for freeing it. For example, if the instructor’s main function calls the Array Load From File function, it is the responsibility of the main function to free the returned array. It is not the responsibility of the Array Shellsort or Array Save To File to free the array. Memory issues will result in 50-point penalty. Given: We provide .h files, namely, sequence.h, shell array.h, and shell list.h. We also provide sample input files in pa1 examples.zip. (Use the command unzip pa1 examples.zip to unzip the zip file.) All “.b” files are binary files. The number in the name refers to the number of long integers the file is associated with. For example, 15.b contains 15 long integers, 15sa.b contains 15 sorted long integers from 15.b. In particular, 15sa.b is created by pa1 by the following command: ./pa1 -a 15.b 15sa.b My implementation of pa1 prints the following output to the screen when the above command is issued: 67 (The count of 67 is based on an implementation that uses insertion sort as the basic sorting algorithm in Shell sort. If we implement Shell sort with bubble sort as the basic sorting algorithm, the count is 80.) My implementation of pa1 prints the following output to the screen when the following command is issued: ./pa1 -l 15.b 15sl.b 104 My implementation of pa1 also created 1Ksa.b and 1Ksl.b. Of course, 15sa.b and 15sl.b are identical and 1Ksa.b and 1Ksl.b are also identical. For the input files 10K.b, 100K.b, and 1M.b, the output files of my implementation of pa1 are not included.Your implementation should not try to match the number of comparisons that my implementation reported. That is not the purpose of the assignment. Getting started: Download all files associated with the assignment from the Brightspace website. As the link to the assignment will disappear after the due date, you would not be able to access any of these files from Brightspace after the deadline. Any updates to these instructions will be announced through Brightspace. Given that the input files are in binary format, you probably want to write some helper functions to print the array of long integers before and after sorting in text (instead of binary) for debugging purpose. Keep in mind that fread and fwrite for binary files are analogous to fscanf and fprintf for text files. You probably want to write and test the load and save functions together because if you call the load and save functions without sorting the array or linked list, the output file should match the input file. The main challenge of this assignment is to perform Shell sort on a linked list. When we perform Shell sort on an array, we do not have to divide the array in sub-arrays. This assignment challenges you to perform Shell sort on a linked list without dividing the list into several sub-lists. This is a rare example when bubble sort is more useful than insertion sort. My suggestion is that you first implement Shell sort of an array using bubble sort as the basic sorting algorithm. It is important that the bubble sort routine terminates early when it detects that an array is sorted. (In the case of Shell sort, the bubble sort should terminate early when it detects that all sub-arrays are sorted.) The following algorithm implements bubble sort on an array of n integers. sorted = false last_exchange = n while (not sorted) sorted = true last_element = last_exchange – 1 for i = 1 to last_element if array[i – 1] > A[i] exchange A[i-1] and A[i] last_exchange = i sorted = false The algorithm employs two techniques to gain some efficiency. It uses a flag sorted to detect sortedness of an array. It also uses last exchange to record the index at which the most recent last exchange occurs. As all elements at and after the last exchange index are already at their correct positions at the end of the for-loop, the next iteration of while-loop should not examine those elements again. Therefore, last element is assigned last exchange – 1. Your Shell sort of an array based on bubble sort should add an outer-loop to account for the sequence. The body of the loop should be very similar to the bubble sort provided above, just like how Shell sort of an array based on insertion sort is developed in class. You probably also want to implement the above bubble sort algorithm on a linked list. Once you have these implementations, you may be able to identify a better connection between Shell sort of an array and Shell sort of a linked list. This assignment is about performing Shell sort. If you implement other sorting algorithms, your submission does not meet the specifications of the assignment, and it will receive a grade of 0.Other than the required output to stdout as specified, do not print other messages to stdout. If you want to print error messages for debugging purposes, use fprintf to print the messages to stderr. If your program produces messages that are not expected, your submission does not meet the specifications of the assignment and it will not earn the relevant credits. We will use valgrind to check for memory issues. While you are most familiar with memory leaks, valgrind can be useful in helping you find the cause of a segmentation fault and identify allocated memory locations that have not been initialized properly. The tool is useful only when you pay attention to all messages that valgrind reports. One useful programming habit is to keep your code valgrind-clean at any stage of programming. In other words, do not leave any memory issues unresolved at any stage of programming. Another good habit to cultivate is to pay attention to the number of memory allocations made by your program. Does the number of memory allocations reported by valgrind match your expectation? For example, I expect my pa1 to make 4 or more allocations for Shell sorting an array, and 18 or more allocations for Shell sorting a list of 15 integers. Why do we need 4 or more allocations and 18 or more allocations, respectively?
Spam Filter Assignment Design a spam filter recipe that will trap 74 messages that you will find in the gzipped tar archive junkMail.tar.gz uploaded on Brightspace along with the assignment. When you gunzip and untar the archive, with say: 1 tar – zxvf junkMail . tar . gz you’ll see 74 individual spam messages with names junkMail 1 through junkMail 74. About these messages: 1. junkMail 1 through junkMail 50: The headers of all these messages have one thing in common: they contain multiple entries in the ”From” header. All these messages were trapped by a single recipe in Prof. Kak’s spam filter. The regex in Prof. Kak’s recipe has only 40 characters in it. 2. junkMail 51 through junkMail 63: These messages can be trapped just on the basis of the “Subject:” line in the email headers. 3. junkMail 64 through junkMail 66: In Prof. Kak’s spam filter, these messages were trapped on basis of the content (email body) of the messages. 4. junkMail 67 through junkMail 74: You need to trap these with a single recipe that contains compound rules. Below is an example of a recipe with compound rules. It is NOT the compound recipe for trapping the messages junkMail 67 through junkMail 74: 1 :0 HB : 2 * ^ Content – Type : text / plain 3 * !^ Content – Type : text / html 4 * !^ content – type : application / pdf 5 * !^ content – type : application / zip 6 * !^ content – type : application / msword 7 * !^ content – type : application /.* signature 8 * Content – Transfer – Encoding : base64 9 junkMailCompound4 1 This recipe says that if the “Content-Type” MIME header is text/plain and none of the MIME objects are of type PDF, ZIP, etc., and yet the “Content-Transfer-Encoding” MIME header calls for Base64 encoding, then there is a great chance it is a spam message. 2 Spam Filter Requirements • You should have a recipe for each of the four groups described above. Design your recipes such that each recipe does not capture junkMail intended for later recipes (e.g. recipe 2 should not capture junkMail 64 through 66) . • While it is hypothetically possible that some earlier junkMail could be caught by later recipes based on their criteria, this should not happen since the emails are processed based on the recipe order. For example, recipe 4 could catch an earlier junkMail based on its criteria, but since that junkMail would already be captured by an earlier recipe, it should not happen. • Each recipe should write the junkMail to one of the following files based on the recipe number: recipe 1, recipe 2, recipe 3, and recipe 4. 3 Useful Notes • After you have incorporated the new recipes in your .procmailrc file, your filter can be tested on an individual message by invoking the command: 1 procmail . procmailrc < junkMail_XX where ”XX” is the integer suffix for the message file. Obviously, you would need to write either a shell script, or a Python script to execute the above command in a loop for all messages. • If your recipes work on all 74 messages that have been sent to you, you will not see any messages being subject to the default action of your procmail filter, which is usually to put the surviving messages in your mailbox /var/mail/account name (this can be viewed with the mailx command). Of course, you should test your recipes with your own messages that shouldn’t be marked as spam (you will need to create your own emails that will specifically avoid the spam criteria 2 for this homework). This way, you can ensure that your recipes allow the desired messages through. • Since the spam message in the tar archive are in their raw form, it is sometimes hard to see what is in them especially if the MIME objects in the message are Base64 encoded. To decipher those spam messages that are fully or partially encoded, you can use Prof. Kak’s Perl script EmailParser2.pl found in Lecture 31. Execute this script (you may need to modify the shebang line based on where perl is installed for you) and give it a command-line argument that is the name of the junk mail file you want to decipher. It will deposit the different MIME objects in the email in a subdirectory called mimemail in the directory in which you execute the script. • If you have trouble using the EmailParser2.pl script, you may want to install the mutt email client on your personal computer to help you read the emails. 4 Submission Instructions • For this homework you will be submitting a zip file titled hw11 .zip, which consists of: – A pdf titled hw11 .pdf containing: ∗ A brief description of how you crafted each recipe – A well commented copy of the .procmailrc file you used to filter the junk mail.
In this assignment, we will explore one of the most prevalent vulnerabilities in software systems – buffer overflows. Buffer overflow attacks remain a significant threat to computer systems, and understanding how they work is crucial for any aspiring cybersecurity professional. The objective of this assignment is to provide you with hands-on experience in identifying, exploiting, and mitigating buffer overflow vulnerabilities. Specifically, you will be tasked with mounting a buffer overflow attack on a socket program. After, the buffer overflow assignment, you will also be tasked with setting up spam filter accounts for next week’s homework assignment. As always, please read the homework document in its entirety before coming to office hours with your questions. The teaching staff have spent a long time writing the assignment to cover many common questions you might have. 2 Buffer Overflow Attack Included with this homework, you will find two socket programs written in C. One of them acts as a server and the other as a client. Your first task is to launch an attack that executes the ”secret” function in the server side code by using the client program to send a carefully crafted string to the server. Following this, your second task is to show how you would fix server.c to prevent such an attack from happening. Listed below are some more details to consider when completing these two tasks. • It is advised that you do this entire assignment on eceprog.ecn.purdue.edu • When compiling the source code with gcc, make sure to include the -fno-stack-protector flag. Refer to pages 36-37 of Lecture 21 for more details. 1 • You will need two terminals to complete this assignment: one terminal for the server and one terminal for the client. Make sure to start the server program before starting the client program • Use gdb to determine how you can develop a string to send (using the client program) to the server program and trigger the execution of secretFunction(). Refer to Lecture 21.6 for more details on how to do this. Some things to consider when crafting the string are: 1. While you send the data with the client program, you will have to run the server program with gdb to determine the buffer overflow string to use. 2. When sending the string to the server program, note that you can send both ASCII characters as well as hexadecimal bytes. You can send, for example, the hex byte 0xAD using the format xAD 3. As in the lecture notes, you will need to reverse the order of addresses sent to deal with the big-endian little-endian conversion problems. • After you have completed crafting your buffer overflow string and triggered the execution of the secret function, modify server.c to remove the buffer overflow vulnerability. Your fix should allow the program to run without the threat of a buffer overflow attack. 3 Spam Filter Account Set-up Next week, we will be doing an assignment involving spam filters. For that assignment, we are providing you temporary ECN accounts on the Shay server. To obtain your credentials for your account, first find ECE404 on Brightspace. Under the ”Grades” section for this class, there are two items of interest, one is your account’s username (titled ”login”) and the other is your account’s password (titled ”Password”). The ”Grade” value for these items indicate the username and password you will use. On Windows, you can use PuTTY to ssh into the account. Alternatively you can ssh into the account using the following syntax on MacOSX and Linux: 1 ssh yourUsername@shay . ecn . purdue . edu 2 Please make sure that you can log into this account. Should you face any trouble, please reach out to Joseph as soon as possible to get the issue resolved. Once you have successfully logged into the account, feel free to change your passworld using the passwd command. For future reference the email address associated with this account is [email protected]. Do not try to log into this account with Microsoft Outlook or ECN webmail. Once you are able to access your account, follow the instructions below to get your account up and fully operational. 1. Unzip the attached tar.gz file that contains a text file named dot procmailrc and a Perl script named GET MESSAGE INDEX 2. Apply the dos2unix command to these files to remove the carriage return characters added after line feed. Do not skip this step as the dot procmailrc file is sensitive to such characters, because it contains regular expressions. 3. Carefully read the comments in the dot procmailrc file and make the necessary changes to Recipes 2 and 3. • Recipe 2 requires that you place the name of your special account in the last line of the recipe • Recipe 3 requires that the string user name in the last line be repalced by your email account at Purdue 4. Rename dot procmailrc to .procmailrc and store it your new account’s home directory (e.g. /home/shay/a/ece404q8). You can invoke sftp or scp to move the file from your local machine to the new account. 5. Create a new directory called Mail at the top level of your new ECN account and place the GET MESSAGE INDEX script in that directory 6. Send a test email message to your new account. You can verify that you recived this test mail if a file titled logfile is created in your Mail directory. 7. The best command-line tool for processing the email recived by your new account is mailx. Do man mailx to see all the options that go with this command. You can even use this command to send messages to others. In my experience, mailx works best when you use SSH to access the account directly (as opposed to using ThinLinc or ECEGrid). 3 8. After your account has become operational, please subscribe to random newsletters, newsgroups, websites… etc. This process will cause spam to be directed to your email addresses in a fairly short time. Include a page worth of logfile contents in your pdf submission. 4 Submission Instructions • For this homework you will be submitting a zip file titled hw10 .zip, which consists of: – A pdf titled hw10 .pdf containing: ∗ the specially-crafted buffer overflow string ∗ an explanation of how you determined the special string ∗ an explanation of your fixes to server.c including screenshots of code snippets that reflect the necessary changes. ∗ A page worth of logfile contents from the Mail directory of your spam accounts – the modified server.c with comments explaining the vulnerability and the fix. – The updated .procmail file References
