MAT 2051 Discrete Mathematics Full Course Tasks

Unit 1 Discussion

DQ1 Logic and Reasoning

Logic and reasoning play important roles in computer applications, systems management, database management, and error management. In this discussion, you will examine logic and deductive reasoning, symbols and definitions, and an application involving database and error logging.

Deductive Reasoning, Part 1

Given the following true logical statement:

If inputs x1, x2, and x3 are all true, then output y is true.

Write this statement as a logical statement using the appropriate logic symbols for conjunction and implication.

Write the converse and contrapositive of this statement.

Is the converse true? Explain why or why not.

Is the contrapositive true? Explain why or why not.

Deductive Reasoning, Part 2

Assume you are a systems manager and that you know a server will log an error message if a database has a retrieval error. With that, complete the following:

Why is it important for errors to be logged?

What is a database retrieval error, and what might cause this type of error?

If you notice that there is an error logged, can you infer that a retrieval error has occurred without reading the log? Explain why or why not. (Hint: This is a question about reasoning.)

Prior to posting your response, review the Discussion Participation Scoring Guide. This is the recommendation for all discussions in this course.

Response Guidelines

Read your peers’ posts and respond to two. Do you agree with your peer’s assessment of the problem? Explain.

DQ2 Practice Problem Set Review

The problem sets are assigned to help you practice solving problems and prepare for the corresponding quiz and the final exam. As mentioned in the studies, the problem sets are not graded or collected.

Each unit you will have an opportunity to discuss the problem sets with your fellow learners. Use this discussion to ask questions, make comments, ask for help, and assist your peers with the problem sets. Teamwork is encouraged.

Four posts are required in this discussion: two initial and two response. Additional posts are optional and recommended, but not required for your grade:

For the first post, select a problem from this unit’s problem set, write it out fully, solve it fully, and post it.

The second post can be a problem you cannot solve or another fully solved problem from the problem set. If there is a problem in the assigned problem set that you are confused about, write it out fully and show any work you have started. Note that you are stuck and ask for help. If you are able to solve every problem in the set without difficulty, post at least one other fully solved problem from the set as your second post.

The third and fourth posts are response posts. Response guidelines are provided below and in every discussion.

Take advantage of this discussion area to work together as a class on the problem set. Post as many problems as you can and review as many of your peers’ posts as you can. Ask questions. Offer answers. If you are stuck on a problem, post your question. Working as a team will help each person gain a better understanding of the problem set and the concepts covered in this unit.

Response Guidelines

The third and fourth posts, the response posts, are your chance to help your peers. Explore the posts made by your peers and find people who are stuck. Help at least two peers through the problems they are stuck on. If you are unable to locate a peer who is stuck, you may instead choose a peer post, write out your solution to the same problem, and compare solutions and methods. The goal of this area is for the entire class to work together as a group on the entire problem set. You are also expected to complete and understand the problem set on your own in preparation for the quizzes and final exam.

MAT2051 Discrete Mathematics

Unit 2 Discussion

DQ1 Relational Databases

Relations and functions play important roles in computer applications, systems management, database management, and error management. In this discussion, you will look at relational databases and their functions and applications.

Databases are common computer and Internet technology applications. Online banking, shopping, iPhones, music, video, personal files, businesses, governments, and academic institutions all use databases to store, process, and retrieve information, including images, video, and music.

Suppose you are a database manager and oversee a large database with the following four tables: EMPLOYEE, DEPARTMENT, SUPPLIER, and BUYER.

Now, turn to page 168 in the text. Under Exercises, you will see these four tables listed as 3.6.4, 3.6.5, 3.6.6, and 3.6.7.

Part 1: Table and Database Operations

Complete the odd problems from 5 through 15 on page 169.

Write out each question fully.

Write a sequence of table operations to answer the query required for each question.

Provide the final answer to the query for each question.

Part 2: Researching the Web for Database Applications

Create two paragraphs that describe two current database application packages. For example, you might choose Oracle and SQL Server.

Read about what these packages offer, how they are alike, how they are different, and what applications they are best suited for.

What language is commonly used to manipulate and communicate with database applications? Offer a few examples of statements from this language.

Review the Discussion Participation Scoring Guide prior to posting.

Response Guidelines

Read your peers’ posts and respond to two. Do you agree with your peer’s assessment of the problem? Explain.

DQ2 Practice Problem Set Review

This discussion allows you to work with your peers to complete and understand the assigned problem set for this unit. Remember, two initial posts and two response posts are required. Further posts are optional and recommended:

For the first post, select a problem from this unit’s problem set, write it out fully, solve it fully, and post it.

