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-3a
- Show the relationship between the following (both ways. 2n and n!
- 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.
- More Algorithm Complexity
- Exam Wed
- 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
- Median algorithms(heaps and BST trees)
- BST tree operations and complexity
Week8: Oct 13-15
- Linear sorting
Week9: Oct 20-22
- More hashing,Coalesced Hashing
- Exam Wed
Weel10:Oct 27-29: (Oct 27 is last day to drop)
- Project4: Coalesced Hashing (due Nov 12)
- Red Black Trees (Demo)
- Dynamic programming. Watch MIT video on Dynamic Programming
- Matrix Chain Multiplication
- Optimal Binary Search Trees
- Longest Common Sub-sequence
- Other examples
- More examples to discuss. Knapsack, Intro to Greedy ALgorithms
- Exam Wed (Red Black Trees, Dynamic programming and Coalesced Hashing)
Final Exam Monday Dec 8th @5:45-7:45