Colorado Technical University Virtual Campus: Multimedia Printable Version

https://campus.ctuonline.edu/

…
t=Course%20Materials:%20MATH203-1402B-04%20:%20Applications%20of%20Discrete%20Mathematics
[6/16/2014 1:47:33 AM]
Phase 5 – Task 2
Task Type:
Individual Project
Deliverable Length:
5 Parts Total: See Assignment Details
Points Possible:
250
Due Date:
6/23/2014 11:59:59 PM
Weekly tasks or assignments (Individual or Group Projects) will be due
by
Monday and late submissions will be
assigned a late penalty in accordance with the late penalty policy found in the syllabus. NOTE: All

submission posting
times are based on midnight Central Time.
Task Background:
This assignment is to include a revised version of parts I-IV from week 4, plus Part V, described
below. In part V, you are asked to demonstrate the procedures of data-processing algorithms and

discuss their runtime.
Parts I-IV
Review and revise your Week 4 Individual Project as needed based on comments from your instructor.

NOTE: Submit
these parts again even if you made no changes were necessary from the previous project.
Part V
Algorithm Analysis
Consider searching algorithms on the following array of data:
[22 21 9 4 16 2 10 14 20 31 26 19 17 28 8 13]
Suppose you want to implement a searching algorithm to see if the data set contains the number 19.
Demonstrate how the search would go if you used:
A sequential search
A binary search
State the runtime for each of the searches, in this example, and for general data sets of size
n
. Address the
issue of the order of the data in binary searching.
Suppose an algorithm that processes a data set of size 8 has a runtime of 72. The same algorithm has a
runtime of 110 when applied to a data set of size 10; and when applied to a data set of size 20, it has a
runtime of 420. Using big-O notation, state the runtime for this algorithm for the general case of a data

set of
size
n
.
Suppose you develop an algorithm that processes the first element of an array (length of
n
), then processes
the first 2 elements, then the first 3 elements, and so on, until the last iteration of a loop, when it

processes
all elements. Thus, if n = 4, the runtime would be 1 + 2 + 3 + 4 = 10.
Create a table that depicts the runtime for arrays of length 1 to 10. Would you expect the general
runtime to be O(
n
), O(
n
2
), O(
n
3
), or some other function of
n
? Explain.
Please submit your assignment.
Click on
Student Expectations
to view the expectations for this assignment.
For assistance with your assignment, please use your text, Web resources, and all course materials.
Course Materials 1
Course Materials 2
Colorado Technical University Virtual Campus: Multimedia Printable Version

https://campus.ctuonline.edu/

…
t=Course%20Materials:%20MATH203-1402B-04%20:%20Applications%20of%20Discrete%20Mathematics
[6/16/2014 1:47:33 AM]
Course Materials 3
Presentation
Logic and Set Theory
Set theory, logic, and mathematical notation are integral aspects in the study and application of

computer science. From
database design to Internet technologies, the use of concise mathematical notation, set notation and

set theory, and logical
constructs assists teams of developers in communication, specification, and design planning. Design

teams work together with
clients to develop specification documents. Development teams start and conclude the development

process and continue
communications with their clients throughout the design term. With the use of appropriate

mathematical tools, this design
process can be disambiguated, clarified, and successfully concluded.
Working With the Client
Computer science development teams work together with their clients to understand, clarify, and

specify the intended
deliverable product. For example, an academic institution may wish to store, organize, and retrieve

information about its
students in a database. This type of student information might include details such as the student’s

personal information,
including name and address; the student’s scholastic information, such as GPA and major; and the

student’s status
information, such as class and exam completions. While working together to define client specifications

and requirements, it
is often necessary to use mathematical tools such as set theory; set notation; logic; and related

decision-making tools, such
as truth tables.
Developing a Specification Document
While working with a client, it is often very helpful to create a formal specification document that

includes all of the client’s
requirements. To create a nonambiguous specification document, mathematical notation, logic, and set

theory can be utilized.
For example, a complete list, or set, of items to be included in the database can be generated. This set

of items now falls
under the properties of set theory. Each item in the set can have its own set of attributes. These sets

might be disjoint or
may have a nonempty intersection. Details such as these can be reviewed and displayed with the use of

Venn diagrams and
other logical tools. Decisions can then be made about these items and how they will relate to each

other within the database
system. Such decisions can be tested and analyzed with the use of Boolean algebra and set operations.
Starting the Design Process
Once the client has agreed on a specification document and is satisfied with the development plan, the

computer science
team can begin the project development. Project planning is a key step in the development of a new

tool or technological
application. Planning a project requires clear notation, concise definitions, attention to detail, and

logical decision making.
Mathematical notation and set theory can allow project requirements to be demonstrated in a

nonambiguous and logic-based
manner. Sets can be manipulated with set theory and related mathematical rules, so they can be used in

