### 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.

### Schedule

- Lecture 1, Aug 26
- Course Logistics
- 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.