CSCI 385 Spring 2019
Advanced Data Structures and Algorithms
Archived Class
Charles Cusack
Computer Science
Hope College
Main
Schedule
Grading
Gradebook

Policies
College
    Policies
Advice

Notes
Programs
Tutorials

CSCI 112
CSCI 125
Others

Admin
previous     next     today     future     all    

Schedule for weeks 1 through 16

Wk Day Date TopicResourcesEvents

1MonJan 07Course Introduction
  • Algoraph

  • WedJan 09Graph AlgorithmsSkim ALG 3.1-3.4, 4.1-4.7

    FriJan 11
  • Divide-and-conquer
  • Graph algorithms
  • Skim ALG 2.1-2.5

    2MonJan 14Greedy Algorithms
  • Horn Formulas
  • Set Cover
  • ALG 5.3-5.4
  • HW 1 due

    WedJan 16Graph Algorithms

    FriJan 18Algoraph Stuff

    3MonJan 21Dynamic Programming
  • Shortest Paths
  • Travelling Saleseman
  • ALG 6.6
  • Warshall's Algorithm Notes (Read)
  • Floyd's Algorithm Demo
  • HW 2 due

    WedJan 23Divide-and-conquer
  • Read Mergesort notes
  • Read Quicksort notes
  • Answer Mergesort Reading Questions
  • Answer Quicksort Reading Questions

  • FriJan 25Prim's algorithm discussion

    4MonJan 28Snow Day!No Class

    WedJan 30Snow Day! (Really?! Another one?)No Class

    FriFeb 01Optimizing Algorithms: Practice!HW 3 due (No lates!)

    5MonFeb 04Linear Programming
  • ALG 7.1

  • WedFeb 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

  • FriFeb 08
  • Duality
  • Zero-sum games
  • ALG 7.4-7.5
  • HW 4 due

    6MonFeb 11Winter RecessNo Class

    WedFeb 13
  • Simplex Algorithm
  • Circuit Evaluation
  • ALG 7.6-7.7 (Skip 7.6.3)
  • HW 5 due

    FriFeb 15Parallel ProgrammingRead Introduction to Parallel Programming
  • SRQ → Answer IPP Questions

  • 7MonFeb 18Open 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

  • WedFeb 20Open 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

  • FriFeb 22Open MP
  • Watch videos 16-18 from Intro to OpenMP
  • SRQ → OMP Video 16-18 Question

  • 8MonFeb 25Everything
  • Brain
  • Writing utensil
  • Paper
  • Midterm Exam

    WedFeb 27Open MP
  • Watch videos 19-22 from Intro to OpenMP
  • SRQ → OMP Video 19-22 Question

  • FriMar 01Open MP

    9MonMar 04Open MP
  • QuickSortProject.zip
  • HW 7 due (program)

    WedMar 06Open MP
  • Watch videos 23-27 from Intro to OpenMP
  • HW 7 due (write-up)

    FriMar 08Search problems
  • ALG 8.1

  • 10MonMar 11NP-Complete Problems
  • ALG 8.2
  • ALG 8.3 through top of page 249
  • A Few Sample Reduction
  • HW 8 due (code)

    WedMar 13Problem Reductions
  • ALG 8.3
  • NP-Completeness Notes
  • HW 8 due (write-up)

    FriMar 15Spring BreakNo Class

    Spring Break Week

    11MonMar 25
  • Backtracking
  • Branch-and-Bound
  • ALG 9.1
  • Backtracking and Branch-and-bound links

  • WedMar 27Approximation Algorithms
  • ALG 9.2
  • HW 9 due

    FriMar 29Parallel Programming Read Ch 2-3.3 of SIPC
  • Sophomoric Parallelism and Concurrency (SIPC)

  • 12MonApr 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

  • WedApr 03
  • Local Search Heuristics
  • ALG 9.3
  • Read Grossman notes 1
  • Work day

    FriApr 05
  • Java's ForkJoin
  • Divide-and-conquer in parallel
  • Read Ch 4-5.2 of SIPC
  • Grossman notes 2

  • 13MonApr 08
  • Analyzing Parallel Algorithms
  • Grossman notes 2
  • HW 10 due

    WedApr 10
  • Parallel Prefix
  • Pack
  • Read Ch 5 of SIPC
    (Re-read 5-5.2, finish chapter)
  • Grossman Notes 3

  • FriApr 12
  • Parallel Quicksort and Mergesort

  • 14MonApr 15
  • Parallel Sorting
  • Concurrency
  • Read Ch 6 of SIPC
  • Grossman Notes 4

  • WedApr 17
  • Race conditions
  • Read Ch 7 of SIPC
  • Grossman Notes 5
  • HW 11 due

    FriApr 19Easter BreakNo Class

    15MonApr 22Easter BreakNo Class

    WedApr 24
  • Programming Pack and Partition

  • FriApr 26ReviewHW 12 due

    ExFriMay 03Final Exam, 9:00 - 11:00 am