The second post can be a problem you cannot solve or another fully solved problem from the problem set. If there is a problem in the problem set that you are confused about, write it out fully and show any work that you have started. Note that you are stuck and ask for help. If you are able to solve every problem in the set without difficulty, post at least one other fully solved problem from the set as your second post.

The third and fourth posts are responses. Response guidelines are provided below and in every discussion.

Response Guidelines

MAT2051 Discrete Mathematics

Unit 3 Discussion

DQ1 Networking and Probability

Probability and statistics allow us to make decisions when dealing with uncertain variables. For example, assume you are the network administrator of a large firm and have ordered 100 RAID (redundant array of independent disks) devices. You would like to make sure all of the RAIDs work before sending them to different departments. But you do not have time to check all of the devices. If you check some of them and show they work, how confident could you be that all 100 devices work?

Of course, testing all of the RAIDs would be the best way to be confident, but assume you do not have the time. If you only have time to check 5 of the 100, and none of the 5 are defective, how confident would you be that none of the other microprocessors are defective (that is, all 100 devices are fully functional)?

Answer the following questions, which will help you understand the problem. Explain each question and your answer:

How can you use discrete probability to calculate the probability of testing 5 devices such that all 5 end up being nondefective RAIDs, given there are 20 defective RAIDs total of the original 100 RAID devices?

What is the sample space in this problem?

Is this a ratio of combinations or permutations problem? Explain why and show an example. Hint: Read section 6.5 and see Example 6.5.4 in your textbook.

Assume there are exactly 5 defective RAIDs out of the 100 RAID devices. What is the probability of testing 20 RAIDs at random and finding all of them nondefective?

Review the Discussion Participation Scoring Guide prior to posting.

Response Guidelines

Read your peers’ posts and respond to two. Do you agree with your peer’s assessment? Explain.

DQ2 Practice Problem Set Review

For the first post, select a problem from this unit’s problem set, write it out fully, solve it fully, and post it.

The third and fourth posts are responses. Response guidelines are provided below and in every discussion.

Response Guidelines

MAT2051 Discrete Mathematics

Unit 4 Discussion

DQ1 Machines, Intelligence, and Neural Networks

In this discussion, you will research the history of artificial intelligence (AI). Write two to three paragraphs on the history of AI and how the ideas of logic, resolution, and unification were implemented within machines so they could demonstrate “intelligence.” In your post, answer at least two of the following questions:

What is the resolution and unification algorithm, and what is an algorithm?

What is the Turing test, and who is Alan Turing?

What is a neural network?

Can machines really demonstrate intelligence?

In order to answer these questions, you will have to search the Internet. Suggested search terms include history of artificial intelligence, Turing test, and so on.

Review the Discussion Participation Scoring Guide prior to posting.

Response Guidelines

Read your peers’ posts and respond to two. Assess your peer’s post. Do you agree or disagree? Explain.

DQ2 Practice Problem Set Review

For the first post, select a problem from this unit’s problem set, write it out fully, solve it fully, and post it.

The third and fourth posts are responses. Response guidelines are provided below and in every discussion.

Response GuidelinesThe third and fourth posts, the response posts, are your chance to help your peers. Explore the posts made by your peers and find people who are stuck. Help at least two peers through the problems they are stuck on. If you are unable to locate a peer who is stuck, you may instead choose a peer post, write out your solution to the same problem, and compare solutions and methods. The goal of this area is for the entire class to work together as a group on the entire problem set. You are also expected to complete and understand the problem set on your own in preparation for the quizzes and final exam.

MAT2051 Discrete Mathematics

Unit 5 Discussion

DQ1 Data Mining, Time Complexity, and Algorithms

In Appendix C, you read about different programming control structures used to write pseudocode and actual computer algorithms, such as if statements, while and for loops, and function calls. For this discussion, assume you work for a data mining company and your job is to write a program to find information on various Web sites pertaining to sales of the Lenovo X200. After your algorithm finds this data, more complex analysis will be done to extract more meaningful information from the data.

Your algorithm is going to scan different sites and search for the character string “Lenovo X200.” Assume you decide to use an algorithm similar to Text Search (see algorithm 4.2.1 on page 178 of your text for an explanation of what this is). If the algorithm finds a site that contains the string (that is, Lenovo X200), assume that it then stores all data or all the text on that particular site into a storage area.

To understand this problem fully, answer the following questions:

What is data mining?

What is a character string?

What is the worst case run time of this algorithm in terms of p, m, t, n (that is, what is O)?

How long do you think it will take this algorithm to run? Note the time complexity as O (run time in terms of n).

