15-112 Fundamentals of Programming

For this homework, there is no starter file. You have to create your own .py file and submit it to Autolab. You can take a previous starter file and modify it appropriately.

Please add your name, Andrew id, and section at the top of the file.

Write test functions for each function you write.

APPLY TOP-DOWN DESIGN, USE LOTS OF HELPER FUNCTIONS.

IMPORTANT: All the code above the #ignore_rest line is autograded, and all the code below it is ignored. Make sure you put all test functions below #ignore_rest.

From now on you will be graded on style. For this homework, however, style deductions are half-weighted, so the maximum number of points you can lose on style is 5 (out of 100). Please see here for the style rubric.

You may not use recursion, sets, dictionaries or any other constructs that we have not yet covered in class.

You will have 4 submissions on Autolab for this homework.

Questions

1. The 15-112 CAs need your help. Each CA has an alphabetically ordered list of the students in their section. However, we would like to get one ordered list that contains all the students in all sections. Write a function called combine(L1, L2) that takes two sorted lists as input, combines all the elements in the two lists into one sorted list, and then returns that list. For example, if L1 = ["Alice", "Bob", "Charlie", "Eve"] and L2 = ["Adam", "Chloe", "David"], then the returned list would be ["Adam", "Alice", "Bob", "Charlie", "Chloe", "David", "Eve"]. You can assume that the lists contain only strings and no other type of data. However, a list can potentially be empty.
   
   For this question, you are not allowed to use any built-in list methods other than append, and you are not allowed to use the sorted function. Furthermore, the efficiency of your program is important. In particular, you are not allowed to concatenate the two lists with the + operator and then sort the resulting list. This is not the most efficient solution and does not make use of the fact that the input lists are already sorted. As you insert elements one by one to the new list (i.e. the list that you will return), you should ensure that it is sorted (i.e. once all the elements are inserted, you should be done). Think carefully about how you can exploit the fact that the lists are already sorted to begin with.


2. Do problems 1, 2, 3, 5, and 6 from here.