CSCI 385 Fall 2015
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

1TueSep 01
  • Course intro
  • Graph Pebbling
  • Brickficiency
  • bricklink
  • BrickStore
  • Brickficiency

  • ThuSep 03Brickficiency
  • NATCF 1-2
  • Brickficiency Project 1 due

  • FriSep 04Algorithm Analysis
  • NATCF 3
  • FA 1-1.3 (pages 1-26)

  • 2TueSep 08Asymptotic Notation
  • NATCF 4
  • FA 1.4-1.5
  • AIDMA 7 (optional)
  • HW 1 due

    ThuSep 10Recurrence Relations
  • NATCF 5
  • FA App B.1 (603-607)
  • FA App B.3 (626-627)
  • FA App B.4 (628-635)
  • AIDMA 8.3-8.3.3 (288-304) (Optional)

  • FriSep 11Algorithm Design and Analysis
  • NATCF 6
  • FA 3-3.1, 3.3, 4-4.1
  • Ch 3/4 SRQ due

  • 3TueSep 15Divide-and-conquer
  • NATCF 7
  • FA 2-2.4
  • HW 2 due

    ThuSep 17Divide-and-conquer
  • NATCF 8
  • FA 2.5, 2.8
  • FA 2.7 (optional)
  • Top 4 NATCF topic list due

  • FriSep 18Divide-and-conquer
  • NATCF 9
  • HW 3 due

  • 4TueSep 22
  • Finishing up divide-and-conquer
  • Brief discussion of parallel divide-and-conquer
  • NATCF 10-11 (no SRQ)
  • FA 3.4 (required, no SRQ)
  • FA 3.5 (Bring SRQ to class)
  • FA 3.7 (Bring SRQ to class)
  • Strassen's Algorithm Slides
  • Strassen's Algorithm (from a blog)
  • Other Strassen's Algorithm Slides
  • HW 4 due

  • ThuSep 24Dynamic Programming
  • Optimal Binary Search Trees
  • Sequence Alignment
  • FA 4.5 (Bring SRQ to class)
  • Hoang and John Presenting

  • FriSep 25
  • Knapsack (Greedy Versus Dynamic)
  • FA 4.2 (Bring SRQ to class)
  • FA 4.3 (Bring SRQ to class)
  • Nathan Presenting

  • 5TueSep 29Greedy Algorithms
  • Dijkstra's Algorithm
  • Scheduling
  • HW 5 due
  • Cole and Katie presenting

  • ThuOct 01Applications

    FriOct 02Backtracking
  • FA 5-5.4
  • 8 Queens Animation (GIF)
  • 8 Queens Animation (YouTube)
  • Project Proposal Due

  • 6TueOct 06No ClassFall Recess

    ThuOct 08Backtracking
  • FA 5.6-5.7
  • HW 6 due

    FriOct 09Branch-and-Bound
  • FA 6-6.2

  • 7TueOct 13
  • Backtracking
  • Branch-and-Bound
  • Work Day!

    ThuOct 15NP-Complete
  • FA 9-9.4
  • NP-complete notes
  • HW 7 due

  • FriOct 16Approximation Algorithms
  • FA 9.5
  • Annotated Bibliography for Project Due

  • 8TueOct 20EverythingMidterm Exam

    ThuOct 22Genetic Algorithms
  • FA 10-10.2

  • FriOct 23
  • Genetic Programming
  • Work day
  • FA 10.3-10.4
  • GP Tutorial (mainly for the pictures)

  • 9TueOct 27
  • Parallel Programming
  • OpenMP
  • Read Introduction to Parallel Programming (SRQ)

    ThuOct 29Open MP
  • Watch 1-7 from Introduction to OpenMP
  • Open MP Slides (from videos, for reference)
  • Open MP Exercises (code from videos)
  • Patternlets (in class)
  • Open MP Introduction (for reference)
  • Submit your Pi program

  • FriOct 30Open MP
  • Watch 8-17 from Introduction to OpenMP
  • mandel.c in class
  • HW 8 due

  • 10TueNov 03Open MP
  • Watch 18-22 from Introduction to OpenMP

  • ThuNov 05Open MP
  • Watch 23-27 from Introduction to OpenMP

  • FriNov 06Parallel ProgrammingRead Ch 2-3.3 of SIPC (SRQ)
  • Sophomoric Parallelism and Concurrency
  • Project Readings/Handouts Due

  • 11TueNov 10
  • Java's ForkJoin
  • Read Ch 3.4-3.6 of SIPC (SRQ)
  • Grossman notes 1
  • Java ForkJoin Framework
  • Java ForkJoin Framework Guide
  • Java ForkJoin Javadoc
  • HW 9 due

    ThuNov 12
  • Analyzing Parallel Algorithms
  • Read Ch 4 of SIPC (SRQ)
  • Read Ch 5-5.2 of SIPC (SRQ)
  • Grossman notes 2

  • FriNov 13
  • Parallel Prefix
  • Pack
  • Read Ch 5 of SIPC (SRQ) (Re-read 5-5.2 and finish the chapter)
  • Grossman Notes 3
  • Project Activity Due

  • 12TueNov 17
  • Parallel Sorting
  • Concurrency
  • Read Ch 6 of SIPC (SRQ)
  • Grossman Notes 4
  • HW 10 due

    ThuNov 19
  • Race conditions
  • Read Ch 7 of SIPC (SRQ)
  • Grossman Notes 5
  • HW 10 due (Write up)

    FriNov 20
  • Locks and stuff
  • Read Ch 8-9 of SIPC (SRQ)
  • Grossman Notes 6

  • 13TueNov 24
  • Synchronization
  • Read Ch 10 of SIPC (SRQ)
  • HW 11 due

    ThuNov 26No Class
  • Turkey (or Tofurky or maybe even Turducken)
  • Stuffing
  • Mashed Potatoes
  • Gravy
  • Thanksgiving Break

    FriNov 27No ClassThanksgiving Break

    14TueDec 01PageRank
  • PageRank reading (handed out, SRQ!)
  • Page Rank Calculation Spreadsheet
  • John Dood presenting

    ThuDec 03Data compression
  • Blelloch Reading (handed out, SRQ!)
  • Data Compression Notes (in class)
  • Compression Animation
  • Katie Brudos presenting
  • Exam Problems due (project, normal)

  • FriDec 04Public-Key CryptographySRQ for all:
  • FA11.1-11.2
  • Stinson reading (handout)
  • RSA Notes
  • Hoang Vu presenting

    15TueDec 08Digital SignaturesSRQ for all:
  • Crash Course on Digital Signatures (read)
  • Extended Euclidean Algorithm (read)
  • Handout (read)
  • Digital Signatures Notes (in class)
  • Cole Watson presenting
  • HW 12 due (program)

  • ThuDec 10BitcoinsSRQ for all:
  • Bitcoin Primer (Read through page 9)
  • Bitcoin Mining (Read to "Mining with a pool", including footnotes.)
  • Block Hashing (Read all)
  • Difficulty (Read all)
  • Nate Vance presenting
  • HW 12 due (write-up)

  • FriDec 11Review

    ExWedDec 16EverythingFinal Exam 3-5 pm