Midterm Exam

Spring 2020

The questions below are due on Friday April 10, 2020; 11:59:00 PM.
 
You are not logged in.

If you are a current student, please Log In for full access to the web site.
Note that this link will take you to an external site (https://shimmer.csail.mit.edu) to authenticate, and then you will be redirected back to this page.
A Python Error Occurred:

Error on line 19 of Python tag (line 20 of source):
    kerberos = cs_user_info['username']

KeyError: 'username'

This is your midterm exam. It is due at 11:59PM EDT on Friday April 10, 2020. This exam is open notes and open internet, though you are not to use a C/C++ compiler or Python evaluator. You are also not to communicate with anybody else during the exam except for staff members. You are not to copy or transfer any of the content of this exam off of the web page.

A Python Error Occurred:

Error on line 5 of question tag.
    csq_soln = kerberos

NameError: name 'kerberos' is not defined

If you have a question, post a private question in piazza.

1)

The array a is declared and defined as shown:

char a[37] = "cats and dogs.";

A Python Error Occurred:

Error on line 10 of question tag.
    csq_msg_function = what_was_submitted

NameError: name 'what_was_submitted' is not defined

A Python Error Occurred:

Error on line 10 of question tag.
    csq_msg_function = what_was_submitted

NameError: name 'what_was_submitted' is not defined

A Python Error Occurred:

Error on line 11 of question tag.
    csq_msg_function = what_was_submitted

NameError: name 'what_was_submitted' is not defined

Consider the following code:

int vowels(const char* str){
  int tally = 0;
  int i = 0;
  while(str[i]!='\0'){
    if (CONDITION){
      tally++;
    }
    i++;
  }
  return tally;
}

We want the following function to return the number of lower-case vowels ('a', 'e', 'i', 'o', 'u') (ignore 'y') in a string str, what would a valid CONDITION to check be to exhibit this behavior?

A Python Error Occurred:

Error on line 10 of question tag.
    csq_msg_function = what_was_submitted

NameError: name 'what_was_submitted' is not defined

Consider the situation where we rewrite the function above to instead be the following:

int vowels(char* str){
  int tally = 0;
  char* letters = str;
  while(CONDITION_1){
    if (CONDITION_2){
      tally++;
    }
    OPERATION_1;
  }
  return tally;
}

If we still want the function to return the number of lower-case vowels, what should CONDITION_1, CONDITION_2, and OPERATION_1 be?

From the options provided below, choose a consistent set of answers for what should go into CONDITION_1, CONDITION_2, and OPERATION_1:

A Python Error Occurred:

Error on line 10 of question tag.
    csq_check_function = list_checker_mc

NameError: name 'list_checker_mc' is not defined

A Python Error Occurred:

Error on line 9 of question tag.
    csq_check_function = list_checker_mc

NameError: name 'list_checker_mc' is not defined

Choose a replacement for OPERATION_1
letters--;
*letters--;
letters++;
letters = +1;
(*letters)++;

2)

Consider the circuit below:

Placeholder for Diagram 8e468c9155360e0a802f426bf9502110
A circuit comprised of unknown elements DA, DB, DC, and DD as well as two resistors.

What is the magnitude of the current flowing through the 8.9Ω resistor?
1.950A
0.117A
0.126A
0.090A
0.063A

What is the power consumed by component DC
1.489W
0.320W
0.410W
1.353W
0.902W
None of the above

Assume that component DA is providing power to the system and component DB is a linear regulator. What is the efficiency of the system (where we consider power consumed by components DC, DD, and both resistors as "useful")?
63.71%
69.23%
66.55%
34.62%
17.31%
None of the above

3)

Consider the following circuit:

When pin IO5 is set to 3.3V, the current through the LED is 42 mA. How much power does the LED consume in this state?

How much power does the LED consume in the state described above?
0.13 W
0.0127 W
0.4 W
0.1386 W
138.6 W
None of the above

The system shown in the schematic above can operate in two modes:

  • In Mode 1 ("Wake Mode"), the LED is driven at a PWM frequency of 120Hz and a duty cycle of 75%
  • In Mode 2 ("Sleep Mode"), the LED is driven at a PWM frequency of 500 Hz and a duty cycle of 10%

In both Mode 1 and Mode 2, the ESP32 consumes 14 mA at 3.3V. Assume the entire system is powered by an ideal 3.3V battery with capacity 2.90 Amp\cdothours. How long will the entire system last when in Mode 1?

How long will the entire system last when in Mode 1?
159.34 hours
63.74 hours
81.23 hours
690.48 hours
92.06 hours
None of the above

How long will the entire system last when in Mode 2?
690.48 hours
81.23 hours
159.34 hours
63.74 hours
92.06 hours
None of the above

