ผลต่างระหว่างรุ่นของ "Algo lab/running times"
ไปยังการนำทาง
ไปยังการค้นหา
Jittat (คุย | มีส่วนร่วม) |
Jittat (คุย | มีส่วนร่วม) |
||
| (ไม่แสดง 9 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน) | |||
| แถว 1: | แถว 1: | ||
: ''This is part of [[ske algo lab]]'' | : ''This is part of [[ske algo lab]]'' | ||
| + | |||
| + | == Lab descriptions == | ||
| + | |||
| + | * Work on this [https://theory.cpe.ku.ac.th/wiki/images/Algo-lab-running-time.pdf 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 1: Closest pairs == | ||
| − | {{กล่องสี|# | + | {{กล่องสี|#e7e7e7| |
'''Task statement''' | '''Task statement''' | ||
| แถว 10: | แถว 17: | ||
'''Input''' | '''Input''' | ||
| − | * First line: integer '''n''' | + | * 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) | * Next '''n''' lines: each line contains one integer (ranging from 1 to 1,000,000,000) | ||
| แถว 17: | แถว 24: | ||
* One line: the minimum difference between pairs of these integers. | * One line: the minimum difference between pairs of these integers. | ||
| + | '''Example''' | ||
| + | |||
| + | Input: | ||
| + | <pre> | ||
| + | 5 | ||
| + | 1 | ||
| + | 50 | ||
| + | 4 | ||
| + | 13 | ||
| + | 25 | ||
| + | </pre> | ||
| + | |||
| + | Output: | ||
| + | <pre> | ||
| + | 3 | ||
| + | </pre> | ||
}} | }} | ||
| + | |||
| + | === Your job === | ||
| + | * Template for quadratic solution [https://theory.cpe.ku.ac.th/~jittat/algo-lab/running-times/closest-slow-template.cpp closest-slow-template.cpp] | ||
| + | * Fast solution [https://theory.cpe.ku.ac.th/~jittat/algo-lab/running-times/closest-fast.cpp closest-fast.cpp] | ||
| + | * Test data: ''see below'' | ||
== Task 2: Sorting == | == Task 2: Sorting == | ||
| + | |||
| + | {{กล่องสี|#e7e7e7| | ||
| + | '''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: | ||
| + | <pre> | ||
| + | 5 | ||
| + | 1 | ||
| + | 50 | ||
| + | 4 | ||
| + | 13 | ||
| + | 25 | ||
| + | </pre> | ||
| + | |||
| + | Output: | ||
| + | <pre> | ||
| + | 1 | ||
| + | 4 | ||
| + | 13 | ||
| + | 25 | ||
| + | 50 | ||
| + | </pre> | ||
| + | }} | ||
| + | |||
| + | === Your job === | ||
| + | * Template for quadratic solution [https://theory.cpe.ku.ac.th/~jittat/algo-lab/running-times/sort-slow-template.cpp sort-slow-template.cpp] | ||
| + | * Fast solution [https://theory.cpe.ku.ac.th/~jittat/algo-lab/running-times/sort-fast.cpp sort-fast.cpp] | ||
| + | * Test data: ''see below'' | ||
== Test data == | == Test data == | ||
| + | * Download [https://theory.cpe.ku.ac.th/~jittat/algo-lab/running-times/testdata/ here] | ||
รุ่นแก้ไขปัจจุบันเมื่อ 00:56, 3 กันยายน 2561
- 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
