CS W3137 Data Structures and Algorithms, Spring 2015,

TENTATIVE SCHEDULE, SUBJECT TO CHANGE

Class 1: Jan. 20	Introduction to Data Structures and Algorithms	Assignment: Read Chapters 1-2 Weiss textbook Homework 1 Due 2/5
Class 2: Jan. 22	Measuring Running Time of Programs - PDF Measuring Running Time of Programs - Presentation Selection Sort Demo Proof that log^c(n) is O(n) Merge Sort Demo Merge Sort Example
Class 3: Jan. 27	Towers of Hanoi program Fibonacci Number computation with timings Java TimeInteval computation code Graph of Fibonacci and Towers of Hanoi timings	Assignment: Read Chapter 3
Class 4: Jan. 29	Linked Lists MagazineRack Java program (.zip format) Java Collection Interfaces and Sub classes
Class 5: Feb. 3	Linked Lists Lecture 2: Collections, Fibonnaci, Gradle 101, and Homework 1 submission details Adding arbitrary precision integers Factorial Program using Linked Lists and arbitrary precision arithmetic Homework 1 part 2 build script Homework 1 part 2 run script (Choice 1 - nonapplet version) Homework 1 part 2 applet html (Choice 2 - applet version)
Class 6: Feb. 5	Stacks Notes Stacks Class Presentation
Class 7: Feb. 10	Queues Java code for Queue implementation as circular linked list Maze Search Algorithm: Breadth First Search Queues class presentation	Assignment: Read Chapter 4, sections 4.1 - 4.3
Class 8: Feb. 12	Problem solving review
Section 1: Feb. 13	Special Java Review Section -
Class 9: Feb. 17	Trees Tree Traversal code and output Java code for printing out the file names in a file system Tree Class Presentation
Class 10: Feb. 19	Binary Search Trees Java code to build and Display a Binary Search Tree. PDF version of code. Binary Search Tree Class Presentation.	Assignment: Read Chapter 4, section 4.4 - 4.9
Class 11: Feb. 24	AVL Trees AVL Applet demo AVL class presentation
Class 12: Feb. 26	Splay Trees Multiway trees (Tries) Java Code to build a Trie Splay Trees and Tries	Assignment: Read Chap. 6.1 - 6.4
Class 13: Mar. 3	Priority Queues Treaps Priority Queues and Treaps	Homework 3 Written due 3/10, Programming due 3/24 Treaps, section 12.3
Class 14: Mar. 5	Huffman Coding and Trees Midterm Exam Sample Problems Huffman Codes and Midterm	Weiss sec. 10.1.2
Class 15: Mar 10:	Homework 3 Solutions
Class 16: Mar. 12	Midterm Exam, in class, closed book and notes	Reading Assignment: Chapter 5, Hashing
Class 17: Mar. 24	Midterm Post Mortem LZW Coding LZW coding applet Hashing	Homework 4 - Hashing, Heaps, and Huffman Codes - Due 4/7
Class 18: Mar. 26	Perfect hashing Calculating Primes HashMap in Java	Read Ch. 7, Sorting
Class 19: Mar. 30	Sorting Animated Sorting Algorithm applets More Animated Sorting Algorithm applets	Read Chapter 9, Graphs
Class 20: Apr. 2	Graphs
Class 21: Apr. 7	More graphs	Homework 5 due 4/21
Class 22: Apr. 9	Shortest Path Algorithms
Class 23: Apr. 14	Graph Applications
Class 24: Apr. 16	The Traveling Salesman Problem Lecture Notes on TSP
Class 25: Apr. 21	Convex Hull Algorithms
Class 26: Apr. 23	Map Reduce, Big Data, and Parallelism Map/Reduce by example Distributed KD Tree for Map/Reduce image retrieval	Homework 6 - Due 5/7 11:30 AM Read Chapter 12.5 KD trees
Class 27 Apr. 28	Homework 4 and 5 solutions
Class 28 Apr. 30	Study Sheet for Final Exam	Study sheet review
Fri. May 8	Final Exam Review Session, 4:30 - 6:00 833 Mudd
TBA	Final Exam, 9:00am - 12:00pm, 833 Mudd