conjunction with a
Venn diagram, truth tables, and other set structures. For example, when designing a database, many

items in the database
might be related to each other in different logical ways. These relationships can be analyzed using set

and logical tools and
notations.
Communicating With the Client During Development
Client communication and review is paramount in the development of an application or database tool.

The use of concise
logical and mathematical notation combined with set notation and set theory will largely assist in the

clear communication
and cooperation with the client. Set diagrams will allow the client to visualize his or her requirements

and to make necessary
adjustments and changes. Logical and set theory rules will allow for the testing and manipulation of the

application or
database to ensure its full desired functionality, durability, and robustness. Mathematical notations

support clearer
specification, communication, development, maintenance, and future alteration.
Presentation
Graphs and Trees
Graphs and Trees
One of the most powerful tools in data analysis, organization, and storage is visualization. From

designing the specifications
of a database to illustrating the relationships between the contained data types, graphing and related

visual tools are an ideal
mechanism. While datasets and databases can often contain immense amounts of interrelated data,

graphical visualization
can offer considerable simplification and can improve both comprehension and subsequent

communication.
Understanding Graphs
While the word
graph
has adopted many meanings, it has a specific meaning in the context of discrete mathematics and
mathematics in general. A graph can be thought of as a collection of points that can be connected to

each other. This basic
definition encompasses many types of familiar graphs, such as the graph of a line; the graph of a

quadratic equation, namely
Colorado Technical University Virtual Campus: Multimedia Printable Version

https://campus.ctuonline.edu/

…
t=Course%20Materials:%20MATH203-1402B-04%20:%20Applications%20of%20Discrete%20Mathematics
[6/16/2014 1:47:33 AM]
a parabola; a scatter plot; or a bar graph.
Graph of a Line (Linear Graph)
Quadratic Graph (Parabola)
Scatter Plot
Colorado Technical University Virtual Campus: Multimedia Printable Version

https://campus.ctuonline.edu/

…
t=Course%20Materials:%20MATH203-1402B-04%20:%20Applications%20of%20Discrete%20Mathematics
[6/16/2014 1:47:33 AM]
However, this definition can also be relaxed and extended into a generalized definition for a

mathematical graph. By
definition, a graph simply contains vertices and edges. Vertices can be points or can contain textual or

numerical meaning.
The edges that connect the vertices can be lines, can also be weighted or valued, and can specify

direction. For example,
data in a database can be contained within the vertices of a graph. Then, these vertices can be

connected using edges to
show the relationships between the data. If the edges are weighted, this might signify value or cost in

the relationship. Maps
are a good example of graphs because the cities are the vertices and the weighted edges connecting

the cities specify
distance and accessibility.
Understanding Trees
A
tree
, in mathematical terms, is a special type of graph. Often, especially in a database system, hierarchical

relationships
exist between certain data types. For example, in an educational institution, the administrative

hierarchy might include a
president at the top, then a vice president, then perhaps administrative assistants, then professors and

staff, and then
students. While these relationships can be displayed using a basic graph, they can be more accurately

illustrated using a
tree.
Colorado Technical University Virtual Campus: Multimedia Printable Version

https://campus.ctuonline.edu/

…
t=Course%20Materials:%20MATH203-1402B-04%20:%20Applications%20of%20Discrete%20Mathematics
[6/16/2014 1:47:33 AM]
Figure: A hierarchical structure represented by a tree (a tree is a specialized type of graph)
Trees are graphs that have exactly one top vertex, or root. This root would represent the top level of

the hierarchy. Next, the
root has vertices connected to it known as
children
. These children are connected to the root with directed edges that always
point from the root downward. This notion is continued as the children have children of their own until

the tree ends. Trees,
like graphs in general, are powerful tools in the visualization of data and numerical relationships.
Traversing, Searching, and Sorting
Both graphs and trees offer further functionality beyond visualization. Once data are placed in either a

graph or tree format,
data can be searched, sorted, and traversed with significantly greater ease and organization. Within the

area of computer
science, there are well-known computer algorithms that can traverse or travel through a tree or graph.

Similarly, there are
algorithms that can search for a data item within a graph or tree or can sort items using a graph or

tree. These methods are
invaluable when utilizing a database for organizing and analyzing information. For example, once a

database is developed
and contains related data, a user may want to extract information from the database in an orderly

fashion. As such, the user
would want to search the database and then display the results as a sorted list. This type of application

is best accomplished
by storing the data into either trees or graphs and then using
search
and
sort
algorithms to return the desired results.
Article
Purpose of Measuring Variables
Measurement refers to the assignment of numbers to various psychological and/or social properties of

persons and groups
according to rules for the purpose of differentiating between them. Variables are quantities that

assume more than one value
and may be discrete, continuous, dependent, or independent. Examples are, gender, race, religion

