Assignment 4 Math

docx

School

Florida International University *

*We aren’t endorsed by this school

Course

MISC

Subject

Computer Science

Date

Feb 20, 2024

Type

docx

Pages

Uploaded by gonzvegas

Exercise Set 9.3 (p. 599+ of Epp, fifth edition): Exercises 7, 9, 12 There are 26 uppercase letters, 10 digits and 14 symbols. The total number of choices is 26+10+14=50 (a) If repetition of symbols is allowed: There are 50 choices for each entry in the password. So, by multiplication rule, The number of passwords of length n is (50)n. Then, If the password is of length 3, then total number of choices are (50)3. If the password is of length 4, then total number of choices are (50)4. If the password is of length 5, then total number of choices are (50)5. By addition rule, The total number of passwords consisting of 3, 4, or 5 symbols is: (50)3+(50)4+(50)5=318875000 (b) If repetition is not allowed: Password is of length 3, then total number of choices are 50×49×48=117600.

If the password is of length 4, then total number of choices are 50×49×48×47=5527200. If the password is of length 5, then total number of choices are 50×49×48×47×46=254251200. So, the total number of passwords of 3, 4, or 5 symbols, each has no repeated symbol, is 117600+5527200+254251200=259896000. (c) At least one repeated symbol: The number of passwords with at least one repeated symbol plus the number of passwords with no repeated symbols is 318875000. The number of passwords with at least one repeated symbol+259896000=318875000 ⇒ The number of passwords with at least one repeated symbol=318875000−259896000=58979000 (c) Probability: Now, the probability that a password chosen at random has at least one repeated symbol been: 58979000/318875000=18.5% a) 4(4+1)/2= 4*5/2= 10 times b) When the algorithm is implemented and run, the inner loop will be iterated for i=1 to i=n . 1 + 2+ 3+ 4 +…+ (n - 1) + n = n (n + 1) / 2 times.

a) For the word THEORY, the total number of arrangements is 6 factorial (6!). So total number of arrangements in row = 720. b) If H and T must stay together, consider them as a single entity and along with the other four letters, arrange them in 5 factorial ways. So number of arrangements is = 120 Exercise Set 9.4 (p. 614+): Exercises 2, 6, 15, 16, 27 a) Yes, selecting 13 cards from a standard 52-card deck ensures at least two cards will have the same denomination. This is because there are only 4 suits, each containing one card of each denomination. By the pigeonhole principle, drawing more than one suit's worth of cards means duplication is inevitable. b) Yes, if 20 cards are selected from a standard 52-card deck, at least two must be of the same denomination. This is because there are only 13 different denominations in a deck (Ace through King). When you select more than 13 cards, the pigeonhole principle ensures that at least two cards will have the same denomination since there are not enough unique denominations to assign to each card uniquely.

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

A) When you divide an integer by 6, the possible remainders are 0,1,2,3,4,5 which is a total of 6 elements. If you have seven integers at least two of them must have the same remainder when divided by 6 because you have more integers than possible remainders. b) For any set of seven integers, there must be two that have the same remainder when divided by 8 due to the pigeonhole principle. When you divide an integer by 8, the possible remainders are 0 through 7, which is a total of 8 possible outcomes. With seven integers, if you were to have all distinct remainders, you would have only 7 remainders used once, but since you have 7 numbers and 8 possible remainders, at least two of your integers must share the same remainder when divided by 8. Selecting at least one odd number: In the range from 0 through 2n, there are n+1 even numbers (including 0) and n odd numbers. To be sure of selecting at least one odd number, you must consider the worst-case scenario where you pick all the even numbers first. Therefore, after picking n+1 numbers (all the possible even numbers), the next number you pick must be odd. So, you need to pick n+2 numbers to be sure of getting at least one odd number. Selecting at least one even number: The range from 0 through 2n includes 0, which is even. Therefore, to be sure of selecting at least one even number, you only need to pick 1 number in the worst-case scenario, as the first number you pick could be 0 (or any other even number). So, the answer is just 1 for selecting at least one even. There are 20 numbers divisible by 5 in the interval [1, 100]. In the worst chase you have to pick 81 numbers - the 80 numbers that are not divisible by 5, and finally one that is. 81 Integers is the final answer. there are 365 days in a year. If we distribute 2,000 people across these 365 days evenly, each day will have 2000/365 = 5.48 people. A person cannot be represented by a fraction. Therefore, some days must have at least 6 people sharing a birthday to balance out those days with only 5 or fewer.

