University Course Catalog Description

Advanced design and analysis techniques: dynamic programming, greedy algorithms, amortized analysis. Advanced data structures: Fibonacci heaps, union-find data structures. Study of variety of special topics, which may include: graph algorithms, optimization problems, Fast Fourier Transform, string matching, geometric algorithms, NP-completeness and approximation algorithms.

Course objectives

By the end of the course you are expected to gain the following skills:

1. Understanding design techniques of algorithms
2. Understanding how to analyze the performance of algorithms
3. Implementing and testing algorithms
4. Showing correctness and efficiency of algorithms

Prerequisites

1. CSCI-2312 – Object Oriented Programming
2. CSCI-2421 – Data Structures and Program Design
3. CSCI-2511 – Discrete Structures
4. CSCI-3412 – Algorithms

Required Textbooks

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein (2022). Introduction to Algorithms (4th edition). We will call it the CLRS textbook. MIT Press https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/.

Schedule

Week 1

• Introduction – The Role of Algorithms in Computing (CLRS: Chapter 1)
• Space and time complexity; Asymptotics (CLRS: Chapter 3)

Week 2

• Divide and Conquer; Recurrences (CLRS: Chapter 4)

Week 3

• Dynamic Programming (CLRS: Chapter 14)
• Greedy Algoriothms (CLRS: Chapter 15)

Week 4

• Median Finding algorithms (CLRS: Chapter 9)
• Quicksort (CLRS: Chapter 7),

Week 5

• BST (CLRS: Chapter 12)
• Heaps, Heapsort (CLRS: Chapter 6)

Week 6

• Red Black Trees (CLRS: Chapter 13)
• Union Find (CLRS: Chapter 19 / Data structures for disjoint sets)

Week 7

• Introduction to Graphs (CLRS: Chapter 20/ Elementary Graph Algorithms)
• BFS, DFS (CLRS: Chapter 20/ Elementary Graph Algorithms)
• Minimum Spanning Trees, Kruskal’s algorithms (CLRS: Chapter 21)

Week 8

• Reserved for midterm exam.

Week 9

• Shortest Path (CLRS: Chapter 22 / Single Source Shortest Paths; Chapter 23 / All-pairs shortest Paths)
• Network Flow (CLRS: Chapter 24: Maximum Flow)

Week 10

• Bipartite Matching (CLRS: Chapter 24.3 Maximum Bipartite matching)
• String Matching Algorithms (CLRS: Chapter 32 / String Matching)

Week 11

• String Matching Algorithms (CLRS: Chapter 32 / String Matching)

Week 12

• Matrix operations (CLRS: Chapter 28)

Week 13

• Linear Programming (CLRS: Chapter 29)

Week 14

• NP-Completeness (CLRS: Chapter 34)

Week 15

• NP-Completeness (CLRS: Chapter 34)

Week 16

• NP-Completeness (CLRS: Chapter 34)
• Approximation Algorithms (CLRS: Chapter 35)

Week 17

• Reserved for final exam.