Computer Science 431
Algorithms
Spring 2015, The College of Saint Rose
Lecture 3: More Data Structures; Asymptotic Analysis
Date: Wednesday, January 21, 2015
Agenda
- Announcements
- those who do not have accounts on mogul.strose.edu should get one today
- class code examples will be on mogul.strose.edu in /home/cs431/examples
- please be careful about which assignment name you choose when submitting items in submission box
- Problem Set 1: Data Structures [HTML] [PDF] continues
- Lecture 2 assignment recap
- Fundamental data structures wrapup
- a bit about maps and dictionaries
- a look through the structure package structures
- Asymptotic analysis (some should be review)
- basic complexity ideas
- basic efficiency classes
- Big O
- Analyzing non-recursive algorithms
Lecture 3 Assignment
Due at the start of class, Monday, January 26.
Please submit answers to these questions
in Submission
Box under "LA3" or in hard copy 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.
- Levitin Exercise 1.4.4, p. 37 (4 points).
- Levitin Exercise 2.1.1, p. 50 (6 points).
- Levitin Exercise 2.1.4, p. 51 (4 points).
Terminology
- time vs. space tradeoff
- computational cost
- basic operation
- space cost
- trends
- asymptotic analysis
- Big O
- relative rates of growth
- order of growth/complexity
- constant, logarithmic, linear, quadratic, cubic, polynomial, exponential, factorial
- best/worst/average case complexity
- basic efficiency classes
Examples