Assume the system can switch between Mode 1 and Mode 2. We would like the system to operate in a periodic fashion toggling between Modes 1 and 2 repeatedly. If we're required to periodically flash the LED (operate in Mode 1) for a duration of 1 minute, how long must the time spent in Mode 2 per period be in order for the system to last 124 hours with the battery given above?

How long must the the time spent in Mode 2 per period be for the system to last 124 hours?
6.26 minutes
5.26 minutes
4.26 minutes
8.26 minutes
7.26 minutes
7.58 minutes
None of the above

4)

How many bytes are there in a uint32_t typed variable?
4
5
2
1
None of the above

If a device's memory is comprised of 535,000 bytes, what is the minimum number of bits required by a pointer variable to fully describe each byte in the memory space?
20
1
18
21
9
24
22
None of the above

If I want to store 15 seconds of a signal in 60,000 byte memory at 6,000 samples/sec, what is the maximum bit depth possible for the measurements? (you can assume no restrictions in how you use the individual bits of a byte)
7
5
13
4
6
None of the above

In a quiet room, suppose you have a microphone that has a DC Offset of 2.0V going into a 16-bit Analog to Digital converter with an analog range of 0 to 3.3 V. What would the analog reading be?
4097
465
39618
39818
1247
1024
39718

5)

Assume you have a difference equation of the form:

y[n] = y[n-1] - x[n]

Below is an implementation of the above difference equation in C/C++.

float old_y;

void diff_eq(float x, float* y){
  CODE_0;
  CODE_1;
}

We'd like to be able to "step" through this difference equation, providing the input x to it, and getting its output returned to us via the variable y. An example usage would look like the following (where we provide the sequence of inputs [1,2,3] and store the first three outputs in variables y_0, y_1, and y_2):

  float y_0,y_1,y_2;
  diff_eq(1,&y_0);
  diff_eq(2,&y_1);
  diff_eq(3,&y_2);

Answer the following questions about what should go into CODE_0 and CODE_1.

What should be put in place in CODE_0?
*y=*y-x
*y=old_y-x
y=old_y-x
*y=old_y

What should be put in place in CODE_1?
old_y=*y-x
old_y=*y
old_y=y
old_y=0

6)

Consider the difference equation:

y[n] = 0.6y[n-1] + 24.0x[n]-3.0x[n-2]

We want to implement this difference equation on the server so that we can POST input values to it and get output values as a response. This difference equation uses past information so it must be stateful and use a database. A functioning implementation is shown below (minus the code you need to insert).

import sqlite3
import datetime

de_db = "__HOME__/midterm/de.db" # just come up with name of database

def request_handler(request):
    x_n = float(request['form']['x'])
    conn = sqlite3.connect(de_db)
    c = conn.cursor()
    c.execute('''CREATE TABLE IF NOT EXISTS diffeq_table (timing timestamp,y_n real,x_n real,x_n1 real, x_n2 real);''')
    state = c.execute('''SELECT * FROM diffeq_table ORDER BY timing DESC;''').fetchone()
    if state==None:#first call/initialize history to zero
      new_y = 0.6*0 + 24.0*x_n -3.0*0
      c.execute('''INSERT INTO diffeq_table VALUES (?,?,?,?,?);''',(DB_TERMS_0))
    else:
      y_n1 = state[1]
      x_n2 = state[3]
      new_y = 0.6*y_n1 + 24.0*x_n - 3.0*x_n2
      c.execute('''INSERT INTO diffeq_table VALUES (?,?,?,?,?);''',(DB_TERMS_1))
    conn.commit()
    conn.close()
    return new_y

We direct a POST request up to the API as shown below:

POST /sandbox/sc/<div><font color='red'><b>A Python Error Occurred:</b><p>
Error on line 1 of Python tag (line 605 of source):
    print('%s' % (kerberos,))

NameError: name 'kerberos' is not defined
<p></font></div>/midterm/de.py HTTP/1.1 Host: 608dev-2.net Content-Type: application/x-www-form-urlencoded Content-Length: 5 BODY

What should BODY be if we'd like to provide an input value of 1.9 to the system?
x=1.9
x=2.9
a=1.9
c=0.9
None of the above

What should be put in place in DB_TERMS_0?
new_y,x_n,0,0
datetime.datetime.now(),new_y,x_n,0,0
datetime.datetime.now(),new_y,x_n,new_y,x_n
datetime.datetime.now(),new_y,0,0,0

A Python Error Occurred:

Error on line 9 of question tag.
    csq_check_function = list_checker_mc

NameError: name 'list_checker_mc' is not defined

7)

You're building a washer-dryer system for your dorm that accepts bitcoin. The volatility of bitcoin, however makes this a risky venture since a fixed price cost in bitcoin could correspond to 15 USD one day and 1.50 USD another. As a result, you decide to have the washer/dryer contact the 608dev-2.net server, which in turn accesses the following open API that provides current cryptocurrency prices. In particular the following GET request:

