代写ECS 32B程序、代做Data Structures编程、Python语言程序代写

日期：2021-05-15 11:08

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.

4