Transcript 404_lecture1a - Computer Science

UMass Lowell Computer Science 91.404
Analysis of Algorithms
Prof. Karen Daniels
Spring, 2004
Lecture 1
Introduction/Overview
Text: Chapters 1, 2
Wed. 1/28/04
Web PageWeb Page
http://www.cs.uml.edu/~kdaniels/courses/ALG_404.html
Nature of the Course


Core course: required for all CS majors
Advanced undergraduate level


Graduate students take separate course (91.503)
No programming required


“Pencil-and-paper” exercises
Lectures supplemented by:


Programs
Real-world examples
What’s It All About?

Algorithm:



steps for the computer to follow to solve a
problem
well-defined computational procedure that
transforms input into output
Some of our goals:





recognize structure of some common
problems
understand important characteristics of
algorithms to solve common problems
select appropriate algorithm to solve a
problem
tailor existing algorithms
create new algorithms
Some Algorithm Application Areas
Robotics
Bioinformatics
Geographic
Information Systems
Design
Analyze
Telecommunications
Apply
Computer
Graphics
Medical Imaging
Astrophysics
Some Typical Problems
Sorting
Input: Set of items
Problem: Arrange items “in
order”
Median finding
Input: Set of numbers or keys
Problem: Find item smaller than
half of items and bigger than
half of items
Minimum Spanning Tree
Input: Graph G = (V,E) with weighted
edges
Problem: Find subset of E of G of
minimum weight which forms a
tree on V
Shortest Path
Input: Edge-weighted graph G , with
start vertex and end vertex t
Problem: Find the shortest path from
to t in G
SOURCE: Steve Skiena’s Algorithm Design Manual
(for problem descriptions, see graphics gallery at http://www.cs.sunysb.edu/~algorith)
Tools of the Trade

Algorithm Design Patterns such as:
 divide-and-conquer

Data Structures such as:
 trees,

linked lists, hash tables, graphs
Algorithm Analysis Techniques
such as:
 asymptotic analysis
 probabilistic analysis
Summations
Proofs
Sets
Combinations
Growth of Functions
Permutations
MATH
Probability
Recurrences
Logarithms
Tools of the Trade: (continued)
Algorithm Animation
http://www.cs.brockport.edu/cs/java/apps/sorters/insertsortaniminp.html
What are we measuring?

Some Analysis Criteria:

Scope



“Dimension”


Upper? Lower? Both?
Type of Input


Time Complexity? Space Complexity?
Type of Bound


The problem itself?
A particular algorithm that solves the problem?
Best-Case? Average-Case? Worst-Case?
Type of Implementation

Choice of Data Structure
Prerequisites
Computing I (91.101)
 Computing II (91.102)
 Discrete Math I & II (92.321, 92.322)
 Statistics for Scientists and Engineers
(92.386)
 Calculus I-III (92.131-231)

Summations
Proofs
Sets
Combinations
Growth of Functions
Permutations
MATH
Probability
Recurrences
Logarithms
Course Structure: 4 Parts

Foundations


Sorting


Heapsort, Priority Queues, Quicksort, Sorting in Linear
Time
Data Structures


Analyzing & Designing Algorithms, Growth of Functions,
Recurrences, Probability & Randomized Algorithms
Stacks and Queues, Linked Lists, Introduction to Trees,
Hash Tables, Binary Search Trees, Balancing Trees: RedBlack Trees
Graph Algorithms

DFS, BFS, Topological Sort, MST, Shortest paths
Textbook
Required:
 Introduction
to Algorithms
 by
T.H. Corman, C.E. Leiserson, R.L. Rivest
 McGraw-Hill
New Edition
 2001
 ISBN 0-07-013151-1

see course web site (MiscDocuments) for errata (1st edition)
Ordered for UML bookstore
Syllabus (current plan)
Lecture Date
Topic
Reading
Foundations
Chapters 1-5
W 1/28
Introduction/Overview
Chapter 1
F 1/30, M 2/2, W 2/4
Analyzing & Designing Algorithms
Chapter 2
F 2/6, M 2/9, W 2/11
Growth of Functions
Chapter 3
F 2/13, W 2/18, Th 2/19
Recurrences
Chapter 4
F 2/20, M 2/23, W 2/25
Probability & Randomized Algorithms
Chapter 5
Sorting
Chapters 6-9
F 2/27, M 3/1
Heapsort/ Priority Queues
Chapter 6
W 3/3, F 3/5
Quicksort
Chapter 7
M 3/8, W 3/10
Review
Chapters 1-5
F 3/12
Midterm Exam
Chapters 1-5
M 3/22
Quicksort
W 3/24, F 3/26, M 3/29
Sorting in Linear Time
Chapter 8
Data Structures
Chapters 10-13
W 3/31, F 4/1, M 4/5
Stacks, Queues, Linked Lists, Trees
Chapter 10
W 4/7, F 4/9
Hash Tables
Chapter 11
M 4/12, W 4/16, F 4/18
Binary Search Trees
Chapter 12
W 4/21, F 4/23
Balancing Trees: Red-Black Trees
Chapter 13
Graph Algorithms
Chapters 22-24
M 4/26, W 4/28, M 5/3
Elementary Graph Algorithms
Chapter 22
W 5/5, F 5/7
Minimum Spanning Trees
Chapter 23
M 5/10
Shortest Paths
Chapter 24
W 5/12, F 5/14
Review
1-13, 15-16, 22-24
To Be Determined
Final Exam
1-13, 15-16, 22-24
CS Theory Math Review Sheet
The Most Relevant Parts...



p. 1
 O, Q, W definitions
 Series
 Combinations
p. 2 Recurrences &
Master Method
p. 3
 Probability
 Factorial
 Logs
 Stirling’s approx





p. 4 Matrices
p. 5 Graph Theory
p. 6 Calculus
 Product, Quotient
rules
 Integration,
Differentiation
 Logs
p. 8 Finite Calculus
p. 9 Series
Math fact sheet (courtesy of Prof. Costello) is on our web site.
Important Dates
Midterm Exam (Chapters 1-5):
 Final Exam:

Friday, 3/12
TBA
Grading
Homework
 Midterm (Chapters 1-5)
 Final Exam

35%
30%
35%
(open book, notes )
(open book, notes )