06 Feb The third and fourth posts are

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

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.

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. Although the problem sets are not graded they will help you prepare for the quizzes in this course.