Introduction to Computer Science

Quiz 5 Study Guide

This page contains a list of things you should know before taking Quiz 5. If you have any questions as to the correct answers to any of these questions, please let me know.

Files

Recent labs have made thorough use of files. You should know how to open and close a file, how to retrieve its contents, and how to work with strings.

Exercises

Write the following Python functions. Attempt to do so without the aid of a computer whenever possible.

• A function which opens a file Comments.txt and returns the number of lines in that file.
• A function which opens a file Comments.txt and displays any line in that file containing the text Total Score.
• A function which opens the twitter-data.txt file from Lab 08 and returns the largest number of retweets that any tweet received.
• A function which opens a file (the name of which is specified in a parameter) and returns the number of lines on which a word (also specified as a parameter) appears.

Searching

We spent a week discussing the process of searching through a list in class. You should know linear and binary search algorithms and be able to write them as Python code. You should be able to explain the advantages and disadvantages of each. You should understand these algorithms well enough to debug them.

Exercises

Answer the following questions.

• What is the runtime complexity (in big-O notation) of linear search? Binary search?
• What do you need to know about a list in order to perform a linear search on it? What do you need for binary search?

Write the following Python functions. Attempt to do so without the aid of a computer whenever possible.

• A function which performs a linear search on a list.
• A function which perofrms a binary search on a list.
• A function which determines whether a list is sorted.

Sorting

We spent a week discussing the process of sorting a list of values. Lab 08 required you to sort a data file. You should know at least the Selection Sort and Bubble Sort algorithms and be able to write them as Python code. (Ideally, you should also understand Insertion Sort.) You should understand these algorithms well enough to debug them.

Exercises

Complete the following tasks.

• Write the algorithm for Selection Sort.
• Write the algorithm for Bubble Sort.
• Write an implementation of Selection Sort as three different functions: a swap function, a find_smallest_from function (which locates the smallest element in a list starting from a particular index), and a selection_sort function (which performs the complete sort.
• Write an implementation of Bubble Sort as three different functions: a swap function, a bubble function (which runs through the list once), and a bubble_sort function (which performs the complete sort).
• The following implementation of Bubble Sort contains two bugs. Identify them and explain how to correct them.

def swap(lst,i,j):
  temp = lst[i]
  lst[j] = lst[i]
  lst[i] = lst[j]

def bubble(lst):
  for i in range(len(lst)-1):
    if lst[i] < lst[i+1]:
    swap(lst,i,i+1)
    
def bubble_sort(lst):
  for i in range(len(lst)):
    bubble(lst)