Lecturer: Derek Corneil,
SF 3301B, 978-8954, dgc@cs.utoronto.ca
Lectures: Tuesday 3:10 - 5:00 in WB 144
Tutorial: Thursday 3:10 - 4:00 in WB 144 (Natasa Przulj)
Marking Scheme:
7 assignments
@ 10 marks each 70
1 project
@ 20 marks 20
class participation
10
* lateness penalty is 50% - unless advance permission is obtained; assignments that are over 1 week late will not be accepted.
* unless cooperation is explicitly allowed, all work must be done independently.
Text: G. Rawlins: "Compared to what? - an introduction to the analysis of algorithms", Computer Science Press, 1992.
Approximate Course Outline:
Introduction (4)
what is
a beautiful algorithm?
development
of pseudo-language
efficiency
issues
Data Storage (14)
sorting
searching
heaps and
other data structures
Number Theory (9)
factoring,
primes
application
to cryptography
multiplying
integers and matrices
Graph Theory (20)
search
strategies
games on
graphs
distance
calculation
minimum
spanning tree
touring
a graph
Miscellaneous (5)
numerical
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Project due Friday April 12
Announcement (April 2, 2002)
from Natasa:
There will be a class next Tuesday, April 9, 3:40pm-5:40pm in LP 266.
Announcement (March 5, 2002)
from Natasa:
The class is rescheduled for Tuesdays 3:40pm to 5:40pm starting on
March 19.
The new classroom is LP 266 (Pratt Building).
Announcement (January 16,
2002) from Derek:
"In lecture on Tuesday the 15th, I goofed in my answer to a question
about
the Modular_Power algorithm. In particular, given a binary representation
of power, we can compute floor(power/2) by shifting power one place
to the
right. If power was odd, then a "1" has fallen off the right
hand end; if
power was even, then a "0" has fallen off. This is why it helps
to have a
binary representation of the original value of power."