Algorithms and Data - CS 4800 List of topics on the Final Exam What is on the test? Definitions Short answer (see concepts) Algorithm implementation Poly-time reductions Polynomial-time reduction Local Search (Gradient descent, Metropolis, Hopfield nets) Approximation Algorithms Randomized Algorithms (randomized algorithms, Chernoff bounds) Concepts: Bipartite Matching Independent Set Adjacency Matrix Adjacency List Paths and Connectivity Cycles Trees Rooted Trees Phylogeny Trees Graph Traversal BFS DFS A* Heuristic Connected Component Testing Bipartiteness Directed Graphs DAGs Strong Connectivity Minimum Spanning Tree Cycles and Cuts Cut sets Greedy Algorithms Clustering Single-link clustering Dendrograms max-flow and min-cut P vs. NP NP-complete Reductions Approximation algorithms Hopfield neural networks Nash equilibria Payoff Matrix Probability Randomized algorithms Chernoff bounds Linear Programming Algorithms you need to be able to implement: Gale-Shapley BFS Topological sort Kruskals algorithm Prims algorithm Dijkstras Shortest Path Weighted Interval Scheduling Knapsack problem Mergesort Quicksort Bellman-Ford algorithm Ford-Fulkerson algorithm Polynomial-time reduction Metropolis algorithm Chernoff bounds What can you bring? No-Internet connected stuff. A book (like Kleinberg & Tardos), 5 pages of cheat sheets, and a non-Internet-connected calculator (or abacus or slide-rule)
Posted on: Wed, 13 Aug 2014 00:51:12 +0000
Trending Topics
Recently Viewed Topics
© 2015