Uses and reinforces basic data structure knowledge and techniques from Data Structures and Algorithms I (CS 3316). Covers several advanced data structures, including balanced search trees and graphs. Studies common algorithm design methods (Brute Force, Decrease and Conquer, Divide and Conquer, Greedy, and Dynamic Programming) to solve various classic problems. Emphasizes the space and time complexities of various data structures and their associated algorithms. Prerequisite: C.S. 3316. (1st)
Expectations:
E1. Students know how to program in C++. (CS 3316)
E2. Students understand basic data structures like lists, sorted lists, stacks, and queues and can evaluate the best data structure to implement them. (CS 3316)
E3. Students understand space and time efficiency (Big O notation) of data structures and algorithms. (CS 3316)
E4. Students can write correct proofs by various means (proof by construction, proof by contradiction, proof by induction). (CS 3316)
Course Outcomes:
R1. Students implemented advanced data structures (Open Hash Table, B-Tree, and a Graph) using OOP design in C++ and used them in simple programs. (CS/SE 6, CS/SE 11, CS/SE 15)
R2. Students can perform in depth algorithm analysis, including average case efficiencies and Ω and Θ asymptotic notations. (CS/SE 3, CS/SE 14)
R3. Students know how to solve recurrences and use the Master Theorem for Divide and Conquer algorithms. (CS/SE 3, CS/SE 14)
R4. Students understand different algorithm design techniques (Brute Force, Divide and Conquer, Decrease and Conquer, Greedy, Dynamic Program, etc.). (CS/SE 3, CS/SE 11)
R5. Students can prove the correctness of an algorithm. (CS/SE 11, CS/SE 14)
R6. Students understand algorithms that solve the classic problems, such as sorting, knapsack, string processing, matrix multiplication, spanning trees, shortest paths, traveling salesperson, and Huffman coding. (CS/SE 3, CS/SE 11)
R7. Students can identify and understand why some problems cannot be solved efficiently (NP problems). (CS/SE 3, CS/SE 11) |
