## A Study Guide to Quiz 2 and Exam 2

**Note:** Don Curtis will run Quiz 2 in the discussion sections on
Monday (4/6) and Tuesday (4/7). Exam 2 will be in class on Friday, April 10th.
Quizzes and exam will be open notes and book.

- Lists in Python and various list operations including append,
insert, remove, pop, sort, +, etc.

- Given a code fragment, function, or an algorithm described in psedocode,
how to figure out the running time, as a function of the input size.

- Algorithms for searching:
*linear search*, *binary search*
and why linear search runs in O(`n`) time in the worst case
and why binary search runs in O(log_{2}`n`) worst case time.

- A slow sorting algorithm:
*bubble sort*. Why the running time
of bubble sort is O(`n`^{2}).

- Sorting with comparisons:
*counting sort*; situations in which
we can do counting sort and the running time of counting sort.

- The
*divide-and-conquer* paradigm and *quick sort* as an
example of this. Details of the quick sort algorithm and its implementation.
The importance of choosing a "balanced" pivot, randomized choice of a pivot, etc.
Two implementations of `partition` discussed in class.

- Optimization problems, greedy algorithms, how greedy algorithms
may yield solutions that are not optimal, constructing counter
examples for greedy algorithms. The
*job scheduling* problem
and two greedy algorithms for the problem that are suboptimal and one that
is optimal.

- How the dictionary data structure in Python works.