Algorithms (Math 182, Summer 2022)
Instructor: Igor Pak
See email instructions below.
Class schedule: MWF 9:00 - 9:50, 10 min break, 10:00 - 10:50 am
Zoom: Meeting id: 372 517 9299 (password: see email).
Discussion: Tue, same time, Zoom
Office Hours: M 4-4:50 pm (same Zoom link) or by appointment.
Teaching Assistant: William Swartworth (wswartworth AT math.ucla.edu)
TA Office Hours: Tue, Wed 11:00 - 11:50 am.
Textbooks: Kleinberg, Tardos: Algorithm Design (KT), Addison Wesley
(see the Amazon
page)
Additional reading will be posted on this page if necessary.
Grading: Homeworks: 20%, Midterm: 20%, Final: 60%.
Difficulty: This is an advanced undergraduate course in
Algorithmss. The students are expected to
learn the theory and solve problems on the homeworks. The exams and especially
the homeworks will be challenging and require problem solving abilities.
Other expectations:
I would guess that the average student
should spend about 8-10 hours per week outside of class to get a decent grade.
Much of this time should be spent on the homeworks, but some should
be spent on reading the book and absorbing the class material.
Content
We will cover selected book sections concentrating on rigorous Analysis of Algorithms.
Although much of the material will follow the textbook, I will change the style of presentation,
as well as the order of sections. Some additional material will be presented
in class, so both class attendance and participation are very important.
Approximate course content is here.
Zoom recordings and lecture notes are available on Canvas pages, see here.
Additional Reading
- Excellent chapter-by-chapter slides are available here.
- Allen Gehret's detailed lecture notes for Math 182 are linked here.
Supplementary material to lectures
- L1: Balance puzzle and
Bottle puzzle.
- L2: Binary
addition and multiplication (and some growth rate discussion), also available as a .pdf file or
a powerpoint presentation.
- L3: Kruskal's algorithm
- L4: Bubble sort, merge sort,
Karatsuba multiplication algorithm
- L5: Strassen algorithm
- L6: Subset sum problem and
Knapsack problem
- L7: Gale-Shapley algorithm
and Max-flow min-cut theorem
- L8: Ford-Fulkerson algorithm
- L9: Konig's theorem,
Hall's theorem
and Tutte's theorem
- L10: Image segmentation
- L11:
Maximal independent set,
Vertex cover,
Boolean algebra,
SAT
and
Polynomial time reduction
- L12: NP-completeness
- L13: coNP, PSPACE,
PSPACE-completeness
- L14: Bernoulli distribution,
Geometric distribution,
Coupon collector's problem
Home Assignments
The assignments will be posted here (on the course web page) in .pdf format.
You must submit solutions to Gradescope (see this link).
No late assignments will be accepted. Worst HA is dropped.
- HA1 is here, due Wed June 29, 5 pm.
- HA2 is here, due Wed July 6, 5 pm.
- HA3 is here, due Wed July 20, 5 pm.
- HA4 is here, due Wed July 27, 5 pm.
Midterm and Final Exams
Midterm: Online, 50 min during 24 hour window from Thu July 7, 11:00 am, to Fri July 8, 11:00 am.
Midterm problems: here.
Answers: (1) 11 inv,
(2) f=o(g), g=o(u), u=o(v), v=o(h) and by transitivity 10 comparisons in total,
(3) 0 → 7 → 6 → 5 → 4 (total weight 21), unique,
(4) edges with weights 34, 44, 50, 51, 77 (256 total), unique
(5) FTFTT, TTFTT, TFFFT
Final: Online, 180 min during 24 hour window from Thu July 28, 11:00 am, to Fri July 29, 11:00 am.
Both exams are open book, open web, but no collaboration and no cheating.
Cheating
Cheating is a serious violation of UCLA policies.
Please read here
and here (note especially section 102.01a).
Students caught cheating will be reported and suffer the
consequences. Do NOT cheat!! Don't even think about it!
Collaboration Policy
For the homeworks, you can form discussion groups of up to 3 people each.
In fact, I would like to encourage you to do that.
You can discuss problems but have to write your own separate solutions.
You should write the list of people in you group on top of each HW.
See the group chat
on Canvas if you are looking for study partners.
Click here
to return to Igor Pak Home Page.
To e-mail me click
here and delete .zzz
Put Math 182 in the Subject line.
Please put in your first line "Dear Professor Pak," -- no other salutations are allowed in the first line of the message.
At the end of your email, you must include your full name, UCLA id, and your
official ucla.edu email address (for privacy purposes). Replies will
be send only to the UCLA address.
Last updated 7/27/2022