**TCSS 343, Spring 2016**

**Handouts**

- Course syllabus (organization, objectives, grades, schedule)
- Peer assessment guidelines
- Assumptions that guide this course
- Group work in TCSS 343

**Extra Resources**

- 321, 342 review sheet: review
- Some mathematics basics: Exponentials, logarithms, summations
- Guide to proof by induction
- Short guide to big-Oh and algorithm analysis
- Motivating examples for the course

- Guide to pseudocode
- PDF Pencasts on summations and proof by induction
- PDF
Pencast on In-class exercise #2
(parts a and b)

- Worksheet on the RAM model, big-Oh, and algorithm analysis (from 3/30 lecture)
- Some preliminaries (from 3/30 lecture) – solutions to problems 1, 2a, and 2b
- Analysis fundamentals (from 4/4 lecture)
- Code analysis exercises (from 4/4 lecture)
- More loop exercises
- Lecture slides about algorithm analysis (from 4/4, 4/6 lecture)
- Average case analysis of binary search
(from 4/6 lecture)
- Slides on mergesort, quicksort, quickselect
(from 4/15, 4/18 lecture)
- Case 1 of the proof of the Master
Theorem (from 4/22 lecture)
- The gory detail of Large Integer Multiplication (from 4/27
lecture)
- Binary exponentiation (from 5/4
lecture)

- PDF Pencast on Dynamic Programming: Fibonacci
numbers and coin changing
- PDF Pencast on Dynamic Programming: 0-1 Knapsack
Problem (intro)
- Ling Ding’s slides on Dynamic Programming: part 1
- Ling Ding’s slides on Dynamic Programming: part 2

- Lecture slides for optimal binary search tree
(from 5/16 lecture)
- Lecture slides for minimum spanning trees
(from 5/20 lectures)
- Lecture slides for shortest paths (from 5/23,
5/25 lecture)
- Proof of correctness of Prim’s algorithm
- Lecture slides for lower bound
on comparison-based sorting (from 6/1 lecture)

**Homework Assignments**

- Homework #1 (due Wednesday, April 6): hw1.pdf
- Homework #2 (due Wednesday, April 13): hw2.pdf
- Homework #3 (due Friday, April 22): hw3.pdf
- Homework #4 (due Friday,
April 29): hw4.pdf

Starter code for hw #4: Sort.java BinaryHeap.java EmptyHeapException.java HeapNode.java

PDF Pencast on repeated substitution (possibly helpful for hw #4 group problem) - Homework #5 (due Monday, May 9): hw5.pdf
- Homework #6 (
**HW 6A**due Monday, May 23;**HW 6B**due Wednesday, June 1): hw6.pdf

starter code for hw #6B: hw6b-start-code.zip

PDF Pencast on how to implement Prim’s algorithm using a heap (useful for the heap implementation of Dijkstra’s algorithm)

**Peer Assessment (All peer problem solutions need to be turned in both
hard copy and by e-mail. Only hard copy for critiques are necessary.)**

- Template for your critiques: template-peer-critique.pdf
- Peer
assessment #1: solutions (groups 1-3, hard copy
**and**email) due Monday, April 4; critique (all groups, hard copy) due Monday, April 11

**IMPORTANT NOTE:**for your soft copy (electronic), I’d prefer if you submitted an editable document (for exmaple, Word), so that I can anonymize your work before posting it to this web site. If what you send me is not easily editable, then send me an anonymized document. Your hard copy should have all group member names on it.

peer1.pdf

Solutions to be critiqued: peer1-solns1-2.pdf peer1-soln3.pdf

- Peer
assessment #2: solutions (groups 4-6, hard copy
**and**email) due Monday, April 18; critique (all groups, hard copy) due Monday, April 25

peer2.pdf

Solutions to be critiqued: peer2-soln1.pdf peer2-soln2.jpg peer2-soln3.pdf

- Peer
assessment #3: solutions (groups 1-3, hard copy
**and**email) due Wednesday, May 4; critique (all groups, hard copy) due Monday, May 16

peer3.pdf

Solutions to be critiqued: peer3-solns.pdf

Peer assessment #4: solutions (groups 4-6, hard copy **and** email) due Wednesday, May 25;
critique (all groups, hard copy) due Friday, June 3

peer4.pdf

Solutions to be critiqued: peer4-solns.pdf

**Exams**