Computer Science 477/677
Design and Analysis of Algorithms
CSC 477/677 Study Guide for the First
Midterm Examination Spring 2008
-
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 Februarary 21 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 have full understanding of each of the sorting algorithms
we covered in class.
-
Know what an ADT is. You should know the definition and the
implementations covered in class of each of the following ADTs:
-
Search structure.
-
Stack.
-
Queue.
-
Heap.
-
Greedy algorithms, dynamic programming, divide and conquer.
-
Know about preorder, inorder, and postorder traversals of a binary tree.
-
Specific algorithm you should know:
-
Linear search in an array.
-
Binary search in a sorted array.
-
Bubblesort.
-
Selection sort.
-
Quicksort.
-
Heapsort.
-
Mergesort.
-
Polyphase mergesort.
-
Huffman's algorithm.
-
Finding a minimum path in a directed acyclic graph using dynamic programming.
-
Order statistics.