Table of Contents

CS 190C: In-Lab Final Exam

Wednesday April 30, 2008

This is an in-lab, open book final exam. The exam contains three types of questions: questions that have a written answer (typed or handwritten), questions for which you have the option to run a program/statements, and questions for which you are required to write and run a program.

You can access all material on the CS 190C course website or reachable from the course website, your notes and textbooks. You can also access other course related reference material you used during the semester. We strongly encourage you to not initiate searches to look for answers as this will cost you valuable time (and you are unlikely to find something useful).

Sending e-mail to a person, visiting someone Facebook page, or engaging in any form of messaging is considered cheating. It would result in an F on the final exam and the case would be forwarded to the departmental academic conduct committee.

Create a directory (“final”) with one file for each problem (“p1.py” or “p1.txt”, for example, for Python code or plain text answers). Submit a zip file of the “final” directory to Blackboard.

Problem 1

(22 pts) Below each comment write a one-line statement achieving the specified action. Do not use iterators. Assume that the statements are executed in the order given.

We suggest you run the commands in the interactive shell and show the list/dictionary after an operation changing it.

    A = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i']
 
    # print elements c to f
 
 
    # print elements up to and including c 
 
 
    # print elements f to the end of the list
 
 
    # remove elements 'e' to 'h' from list A 
 
 
    # create a list B containing 2 copies of every element in A 
 
 
    # change the first element in A to [1,2,3,4]
 
 
    # reverse the elements in list A
 
 
    # sort the elements in list B
 
 
 
    M = [[0,1,2,4], [4,5,6], [], [7,8,9,10]]
 
    # in M, change element having value 6 to -6  
 
 
    # remove the third element in list M
 
 
    # append [0, -1, -2] to list M 
 
 
    # append 12 to the first element in list M
 
 
    BD = {'Molly': 'March 15', 'Lucy': 'July 31', 'Andy': 'May 20'} 
 
    # change Andy's birthday to May 16
 
 
    # add Peter with a December 31 birthday to the dictionary 
 
 
    # print all dates in BD

Problem 2

a) (5 pts) What is the difference between accuracy and precision? Give two examples for which accuracy and precision are different. Explain your examples.

b) (5 pts) Consider computing the harmonic series 1 + 1/2 + 1/3+ … + 1/n + … which diverges. If you were to write a program (with limited precision) that computes this series, which will happen first: (1) numeric overflow (the sum grows greater than the size of the largest integer), (2) numeric underflow (quotient of 1/n computes to zero), or (3) the accumulated sum does not change (due to a lack of precision)? Explain (no need to write a program).

c) (12 pts) Consider the following piece of code.

from pylab import *
 
def f1(x):
     return (x - 1e8) * (x - 1e8)
 
def f2(x):
     return x**2 - 2e8*x + 1e16
 
y1 = []
y2 = []
 
t = arange(1e8-1, 1e8+1, .01)
 
for x in t:
    y1.append(f1(x))
    y2.append(f2(x))
 
subplot(211)
plot(t, y1 ,'ro')
grid(True)
title('f1')
ylim(-2.25,2.25)
 
subplot(212)
plot(t, y2, 'go')
grid(True)
title('f2')
ylim(-2.25,2.25)
 
show()

Explain the graphs generated and why there is a discrepancy. Which function delivers the more accurate values and why?

Problem 3

File problem3_code.py contains a skeleton of a program operating on undirected graphs. It contains a function import_edge_list(path) that creates a graph, reading it from file path (same code was used in project 3).

a) (10 pts) Write a function count_degree(G,d) that returns the number of nodes in G having degree at least d. Recall that the degree of a node is the number of edges incident to the node.

b) (11 pts) Generate a histogram of the degrees of all the nodes in G. The code skeleton suggests using pylab, but you can can use VPython as well.

Place your code as indicated in file problem3_code.py.

Here are some input files: graph0.txt, graph1.txt, graph2.txt

