CS 375 HW Assignments
Colby College, Spring 2020

Prof. Eric Aaron



HW1
HW2
HW3
HW4
HW5
HW6
HW7
HW8
HW9

NOTE: HW10 has been incorporated into the HW assignment for Recurrences, below.





Course Module Topics HW Assignment
Recurrences
  • Solving Recurrences: Unwinding
  • Solving Recurrences: Recursion-Tree Method
  • Solving Recurrences: Master Method
    		•

    Reading: Ch. 2, Ch. 3, and
    pages 65-67, 88-97 from Ch. 4.

    HW: Recurrences
    Due date: TBD April 8

    Graphs;
    Intro to Graph Algorithms
  • Graph Vocabulary
  • Adjacency Lists and Adjacency Matrices
  • BFS and DFS
    		•

    Reading: Chapters 22.1-22.3

    HW: Graphs; Intro to Graph Algos
    Due date: TBD April 15

    Dynamic Programming
  • Fibonacci Numbers
  • Dynamic Programming
  • Sequences and Subsequences
  • Longest Common Subsequence
  • Weighted Graphs and Shortest Paths
  • Shortest Path Problems
  • All-Pairs Shortest Paths
  • Floyd-Warshall Algorithm
    		•

    Reading: Chapter 15, pages 359-360;
    Chapter 15, pages 378-396;
    Chapter 24, pages 643-647;
    and Chapter 25.2

    HW: Dynamic Programming
    Due date: TBD April 27

    Intro to Greedy Algorithms;
    Minimum Spanning Trees
  • Coin Changing and Greedy Algorithms
  • Trees
  • Minimum Spanning Trees
  • Kruskal's Algorithm
    		•

    Reading: Chapter 16,
    up to (and including) Ch. 16.1;
    and Chapter 23

    HW: Greedy Algos; MSTs
    Due date: TBD April 29