-
Notifications
You must be signed in to change notification settings - Fork 36
/
A08-lexicographic.html
96 lines (91 loc) · 3.63 KB
/
A08-lexicographic.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
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-type" content="text/html;charset=UTF-8">
<title>Assignment 10: Lexicographic String Sorting</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-10-Lexicographic-String-Sorting">Assignment 10: Lexicographic String Sorting</h1>
<p>For this assignment you will be implementing an algorithm capable of sorting strings lexicographically.</p>
<h2 id="The-Algorithm">The Algorithm</h2>
<p>Lexicographic sorting is the process of sorting strings in alphabetic order.</p>
<blockquote>
<p>Hint: We have already constructed a fantastic data structure to accomplish this goal.</p>
</blockquote>
<h2 id="Example">Example</h2>
<p>sort(["abz", "abc"], 2) -> ["abc", "abz"]
sort(["ab", "ba", "aa"], 3) -> ["aa", "ab", "ba"]</p>
<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/rWxvtRFI">this link</a></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>)</li>
</ol>
</li>
<li>Getting things in order
<ol>
<li>Open your new folder in VS Code</li>
</ol>
</li>
<li>Implement the algorithm <strong>Commit and Push your work after each task</strong>
<ol>
<li>Locate the header file <code>lexicographic.hpp</code> under <code>Algorithms</code></li>
<li>In the docstring for your sorting algorithm, detail your pseudocode for accomplishing this task.</li>
<li>Under the signature <code>sort(String* arr[], int n)</code> implement a lexicographic sorting algorithm.</li>
<li>Analyze your work, providing the O(?) runtime.</li>
</ol>
</li>
<li>Submit your work (<code>git add . && git commit -m "Done" && git push</code></li>
</ol>
<h2 id="Grading">Grading</h2>
<table>
<thead>
<tr>
<th>Criteria</th>
<th>Points</th>
</tr>
</thead>
<tbody>
<tr>
<td>Functional Correctness</td>
<td>80</td>
</tr>
<tr>
<td>Analysis</td>
<td>10</td>
</tr>
<tr>
<td>Quality</td>
<td>10</td>
</tr>
</tbody>
</table>
<h2 id="Bonus">Bonus</h2>
<p>For this assignment, you may accrue an additional 25 bonus points by implementing the <code>Burstsort</code> algorithm, which is a slightly more advanced implementation of lexicographic sorting.</p>
<h3 id="Resources">Resources</h3>
<ul>
<li><a href="https://people.eng.unimelb.edu.au/jzobel/fulltext/acmjea04.pdf">The paper that introduced burtsort</a></li>
<li><a href="https://en.wikipedia.org/wiki/Burstsort">Wikipedia Entry</a></li>
</ul>
<h2 id="Submission">Submission</h2>
<p>Submissions are handled by Github Classroom.
Submissions after the deadline are not graded.</p>
</body>
</html>