Assume that each Web site, on average, has character strings of length 10,000 and that the length of the character string “Lenovo X200” is 11. How many computations will the algorithm need to make per site?

Why is speed and the analysis of algorithm speed so important?

Review the Discussion Participation Scoring Guide prior to posting.

Response Guidelines

Read your peers’ posts and respond to two. Did you arrive at the same time complexity calculation? Explain why or why not.

DQ2 Practice Problem Set Review

For the first post, select a problem from this unit’s problem set, write it out fully, solve it fully, and post it.

The third and fourth posts are responses. Response guidelines are provided below and in every discussion.

Response Guidelines

MAT2051 Discrete Mathematics

Unit 6 Discussion

DQ1 Cryptography and Security

Cryptography is an exciting IT field that focuses on secure communications, typically on a network. Many encryption methods use number theory to encode and decode messages. This number theory typically draws upon ideas such as prime factorization, greatest common divisors (GCD), modulus, and so on.

For this discussion, read Chapter 5, section 5.4, which starts on page 250 of your text, which discusses number theory and applications to cryptography. Post an explanation of how the RSA public-key cryptosystem works that includes answers to the following questions:

What is a key?

What are public and private keys, and how are they used in the RSA public-key cryptosystem?

How are messages encoded and decoded using mod and GCD?

If you are using p = 17, q = 23, and n = 31, what would the encryption of 101 be, using public key z = pq?

Where is security used, and why is it important to everyone?

Review the Discussion Participation Scoring Guide prior to posting. Make sure you include a minimum of three posts and that your first, or main, post responds to all parts of the question posed.

Response Guidelines

Read your peers’ posts and respond to two. Did you reach the same encryption as your peer? Explain why or why not. Show your work.

DQ2 Practice Problem Set Review

For the first post, select a problem from this unit’s problem set, write it out fully, solve it fully, and post it.

The third and fourth posts are responses. Response guidelines are provided below and in every discussion.

Response Guidelines

MAT2051 Discrete Mathematics

Unit 7 Discussion

DQ1 Computer Networks, Distributed Systems, and Mobile Agents

Computer networks typically consist of nodes and edges—they are graphs. The nodes can typically be computers, routers, servers, and so on. The edges indicate a communication path between nodes. Assume you are a network administrator for a distributed system and that you wish to perform maintenance of all the servers in your system. You have decided to do this by using a mobile agent. To get started, look up and answer the questions in Part 1. After that, complete Part 2:

Part 1

What is a distributed system?

What is a mobile agent?

Since this agent is autonomous and moves from computer to computer, it would be smart to equip it with shortest path algorithms, so that it can go from server to server, reaching all the servers only once, in the shortest amount of time. This is the traveling sales person (TSP) problem. Note that computer networks can be modeled using graphs and that shortest paths solutions, Hamilton cycles, TSP, and so on can be found using graph-based algorithms.

Part 2

How would you model a computer network using a graph? What are potential nodes, edges, and weights?

Which of these traversal algorithms should the agent be equipped with? Which will help the agent traverse the network in an efficient manner? Explain why.

What is the TSP problem, and how does it relate to this question?

Review the Discussion Participation Scoring Guide prior to posting.

Response Guidelines

Read your peers’ posts and respond to two. Compare your response to your peer’s response. Did you come up with the same results? Explain why or why not.

DQ2 Practice Problem Set Review

For the first post, select a problem from this unit’s problem set, write it out fully, solve it fully, and post it.

The third and fourth posts are responses. Response guidelines are provided below and in every discussion.

Response Guidelines

MAT2051 Discrete Mathematics

Unit 8 Discussion

DQ1Networking, Graphs, Adjacency Matrices, and Server Application

Assume you are a network administrator of a large business firm that wishes to construct an intranet. Your firm has a number of computers, servers, and services such as printers, all connected to five hubs (hubs 1, 2, 3, 4, and 5), which must now be connected to each other. Assume each hub is separated by distances shown in the following adjacency matrix:

Adjacency Matrix. See D-Link for full description. [D]

Each hub must be connected to at least one other hub, therefore, you only need to make four connections to allow communication between all computers. You can further minimize the cost of the cables and time by only connecting the closest hubs.

Consider and answer the following questions to evaluate this problem:

What is an intranet?

What is an adjacency matrix, and how do they relate to graphs?

What is the optimal connection of the five hubs that will minimize the length of the cable required to connect them? Note: The length of the cable will be the distance between the hubs as shown in the adjacency matrix.

How did you arrive at this answer? What algorithm should be used to solve this problem?

