| Logistics: |
TTh 11-12:30
GDC 5.302 Unique Number: 55195 Course web page: http://www.cs.utexas.edu/~diz/378 |
|||||||||||||||||||||||||||
| Professor: | David Zuckerman Email: diz@cs.utexas.edu Phone: 471-9729 Office: GDC 4.508 Office Hours: Tu 3-4, Th 2-3 |
|||||||||||||||||||||||||||
| Who should take this? | Students interested in theory, probability, and algorithms, and who like a challenge. This course is excellent preparation for graduate school. | |||||||||||||||||||||||||||
| Textbooks: |
Required text:
Mitzenmacher and Upfal,
Probability and Computing, 2nd edition
Supplementary text: Harchol-Balter, Introduction to Probability for Computing |
|||||||||||||||||||||||||||
| Course Overview: |
Randomness is extremely useful in computer science.
Algorithms that make random choices during their execution, known as randomized algorithms, are often faster or simpler than algorithms that don't use randomness.
Examples include Quicksort, primality testing, and Monte Carlo simulations.
However, such randomized algorithms usually come with a small probability of error, so it is important to bound this error probability.
In this undergraduate course, we develop tools and techniques
to design and analyze efficient randomized algorithms.
This course is theoretical and mathematical; there will be no programming
assignments.
Each section of the course is built around a method, with example
applications to randomized algorithms.
This course should be similar to the 2024 version.
We list the topics below.
|
|||||||||||||||||||||||||||
| Prerequisites: | Computer Science 331 or 331H. This means that you need the prerequisites and corequisites for CS 331, including Discrete Math (CS 311 or 311H), Probability (SDS 321 or M 362K), and Linear Algebra (SDS 329C, Math 340L, or Math 341). Strong intuition about probability is essential; I recommend taking this class only if you received an A in Probability. Here is some mathematical background that we will use. | |||||||||||||||||||||||||||
| Grading: |
75% 3 Exams 15% Homework 10% Participation |
|||||||||||||||||||||||||||
| Exams: | The exams will be held in class on the following dates: Exam 1 on Tuesday, September 30, Exam 2 on Thursday, November 6, and Exam 3 on Thursday, December 4. No make-up tests will be given, so plan accordingly. You may bring a single, 8.5x11 inch, handwritten sheet of paper (you may use both sides). No calculators are allowed (they won't be necessary). | |||||||||||||||||||||||||||
| Homework: |
I will assign a problem set about every third class.
Collaboration policy: While you should first think about the problems on your own, you are encouraged to discuss the problems with your classmates. Please limit your collaborations on any particular homework to at most three other students. Discussion of homework problems may include brainstorming and verbally walking through possible solutions, but should not include one person telling the others how to solve the problem. In addition, each person must write up their solutions independently, and these write-ups should not be checked against each other or passed around or emailed. You must acknowledge any collaboration by writing your collaborators' names on the front page of the assignment. You don't lose points by having collaborators. Citation policy: Try to solve the problems without reading any published literature or websites, besides the class text and links off of the class web page. If, however, you do use a solution or part of a solution that you found in the literature or on the web, you must cite it. Furthermore, you must write up the solution in your own words. You will get at most half credit for solutions found in the literature or on the web. Use of AI: You may use AI to help you understand material. However, you may not use AI to solve the homework problems for you. If you want hints for the homework, ask the professor. Submission policy: Each student has two late days that they can use during the semester with no penalty (one assignment two days late, or two assignments one day late). Once late days are used up, no credit will be given for late assignments. A day here means 24 hours. The weekend doesn't count, so Friday to Monday counts as one day. I may not allow late days for certain assignments. | |||||||||||||||||||||||||||
| Participation and Attendance: | Your participation grade is based on the quality and quantity of your participation. While attendance is not required, poor attendance will be reflected in your participation grade. | |||||||||||||||||||||||||||
| Useful Pointers: |
My
100-second talk on randomness on The Academic Minute.
My essay Can Random Coin Flips Speed Up a Computer? |
|||||||||||||||||||||||||||
| Laptops/Phones: | The use of laptops and mobile devices is generally prohibited; however, I will allow use of tablets if you use them only for class-related purposes and sit in the front. All phones must be silenced. | |||||||||||||||||||||||||||
| Canvas: | We will use Canvas, which contains Ed Discussion. Homeworks and grades will be posted on Canvas. We will use Ed Discussion for class discussion. Instead of emailing questions to the teaching staff, please post your questions to Ed Discussion. | |||||||||||||||||||||||||||
|
Students with Disabilites: |
Any student with a documented disability (physical or cognitive) who requires academic accommodations should contact the Services for Students with Disabilities area of the Office of the Dean of Students at 471-6259 (voice) or 471-4641 (TTY for users who are deaf or hard of hearing) as soon as possible to request an official letter outlining authorized accommodations. |