CS 115 Reading: Week 13

Sorting algorithms, continued

By the end of Week 13, you should be comfortable with:

• Tracing the execution of selection sort
• Tracing the steps of merge sort (not the actual code)
• Reasoning about the performance of selection sort and merge sort

Suggested readings:

• Section 13.1 of your textbook is about selection sort. For mergesort, skip Section 13.2 and go straight to Section 13.3, which describes the algorithm at a higher level and compares its performance to that of selection sort. You can go back to Section 13.2 later if you really want the gory details.
• The site sorting-algorithms.com has language-independent visualizations of lots of sorting algorithms, including selection sort and mergesort.

Object-Oriented Programming

By the end of Week 13, you should be familiar with basic object-oriented terminology and how to identify classes, objects, and methods in object-oriented code.

Suggested readings:

• How to Think Like a Computer Scientist has a great introduction to OOP.
• Sections 4.1, 4.2, and 10.1 of your textbook explain the notion of objects and how they relate to the graphics library.
• Section 10.3 and 10.4 of your textbook go over the design of two sample classes.