Hint: This is a graphical minimization problem. Make sure you comment on the following: What are the vertices? What are the weights on the edges? What are we trying to minimize?

Review the Discussion Participation Scoring Guide prior to posting.

Response Guidelines

Read your peers’ posts and respond to two. Compare your response to your peer’s. Explain the similarities and differences between your posts.

DQ2 Practice Problem Set Review

For the first post, select a problem from this unit’s problem set, write it out fully, solve it fully, and post it.

The third and fourth posts are responses. Response guidelines are provided below and in every discussion.

Response Guidelines

MAT2051 Discrete Mathematics

Unit 9 Discussion

DQ1 Data Storage, Retrieval, Sorting Algorithms, Time Complexity

In computer systems, the storage, retrieval, and communication of data occurs frequently and therefore must be optimized and fast. In some instances, it is best to store a list of numbers in some order (for example, in an increasing or decreasing order), to make the retrieval of some of the data very fast (for example, the maximum value).

In section 4.2 of your textbook, you read about the insertion sort algorithm (see Algorithm 4.2.3, page 180). This algorithm will sort a list of n numbers in non-decreasing order. However, in section 9.7, pages 477–483 of the text, you read about a faster sorting algorithm.

In order to fully understand this question, answer the following questions:

The name of the faster sorting algorithm is the tournament sort. How is this faster sorting algorithm achieved?

Given a list of n numbers, what is the worst case times for the insertion sort algorithm and the tournament sort algorithm?

In the insertion sort and the tournament sort algorithms, what discrete structures are used to store the data? Explain.

How does the use of the tree structure provide the framework for a tournament sort?

What is a divide-and-conquer algorithm? Is this a divide-and-conquer algorithm?

You may find the link in the resources section useful for this discussion. Review the Discussion Participation Scoring Guide prior to posting.

Response Guidelines

Read your peers’ posts and respond to two. Compare your post with your peer’s. Explain the similarities and differences.

DQ2 Practice Problem Set Review

For the first post, select a problem from this unit’s problem set, write it out fully, solve it fully, and post it.

The third and fourth posts are responses. Response guidelines are provided below and in every discussion.

Response Guidelines

MAT2051 Discrete Mathematics

Unit 10 Discussion

Problem Set and Final Exam Preparation Discussion

This discussion is set up like the previous problem set discussions. In addition to using this discussion to address the unit’s problem set, use the area to post any questions, concerns, or comments you have as it relates to preparing for the final exam.

For the first post, select a problem from any problem set in this course, write it out fully, solve it fully, and post it.

The second post can be a problem you cannot solve or another fully solved problem from any problem set. If there is a problem in any problem set that you are confused about, write it out fully and show any work you have started. Note that you are stuck and ask for help. If you were able to solve every problem without difficulty, post at least one other fully solved problem from any problem set as your second post.

The third and fourth posts are responses. Response guidelines are provided below.

Take advantage of this discussion area to work together as a class to prepare for the final exam. Post as many problems and questions as you can and review as many of your peers’ posts as you can. Ask questions. Offer answers. If you are stuck on a problem, post your question. Working as a team will help each person gain a better understanding of the problem sets and the concepts covered in this course.

Response Guidelines

MAT2051 Discrete Mathematics

Unit 1 Assignment 1

Complete the following problems from your text. These problems are chosen to parallel the problems in The Practice Problem Sets study for this unit, so it is recommended to do those first, then post and discuss in the Practice Problem Set Review discussion so you are better prepared for this assignment.

Section 1.1, page 12, problems 15, 53.

Section 1.2, page 19, problems 21, 30.

Section 1.3, page 30, problem 72 only.

Section 1.4, pages 35–36, problems 21, 28.

Section 1.5, pages 48–49, problems 36, 74.

Section 1.6, page 55, problems 24, 28.

Section 11.1, page 537, problem 11.

Section 11.2, pages 548–549, problem 2.

MAT2051 Discrete Mathematics

Unit 1 Assignment 2

Boolean Circuits and Technology

This is the first of five independent application assignments. Each assignment will allow you to learn how the topics of this course apply to the areas of computer science, Internet technology, or technology applications.

For this assignment, imagine that we are many years into the future and you have been hired by a technology company to create a human door key system. When a person steps on a special mat containing sensors that is located at his or her front door, these sensors grab information, send it through a set of circuits, and reach a one of two logical conclusions:

Yes (or 1), the person lives in this house and may enter.

No (or 0), this person does not live in this house and may not enter.

If the result is yes, the door automatically opens. If the result is no, you can decide what happens.

For this assignment, complete the following:

