A tree is a connected undirected graph with no cycles. Design a linear time algorithm to find a maximum cardinality matching in a tree.

Solution Preview

Please see the attached.

Algorithm Maximum (T)
Input: T is a rooted tree with n nodes.
Output: A maximum matching M
begin
M←0
number the nodes of T by a BFS (Breadth First Search)
(check the nodes with the backward order of the numbers)
for every node do
if the node or its parent is marked then
skip this node
else
mark its parent
add the edge to M

end
The BFS costs time of O(n) and the loop also costs time of O(n), so the time
complexity of the above algorithm is O(n).

Details:
Suppose T is a tree with a root r(T). Number the nodes by a Breadth First Search (BFS) starting at r(T). Suppose the size of T is n. Number the nodes of T with numbers from 1 to n. The root is ...

Solution Summary

Maximum cardinality matching algorithm example is provided in the solution.

1. Find the maximum flow and the associated minimum capacity cut for the following network, by using flow augmenting path algorithm (in the order of "first labeled, first scannred"). *see attachment for diagram*
2. A maximum capacity flow augmenting path is an augmenting path such that we can increase the flow of the network

It can be shown that R (the set of all real numbers) is an infinite-dimensional vector space over Q (field of rationals).
Is it true that any basis (by basis I mean algebraic basis or Hamel basis) of R over Q has to be uncountable ?

For a mapping %:A -> B, let == denote the kernel equivalence of %, and let *:A -> A== denote the natural mapping. Define $:A== -> B by $([a]) = %(a) for every equivalence class [a] in A==.
1. Show that $ is well defined and one-to-one, and that $ is onto if % is onto. Furthermore, show that % = $*, so that % is the composite

Let A, B, C be sets. Show that the sets (A^B)^C and A^(BxC) have equal cardinality by constructing an explicit bijection between the two sets. Conclude that (a^b)^c=a^bc for any natural numbers a, b, c. Use a similar argument to also conclude a^b x a^c= a^b+c

Explain and give examples for the following:
- Equivalent sets vs. Equal sets
- Cardinality of sets and how cardinality relates to the number of subsets of a set
- Subset vs. Proper Subset
- Complement of a set vs. Complement of a universal set.

Implement two recursive algorithms to solve the following problems:
Problem 1: Implement a recursive algorithm to find the maximum element of given integer array A. Count the number of comparisons while finding the maximum element and print input size, maximum element, and number of comparisons.
Example: integer array A=[1

1. Find the cardinality of the set of all irrational numbers, and prove your answer is correct.
2a. Is there a line in the x-y plane such that both coordinates of every point on the line are rational? Prove your answer is correct.
2b. Find the cardinality of the set of all complex numbers, and justify your answer.
3a. W

Let A and B be sets. Show that A x B and B x A have equal cardinality by constructing an explicit bijection between the two sets. Then use the following proposition to prove that multiplication is commutative. (Let n, m be natural numbers. Then nxm=mxn)
Proposition: Cardinal arithmetic
a) Let X be a finite set, and let x b

Let T[1..n] be a sorted array of distinct integers, some of which may be negative. Give an algorithm that can find an index i such that 1 <= i <= n and T[i] = i, provided such an index exists. Your algorithm should take a time in Big "O" (log n) in worst case.