ECS 32B – Introduction to Data Structures

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 testcases you have passed/failed. To prevent people from manipulating the autogader, the content of only half of the testcases are visible.

•  Please do not copy others’ answers. Autograder can detect similar code.

•  Additionally, consider that the course staff have looked up solutions to the problems, so your TAs know what the internet solutions look like, pleasedon’t just copy paste.

Problem 1 (13 points)

Write a recursive function called smallest that given a non-empty Python list, returns the smallest element in the list. Thinking recursively, the smallest integer is either the first integer in the list or the smallest integer in the rest of the list, whichever is smaller. If the list has only one integer, then the smallest integer is this single value.

Examples:

•  Input: [5, 9, 2, 4] Output: 2

•  Input: [5, 9, 4, 4] Output: 4

(Helpful Python syntax: If A is a

list of integers, and you want to

set the list B to all of the

integers in A except the first

one,you can write B = A[1:])

Problem 2 (50 points)

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 testcases 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.