Instructor: |
Robbie Schweller EIEAB 3.220 956-665-2667 robert.schweller@utrgv.edu |
Schedule: | 3333.01: EENGR-1.272, TR 9:30am - 10:45 3333.03: EIEAB-2.203, TR 12:30-1:45pm |
Books: | Main: "Data Structures and Algorithm Analysis in C++", 4th edition by Mark A. Weiss. Recommended: "Introduction to Algorithms", any edition, by Cormen, Leiserson, Rivest, Stein. | Syllabus: | CSCI3333_syllabus |
Week | T | R | Homework |
1/15 | Algorithm Analysis Heap Sort vs. Selection Sort Read: Chapters 1 and 2. sortTest.cpp | Binary Search vs. Linear Search search.cpp | hw0 (due 1/19) hwTT1 (due 1/21) |
1/22 | Asymptotic Analysis | Asymptotic Notation and Tools Merge Sort and Quick Sort | hwTT2 (due 1/28) |
1/29 | Comparison Based Sorting Read: 7.6 (mergesort) 7.7 (quicksort) 7.8 (lower bound) | Master Theorem Karatsuba's algorithm Reading: Chapter 10.2 Reading: Karatsuba algorithm | hwLLmergeSort (due 2/4) |
2/5 | Divide & Conquer Algorithms Reading: Chapter 10.2 Reading: Strassen algorithm Reading: Linear Time Selection Reading: Multiple-Size Divide-and-Conquer Recurrences | Bounded-Universe Sorting Reading: Section 7.11 Reading: Radix Sort CountingSort.pdf RadixSort.pdf | hwWRITTEN1 (due 2/11) |
2/12 | Bounded-Universe Sorting Reading: Section 7.11 Reading: Radix Sort CountingSort.pdf RadixSort.pdf | Binary Search Trees Reading: 4.1,4.2,4.3 binarySearchTree.h driver.cpp | hwWRITTEN2 (due 2/18) |
2/19 | AVL Trees Reading: 4.1,4.2,4.3 avlRotations.pdf avl.h binarySearchTree.h driver.cpp | Exam 1 | hwAC (due 3/3) |
2/26 | AVL Trees Reading: 4.4, 12.4.2 avlRotations.pdf | Tries wikipedia: Trie trieSlides1.pdf trie.h driver.cpp | hwAC2 (due 3/10) |
3/4 | Tries trieSlides2.pdf | Heaps Reading: 6.1-6.4 lecHEAP-slides.pdf minHeap.h driver.cpp | hwPQ (due 3/24) |
3/11 | Spring Break | Spring Break | |
3/18 | Hash Tables Reading: Chapter 5 STL map, unordered map, and set Reading: STL: unordered map STL: map STL: set mapDemo.cpp | Graphs, Breadth-First Search BFS.pdf directedGraph01.h directedGraph01.h driver.cpp | hwMZ0 (due 3/31) |
3/25 | Graphs, Graph Searching, Breadth First Search BFS.pdf driver.cpp directedGraph.h | Shortest Paths: Dijkstra's Algorithm | hwMZ1.pdf (due 4/7) |
4/1 | Shortest Paths: Bellman-Ford Algorithm | Exam 2 | hwMZ2.pdf (due 4/14) |
4/8 | Network Flows, Perfect Matching, Edmonds-Karp Algorithm lecFLOW.pdf | Network Flows, Perfect Matching, Edmonds-Karp Algorithm lecFLOW.pdf | hwTILE.pdf (due 4/21) |
4/15 | Dynamic Programming Reading: 10.3 | Dynamic Programming Reading: 10.3 | hwBLND.pdf (due 4/28) |
4/22 | Dynamic Programming: Longest Common Subsquence | Dynamic Programming: Floyld-Warshall all-pairs shortest path | |
4/29 | NP-completeness | NP-completeness | |
5/6 | NP-completeness | Final Exam: 3333.01: 5/9 8:00am-9:45am 3333.03: 5/9 10:15 am-12:00 pm |