https://api.coinlore.net/api/ticker/?id=90

...will yield the following response, which is updated relatively frequently:

[
  {
    "id": "90",
    "symbol": "BTC",
    "name": "Bitcoin",
    "nameid": "bitcoin",
    "rank": 1,
    "price_usd": "6712.10",
    "percent_change_24h": "5.80",
    "percent_change_1h": "-1.21",
    "percent_change_7d": "1.73",
    "market_cap_usd": "122704985316.41",
    "volume24": "36890745769.31",
    "volume24_native": "5496154.76",
    "csupply": "18281159.00",
    "price_btc": "1.00",
    "tsupply": "18281159",
    "msupply": "21000000"
  }
]

You write a script to live on the server which accepts a query argument of action specifying whether it is a "wash" (cost: 2.50 USD) or "dry" (cost 1.50 USD). The script then returns a string stating how much the requested action will cost in bitcoins (to six significant figures). For example, requesting a wash should result in:

The cost for a wash is 0.XXXXXX bitcoin.
import requests

def request_handler(request):
  if request['method']=='GET':
    if 'action' in request['args']:
      bci = requests.get("https://api.coinlore.net/api/ticker/?id=90").json()
      if request['values']['action']=='wash':
        cost_in_usd = 2.5
      elif request['values']['action']=='dry':
        cost_in_usd = 1.5
      cost_in_btc = CALCULATION_0
      return STRING
      else:
        return -1

Choose a set of answers below for CALCULATION_0 and STRING that will enable the server script above to behave as required.

What should CALCULATION_0 be?
cost_in_usd/float(bci[1]['price_usd'])
cost_in_usd*bci[0]['price_usd']
float(bci[0]['price_usd'])/cost_in_usd
cost_in_usd/float(bci[0]['price_usd'])
cost_in_usd*float(bci[0]['price_usd'])

What should STRING be?
"The cost for a {} is {:.6f} bitcoin.".format(choice,cost_in_btc)
"The cost for a {} is {:.6f} bitcoin.".format(request['values']['action'],cost_in_btc)
"The cost for a {} is {:.6f} bitcoin.".format(cost_in_btc,request['values']['action'])
"Bitcoin is risky."
"The cost for a {} is {:.6f} bitcoin.".format(request['values']['action'],cost_in_usd)
None of the above

8)

Your ESP32 makes a resquest to an API which returns an image to draw on its display. This image is conveyed in a response that is 20,480 characters long (one for each pixel on the 128 by 160 display). This information is held in a one-dimensional char array called map which is stored as a global variable. In the char array, a '1' represents a black pixel and a '0' represents a white pixel. Pixels are stored in map in order the order that they'll appear on the screen starting in the top left and going as if you were reading an English book (left-to-right, top-to-bottom). (for example, the upper left pixel will be at index 0, the upper right pixel will be at index 127, and the lower right pixel will be at index 20,479).

The code below is intended to draw the map on the screen, but there are two unfinished lines. Choose what goes there in the questions below.

//For reference:
void drawPixel(uint16_t x, uint16_t y, uint16_t color);. //draws single pixel of specified color at location x,y.
const uint16_t SCREEN_WIDTH = 128;
const uint16_t SCREEN_HEIGHT = 160;

int extract_pixel(uint16_t x, uint16_t y){
  int index = CODE_0
  if(CODE_1){
    return TFT_BLACK;
  }else{
    return TFT_WHITE;
  }
}

void draw_map(){
  for (int y=0; y<SCREEN_HEIGHT; y++){
    for(int x=0; x<SCREEN_WIDTH; x++){
      tft.drawPixel(x,y,extract_pixel(x,y));
    }
  }
}

Choose a replacement for CODE_0
x*SCREEN_HEIGHT+y*SCREEN_WIDTH;
x*SCREEN_WIDTH+y;
x+y*SCREEN_WIDTH;
x+SCREEN_HEIGHT*y;
x*SCREEN_HEIGHT+y;
None of the Above

Choose a replacement for CODE_1
map[index]=0
map[index]==0
map[index]=1
map[index]=='1'
map[index]==1

9)

We would like to encrypt the map images sent down to the ESP32 using a Base-2 Caesar Cipher. As mentioned above, messages can be comprised only of the characters 0 and 1. As a result, the full set of non-redundant shifts is also limited to either 0 or 1. A 101 encrypted with a 0 would be 101, for example and would be 010 when encrypted with a 1.

If the original message is 1101011110, what is the encrypted message if the shift is 0.
0010111110
1101011110
1101000001
0010100001
None of the Above

