Algo lab/running times
ไปยังการนำทาง
ไปยังการค้นหา
- This is part of ske algo lab
เนื้อหา
Lab descriptions
- Work on this lab sheet.
- Write quadratic-time solutions to the following two problems.
- Download fast solutions.
- Measure their running times using provided test data and compare them.
Task 1: Closest pairs
Task statement
You are given a list of n integers. You want to find the minimum difference between pairs of these integers.
Input
- First line: integer n (n is at most 100,000)
- Next n lines: each line contains one integer (ranging from 1 to 1,000,000,000)
Output
- One line: the minimum difference between pairs of these integers.
Example
Input:
5 1 50 4 13 25
Output:
3
Your job
- Template for quadratic solution closest-slow-template.cpp
- Fast solution closest-fast.cpp
- Test data: see below
Task 2: Sorting
Task statement
You are given a list of n integers. You want to sort them in an increasing order.
Input
- First line: integer n (n is at most 100,000)
- Next n lines: each line contains one integer (ranging from 1 to 1,000,000,000)
Output
- n lines: the sorted list of integers
Example
Input:
5 1 50 4 13 25
Output:
1 4 13 25 50
Your job
- Template for quadratic solution sort-slow-template.cpp
- Fast solution sort-fast.cpp
- Test data: see below
Test data
- Download here