CMPSC 465 - SPRING 2013
LAST UPDATED 06/27/13 10:22
Data Structures and Algorithms
Course Info & Policies   •  Schedule   •  Resources   •  Solutions

Schedule and Assignments

Jump to Unit 1Jump to Unit 2Jump to Unit 3Jump to Unit 4Jump to Unit 5

This schedule is always subject to change. Anything posted for a week other than the current week should be considered in "draft" form.

date day topic, notes, activities textbook chapter and/or section out-of-class work (problems in for next MWF class unless noted) and announcements
UNIT 1: Introduction to Analysis and Divide-and-Conquer
M 01/07 1 CLRS 1, 2.1

Autobiography

Lab in Recitation: Sorts and Counting Operations. All recitation sections meet in 220 IST today, not in EES.

W 01/09 2
  • Intro to Analysis and Asymptotic Notation
    • Warm up
    • The Idea and graphical view
    • Formal definitions: Θ, O, Ω
    • Examples in asymptotic notation
    • Properties of asymptotic notations
    • Issues with inequalities
Epp 11.2 (4-9, 10, 12 were do-able this day)
F 01/11 3
  • Intro to Analysis and Asymptotic Notation, ctd.
    • Power and polynomial functions
    • Basics of analyzing algorithms

Epp
11.2
11.3

11.2: 4-9, 10, 12, 16, 29, 34, 35, 38, 40, 42, 44
M 01/14 4
  • Intro to Analysis and Asymptotic Notation, ctd.
    • Code fragment examples
    • Analysis of insertion sort
  • Analysis with Exponential and Logarithmic Functions
    • Basics
    • Properties with logs and floors
    • Recurrences with logarithmic solutions
    • Orders with Logs and Exponentials

Epp
11.3
11.4

11.3: 1, 2, 6, 8, 9, 11, 12, 13, 14, 19

11.4: 56

Part II of Lab (or Programming Assignment 1), for recitations, meeting in 220 IST instead of EES today.

W 01/16 5
  • Analysis with Exponential and Logarithmic Functions
    • O-arithmetic and dominance summary
    • Analyzing binary search
    • A little merge sort analysis

Epp
11.4
11.5

11.4: 10, 15, 17, 23, 29, 30, 31, 35, 46, 56

11.5: 11.5: 8-11, 16

F 01/18 6
  • Misc. Analysis and Correctness
    • o and ω
    • Odds and ends about order notation
    • Monotonicity, etc.
    • Polynomially bounded functions
    • Conventions on analysis from CLRS and the RAM model
    • Loop invariants and correctness proofs
  • Intro to Divide-and-Conquer via Merge Sort
    • Algorithm design and D&C
    • Merge sort
CLRS
2.1
2.2
2.3
CRLS Exercise 2.1-3
M 01/21
MLK Day - No Class
W 01/23 7
  • Intro to Divide-and-Conquer via Merge Sort
    • Merge sort
    • Merging in linear time
    • Correctness of the merge algorithm
    • Recurrences
    • Merge sort recurrence
CLRS
2.3
4.0
4.1
4.3

--

Begin solving Unit 1 Challenge Problems

F 01/25 8
  • Intro to Divide-and-Conquer via Merge Sort
    • Merge sort recurrence
    • Analysis via recursion tree
  • Maximum Subarray Problem
    • The problem
    • The algorithm
    • Analysis

CLRS
2.3
4.4
4.1

CLRS Exercises 2.3-1, 2.3-2

Problem in Max Subarray Notes

M 01/28 9
  • Recursion Trees and the Master Theorem
    • Recursion Trees

CLRS
4.1
4.5
4.6

CLRS Exercises 4.4-1, 4.4-3, 4.5-1
W
01/30
10

CLRS 4.6

KT 5.3

CLRS Exercise 4.5-3

KT Reading

R 01/31

EXAM 1 - 8:15 p.m. in 101 Thomas [Exam Info.]
Review Session Offered Wednesday at 8:15 p.m. in 114 EES

UNIT 2: Sorting (& More)
F 02/01 11
  • Heaps and Heapsort
    • What a Heap Looks Like
    • Storing Heaps in Arrays
    • Heapify
    • Building a Heap
6.1
6.2
6.3
CLRS Exercises 6.1-1, 6.1-3, 6.1-4, 6.1-6, 6.2-1, 6.2-2
M 02/04 12
  • Heaps and Heapsort
    • Correctness of Build-Heap
    • Analysis of Build-Heap
    • Heapsort
6.3
6.4
 
W 02/06 13
  • Heaps and Heapsort
    • Heapsort
    • Heapsort Analysis
    • Other Heap Matters
  • Priority Queues
    • Big Picture
    • Operations

6.4
6.5

CLRS Exercises 6.3-1, 6.3-2, 6.4-1, 6.4-2, 6.4-3

