Algorithms Tentative outline

Recursion Practice Problems

Week1:MLK day,  Jan 21

  • Chapter 1 and 2  Algorithms and their Analysis (complexity)
  • PPTs lecture1
  • MIT Video: Peek Finding
  • Software: Anaconda Python, Visual C++ 2013. Python Book

Week2:Jan 26-28:

Chapter 3:Growth of Functions.

  • Please send me an email ASAP so I can add you to my email list!!!!!
  • PPT lecture 2
  • Hw 1 : 3-3  Due: Feb 2
  • MIT Video: Models of Computation
  • Project#1: (Due Friday Feb 5) Empirical Studies of Two Sorting Algorithms.

Week3:Feb 2-4

  • More Algorithm Complexity

Week4:Feb 9-11

  • Exam on Monday!
  • 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.