Note: You may want to use https://networkx.lanl.gov/wiki/QuickReference to look up NetworkX operations.

Problem 4

(10 pts) Consider the problems described below and classify each one as

(A) A problem for which an efficient algorithm exists. Efficient means computable in better than exponential time.

(B) A problem for which no algorithm exists or for which the computation time would become unreasonable for reasonably-sized inputs.

Give a brief explanation for each choice made.

  1. Given are n strings of characters, with each string having length k. Determine whether among the n strings there exist two strings s1 and s2 such that s1 is the reversal of s2.
  2. Given a set S of n integers and an integer K, determine whether there exists a subset T of S such that the elements in T sum up to exactly K.
  3. Given an undirected graph G and two nodes u and v, determine whether there exists a path from u to v in G.
  4. Write a program that takes as input two Python programs, A and B, and determines whether A and B are basically the same programs, meaning that A and B have the identical sequence of statements and they have identical spacing. However, programs A and B can have different comments and they may use different variable names.
  5. Write a program that takes as input two Python programs A and B and an input I, and determines whether or not A and B generate the same output on input I.

Problem 5

In project 2, you wrote a recursive function to detect percolation in a 2-d grid. The recursive exploration of the grid recursively explored one path consisting of open sites until the last row of the grid or a dead end was reached. In case of a dead end, recursion managed exploring all possible paths in a systematic way. This question asks you to write a function detecting percolation based on a different principle, that of expanding wavefronts.

We briefly review relevant material from Project 2. The 2-dimensional grid is represented as a list of lists with [0][0] being the upper left-most position of the grid. A location in grid input_grid is set to 0 if the corresponding site is open, permitting flow, and it is set to 1 if the site is blocked. The goal is to detect unrestricted percolation in input_grid. Recall that for unrestricted percolation grid input_grid percolates if there exists a path of horizontally or vertically adjacent 0's from any location in the top row to any location in the bottom row.

We provide a framework for wavefront percolation detection in problem5_code.py. Note that a grid is read using function readgrid and all visualization is provided. Percolation detection is done by function wave_percolation and it proceeds in waves: the first wave consists of all the open positions in the top row of the grid. The second wave consists of all positions not in the first wave and that can be reached in one step from a position in the first wave. In general, the i-th wave is generated using the (i-1)-st wave and it contains positions not reached earlier. Note that if a position appears in wave i, there is a path of length i to this position from a location in the top row. Waves are numbered starting from zero. Hence, the wave algorithm can be used to not only detect whether the grid percolates, but it also finds the shortest percolation path. The figure below shows the progression of the wavefront percolation algorithm on an example grid.

Example of wavefront percolation

Function wave_percolation uses a grid flow_grid to record the position reached by the waves during all iterations (its entries are initialized to -1) and uses a list wave to record the current wave. All visualization done is provided. Note that once a new wave has been determined, the positions reached by wave from i are recorded in the grid visualized. Function wave_percolation calls function nextwave to generate the next wave. The inputs to nextwave are

  1. input_grid: input_grid[i][j] is 1 if position (i, j) is blocked.
  2. flow_grid: flow_grid[i][j] is -1 if position (i, j) has not been visited by a wave; it contains the value i if the i-th wave reached it.
  3. last_wave: a list of (row, col) pairs indicating the grid positions that were in the last wave.

Function nextwave returns the next wave that contains all positions that

a) (5 pts) The figure below shows a wavefront percolation in progress. Label the positions the wave_percolation algorithm would label 4. You can mark up the hard copy you have or give the coordinates of the positions marked 4 in flow_grid.

Mark the spaces that would be labeled '4'

b) (20 pts) Complete function nextwave in file problem5_code.py. Make sure to explain your approach in the comment part of the function as this will allow you to get partial credit for a correct idea.

Here are some input files for testing your code: grid00.txt, grid01.txt, grid02.txt, grid03.txt.