-
Notifications
You must be signed in to change notification settings - Fork 36
/
A06-binary.html
131 lines (125 loc) · 4.5 KB
/
A06-binary.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-type" content="text/html;charset=UTF-8">
<title>Assignment 06: Tree Sort</title>
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
<style>
body {
font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', 'Ubuntu', 'Droid Sans', sans-serif;
font-size: 14px;
line-height: 1.6;
}
</style>
</head>
<body>
<h1 id="Assignment-06-Tree-Sort">Assignment 06: Tree Sort</h1>
<p>For this assignment you will be implementing and analyzing Tree Sort.</p>
<h2 id="The-Algorithm">The Algorithm</h2>
<p>Using a BST to sort an array of elements.</p>
<p>The steps to perform tree sort are:</p>
<ol>
<li>Insert all of the elements in the array into a BST</li>
<li>Traverse the tree, placing each element back into the array in sorted order.</li>
</ol>
<p>Input constraints:</p>
<p>Let [A = {x \in \mathbb{Z} | -10,000 \leq x \leq 10,000}].</p>
<p>Some pseudocode:</p>
<pre><code class="language-python"><div><span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">treesort</span><span class="hljs-params">(A)</span> -> <span class="hljs-keyword">None</span>:</span>
tree = BST()
<span class="hljs-comment"># Insert all of the elements into a BST</span>
<span class="hljs-keyword">for</span> element <span class="hljs-keyword">in</span> A:
tree.insert(element)
<span class="hljs-comment"># Traverse the tree replacing elements in A</span>
i = <span class="hljs-number">0</span>
<span class="hljs-keyword">for</span> element <span class="hljs-keyword">in</span> A.traverse():
A[i] = element
i += <span class="hljs-number">1</span>
</div></code></pre>
<h2 id="Instructions">Instructions</h2>
<p>This assignment will be hosted on Github Classroom.</p>
<ol>
<li>Register for the assignment on our Github Classroom using <a href="https://classroom.github.com/a/9gBhRcA_">this link</a>
<ol>
<li>Be sure to select your name from the list to link your Github to the class roster!</li>
</ol>
</li>
<li>Clone the repository to your machine
<ol>
<li>Open a terminal</li>
<li>Navigate to your algorithms folder</li>
<li>Go to the parent directory (<code>cd ..</code>)</li>
<li>Clone the repository to this location (<code>git clone <your repository link here></code>)
<ol>
<li>Be sure to use the link for <strong>your copy</strong> of the repository for the assignment</li>
</ol>
</li>
</ol>
</li>
<li>Getting things in order
<ol>
<li>Open your new folder in VS Code</li>
<li>Begin by creating a new file <code>source/Sorts/tree.cpp</code>
<ol>
<li>Within this file, create the definition for the sorting algorithm.</li>
</ol>
</li>
<li>Check that you can compile and run the unit tests for Tree Sort (<code>make tree</code>)</li>
<li>Ensure that your code compiled, ran, and failed the unit tests.</li>
<li>Commit and push your code</li>
<li>Check the online copy of your repository to make sure your changes were pushed successfully</li>
</ol>
</li>
<li>Implement the algorithm <strong>Commit and Push your work after each task</strong>
<ol>
<li>In the docstring for your function, write pseudocode to solve the problem</li>
<li>Commit and push your pseudocode</li>
<li>Implement the algorithm in C++</li>
<li>Pass all unit tests</li>
<li>Commit and push your work</li>
</ol>
</li>
<li>Analyze your work
<ol>
<li>Proceed line by line, noting runtimes for each action</li>
<li>Document your Best and Worst case analysis at the bottom of your docstring</li>
</ol>
</li>
<li>Submit your work
<ol>
<li>Commit and push all code to your assignment repository.</li>
</ol>
</li>
</ol>
<h2 id="Grading">Grading</h2>
<table>
<thead>
<tr>
<th>Criteria</th>
<th>Points</th>
</tr>
</thead>
<tbody>
<tr>
<td>Functionality</td>
<td>70</td>
</tr>
<tr>
<td>Analysis</td>
<td>20</td>
</tr>
<tr>
<td>Quality</td>
<td>10</td>
</tr>
</tbody>
</table>
<h2 id="Submission">Submission</h2>
<p>To submit this assignment, simply commit and push your work to your assignment repository.
Your last submission before the deadline will be graded.</p>
</body>
</html>