Prerequisites for Algorithms by Jeff Erickson

Author lists below as the prerequisites for reading his book: (Below content has been copied from the Prerequisites pages of his book)

• Discrete mathematics: High-school algebra, logarithm identities, naive set theory, Boolean algebra, first-order predicate logic, sets, functions, equivalences, partial orders, modular arithmetic, recursive definitions, trees (as abstract objects, not data structures), graphs (vertices and edges, not function plots). 

• Proof techniques: direct, indirect, contradiction, exhaustive case analysis, and induction (especially “strong” and “structural” induction). Chapter 0 uses induction, and whenever Chapter n−1 uses induction, so does Chapter n. 

• Iterative programming concepts: variables, conditionals, loops, records, indirection (addresses/pointers/references), subroutines, recursion. I do not assume fluency in any particular programming language, but I do assume experience with at least one language that supports both indirection and recursion. 

• Fundamental abstract data types: scalars, sequences, vectors, sets, stacks, queues, maps/dictionaries, ordered maps/dictionaries, priority queues. 

• Fundamental data structures: arrays, linked lists (single and double, linear and circular), binary search trees, at least one form of balanced binary search tree (such as AVL trees, red-black trees, treaps, skip lists, or splay trees), hash tables, binary heaps, and most importantly, the difference between this list and the previous list. 

• Fundamental computational problems: elementary arithmetic, sorting, searching, enumeration, tree traversal (preorder, inorder, postorder, levelorder, and so on). 

• Fundamental algorithms: elementary algorism, sequential search, binary search, sorting (selection, insertion, merge, heap, quick, radix, and so on), breadth- and depth-first search in (at least binary) trees, and most importantly, the difference between this list and the previous list.

• Elementary algorithm analysis: Asymptotic notation (o, O, Θ, Ω, ω), translating loops into sums and recursive calls into recurrences, evaluating simple sums and recurrences. 

• Mathematical maturity: facility with abstraction, formal (especially recursive) definitions, and (especially inductive) proofs; writing and following mathematical arguments; recognizing and avoiding syntactic, semantic, and/or logical nonsense.

Books:

Margaret M. Fleck. Building Blocks for Theoretical Computer Science, unpublished textbook, most recently revised January 2013. Available from http://mfleck.cs.illinois.edu/building-blocks/. 

• Eric Lehman, F. Thomson Leighton, and Albert R. Meyer. Mathematics for Computer Science, unpublished lecture notes, most recent (public) revision June 2018. Available from https://courses.csail.mit.edu/6.042/spring18/. (I strongly recommend searching for the most recent revision.) 

• Pat Morin. Open Data Structures, most recently revised January 2016 (edition 0.1Gβ). A free open-content textbook, which Pat maintains and regularly updates. Available from http://opendatastructures.org/.