Define at least five features that can be sensed by the magic door mat such that each feature has a result of 0 or 1. This magical mat can sense anything, such as weight, height, eye color, hair color, gender, and so on. Because the result of the sensor can only be 0 or 1, you will have to think about how to do this. As an example, if the weight is greater than 125, the sensor returns a 1, else a 0. Similarly, if the hair color is NOT brown, the sensor returns a 0, else 1. These are just some ideas.

Explain each of your features clearly, including exactly what the 0 or 1 represents in each case.

Using at least five gates and at least five inputs, create a logical circuit that describes your system. This circuit will have at least five inputs, at least five gates, and one—and only one—output. Remember, the input values to and from the gates are only 0 or 1, but you can name them according to what they represent.

Create a logic table to show some examples of people who will and will not be able to enter. This table will be labeled with your attributes and will contain values of only 0 and 1.

Describe your circuit using a Boolean expression with proper use of AND, OR, and NOT symbols.

Describe what will happen to a person who cannot enter (that is, when the output of the circuit is 0). This is up to you, so feel free to be creative. Include at least one paragraph explaining your circuit, your features, and what will happen in cases where a person can or cannot enter the door. Hint: You can have the door inform the person that they cannot enter and why.

You may find it useful to read Chapter 11, pages 532–542, and look at the examples. You can combine attributes to make sure only the right person gets in. For example, if a person’s weight is greater than or equal to 125, you can have a 1. If the weight is less than 125, you can have a 0. Therefore, if the person weighs 250 pounds, this would result in a 1. You can use the circuit creatively with AND, OR, and NOT gates to grant or deny access using a set of measurable attributes.

Review the Boolean Circuits and Technology Scoring Guide to understand how you will be graded on this assignment.

MAT2051 Discrete Mathematics

Unit 2 Assignment

Section 3.1, pages 125–126, problems 21, 63.

Section 3.2, pages 137–140, problems 27, 148.

Section 3.3, page 150, problem 31.

Section 3.4, page 156, problems 2, 12.

Section 3.5, pages 163–164, problems 3, 10.

Section 3.6, page 169, problem 12.

Resources

MAT2051 Discrete Mathematics

Unit 3 Assignment 1

Section 6.1, pages 264–265, problems 2, 38.

Section 6.2, page 278, problems 12, 40.

Section 6.3, page 288, problem 2.

Section 6.5, page 299, problems 2, 6, 16, 21.

Section 6.6, pages 311–312, problems 2, 15, 29, 58.

MAT2051 Discrete Mathematics

Unit 3 Assignment 2

Web Addresses and Discrete Math Applications

The World Wide Web is a boundless resource of information. It contains blogs, tutorials, demos, videos, text, references, and resources for just about any topic you may want to research. Computer users visit Web sites identified by an address, or URL (uniform resource locator). You are doubtless familiar with URLs, such as http://www.cnn.com or http://www.fox.com.

Unlike URLs, which use letters, the DNS (domain name system) resolves URLs into a numerical IP (Internet provider) address. These addresses are assigned to nodes in a computer network. While you answer the following questions, ask yourself if there are an infinite number of Web sites available.

Define the following:

What is a URL?

What is an IP address?

What is a DNS?

Explain:

How are URLs assigned to IP addresses?

What does DNS stand for and what does it do?

Is there a limited number of Web sites available using IP version 4 (documented as IPv4)?

What changes have been made in IPv6 compared with IPv4?

Calculate:

Given that an IP address in IPv4 is a 32-bit string, how many different addresses can be encoded? Show your calculation. Hint: Use the multiplication principle.

How many different Web sites could be encoded using IPv6? Show your calculation.

For this assignment, make sure you clearly and completely define, explain, and show all work for your calculations. The assignment should be two to three pages. Include all resources used. Review the Web Addresses and Discrete Math Applications Scoring Guide to understand how the assignment will be graded.

MAT2051 Discrete Mathematics

Unit 4 Assignment

Section 2.1, page 70, problems 5, 11.

Section 2.2, page 81, problems 9, 14.

Section 2.3, page 88, problem 6.

Section 2.4, page 96, problems 3, 9.

MAT2051 Discrete Mathematics

Unit 5 Assignment 1

Section 4.1, page 176, problem 5.

Section 4.2, page 183, problems 5, 9.

Section 4.3, page 198, problems 2, 15, 19, 21.

Appendix C, page 625, problems 2, 8.

MAT2051 Discrete Mathematics

Unit 5 Assignment 2

Algorithms and Time Complexity

