Math 103 Spring 2012
Exam 1 review
The first hour exam will be on Friday, February 17, in class, and will cover through section 3.3 of the textbook
Some preliminary notes:
I have attempted to be comprehensive in the following, but you are responsible for the material covered, even if I do forget to list something here. If you do find an omission, please do let me know.
In your review, look at definitions, textbook examples, and homework problems assigned. In particular:
Be able to give a definition of terms encountered so far (a list of definitions appear at the end of each chapter)
Be able to say when a graph has or does not have an Euler circuit, and be able to find one if one is present.
Be able to "Eulerize" a graph (Chinese Postman Problem)
Be able to find Hamiltonian circuits. Be able to use the "nearest neighbor" and "sorted edges" approaches to solving the Traveling Salesperson Problem
Be able to count the number of circuits that must be checked for a given complete graph in solving the Traveling Salesperson Problem.
Be able to describe and discuss the notion of NP-Complete problems (spotlight 2.1, page 41)
Be able to use Kruskal's algorithm to find a minimum spanning tree.
Be able to find the critical path of an order-requirements digraph.
Given an order-requirements digraph and a task priority list, be able to schedule tasks on a given number of processors.
Given an order-requirements digraph, be able to construct a priority list using the critical path algorithm.
Given a collection of independent tasks, be able to schedule them on a given number of processors using the decreasing-time list approach.
We have discussed the following mathematicians on this exam. Please be prepared to give brief descriptions of each and be able to say how they are relevant to this course. Links provided point to articles about the mathematicians.
Notes:
1. Show your work. Answers given without indication of how you got the answer may not receive credit
2. Calculators will be permitted on this exam. In problems involving calculating a number, however, it is sufficient to leave the calculation in a form in which it can be entered into a calculator. If you do use a calculator, you should include this “pre-calculator” expression as part of your answer.
Any questions? Please ask!