Description
An
introductory course on randomized algorithms, and probabilistic techniques in
computer science.
Instructors
Prof. Nicholas Harvey
Textbook
·
N. Harvey, “A
first course in randomized algorithms”
https://www.cs.ubc.ca/~nickhar/Book1.pdf
Grading Scheme
· 15%: Assignments (there will be 5 of them)
· 5%: Canvas Quizzes
· Max of:
o 40%: In-class quizzes, 40%: Final exam
o 30%: In-class quizzes, 50%: Final exam
There is no additional requirement to pass
the exam.
Positive Space
My expectation is that
all aspects of this course (lectures, Piazza, office hours, textbook, exercises,
etc.) are welcoming and respectful to all members of the UBC community. Please
bring to my attention any behavior that is disparaging, disrespectful,
inflammatory, prejudicial, or could be construed as microaggressions or
bullying.
I will do my best to
hold myself to the same standard. There may be the occasional slip up, but
hopefully they are infrequent and forgivable. If I am the perpetrator of any
negative behavior, please either can bring it to my attention, or notify a
neutral third party, such as the associate head for undergraduate affairs ah-ugrad@cs.ubc.ca.
I am personally very
interested in diversity issues. I have done some academic coursework and research
in this area, and I am a member of the department’s Committee for Outreach, Diversity and
Equity (CODE). I am happy to have conversations with any students on this topic.
Please educate yourself
about the following resources.
·
Resources
for Health and Wellness:
https://www.cs.ubc.ca/students/undergrad/resources/equity-inclusion-wellness
·
UBC
Statement on Respectful Environment:
https://hr.ubc.ca/sites/default/files/documents/UBC-Statement-on-Respectful-Environment.pdf
·
Bulling
and Harassment Prevention at UBC:
https://bullyingandharassment.ubc.ca/
Piazza Usage Policy
·
Enroll using your full name (as recognized in the UBC
registration system)
· Registration will be open until the third
week of the term. After this date, accounts of students not recognized may be
disabled.
· Use the public forum for questions/answers
to your fellow students and/or members of the teaching team.
· For questions that can only be answered by
a member of the teaching team, post them as private messages directly to the
instructors/TAs.
·
Trolling
(public posting of inappropriate questions/comments) is cause for removal from
the course Piazza. If you want to express an opinion (e.g. about challenges
with the class, with an exam, or with students/instructors), you should
communicate with the course staff either face-to-face or by email.
Assignment Guidelines
Software and Collaboration: You are allowed to talk with other
students and use AI software to prepare your assignment. You can submit a
single assignment for a group of students, with no restriction on the size of
the group.
Formatting: We require that assignments be
submitted using LaTeX. We will make the .tex version
of the assignment available, to make it easier for you to prepare your
solutions using LaTeX. Submissions that are not typeset in Latex will not be
graded.
Submission: Submit your assignments on Gradescope by
11:59:00pm. You can submit early and resubmit as often as you want up to the
deadline. After uploading to Gradescope, link each
question with all the pages of your pdf containing your solution.
Late submissions: Late homework
submissions will not be accepted, except in special situations (e.g. medical
issues).
Grading
The effort that we expend on grading the homework will be
commensurate with the effort that we perceive was spent in writing it. Homework
that is obviously written by AI may be marked as correct (if it is), but will
not receive detailed feedback. Homework that is obviously written by a human
will receive traditional levels of feedback.
Quizzes
Some of the quiz questions will be designed to be similar to the
homework questions. If you spend minimal effort on the homework, it will be harder
to do well on the quiz.
Prerequisites
I expect you to be familiar with the following concepts:
·
logic, proofs,
summations, binary representation and modular arithmetic from CPSC 121
o
To
review these topics, see Lehman, Leighton and Meyer’s "Math for
Computer Science" Ch 1-5, 11, 13.
o
Logic
and proofs are covered in the PLP
book.
·
data structures, sorting
and searching, asymptotic notation, trees and graphs from CPSC 221
·
algorithm analysis,
divide-and-conquer algorithms, graph searching algorithms, and asymptotic
notation from CPSC 320
·
probability:
events, independence, probability and its properties, conditional
probabilities, random variables, common distributions, mass functions,
cumulative distribution functions, expectation.
o
For a basic
introduction to some of these topics, aimed at computer scientists see "Math for
Computer Science", Ch 17-20
For a more thorough introduction, also aimed at
computer scientists, see Harchol-Balter’s “Introduction to
Probability for Computing”
Academic Disconduct
See https://www.cs.ubc.ca/students/undergrad/resources/academic-integrity