Computer Science 477/677
Design and Analysis of Algorithms
CSC 477/677 Study Guide for the First
Midterm Examination Fall 2009
-
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 September 29 exam.
-
You should understand what an asymptotic complexity class is, and
be able to solve the kinds of recurrences we did in class.
-
You should know the meanings of various terms, for example, single-source
shortest path problem, knapsack problem, and minimum spanning tree problem.
(Those are only examples. There are more.)
-
You should understand the following abstract data types and their
implementations:
-
You should understand dynamic programming.
-
Specific algorithm you should know:
-
Linear search in an array.
-
Binary search in a sorted array.
-
Bubblesort.
-
Selection sort.
-
Quicksort.
-
Heapsort.
-
Mergesort.
-
Huffman's algorithm.
-
Finding a minimum path in a directed acyclic graph using dynamic programming.
-
Order statistics.
-
Kruskal's algorithm.
-
Bellman-Ford algorithm.
-
Union-Find, as implemented by disjoint forests, given in class or on page 507
of your textbook.