In algorithm development, the time and space required for algorithm completion is paramount. As users, we know that when a computer process takes too long, we try to avoid it. This truth encourages all IT and computer-based companies to produce faster products and services.

For this assignment, write a one- to two-page paper that includes all required algorithms and pseudocode describing the time and space complexity of algorithms. Include the following:

Answer the following questions:

What is time complexity?

What is space complexity?

Compare and contrast polynomial time algorithms and nondeterministic polynomial (NP) time algorithms (one paragraph minimum).

Provide an example of an algorithm for each worst-case run times:

O( n).

O(nk). Note that this is called polynomial-time, where k is any number greater than 1.

NP-time.

Hint: Quick sort is an algorithm that runs in O(nlog n) time.

Review the Algorithms and Time Complexity Scoring Guide to understand how the assignment will be graded.

MAT2051 Discrete Mathematics

Unit 6 Assignment

Section 4.4, page 210, problems 6, 12.

Section 7.1, page 335, problems 2, 6, 20.

Section 7.2, page 347, problems 3, 6.

Section 7.3, pages 360–362, problems 3, 43.

MAT2051 Discrete Mathematics

Unit 7 Assignment 1

Section 8.1, page 382, problems 3, 10.

Section 8.2, pages 392–393, problems 3, 5, 21, 29.

Section 8.3, page 403, problem 5.

Section 8.4, page 410, problems 2, 7.

Section 8.5, page 414, problem 3.

MAT2051 Discrete Mathematics

Unit 7 Assignment 2

Graph Applications and the Traveling Salesperson

In the class discussions, we have talked about how the traveling salesperson (TSP) problem and how it can be modeled using graphs. We also looked at finding a minimum length in a graph as well as Hamiltonian cycles.

Graphs, graph algorithms and methods, and graph theory are integral to IT and computer science applications and coding. For this assignment, write a two- to three-page paper that responds to each of the following questions:

What is a Hamiltonian cycle?

What is a Euler cycle?

What is a minimum length Hamiltonian cycle?

Given a graph with n edges, what is the time complexity of finding a Euler path? Is this a polynomial time algorithm? Explain and show all work and the graph. Hint: Include the algorithm and pseudocode.

Given a graph with n edges, can one find a minimum Hamiltonian cycle (TSP) in polynomial time? Has anyone ever proved that a polynomial time algorithm does not exist for this problem? Explain your answers and show the graph. Hint: Consider NP complete problems.

Offer one example of an IT or computer application that can be modeled as the TSP problem. This must be at least one paragraph.

Your calculations and work must be shown. Include references to any resources you use to complete the assignment.

Review the Graph Applications and the Traveling Sales Person Scoring Guide to understand how the assignment will be graded.

MAT2051 Discrete Mathematics

Unit 8 Assignment

Section 9.1, pages 443–445, problems 3, 16, 33.

Section 9.2, pages 449–450, problems 3, 8, 34.

Section 9.3, page 457, problems 3, 9.

Section 9.4, page 463, problems 3, 8.

Section 9.5, page 470, problem 2.

Section 9.6, pages 476, problem 5.

MAT2051 Discrete Mathematics

Unit 9 Assignment 1

Section 9.7, page 482, problems 3, 13.

Section 10.1, page 510, problem 2.

Section 10.2, page 518, problems 5, 9.

Section 10.3, page 522, problems 2, 8.

Section 10.4, page 527, problems 5, 11.

MAT2051 Discrete Mathematics

Unit 9 Assignment 2

Linear Programming, Reduction, and Max Flow Networks

In the past few units, you have learned about many discrete math and computer science optimization problems, including min cut, max flow; shortest paths; minimum spanning trees; and matching. Each of these optimization problems can be rephrased or rewritten as an equivalent linear programming problem. A linear programming problem consists of an objective (that is, a value to be maximized or minimized) and constraints.

Each of the graphical optimization problems discussed in this class can be rephrased as a linear programming problem by altering the objective or the constraints to refit the problem at hand. Another way to use a linear program to solve an optimization problem is to transform a new problem into a problem for which we already have a linear program solution—this is a reduction. The idea is that you already have a solution for a known linear programming problem. If you can somehow transform a new problem that you have into this known linear programming problem, you already have the solution. The tricky part is to figure out how to transform your problem into a known solution problem.

For this assignment, read the Notes section on page 529 of your textbook. There is a linear program on this page that describes finding a maximal flow in a network G, with a source a, a sink z, flows F, and capacities C. If we want to find a solution to a different problem, maybe the matching problem, for example, we could (1) formulate a linear program for the matching problem or (2) transform the matching problem into a maximal flow problem, then use the already known linear program that solves the maximal flow problem.

