Welcome to ITK 279: Algorithms and Data Structures

Spring, 2007

Syllabus

Grades on WebCT (login required)

UNIX Information Handout

Instructions for Using Exceed on Demand

Week	Date	Reading Assignment for this class	Assignments due	Topic
1	1/17	None	None	Introduction
	1/19	Skim Savitch, chs 1-3	None	UNIX C++
2	1/22	Skim Savitch, chs 4-6	Savitch, p. 136, exercise 4 (electronically submitted) -- postponed to Wednesday Email Questionnaire	C++ cont.
	1/24	Skim Savitch, chs. 7 and 9	Savitch, p. 136, exercise 4 (electronically submitted)	C++ cont.
	1/26	Read Savitch ch. 8	Savitch, p. 228, exercise 2 (electronically submitted)	Classes Strings
3	1/29	Read Savitch ch. 10	Savitch, p. 315, exercise 4 (electronically submitted)	Strings, cont. Overloading Operators Pointers
	1/31	No reading	WebCT Assignment HW 1/31 -- the problem is described in the assignment	Dynamic Arrays
	2/2	Savitch ch. 12 Weiss ch. 1, sections 1-3	None	Dynamic Classes
4	2/5	Weiss ch. 2	WebCT Assignment HW 2/5 -- the problem is described in the assignment	Recursion Algorithm Analysis
	2/7	Weiss, ch 3, sections 1-5	Homework for 2/7 described on WebCT (on paper, and I want only the actual functions)	Algorithm Analysis
	2/9	Finish Weiss, ch. 3	WebCT assignment HW 2/9 plus the paper for that assignment	Linked Lists Stacks Queues
5	2/12	Read Weiss, ch. 4, sections 1-2, 6	Ch. 2, exercises 7, 11(a, c, d), 12 (a, c, d)	Linked Lists Stacks
	2/14			Class cancelled
	2/16	Read Weiss, ch. 6, sections 1-3	See WebCT Notes and Homework for instructions	Queues Binary Trees
6	2/19	Read Weiss, ch.6, section 4	Ch. 3, exs 4, 5 (see notes on slides)	Traversals Priority Queues
	2/21	Read Weiss, ch. 7, sections 1-4	Ch. 4, exs 1-2, 8	Heaps
	2/23	Weiss, chapter 7, section 5	Chapter 6, exs. 2 and 3 (apply 3 to 2a) Program 1	Elementary sorts Shellsort
7	2/26	Weiss, chapter 7, sections 6-7	Elementary sorting exercise on WebCT Chapter 7, exercise 4	Heapsort Mergesort
	2/28	Weiss, chapter 7, section 8-10	Chapter 7, exercises 11, 12 and 15	Quicksort Bin sorting
	3/2	Finish Weiss, chapter 7	Quicksort exercise on WebCT	Exam review External sorting
8	3/5	None	None	Exam 1 (material through mergesort)
	3/7	Weiss, chapter 4, sections 3-4	None	Binary Search Trees AVL Trees
	3/9	Weiss chapter 4, section 5	Chapter 4, exercise 9 Program 2	AVL Trees Splay Trees
		SPRING BREAK	NO SCHOOL
9	3/19	Weiss, chapter 4, sections 7-8	Chapter 4, exercise 19	B-Trees
	3/21	Weiss, chapter 5, sections 1-4	Chapter 4, exercise 27	Hashing
	3/23	Finish Weiss, chapter 5	B-tree exercise on WebCT Paper 1	Hashing, cont.
10	3/26	Read chapter 8	Chapter 5, exercise 1	Disjoint sets
	3/28	Chapter 9, sections 1-2	Chapter 5, exercise 19	Graphs
	3/30	Chapter 9, section 3	Chapter 8, exercises 1 and 2 Program 3, Part 1	Topological Sorting Shortest Paths
11	4/2	Chapter 9, section 4	Chapter 9, exercises 1 and 2	Graphs, cont.
	4/4	Chapter 9, section 5	Chapter 9, exercises 5 and 7a	Graphs, cont.
	4/6	Chapter 9, section 6	Program 3	Graphs, cont.
12	4/9	Chapter 9, section 7	Ressearch paper topic paragraph Chapter 9, exercises 11, 15, 16	Graphs, cont. NP-complete
	4/11	None	None	NP-complete
	4/13	None	None	Exam 2
13	4/16	Chapter 10, section 1	None	Greedy algorithms
	4/18	Chapter 10, section 2	Chapter 10, exercise 3 Exam 2 take home	Bin packing Divide and Conquer
	4/20	Chapter 10, section 3	Program 4	Dynamic Programming
14	4/23	Chapter 10, section 4	Chapter 10, exercise 10	Exam 2 Random numbers
	4/25	Chapter 10, section 5	Chapter 10, exercise 28	Skip Lists Back tracking
	4/27	None	Research paper rough draft	Peer review
15	4/30	None	Chapter 10, exercise 31 Ethics exercise	Back tracking
	5/2		Program 5 Chapter 10, exercise 43	Red-black trees
	5/4		Research Paper	Wrap-up Review