RetroSearch Browse

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://www.math.ucla.edu/~pak/courses/182-Summer-2022/182-Summer-2022.html below:

Math 182 (Summer 2022)

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 ExamsMidterm: 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

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4