CSE232/notes.txt at master · caethan/CSE232 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#### Comments

Introduction
    library use
    sorting (do, but don't implement yourself)
    practice methods

Competition-specific advice
    Examine input ranges - determine how good an algorithm you need
        (e.g, w/ n=10, you can use an n! algorithm, with n=50, a

Data Structures
    know access times and library implementations
    balanced binary trees
    priority queue
    stack
    queue
    dictionary/hash table

Strings
    (approximate) string matching
    longest common substring

Dynamic Programming
    caching vs. computation
    identifying subproblems

Greedy Algorithms

Graph Theory
    depth- and breadth- first search
    representation method
    topological sort
    shortest paths
    maximum flow/minimum cut
    matching

Number Theory, Probability, and Combinatorics
    greatest common divisor
    prime numbers

Computational Geometry
    convex hull


Hard problems
    know how to recognize these when they get asked!
    Traveling salesman
    vertex cover
    hamiltonian cycle