CpSc 2120: Algorithms and Data Structures Lab #7

CpSc 2120: Algorithms and Data Structures

Handout 10: Lab #7 Powers 208
1 Sweep Lines and the STL
This is a somewhat lighter lab (due Friday, not Sunday) with a goal of giving students a chance to
practice using the STL and also to implement a “sweep line” algorithm.
Input for this lab is provided in the file
/group/course/cpsc212/f21/hw02/lab7input.txt
The file describes a line of N students standing in a row. Each line of the file gives the name of a
student and their integer height. All names, and all heights are guaranteed to be distinct. Since
we are shooting for an O(N log N) running time, the value of N for the example file is 250,000.
We’ll be implementing the algorithm discussed in lecture that sweeps downward. In particular, the
main steps are:
- Read the input into a vector<pair<string,int>>, where the string
part is a student’s name and the int part is their height
- Build a second vector<pair<int,int>>> where the first part is height
and the second part is their index
- Sort the contents of this second vector (in order by height)
- For each student in decreasing order of height
- Add student to a balanced BST keyed on index (a set<int>)
- For each student, call the find method to get an iterator pointing
to their record in the set. Use ++ and -- (being careful not to
step out of bounds) to find the successor and predecessor of the
student
- Remember the longest line of sight you find.
- At the end, print the names of 2 students defining a longest line of
sight, as well as the distance between them
2 Submission and Grading
Code should be submitted electronically on on handin.cs.clemson.edu. we will be turning in all
of our work this semester. Zero points will be awarded for code that does not compile, so make sure
your code compiles on the lab machines before submitting! Final submissions are due by 11:59pm
on the evening of Friday, October 8. No late submissions will be accepted.
1