CS 111
Spring 2018

Old version

This is the CS 111 site as it appeared on May 10, 2018.

Midterm 2 Information

Material covered

The exam will focus on the topics covered in lecture from the material on gates and circuits up to and including the material on references. The use of the stack and recursion in the context of assembly language will not be included on the exam.

Remember that you can access all of the relevant pre-lecture videos and lecture notes in the Lectures section of the course’s Blackboard site.

Exam details

Preparing for the exam

Additional practice problems

Solutions to these problems will be posted under Other Content on Blackboard as we get closer to the exam.

  1. Write the complete truth table for the boolean function XYZ + XYZ.

  2. Given the following truth table, perform the minterm expansion for the function f. Don’t simplify! 

    x  y   f(x,y)
-------------
0  0      1
0  1      0
1  0      1
1  1      0

  3. Design the circuit for the function from the previous problem.

  4. Add the following two binary numbers:

       1 1 0 1
 1 0 1 1 1
----------

  5. Multiply the following two binary numbers:

       1 0 1 1
 1 1 1 0 1
----------

  6. Design a truth table, minterm formula, and circuit that will implement a 2-bit greater-than function. Your function should take 4 bits of input, x1, x0, y1 and y0, and produce a true output if and only if the two-bit number x1x0 is greater than the two-bit number y1y0.

  7. Write a Hmmm assembly-language program that gets two positive integers from the user, subtracts the second integer from the first, and writes out the square of the result.

  8. Write a Hmmm assembly-language program that uses a loop that allows the user to enter one or more integers. When the user enters a zero, the program should stop looping and write out two counts: how many of the numbers were positive, and how many were negative. Don’t count the zero.

  9. Write a Hmmm assembly language program that takes in a positive integer as input and calls a separate function that many times. The function should simply write out the number 111. You must use call and jumpr instructions to implement your function.

  10. Write a Python function years_needed that takes three inputs:

    • principal, which is the initial amount of money deposited in an interest-bearing account
    • rate, which is the annual interest rate in decimal form
    • target, which is the final value that the investor wants to reach

    The function should use a loop to determine the number of years of compounded annual interest that are needed for the investment to reach or exceed the specified target. Note: After each year, the new principal is computed as

    principal = principal * (1 + rate)

  11. Write a Python function find(ch, s) that returns the index of the first occurrence of a character ch in a string s, or −1 if the character is not found. You may assume that ch is a single character. Use a loop.

  12. Write a Python function count_vowels(s) that counts and returns the number of vowels in a string. Use a loop.

  13. Write a Python function stars(n) where n is a positive integer. It should print n lines of stars with 1 star on first line, 2 stars on second line, and so forth. For example, stars(4) should print

    *
**
***
****

    Use nested loops. You are not allowed to use the * operator (*). You should use print('*', end= '') to print a single asterisk at a time while remaining on the same line, and an empty print() to go down to the next line.

  14. Write a function all_perfect(lst) that takes a list of numbers lst and returns True if all of the numbers are 100 and False otherwise. Use a loop.

  15. Write a function index_nearest(n, lst) that takes a number n and a list of numbers lst and returns the index of the element in lst whose value is closest to n. Use one or more loops.

  16. A two-part problem:

    • First, write a function num_appearances(substring, s) that returns the number of appearances of the specified substring (which you may assume is of length 2) in the string s. Hint: Use an index-based loop.

    • Next, write a function most_common_pair(s) that returns the two-character string in s that appears most often as a substring within s. For example, most_common_pair('alphabetical') should return al. Ties may be broken arbitrarily. Hint: Use num_appearances as a helper function. In addition, most_common_pair will need its own index-based loop.

  17. Optional challenge: Write a function longest_dna(s) that takes a string s and returns the longest substring that consists only of the characters ‘A’, ‘C’, ‘G’, and ‘T’. For example,

    longest_dna('ACCGXXCXXGTTACTGGGCXTTGT')

    should return 'GTTACTGGGC'. Ties may be broken arbitrarily.

  18. What is printed by the following Python program?

    def loopy(x, y):
    print('starting loopy:', x, y)
    while x < y:
        x += 1
        y -= 2
    print('after loop:', x, y)
    return x

x = 1
y = 8
y = loopy(x, y)
print('after first call:', x, y)
loopy(y, x)
print('after second call:', x, y)

    Hint: Use two different tables – one for the global scope and one for loopy – to keep track of the values of the variables.

  19. Draw one or more memory diagram like the ones we have used in lecture to illustrate the execution of the following Python program:

    a = [1, 2, 3, 4]
b = a
a[3] = 5
b[1] = 7
print('a is', a)
print('b is', b)

    In addition, write a few sentences that refer to your diagram(s) and that explain the result of the program.

  20. Draw memory diagrams that demonstrate why we get different results from the following two Python programs:

    ### Program 1 ###
def foo(a):
    a = 2 * a
    return

b = [1, 2, 3]
for i in range(len(b)):
    foo(b[i])

print('b is', b)

### Program 2 ###
def bar(lst, i):
    lst[i] = 2 * lst[i]
    return

b = [1, 2, 3]
for i in range(len(b)):
    bar(b, i)

print('b is', b)

    In addition, write a few sentences that refer to your diagrams and that explain the difference in output.