Jan 18 Thu 13:15 "Homework and Material Covered" up-to-date. Please check out the substantial material added asap. Reading: determinants.
Jan 17 Wed 17:10 Slides from today's lecture posted.
Jan 11 Thu Friday's problem session moved permanently to Stuart 102 (the same room as the lectures)
Jan 10 Wed 12:40 Slides from today's lecture posted.
Jan 8 Mon 11:15 Slides from today's lecture posted.
Jan 7 Sun 21:45 Slide from Jan 5 problem session posted.
Jan 5 Fri 14:20 ORD01 and BON01 assignments posted on Gradescope. Problems due Tuesday, Jan 9, 23:00.
Jan 5 Fri 11:30 Slides of Friday's class posted.
Jan 4 Thu 9:40 First batch of "Homework and Material Covered" for the Jan 3 class posted. (Click "Homework and Material Covered" on the banner.)
Jan 3 Wed 14:00 Slides of first class posted. (Click "SLIDES" on the banner.)
REMEMBER: problem session
every Friday 16:30-17:20, Stuart 102 (moved from Cobb 106).
First session: Friday, January 5.
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.
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 Winter 2020 course by the same title and course number, the overlap will be significant, and a most valuable source of information about the course content is the Homework, material covered section of the 2020 course website.
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)
Introductory material Kenneth H. Rosen: Discrete Mathematics and its Applications ($n$-th edition, $n=2,3,4,5,\dots$)
Online resources
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
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)
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," i.e., two PDF files per week: one for the "ORD" assignment and one for the "BON" assignment.
Please typeset each solution 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.
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 name of collaborator(s)). You may share ideas, not entire solutions. Sharing .tex source 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 deal 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. 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.
In any case, if you use a web source, acknowledge the source, include the URL at the beginning of your solution. If the URL is long (longer than 15 characters, excluding the "https://" prefix), please also send it by email to the instructor (because it is not possible to cut and paste from the Gradescope site).
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.