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

Class meeting time: TR 3:45 - 5:00pm @ SMH 108
Office hours: TR 1:30-3:30pm @ MSB 352, and by appointment

Office hours during finals week: Tues 12pm-2pm; Thurs 1:30pm-3:30pm, and by appointment.

This schedule is not final. It may change.

Topics Subtopics & Slides Examples Reading Date
Introduction Syllabus
Intro 8/22
Ch 1: Algorithm Analysis Analysis of Algorithms 1.1, 1.2, 1.3, 1.4 8/22; 8/27
Ch 2: Basic Data Structures Elementary Data Structures 1.5, 2.1, 2.2, 2.3 8/27; 8/29; 9/3
Priority Queues and Heaps heap insert, heap removeMin 2.4.1 - 2.4.4 9/3; 9/5
Dictionaries and Hash Tables chaining, linear probing, double hashing 2.5.1 - 2.5.6 9/10; 9/12
Ch 3: Search Trees and Skip Lists Binary Search Trees insert, find, remove 3.1.1 - 3.1.6 9/12; 9/17
Red-Black Trees insert 3.3.3 9/19
Ch 4: Sorting, Sets, and Selection Merge Sort merge sort 4.1.1 9/24
Quick Sort quick sort 4.3.1, 4.6 9/26
Sorting Lower Bound 4.4 10/1
Radix Sort bucket sort, radix sort 4.5.1, 4.5.2 10/1; 10/3
Sets 4.2.1 10/3
Selection quick select 4.7, 4.7.1 - 4.7.3 10/3; 10/8
Ch 5: Fundamental Techniques Greedy Method fractional knapsack, task scheduling 5.1, 5.1.1, 5.1.2 10/22
Divide and Conquer master theorem 5.2, 5.2.1 - 5.2.3 10/24; 10/29
Dynamic Programming matrix chain product, 0-1 knapsack 5.3, 5.3.1 - 5.3.3 10/31; 11/5
Ch 6: Graphs Graphs 6.1 - 6.2 11/5
Depth-First Search dfs 6.3.1 11/7
Breadth-First Search bfs 6.3.3 11/7
Biconnectivity 6.3.2 11/12
Directed Graphs 6.4.1, 6.4.2, 6.4.4 11/14
Ch 7: Weighted Graphs Shortest Paths dijkstra (on undirected graph), dijkstra (on digraph), dag-based, bellman-ford 7.1, 7.1.1 - 7.1.3, 7.2, 7.2.1 11/19; 11/21
Minimum Spanning Trees prim-jarnik, kruskal 7.3, 7.3.1 - 7.3.3 11/26; 12/3
Ch 8: Network Flow and Matching Network Flow ford-fulkerson, edmond-karp 8.1.1, 8.1.2, 8.2.1 - 8.2.3 12/3; 12/5

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)
    Thu 10/17, during class
    Topics include chapters 1-4.
  2. Final Exam (info) (overview)
    Fri 12/13 @ 7:45am-10:00am
    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