CS 375 HW Assignments
Colby College, Spring 2021

Prof. Eric Aaron

Course Module Topics HW Assignment
Introduction and Foundations (No new CS375 topics--problem set (PS, for short)
foundations in mathematics and algorithm design)

Reading: Appendices A.1 and B.1;
Ch.1, 2.1, and 2.2

PS: Foundations
Due date: February 17

Divide and Conquer I
  • Zen and The Art Of Algorithm Design
  • Binary Trees: A Review
  • Recursive Design
  • IntBinTrees
  • Correctness of Recursive Algorithms:
    Inductive Arguments
  • Sum Recursion
  • Brute Force Algorithms
  • Factorial and Exponential functions
    		•

    Reading:Ch. 2.1, 2.2, and 2.3.1

    PS: Divide and Conquer I
    Due date: March 1

    Divide and Conquer II
  • List Algorithms and Recursion
  • LLists
  • Binary Search
    		•

    Reading: Ch. 2.1, 2.2, and 2.3.1

    PS: Divide and Conquer II
    Due date: March 15

    Introduction to
    Asymptotic Complexity
  • Insertion Sort
  • Introduction to Time Complexity
  • Counting Operations
  • Barometer Operations
  • Asymptotic complexity and Big-O Notation
  • Theta and Big-Omega Notation
    		•

    Reading: Ch. 2 and 3

    PS: Introduction to
    Asymptotic Complexity
    Due date: March 29 March 24

    Loop Invariants
  • Loop Invariants
  • Bubble Sort
    		•

    Reading: Ch. 2.1

    No Problem Set (just SA's)

    Recurrences
  • Divide and Conquer: 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.

    PS: Recurrences
    Due date: April 12

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

    Reading: Chapters 22.1-22.3

    PS: Graphs; Intro to Graph Algos
    Due date: April 21

    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: May 5





    Topics Assignment

    CHIPS

    		 Modules Foundations through Recurrences, inclusive
    (but nothing from Loop Invariants)

    CHIPS
    (See assignment sheet for deadlines)