Algorithms and OOD (CSC 207 2013F) : Assignments
Primary: [Front Door] [Schedule] - [Academic Honesty] [Disabilities] [Email] [FAQ] [IRC] [Teaching & Learning]
Current: [Assignment] [EBoard] [Lab] [Outline] [Partners] [Reading]
Sections: [Assignments] [EBoards] [Examples] [Handouts] [Labs] [Outlines] [Partners] [Readings]
Reference: [Java 7 API] [Java Code Conventions]
Related Courses: [CSC 152 2006S (Rebelsky)] [CSC 207 2013S (Walker)] [CSC 207 2011S (Weinman)]
Misc: [SamR] [Glimmer Labs] [CS@Grinnell] [Grinnell] [Issue Tracker (Course)] [Issue Tracker (Textbook)]
This assignment is currently in draft form.
Due: 10:30 p.m., Tuesday, 5 November 2013
Summary: In this assignment, you will explore the implementation of sorting algorithms.
Purposes: To help you better understand the core sorting algorithms. To improve your facility with Java lists and list iterators.
Collaboration: I encourage you to work in groups of size two or three, although you may also work alone. You may discuss this assignment with anyone, provided you credit such discussions when you submit the assignment.
Wrapper (Prologue): Individually read through this assignment and make sure that you understand what is required. Then use the form available at http://bit.ly/207hw8pro to indicate (a) how long you think this assignment will take and (b) what you think will be the most challenging aspect of this assignment.
Wrapper (Epilogue): When you are done with the assignment, fill out the form available at http://bit.ly/207hw8epi to indicate (a) how long the assignment took, (b) what the most challenging part of the assignment was, and (c) something important you learned from doing the assignment. If you find that the assignment took much less or much more time than you expected, also include (d) a note as to what might have led to that difference.
Submitting:
Please put all of your work in a GitHub repository named
csc207-hw8
. Email me the address of that repository.
Please title your email “CSC207 2013F Assignment 8
(Your Names)”.
Warning: So that this assignment is a learning experience for everyone, we may spend class time publicly critiquing your work.
a. Fork the repository at https://github.com/Grinnell-CSC207/sorting.
b. Clone the repository to your local disk.
1. Write loop invariants for the primary loops in:
SelectionSorter.indexOfSmallest
,
SelectionSorter.sorti
,
Utils.merge
,
IterativeMergeSorter.sort
, and
Quicksorter.partition
. You should express your invariants
in text/math. If you'd like, you may also add ASCII art to help
explain the invariants.
Note that these loops may not yet exist (depending on where you stand in the various labs). That's okay. You should write invariants before writing loops anyway.
2. Finish the implementations of insertion sort, selection sort, recursive merge sort, iterative merge sort, and Quicksort over arrays.
3. Augment your code to count the number of swaps that the procedures
do. (This won't help with analyzing merge sort, but should help with
the rest.) You will likely want to add a counter to Utils
,
augment Utils.swap
to increment the counter, and perhaps
add methods to get and set that counter.
4. The Quicksort algorithm is supposed to do O(nlogn) swaps. Using the work from the previous problem, verify that claim experimentally.
5. We don't just want to sort arrays. We also want to sort lists.
Add a method declaration for an optional sorting method over
java.util.AbstractList
objects to our
Sorter
interface. Allow implementers to throw
an appropriate exception if they have not implemented this method.
6. It is, of course, possible to turn any array sorting method into
a list sorting method: Convert the list into an array, sort the array,
and turn it back into a list. Add this approach to
SorterBridge
>
7. Converting to arrays is inefficient. Hence, we often want to
reimplement our sorting algorithms over other types. Implement
recursive merge sort over lists. If you'd like, you may assume
that both the get
and set
methods are
implements.
8. Implement an in-place Quicksort over Java lists, using only
ListIterator
objects to access and change values.
Primary: [Front Door] [Schedule] - [Academic Honesty] [Disabilities] [Email] [FAQ] [IRC] [Teaching & Learning]
Current: [Assignment] [EBoard] [Lab] [Outline] [Partners] [Reading]
Sections: [Assignments] [EBoards] [Examples] [Handouts] [Labs] [Outlines] [Partners] [Readings]
Reference: [Java 7 API] [Java Code Conventions]
Related Courses: [CSC 152 2006S (Rebelsky)] [CSC 207 2013S (Walker)] [CSC 207 2011S (Weinman)]
Misc: [SamR] [Glimmer Labs] [CS@Grinnell] [Grinnell] [Issue Tracker (Course)] [Issue Tracker (Textbook)]
Copyright (c) 2013 Samuel A. Rebelsky.
This work is licensed under a Creative Commons Attribution 3.0 Unported License. To view a copy of this
license, visit http://creativecommons.org/licenses/by/3.0/
or send a letter to Creative Commons, 543 Howard Street, 5th Floor,
San Francisco, California, 94105, USA.