Computer Science 431

Spring 2015, The College of Saint Rose

Problem Set 4: Brute Force and Decrease and Conquer
Due: 11:59 PM, Thursday, March 12, 2015

You may work alone or in groups of size 2 or 3 on this assignment. Only one submission per group is needed.

Programming Task: Insertion Sort

Extend your sorting algorithm comparison program from the previous problem set to include options to use insertion sort. (5 points)

Use the extended code to perform an empirical analysis of insertion sort and add it to your document describing your empirical studies. (6 points)

Note: the code, empirical results, and analysis for bubble sort and selection sort that you submitted previously will not be graded. Instead, your grade for that part of the previous problem set will be determined by your updated submission. So fix it up!

Programming Tasks: Working with Highway Data

You worked a bit with the graph data representing highways in your first problem set. We will now return to that to start building a program in which you will implement several algorithms over the course of the rest of the semester.

Start with the skeleton of the program in /home/cs431/maps/ As you can see, this program reads in a .gra file, then enters an interactive loop where the user can perform a variety of operations on the graph.

Your tasks for this problem set:

Written Problems

  1. Levitin Exercise 3.3.3, p. 113 (5 points)
  2. Levitin Exercise 3.5.1, p. 128 (3 points)
  3. Levitin Exercise 3.5.4, p. 128 (3 points)
  4. Levitin Exercise 4.1.9, p. 137 (2 points)
  5. Levitin Exercise 4.4.8, p. 156-157 (6 points)


Before 11:59 PM, Thursday, March 12, 2015, submit your problem set for grading. To complete the submission, upload an archive (a .7z or .zip) file containing all required files using Submission Box under assignment "PS4".


This assignment is worth 60 points, which are distributed as follows:

> FeatureValueScore
Insertion sort implementation 5
Insertion sort section of empirical analysis 6
listPlaces method in Mapping 3
listConnections method in Mapping 3
Stats command in Mapping 12
PrintDepthFirst and PrintBreadthFirst commands 12
Exercise 3.3.3 5
Exercise 3.5.1 3
Exercise 3.5.4 3
Exercise 4.1.9 2
Exercise 4.4.8 6
Total 60