Prerequisites. You need upper-level undergraduate or graduate-level algorithm / data structure classes, such that you are familiar with basic algorithm design ideas such as divide-and-conquer, graph algorithms, data structures, etc. Similar classes at UCR can be (CS10C + CS141) or CS218. For your reference, CS141 slides are also provided here.

Preparation checklist:

Make sure you are familiar with the following concepts/algorithms:

  • Basic algorithmic ideas: asymptotic notations (big-O, Big-Omega, small-O, small-Omega, Theta), divide-and-conquer, random access machine (RAM)

  • Sorting algorithm: quicksort, merge sort

  • Algorithm and analysis of the following data structures: Hash tables (algorithm, analysis), search trees (e.g., AVL tree, red-black tree, B-tree), linked lists, stacks, queues

  • Graphs concepts: graphs and basic concepts (directed/undirected, weighted/unweighted), shortest paths, minimum spanning trees, connectivity, breadth-first search (BFS), depth-first search (DFS).

  • Graph algorithms: BFS algorithm, Dijkstra’s algorithm

  • Maths: solving recurrences, Master Theorem for solving recurrences, probability theory, computing expectations and probability, associativity, commutativity, matrices, matrix multiplication

  • System/programming: familiar with C++, pointers, references, arrays, memory allocation