Welcome to ITK 279: Algorithms and Data Structures

Fall, 2009

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	8/17	None	None	Introduction
	8/19	Skim Savitch, chs 1-3	None	C++
	8/21	Skim Savitch, chs 4-6	Email Questionnaire	C++, cont.
2	8/24	Skim Savitch, chs 7 and 9 Read Savitch 11.1	C++ practice 1	Classes
	8/26	Read Savitch, ch. 8	C++ practice 2	Strings Operator Overloading
	8/28	Read Savitch, ch. 10	C++ practice 3	Pointers Dynamic Memory
3	8/31	Read Savitch, ch. 12	C++ practice 4	Dynamic Classes
	9/2	Read Weiss, ch. 1	None	Files in C++ Recursion review
	9/4	Read Weiss, ch. 2	C++ practice 5	Algorithm Analysis
4	9/7	None	None	Labor Day, no class
	9/9	Weiss, 3.1-3.5	Recursion homework described on Blackboard in Notes and Homework	List review
	9/11	Finish Weiss, ch. 3	Weiss chapter 2, exercises 7, 11 (a,c,d), 12 (a,c,d)	Stack review Queue review
5	9/14	Weiss, 4.1-4.2, 4.6	List practice homework described on Blackboard in Notes and Homework	Binary Tree review
	9/16	Weiss, 6.1-6.3	Weiss chapter 3, exercises 4-5	Traversals Priority Queues
	9/18	Weiss, 6.4	Weiss, chapter 4, exercises 1, 2, and 8	Heaps
6	9/21	Weiss, 7.1-7.3	Weiss, chapter 6, exercises 2-3 (do 3 only for 2a)	Elementary Sorting Shellsort
	9/23	Weiss, 7.4-7.6	Elementary sorting homework described on Blackboard  in Notes and Homework	Heapsort Mergesort
	9/25	Weiss, 7.7-7.8	Weiss, chapter 7, exercise 4 Program 1 due by Thursday at 11pm	Bottom-up Mergesort Quicksort
7	9/28	Finish Weiss, ch. 7	Weiss, chapter 7, exercises 11, 12, 15	Bin sort External sorting
	9/30	Weiss, 4.3	Quicksort homework described on Blackboard in Notes and Homework	Review Binary search trees
	10/2	None	None	Exam 1
8	10/5	Weiss, 4.4	Weiss, chapter 4, exercise 9	AVL trees
	10/7	Weiss, 4.5	Weiss, chapter 4, exercise 19	Splay trees
	10/9	Finish Weiss ch. 4	Program 2 due by Thursday at 11pm	B-trees
9	10/12	Weiss, 5.1-5.5	Weiss, chapter 4, exercise 27 B-tree homework from Blackboard	Hashing
	10/14	Finish Weiss ch. 5	Weiss, chapter 5, exercise 1	Extendible hashing
	10/16	Weiss, 8.1-8.3	Paper 1	Class canceled
10	10/19	Finish Weiss, ch. 8	Weiss, chapter 5, exercise 19	Disjoint Sets
	10/21	Weiss, 9.1-9.3	Weiss, chapter 8, exercises 1-2	Graph representation
	10/23	Weiss, 9.4	Prog 3 part a	Topological Sorting Shortest paths
11	10/26	Weiss, 9.5	Weiss, chapter 9, exercises 1-2	Network flow Critical paths Transitive closure
	10/28	Weiss, 9.6	Weiss, chapter 9, exercises 5, 7a	Minimum Spanning Tree Applications of Searching
	10/30	Finish Weiss, ch. 9	Program 3	Applications of Searching NP
12	11/2	Weiss, 10.1	Weiss, chapter 9, exercises 11, 15, 16	NP problems Greedy algorithms
	11/4	None	Topic paragraph for research paper	Huffman code Bin-packing
	11/6	None	Exam 2 take-home	Exam 2
13	11/9	Weiss, 10.2	Weiss, chapter 10, exercise 3	Bin-packing Divide and Conquer
	11/11	Weiss, 10.3	Weiss, chapter 10, exercise 10	Dynamic Programming
	11/13	None	Program 4	Dynamic Programming, cont.
14	11/16	Weiss, 10.4	Chapter 10, exercise 28	Randomized algorithms
	11/18	Weiss, 10.5	Chapter 10, exercise 31	Backtracking
	11/20	None	Rough draft	Peer review
				Thanksgiving Break - no class
15	11/30	Weiss, 12.2	Chapter 10, exercise 36 Ethics exercise
	12/2		Chapter 10, exercise 43 Program 5
	12/4		Research paper