Advanced Algorithms and Data Structures Tentative Schedule

  Send me an E-mail today (from your preferred email address) with the subject line containing “CMPS 3013″
  • Week 1 ( Aug 28-30-Sept 1) Introduction, Project#0 (Set of solutions)Due Sept 6, Review visual studio together with c++ classes and constructors.  Weekend Practice for building a linked list list class.
  • Week 2 (Sept 6-8)  Complexity, Homework#0 Due Wed Sept 13
  • Week 3 (Sept 11-13-15)Continue complexity,  Standard Template Library(part 1), for-range  and vectors. Note there are two reference sites that are very nice.  They are cppreference.com and cplusplus.com. Make a habit of using at least one of these regularly.  I normally use cplusplus.com. Pay particular note to the complexities of the methods you use. Here is a nice refresher tutorial on Classes if you need some review.
  •   Quiz Friday on Series and Complexity, Here is Project#1(Due Wed 27):Linked List class (Start NOW! and test,test, test as you proceed!!!.  Use the built in class generator of Visual Studio to construct all classes that you need in this course.  This is required!
  • Week 4 (Sept 18,20,22)  Template tutorial and the concise cplusplus version. Making classes and functions generic. Friday I will look at overloaded operators for the Fraction class. This allows you to define fractions x , y ,z and do things like z=x+y  and   z=x*y etc.  You can even overload << and be able to do this   cout<<x<<endl and also overload > in order to compare fractions. Vector vector, Matrix matrix are nice overloading examples. that are used in OpenGL graphics projects.
  • Week 5 (Sept 25,27,29)  Look at vector and matrix above, More templates. Project#1 Due on wed and Exam on Friday. We will review for the exam on Wed.    Project#2:(Jolly Jumpers) Due Oct 9th:(turn in just the source with your login name at top)
  • Week 6 (Oct 2,4,6) Go over exam, Look at UVa (see format),  BinSearchTrees ,  visualization of a BST,  (side note: Implementation of BST using smart ptrs)
  • Week 7 (Oct 9,11,13) Discuss project, More on BST’s, Example BST recursion problems,  Project#3(trees, Due wed 25 )<<–Start on this NOW there are ISSUES!
  • Week 8 (Oct 16,18,20)Threaded trees wiki (t), See PfaafExam II Oct 20 (BST trees and project)
  • Week 9 (Oct 23,25,27)DSW algorithm,  AVL-Treesvisualization
  • Week 10 (Oct 30,Nov 1,3)(Review Recurrence relations) heaps-and-heapsort, Project#4:Priority Queue Due Nov 10.
  • Week 11 (Nov 6,8,10)quicksort, O(n) sorts, sorting simulations, Shell sort(paper)(The complexity of this sort depends on the sequence and we do not know the best sequence,see wiki), Discuss some debugging methods!
  • Week 12 (Nov 13,15,17)  graphs, See graph editors below, project#5a:Graph Class Due Nov 21.
  • Week 13 (Nov 20,ThanksGiving) Minimal Spanning Trees
  • Week 14 (Nov 27,29,Dec 1Shortest Paths, Exam III 
to be completed

Useful sites

Debugging in Visual Studio

Lambda functions (Dr Dobb’s discussion)

Lvalue and Rvalue references and move semantics (dicusssion)

Algorithms in Java and Python are developed here. Here is a nice paper on the performance of different BST structures Pfaaf.  If you are interested in adding iterators to a BST class see this.  A great project would be to implement this using threaded pointers.

An algorithm DS course by MIT Prof. Erik Demaine .

Here is a graph editorHere‘s another one.

Comments are closed.