To better understand linear programs and reductions, write a two- to three-page paper that addresses the following questions:

What is a linear program? Explain in at least one paragraph. Feel free to show an example.

What are constraints in linear programming problems? Offer at least one example.

What is an optimization problem? Offer an example and explain.

What is a reduction (specifically, changing one problem into another)? Provide an example. You may use the Internet to locate an example.

Given Example 10.4.4 and Theorem 10.4.5 in the textbook, explain how you would transform the matching problem into a maximal flow problem.

Once you complete question 5, use the already known linear program that solves the maximal flow problem. Show all of your work and how you are doing the reduction.

Show all of your work and include references for resources you use to complete the assignment.

Hint 1: Transform the matching problem into a matching network, and then find the maximal flow to this network.

Hint 2: The goal here is to learn that, while problems might appear different, they are often the same. Knowing how to transform a new problem into a known problem can save a lot of solving time. Use the Internet and your textbook.

Review the Linear Programming, Reduction, and Max Flow Networks Scoring Guide to understand how the assignment will be graded.

MAT2051 Discrete Mathematics

Unit 2 Quiz 1

Question 1What is a set?

Answers:

a. An unordered collection of objects.

b. An ordered collection of objects.

c. The study of reasoning.

d. A partition of numbers.

Answer Feedback: .

Question 2What is the cardinality of the set X = {1, 5, 3, 8, 10}?

Answers:

a. 5.

b. 1.

c. 10.

d. 27.

Question 3 What value replaces ?in the following truth table?

Answers:

a. 0.

b. 1.

c. Cannot solve with the given information.

d. Can be either 0 or 1.

Question 4Let:

P: Jerry receives a scholarship.

Q: Jerry goes to college.

Assume the statement P → Q is true.

If Jerry does not go to college, did he receive his scholarship?

Answers:

a. Yes, because the converse of the statement is true.

b. No, because the contrapositive of the statement is true.

c. There is not enough information.

d. Can be either.

Question 5 What is deductive reasoning?

Answers:

a. A hypothesis together with a conclusion.

b. Valid arguments of a hypothesis.

c. The process of drawing a conclusion from a sequence of propositions.

d. A simplification of the rules of inference.

MAT2051 Discrete Mathematics

Unit 4 Quiz2

Question 1 How many different eight-bit strings begin with 100?

Answers:

a. 4.

b. 32.

c. 64.

d. 16.

Answer Feedback: .

Question 2How many strings can be formed using the letters in the word router (that is, R-O-U-T-E-R)?

Answers:

a. 6!/2!

b. C(6, 1).

c. (6 1)!

d. C(1, 6).

Question 3 There are 100 processors, 30 of which are defective. If you select 20 microprocessors from these 100 microprocessors, what is the probability that you select no defective processors?

Answers:

a. C(100, 10)/C(30, 20).

b. C(100, 20).

c. C(100, 20)/C(70, 20).

d. C(70, 20)/C(100, 20).

Question 4 What is the probability of drawing a queen from a standard deck of cards?

a. 2/52.

b. 10%.

c. 8/52.

d. 4/52.

Answer Feedback: .

Question 5 Assume the probability of having a boy or a girl is the same. If a family has five children, what is the probability that they are all boys?

Answers:

a. 1/32.

b. 1/16.

c. 1/2 + 1/2 + 1/2 + 1/2 + 1/2.

d. 1/2.

MAT2051 Discrete Mathematics

Unit 6 Quiz 3

Question 1 How many times does the computer print the string “Hello”?

i = 2

while (i < 4) {

print (“Hello”)

i = i + 1}:

Answers:

a. 1.

b. 2.

c. 3.

d. 4.

Question 2Which of the following is O(n)?

Answers:

a. 3n + 1.

b. n * log(n).

c. n * n + n.

d. None of the above.

Question 3 If each of the following describes the run time of an algorithm, which of the following could have the longest run time?

Answers:

a. O(nlog(n)).

b. O(n!).

c. O(n/2).

d. O(n * n).

Question 4What does the following algorithm return?

