Algorithms Tentative outline

Recursion Practice Problems

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.
  1.   page 61 3-2, 3-3a
  2. Show the relationship between the following (both ways.   2n and n!

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

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

Week11:Nov 3-5

  • Matrix Chain Multiplication
  • Optimal Binary Search Trees

Week12:Nov 10-12

  • Longest Common Sub-sequence
  • Other examples

Week13:Nov 17-19

  • More examples to discuss.  Knapsack, Intro to Greedy ALgorithms
  • Exam  Wed (Red Black Trees, Dynamic programming and Coalesced Hashing)

Week14:Nov 24-Thanksgiving

Week15:Dec 1-3

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

Week 17:

Comments are closed.