Location & Time

TR 6.30 PM-7.45 PM
113 IST Building

Recitation Sections

Mondays, Willard Building
001: 9.05 AM-9.55 AM (room 318)
002: 11.15 AM-12.05 PM (318)
003: 10.10 AM-11.00 AM (103)
004: 12.20 PM-1.10 PM (369)
005: 1.25 PM-2.15 PM (075)

Instructor

Prof. Kamesh Madduri
Office hours:
MTR 3.00 PM-4.00 PM (343E IST)
Appointment (cal)

Teaching Assistants

Xin Chen
TR 2.30 PM-3.30 PM (338E IST)
Yu-San Lin
W 1.00 PM-2.00 PM (338E IST)
F 10.00 AM-11.00 AM (338E IST)
Xianliang (Leon) Zhang
T 4.00 PM-5.00 PM (338E IST)
F 1.00 PM-2.00 PM (338E IST)

Important Dates

Aug 26. First class
Oct 02. Midterm 1
Nov 11. Midterm 2
Dec 16. Final exam

Course Objectives

This class introduces undergraduate students to the principles of efficient algorithm design, and teaches them how to analyze the asymptotic behavior of both recursive and non-recursive algorithms. The first objective is to teach a precise notion of efficiency: time and space complexity. The second is to provide mathematical tools to compare efficiency of various algorithms or programs. These tools contain the basic methods for finding the rates of growth of functions, which include solving recurrence relations. A part of this objective is to convey the dramatic importance of the selection of an appropriate algorithmic method for a given task. The third goal is to provide a variety of tools which are indispensible in the design of efficient algorithms. These tools consist of: (a) building blocks, which include the most important data structures and several classic algorithms, (b) design paradigms, including divide-and-conquer, greedy and dynamic programming; several classic algorithms are presented as applications of these paradigms. It is assumed that students entering this class know how to analyze algorithms for correctness, but further mastery of this aspect of algorithm design is also an objective of this course.

Topics

Introduction, Asymptotic Notation, Recurrences, Divide-and-conquer, Dynamic Programming, Greedy Algorithms, Elementary data structures, Heaps, Hash Tables, Binary Search Trees, Sorting Algorithms, Graph Algorithms, NP-Completeness.

Syllabus

Last updated Oct 20. pdf icon

Schedule

Lecture 1, Aug 26
Course Logistics pdf icon
Introduction
Insertion sort algorithm
CLRS (textbook) Chapter 1, 2.1, 2.2
Lecture 2, Aug 28
Loop invariants
Divide-and-conquer: Introduction
Merge sort algorithm, analysis
Asymptotic notation
CLRS Chapter 2.2, 2.3, 3.1, 3.2
Lecture 3, Sep 2
Asymptotic notation
Strassen's algorithm
DFT and FFT
Solving recurrences: Substitution
CLRS Chapter 3.1, 3.2, 4.2, 4.3, 30.2
Lecture 4, Sep 4
The maximum-subarray problem
Solving recurrences: Recursion tree method
Solving recurrences: Master method
Python tutorial
CLRS Chapter 4.1, 4.4, 4.5
Lecture 5, Sep 9
HW1 discussion
Review of Lecture 4 notes
Dynamic set ADT
Linked lists
CLRS Chapter 10.2
Lecture 6, Sep 11
Stacks and queues
Dynamic Programming: Introduction
Rod cutting problem
CLRS Chapter 10.1, 15.1, 15.3
Lecture 7, Sep 16
Computing terms of Fibonacci series
Computing binomial coefficients
Weighted interval scheduling
Matrix-chain multiplication
CLRS Chapter 15.2, 15.3
Online reading
Lecture 8, Sep 18
Knapsack problem
LCS, Edit distance
Dynamic programming exercises
CLRS Chapter 15.4
Online reading
Lecture 9, Sep 23
HW2 solutions discussion
Greedy algorithms: Introduction
Activity Selection problem
CLRS Chapter 16.1, 16.2
Lecture 10, Sep 25
Dynamic programming exercises
HW3 solutions discussion
Lecture 11, Sep 30
Review for Midterm 1
Practice exam solutions discussion
Midterm 1, Oct 2
In-class (6.30-7.45 pm), closed book exam
Lecture 12, Oct 7
Interval partitioning
Fractional knapsack problem
Greedy algorithms exercises
CLRS Chapter 16.1, 16.2
Lecture 13, Oct 9
Greedy algorithms, more problems
Priority queues
CLRS Chapter 16.1, 16.2, 6.5
Lecture 14, Oct 14
Heaps
Maintaining heap property
CLRS Chapter 6.1, 6.2
Lecture 15, Oct 16
Building a heap
Heapsort algorithm
CLRS Chapter 6.3, 6.4
Lecture 16, Oct 21
Quicksort
CLRS Chapter 7
Lecture 17, Oct 23
Comparison sorting lower bound
Maximum and Minimum
Selection in expected linear time
CLRS Chapter 8.1, 9.1, 9.2
Lecture 18, Oct 28
Deterministic selection in linear time
Counting sort
CLRS Chapter 9.3, 8.2
Lecture 19, Oct 30
Radix sort, bucket sort
Hash tables
CLRS Chapter 8.3, 8.4, 11.1-11.3
Lecture 20, Nov 4
Hash tables
CLRS Chapter 11.1-11.3
Lecture 21, Nov 6
Midterm review
Midterm 2, Nov 11
In-class (6.30-7.45 pm), closed book exam
Lecture 22, Nov 13
Midterm 2 solutions discussion
Lecture 23, Nov 17
Hash tables: open addressing
CLRS Chapter 11.4
Lecture 24, Nov 18
Binary Search Trees
CLRS Chapter 12
Lecture 25, Nov 20
Network Science: Introduction
Lecture 26, Dec 1
Representing graphs
BFS
CLRS Chapter 22.1, 22.2
Lecture 27, Dec 2
DFS
CLRS Chapter 22.3
Lecture 28, Dec 4
SSSP
Bellman-Ford algorithm
Dijkstra's algorithm
Graph algorithms in Python
CLRS Chapter 24.1, 24.3
Lecture 29, Dec 9
NP-Completeness: Introduction
CLRS Chapter 34
Lecture 30, Dec 11
Final exam review
Final exam, Dec 16
(Comprehensive) final exam

Textbook

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, third edition, MIT Press, 2009.

Prerequisites

CMPSC 122; CMPSC 360 or MATH 311W.

Class material

Lecture slides, code, homeworks, assessments, and general class announcements will be posted on Angel. We will use Piazza for class discussions and for clarifications regarding homeworks and exams.



Last updated: