**Week1: Aug 25-27**

**Chapter 1 and 2 Algorithms and their Analysis (complexity)****PPTs 1 and 2**

**Hw 1**Due Sept 8:**<<— Note date change.**

page 61 3-2, 3-3aShow the relationship between the following (both ways. 2^{n}and n!

**MIT Video:**Peek Finding**Software**: Anaconda Python, Visual C++ 2013. Python Book

**Week2:Sept 3**

**Chapter 3:**Growth of Functions.- Project#1: Algorithm Growth
**Hw 2:**Due Sept 8**MIT Video:**Models of Computation**Project#1:**Write in python a function that when given a Roman Numeral will convert it to base 10. Here is a discussion of Roman Numerals. Add to this function main code that will convert and print 10 different well thought out test cases that exercise your function. Look for errors. Warm Up exercise.

**Week3:Sept 8-10**

- More Algorithm Complexity

**Exam Wed**

**Week4:Sept 15-17**

- Recurrence Relations and Merge Sort (see ppt) (See video)
- Recurrence Homework due Sept 24.
- Roman Numeral due Sept 22.
**Project#2:**Implement the 1D peak algorithm and determine the average complexity of finding a peak given the array is filled using a uniform random generator. Do some empirical calculation to determine this average complexity. Due Monday.- Study the list and tuple objects in Python. How do you think python list’s are implemented? What is the complexity of the append operation using your implementation ? Turn in a one page discussion assuming table doubling with associated complexity on Sept 24.

**Week5: Sept 22-24**

- Quick Sort and Heapsort
**Project#3: Median Analysis**

**Go to room 213**for class on Wednesday.

**Week6: Sept 29-Oct 1**

- Priority Queues and Project#3 discussion.

**Exam Wed**

**Week7:Oct 6,8**

**Median algorithms(heaps and BST trees)****BST tree operations and complexity**

**Week8: Oct 13-15**

**Linear sorting****Hashing**

**Week9: Oct 20-22**

- More hashing,Coalesced Hashing

**Exam Wed**

**Weel10:Oct 27-29: (Oct 27 is last day to drop)
**

**Week11:Nov 3-5
**

- Billiard Ball problem:In this project you are to apply the backtrack algorithm efficiently to solve the 15 ball problem. When this is solved apply it to the 21 ball problem as well. Document the code and give output for both of the above cases. Due next Tuesday.

**Week12:Nov 10-12**

**Exam Wed**

**Week13:Nov 17-19
**

**Week14:Nov 24-Thanksgiving
**

**Week15:Dec **1-3

**Final Exam Monday Dec 8th @5:45-7:45
**

**Week 17:**