f(n){

if (n< 2)

return 1

else

return f(n – 1) * n:

Answers:

a. n!

b. The maximum divisor of n.

c. (n – 1)!

d. n 2.

.Question 5 Given that S_n denotes the number of n-bit strings that do not contain the pattern 00, what are the initial conditions?

Answers:

a. S_1 = 2, S_2 =3.

b. S_1 = 1, S_2 =2.

c. S_1 = 0, S_2 =2.

d. None of the above.

MAT2051 Discrete Mathematics

Unit 8 Quiz 4

Question 1 Is a graph a tree? Is a tree a graph?

a. Yes, Yes.

b. No, Yes.

c. Yes, No.

d. No, No.

Question 2Given a graph with n vertices, what is the minimum number of edges needed to make the graph connected?

Answers:

a. n.

b. n – 1.

c. n * n.

d. n log n.

Question 3Given the graph below, what type of path is path (A, D, E, C, B)?

Graph A-E. [D]

Answers:

a. Simple Path.

b. Cycle.

c. Simple cycle.

d. None of the above.

Question 4 Given the graph below, which of the following is a Hamiltonian cycle?

Answers:

a. (A, D, B).

b. (A, D, B, C, E, D, A).

c. (B, C, E, D, A, B).

d. (C, E, D, A, C).

Question 5 Given the graph below, what is the total weight of the shortest weighted path from A to E:

Answers:

a. 8.

b. 5.

c. 4.

d. 3.

MAT2051 Discrete Mathematics

Unit 10 Quiz 5

Question 1Given an unordered list of n numbers, what algorithm would you use to sort it, and what is the worst-case runtime of the algorithm?

Answers:

a. Tournament sort, O(n log n).

b. Tournament sort, O(n).

c. Prim’s Algorithm, O(n log n).

d. Prim’s Algorithm, O(n * n).

Question 2Given a graph with n vertices, what is the minimum number of edges needed such that the graph is connected?

Answers:

a. n.

b. n – 1.

c. n * n.

d. n log n.

Question 3Which is a minimal spanning tree of the following graph:

Graph A-E.[D]

Answers:

a. A-B-D-E-C.

b. A-D-E-C-B.

c. A-B-D.

d. There is no minimal spanning tree.

Question 4How many six-bit strings begin with 100?

Answers:

a. 4.

b. 8.

c. 32.

d. 16.

MAT 2051 Discrete Mathematics Full Course Tasks

Question 5If you select 5 microprocessors from 100 microprocessors, where 30 of the 100 are defective, what is the probability that you select no defective processors?

Answers:

a. C(100, 10)/C(30, 5).

b. C(70, 5)/C(100, 5).

c. C(100, 5).

d. C(100, 5)/C(70, 5).

Click here to ORDER an A++ paper from our Verified MASTERS and DOCTORATE WRITERS: MAT 2051 Discrete Mathematics Full Course Tasks

APA Writing Checklist

Use this document as a checklist for each paper you will write throughout your GCU graduate program. Follow specific instructions indicated in the assignment and use this checklist to help ensure correct grammar and APA formatting. Refer to the APA resources available in the GCU Library and Student Success Center.

Check Out Also: MAT 2051 Unit 1 Discussion DQ1 Logic and Reasoning

☐ APA paper template (located in the Student Success Center/Writing Center) is utilized for the correct format of the paper. APA style is applied, and format is correct throughout.

☐ The title page is present. APA format is applied correctly. There are no errors.

☐ The introduction is present. APA format is applied correctly. There are no errors.

☐ Topic is well defined.

☐ Strong thesis statement is included in the introduction of the paper.

☐ The thesis statement is consistently threaded throughout the paper and included in the conclusion.

☐ Paragraph development: Each paragraph has an introductory statement, two or three sentences as the body of the paragraph, and a transition sentence to facilitate the flow of information. The sections of the main body are organized to reflect the main points of the author. APA format is applied correctly. There are no errors.

☐ All sources are cited. APA style and format are correctly applied and are free from error.

☐ Sources are completely and correctly documented on a References page, as appropriate to assignment and APA style, and format is free of error.

Scholarly Resources: Scholarly resources are written with a focus on a specific subject discipline and usually written by an expert in the same subject field. Scholarly resources are written for an academic audience.

Examples of Scholarly Resources include: Academic journals, books written by experts in a field, and formally published encyclopedias and dictionaries.

Peer-Reviewed Journals: Peer-reviewed journals are evaluated prior to publication by experts in the journal’s subject discipline. This process ensures that the articles published within the journal are academically rigorous and meet the required expectations of an article in that subject discipline.

Empirical Journal Article: This type of scholarly resource is a subset of scholarly articles that reports the original finding of an observational or experimental research study. Common aspects found within an empirical article include: literature review, methodology, results, and discussion.

Adapted from “Evaluating Resources: Defining Scholarly Resources,” located in Research Guides in the GCU Library.

☐ The writer is clearly in command of standard, written, academic English. Utilize writing resources such as Grammarly, LopesWrite report, and ThinkingStorm to check your writing.