Exercise Set 9.5 (p. 630+): Exercises 2, 7 List out the all 3-combinations for the set .=a The set of all 3-combinations for the set a is union of all 3-combinations, so that the object x1 is always included and the object x is never included. First, let’s consider the 3-combinations so that the object x1 is always included. So, two more elements are required for a 3-combination. Those are Therefore, all 3-combination so that the object x1 is always included are, {x1,x2,x3},{x1,x2,x4},{x1,x2,x5},{x1,x3,x4},{x1,x3,x5},{x1,x4,x5} Now lets consider all 3-combinations so that the object x1 is never included. Those are, {x2,x3,x4},{x2,x3,x5},{x2,x4,x5},{x3,x4,x5} Therefore, all 3-combinations for the set are, The value is, = 5!/[(5-3)!*3!] = 10 (b) The list of all unordered selections of two elements from the set is, {x1,x2},{x1,x3},{x1,x4},{x1,x5},{x1,x6},{x2,x3},{x2,x4},{x2,x5},{x2,x6},{x3,x4},{x3,x5}, {x3,x6},{x4,x5},{x4,x6},{x5,x6} Counting the elements we get 15 or 6!/(6-2)!x2!= 15

a) (13 and 7) = 13!/(13-7)!*7!= 1716 b) (i) (7 and 4) (6 and 3) = [7!/(7-4)!*4!]* [6!/(6-3)!*3!] = 700 (ii) (13 and 7) - (7 and 7) = (13 and 7)-1=1715 (iii) (7and 3)(6 and 4)+(7 and 2)(6 and 5)+(7 and 1)(6 and 6) = 658 c) (2 and 1)(11 and 6) + (11 and 7) = 1,254 d) Total possibilities are (2 and 2) (11 and 5)+ (11 and 7) = 792 Exercise Set 10.1 (p. 639+): Exercises 2, 5, 9, 25 A walk consists of a sequence of vertices and the edges that connect them in an alternating fashion. A closed walk starts and finishes at the same vertex.

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

A path is a sequence of vertices connected by edges where each vertex appears only once, except potentially the first and last vertices being identical. A trail is a type of walk where no edges are traversed more than once. It can revisit a vertex as long as it arrives and departs via distinct edges. A cycle is a specific type of path that has the same starting and ending vertex. A circuit is a trail that begins and ends at the same vertex. Examples: The sequence v1-e2-v2-e3-v3-e4-v4-e5-v2-e2-v1-e1-v0 demonstrates a walk. The sequence V2-V3-V4-V5-V2 forms a cycle. The sequence V4-V2-V3-V4-V5-V2-V4 shows a closed walk. The sequence V2-V1-V5-V2-V3-V4-V2 represents a circuit. The sequence V0-V5-V2-V3-V4-V2-V1 is a trail. The sequence V5-V4-V2-V1 constitutes a path. To find the number of paths from point A to point C on a graph: A path is a sequence of edges and vertices where none are repeated at the edges of a graph. The possible sequences from A to C are AE1-BE5-C, AE2-BE5-C, AE3-BE5-C, and AE4-BE5-C, which totals 4 distinct paths. For the number of trails from A to C: A trail is a sequence where edges are not repeated, though vertices may be revisited. The options include the direct paths AE1-BE5-C, AE2-BE5-C, AE3-BE5-C, AE4-BE5-C, plus combinations that loop back to A before heading to C like AE1-BE2-AE3-BE5-C, AE1-BE2-AE4-BE5-C, and so on. There are 28 such trails. Regarding the number of walks from A to C:

A walk can revisit both vertices and edges. Given that vertices and edges can be repeated, there's an infinite number of walks from A to C since you can keep traversing the graph in loops before reaching C. In summary, there are 4 paths, 28 trails, and an infinite number of walks from A to C. We have been provided with a set of claims concerning Eulerian graphs and are tasked with evaluating their validity. In the realm of graph theory, a Eulerian circuit is a route that traverses each edge of a graph exactly once and concludes at the vertex where it began. For a graph to host a Eulerian circuit, it must not only be fully connected but also feature vertices each with an even number of connecting edges. For option (e), the answer is incorrect. This is because the graph in question has vertices with an odd number of edges, but a requirement for a Eulerian circuit is that all vertices must have an even number of edges. Therefore, since this graph contains vertices that do not meet this criterion, it cannot have a Eulerian circuit. Moving on to the next point, the correct answer is affirmative: the graph G does possess a Eulerian circuit as it fulfills the stipulations outlined in Theorem 10.1.3. The first option is correct because graph G, being connected and having all vertices with an even degree (2, 2, 4, 4, and 6), meets the necessary conditions for a Eulerian circuit. Lastly, we cannot conclusively state that the graph has a Eulerian circuit because there is no information confirming whether the graph is connected. Although the graph has vertices with even degrees, the absence of confirmation about its connectivity leaves the existence of a Eulerian circuit in G uncertain.

