CS 380 Spring 2015

An introduction to the formal techniques that support the design and analysis of algorithms, focusing on both the underlying mathematical theory and the practical considerations of efficiency. Topics include asymptotic complexity bounds, techniques of analysis, algorithmic strategies, advanced data structures, graph theory and other selected topics. Coursework includes object-oriented programming in C++ and covers templates, STL, and exception handling. Prerequisite: CS 300 and MATH 240 each with a minimum grade of C. Offered alternate years. 4 credits.

Schedule:

Weeks	Date	Topics	Homework & Assignments
Week 1	Jan 26	Syllabus Chapters 1 & 2 Introduction / Motivation Insertion Sort
	Jan 28	Continue Insertion Sort	01 Visual Studio and Subversion Coding Standards DreamSpark Connecting to Grace
	Jan 30	Chapters 1 & 2 & 3 Divide and Conquer Merge Sort
Week 2	Feb 2	Standard Template Library Meet in CS lab	02 Sorting CS380Sorting.zip
	Feb 4	Asymptotic analysis - continue notes from Jan 30
	Feb 6	Class cancelled - Prof. was sick
Week 3	Feb 9	Analysis of Merge Sort Analyzing divide and conquer
	Feb 11	Heapsort
	Feb 13	Heapsort
Week 4	Feb 16	Priority queue Quiz	DUE: 02
	Feb 18	Discussion of assignment Review	03 Disk IO Scheduling
	Feb 20	Exam 1
Week 5	Feb 23	Introduction to Quicksort
	Feb 25	Continue quicksort
	Feb 27	Finish quicksort Linear Sorting
Week 6	Mar 2	Continue linear sorting	DUE: 03 part 1
	Mar 4	Class Cancelled - Prof at conference
	Mar 6	Class Cancelled - Prof at conference
Week 7	Mar 9	Bucket sort Order statistics	DUE: 03 part 2 04 Assignment
	Mar 11	Order statistics
	Mar 13	review
Week 8	Mar 16	Exam 2
	Mar 18	Dynamic Programming: Rod Cutting
	Mar 20	Performance Analysis of Assignment 4	DUE: 04
	Mar 23	SPRING BREAK
	Mar 25	SPRING BREAK
	Mar 27	SPRING BREAK
Week 9	Mar 30	Dynamic Programming: Rod Cutting
	April 1	Dynamic Programming: Matrix Chain Multiplication	Talk about the app Tinn
	April 3	Continue Matrix Chain Multiplication
Week 10	April 6	Dynamic Programming: LCS
	April 8	Dynamic Programming: Edit Distance	05 Assignment: DNA alignment
	April 10	Dynamic Programming: Sequence Alignment
Week 11	April 13	String Matching
	April 15	Continue String Matching Elementary Graph Algorithms Quiz
	April 17	Exam 3
Week 12	April 20	Graph Algorithms
	April 22	NO CLASS - Senior Projects Day
	April 24	Minimum Spanning Trees
Week 13	April 27	Lab Work	DUE: 05
	April 29	Lab Work
	May 1	Lab Work
Week 14	May 4	Lab Work
	May 6	Reading Day
	May 8