CS 325: Juli Shutfort

Upon entering this class, we expect all students to (red text = math expectations):

• Understand proof by induction (if something is true for “n”, prove it is true for “n+1”, then, by pointing out that it is obviously true for n=0 or 1, it is now proven that it is true for all integers)
• Understand proof by contradiction (if something is assumed true, but that creates a major problem with an already-proven principle, the original assumption must really be false)
• Solve algebraic equations and inequalities: one equation, one unknown: 3x+10=19
• Understand laws of exponents: xa * xb = xa+b ; xa / xb = xa-b ; (xa)b = xab
• Understand laws of logarithms: log(ab) = loga + logb ; log(a/b) = loga – logb ; log(ab) = b*loga
• Know the formulas for arithmetic series, e.g., 1 + 2 + 3 + 4 + … + N = N*(N+1)/2
https://en.wikipedia.org/wiki/Arithmetic_progression
• Know the formulas for geometric series, e.g., a + ar + ar2 + … + arn-1 = a(1-rn)/(1-r)
https://en.wikipedia.org/wiki/Geometric_series
• Write a recursive function (e.g., a function that breaks the problem into pieces and then calls itself on each piece)
• Know basic graph theory: the formal definition of a directed and undirected graph, tree, path, cycle, and spanning tree in a graph. Be familiar with a Breadth-First Search (BFS), a Depth-First Search (DFS), and a shortest path algorithm (e.g., Dijkstra’s Algorithm).
• Understand basic trees: be familiar with a Breadth-First Search (BFS) and a Depth-First Search (DFS). Understand how binary trees help in achieving O(log2n) behavior.
• Know how to plot and fit a line or curve to data using any software. Most students use Excel or Matlab. Other options are Python, R, Statgraphics, or any other software that works.
• Know how to accomplish basic file I/O in any language you choose: C, C++, Python, Java.

mjb – July 5, 2017