CPSC 327 (Data Structures and Algorithms): Calendar

Hobart & William Smith Colleges, Spring 2017

Calendar

(Last Update: 01/24/2017)

The following is the current outline of topics and readings for the course. Please note:

  • The reading assignment associated with a particular day must be completed by the start of class that day, not afterwards (see the section on "Participation and Preparation" in the Syllabus).
  • Readings considered optional are given in [square brackets].

As appropriate to the needs of this learning community, we will alter details of any given week to reflect a slower or faster pace. This will almost certainly happen more than once, so check back here for regular updates.

TOPICS READINGS NOTES
Week 1
01/18–01/20
Problem classification
  • W: 1.1 - 1.2
  • F: 1.3
Week 2
01/23–01/27
Data structures; Analysis framework; Proof by induction, Asymptotic bounds; Analysis of non-recursive algorithms;
  • M: 1.4, 2.1, App. A
  • W: 2.2, 2.3
  • F: 2.3
Do Problems 2.1 (4 and 7), 2.2 (7 and 10), and 2.3 (2, 4–6)
Week 3
01/30–02/03
Recursion (review), analysis of recursive algorithms, recurrences; Brute force techniques
  • M:
  • W:
  • F:
Week 4
02/06–02/10
Exhaustive Search; Divide-and-conquer techniques, the Master Theorem
  • M:
  • W:
  • F:
Week 5
02/13–02/17
Binary search, tree traversals; Integer multiplication
  • M:
  • W:
  • F:
Week 6
02/20–02/24
Computational geometry
  • M:
  • W:
  • F:
Week 7
02/27–03/03
Decrease by constant size; decrease by variable size
  • M:
  • W:
  • F:
Week 8
03/06–03/10
Transformation techniques; balanced trees
  • M:
  • W:
  • F:
03/11–03/19 (Spring Vacation: no class or office hours)
Week 9
03/20–03/24
Balanced trees; Heaps and heapsort;
  • M:
  • W:
  • F:
Week 10
03/27–03/31
Space/time trades: B-Trees
  • M:
  • W:
  • F:
Week 11
04/03–04/07
Space/time trades: String matching
  • M:
  • W:
  • F:
Week 12
04/10–04/14
Greedy techniques: spanning trees, Dijkstra's algorithm; Union-find
  • M:
  • W:
  • F:
Week 13
04/17–04/21
Dynamic programming techniques: Floyd/Warshall, sequence alignment
  • M:
  • W:
  • F:
Week 14
04/24–04/28
Bipartite matching; P, NP, and NP-Complete problems
  • M:
  • W:
  • F:
Week 15
05/01
Wrap-Up and Review