CLRS Exercises 6.5-1, 6.5-2

F 02/08 14
  • Quicksort
    • High-Level Overview
    • Partitioning
    • Analysis of Partitioning
7.1
7.2
 
M 02/11 15

7.2
8.0

CLRS Exercises 7.1-1, 7.1-3, 7.2-1, 7.2-4
W 02/13 16
  • Analyzing Comparison vs. Linear Time Sorting
    • Sorting: The Big Picture
    • Bounding Comparison Sorts
    • Counting Sort and Radix Sort in a Nutshell
    • Bucket Sort

8.1-4

Begin Unit 2 Challenge Problems
F 02/15 17
  • Analyzing Comparison vs. Linear Time Sorting
    • Bucket Sort
    • Analysis of Bucket Sort

8.4

CLRS Exercises 8.4-1, 8-4.2, 8-4.3

Read 10.1, 10.2, 10.4 and review this from 122 as needed

UNIT 3: Searching and Trees
M 02/18 18
  • Finish Bucket Sort
  • Hashing
    • Dictionaries and Dynamic Sets
    • Why Hashing?
    • Direct Address Tables
    • Collision Resolution with Chaining
    • Load Factor and Other Performance Influences
11.1-4

Start Programming Assignment #2 (due next week)

CRLS Exercise 11.1-1

W 02/20 19
  • Hashing
    • Load Factor, etc., ctd.
    • Analysis of Hashing with Chaining
  • Two out-of-class responsibilities
    • Study Epp 10.6 as necessary
    • Readings and active note taking on Undecidability and NP-completeness - due early April

11.1-4

CLRS Exercises 11.2-1, 11.2-2, 11.2-3
R 02/21

EXAM 2 - 8:15 p.m. in 101 Thomas [Exam Info.]
Optional Exam Review Tuesday at 8:30 p.m. in 26 Hosler

F 02/22 20
  • No lectures
--

Study Epp 10.6 on your own if you didn't do it in 360 (you did with me)

M 02/25 21
  • Hashing
    • Picking Hash Functions
    • A Taste of Universal Hashing
    • Open Addressing
    • Brief Open Addressing Analysis
11.1-4 CLRS Exercises 11.3-3, 11.3-4, 11.4-1
W 02/27 22
  • Binary Search Trees
    • Review & Extension
    • Minimum and Maximum
    • Successor and Predecessor
    • Transplant
    • Deletion

12.1
12.2
12.3

CLRS Exercises 12.2-2, 12.2-3, 12.2-4, 12.3-1, problem in notes
F 03/01 23
  • Finish Binary Search Trees
  • Review of an Old Problem
  • Red-Black Trees
    • The Big Picture
    • Black Height and Red-Black Properties
13.1
13.2
Relax and enjoy your break!
03/02
to
03/10
Spring Break - No Class
M 03/11 24
  • Red-Black Trees
    • Consequences of RB Properties
    • Thinking about Insertion/Deletion
    • Rotations
    • Rotations
    • Cases of Insertion
    • Insertion, Formally
    • Performance of Insertion
13.3

CLRS Exercises 13.1-1, 13.1-2, 13.1-5, 13.2-1, 13.2-4, 13.3-2, 13.3-3

Formal Problem Write-Up 1, due Friday

W 03/13 25
  • 2-3-4 Trees
    • Motivating Example
    • Definition
    • Splitting Nodes
    • Insertion
    • Capacity
--

Problems available in notes packet only

Challenge Problems (PDF)

F 03/15 26
  • B-Trees
    • The Big Picture
    • Definition
    • Height Issues
    • Searching
    • Creating
    • Splitting Nodes
    • Insertion
18.0-2 CLRS Exercises 18.1-1, 18.1-2, 18.1-3 (but using t = 3 instead), 18.1-4, 18.1-5
M 03/18 27
  • B-Trees
    • Performance of Basic B-Tree Operations
    • Deleting Keys
18.2-3 CLRS Exercises 18.2-3, 18.2-6, 18.3-1, 18.3-2
UNIT 4: Graph Algorithms
W 03/20 28
  • Wrap up B-trees and Unit 3
  • Representations of graphs
  • Graph Traversals: The Idea
22.1
22.2
See notes handout
R 03/21

EXAM 3 - 8:15 p.m. in 101 Thomas [Exam Info.]

