(posted 03-03)
Week of March 8--12: business as usual, including the next two items:
03-12 2:10pm Posted: class notes from today's class (ellipsoid method) and yesterday's problem session
03-10 2:30pm Posted: second batch of problems for final assignment. Due Fri, March 19, 6pm.
03-10 11:20am Posted: class notes from today's class. Click "Class notes, slides" on the banner.
03-08 3:55pm Posted: class notes from today's class.
03-05 10:35am Posted: class notes from today's class.
03-04 8:00pm Posted: class notes from today's problem session.
03-03 11:00pm Posted: exercises from today's class: MAX3SAT: satisfying at least the expected number of clauses. Method of 3-wise independence. Method of conditional expectations. Problems due Mar 9.
03-03 4:05pm Posted: exercises from Monday's class: Random variables, expected value, MAX3SAT. Problems due Mar 9.
03-03 11:18am Posted: class notes from today's class.
03-01 11:05am Posted: class notes from today's class.
02-27 9:35am Posted: statistics of Assignments#1-5. UPDATED 02-27 3:40pm. Click "Statistics" on the banner.
02-26 11:10am Posted: class notes from today's class.
02-26 3:40am Posted: assignments on Gradescope, due Tuesday, Mar 2, 11pm
02-25 8:00pm Posted: class notes from today's problem session.
02-24 12:15pm Posted: class notes from today's class.
02-22 11:00am Posted: class notes from today's class.
02-19 12:30pm Posted: class notes from today's class and yesterday's problem session. Click "Class notes, slides" on the banner.
02-18 8:30pm Posted: assignments on Gradescope, due Tuesday, Feb 23, 11pm
Instructor: László Babai
Class schedule
Websites: Go to
Canvas, login, and then
Click Zoom to access the class
Click Gradescope to access the assignments and the video recordings
of the classes
For everything else, check out the links on the banner on this website. Not all tabs on the banner are operational yet. If you think a link should already work but it does not, please send email to the instructor.
Please send email to the instructor with answers to these questions, even if you are only auditing the class, did not register, or have an unusual status. Your answers to these questions will help me to better plan the course. Please write "CMSC 27230 data" in the subject.
This is a proof-based course. It requires familiarity with mathematical proofs and certain degree of mathematical maturity. The course involves mathematical problem solving as well as the design of elegant pseudocodes. There will be no programming assignments.
The subject is the design and analysis of efficient algorithms, with emphasis on ideas rather than on implementation. The complexity of algorithms in a variety of models of computation will be studied; the main emphasis is on asymptotic worst-case analysis. Performance bounds will be rigorously proved.
Design techniques include divide-and-conquer, dynamic programming, greedy algorithms, graph search, various combinatorial optimization techniques, as well as the design of efficient data structures. Methods of algorithm analysis include asymptotic notation, evaluation of recurrent inequalities, the potential function method, methods of basic number theory and linear algebra. We shall discuss the concepts of polynomial-time algorithms and NP-completeness.
e-mail:
laci(at)cs(dot)(university postfix) (do not miss the "cs")
and
lbabai(at)[Google's mail service]
Contact: e-mail.
Please send any messages to both email addresses; each address
has its advantages and disadvantages.
Please do NOT send me messages via Canvas.
TA: Xifan Yu
e-mail: [firstname](at)uchi...
Class notes (slides and iPad notes) will be posted on this webite. Video recordings of lectures and problem sessions will be available on the Canvas/Panopto site.
The instructor places an emphasis on interaction with the students. The primary method of feedback during class is zoom's private "chat" feature. Please make sure you do NOT broadcast your "chat" messages to the class, to permit everybody else to think and send their independent answers.
Outside class, email is the best way to communicate with the instructor.
Your primary text will be the course notes posted on this website, along with the explanations given in class, so please make sure you don't miss classes.
Recommended references:
"Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein
"Algorithm Design" by Jon Kleinberg and Éva Tardos
"Algorithms" by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani
"Invitation to Discrete Mathematics" by Jiri Matoušek and Jaroslav Nešetříl (a wonderful introduction for the mathematically inclined)
"Discrete Mathematics and its Applications" by Kenneth H. Rosen (n-th edition, n=2,3,4,5,...) (a very basic introduction)
Online resources
"MR20" -- Introduction to Mathematical Reasoning via Discrete Mathematics (introductory course, Fall 2020)
"DM" -- Discrete Mathematics Lecture Notes. Skip Sections 2.2 and Chap. 7. DM Sec 2.2 is replaced by ASY (below) and DM Chap. 7 is replaced by PROB (below).
"ASY" -- Asymptotic Equality and Inequality (lecture notes, replaces DM Sec 2.2)
"PROB" -- Finite Probability Spaces (lecture notes)
"LinAlg" -- Discover Linear Algebra (online text)
Puzzle problems for challenge and fun
There are additional online handouts for the following subjects.
Grading will be based on weekly homework assignments, class participation via "chat", and possibly tests. Homework assignments appear on Gradescope and consist of HW (ordinary homework) and Bonus problems posted on this website (click "EXERCISES, material covered" on the banner). For more information, go to the Categories of exercises section below. Class participation will account for 15% of the course grade.
Unless otherwise stated, all homework is due next Tuesday.
Homework problems are posted on this website. They are organized into weekly assignments on Gradescope. You will need to upload your solutions on Gradescope by the deadline stated (usually Tuesday 11:00pm). Problems may be updated. Please make sure to refresh your browser to get the latest version of the homework problems. You may also need to clear your browser's cache to avoid reading an older, cached version.
Errors may occur, both in class and in the posted version of the
problems. Please recheck the website, especially if you suspect an
error.
If you find an error or something looks suspicious in an
assignment (e.g., it seems too easy or it has already been
discussed), please notify the instructor (by email).
Such reports will enhance your class participation score.
Trivial errors. If the error is of a trivial nature (e.g., the statement is false for $n=0$ but true otherwise), you are expected to discover the error, correct the problem, and solve the corrected problem. Merely stating that the problem is in error and giving an easy counterexample will not earn you the credit.
Homework help. Take advantage of the TA's office hours. You may also contact the instructor by email and ask for a hint. See also the Policy on collaboration and Policy on web sources below.
Collaboration on current homework is discouraged but not
prohibited. If you collaborate on a problem, acknowledge this
at the beginning
of your solution (give name(s) of collaborator(s),
state the extent of collaboration). The LaTeX homework
template gives examples of such acknowledgments.
Acknowledged collaboration on homework may incur a minor penalty.
Collaboration may involve discussing ideas, giving/receiving a hint.
You need to understand the ideas discussed and give your own rendering.
Sharing a solution or a significant portion of a solution
before the deadline is not permitted and may incur heavy
penalties on both parties.
You may ask the instructor by email for a hint; there is no penalty
for doing so. Also, take advantage of the TA's office hours.
You may use web sources to study material related to the course.
Looking up solutions to homework problems on the web
is strongly discouraged but not prohibited.
It is counterproductive; solving the problems by yourself
is a key part of learning. Without this experience,
your knoweldge will be superficial. You may ask the
instructor for a hint; there is no penalty for doing so.
If you consult a web source that explains the solution
to a homework problem or a closely related problem, you are
required to state the URL at the beginning of your
solution. Acknowledged use of a web source may incur a small penalty.
Unacknowledged use of a web source may incur a
heavy penalty ranging from zero points for the given
problem to failing the course.
Copying from a web source is strictly prohibited
and is subject to heavy penalties. If you do use a web source,
understand it, close it, wait at least 30 minutes, and
then give your own rendering of the solution.
Soliciting a solution to a homework problem on the web is an extreme violation of academic honesty and may incur disciplinary action in addition to failing the course.
Note that you can set your name in your Zoom profile, so you do not have to go with whatever has been assigned. You may include your preferred pronouns after your last name. I recommend that you follow this practice for multiple reasons. If you set yourself a name that cannot be easily matched to your name on record with the University, please let your instructor know.
You are strongly encouraged to attend the classes synchronously and be an active partiticipant. Our Zoom class meetings will be recorded and saved to the cloud to allow students enrolled in this class to review it and to allow students enrolled in this class who cannot participate synchronously to benefit from the class. It is illegal for anyone other than the instructor to record the class or to post a recording or to pass it on to anyone. The recording is intended to be available only to the participants of this class and will not be available after the quarter ends. However, I am not in the position to prevent illegal activity. If you have FERPA concerns, please mask yourself accordingly, e.g., by turning off the video and using an alias.