Prerequisite Topics for CSE 415: Introduction to Artificial Intelligence

If you wish to take CSE 415, you should be familiar with the following topics. Most, but not all, of these are covered in CSE 373. If you know 80% of these, you can probably pick up the rest during the course, as needed.

Trees and tree traversal via recursion.
  Inorder, preorder, postorder.

Hashing...
  Hash tables
  hash functions
    Many-to-one aspect
  Collisions and resolution
    Linear Probing

Priority queues
  INSERT
  DELETE_MIN

Graph and graph representations
  Adjacency lists
  Adjacency matrices

Graph Algorithms.
  Dijkstra's algorithm
  Min. Spanning trees
    Prim's Algorithm
    Kruskal's algorithm

Programming:
  Deep and shallow copies of objects and other compound data structures
  Tree represented using nested lists
  Regular expressions (basic concepts of REs)
  Recursive functions, co-recursive functions

Logic:
  Basic Boolean algebra and propositional calculus:
    AND, OR, NOT, Exclusive-OR, Implies
    Simple formula manipulation
      DeMorgan's Laws.
    Conjunctive Normal Form
  Quantifiers    
    Forall x,  Exists x,  Variable Scope

Discrete Math:
  Sets of elements
    union, intersection, complement
    partitions of a set
  Binary relations
    reflexive, symmetric, antisymmetric, transitive properties
    partial order
    equivalence relation
  Cartesian products
  Functions
    Function property of a binary relation
    function domain, range
    Partial function.
    Predicate,
    Function properties: surjection, injection, 1-1 corresp.

  Countably infinite sets
  Power set
  Permutations and counting them.
  Combinations and counting them.
  Proof by Induction
    Basis
    Induction hypothesis
    Inductive step

Probability:
  Random variable with finite domain
  Joint probability distribution
  Conditional probability

Other Math:
  Geometric sequences and series, and formula for G.S.
  Harmonic sequences and series.

Asymptotic Analysis:
  Big O, Omega, Theta definitions and applications
  Code examples, including nested loops, recursive functions.
  Complexity of standard algorithms such as
    Mergesort, Heapsort, Quicksort

Algorithm Design Paradigms
  Divide and Conquer
  Dynamic Programming
  Greedy algorithm
  Backtracking Search

Command-line skills (Unix or DOS)
  Folder navigation, folder creation
  Running programs from the command line; path syntax.
  Unarchiving tar archive files.