ECS 32B – Introduction to Data Structures
Homework 04
Due: Friday, May 14, 2020, 5:00pm PST
Important:
• You may upload as many times as you want before the deadline. Each time the autograder will let
you know how many of the test cases you have passed/failed. To prevent people from manipulating
the autogader, the content of some test cases are hidden.
• Please do not copy others’ answers. Autograder can detect similar code.
Problem 1 (5 points)
For Problem 2 in Homework 03, the recursive version of transform can be written as:
1 def transformRecursive ( lst ) :
2 if not lst :
3 return []
4 return [ lst . val ] + transformRecursive ( lst . next )
Let head be the head of the linked list 10 → 6 → 3 → 13 → 2. Visualize the call transformRecursive(head)
using
• the activation stack model; and
• the substitution model.
(Please follow the definiton of transformRecursive above instead of your own version in homework 03.)
Problem 2 (5 points)
For Problem 3 in Homework 03, the recursive version of concatenate can be written as:
1 def concatenateRecursive ( lst1 , lst2 ) :
2 return concatenateRecursive_helper ( lst1 , lst2 , lst1 )
3
4 def concatenateRecursive_helper ( lst1 , lst2 , cur ) :
5 if not lst1 :
6 return lst2
7 if not cur . next :
8 cur . next = lst2
9 return lst1
10 return concatenateRecursive_helper ( lst1 , lst2 , cur . next )
1
Let head1 be the head of the linked list 8 → 20 → 4 → 5 → 10, and head2 the head of the linked list
7 → 2 → 3. Visualize the call concatenateRecursive(head1, head2) using
• the activation stack model; and
• the substitution model.
(Please follow the definiton of concatenateRecursive above instead of your own version in homework 03.)
Problem 3 (28 points)
1. (8 points) Suppose we have a hash table of size 29 and we want to implement a system for looking
up a friend’s information given his/her name. Which of the following hash functions is the best
(none of them is perfect)? Justify your choice. (Assuming none of the names is empty.)
(a) h(x) = x
(b) h(x) = len(x) % 29
(c) h(x) = 29
(d) h(x) =
len(x)
∑
i=0
ord(x[i]), where x[i] the ith character in x, and ord(c) returns the ordinal value of a
character. (Instruction on the Σ summation symbol https://www.mathsisfun.com/algebra/
sigma-notation.html)
2. (4 points each) Given a hash table with size 7, a hash function hash(x) = x % 7, and keys 5, 7, 14, 1,
19, 21.
(a) Hash the keys using chaining to resolve collisions. Show your work.
(b) Hash the keys using linear probing to resolve collisions. Show your work.
(c) Hash the keys using quadratic probing to resolve collisions. Show your work.
(d) Hash the keys using double hashing to resolve collisions. Suppose the second hash function
hash0
(x) = 3 − (x % 3). Show your work.
(e) What is the load factor after the keys are hashed?
Problem 4 (23 points)
Download the “run_sort.py“, “num1.txt“, “num2.txt“, and “num_sorted.txt“ files from Canvas → Files
→ Homework → Homework 04.
The “run_sort.py“ file contains code to import data from “num1.txt“ into a Python list, run Bubble sort
on the Python list for 10 times, record the start and end time, and calculate how long it takes to run. You
may run the file in your IDE directly. It might take a couple of minutes to run. Record the time it takes
to run in Column 1, Row 1 in the table below.
Then replace “num1.txt“ by “num2.txt“ and “num_sorted.txt“ and fill in the rest of row 1 in the table.
“num1.txt“ and “num2.txt“ contain a large amount of unsorted data, and “num_sorted.txt“ contains
sorted data.
2
Replace the Bubble sort function by each of the sorting algorithms we have learned (use the code in the
lecture slides, not the textbook), run the sorting algorithms on all the three text files one by one, and fill
in the rest of the table. Also write what you think about the following questions:
• Which combination of sorting algorithm and data file runs fast and why?
• Which combination of sorting algorithm and data file runs slowest and why?
The functions for merge sort and quick sort are recursive. You will notice that Python throws a RecursionError,
saying maximum recursion depth exceeded in comparison. To allow more recursion calls, you
may add
1 import sys
2 sys . setrecursionlimit (20000)
at the top.
Sorting Algorithm num1.txt num2.txt num_sorted.txt
Bubble sort
Short Bubble
Selection sort
Insertion sort
Merge sort
Quick sort
Problem 5
Given a sorted (in ascending order) Python list of distinct integers, return all the indices i such that the
elements at index i equals i. There may be more than one such index, so the return type is a Python list
containing all indices that satisfy the criteria.
Write two functions for the same problem. The first function, linearSearchValueIndexEqual, uses linear
search, and the second function, binarySearchValueIndexEqual, uses binary search. The test cases for the
two functions in Gradescope are the same.
When the input list is empty, return an empty list.
Examples:
• Input: [0, 2, 5, 7]
Output: [0]
Explanation: The element at index 0 is 0, so the value equals its index.
• Input: [-5, 1, 2]
Output: [1, 2]
Explanation: The element at index 1 is 1, and the element at index 2 is 2.
Problem 6
Suppose you need to write an anonymous letter and disguise your handwriting. You decide to cut
the characters you need from a book and paste the characters on a paper to form the letter. (Note that
3
we mean a physical book and a physical letter, not digital.) Given the content of a book book and the
content of the letter letter (each is reprented as a string), write a function anonymousLetter(book, letter)
that determines if it is possible to write the anonymous letter using the book.
Note:
• Your algorithm must use hashing (or dictionary in Python).
• The time complexity is O(max(m, n)), where m is the length of the book string and n is the length
of the letter.
Examples:
• Let the book be “I am a book. Not a letter.” and the letter be “I am a letter.”
anonymousLetter(book, letter) should return True.
• Let the book be “I am a book. Not a letter.” and the letter be “I am a letter!”
anonymousLetter(book, letter) should return False.
• Let the book be “abcde” and the letter be “abcdef”
anonymousLetter(book, letter) should return False.