####
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.
``` |
||

```
``` |