Math Foundations for Computer Science


CSCI 226-01


Spring Semester 2012


The course syllabus.

The textbook's companion website. Don't forget to download the errata for your particular printing. I suggest you go through and make the corrections in your text right away!

In addition to the course textbook, the library and the instructor have a plethora of additional resources, three favorites are:

Instructor's Home Page and current schedule.

Date: Section from text to have read (3rd edition reading): Activity or What's Due:
Friday April 27
 PIZZA!
 Man Who Counted Paper
Homework 12 (chap 11)
Wednesday April 25
EC (4-Kruskal's MST algorithm)
PtoW: Rumor Spreading
Monday April 23
 Sections §11.4 & §11.5 (§9.4 & §9.5) - Analysis of exponential and
                               logarithmic functions
Friday April 20

Wednesday April 18
 WOX Luncheon - Class Canceled
 Homework 11 (§10.7)
Monday April 16
 Sections §11.1 & §11.2 (§9.1 & §9.2) - Intro to Algorithm Analysis
Friday April 13

Wednesday April 11
 Sections §18.1-18.5 in "Algorithms in Java, 3/e, Part 5: Graph Algorithms"
Chapters 33-34  in The Man Who Counted
EASTER BREAK!
 EASTER BREAK! EASTER BREAK!
Wednesday April 4
 §10.6 & 10.7  (§11.5 & 11.6) - Trees
Chapters 29-32  in The Man Who Counted
Monday April 2
PotW: Longest Path
Friday March 30

Wednesday March 28
 Chapters 25-28  in The Man Who Counted Homework 10 (§10.1)
Monday March 26
 §10.2  (§11.2) - Trails, Paths and Circuits
Friday March 23

Wednesday March 21
 §10.1  (§11.1) - An Introduction to Graphs
Chapters 21-24  in The Man Who Counted 		Homework 9 (§9.8-9.9) - extended
Monday March 19
PtoW: Sorting 5 In 7
Friday March 16

Wednesday March 14
 Chapters 17-20  in The Man Who Counted
Monday March 12
 §9.9  (§6.9) - Conditional Probability and Bayes' Formula PotB: Derangement
SPRING BREAK!
 SPRING BREAK!
 SPRING BREAK!
Friday March 2
 Class Cancelled: Start Spring Break Early
Wednesday February 29
Homework 8 (§9.6-9.7)
Monday February 27
 §9.8  (§6.8) - Probability Axioms PotW: Last One Standing,   EC(3)
Friday February 24
EC(2)
Wednesday February 22
 §9.7  (§6.6-6.7) - Binomial Theorem Homework 7 (§9.5)
Monday February 20
PotW: Poisoned Wine
Friday February 17
 §9.6  (§6.5) - Combinations w/repetitions
Wednesday February 15
Homework 6 (§9.3)
Monday February 13
 §9.5  (§6.4) - Combinations PotW: The Odometer Puzzle
Friday February 10

Wednesday February 8
 §9.2 & §9.3 (§6.2 & §6.3) - Counting Rules
Chapters 13-16  in The Man Who Counted
Monday February 6
 §9.1 (§6.1) - Introduction to Probability             
PotW: Calendar Counting
Friday February 3
 §5.9 (§8.4) - Recursive Definitions and Structural Recursion Homework 5 (§5.8)
Wednesday February 1
 Chapters 9-12  in The Man Who Counted
Monday January 30
 §5.8 (§8.3) - 2nd Order Linear Recurrences Homework 4 (§5.7)
PotW: Chuck-a-Luck
Friday January 27

Wednesday January 25
 §5.7 (§8.2) - Solving Recurrences Using Iteration
Chapters 5-8 in The Man Who Counted 		Homework 3 (§5.4) + EC (1)
Monday January 23
 §5.6 (§8.1) - Recursively Defined Sequences PotW: Desert Trek
Friday January 20
Homework 2 (§5.2)
Wednesday January 18
 §5.4 (§4.4) - Strong Mathematical Induction
Chapters 1-4 in The Man Who Counted
Monday January 16 - MLK DAY!
 MLK DAY!
 MLK DAY!
Friday January 13
 §5.3 (§4.3 - Mathematical Induction Homework 1 (§5.1)
Wednesday January 11
 §5.2 (§4.2) - Mathematical Induction
Monday January 9
 §5.1 (§4.1) - Sequences

Extra Credit Opportunities:

  1. Provide the recurrence relation for either Selection Sort and/or Merge Sort
  2. Determine how many combinations exist for displaying 30 balloons, from an inventory of eight different colored balloons.  Furthermore, there are only 12 red balloons and 8 blue balloons in stock.  There exists more than 30 balloons each for the other six colors.
  3. Derive the general formula for the Multi-nomial Theorem.  Hint: Start by generalizing binomials to trinomials, then generalize to multi-nomials.
  4. Implement Kruskal's algorithm for finding a Minimum Spanning Tree (MST).  You should use a matrix graph representation.  While you may utilize a built-in sort function, you need to implement your own Depth First Search (DFS) algorithm for cycle testing. 



Examinations: