主观题：Skip Lists
Skip list is a data structure that supports both searching and insertion in $$O(log N)$$ expected time.
This project requires you to introduce the skip lists, and to implement insertion, deletion, and searching in skip lists. A formal proof is expected to show that the expected time for the skip list operations is $$O(log N)$$. You must generate test cases of different sizes to illustrate the time bound.
### Grading Policy:
**Programming:** Implement the functions (6 pts.). Write a test of performance program (1 pts.). **All the codes must be sufficiently commented.**
**Testing:** Generate the test cases and give the run time table (2 pts.). Plot the run times vs. input sizes for illustration (2 pts.). Write analysis and comments with the proofs (5 pts.). The analysis must be based on your testing results.
**Documentation:** Chapter 1 (1 pt.), Chapter 2 (2 pts.), and finally a complete report (1 point for overall style of documentation).
答案：Rubric items: 6
Item 1: 1 point
The cover page must be presented with the title and the date of completion (+ 0.2 pts.). A complete problem description must be given in Chapter 1 (+0.8 pts.). Deduct points if:
- the cover page is not complete (-0.2)
- the introduction is a simple copy + paste of the assignment statement (-0.3)
- the introduction is not very clear -- in this chapter they are supposed to make it clear WHAT is to be done, besides why they are doing it (-0.1 ~ 0.5)
- others – please specify in the final comments.
Item 2: 2 points
Chapter 2 is supposed to specify the structure of skip lists (+1 pt.), together with insertion, deletion, and searching (+1 pt.). Deduct (at most 2) points if:
- the description is way too simple (-1)
- the algorithm specification is not complete – the skip list description is missing (-1)
- the algorithm specification is not complete – the insertion, deletion, and searching descriptions are missing or incomplete (-0.5~1)
- not making their algorithm easier to understand than a simple program (-1)
- only a program + comments, which is not acceptable (-1)
- others – please specify in the final comments.
Item 3: 1 point
The overall style of documentation is supposed to be neat and clear. Deduct (at most 1) point if:
- the document looks like a patch work (-1)
- messy – some of the data in the charts and tables are missing (-1)
- the hand-in is not zipped with proper folders (-1)
- the hand-in is not complete – some files are missing (-1)
- others – please specify in the final comments.
Item 4: 2 points
A complete table of testing data must be given in Chapter 3, including testing the correctness (+0.5 pt.) and the performance (+1 pt.). A case generator program must be given to generate large amount of performance testing data (+0.5 pt.). Deduct (at most 2) points if:
- the testing results have a problem: some of the tick numbers are less than 10, which means that their answer is not accurate enough (-0.2)
- the case generator program is missing (-0.5)
- the testing results are not complete (-0.5~1)
- others – please specify in the final comments.
Item 5: 7 points
Plots (+2 pts.) and comments (+3 pt.) on the performances of skip list functions are supposed to be given in Chapter 4, together with a proof of the expected time bound (+2 pts.). Deduct points if:
- the plot is missing (-2)
- the plot is misleading since the x-axis is NOT EQUALLY SPACED (-1)
- the analysis does not seem to fit with their testing results (-1)
- the analysis of the performances is incomplete (-1~3)
- the proof of the expected time bound is missing (-2)
- others – please specify in the final comments.
Item 6: 7 points
A main program (+6 pts.) and a testing program (+1 pt.) must both be presented. Deduct points if:
- the testing program is missing (-1)
- some of the programs are not working properly (-1 ~ 3)
- the programs are not well-commented (-7)
- others – please specify in the final comments.
This project requires you to introduce the skip lists, and to implement insertion, deletion, and searching in skip lists. A formal proof is expected to show that the expected time for the skip list operations is $$O(log N)$$. You must generate test cases of different sizes to illustrate the time bound.
### Grading Policy:
**Programming:** Implement the functions (6 pts.). Write a test of performance program (1 pts.). **All the codes must be sufficiently commented.**
**Testing:** Generate the test cases and give the run time table (2 pts.). Plot the run times vs. input sizes for illustration (2 pts.). Write analysis and comments with the proofs (5 pts.). The analysis must be based on your testing results.
**Documentation:** Chapter 1 (1 pt.), Chapter 2 (2 pts.), and finally a complete report (1 point for overall style of documentation).
答案：Rubric items: 6
Item 1: 1 point
The cover page must be presented with the title and the date of completion (+ 0.2 pts.). A complete problem description must be given in Chapter 1 (+0.8 pts.). Deduct points if:
- the cover page is not complete (-0.2)
- the introduction is a simple copy + paste of the assignment statement (-0.3)
- the introduction is not very clear -- in this chapter they are supposed to make it clear WHAT is to be done, besides why they are doing it (-0.1 ~ 0.5)
- others – please specify in the final comments.
Item 2: 2 points
Chapter 2 is supposed to specify the structure of skip lists (+1 pt.), together with insertion, deletion, and searching (+1 pt.). Deduct (at most 2) points if:
- the description is way too simple (-1)
- the algorithm specification is not complete – the skip list description is missing (-1)
- the algorithm specification is not complete – the insertion, deletion, and searching descriptions are missing or incomplete (-0.5~1)
- not making their algorithm easier to understand than a simple program (-1)
- only a program + comments, which is not acceptable (-1)
- others – please specify in the final comments.
Item 3: 1 point
The overall style of documentation is supposed to be neat and clear. Deduct (at most 1) point if:
- the document looks like a patch work (-1)
- messy – some of the data in the charts and tables are missing (-1)
- the hand-in is not zipped with proper folders (-1)
- the hand-in is not complete – some files are missing (-1)
- others – please specify in the final comments.
Item 4: 2 points
A complete table of testing data must be given in Chapter 3, including testing the correctness (+0.5 pt.) and the performance (+1 pt.). A case generator program must be given to generate large amount of performance testing data (+0.5 pt.). Deduct (at most 2) points if:
- the testing results have a problem: some of the tick numbers are less than 10, which means that their answer is not accurate enough (-0.2)
- the case generator program is missing (-0.5)
- the testing results are not complete (-0.5~1)
- others – please specify in the final comments.
Item 5: 7 points
Plots (+2 pts.) and comments (+3 pt.) on the performances of skip list functions are supposed to be given in Chapter 4, together with a proof of the expected time bound (+2 pts.). Deduct points if:
- the plot is missing (-2)
- the plot is misleading since the x-axis is NOT EQUALLY SPACED (-1)
- the analysis does not seem to fit with their testing results (-1)
- the analysis of the performances is incomplete (-1~3)
- the proof of the expected time bound is missing (-2)
- others – please specify in the final comments.
Item 6: 7 points
A main program (+6 pts.) and a testing program (+1 pt.) must both be presented. Deduct points if:
- the testing program is missing (-1)
- some of the programs are not working properly (-1 ~ 3)
- the programs are not well-commented (-7)
- others – please specify in the final comments.
