« Lecture #Syllabus for all sect | Main | Lecture #Syllabus for all sect »
February 03, 2006
Exam #1: Syllabus for all sect
The first monthly exam is now available (this link will take you to the download page).
The exam is Thursday through Saturday next week. It will be 3 hours and TAKE HOME. Closed book, one page of notes. No calculators (and you won't need one).
If I were taking the exam, which I will before I put it in the testing center, then I would do the following to study these topics:
- Homework problems are fair game for exam questions though not all exam questions will be old homework problems.
- Get the solution key for the homeworks and get your homeworks and determine if you correctly understood the homework and solved the problems correctly.
- Go through the lecture notes to see what topics where emphasized in class and be sure that you understand those topics.
- The exam will have almost nothing in common with the project. In fact, the only direct overlap is that there is a question which says "what did you learn about efficient programming from Project #1? (including the improvement if you want to)"
- NP-completeness: how to prove it and what does it mean?
- big-O, big-Theta and big-Omega
- parts of a greedy algorithm
- greedy algorithms for minimum spanning trees and sorting.
- greedy algorithms for knapsack loads.
- Equation 7.1 (The "Master Theorem")
- parts of a divide and conquer algorithm
- Quicksort, the pivot selection problem and the worst-case behavior of quicksort (but nothing about the proof of the average case behavior).
- Divide and conquer algorithms for multiplying integers (but nothing like question 7.2)
- Binary search.
- Strassen's matrix multiplication algorithm. (You won't be asked to do the busy work to multiply two actual matrices, but you should know how the algorithm works and why).
- No questions about phylogenetics. That will just be on the project.
The exam will cover a subset of the aforementioned topics.
Posted by jones at February 3, 2006 03:58 PM
Comments
What will the format be like? Multiple choice, fill in the blank, short answer?
Posted by: Brian ![[TypeKey Profile Page]](http://vv.cs.byu.edu/cs312/nav-commenters.gif)
at February 6, 2006 04:50 PM
short answer. One fill in the blank, no multiple choice.
Mike.
Posted by: Mike Jones at February 6, 2006 05:42 PM
Post a comment
Thanks for signing in, . Now you can comment. (sign out)
(If you haven't left a comment here before, you may need to be approved by the site owner before your comment will appear. Until then, it won't appear on the entry. Thanks for waiting.)