CPSC 436R (Randomized Algorithms)

Description

An introductory course on randomized algorithms, and probabilistic techniques in computer science.

Instructors

Prof. Nicholas Harvey

TAs:

· Emily Gong, gongz@student.ubc.ca

· Victor Sanches Portella, victorsp@cs.ubc.ca

· Yennis Ye, yxyapp18@student.ubc.ca

Textbook

· N. Harvey, “A first course in randomized algorithms”
https://www.cs.ubc.ca/~nickhar/Book1.pdf

Grading Scheme

· 25%: Assignments (there will be 5 of them)

· 30%: In-class quizzes (there will be 3 of them)

· 5%: Tutorials

· 40%: Final exam

There is no additional requirement to pass the exam.

Tutorials

· There are weekly tutorials, except for the first week of classes. Every student should be registered in a tutorial section.

· Every week there is a Canvas Quiz, consisting of 3 Multiple Choice Questions. If you get all 3 correct, your tutorial grade is 100% for this week (and you do not need to attend the in-person tutorial.)

· Otherwise, you should attend the in-person tutorial. A TA will present several questions for you to work through in groups. Your tutorial grade for the week is based on participation.

Positive Space

My expectation is that all aspects of this course (lectures, Piazza, office hours, textbook, exercises) 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 microaggresions 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.

Please educate yourself about the following resources.

· https://www.cs.ubc.ca/students/undergrad/resources/equity-inclusion-wellness

· https://bullyingandharassment.ubc.ca/

Piazza Usage Policy

· Enroll using your full name (as recognized in the UBC registration system) at https://piazza.com/ubc.ca/winterterm12023/cpsc436r

· Registration will be open until Sept 18th, midnight. 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

Collaboration: Assignments are to be done individually, not in groups. You can discuss problems and brainstorm with your classmates. Acknowledge all collaborators or sources of assistance in your submission, although you need only name course staff, handouts, and textbooks if you quote or adapt directly from them. If you simply copy a solution that you found by internet search tools (e.g. Google or ChatGPT), that will be construed as cheating.

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 incur a severe penalty. Their grade will be multiplied by 0.5.

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. We strongly encourage you to submit something a few days in advance of the first assignment, to make sure that things are working properly.

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).

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”

Regrading Requests

We do our best to grade all submissions fairly and consistently. Because graders occasionally make mistakes, we welcome regrade requests that help us correct such mistakes and ensure fairness. You have one week from the time that the grades are posted to submit a regrade request on Gradescope. Please be respectful and help us ensure that time spent on regrades is productive by following these guidelines.

• Prior to making a regrade request, make sure you understand the solution to the problem, and read any comments provided on Gradescope or Piazza about how the problem was graded. If you don't understand what's missing from your answer, come see one of us during office hours before submitting a regrade request.
• Explain clearly and specifically why you believe your mark is inappropriate, referring to your solution, and the rubric. Good examples: "I lost a point for not initializing my table entries, but I initialize them in line 6." Or, "My solution is quite different from the one in the sample solution, but I'm confident that my approach also works for the following reason..."
• Don't submit a request because you think the rubric is unfair, or if you disagree with a judgment call of the grader. A bad example that disputes the rubric is: "I lost a mark for not justifying my answer, but I didn't think I needed to justify my answer, and I don't feel I should be penalized." A bad example that disputes a judgment is: "I should get 'minor errors (-0.5 points)' instead of 'significant errors (-2 points)'." An example that is not sufficiently specific is: "My friend gave basically the same answer and got a higher grade."

The person who graded the question will review your request, possibly with input from an instructor or other TAs. The decision of your TA or instructor is final. It may either increase or decrease your mark. Submitting several poorly-explained regrade requests may result in a penalty.

Academic Disconduct

See https://www.cs.ubc.ca/students/undergrad/resources/academic-integrity