If the original message is 1101011110, what is the encrypted message if the shift is 1.
0010111110
0010100001
1101011110
1101000001
None of the Above

Now consider a Base-2 Vigenere Cipher applied to our map messages. A keyword, comprised of the characters 1 and 0 is used to both encrypt and decrypt a message an n-long word comprised of 1's and 0's.

Let's assume that a portion of one of the maps sent down was 00000100010010000001. What will the encrypted form of this map be if the key is 0011?

00000100010010000001
00101000000000101000
00011011001100011011
00110111011110110010
None of the Above

Let's assume an encrypted portion of a map is received: 00011011001100011011 that was encoded with key 0011. What is the original unencrpyted form of the message?

00000100010010000001
00110111011110110010
00011011001100011011
00101000000000101000
None of the Above

10)

Continuing from Part 8 above, after the map is correctly drawn, a player is positioned on the screen. For example, a map might look like the following with a player pixel drawn in red.

An example map with a player pixel drawn in red

We can assume that every shape drawn on the screen is continuous and closed. We can also assume that no shape goes off the screen and no shapes every overlap or touch.

We'd like to know if a "player", represented by a red pixel at location p_x and p_y is within any shapes drawn on the screen. Ideally it'd be great to use the same sort of logic from Lab 04A, but unfortunately, from the perspective of the ESP32, we don't have a list of points to describe the shapes on the screen, instead only having access to the pixel values in the map character array.

The "Crossings Test" from Lab 04A. Unfortunately our Python implementation won't work here.

To solve this problem, your team comes up with a slightly modified version of the algorithm:

  • Analyze the pixel where the player is at
  • Move right one pixel at a time, analyzing each pixel
  • Keep track of when edges are crossed in the image, tallying the number of times an edge is crossed.
  • Do this until the right edge of the screen is reached. Use the number of crossed edges to determine if the player is inside or outside a shape.

As a first draft, your team designs an FSM help with this task. A diagram of this FSM is shown below, with its state transitions based solely on the input value of pixel.

Placeholder for Diagram 4c5cb0450c76cd5d7d163e9e0b7939da
State Machine Diagram for FSM0

The FSM returns a value indicating if a line has been crossed on a given timestep. This behavior is stateful and is described by the table below:

A description of the outputs of the FSM as a function of state and input

Study the diagram and table above and look at how it is deployed in the code below:

uint16_t state;

int fsm_0(uin16_t pixel){
  switch (state){
    case 0:
      if (pixel==TFT_BLACK){
        state = 1;
      }
      return 0;
    case 1: 
      if (pixel==TFT_WHITE){
        state = 0;
        return 1;
      }
      return 0;
    default:
      return 0;
  }
}

//Function below should return true if point inside shape, otherwise false:
uint8_t in_or_out(uint8_t p_x, uint8_t p_y){
  int tally = 0;
  for (uint8_t x = p_x; x<SCREEN_WIDTH; x++){
    tally +=fsm_0(extract_pixel(x,p_y));
  }
  return tally%2;
}

When is the line-crossing tally incremented?
When it goes from white to black
When it goes from black to white
When the last two pixels have been black
When the current pixel is black
None of the Above

Shown below is a graphical depiction of the first ten pixels checked on a call to in_or_out from above in one region of a particular map.

Ten-step scanning

Answer the following questions about the system operation:

For the first ten iterations through the for loop in in_or_out, what are the values of state at the end of each iteration through the loop?
[0, 0, 0, 0, 1, 0, 1, 0, 0, 0]
[0, 0, 0, 1, 1, 1, 1, 0, 0, 0]
[0, 1, 1, 0, 1, 1, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 1, 0, 0, 0, 0]
[1, 0, 1, 0, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 1, 1, 0, 0, 0, 0]

For the first ten iterations through the for loop in in_or_out, what are the output values of the fsm during each iteration through the loop?
[0, 0, 0, 0, 1, 0, 1, 0, 0, 0]
[0, 0, 0, 1, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 1, 1, 1, 0, 0, 0, 0]
[1, 0, 1, 0, 1, 0, 0, 0, 0, 0]
[0, 1, 1, 0, 1, 1, 0, 0, 0, 0]
[0, 0, 1, 0, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 1, 1, 1, 0, 0, 0]

For the first ten iterations through the for loop in in_or_out, what are the values of tally at the end of each iteration through the loop?
[0, 0, 0, 1, 1, 1, 0, 0, 0, 0]
[0, 0, 1, 1, 2, 2, 2, 2, 2, 2]
[0, 0, 0, 1, 2, 2, 2, 2, 2, 2]
[0, 0, 0, 0, 1, 1, 2, 2, 2, 2]
[0, 0, 0, 1, 0, 2, 0, 0, 0, 0]
[0, 0, 0, 1, 1, 1, 1, 0, 0, 0]