affiliation, political
affiliation, income, age, ethnicity, education, nationality, and occupations. These examples are

attitudinal variables and may
be assigned different values. Thus, research efforts to describe persons and at the same time

differentiate among them
according to the above variables and other characteristics involve measurement.
Measurement has many functions, such as the following:
Describing social and psychological phenomena empirically
Helping to
differentiate among people according to various properties they possess
Rendering data amenable to some kind of statistical manipulation or treatment
Assisting in hypothesis testing and theory verification
Conceptualization of social and psychological phenomena refers to exploratory and descriptive studies

of phenomena, which
depict both social settings and characteristics of persons in those settings.
When differentiating among people according to properties they possess, the differences may be either

great or small,
depending on the variables or characteristics examined, which may include age, educational attainment,

morale, stress and
burnout, job satisfaction, and attitudes toward supervision.
Rendering data amenable to statistical treatment involves transforming collected data into numerical

quantities and
then
applying various statistical tools and effectively and precisely analyzing the data.
Hypothesis testing involves the process of determining the truthfulness or falsity of any speculative

statement. The
statements are usually derived from a theory and most frequently involve statistical tests. In other

words, hypothesis testing
is the use of statistics to determine the probability that a given testable statement (the hypothesis) is

true or false.
Testing a hypothesis to determine the result takes the following four major steps:
1
.
The formulation of a null hypothesis and an alternative hypothesis
2
.
The identification of test statistics and the null hypothesis
3
.
The computation of the
p
-value (the probability of getting a result which is closely similar to that which was actually
observed with the assumption that the null hypothesis is true)
4
.
The comparison of the
p
-value to an acceptable significance value
If the observed effect is statistically significant, the null hypothesis is ruled out, making the alternative

hypothesis valid.
For example, researchers proceed in their inquiry by theorizing about events such as why some

students hate mathematics in
school. Later, researchers provide possible explanations as to why these students hate mathematics in

school, and the
explanations are translated into hypotheses. The hypothesis is the statement of the relationship

between an event and an
explanation of it. Such statements could be:
The less exposure the students have at their earlier stage in college, the more
dislike they will have for mathematics
. A
test of hypotheses
is a
test of theory
. Once the tested hypotheses are supported by
the data collected, the theory from which the hypotheses were drawn is also supported.
Hypotheses Results
Whenever hypotheses in one’s research are tested, it is usually the case that several hypotheses are

either confirmed or
refuted. Outcomes of hypothesis tests depend on many factors, including theory adequacy,

representativeness of the sample,
type of respondent involvement, the validity and reliability of measuring instruments, and statistical

sophistication. Data-
collection procedures also influence the quality of data obtained as well as hypothesis test results.

With the result from the
tests, subsequent investigations of the same or similar phenomena are ordinarily recommended because

single studies are
rarely conclusive about variable interrelationships.
Colorado Technical University Virtual Campus: Multimedia Printable Version

https://campus.ctuonline.edu/

…
t=Course%20Materials:%20MATH203-1402B-04%20:%20Applications%20of%20Discrete%20Mathematics
[6/16/2014 1:47:33 AM]
Article
FAQ: Graphs and Trees
Question 1: What is a mathematical tree?
Answer 1:
A mathematical tree is a specialized type of graph. A graph has vertices and edges that form paths

between the
vertices. A tree is a connected graph that does not contain any cycles. Within a tree, there is a path

from a vertex to
another vertex, and there can be no cycles. Once a path leaves a vertex, it cannot return to that

vertex.
Example of a tree
Example of a graph that is not a tree
Notice that this graph has a cycle, which is not permitted in a tree. In addition, the graph is not

connected; there is no way
to reach vertex 6 from any other vertex. Although this is permissible within graphs, it is not within

trees.
Question 2: How are trees and graphs similar and different?
Answer 2:
Trees and graphs are similar because they both contain vertices and edges that can attach those

vertices. Both
trees and graphs can be directed, meaning that the edges have a specified required direction

associated with them. Both
graphs and trees can have weighted edges, meaning that the edges have value or cost associated with

them. In fact, all
trees are graphs, but not all graphs are trees. To be a tree, a graph must be connected and must not

contain any cycles. It is
important to note that a tree must have exactly one fewer edges than vertices. If a graph has the same

number of edges
and vertices, it has a cycle and cannot be a tree. If a graph has two fewer edges than vertices, it is not

connected and
cannot be a tree.
Question 3: Do all trees require a root?
Answer 3:
In general, trees are thought of as having a root or a starting vertex, but this is not a strict

requirement. Trees
without a root vertex are said to be
free
. Free trees do not have a designated root vertex but by definition may still appear

PLACE THIS ORDER OR A SIMILAR ORDER WITH US TODAY AND GET AN AMAZING DISCOUNT