Description

COMP 3270 Programming Assignment 1 Asymptotic Analysis of Sorting Algorithms Solved

1. Overview

To empirically evaluate 4 sorting algorithms and verify their theoretical upper
bound. The sorting algorithms we will evaluate are: merge sort, quick sort,
insertion sort, and selection sort.

A starter code with helper functions and
implementations of 2 algorithms (selection sort and merge sort) has been
provided.

Your task is to implement the remaining two sorting algorithms
(quick sort and insertion sort) and perform the following empirical analyses.
You will run a specific algorithm on three different types of arrays – sorted,
random, or constant array of a given size n. The provided starter code will
generate the input arrays for your analysis.

The starter code will take as input three command line arguments in the following order:

1. Type of input array. You have three choices: ‘r’, ‘c’, and ‘s’ that
correspond to random, constant and sorted arrays, respectively. If
invalid values are given, it will default to a random input array.

2. Size of the array to generate and analyze. It must be a positive number
greater than zero. It will default to 10 if an invalid value is provided.

3. Sorting algorithm to use. You have four choices: ‘m’, ‘i’, ‘s’, and ‘q’ that
correspond to merge sort, insertion sort, selection sort, and quick sort,
respectively. If an invalid value is given, it will default to quick sort.

If an incorrect number of arguments are given or if an integer is not provided
for the second command line argument, it will default to running quick sort
on a random input array of size 10.

For stable computation of timing, the
starter code will run each algorithm three times and provides the median of
the three runs. For accurate timing, ensure that there are no other processes
running on the machine while you conduct your analysis. The output timing
will be in nanoseconds.

2. Deliverables:

There are two deliverables for this programming project: (i) the completed
code with the two sorting algorithms completed in the functions marked with
“TODO”, and (ii) a report with your analysis clearly marked with two sections
– “Results” and “Analysis.” More details about what is expected to be
presented in each section are provided below.

2.1 Results

Run each of the four sorting algorithms on constant, sorted, and random
arrays that are powers of 10. For each of the twelve cases, you should record
the following:
• Nmin: the smallest power of 10 array size that takes 20 milliseconds or
more per run to sort.

• Nmax: the largest power of 10 array size that takes 10 minutes or less
per run to sort (30 mins for all 3 runs), or the largest input size you can
successfully sort if no input took more than 30 minutes total.
• Tmin: the time to sort an array of size Nmin.

• Tmax: the time to sort an array of size Nmax.
You should report your results in a table. Your table should have 12 rows and
5 columns. Each row must have a label with 2 letters, where the first
corresponds to the algorithm (Merge, Quick, Insertion, or Selection) and the
second corresponds to the array type (Sorted, Random, or Constant).

For
example, SS corresponds to Selection sort run on a Sorted array. An
example table is shown below.

Note that the goal of this project is to find a Nmin and Nmax that are sufficiently
far apart that the growth rate of the time complexity can be approximated
using the timing and input size ratios.

The descriptions of Nmin and Nmax given
above are just to give you a reasonable idea of how to find good array sizes;
finding the exact value of Nmin that takes 20 milliseconds to run, for instance,
is not critical. You may have to check values of up to 1 billion to find Nmax.

2.2 Analysis

In this section, you will estimate the complexity of the four algorithms by
comparing the ratio between Tmin and Tmax to ratios representing the
complexity of the algorithm. Specically, you should compute f(Nmax) = f(Nmin)
for f1(n) = n, f2(n) = n ln(n), and f3(n) = n2

. You should round to the nearest
integer when computing these ratios. Finally, you should label each
experiment according to the ratio Tmax=Tmin most resembles.
For example, if you get Nmin= 10 and Nmax = 100, your ratios would be:

• f1(Nmax)/f1(Nmin) = 100/10
• f2(Nmax)/f2(Nmin) = (100*ln(100))/
(10*ln(10))
• f3(Nmax)/f3(Nmin) = 1002
/102

You should then label the algorithm based on which of these three ratios Tmax
= Tmin is closest to. As part of your report, you should create a table that
includes the computed ratios as well as the behavior of the algorithm (Linear,
n lg n, or Quadratic), across all 12 experiments.

An example is given below:
Your report should contain a summary of (1) how your results compare
to the theoretical analysis for all four algorithms, and (2) why your
results make sense or are surprising.

You should spend more time
explaining your results when they are unusual or unexpected.

COMP 3270 Programming Assignment 2 Graph Traversal Algorithms Solved

1. Overview

Imagine you are given a dataset that represents a social network, where
individuals are nodes in the graph, and their connections or friendships are
represented as edges in an edge list.

Your task is to analyze this social
network to extract valuable insights. The dataset is in the form of an edge
list. A visualization of the graph is shown below to help you.

Input:

An edge list file where each line represents a friendship connection between
two individuals, e.g., “N_0, N_1.”

Output:

A report with a table such as the one below that documents the length of the
shortest path between two individuals (or vertices) in this graph and the time
taken to find the path between the two nodes.

You must explore all pairs
indicated in the table and complete the table below for each of the following
algorithms. You should not include an entry if there are no paths between the
two nodes. Use the graph above to identify if the nodes have paths
connecting them.

Node 1 Node 2 BFS DFS
Distance Time (ms) Distance Time (ms)
N_0 N_1
N_0 N_2
N_0 N_3
N_0 N_4

N_0 N_5
N_0 N_6
N_0 N_7
N_0 N_8
N_0 N_9
N_0 N_10
N_0 N_11
N_0 N_12

N_0 N_13
N_0 N_14
N_0 N_15
N_0 N_16
N_0 N_17
N_0 N_18

N_0 N_19
N_0 N_20
N_0 N_21
N_0 N_22
N_0 N_23
N_0 N_24

You must explore the following algorithms. Breadth First Search (BFS) and
Depth-First Search (DFS). For each of the node pairs in the table, you must
run BFS/DFS with the start node as Node 1 and terminate the algorithm
when Node 2 is reached.

For example, to find the distance between N_0 and
N_1, the start node is N_0. The algorithm terminates when N_1 is visited or
“explored” by the algorithm. The distance is the total number of nodes visited
by the algorithm before reaching the target vertex.

Your report should also have a brief description of the data structure that you
will use to represent the graph and a short justification.

The goal of this assignment is to analyze how long it takes for BFS and DFS
to reach nodes at different depths.

Based on your experiments above, briefly answer the following questions with an example:

1. Suppose you want to find a path between nodes at a shallow depth to
your start node. Would you use BFS or DFS?
2. Suppose that the end node is at a very large depth from the start node.
Would you use BFS or DFS?