CSCI 385 Spring 2019
Advanced Data Structures and Algorithms
Archived Class
Charles Cusack
Computer Science
Hope College
Main
Schedule
Grading
Gradebook
Policies
Advice
College Policies
Notes
Programs
Tutorials
CSCI 385
MATH 160
Others
Admin
previous next
today
future
all
Schedule for weeks 1 through 16
Wk
Day
Date
Topic
Resources
Events
1
Mon
Jan 07
Course Introduction
Algoraph
Wed
Jan 09
Graph Algorithms
Skim ALG 3.1-3.4, 4.1-4.7
Fri
Jan 11
Divide-and-conquer
Graph algorithms
Skim ALG 2.1-2.5
2
Mon
Jan 14
Greedy Algorithms
Horn Formulas
Set Cover
ALG 5.3-5.4
HW 1
due
Wed
Jan 16
Graph Algorithms
Fri
Jan 18
Algoraph Stuff
3
Mon
Jan 21
Dynamic Programming
Shortest Paths
Travelling Saleseman
ALG 6.6
Warshall's Algorithm Notes
(Read)
Floyd's Algorithm Demo
HW 2
due
Wed
Jan 23
Divide-and-conquer
Read
Mergesort notes
Read
Quicksort notes
Answer
Mergesort Reading Questions
Answer
Quicksort Reading Questions
Fri
Jan 25
Prim's algorithm discussion
4
Mon
Jan 28
Snow Day!
No Class
Wed
Jan 30
Snow Day! (Really?! Another one?)
No Class
Fri
Feb 01
Optimizing Algorithms: Practice!
HW 3
due (No lates!)
5
Mon
Feb 04
Linear Programming
ALG 7.1
Wed
Feb 06
Network Flow
Bipartite Matching
ALG 7.2-7.3
Ford-Fulkerson Demo
(Does not seem to fully work in Chrome. Try Firefox.)
Network Flow Demo
Bipartite Matching Demo
Fri
Feb 08
Duality
Zero-sum games
ALG 7.4-7.5
HW 4
due
6
Mon
Feb 11
Winter Recess
No Class
Wed
Feb 13
Simplex Algorithm
Circuit Evaluation
ALG 7.6-7.7
(Skip 7.6.3)
HW 5
due
Fri
Feb 15
Parallel Programming
Read
Introduction to Parallel Programming
SRQ → Answer
IPP Questions
7
Mon
Feb 18
Open MP
Watch
videos
1-7 from
Intro to OpenMP
OpenMP.org
Open MP Slides
(from videos, for reference)
Open MP Introduction
(for reference)
Open MP Exercises
(code from videos)
Patternlets
(in class)
OpenMP Patternlets code
SRQ, important note →
OMP Videos 1-7 Question
Wed
Feb 20
Open MP
Watch
videos
8-15 from
Intro to OpenMP
OpenMP Reference Sheets
SRQ →
OMP Videos 8-15 Question
HW 6
due
Submit pi2.c (using reduction as suggested in video 11) as 385-SRQ
Fri
Feb 22
Open MP
Watch
videos
16-18 from
Intro to OpenMP
SRQ →
OMP Video 16-18 Question
8
Mon
Feb 25
Everything
Brain
Writing utensil
Paper
Midterm Exam
Wed
Feb 27
Open MP
Watch
videos
19-22 from
Intro to OpenMP
SRQ →
OMP Video 19-22 Question
Fri
Mar 01
Open MP
9
Mon
Mar 04
Open MP
QuickSortProject.zip
HW 7
due (program)
Wed
Mar 06
Open MP
Watch
videos
23-27 from
Intro to OpenMP
HW 7
due (write-up)
Fri
Mar 08
Search problems
ALG 8.1
10
Mon
Mar 11
NP-Complete Problems
ALG 8.2
ALG 8.3 through top of page 249
A Few Sample Reduction
HW 8
due (code)
Wed
Mar 13
Problem Reductions
ALG 8.3
NP-Completeness Notes
HW 8
due (write-up)
Fri
Mar 15
Spring Break
No Class
Spring Break Week
11
Mon
Mar 25
Backtracking
Branch-and-Bound
ALG 9.1
Backtracking and Branch-and-bound links
Wed
Mar 27
Approximation Algorithms
ALG 9.2
HW 9
due
Fri
Mar 29
Parallel Programming
Read
Ch 2-3.3 of SIPC
Sophomoric Parallelism and Concurrency (SIPC)
12
Mon
Apr 01
Java's ForkJoin
Read
Ch 3.4-3.6 of SIPC
Read
Grossman notes 1
Java ForkJoin Framework
Java ForkJoin Framework Guide
Java ForkJoin Javadoc
Wed
Apr 03
Local Search Heuristics
ALG 9.3
Read
Grossman notes 1
Work day
Fri
Apr 05
Java's ForkJoin
Divide-and-conquer in parallel
Read
Ch 4-5.2 of SIPC
Grossman notes 2
13
Mon
Apr 08
Analyzing Parallel Algorithms
Grossman notes 2
HW 10
due
Wed
Apr 10
Parallel Prefix
Pack
Read
Ch 5 of SIPC
(Re-read 5-5.2, finish chapter)
Grossman Notes 3
Fri
Apr 12
Parallel Quicksort and Mergesort
14
Mon
Apr 15
Parallel Sorting
Concurrency
Read
Ch 6 of SIPC
Grossman Notes 4
Wed
Apr 17
Race conditions
Read
Ch 7 of SIPC
Grossman Notes 5
HW 11
due
Fri
Apr 19
Easter Break
No Class
15
Mon
Apr 22
Easter Break
No Class
Wed
Apr 24
Programming Pack and Partition
Fri
Apr 26
Review
HW 12
due
Ex
Fri
May 03
Final Exam, 9:00 - 11:00 am