This is a list of topics you need to study for the final exam. You are also advised to look at the lecture schedule on the course website. You also need to study the handouts (scroll below). Please email me immediately regarding any doubts about this.

Chapter 2

Section 2.3: Cartesian products, Relations as subsest of Cartesian products, counting the number of possible relations; Functions, domain and co-domain, equivalence of functions, one-one functions, onto functions, bijections (functions that are one-one and onto), examples of each type,importance of domain and co-domain in defining a function, inverse function, function composition, non-commutativity of compositions, existence of function compositions, floor and ceiling functions, counting problems on number of functions of different types (except for onto functions) from one finite set to another.
Section 2.4: sequences and summations, arithmetic and geometric series, summation of the first n terms of an arithemtic and geometric sequence, concept of cardinality, countable infinity, countable infinity of set of all even/odd integers, all integers (positive and negative), all rational numbers, concept of uncountable infinity, subset of countable set is countable.

Chapter 3

Section 3.1: Linear search, Bubble sort, Insertion sort.
Section 3.2: Big-O notation, proving that one function is (or isn't) big-O of another one, Big Omega, Big Theta.
Section 3.3: Complexity of Algorithms in worst case, Look at Table 1 on page 196.
Other stuff on Algorithms: Binary search, Search for the maximum element of a unimodal array, Fast evaluation of a^n where n = 2^k, Determining whether a point lies inside a convex polygon in O(log n) time [all the aforementioned fall into the Divide and Conquer category]; Greedy Knapsack.

Chapter 4

Section 4.1: Mathematical Induction, Flaws in Inductive Proofs, Induction in geometry.
Section 4.2: Strong induction, study the two examples done in class.
Section 4.3: Concept of recursion, Recursively defined sequences and simple recursively defined sets.
Section 4.4: Recursive algorithms to compute a^{2^k}, fibonacci numbers, comparison of iterative and recursive procedures, emphasis on Merge sort, Quick sort: examples and time complexity analysis.

Chapter 5

Section 5.1: Counting basics: sum rule and product rule, problems involving use of both, look at examples 9 and 13 in your book, inclusion exclusion principle with 2 and 3 sets (see section 7.5 for this part.). You do NOT need to study the inclusion-exclusion formula for n sets.
Section 5.2: Pigeonhole principle and generalized pigeonhole principle.
Section 5.3: Permutations (choosing r objects out of n objects such that the ordering matters), Combinations (choosing r objects out of n objects such that the ordering does not matter), Comparison between the foll. problems: (A) Number of ways to choose one object each from k buckets containing n_1,n_2,...n_k objects respectively (when the ordering does or does not matter); and (B) Number of ways to choose k objects from a single bucket containing n different objects (when the ordering does or does not matter).
Section 5.3: Combinations viewed as subsets, Combinatorial proof involving two ways to calculate the number of subsets, ~~Combinatorial proof of Pascal's Identity [see theorem 2 in section (5.4)].~~
Section (5.5): permutations with repetition, permutations with indistinguishable objects, distributing n different objects into k different boxes. You do NOT need to study the case of combinations with repetition even if it's there in section (5.5). You do not need to study section (5.4) or (5.6) as it was not done in class.

Chapter 9

Section 9.1: definition of graph, types of graphs: directed versus undirected, simple graphs versus multigraph, examples of graph modelling: web graph, collaboration graph, precedence graph.
Section 9.2:
1. Definition of adjacency, degree of a vertex, isolated vertices.
2. Handshaking lemma and its corollary (i.e. theorems 1 and 2 in section 9.2), in-degree and out-degree in a connected graph, theorem that sum of in-degrees and out-degrees is equal to number of edges (theorem 3 in your book).
3. Types of graphs: complete graph, cycle graph, wheel graph, bipartite graph, coloring theorem for bipartite graph (theorem 4), complete bipartite graph, applications in job assignments.
4. Subgraphs of a graph, union of graphs, complement of a graph (see exercise 53 of your book), spanning subgraph.
5. Counting number of edges in different types of graphs, Counting number of subgraphs and spanning subgraphs of a complete graph.
Section 9.3: Adjacency Matrix, Adjacency List, Comparison of Adjacency Matrix and Adjacency List, Graph Isomorphism: Formal definition of isomorphism in terms of bijections between vertices, failure of degree sequences as a sufficient condition for isomorphism of graphs, applications of graph isomorphism in chemistry (for discovery of new isomers) and in flow graphs for plagiarism detection.
Section 9.4: Definition of a path and circuit, Counting number of paths of given length (say r) between two vertices, Connected graphs and connected components(undirected), Strongly and weakly connected graphs (directed).
Section 9.5: Eulerian circuit and Eulerian Path, necessary and sufficient conditions for both, Seven bridges of Konigsberg problem, example of Eulerian circuit in picture drawing, hamiltonian circuit and hamiltonian path, examples of graphs have both HC and EC, neither of the two, only one of the two.
Section 9.7: Planar graphs and planar embeddings, Proof of non-planarity of K_{3,3}, Euler's formula and its proof, Corollaries of Euler's formula.

Here is a list of handouts that you SHOULD study:

As always, homework solutions and quiz solutions will provide you a good idea of the different types of questions that you should prepare for. Reading through the solutions will be useful for you. Quizzes have covered a few finer nuances such as count and radix sort, and the challenging recurrence relation in quiz 5.
Greedy Knapsack (check courseworx)
Strong induction proof for the property that in any triangulation of a convex polygon, there are two non-adjacent vertices that are not the endpoints of any diagonal.
Online material for some of the stuff on Unimodal arrays and convex polygons (ignore ALL other stuff from the link).
Handout for quick-sort (you do not need to study the gory details of the in-place partition algorithm on slide 4, or study the average-case running time (slides 14 and 15), or the in-place version of quick sort (slide 16) [Please email me if you have any doubts]. Here is a local copy of the stuff on quick-sort. Here is a detailed analysis of the time complexity of quicksort and mergesort.
For the proof of necessary and sufficient conditions for existence of Eulerian circuits, study the handout on courseworx (under "Solutions and Lecture Notes" -> "Handouts". It's in the same place where the Greedy Knapsack stuff was). Study the introduction to Eulerian circuits, the Lemma 1.2.25 in that handout, proof of theorem 1.2.26. Do not study proposition 1.2.27, or theorem 1.2.23 in the handout.

Here is a list of what you do NOT need to study:

Cantor's diagonalization argument for uncountable infinities.
Proof of correctness of greedy knapsack or any other algorithm.
Halting problem.
Advanced topics such as proof of lower bound on sorting [though, for interested souls, it exists on pages 699 and 700 of your book], or description of linear time median-finding algorithms.
Structural or generalized induction or recursive definition of strings (even though these things are mentioned in section 4.3).
Do not do Example 4 (from section 4.2) on Page 287, which looks at multiple base cases for strong induction. In fact, this example employs a special, slightly different form of strong induction, which we haven't covered in class. Such problems will not be asked in the exam. Also you do not need to look at the well-ordering property, and you do not need to study the highly complicated proof of Lemma 1 on page 289.
Do not study section 5.4 (Binomial theorem) or section 5.6 (generation of permutations and combinations). Do not study combinations with repetition from section 5.5.
You do not need to study the inclusion-exclusion principle for more than 3 sets.
In section 9.5 do not study Dirac's theorem and Ore's theorem.
Do not study section 9.6 or 9.8 of chapter 9.
Do not study Kuratowski's theorem in section 9.7 (just read it).
In section 9.4, do not study the algorithm to construct an Eulerian circuit.
Incidence matrices from section 9.3 not required
Occasionally, in chapter 9, there are references to different types of "relations", a concept explored in depth in chapter 8, which we haven't covered. You are not expected to know the different types of relations. But you are expected to know what is meant by a "relation" as the definition was discussed in chapter 2. A relation between two sets A and B is any subset of their Cartesian product.
Do not study combinatorial proofs, except for the proof which involves two different ways of counting subsets (see the proof on page 364, 365).