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.

Important Dates
  • Midterm I : Tuesday, October 05, 6:30 PM - 8:30 PM, Location: ESJ 0202
  • Midterm II : Thursday, November 11, 6:30 PM - 8:30 PM, Location: ESJ 0202
  • Final : Friday, December 17, 4:00 PM - 6:00 PM, Location: IRB 0324

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


Lectures


Week of
Monday
Wednesday
Friday
08/30 Introduction Maximum Contiguous
Subarray (MCS) sum		 MCS Contd.
Dynamic Programming Approach /
Bubble Sort
09/06 No class - labor day Modified Bubble Sort /
Selection Sort 		Insertion Sort Intro /
Insertion Sort (w/ sentinel)
09/13 Insertion Sort
( Average Case w/ sentinel ) /
Insertion sort w/o sentinel		 Insertion Sort ( Average case w/o sentinel) /
Divide and Conquer 		Mergesort
09/20 Heapsort
(Build Max-heap) 		Heapsort (Sorting max-heap)
Build max-heap analysis		 Heap sort Analysis /
Integer Addition
09/27 Integer Multiplication
(Elementary school algorithm)
 Divide & Conquer Multiplication
algorithm analysis		 Karatsuba Multiplication algorithm
("clever" method)
10/04 Midterm Review Lower & Upper bounds of functions (summations) /
Upper bound of Harmonic series		 Integral approximations
(Summations ,
harmonic series)
(see A.2 in CLRS) /
Constructive Induction
10/11 Intro to Quicksort /
Example /
Quicksort Analysis
(best cases) 		Quicksort Analysis
(Best case, 25-75% split)		 Quick sort Analysis
(random partition sizes, Random Pivot)
10/18 Quicksort Analysis
(Random Pairwise Comparisons)		 Lower bound on
comparison based
sorting algorithms
(Decision Tree) 		Counting Sort
10/25 Radix Sort Bucket Sort Algorithm Bucket Sort runtime analysis
(Average case)
11/01 k-th order statistic (Selection Algorithm)
(worst-case, best-case)		 k-th order statistic(randomized,average case) Select Algorithm
(Blum,Floyd,Rivest,Tarjan,Pratt)
11/08 Intro to Graphs / Graph Representations Midterm II Review Bread First Search
11/15 Depth First Search Eulerian Paths and Circuits Minimum spanning tree
(Generic Algorithm)
Kruskal's MST
11/22 Prim's MST/
Dijkstra's Shortest Path Algorithm 		Thanksgiving break
11/29 Prims / Dijkstra's algorithm Contd. NP-Completeness Intro NP-Completeness Contd. /
Circuit-SAT to Formula-SAT Reduction
12/06 NP Verification NPC Decision / Optimization Problems NP-Completeness wrap-up /
Floyd-Warshall Algorithm
12/13 Review

Staff

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

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


Teaching Assistants

  • Jeovane Slater-Taylor, jmst at umd.edu
  • Jon Nelson, nelson1 at umd.edu
  • Gihan Jayatilaka, gihan at umd.edu
  • Alperen Keles, akeles at umd.edu
  • Ashwin Kammula, akammula at umd.edu

TA Office Hours


Day
Office hours (IRB 1108)
Monday Jeovane: 11:00 AM - 1:00 PM
Tuesday Gihan: 11:00 AM - 1:00 PM,
Jon: 2:00 - 4:00 PM
Wednesday Jon: 1:00 PM - 3:00 PM,
Ashwin: 2:00 PM - 4:00 PM
Thursday Alperen: 9:00 AM - 11:00 AM,
Gihan: 11:00 AM - 1:00 PM ,
Ashwin: 12:30 - 1:30 PM
Friday Alperen: 11:00 AM - 1:00 PM,
Jeovane: 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. 03, 2021
Homework 1 Fri. Sep. 10, 2021
Homework 2 Sat. Sep. 18, 2021
Homework 3 Sat. Sep. 25, 2021
Homework 4 Sat. Oct. 02, 2021
Homework 5 Sat. Oct. 16, 2021
Homework 6 Sat. Oct. 23, 2021
Homework 7 Sat. Oct. 30, 2021
Homework 8 Sat Nov. 06, 2021
Homework 9 Sat Nov. 20, 2021
Homework 10 Sat Dec. 04, 2021
Homework 11 Sat Dec. 11, 2021

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