Computer Science 477/677
Design and Analysis of Algorithms
CSC 477/677 Study Guide for the Second
Midterm Examination Spring 2008
-
A few questions will be from material covered before the first exam.
-
Review the homework assignments.
-
There will be some true/false and fill-in-the-blank questions.
-
I have posted
exams from prior semesters.
If a question that you see on one of those exams is not related to anything
we've covered in class so far this semester up to the last class day before
the exam, then don't worry: it will not be on our April 1 exam.
-
Understand what the array ADT is.
-
Be able to find the base address of an array object in the machine's memory.
-
You should know about various data structures used to implement graphs,
ordered graphs, weighted graphs, or weighted ordered graphs,
such as matrix, neighborlist (also called adjacency list), or other.
-
You should know the meanings of various words and phrases, including,
but not limited to:
-
connected
-
worst case
-
minimal, maximal (as opposed to minimum and maximum)
-
sparse
-
component
-
acyclic
-
strong component
-
path
-
simple path
-
shortest path (as in, smallest weight)
-
lazy deletion
-
single source, single pair, all pairs shortest path problems
-
additional words or phrases mentioned in class April 1
-
Specific algorithms you should know:
-
Kruskal's algorithm.
-
Prim's algorithm.
-
Dijkstra's algorithm.
-
Breadth first search, implemented using a queue.
-
Depth first search, implemented using a stack.
-
Tropical matrix multiplication.
-
Topological sorting: any correct algorithm will do.
-
Bellman-Ford algorithm.
-
Union-Find as implemented by disjoint forests, given
in class or on page 507 of your textbook.
-
Additional algorithms covered in class on April 1.