Capella MAT2051 All Assignments Latest 2019 October

MAT2051 Discrete Mathematics

Unit 1 Assignment 1

Graded Problem Set

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

Graded Problem Set

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 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.

 

 

 

 

 

MAT2051 Discrete Mathematics

Unit 3 Assignment 1

Graded Problem Set

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 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

Graded Problem Set

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 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

Graded Problem Set

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 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

Graded Problem Set

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 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

Graded Problem Set

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 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

Graded Problem Set

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 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

Graded Problem Set

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 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.