CMSC 351 - Algorithms



Section 0301:

This course presents an introduction to the techniques for designing efficient computer algorithms and analyzing their running times. General topics include asymptotics, solving summations and recurrences, algorithm design techniques, analysis of data structures, and introduction to NP-completeness.

Course Information

Textbook (on reserve at McKeldin Library):
  • Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms (3rd Ed.). MIT Press (any edition is fine).
Supplementary Book:

Schedule

Exam Dates


  • Midterm #1: Tuesday, October 6, 6:00 PM - 8:00 PM, Location: Zoom Online
  • Midterm #2: Tuesday, November 10, 6:00 PM - 8:00 PM, Location: Zoom Online
  • Final Exam: Friday, Dec 18, 4:00 PM - 6:00 PM, Location: Zoom Online

Lectures


Week of
Monday
Wednesday
Friday
08/31 Introduction Maximum Contiguous
Subarray (MCS) sum
MCS Contd.
Dynamic Programming Approach
09/07 no class (labor day) Bubble Sort Modified Bubble Sort /
Selection Sort
09/14 Insertion Sort Intro /
Insertion Sort
(w/ sentinel)
Insertion Sort
(w/o sentinel)
(best and worst case)
Insertion Sort
(avg. case w/o sentinel)
09/21
Divide & conquer /
Merge Sort Algorithm
Merge sort analysis Merge sort Analysis /
Heapsort /
heapsort animation
09/28 Heap sort
(Build max heap)
Heapsort
(sort max heap)
Heap sort
runtime analysis
10/05 Midterm Review Integer Addition
Integer Multiplication
(Elementary schhol algorithm)
Integer Multiplication
(Recursive algorithm)
10/12 Recursive Multiplication / Karatsuba "clever" method Lower & Upper bounds of functions (summations) Integral approximations (summations)
(see A.2 in CLRS)
10/19 Integral approximations
(harmonic series)/
Constructive Induction /
Intro to Quicksort
Quicksort Analysis
(Worst, best cases)
Quicksort Analysis
(25-75% split, random partition sizes)
10/26 Random Quicksort
(random partitions)
Random Quicksort
(Pairwise comparisons)
Lower bound on
comparison based
sorting algorithms
(Decision Tree)
11/02 Lower bound on
comparison based
sorting algorithms
(Decision Tree)
Counting Sort Radix Sort
11/09 Midterm II Review Radix Sort Analysis /
Bucket Sort Algorithm
Bucket Sort analysis
11/16 k-th order statistic /
Selection Algorithm
k-th order statistic (best-case, approx. average-case) (Randomized) k-th order statistic(randomized,average case)/

Intro to Select Algorithm
11/23 k-th order statistic
(Blum,Floyd,Rivest,Tarjan,Pratt)

Select Algorithm
Thanksgiving break
11/30 Intro to Graphs / Graph Representations /
Bread First Search
Depth First Search / Eulerian Paths and Cycles Eulerian Paths and Cycles
12/07 Eulerian Paths and Cycles /
Minimum spanning tree (Generic Algorithm)
Kruskal and Prim's MST Dijkstra's Shortest Path Algorithm
12/14
Dijkstra's Shortest Path Algorithm Wrap-up /
NP-Complete

Staff

Instructor
Mohammad Nayeem Teli (nayeem at cs.umd.edu)

Office: Online
Office Hours: MWF 11:00 - 12:00 PM


Teaching Assistants

  • Eric Xiao, erix at umd.edu
  • Jie Li, jli2718 at umd.edu
  • Md Ishat-E-Rabban, ier at umd.edu
  • Ksenia Lekomtceva, klekomtc at umd.edu
Name
Office hours (Online)
Monday Jie: 12:00 PM - 2:00 PM
Tuesday Eric: 10:00 AM - 11:00 AM,
Ksenia: 1:00 - 2:00 PM
Wednesday Ishat: 1:00 PM - 5:00 PM
Thursday Eric: 10:00 AM - 11:00 AM,
Ksenia: 1:00 - 2:00 PM
Friday Jie: 1:00 PM - 3:00 PM


Class Resources

Online Course Tools
  • GradeScope - This is where you submit and view your homework submissions and see your grades.
  • ELMS - This is where you can see your final grades and homework solutions.
  • Piazza - This is the place for class discussions. Please do not post homework solutions here.


Background Material
The following web pages provide some background and other helpful information.



Exam Related Material

Homeworks

Click the name of an assignment below to see its specifications.


Homework Name
Due Date*
Homework 0 Fri., Sep. 04, 2020
Homework 1 Fri., Sep. 11, 2020
Homework 2 Fri., Sep. 18, 2020
Homework 3 Sat., Sep. 26, 2020
Homework 4 Fri., Oct. 02, 2020
Homework 5 Sun., Oct. 18, 2020
Homework 6 Sat., Oct. 24, 2020
Homework 7 Sat., Oct. 31, 2020
Homework 8 Sat. Nov. 14, 2020
Homework 9 Sat Nov. 21, 2020
Homework 10 Sat Dec. 05, 2020
Homework 11 Sat Dec. 12, 2020

* All homeworks are due at 11:59 PM on the due date.