Revision as of 14:20, 16 April 2012

Rhea Section for MA 375 Professor Walther, Spring 2012

Welcome to the MA 375 course page. Preferred Browser is Firefox.

at the bottom of the page.

OTHERWISE NO CREDIT ! (If you use the "Create a child page" button, this should happen automatically...)

Links

(See more below in Miscellaneous)

First time? Read this general note

corner/How to get started

Read the marvelous Rhea Help Manual written by Nate Orlow. Consider attending this informal mediawiki training session on Monday Jan 18. Your colleague Zach will tell you everything you need to know about editing and navigating Rhea.

Getting started
- To start, click the "Help" button above and read what's there.
- To edit pages, first log in (with your purdue account to create pages. Then click "edit" (under "Page" above) and remember to click "Save Page" after you are done editting.).
- To get a quick idea what works how, click "edit" on this page to see how to do the things visible on this page.
- Note that the "edit" mode has a spell-checking feature: look for red-underlined stuff.

Creating pages
- To create a new page named "B" from a page A, go to edit page A and insert the text [[B]]. (Note that "B" is like a web address for a webpage. Each page also has a name, but you can call the link anything (like fancy_title) by typing [[B|fancy_title]] rather than just B. After saving, find the new red link on page A that appeared. When you click it, you'll note you are now on page B (which of course is empty at this point).
- NOTE: if the "new" link comes out blue, instead of red, you chose a title of an existing page and did not create a new one. The blue link gets you simply to the already existing one. Use distinctive names for your new creations!
- If you place "Category:MA375Spring2012Walther" enclosed by square brackets on top of a new page it will be parsed by the system as belonging to this course. It can then be searched (for) in a meaningful way.

Advanced Rhea techniques
- You can look at other Rhea pages by clicking "main page" and then "course pages". Especially the ECE pages will get you an idea where one can take Rhea...
- Do you want to display pages in other pages?

Course Related Material

Your turn! A bonus point opportunity

Students in MA375 (Walther) have the opportunity to earn up to a 5% bonus by contributing a Rhea page on a subject related to linear algebra. To pick a subject, simply write your name next to it. Please no more than one student per subject. Your page will be graded based on content as well as interactions with other people (page views, comments/questions on the page, etc.). The number of links to other courses and subjects will also be taken into account: the more the merrier! Please do not simply copy the lecture notes and do not plagiarize. Read Rhea's copyright policy before proceeding.

For some lovely contributions, see Honors Project 2011 by Daniel Lee

Topic Number	Topic Description	Student Name	Deadline
1	Special sequences of numbers	Your Name Here	At Final
2	Games and mathematics	Carolyn Hanes	At Final
3	Mysteries of probability	Your Name Here	At Final
4	Hyperplane arrangements	Your Name Here	At Final
5	The use of graph theory	Yuedong Fang	At Final
6	Explaining a Clay problem	Your Name Here	At Final
7	Coloring problems	Chencheng Wang	At Final
8	What is homology?	Your Name Here	At Final
9	Greedy methods	Your Name Here	At Final
10	Cantor, sets, and continua	Your Name Here	At Final
11	Paradoxa come in different kinds	Your Name Here	At Final
12	What really IS a real number?	Edward Gier	At Final
13	Making Friends With ...	Theresa Blaisdell	At Final
14	Choose Your Topic	Your Name Here	At Final

Note: if you want to make a matrix, look at the source code for this page (click "edit") to see the syntax for the following matrix: $\left(\begin{array}{cccc}1&2&3&4\\5&6&7&8\end{array}\right)$

Postings of Course Notes

Discussion of Definitions

Table of Formulas

Discussion of Homework Problems (Just keep adding to it!)
- HW 1:
- HW 2:

Other Discussions

Exam Related

Miscellaneous

@@ Line 9: / Line 9: @@
 ----
 <div style="border-bottom: #448 1px solid; text-align: center; border-left: #338 4px solid; padding-bottom: 2em; margin: auto; padding-left: 2em; width: 30em; padding-right: 2em; background: #eef; border-top: #448 1px solid; border-right: #448 1px solid; padding-top: 2em">
-If you cre
+<br>
-<pre>• A covering for Figure 2 is {1, 2, 3, 17}.
-• Show the minimum cover for the bipartite graph shown in Figure 2.
-o The cover is {1, 16, 17}.
-Figure 2 Bipartite Graph
-• Examples:
-o Suppose you have a set of interpreters and a set of languages that need to be
-interpreted. Edges represent “can interpret.” We want to find the minimal
-number of interpreters to hire so that you can interpret all languages.
-o Set of people and a set of categories (male, Asian, CS major, single, ...). We want
-to form a committee with representation from all groups.
-• Set cover – given a collection of subsets, find a minimum number of subsets such that
-their union is the universe.
-o Can you see how to map this problem to the bipartite cover problem?
- Nodes for each subset. Nodes for each element. Edges represent “contains.”
-• This ability to map one problem into another is key to using knowledge of “algorithms community.” This is likely the reason why I always try to find similarities between things that seem different (e.g., cleaning up for company).
-• NP-hard – no one has developed a polynomial time algorithm. o Also called intractable or exponential.
-o We use greedy algorithms to approximate.
-• Greedy criterion – Select the vertex of A that covers the largest number of uncovered vertices of B. Also keep a Boolean array that tells whether each node is covered or not.
-o This idea could be implemented via a max tournament tree of “willCover” – take the biggest.
-Shortest Paths
-• Given a digraph with each edge in the graph having a nonnegative cost (or length).
-• Try to find the shortest paths (in a digraph) from a node to all other nodes.
-• Greedy criterion – From the vertices to which the shortest path has not been generated,
-select one that results in the least path length (the smallest one).
-• Have a reached set of nodes and an unreached set of nodes.
-. Initially, only the start node is reached.
-The Greedy Method Page 4
-. Use a min priority queue to store the total path lengths of each of the reached nodes to its successors.
-. While priority queue is not empty
- Pick the shortest total length node.
-• If it has already been reached, discard.
-• Else count it as reached.
- Enqueue the total path lengths of each of the reached nodes to its
-successors.
-• For example, consider the digraph Figure 3 in and calculate the shortest path.
-Figure 3 Shortest Path
-Minimal Spanning Trees
-• Problem – select a subset of the edges such that a spanning tree is formed and the weight of the edges is minimal.
-• Example – need to connect all sites to sewer system - want to minimize the amount of pipe.
-• Consider the spanning tree shown in Figure 4.
-Figure 4 Spanning Tree
-• Prim’s algorithm
-o Greedy criterion – From the remaining edges, select a least-cost edge whose
-addition to the set of selected edges forms a tree. Tree – set of vertices already in MST
-Succ – set of vertices not in Tree but in Succ[Tree] Place any vertex (to serve as root) in MST.
-The Greedy Method
-Page 5
-. Find the smallest edge that connects Tree with Succ
-. Add the edge to the MST and update Tree and Succ
-• Uses a greedy method – obtain a globally optimal solution by means of a locally optimal
-solution.
-• Using Figure 4 and Prim’s algorithm, we add the edges in the following order: (1,6),
-(6,5), (5,4), (4,3), (3,2), and (2, 7).
-• How do we find smallest edge? (sort or priority queue)
-• Kruskal’s algorithm
-o Greedy criterion – From the remaining edges, select a least-cost edge that does not result in a cycle when added to the set of already selected edges.
-Let each vertex be a separate component.
-. Examine each edge in increasing order of cost.
-. If edge connects vertices in same component, discard it. Otherwise, add edge to
-MST. Update components.
-• Using Figure 4 and Kruskal’s algorithm, we add the edges in the following order: (1,6),
-(3,4), (2,7), (2,3), (4,5), and (5,6).
-• How do we find smallest edge? (sort or priority queue)
-More Traversals of a Graph or Digraph
-• Tour – visit each vertex in a graph exactly once and finish at the vertex started from.
-• Eulerian tour – find a path/tour through the graph such that every edge is visited
-exactly once. (Easy – check nodal degree; if all are even, it is possible.)
-• Hamiltonian tour – find a path through the graph such that every vertex is visited
-exactly once. (NP complete)
-• See Figure 5 for different tours.
-Figure 5 Different Tours
-The Greedy Method
-Page 6</pre>
 at the bottom of the page.

Difference between revisions of "2012 Spring MA 375 Walther" - Rhea