🏷️ LIMITED TIME OFFER: GET 20% OFF GRADE+ YEARLY SUBSCRIPTION →

HomeClass Notes1,200,000CA670,000

CISC 365 Lecture Notes - Lecture 13: American Broadcasting Company, Substring, Subsequence

33 views7 pages

amaranthcricket401

21 Nov 2016

School

Queen's University

Department

Course

Professor

For unlimited access to Class Notes, a Class+ subscription is required.

Document Summary

Review of the dynamic programming solution for subset sum. Let s = { } and let the target value be k. Suppose there is a subset s* of s that sums to k. let be the nal element of s*. Then the rest of s* is a solution to the subset sum problem on { } with target value k - . (this is the. Principle of optimality at work we discuss this in more detail below. ) We can look at the process of nding a solution as a sequence of decisions: rst we decide whether or not to include , then , etc. This suggests constructing a table s_s in which we list the elements of s on one axis, and possible target values x on the other. For the x values, we will use 1 k. then s_s(i,x) = true i { } contains a subset that sums to x.

Related Documents

CISC 365 Lecture Notes - Lecture 8: C Max, Message Passing, While Loop

amaranthcricket401

CISC 365 Lecture Notes - Lecture 10: Huffman Coding, Bit Array, Binary Tree

amaranthcricket401

CISC 365 Lecture Notes - Lecture 5: Metar, Non-Deterministic Turing Machine, Halting Problem

amaranthcricket401

Related Questions

These questions are asking about subrgoups, groups, isormorphic.

actually, after 2day, I got a midterm for abstract math test,and I got a sample of midterm test, so I hope to get a solution ofall these question. I think it is a lot, but I hope that pleaseshow me the answer and I want to know why these answer is this.

The reason why these problems are bunch of questions, so I willgive big pts for this questions. thanks.

you guys can upload by the picture.

(below question)

SAMPLE MIDTERM 1, MATH 120A

(1) 1. Write the denition of group.

2. Give an example of a group of order 2011.

3. Give an example of a non-abelian group with 12 elements.

(2) Let (G,*) and (H . ) be groups.

1. Dene what it means for G and H to be isomorphic.

2. Assume that G has exactly two solutions to the equation x^2 =e.

Prove, directly from the denition in (1), that if G and H areiso-

morphic, then H has exactly two solutions to the equation x^2 =e.

3. Prove or disprove: (R, +) is isomorphic (R+, . ). Here R+ ={x is subset of R : x>0}.

4. Prove or disprove: (R, +) is isomorphic (R*, . ). Here R* ={x is subset of R : x is not 0}

(3) Let G be the group Z_20, with addition modulo 20.

1. Draw the subgroup diagram of G, giving a generator for eachsubgroup

2. Find the subgroup H =< 16 > of G.

3. Find a subgroup K of U_20 isomorphic to H.

(4) Let (G, . ) be a group and let H be a subgroup of H. Fix anelement a of

G and let K = { aha^-1 : h is subset of H}

1. Prove that K is a subgroup of G.

2. Prove that the map psi : H -> K, h -> aha^-1 isan isomorphism of groups.

(5) Let (G, . ) be a group and let a be an element of G.

1. Dene the order of a.

2. Give an example of an element of order 4 in GL(2,R).

3. Find the order of 16 in Z_20.

I have the answer for the following question. But some of theanswers are not correct.

Please do the following question by yourself and check which arethe wrong answers,please post your answers and compare to it.

Let r in and u =(1 1 0), v = (1 4 1), w = (r2 1 r2), b = (3+2r 5+12r 2r). For which values r in is the set {u. v, w} linearly independent? For which values r in is the vector b a linear combination of u. v and w? For which of these values of r can b be written as a linear combination of u. v and w in more than one way? The set 3 of all column vectors of length three, with real entries, is a vector space. Is the subset B = {(x y z) in 3 | xy + yz = 0} a subspace of 3? Justify your answer. Show that the set of all twice differentiable functions f : satisfying the differential equation sin(x) f"(x) + x2f(x) = 0 is a vector space with respect to the usual operations of addition of functions and multiplication by scalars. Here, f" denotes the second derivative of f. Let S be the following subset of the vector space 3 of all real polynomials p of degree at most 3: S = {p in 3 | p(l) = 0, p'(l) = 0}, where p' is the derivative of p. Determine whether S is a subspace of 3. Determine whether the polynomial q(x) = x - 2x2 + x3 is an element of S. u = (1 1 0), v = (1 4 1), w = (r2 1 r2) if {u, v, w} is linearly independent set 1(4r2 - 1)-1(r2 - r2) ne 0 4r2 ne 1 r ne plusmn1/2 this set is linearly independent set for values of e ne plusmn1/2 - - - - - - - (3+2r 5+12r 2r) = a1 (1 1 0) + a2 (1 4 1) + a3 (r2 1 r2) this forms system of equations in a1, a2, a3 if 4r2 - 1 ne 0 then system has unique solution if 4r2 - 1 = 0 and -2 - 4r = 0 rArr r = -1/2, the system has more than one solution if 4r2 - 1 ne 0 b can be written as linear combination of u,v,w as uniquely if r = -1/2 then b can be written as linear combination of u,v,w more than one way - - - - - - - - - (1 1 -1) in B and (1 0 1) in B (1 1 -1) + (1 0 1) = (2 1 0) not in B since 2times1+1times0 ne 0 so addition of vector is failed, this set is not forms subspace consider the following differential equation (sinx)f"(x) + x2f (x) = 0 each solution is continuous function the set of all solutions is subset of space of set of all continuous functions n from R to R let f,g are two solutions (sinx)f"(x) + x2f (x) = 0 (sinx)g"(x)+x2g(x) = 0 ccheck whether af+bg is solution or not (sinx)f"(x) + x2f(x) = 0 rArr (sinx) af"(x) + x2?f (x) = 0 (sinx)g"(x) + x2g (x) = 0 rArr (sinx)bg" (x) + x2bg (x) = 0 (sinx)(af"(x)+bg"(x)) +x2 (af (x) + bg(x)) = 0 af+bg is also solution to differential equation the set of all solutions to differential equation forms subspace - - - - - - - - - - consider the following subset of P3 {p in P3/.p(l)=0, p'(l) = 0} let p, q in S rArr p(l)= 0, p'(l) = 0 and q(l) = 0, q'(l) = 0 (ap + bq) (l) = ap (l) +b q(l) = a (0) + b (0) = 0 (ap + bq)'(1) = ap'(l) +bq'(1) = a (0) + b(0) = 0 p, q in S rArr ap +bq in S then S is subspace q(x) = x - 2x2 + x3 q(1) = 1 - 2 + 1 = 0 q'(x)=1 - 4x + 3x2 q'(l) = 1 - 4 + 3 = 0 q is element of S