Monday, August 29, 2022
Sunday, August 21, 2022
Tuesday, August 16, 2022
Friday, August 12, 2022
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/.