CSCI 665 Final - Any of The Objectives Can Be Tested On Your Final Examination

CSCI 665 Final - Any of the objectives can be tested on your final examination:
Chapter 1
1.1 Stable Matching – know what a stable match is; know how to tell if a match is stable; be
able to make a stable match on a small example; know basic properties of a stable match
Chapter 2 – Basic Algorithm Analysis
2.1 Tractability – know brute force analysis for problems in 2.1; scaling property of polynomial
complexity problems; rank functions by runtime complexity; compute input size given a
runtime complexity and operations per second; determine runtime complexity (as big-Oh,
Ω, Θ ) given a function; know what big-Oh, Ω, Θ are as definitions; know and use basic
properties of asymptotic orders of growth
Chapter 3 – Graphs
you should know terminology associated with each topic
3.1 Basic Definitions – know graph terms: nodes, edges, path, cycle; know definition of
directed, undirected, connected graph; know tree definitions
3.2-3.3 Connectivity,Traversal, Representation – know how to perform BFS, DFS; know
properties of BFS in terms of its layers; know graph representations: adjacency matrix,
adjacency list and the runtime implications of each;
3.4 Bipartite Graphs – know how to define one; know how to test for bipartiteness; know
bipartite properties as they relate to layers of a BFS of a graph; know how to test for
bipartiteness in terms of layers of a BFS of a graph;
3.5-3.6 Strong Connectivity, Topological Sorts – know what strong connectivity is and how to
test for it with a BFS; know what a DAG is and how to perform a topological ordering of one;
be able to compute the number of topological orderings on a small DAG
Chapter 4 – Greedy Algorithms
Be able to identify a greedy algorithm when you meet it in a dark alley – that is, its basic
properties; you should know terminology associated with each topic
4.1 Interval Scheduling – know what the problem is and a greedy algorithm for solving it; know
what the scheduling all interval problem is and a greedy algorithm for solving it
4.2 Scheduling to Minimize Lateness – know what the problem is and a greedy algorithm for
solving it
4.4 Shortest Path in a Graph (Single source) – know Dijkstra’s algorithm and be able to use it to
solve a graph problem
4.5 Minimum Spanning Tree – know Prim’s algorithm, running time, and be able to apply it;
know Kruskal’s algorithm, running time, and be able to apply it
4.6 Union/Find – know the data structure and its implementation; know how to refine Union by
size and height; know how to make find more efficient with path compression;
4.7 Clustering – know what the problem is, and how to use an appropriate algorithm to obtain a
k-cluster
Chapter 5 – Divide and Conquer Algorithms
basic properties of divide and conquer algorithms; you should know terminology associated
with each topic
5.1-2 Solving Recurrences – be able to solve basic recurrences for closed solutions
5.3 Solving Inversions – know what the problem is and how to solve it with divide and conquer
5.4 Closest Pair of Points – know what the problem is and how to solve it with divide and
conquer
Chapter 6 – Dynamic Programming
basic properties of dynamic programming algorithms; you should know terminology associated
with each topic
6.1-2 Weighted Interval Scheduling– know what the problem is and how to solve it recursively
and with dynamic programming
6.4 Subset Sum - know what the problem is and how to solve it recursively and with dynamic
programming; know the Knapsack variant of this problem
6.6 Sequence Alignment – same as above
6.8 Shortest Paths – from all nodes to a single destination node – same as above
Chapter 7 – Network Flow
basic properties of network flow algorithms; you should know terminology associated with each
topic
7.1 Know how to build a maximum flow graph using successive residual graphs
7.2 Be able to identify maximum flow with a cut; be able to explain how max flow relates to
minimum cut.
7.5-7 Know the following applications of maximum flow: bipartite matching, disjoint paths,
circulations with demand.
Chapter 8 – P/NP
you should know terminology associated with each topic
Know the reduction process and be able to apply it to a simple couple problems; know what
what it proves about problems
Know what NP Hard problems are, be able to identify them
Know the definition of NP, NP Complete, NP Hard problems and know how they relate to each
other; know where P problems fit in and why
Be able to identify a P problem, NP Complete problem, an NP Hard problems
Know the significance of the SAT problem
Know the process for proving problems are NP Complete
Be able to apply that process to problem that SAT easily reduces to (like K CLIQUE).
Examination Breakdown: 30 questions total, 2.5 hours. The distribution of questions will be the same
as the distribution of points.
Chapter # Questions
1-2 3
3 4
4 5
5 5
6 5
7 5
8 3

CSCI 665 Final - Any of The Objectives Can Be Tested On Your Final Examination

Uploaded by

Copyright:

Available Formats

CSCI 665 Final - Any of The Objectives Can Be Tested On Your Final Examination

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

CSCI 665 Final - Any of The Objectives Can Be Tested On Your Final Examination

Uploaded by

Copyright:

Available Formats

CSCI 665 Final - Any of the objectives can be tested on your final examination:

You might also like