a. The complement of the graph K 4, the complete graph on four vertices, is K 4Since K 4is a complete graph, every pair of distinct vertices is connected by an edge. Therefore, in K 4, no pair of vertices will be connected by an edge. The complement K 4 will thus have no edges, and it will be an empty graph with 4 isolated vertices. b. The complement of the graph k3,2 the complete bipartite graph on 3 and 2 vertices, is k3,2. In k3,2 all vertices from the first set of 3 vertices are connected to all vertices of the second set of 2 vertices, and there are no edges among vertices within the same set. Thus, in k3,2 there will be no edges between the sets, but all vertices within the same set will be interconnected. The complement k3,2 will be two complete graphs:k3 and k2 with k3 vertices of k2. Exercise Set 10.4 (p. 731+): Exercises 7, 15, 16, 17 a) In a rooted tree, terminal vertices are those vertices that do not have successors. Conversely, vertices that do have children are known as internal vertices. For example:

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

Terminal vertices include v1, v5, v7. Internal vertices include v2, v3, v4, v6. b) Terminal vertices in another instance are v1, v2, v5, v6, v8. Internal vertices in this case are v3, v4, v7. Yes. A graph with these properties can exist. It is circuit-free, meaning there are no closed loops or cycles. It contains exactly seven vertices (labeled 1 through 7). There are four edges, connecting vertices 1 to 5 in a linear chain. The remaining vertices (6 and 7) are isolated, ensuring that no circuit is formed. Fifteen Edges: There's a contradiction here, as a tree with twelve vertices can only have eleven edges (since a tree always has vertices−1 edges). Given these points, it's impossible to construct a tree with twelve vertices and fifteen edges.

It has exactly six vertices (labeled 1 through 6). There are five edges in the graph. Importantly, it is not a tree. This is because it contains a, which violates the definition of a tree as a cycle-free graph. Exercise Set 10.5 (p. 700+): Exercises 2, 13, 14, 15 a. Level 3 b. Level 0 c. 5 (considering root as height 0) d. V14,v15,v16 e. V1 f. V2 g. V17,v18,v19 h. 10 leaves : {v7,v13,v9,v14,v15,v16,v11,v18,v19,v4}

Given that there are five internal vertices, the number of leaves should be 5+1=6. Therefore, the total number of vertices in the tree would be 5 (internal) +6(leaves)=11. However, the requirement is to have only nine vertices in total, which contradicts the inherent properties of a full binary tree. Thus, it's impossible to construct a full binary tree with nine vertices and five internal vertices. The requirements conflict with the fundamental structure of a full binary tree. Exercise Set 10.7 (p. 757+): Exercises 4, 11

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

4 The graph G contains four circuits: rztxyr, syxs, uvxu, and xvwx. By eliminating certain edges from these circuits, we can derive a spanning tree that connects all vertices in the graph. The specific edges removed to achieve this are zt, yx, xu, and xv. As a result, the spanning tree is constructed as follows: 17 Consider the six cities as vertices and the pipelines connecting two cities as edges, forming a connected graph G. To construct a network of pipelines that connects all cities while minimizing the total cost, the Kruskal's algorithm can be applied. Begin by including all vertices of G in the set T, and let E represent the set of all edges in G. The cities are designated as follows: S for Salt Lake City, C for Cheyenne, D for Denver, P for Phoenix, L for Albuquerque, and M for Amarillo, which constitute the vertices of G. Search for the edge with the lowest weight in E; the edge {C, D} has the minimum weight. Eliminate this edge from E and include it in T. Next, identify the edge with the lowest weight in E excluding {{C, D}}. The edge {L, M} has the least weight. Remove this edge from E and incorporate it into T, ensuring that it does not create a cycle within T. Continue this method, eliminating the lowest-weight edge and adding it to T, without forming any cycles. Following this procedure, T will evolve into a spanning tree of G, specifically, the minimum spanning tree of G. Include an edge in T only if its addition does not result in a cycle within T.

Order of edges: {C, D}, {L, M}, {L, P}, {S, C}, {D, M} Exercise Set 12.2 (p. 855+): Exercises 4, 9, 10 a. (a) s0,s1,s2 are states. b. (b) 0, 1 are input symbols. c. (c) is the initial state. d. (d) is the accepting state. e. (e). Inputs 0 1 S0 S1 S0 S1 S2 S0 S2 S2 S0

a. The first column of the annotated table denotes the states of the automaton, which are s0, s1, s2, and s3. b. The automaton accepts two input symbols, which are 0 and 1. c. The initial state of the automaton is s0, as indicated by the unlabeled arrow pointing to it. d. The state s1 is the sole accepting state, as it is uniquely distinguished by a double circle. e. The transition diagram reflects the structure and rules of the automaton as presented. a. N(s1, 1) = s2, N(s0, 1) = s3 b. N(s2,0) = s3, N(s1,0) = s3

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

c. N*(s0, 10011) = s2, N*(s1, 01001) = s2 d. N*(s1,11010) = s2, N*(s0,01000) = s3

Assignment 4 Math

Related Documents