Computer Science > EXAM > University of California, Davis CS 103 440S Practice Final Exam 2 Solutions-ALL ANSWERS CORRECT (All)

University of California, Davis CS 103 440S Practice Final Exam 2 Solutions-ALL ANSWERS CORRECT

Document Content and Description Below

CS103 Handout 44S Fall 2018 November 30, 2018 Practice Final Exam II Solutions This handout contains the solutions to the second practice final exam. Please, please, please, please don’t read ov ... er these solutions unless you set aside three hours and worked through the practice exam under realistic conditions (closed-book, closed-computer, limited-note). Taking this exam under realistic conditions is an excellent way to see what areas you need to focus on and to honestly size up where you stand and how to improve. These solutions are for use only by students in the Fall 2018 offering of CS103 and must only be used during that quarter. It is a violation of the Stanford Honor Code to use these solutions in any other context.2 / 15 Problem One: Set Theory and Logic An independence system over a set A is a nonempty set I ⊆ ℘(A) with the following property: ∀S ∈ I. ℘(S) ⊆ I. This question explores some properties of independence systems. i. (3 Points) Prove that if I is an independence system over a set A, then Ø ∈ I. Proof: Let I be an arbitrary independence system over a set A. Since I is an independence system, we know that it's nonempty, so there must be some set S ⊆ A such that S ∈ I. Notice that Ø ∈ ℘(S), since Ø is a subset of all sets. By the definition of an independence system, we know that ℘(S) ⊆ I. Therefore, since Ø ∈ ℘(S) and ℘(S) ⊆ I, we see that Ø ∈ I, as required. ■ ii. (5 Points) Let I₁ and I₂ be independence systems over the same set A. Prove that I₁ ∩ I₂ is also an independence system over A. Proof: Let I₁ and I₂ be independence systems over the same set A. We will prove that I₁ ∩ I₂ is also an independence system over A. First, note that I₁ ∩ I₂ is a subset of ℘(A), as mentioned in the problem statement. Next, we will show that I₁ ∩ I₂ is nonempty. To see this, notice that by our result from part (i) of this problem we know that Ø ∈ I₁ and Ø ∈ I₂, so we see that Ø ∈ I₁ ∩ I₂, so I₁ ∩ I₂ is nonempty. Finally, consider any S ∈ I₁ ∩ I₂. We need to show that ℘(S) ⊆ I₁ ∩ I₂. To do so, consider any set T ∈ ℘(S). We will prove that T ∈ I₁ ∩ I₂. Since I₁ and I₂ are independence systems over A, we know that ℘(S) ⊆ I₁ and that ℘(S) ⊆ I₂. Consequently, since T ∈ ℘(S), we see that T ∈ I₁ and T ∈ I₂. This means that T ∈ I₁ ∩ I₂, as required. ■ Why we asked this question: This question was designed to assess your ability to work with sets, elements, and subsets (and some weird interactions involving power sets of elements of sets being subsets!) and your ability to write proofs that call back to the formal definitions. The particular mathematical structure here – the independence structure – is relate [Show More]

Last updated: 3 years ago

Preview 1 out of 15 pages

Buy Now

Instant download

We Accept: