CS 341: What to know for the midterm
The midterm is
Tuesday, October 25 2016, 7 PM - 9 PM, STC 1012 and 0040. Pick either room,
any seat. You can bring one sheet of paper to the exam with anything
(written, printed, drawn -- anything!) on it. Both sides may be used. No other aids allowed. In particular, no computers, calculators, tablets, phones, or electronic devices. Do not bring phones!
You are responsible for all the class content in
of lectures 1-12, and all the lecture notes for lectures 1-12,
available on the course home page, as well as
the suggested readings in the textbook:
Chapter 2, 3, and 4.
Section 5.3.
Section 7.3, 7.4.
Chapter 15.
Sections 16.1, 16.2.
Section 28.2 (of 2nd edition only; if you have the 3rd edition this material
is in Chapter 4).
Section 31.1, 31.2, 31.3.
Section 33.3, 33.4.
You should know
- properties of logarithms and factorials and exponents
- when an algorithm is considered "good"
- operations counted as function of size of problem instance
- measuring the size of an input
- counting operations
- types of analysis: worst-case, average-case; time, space
- how to compare algorithms
- order notation (O, Ω, Θ, o)
- recurrence relations, recursion tree, master method
- nine paradigms of algorithm design, especially "reduce to known
problem"; greedy; dynamic programming; divide-and-conquer
- all the algorithms we discussed
You should know basic stuff from previous courses, such as basic
calculus, and basic aspects of algorithms from CS 240.
The best way to study for the midterm is to read the lecture notes and make
sure you understand them, and to do some of the exercises in the textbook
in the sections listed above.