Dixie State College -- Computer and Information Technology

SCHEDULE

Course:		CS 2420
This is an APPROXIMATE schedule.
Week	Reading and Lecture	Assignments�
1	Introduction, roll, syllabus, BartsBanner, Chapter 1.1, Exponents, binary, Logs, C++ Classes versus structs. Making robust classes. Start Student Class.� Assignment operator and Copy Constructor. Const methods and parameters
2	#include protection. Introduce program 1. Software testing. Vector and string classes. Template functions. Template classes - Pair example. Begin Big-O discussions.
3	Program 2 introduction. More Big-O. SAT, TSP, NP-Complete, Unsolveables. Multiplying and factoring 200 digit numbers. assert, Chapter 2 - algorithm analysis. Big O and other definitions. Big O rules and more examples. Average, Worst, Best cases. Max Subsequence problem.	Program 1 - Robust student class.
4	Chapter 3 - ADTs, Brief list, Stack, Queue. List as vector or linked list. STL template classes. STL iterators. Finish Ch 2. GCD.	Program 2 - vector of students timed.
5	Implementing a Linked List (ADT and header file). List constructor, Insert, TraverseAll. Node struct. General Linked Lists.	Program 3 - Enhance Program 2 with Delete and Retrieve
6	More TraverseAll examples. 2 GetCount ideas. Overview Find, Retrieve, Delete, Destructor. Check for repeats. Stack and Queue ADT. Queue as a circular linked list with 1 back pointer. Program 5 intro- Graphing Calculator. Infix versus postfix.	Test 1.
7	Calculator demo. Explain starting code. InfixToPostfix. EvalPostfix.	Program 4 - Redo Program 3 with Linked List.
8	Graphics calculator help.� Return Test 1. Calculator questions. Introduce Trees
9	BST::Insert code on board. Field Trip - AI competition? BST methods in groups, then on board by students. Find Retrieve, Destruct, Traverse	Program 5 - Graphing Calculator
10	BST::Delete on board by teacher. 3 Trees and general trees. Implementation ideas. 2-3 Trees. Pre order and post order traversals. Min and Max. AVL trees. Splay trees. STL maps and sets.
11	Hash tables. Hash functions. Collisions. Probing. Status array. Prime numbers. Hash constructor. Compare Hash and BST. Career presentation	Program 6 - BST template class and testing code
12	Hash delete issues. Wrapping when probing. Good hash functinos for numbers and strings. Bad hash functions. Clustering issues and fixes. Hash applications. Hash help. Recursion examples	Test 2.
13	Separate chaining and STL hash. Priority Queues using heaps. Test review. Program 8 introduction - Recursing a maze.	Program 7 - Hash template class and testing code.
14	Maze questions. Heap insert and Delete. Graphs.
15	Sorting algorithms - Bubble, Shaker, Quick, Merge. Try Catch. External methods	Program 8 - Maze solver using recursion
16	Test 3	Comprehensive FINAL TEST