This page is under construction. Refresh your browser to find the latest material.
We are MOVING to Stuart 104
immediately, starting with this Wednesday's class (Jan 15).
To get to Stuart Hall, go South from the center of the
Main Quad. You get into the "Harper Quadrangle." Walk almost all the
way down HQ. Stuart Hall will be to your left, an entrance similar
to the Ryerson entrance. 104 is a few stairs up, to your right.
REMEMBER: problem session
every Friday 16:30-17:20, Stuart 104 (previously Ryerson 255)
First session: Friday, January 10.
The problem session is followed by an office hour.
There will be frequent postings on this course website. Please check it frequently, and always REFRESH your browser.
03-07 11:20 Today's slides posted (lecture 26, March 7)
03-07 2:50 Wednesday's slides posted (lecture 25, March 5)
03-05 4:10 Monday's slides posted (lecture 24, March 3)
03-02 23:10 Last Friday's slides posted (lecture 23, problem session 02-28)
02-28 4:00 Eighth assignment posted on Gradescope. Due Tue, March 4 at 23:00.
02-27 16:00 Most problems due Tue Mar 4 have been posted on the course website. 16:20 Wednesday's slides posted (lecture 22, Feb 26)
02-26 2:00 Monday's slides posted (lecture 21, Feb 24)
02-25 11:50 Last Friday's slides posted (lecture 20, problem session)
02-21 01:20 Seventh assignment posted on Gradescope. Due Tue, Feb 25 at 23:00.
02-19 17:00 SLIDES up to date: Class #19 posted. The slides have been significantly updated: the verbal information about Edmonds's result (polynomiality of Gaussian elimination) is now written is detail.
02-17 21:45 SLIDES up to date: Feb 14 problem session and Classes ##17-18p (Feb 14, 17) updated, posted (DO READ THEM). "Material covered" up to date (Classes ##17-18).
02-16 12:30 Sixth assignment posted on Gradescope. Due Tue, Feb 18 at 23:00.
02-13 12:40 SLIDES up to date: Feb 7 problem session and Classes ##15-16 (Feb 10, 12) posted
02-12 2:45 First batch of homework problems posted. Due Feb 18.
02-08 9:15 Fifth assignment posted on Gradescope. Due Feb 11.
02-07 14:40 First batch of homework problems posted (due Feb 11).
02-07 12:20 SLIDES up to date: classes ##12-14 (Feb 3, 5, 7) and 3rd problem session (Jan 31) posted
01-31 15:30 Fourth assignment posted on Gradescope. Due Tue, Feb 4 at 23:00.
01-31 12:25 The slides of Class #11 (Jan 31) have been updated and posted. (Click SLIDES on the banner). The UPDATES on the last page (BFS) are important. The mistakes made in class have been fixed, and parent links have been added to the pseudocode; they organize into the BFS tree. The parent of vertex $y$ is $x$ if $y$ has been discovered while exploring $x$, i.e., $y$ is an out-neighbor of $x$ and not an out-neighbor of any vertex discovered before $y$.
01-30 19:00 The slides of Classes #9 and #10 (Jan 27 and 29) and the third problem session (Jan 24) have been posted. The last page of the Jan 24 Problem session has added material about the hardness of approximation (last page).
01-24 12:05 Third assignment posted on Gradescope. Due Tue, Jan 28 at 23:00.
01-24 11:36 The slides of Class #8 (Jan 24) have been revised and posted. Check out p6 (Heapify on $O(n)$ comparisons).
01-24 4:15 Homework related to 7th lecture (Jan 22) posted on the course website. (Click "HOMEWORK, material covered" on the banner.) Due Jan 28 except where stated otherwise.
01-22 17:00 The slides of the seventh lecture (Jan 22) have been revised and posted (click SLIDES on the banner). IMPORTANT! Please CHECK the bottom of p.8: the MERGE-SORT algorithm, stated in the last minutes of class, had multiple errors. These have been fixed.
01-18 12:00 IMPORTANT!
Inspired by the discussion during the 2nd problem session (Jan 17),
I posted a set of DO exercises, numbered P2.10 -- P2.54.
(Click HOMEWORK, material covered > #P2 on the banner.)
These exercises will help clarify misunderstandings regarding the concepts
of limits and asymptotic equality that seem to affect a majority
in this class. DO solve these exercises.
If you already possess conceptual clarity on these issues,
each exercise will take you seconds to solve. If you don't, it will give
you insights you missed while studying the basics of logic and calculus,
and without such foundations you will struggle throughout this course
and throughout your career whenever you encounter theoretical
concepts that now permeate discussions of computer science.
01-17 21:00 The slides of the sixth lecture (Jan 17) have been slightly revised and posted (click SLIDES on the banner)
01-17 15:00 Second assignment posted on Gradescope. Due Tuesday, Jan 21 at 23:00.
01-17 14:30 Homework, study material for sixth class posted
01-15 15:30 More problems, study material for fifth class posted.
01-15 14:25 "Communication complexity" section added to the Class #1 material. (Click "HOMEWORK, material covered" and then "#1" on the banner.)
01-15 11:45 The first batch of homework problems due Tue, Jan 21, has been posted.
01-15 11:00 The slides of the fifth lecture have been slightly revised and posted (click SLIDES on the banner)
01-13 12:00 The slides of the first problem session and the fourth lecture have been revised and posted
01-11 09:55 Assignment posted on Gradescope. Due Tuesday, Jan 14, 23:00. Use the LaTeX template provided (click "LaTeX HW template" on the banner).
01-11 08:45 Challenge problems and historical remarks added to the Class #3 homework page (click "HOMEWORK, material covered" on the banner).
01-10 14:55 Homework problems posted: click "HOMEWORK, material covered" on the banner. Due Tue, Jan 14, 23:00 on Gradescope.
01-10 13:45 The slides of the third lecture have been revised and posted.
01-09 03:00 The slides of the first two lectures have been posted. Click "SLIDES" on the banner.
Health warning. Covid is now endemic. I encourage everybody get the latest updated Covid vaccine. Remember that the effectiveness of vaccines diminishes with passing time, another reason to get revaccinated. Remember also that even with the vaccine, you can get the virus (but your illness is likely to be much milder) and you can spread the virus even while you have no symptoms. -- Flu vaccine is also strongly recommended. Masks are optional but recommended because our classroom is crowded. Remember that the N95 masks reduce the spread of the both Covid and the flu. The instructor does not wear mask because the mask impedes understanding what is being said.
Homework problems will be posted on this website. Homework is due every Tuesday by 23:00, submitted online on Gradescope.
The instructor places an emphasis on interaction with the students.
Outside class, email is the best way to communicate with the instructor.
Instructor: László Babai
Class schedule
e-mail: laci(at)u.e. (expand abbreviation) and lbabai(at)[Google's mail service]
I have experienced a variety of uncertainties about email. When sending me a message, please use BOTH email addresses to help ensure that I see it.
Office hours: The weekly problem sessions (Fri 4:30-5:20) will be followed by an office hour. Please send me email if you wish to have a one-on-one appointment.
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 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.
While this course will not be identical with the instructor's previous courses by the same title, the overlap will be significant, the material of those courses, posted on this website, is a valuable source of information about the content of this course. Please consult the material of the Winter 2024 course by the same title and course number and especially the "Homework, material covered " section of that course.
Your primary text will be your course notes.
So please make sure you don't miss classes.
If you do, try to discuss the class with a peer
and copy their notes.
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)
"Linear Algebra Done Wrong" by Sergei Treil (highly recommended text on linear algebra over the real and complex numbers)
Introductory material Kenneth H. Rosen: Discrete Mathematics and its Applications ($n$-th edition, $n=2,3,4,5,\dots$)
DMmini: Instructor's Discrete Mathematics Lecture Notes (PDF)
PROB: Finite Probability Spaces (update of DM Chap. 7) (PDF)
ASY: Asymptotic Equality and Inequality (update of DMmini Chap. 1.1) .
LinAlg: Discover Linear Algebra (linear algebra presented in sequences of exercises)
Discrete Math Lecture Notes by Morgan Sonderegger and Lars Bergstrom (PDF)
(detailed notes based on the instructor's 2007 DM class, but not proofread by instructor)
REAS22: "Introduction to Mathematical Reasoning via Discrete Mathematics 2022" (introductory course for those without a strong background in mathematical reasoning)
There are online handouts for the following subjects.
Puzzle problems for challenge and fun
Grading scheme Homework 85% Class participation 15%
Homework problems are posted on this website;
Please make sure to refresh your browser to
get the latest version of the homework problems.
The problems are organized into weekly assigments on Gradescope.
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) as soon as possible. This will help you and everyone else in class. 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.
Homework help. If you encounter difficulties with an assigned problem, you may contact the instructor by email.
While solutions to Challenge problems don't earn you credit toward your grade, they do earn you the instructor's attention, in addition to giving you valuable experience. If you later ask me for a letter of recommendation for graduate study, the first thing I will ask, which challenge problems did you solve.
On Gradescope you will find a brief description of each problem. These descriptions do NOT constitute the problem statements. You find the authentic statement of each question on the course homepage. (Click "HOMEWORK and material covered" on the banner.)
Please use the LaTeX homework template (click on the navigation bar on the top) to typeset your solutions. Make sure to put in your name, and for each solution, complete the entry "Sources and collaborations" (see "Policy on collaboration and the use of web sources and AI tools" below). If you did use AI tools, mention it in "Sources and collaborations" and send me a detailed report by email. (Write "None" if you did not use sources and did not collaborate.)
Please upload one PDF file per "assignment."
Please typeset your solution top each problem on a separate page (but parts (a), (b), etc. of the same problem can go on the same page).
IMPORTANT: As you upload your PDF file,
Gradescope will ask you to assign page numbers to each solution.
If a solution extends over more than one page, you need to assign
each of those pages to the problem. Failing to accurately assign the pages
causes significant extra work for the graders and may the grader overlook
a solution.
If you do not submit a solution to a problem, please assign "page 1"
(the cover page) to the problem.
Collaboration on current homework is discouraged but not prohibited. If you do collaborate, state it at the beginning of your solution (give the name(s) of your collaborator(s)). You may share ideas, not entire solutions. Sharing .tex source files or fragments of such files is strictly prohibited. DO NOT COPY someone else's solution. If you got some help, understand the ideas discussed and give your own rendering. Violation of these rules constitutes academic dishonesty and will be dealt with accordingly.
Posting a solution to an assigned problem online without the instructor's permission is a serious academic offense.
Use of the Web. You may look up pertinent general information online but not the posted solution to a problem that significantly overlaps with the problem assigned.
Do NOT SEARCH for a solution to the specific problem assigned. If you found a closely related website, okay, but include the link in your homework submission and also send the link to the instructor by email (because I am unable to cut and paste from the Gradescope site). DO NOT COPY: understand, then write your own version without looking at the source.
Unfortunately, by widespread abuse of the web, you can find solutions online to the great majority of the most elegant and instructive problems. Use the web with restraint. The way to learn matematical subjects (such as the Theory of Algorithms) is by discovering it through solving problems. If you look up the solutions, you are denying yourself the experience of discovery.
Using AI tools. At this point I am not prohibiting this, but this policy may change. For now, if you do use AI tools, acknowledge it at the beginning of the solution, and send me, by email, a detailed report of what exactly you were using, and how. The report should be sufficiently detailed to allow me to reproduce your experiment. Tell me about your experience and your opinion about the pros and cons of using these tools.
Note that you can set your name in your Zoom profile, so you do not have to go with whatever has been assigned. If you set a name that cannot be easily matched to the your name on record with the University, please let your instructor know.