CS:4/56101 Design and Analysis of Algorithms - Spring 2019

MW 12:30-1:45pm @ MSB 109

I will have extended office hours on Friday 5/3 from 12pm-2pm in MSB 352, and also by appointment during finals week.

This schedule is not final. It may change.

Topics Subtopics & Slides Reading Date
Introduction Syllabus
Intro 1/14
Ch 1: Algorithm Analysis Analysis of Algorithms 1.1, 1.2, 1.3, 1.4 1/14; 1/16
Ch 2: Basic Data Structures Elementary Data Structures 1.5, 2.1, 2.2, 2.3 1/24; 1/28
Priority Queues and Heaps 2.4.1 - 2.4.4 1/30; 2/4
Dictionaries and Hash Tables 2.5.1 - 2.5.6 2/6
Ch 3: Search Trees and Skip Lists Binary Search Trees 3.1.1 - 3.1.6 2/13
Red-Black Trees 3.3.3 2/18
Ch 4: Sorting, Sets, and Selection Merge Sort 4.1.1 2/20
Quick Sort 4.3.1, 4.6 2/25
Sorting Lower Bound 4.4 2/27
Radix Sort 4.5.1, 4.5.2 2/27
Sets 4.2.1 3/4
Selection 4.7, 4.7.1 - 4.7.3 3/4
Ch 5: Fundamental Techniques Greedy Method 5.1, 5.1.1, 5.1.2 3/6; 3/11
Divide and Conquer 5.2, 5.2.1 - 5.2.3 3/18; 3/20
Dynamic Programming 5.3, 5.3.1 - 5.3.3 4/1; 4/3
Ch 6: Graphs Graphs 6.1 - 6.2 4/3
Depth-First Search 6.3.1 4/8
Breadth-First Search 6.3.3 4/8; 4/10
Biconnectivity 6.3.2 4/10
Directed Graphs 6.4.1, 6.4.2, 6.4.4 4/15
Ch 7: Weighted Graphs Shortest Paths 7.1, 7.1.1 - 7.1.3, 7.2, 7.2.1 4/17; 4/22
Minimum Spanning Trees 7.3, 7.3.1 - 7.3.3 4/24
Ch 8: Network Flow and Matching Network Flow 8.1.1, 8.1.2, 8.2.1 - 8.2.3 4/29; 5/1

Homework

Clearly number your solution to each problem. Staple your solutions and bring them to class on the due date. Express your algorithms in pseudo-code when directed. Always provide justification for your answer when asked to give the running time of an algorithm, or when asked to given an algorithm running in a specific time. Be brief and concise, and draw pictures where appropriate.

Exams

  1. Midterm Exam (info) (overview)
    Wed 3/13, during class
    Topics include chapters 1-4.
  2. Final Exam (info) (overview)
    Wed 5/08, 10:15am-12:30pm
    Topics include chapters 5-8.

Piazza

Sign up for Piazza, a Q&A web service where you can ask and answer questions related to the class.

Heather M. Guarnera / hmichaud@kent.edu