81 lines
2.3 KiB
Plaintext
81 lines
2.3 KiB
Plaintext
CS 325-001, Analysis of Algorithms, Fall 2019
|
||
HW2 - Divide-n-conquer: mergesort, number of inversions, longest path
|
||
|
||
Due Monday Oct 7, 11:59pm (same submission instructions as HW1).
|
||
No late submission will be accepted.
|
||
|
||
Need to submit: report.txt, msort.py, inversions.py, and longest.py.
|
||
longest.py will be graded for correctness (1%).
|
||
|
||
To submit:
|
||
flip $ /nfs/farm/classes/eecs/fall2019/cs325-001/submit hw2 report.txt {msort,inversions,longest}.py
|
||
(You can submit each file separately, or submit them together.)
|
||
|
||
To see your best results so far:
|
||
flip $ /nfs/farm/classes/eecs/fall2019/cs325-001/query hw2
|
||
|
||
|
||
Textbooks for References:
|
||
[1] CLRS Ch. 2
|
||
|
||
0. Which of the following sorting algorithms are (or can be made) stable?
|
||
(a) mergesort
|
||
(b) quicksort with the first element as pivot
|
||
(c) quicksort with randomized pivot
|
||
(d) selection sort
|
||
(e) insertion sort
|
||
(f) heap sort --- not covered yet (see CLRS Ch. 6)
|
||
|
||
1. Implement mergesort.
|
||
|
||
>>> mergesort([4, 2, 5, 1, 6, 3])
|
||
[1, 2, 3, 4, 5, 6]
|
||
|
||
Filename: msort.py
|
||
|
||
2. Calculate the number of inversions in a list.
|
||
|
||
>>> num_inversions([4, 1, 3, 2])
|
||
4
|
||
>>> num_inversions([2, 4, 1, 3])
|
||
3
|
||
|
||
Filename: inversions.py
|
||
Must run in O(nlogn) time.
|
||
|
||
3. [WILL BE GRADED]
|
||
|
||
Length of the longest path in a binary tree (number of edges).
|
||
|
||
We will use the "buggy qsort" representation of binary trees from HW1:
|
||
[left_subtree, root, right_subtree]
|
||
|
||
>>> longest([[], 1, []])
|
||
0
|
||
|
||
>>> longest([[[], 1, []], 2, [[], 3, []]])
|
||
2
|
||
|
||
>>> longest([[[[], 1, []], 2, [[], 3, []]], 4, [[[], 5, []], 6, [[], 7, [[], 9, []]]]])
|
||
5
|
||
|
||
Note the answer is 5 because the longest path is 1-2-4-6-7-9.
|
||
|
||
Filename: longest.py
|
||
Must run in O(n) time.
|
||
|
||
Debriefing (required!): --------------------------
|
||
|
||
1. Approximately how many hours did you spend on this assignment?
|
||
2. Would you rate it as easy, moderate, or difficult?
|
||
3. Did you work on it mostly alone, or mostly with other people?
|
||
Note you are encouraged to discuss with your classmates,
|
||
but each students should submit his/her own code.
|
||
4. How deeply do you feel you understand the material it covers (0%–100%)?
|
||
5. Any other comments?
|
||
|
||
This section is intended to help us calibrate the homework assignments.
|
||
Your answers to this section will *not* affect your grade; however, skipping it
|
||
will certainly do.
|
||
|