CSC373H Lecture 1
CSC373H Lecture 1
September 8, 2021
Welcome to CSC373
▶ This course introduces powerful ways of designing algorithms
▶ We’ll learn
▶ Greedy algorithms: generally very fast . . . when they work!
▶ Dynamic programming: applies to many problems
▶ Maximum-flow: useful for reductions
▶ Approximation algorithms: for problems that are just too tough
▶ Other topics as time permits (maybe string or randomized
algorithms)
▶ Bonuses
▶ You’ll learn some of the most famous and widely-applicable
algorithms developed in the history of CS
▶ You’ll kick butt in algorithms portions of interviews!
Lecture Recordings
▶ I plan to make lecture recordings available to those students
enrolled in the course
▶ Please keep private and use only for your own studying
▶ Please don’t use the videos as a substitute for attending and
engaging in class
▶ If you have any questions or concerns, please let me know
Evaluation
▶ One midterm test (15%)
▶ Final exam (40%)
▶ Must earn at least 40% on exam to pass the course
▶ Problem sets (40%)
▶ Float (5%), added to higher of midterm or exam grade
Midterm Test Plan
▶ The midterm test will be like a take-home test, written
individually
▶ Instead of crunching everyone into the same starting time, we
are going to use a time window during which you have to
write and submit the test
▶ Benefits
▶ Adjusts for different time zones
▶ You can submit what you know, not only what you can do
under time pressure
▶ Lets me ask you for LaTeX and working Python code 🙂
Let’s talk about this!
Submission Policy
▶ LaTeX is a system for typesetting documents
▶ Many computer scientists, mathematicians, physicists, etc.
use LaTeX
▶ I am requiring you to submit all problem sets using LaTeX
▶ You must submit both your .tex source and resulting .pdf
file to MarkUs
▶ Please check the course website for useful introductory LaTeX
resources
Problem Sets
▶ You can work alone or with one partner
▶ Each student has eight 12-hour tokens that they can use (see
syllabus for all details)
▶ If you work with a partner, don’t split up the problem set by
question
▶ Work together throughout!
▶ This is great practice for tests and your own future algorithm
work
Academic Integrity
▶ I hope that you all know what I expect by now
▶ Do not discuss problem sets outside of your group
▶ Please don’t “help” others by helping them solve the problem
sets!
▶ Please don’t put others in awkward positions by asking them
for help on a problem set
▶ What you can do to help
▶ Discuss examples from lecture and the course materials
▶ Find and discuss related online resources
Tutorials
▶ Tutorial attendance is not required for marks
▶ Our TAs run the tutorials
▶ They can help you understand course material and work
through examples and previous problem sets
▶ Feel free to bring questions!
▶ First tutorial next week: more examples of greedy algorithms
Course Materials
▶ There is no primary textbook
▶ For additional reading/practice, you might consider
▶ Cormen et al., Intro to Algorithms 3/e (free through library,
famous, can be tough slogging!)
▶ Kleinberg and Tardos, Algorithm Design (more approachable,
less comprehensive)
▶ Me, Algorithmic Thinking (my best effort at an intuitive but
rigorous treatment of a subset of our topics)
▶ Don’t hesitate to refer to other books or online materials
Greedy Algorithms
Greedy Algorithm: at each step, make the choice that seems like
the best thing to do right now.
▶ Greedy algorithms can sometimes be used to solve a problem
▶ When they do work, they are usually very fast
▶ The design involves determining the “greedy choice” to make
▶ How do we know that a greedy algorithm is correct?
▶ Requires a proof. These proofs are often subtle
Activity Scheduling
▶ Input: set of activities a1, a2, . . . , an
▶ Each activity ai has start time si and finish time fi
▶ Output: subset of activities S such that no activities in S
overlap in time and the number of activities |S | is maximum
Activity Scheduling: Example
Here are 11 activities each given as [startTime, finishTime). What
is the maximum number of activities that we can schedule?
[1, 4), [3, 5), [0, 6),
[5, 7), [3, 9), [5, 9),
[6, 10), [8, 11), [8, 12),
[2, 14), [12, 16)
Brute Force
▶ A brute-force solution involves considering each subset of
activities and checking whether it is a valid schedule
▶ But, there are 2n subsets of n activities
▶ So, this will yield an Ω(2n) algorithm
▶ A greedy algorithm, if it works, would be much faster . . .
Greedy Attempt 1: Start Time
▶ OK. Greedy. But greedy how?
▶ Let’s try greedy by start time
sort activities by start time: s_1 <= s_2 <= ... <= s_n S = {} f = 0 # finish time of last activity added to S for i in [1,2,...,n]: if s_i >= f:
S = S + {a_i}
f = f_i
return S
Greedy Attempt 1: Start Time…
It’s a greedy algorithm, but it doesn’t always work!
Simplest counterexample:
[0, 7), [1, 2), [3, 4)
Taking [0, 7) is not as good as taking both [1, 2) and [3, 4)!
Greedy Attempt 2: Duration
What if we consider activities in order of increasing duration (i.e.
length of time they take)?
It’s wrong too! Simplest counterexample:
[4, 6), [1, 5), [5, 9)
Greedy Attempt 3: Finish Time
Considering activities in order of increasing finish time is a correct
greedy algorithm.
▶ Can’t find a counterexample
▶ Intuitively makes sense
▶ Careful, though: some of the wrong ones might make intuitive
sense to you, too
▶ How can we prove correctness?