Welcome to ITK 279: Algorithms and Data Structures

Spring, 2008

Syllabus

Blackboard Course Site for Grades, Assignment Submission and Other Stuff (login required)

UNIX Information Handout

Instructions for Using Exceed on Demand

179 UNIX Lab

Week	Date	Reading Assignment for this class	Assignments due	Topic
1	1/14	None	None	Introduction
	1/16	Skim Savitch, chs. 1-3	None	C++
	1/18	Skim Savitch, chs 4-6	Email Questionnaire	C++ cont.
2	1/21	Labor Day, no class	None	None
	1/23	Skim Savitch, chs 7 and 9	Savitch, page 128, exercise 4 (submitted electronically)	Classes
	1/25	Read Savitch, ch. 8	Savitch, p. 219, exercise 2 (electronically submitted)	Strings Operator Overloading
3	1/28	Read Savitch, ch. 10	Savitch, p. 306, exercise 4 (electronically submitted)	Pointers Dynamic Arrays
	1/30	Read Savitch, ch. 12	C++ practice 4 as described on Blackboard (electronically submitted)	Dynamic classes Files
	2/1	Read Weiss, ch. 1, sections 1-3	None	Class cancelled (weather)
4	2/4	Read Weiss, ch. 1, sections 1-3	C++ practice 5 as described on Blackboard (electronically submitted)	Recursion Algorithm Analysis
	2/6	Read Weiss ch. 2	Recursion Homework described on Blackboard	Algorithm analysis
	2/8	Read Weiss, ch. 3, sections 1-5	Weiss, ch. 2, exercises 7, 11 (a,c,d), 12 (a,c,d)	Lists
5	2/11	Finish ch. 3	List Homework described on Blackboard	Linked Lists
	2/13	Read Weiss, ch. 4, sections 1-2 and 6	Weiss, ch. 3, exercises 4-5 (use the STL list class and be efficient)	Stacks Queues Binary Trees
	2/15	Read Weiss, ch. 6, sections 1-4	Weiss, ch. 4, exercises 1 and 2 (use a table for exercise 2)	Binary Trees Priority Queues
6	2/18	Read Weiss, ch. 7, sections 1-3	Weiss, ch. 4, exercise 6	Heaps Elementary Sorts
	2/20	Read Weiss, ch. 7, section 4	Weiss, ch. 4, exercise 8 Weiss, ch. 6, exercises 2 and 3	Elementary Sorts Shellsort
	2/22	Read Weiss, ch. 7, sections 5-6	Program 1 due	Shellsort Heapsort
7	2/25	Read Weiss, ch. 7, section 7	Elementary sorting practice described on Blackboard Weiss, ch. 7, exercise 4	Heapsort Mergesort
	2/27	Read Weiss, ch. 7, sections 8-10	Weiss, ch. 7, exercises 11, 12, 15	Review Quicksort
	2/29	None	None	Exam 1 (through mergesort -- does not cover quicksort)
8	3/3	Read Weiss, ch. 4, section 3	None	Quicksort Bucket sort Binary search trees
	3/5	Read Weiss, ch. 4, section 4	Quicksort practice described on Blackboard	AVL trees
	3/7	Read Weiss, ch. 4, section 5	Weiss, ch. 4, exercise 9 Program 2 due	Splay trees
		SPRING BREAK	NO SCHOOL
9	3/17	Finish Weiss, ch. 4	Weiss, ch. 4, exercise 19	B+ trees
	3/19	Read Weiss, ch. 5, sections 1-5	Weiss, ch. 4, exercise 27	Hash tables
	3/21	Finish Weiss, ch. 5	B+ tree homework from Blackboard Paper 1 due	Double Hashing
10	3/24	Read Weiss, ch. 8	Weiss, ch. 5, exercise 1	Extendible Hashing Disjoint sets
	3/26	Read Weiss, ch. 9, sections 1-2	Weiss, ch. 5, exercise 19	Disjoint sets, cont. Graphs Topological sorting
	3/28	Read Weiss, ch. 9, section 3	Weiss, ch. 8, exercises 1-2  Program 3, part 1 due	Graph representation Topological sorting Shortest paths
11	3/31	Read Weiss, ch. 9, section 4	Weiss, ch. 9, exercises 1-2	Shortest Paths Network flows
	4/2	Read Weiss, ch. 9, sections 5-6	Weiss, ch. 9, exercises 5, 11	Minimum Spanning Trees
	4/4	No reading	Weiss, ch. 9, exercises 7a, 15-16 Program 3 due	Review More Graphs
12	4/7	No reading	None	Exam 2
	4/9	No reading	None	No class
	4/11	Read Weiss, ch. 9, section 7	Take home for exam 2 due	NP-Complete Problems
13	4/14	Read Weiss, ch. 10, section 1	None	Greedy Algorithms
	4/16	None	None	Greedy Algorithms
	4/18	Read Weiss, ch. 10, section 2	Weiss, ch. 10, exercise 3 Program 4 due	Bin Packing Divide and Conquer
14	4/21	Read Weiss, ch. 10, section 3	Weiss, ch. 10, exercise 10	Dynamic Programming
	4/23	Read Weiss, ch. 10, section 4	Weiss, ch. 10, exercise 28	Randomized Algorithms
	4/25		Rough draft of research paper	Peer Review
15	4/28	Read Weiss, ch. 10, section 5	Weiss, ch. 10, exercise 31 Ethics exercise (on Blackboard)	Backtracking
	4/30	Read Weiss, ch. 12, section 2	Weiss, ch. 10, exercise 36 Program 5 due	Backtracking and Games Red-Black Trees
	5/2	No reading	Weiss, ch. 10, exercise 43 Paper 2 due	Wrap-up and Review