Computer Science 501
Data Stuctures and Algorithm Analysis
Fall 2013, The College of Saint Rose
Lecture 3: Analysis Tools
Date: Wednesday, September 11, 2013
Agenda
- Announcements
- New link on home page to web repository of class examples
- Get onto the CS department web page, if you're not yet
- Lab 1 recap
- Lecture 2 assignment recap
- Programming Project 1: Timing Java [HTML] [PDF]
- Costs of Vector operations
- Asymptotic analysis
- finding trends
- Big O
- common orders of growth
- best/worst/average cases
- Basic efficiency classes
Lecture 3 Assignment
Due at the start of class, Wednesday, September 18.
Please submit answers to these questions
in Submission
Box under "LA3" by the start of our next
class. We will discuss these questions at the start of class, so no
late submissions are accepted. Please be sure that your name is
clearly indicated in all submissions.
- Bailey Problem 5.2, p. 112 (4 points)
- Bailey Problem 5.4, p. 112 (3 points)
- Bailey Problem 5.10, p. 113 (4 points)
- There are 22 gloves in a drawer: 5 pairs of red gloves, 4 pairs
of yellow, and 2 pairs of green. You select the gloves in the dark
and can check them only after a selection has been made. What is the
smallest number of gloves you need to select to have at least one
matching pair in the best case? In the worst case? (3 points)
Examples