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

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

1TueJan 10
  • Introduction
  • Prerequisite Review

  • ThuJan 12Brute Force
  • Closest-Pair
  • Convex Hull
  • IDAA 3.3

  • FriJan 13Decrease-and-conquer
  • Generating Permutations
  • Generating Subsets
  • IDAA 4 intro (pages 131-134)
  • IDAA 4.3

  • 2TueJan 17Divide-and-conquer
  • Closest-Pair
  • Convex Hull
  • IDAA 5 intro (pages 169-171)
  • IDAA 5.5

  • ThuJan 19Transform-and-Conquer
  • Gaussian Elimination
  • LU Decomposition
  • IDAA 6.2 (to top of page 214)
  • HW 1 due

    FriJan 20Transform-and-Conquer
  • Problem Reduction
  • IDAA 6.6
  • Linear Programming Exploration (Geogebra)
  • Linear Programming Example (Desmos)

  • 3TueJan 24Transform-and-conquer
  • Balanced search trees
  • Space and Time Trade-Offs
  • B-Trees
  • IDAA 6.3
  • IDAA 7.4

  • ThuJan 26Dynamic Programming
  • Knapsack Problem
  • IDAA 8.2
  • HW 2 due

    FriJan 27Dynamic Programming
  • Optimal Binary Search Tree
  • IDAA 8.3

  • 4TueJan 31Dynamic Programming
  • Warshall's Algorithm
  • Floyd's Algorithm
  • IDAA 8.4
  • Warshall Notes
  • Floyd Visualization
  • 385 Google Doc
  • HW 3 due

    ThuFeb 02Greedy Technique
  • Prim's Algorithm
  • Dijkstra's Algorithm
  • IDAA 9.1 (hopefully review)
  • IDAA 9.3
  • Minimum Spanning Trees Notes
  • Algoraph

  • FriFeb 03Iterative Improvement
  • Maximum-Flow Problem
  • IDAA 10.2
  • Ford-Fulkeron Demo
  • Max Flow Demo
  • Network Flow Solver
  • HW 4 due

    5TueFeb 07Iterative Improvement
  • Maximum Matching
  • IDAA 10.3
  • HW 5 due

    ThuFeb 09Limitations of Algorithm Power
  • Lower-Bound Arguments
  • IDAA 11.1
  • Sorting Lower Bound notes
  • Kelvin predictions

  • FriFeb 10Limitations of Algorithm Power
  • Decision Trees
  • IDAA 11.2
  • HW 6 due

    6TueFeb 14No ClassWinter Recess

    ThuFeb 16Limitations of Algorithm Power
  • P, NP, and NP-Complete
  • IDAA 11.3
  • Halting Problem Notes
  • Turing and the Halting Problem

  • FriFeb 17Limitations of Algorithm Power
  • Challenges of Numerical Algorithms
  • IDAA 11.4
  • IEEE 754
  • Roundoff Error

  • 7TueFeb 21Coping with Limitations
  • Backtracking
  • IDAA 12.1
  • Knight Tour (Java)
  • n-Queens (C++)
  • HW 7 due

    ThuFeb 23Coping with Limitations
  • Branch-and-Bound
  • IDAA 12.2
  • Branch-and-Bound Example

  • FriFeb 24ReviewHW 8 due

    8TueFeb 28Everything
  • Brain (Not Brian. You can't get his help.)
  • Book
  • Notes
  • Writing utensil
  • Paper
  • Midterm Exam

    ThuMar 02Parallel Programming
  • Read Introduction to Parallel Programming
  • For RQ: write 2 page summary
  • Algoraph
  • Install SSH client (e.g. MobaXterm)
  • Install Eclipse
  • Install Algoraph plugin for Eclipse

  • FriMar 03Catch up on stuff

    9TueMar 07Open MP
  • Watch videos 1-7 from Intro to OpenMP (Look at video numbers, not titles!)
  • RQ, important note → OMP Videos 1-7 Question
  • OpenMP.org
  • Open MP Introduction (for reference)
  • Open MP Slides (from videos, for reference)
  • Open MP Exercises (code from videos)
  • OpenMP Patternlets (in class)
  • OpenMP Patternlets code
  • Submit pi.c (video 6?) with Webhandin 385-SRQ

  • ThuMar 09Open MP
  • Watch videos 8-15 from Intro to OpenMP
  • OpenMP Reference Sheets
  • SRQ → OMP Videos 8-15 Question
  • Submit pi2.c (video 11) with Webhandin 385-SRQ

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

  • 10TueMar 14Open MP
  • Watch videos 19-22 from Intro to OpenMP
  • SRQ → OMP Video 19-22 Question
  • HW 9 due

  • ThuMar 16Work Day

    FriMar 17No ClassSpring Break

    Spring Break Week

    11TueMar 28Open MP
  • QuickSortProject.zip

  • ThuMar 30Open MP
  • Watch videos 23-27 from Intro to OpenMP
  • HW 10 due (program)

    FriMar 31Parallel Programming Read Ch 2-3.3 of SIPC
  • Sophomoric Parallelism and Concurrency (SIPC)
  • Grossman notes 1
  • HW 10 due (write-up)

    12TueApr 04
  • Java's ForkJoin
  • Read Ch 3.4-3.6 of SIPC
  • Grossman notes 1
  • Java ForkJoin Framework Guide
  • HW 11 due (code)

    ThuApr 06
  • Java's ForkJoin
  • Divide-and-conquer in parallel
  • Read Ch 4-5.2 of SIPC
  • Grossman notes 2
  • HW 11 due (write-up)

    FriApr 07No ClassGood Friday

    13TueApr 11
  • Analyzing Parallel Algorithms
  • Grossman notes 2

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

  • FriApr 14
  • Parallel Quicksort and Mergesort

  • 14TueApr 18
  • Parallel Sorting
  • Concurrency
  • Read Ch 6 of SIPC
  • Grossman Notes 4

  • ThuApr 20
  • Race conditions
  • Read Ch 7 of SIPC
  • Grossman Notes 5b
  • HW 12 due

    FriApr 21Parallel Partition
  • Ch 8 and 9
  • Parallel Partition Demo
  • Read Ch 8-9 of SIPC
  • Grossman Notes 6b

  • 15TueApr 25Work day

    ThuApr 27Quantum Computing
  • Quantum Computing notes
  • HW 13 due

    FriApr 28Review

    ExThuMay 04Final Exam
    9:00-11:00am