F 03/22 29
  • Basics of Graphs from 360
    (Only at 10:10, optional, recommended only if you didn't take 360 with me)
    • Terminology, Special Kinds
    • Subgraphs
    • Degree
    • Spanning Trees
Epp 10.1, 10.7  
M 03/25 30
  • Graph Traversals
    • Colors and Attributes of Vertices for BFS
    • BFS Algorithm
    • BFS Example
    • BFS Analysis
    • BFS Spanning Trees
22.2 CLRS Exercises 22.2-1, 2 <--- note correction from packet
W 03/27 31
  • Graph Traversals
    • Attributes for DFS
    • DFS Algorithm
    • DFS Example
    • DFS Analysis
    • DFS Trees and Graph Structure Observations
22.3 CLRS Exercises 22.3-1, 2, 3, 7
F 03/29 32
  • Graph Traversals
    • DFS Trees and Graph Structure Observations
  • Directed Acyclic Graphs and Topological Sort
    • DAGs and Partial vs. Total Orders
    • More DFS Matters
    • Back Edges and DAGs: A Lemma
    • Topological Sort Algorithm
    • Topological Sort Examples
    • Correctness of Topological Sort
22.4 CLRS Exercises 22.4-1, 2
M 04/01 33
  • Finish Topo. Sort, probably
  • Minimum Spanning Trees
    • The Idea & Generic Solution
    • Cuts, Crossing Cuts, and Light Edges

CLRS 23
Epp 10.7
KT 4.5

CLRS Exercises 23.1-2, 3
W 04/03 34
  • Minimum Spanning Trees
    • Kruskal's Algorithm & Brief Analysis
    • Prim's Algorithm with Priority Queues
    • Analysis of Prim's Algorithm
  • Shortest Paths: Dijsktra's algorithm
    • Background on the Shortest Path Problem
CLRS 24.3
Epp 10.7
KT 4.4
CLRS Exercises 23.2-1, 8
Epp 10.7: #9-11 (any you did in 360 are optional)

Theory of Computation reading worksheet due Friday
F 04/05 35
  • Shortest Paths: Dijsktra's algorithm
    • Dijkstra's Algorithm
    • Examples
    • Implementation
    • Optimization Problems and Algorithmic Strategies (Greedy)
CLRS 24.3
Epp 10.7
KT 4.4
CLRS Exercises 24.3-1, 3; Epp 10.7: #12-13
Unit 4 Challenge Problems
M 04/08 36
  • Shortest Paths: Dijsktra's algorithm
    • Performance Analysis
    • Correctness
    • Optimization Problems and Algorithmic Strategies (Greedy)
  • Greedy: Inverval Scheduling
    • The Problem
    • Possible Greedy Algorithms
KT 4.1  
UNIT 5: Advanced Design Techniques and Constraints
W 04/10 37
  • Greedy: Inverval Scheduling
    • The Problem
    • Possible Greedy Algorithms
    • An Algorithm That Works
    • Analysis
  • Greedy: Inverval Partitioning
    • Interval Partitioning
KT 4.2  
R 04/11

EXAM 4 - 8:15 p.m. in 101 Thomas [Exam Info.]

F 04/12 38
  • Greedy: Inverval Partitioning
    • Interval Partitioning
    • Interval Partitioning Solution
    • Interval Partitioning Analysis
  • Greedy: Scheduling to Minimize Lateness
    • The Problem
    • Possible Greedy Solutions
    • Earliest Deadline First Algorithm
    • Inversions and Idle Time
    • Analysis of Greedy Algorithm
    • General Greedy Analysis Strategies
KT 4.2
KT 6.1
 
M 04/15 39
  • Greedy: Scheduling to Minimize Lateness
    • Analysis of Greedy Algorithm
    • General Greedy Analysis Strategies
  • Dynamic Programming: Weighted Interval Scheduling
    • Motivation via Fibonacci
    • The Weighted Interval Problem and Some Exploration
KT 6.1
KT 6.2
Programming assignment begun last Monday in recitation due this Weds. at start of lecture
W 04/17 40
  • Dynamic Programming: Weighted Interval Scheduling
    • Performance of the Optimal Value Algorithm and Improving It
    • Computing a Solution
    • Generalizing Dynamic Programming
KT 6.2
KT 6.4
Code the D.P. algorithm from lecture in (a) function(s) and test it on the example in the notes and one other example

Coming around here: DP/greedy problem set in lieu of Chall. Probs.
F 04/19 41
  • DP: Knapsack Problem
    • The Problem
    • Getting to a DP Solution
    • Bottom-Up Algorithm
    • Example
    • Running Time Analysis
KT 6.4 In notes packet
M 04/22 42
  • DP: Bellman-Ford Shortest Paths
    • Problem Statement
    • Negative Cost Cycles
    • Building an Algorithm for Shortest Path Lengths
    • Finding Shortest Paths
KT 6.8
CLRS 24.1
In notes packet
W 04/24 43
  • DP: Edit Distance
    • Problem Statement and Getting Started
    • Building a Recursive Definition
    • Memoization
    • Example Trace
  Problem Set due Friday
F 04/26 44
  • Wrap up DP
  • Summarizing undecidability and NP from reading assignment
  • Course Wrap-Up
--  
F 05/03

FINAL EXAM - 104 KELLER - 8 a.m. to 9:50 a.m. - [Exam Info.]