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(log2n) worst case time.
- A slow sorting algorithm: bubble sort. Why the running time
of bubble sort is O(n2).
- 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.