$\newcommand{\nnn}{\mathbb N}$ $\newcommand{\zzz}{\mathbb Z}$ $\newcommand{\rrr}{\mathbb R}$ $\newcommand{\ccc}{\mathbb C}$ $\newcommand{\fff}{\mathbb F}$ $\newcommand{\eee}{\mathrm e}$ $\newcommand{\vf}{\varphi}$ $\newcommand{\vt}{\vartheta}$ $\DeclareMathOperator{\Div}{\mathrm Div}$ $\DeclareMathOperator{\lcm}{\mathrm lcm}$ $\DeclareMathOperator{\var}{\mathrm Var}$ $\DeclareMathOperator{\cov}{\mathrm Cov}$ $\DeclareMathOperator{\period}{\mathrm per}$ $\DeclareMathOperator{\rank}{\mathrm rk}$ $\DeclareMathOperator{\trace}{\mathrm Tr}$ $\DeclareMathOperator{\span}{\mathrm Span}$ $\DeclareMathOperator{\sgn}{\mathrm sgn}$ $\DeclareMathOperator{\inv}{\mathrm Inv}$ $\DeclareMathOperator{\diam}{\mathrm diam}$

CMSC 27230:  Honors Theory of Algorithms

Winter 2020


What's new | Course description | Course info | Texts | HANDOUTS | Grading, tests | Rules on homework | Policy on collaboration | HOMEWORK, material covered | Statistics | Instructor's past courses

What is new?

PRESS "REFRESH" to find out!

This page is under construction. Refresh your browser to find the latest material.




Old news


Instructor: László Babai

Class schedule


Questionnaire

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.

Go to top


Course description

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.

Go to top


Course information

Instructor:   László Babai     Ryerson 164 and JCL 242

    e-mail: laci(at)cs(dot)etc.   (do not miss the "cs") and
       lbabai(at)[Google's mail service]

Please send any messages to both email addresses; each address has its advantages and disadvantages.

Office hours: by appointment (please send e-mail)

TA:   Goutham Rajendran

     e-mail: [firstname](at)uchi...

  Office hours:    Fri 5:00pm-6:00pm JCL 205   starting Jan 10
  (first office hour will be held by instructor)


Go to top


Text

Your primary text will be your course notes, so please make sure you don't miss classes. If you do, you should copy somebody's class notes and discuss the class with them.

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

LN: Instructor's Discrete Mathematics Lecture Notes (PDF)

FPS: Finite Probability Spaces (updated fragment of LN Chap. 7) (PDF)

Puzzle problems for challenge and fun

HANDOUTS

There are online handouts for the following subjects.

Go to top


Grading    will be based on homework (50%), tests (3 quizzes 6% each, final exam 25%), and class participation (7%). For a grade of A you need to earn at least 60% of the homework Bonus points and 40% of the test Bonus points (in addition to most ordinary (non-bonus) homework points and a good fraction of the ordinary test points). For a grade of A- you need to earn at least 30% of the homework Bonus points and 25% of the test Bonus points (in addition to most ordinary homework points and a good fraction of the ordinary test points).

Test rules
Tests are closed-book. You can use a "cheat sheet": one page of handwritten notes in English, written in ink in your handwriting, with your name printed in large English letters on the top. No photocopies permitted. Hand in your cheat sheet with the test.

The use of electronic devices is strictly forbidden.

For the test, use the space provided on the problem sheets; no scrap paper allowed. Show all your work.

Test dates
First Quiz       Thu, Feb 6,   4:30 - 5:00pm   Ry-276
Second Quiz   Thu, Feb 20,   4:30 - 5:00pm   Ry-276
Third Quiz   Thu, Mar 5,   4:30 - 5:10pm   Ry-276
Final Exam     Mon, Mar 16, 10:30am - 12:30pm   Ry-251


Rules on homework

Typeset your homework in LaTeX, print it in PDF, and submit it on paper. If you are not familiar with LaTeX, you have two weeks grace period to learn it. All homework must be typeset in LaTeX starting January 20. Print your name on each sheet.

Unless otherwise stated, all homework is due next Monday. Hand it in before class.

Homework is stated in class and will also be posted on the website. In case posting is delayed, do the homework as assigned in class. If there is a discrepancy between homework stated in class and posted on this site, the posted version rules. Additional problems, not stated in class, may also be assigned in the posting. Please make sure to refresh your browser to get the latest version of the homework.

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). If you are the first to point out an error, you may receive bonus points. 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; also, notify the instructor.

Homework help. If you encounter difficulties with an assigned problem, try to find a peer who can help. Also, take advantage of the TA's office hours. You may also contact the instructor by email.

Categories of exercises.

Policy on collaboration

Studying in groups is strongly encouraged.

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)). There is no penalty for acknowledged collaboration on homework. DO NOT COPY someone else's solution: after the discussion, throw away any written records. Understand the ideas discussed and give your own rendering.

The same applies to other sources such as the Web: give the source (URL), but DO NOT COPY. Understand; then write your own version without looking at the source or your notes.

Instructor's home page

Department of Computer Science home page

Go to top