CMSC 351 - Algorithms



Section 0101:

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: Thursday, October 3, 6:30 PM - 8:30 PM, Location: ESJ 0324, SKN 0200
  • Midterm #2: Thursday, November 7, 6:30 PM - 8:30 PM, Location: ESJ 0324, ESJ 0202
  • Final Exam: Friday, December 13, 4:00 PM - 6:00 PM, Location: ARC 0204, KEY 0106

Lectures


Week of
Monday
Wednesday
Friday
08/26 Introduction Maximum Contiguous
subarray sum
Maximum subarray sum /
Bubble sort
09/02 Labor Day (No Class) Bubble Sort Contd. /
Intro to insertion sort
Insertion Sort Analysis
09/09 Insertion sort without
sentinel (Analysis)/
Selection sort
Merge Sort /
Analysis
Heap sort /
Heap sort animation
09/16 Heap build analysis Heap sort analysis /
Integer Addition,
Integer Multiplication
(Brute force)
Integer Multiplication
(Divide and Conquer)
09/23 Integer Multiplication
(Karatsuba Approach /
Clever method)
Lower and Upper
bounds of functions (summations)
Integral Approximations (Summations) /
Constructive Induction /
Intro to Quicksort algorithm
09/30 Quicksort Analysis
(Worst Case)
Midterm Review Quick Sort Analysis
best case (Median pivot)/
"approximate" average case (25%-75% split)
10/07 Quicksort Analysis
(Randomized pivot)
Randomized QS Analysis
(Pairwise comparisons)
Decision Trees
(Lower bound on
comparison based sorting )
Intro to Counting sort
10/14 Counting sort
Intro to Radix sort
Radix sort Bucket sort
10/21 kth order statistic
( Selection algorithm)
Best and worst case
Selection - Avg. case Worst-case Selection (deterministic)
(kth order statistic)
10/28 Deterministic Select Analysis /
Intro to Graphs
Breadth First Search/
Depth First Search
Eulerian Paths and Cycles
11/04 Minimum Spanning Trees (MST) Midterm Review Kruskal's and Prim's
MST algorithms
11/11 Dijkstra's shortest path algorithm Dijkstra's algorithm Dijkstra's wrap-up / Intro to
Random Number Generators
11/18 Random Number Generators /
Intro to NP-Completeness
NP-Completeness /
Circuit-SAT to Formula-SAT reduction
Optimization / decision problem
(example: Independent set)
11/25 Polynomial runtime
Random walk algorithm
for 2-SAT
Thanksgiving break
12/02 All pairs shortest path
Floyd-Warshall Algorithm
Transitive Closure Karger's min-cut algorithm
12/09 Final Review (last day of class)

Staff

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

Office: 1128 IRB
Office Hours: MWF 2:00 - 3:00 PM


Teaching Assistants


Administrators:

  • Anton Pozharsky (apozharski@gmail.com)
  • Eric Xiao (ericxiao2013@gmail.com)

Name
Email
Anton Pozharsky apozharski@gmail.com
Deep Patel dpatel17@umd.edu
Eric Xiao ericxiao2013@gmail.com
Jie Li jli2718@umd.edu
Mara Levy mlevy2525@gmail.com
Matthew Walmer mwalmer@cs.umd.edu
Harihara Muralidharan hsmurali@cs.umd.edu
Peihong Yu peihong@umd.edu
Masataro Koizumi masataro.koizumi@gmail.com
Ruochen Wang rwang113@terpmail.umd.edu
Shubhankar Sachdev ssachdev@terpmail.umd.edu
Bryce Toole bctoole@gmail.com


TA Office Hours

All TA office hours take place in room IRB 1108. Please note that a TA may need to leave 5 minutes before the end of the hour in order to go to his/her class. Please be understanding of their schedules.

Time MON TUE WED THU FRI
9:00 - 10:00 Ruochen Mara Ruochen
10:00 - 11:00 class Mara class Masa class
11:00 - 12:00 Hari Hari Bryce Anton Anton
12:00 - 1:00 Hari Hari Shubhankar Deep Eric
1:00 - 2:00 Matt Peihong Matt Peihong Masa
2:00 - 3:00 Matt Peihong Anton / Matt Peihong / Mara Jie
3:00 - 4:00 Jie Bryce / Deep Eric Mara Jie
4:00 - 5:00 Jie Bryce Eric
5:00 - 6:00 Shubhankar Shubhankar

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 Aug. 30, 2019
Homework 1 Sep. 6, 2019
Homework 2 Sep. 14, 2019
Homework 3 Sep. 21, 2019
Homework 4 Sep. 28, 2019
Homework 5 Oct. 12, 2019
Homework 6 Oct. 19, 2019
Homework 7 Oct. 26, 2019
Homework 8 Nov. 02, 2019
Homework 9 Nov. 16, 2019
Homework 10 Nov. 23, 2019
Homework 11 Dec. 06, 2019