Transcribed TextTranscribed Text

Overview. The problems in this assignment must be written up in a Microsoft Word document. Remember to include your name and course number within the document that you submit. Problem 1. [4 points] Sorting: Read the assigned chapter and the notes for Week 7 located in the Learning Activities area, and then do the following problems: (a) [2 points] What is the big-O of the shellsort() function provided in Figure 7.6 on page 297? Briefly explain how you arrived at your answer. Remember big-O measures the worst case runtime scenario. (b) [2 points]. Both the Mergesort and the Quicksort algorithms will sort a list by portioning the list. Briefly explain how Mergesort differs from Quicksort when partitioning the list. Problem 2. [6 points] Graphs: Read the assigned chapter and notes for Week 8 located in the Learning Activities area, and then do the following problems: (a) [3 points] Draw the adjacency list for the following graph: Hint: Remember that links without arrows are considered bi-directional. (b) [3 points] Briefly explain the differences between dense and sparse graphs. When is if more feasible to use a linked representation for a graph over an adjacency matrix. Also, justify your answer using a mathematical definitions for sparse and dense graphs. Other Notes: Submit your solutions within a single document (e.g. MS Word) using the Problem Set 4 link provided in the Assignment area. As usual, please ask if you have questions in either the Ask the Instructor forums area or via e-mail.

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

Problem 1
From the provided implementation can be noticed that a key steps are the insertion sort and the number of performed insertion sorts. With respect to Big-O complexity must be explained that ShellSort with the provided increments performs hk insertion sorts on arrays of size N/hk. In the worst-case and average-case scenarios the insertion sort has quadratic running time (it is not the case here to have best-case behavior which would require only linear time). In order to make the computations easier it is assumed that N is a power of two (all increments but the last are even, while the last one is 1). Since the insertion sort has quadratic running time as Big-O, the total cost of ShellSort becomes O(hk* insertion_sort_running_time)=...

By purchasing this solution you'll be able to access the following files:

50% discount

$28.00 $14.00
for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Data Structures and Algorithms Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Upload a file
Continue without uploading

We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats