| Instructor: |
Robbie Schweller EIEAB 3.220 956-665-2667 robert.schweller@utrgv.edu Office hours: M: 8:15 am-10:15, W: 1:45-3:45 pm, and by appointment. |
| Schedule: | EIEAB 2.209, TR 9:30 am - 10:45 am |
| 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 |
| Sorting and Searching | |||
| 8/24 | No class |
Algorithm Analysis
Heap Sort vs. Selection Sort Read: Chapters 1 and 2. |
hw0 (due 8/28) |
| 8/31 | Binary Search, QuickSort, MergeSort | Comparison Based Sorting
MergeSort analysis Asymptotic Notation Read: 7.6, 7.7, 7.8 |
hwTT1 (due 9/6) |
| 9/7 | Comparison Based Sorting
Lower Bound
Read: 7.6, 7.7, 7.8 |
Bounded-Universe Sorting: Counting Sort and Radix Sort
Read: Section 7.11 CountingSort.pdf RadixSort.pdf |
hwTT2 (due 9/13) |
| Data Structures | |||
| 9/14 | Binary Search Trees | Binary Search Trees, AVL Trees
Reading: 4.1-4.3, 4.4, 12.4.2 avlRotations.pdf |
|
| 9/21 | AVL Trees
avlRotations.pdf |
Exam 1 | |
| 9/28 | Tries trieSlides1.pdf wikipedia: Trie | Tries
trieSlides1.pdf
wikipedia: Trie words2.txt |
|
| 10/5 | Heaps
lecHEAP-slides.pdf Reading: 6.1-6.4 |
Hash Tables and Maps
unordered_map map Reading: Chapter 5 |
|
| Graph Algorithms | |||
| 10/12 | Graphs
Reading: 9.1-9.3 |
Graphs, Graph Searching, BFS
BFS.pdf |
|
| 10/19 | Shortest Paths: Dijkstra | Shortest Paths: Dijkstra | |
| 10/26 | Shortest Paths: Bellman-Ford | Network Flows, Perfect Matching, Edmonds-Karp
lecFLOW.pdf Reading: 9.4 |
|
| 11/2 | Network Flows, Perfect Matching, Edmonds-Karp
lecFLOW.pdf Reading: 9.4 |
Exam 2 | |
| Algorithm Design | |||
| 11/9 | Divide and Conquer Algorithms
Master Theorem Reading: Chapter 10.2 Karatsuba algorithm |
Divide and Conquer Algorithms
Reading: Chapter 10.2 Strassen algorithm Linear Time Selection Master Theorem - Multiple Size Divide and Conquer |
|
| 11/16 | Divide and Conquer Algorithms
Master Theorem - Multiple Size Divide and Conquer Linear Time Selection |
Dynamic Programming: Longest Common Subsequence
Reading: 10.3 |
|
| 11/23 | Dynamic Programming: Matrix Chains | Thanksgiving | |
| Complexity | |||
| 11/30 | NP-completeness
P,NP,NP-hard,NP-complete, polynomial-time reductions 3-SAT, k-clique |
Study Day | |
| 12/7 | Final Exam:
Section 05: Wednesday, 8:00am-9:45 Section 06: Wednesday, 10:15am-12:00 |
||