## Design and Analysis of Algorithms

3 Cr. (Hrs.:3 Lec.)

Uses and reinforces basic data structure knowledge and techniques from Data Structures and Algorithms (CSCI 232). 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: CSCI 232 & CSCI 246 (2nd)

Course generally offered spring (2nd) semester.

#### Expectations:

E1. Students know how to program in C++. (CSCI 232)

E2. Students understand basic data structures like lists, sorted lists, stacks, and queues and can evaluate the best data structure to implement them. (CSCI 232)

E3. Students understand and can use general trees, binary trees, binary search trees, and balanced search trees, tables, priority queues, heaps, hash tables, and graphs. (CSCI 232, CSCI 246)

E4. Students understand space and time efficiency (Big O notation) of data structures and algorithms. (CSCI 232)

E5. Students are able to use inference and to develop direct and inductive proofs, proofs by construction, and proofs by contradiction. (CSCI 232, CSCI 246)

E6. Students are familiar with a modern software configuration and management (SCM) platform. (CSCI 232)

#### Course Outcomes:

R1. Students have implemented advanced data structures (hash table, balanced search tree, and a graph) using OOP design in a high level programming language and used them in simple programs. (CS: 2, 6; SE: 1)

R2. Students can perform in depth algorithm analysis, including average case efficiencies and Ω and Θ asymptotic notations. (CS: 1, 6; SE: 1)

R3. Students know how to solve recurrences and use the Master Theorem for Divide and Conquer algorithms. (CS: 1, 6; SE: 1)

R4. Students understand different algorithm design techniques (Brute Force, Divide and Conquer, Decrease and Conquer, Greedy, Dynamic Programming). (CS: 2, 6; SE: 1)

R5. Students can prove the correctness of an algorithm. (CS: 6; SE: 1)

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: 5-1, 2, 6; SE: 1, III-1-2-1)

R7. Students can identify and understand why some problems cannot be solved efficiently (NP problems). (CS: 2, 6; SE: 1)

CS:
5-a-1 - Substantial coverage of algorithms and complexity, computer science theory, concepts of programming languages, and software development
5-a-2 - Substantial coverage of at least one general-purpose programming language
5-a-4 - The study of computing-based systems at varying levels of abstraction

SE:
III-1-2-1 - Computing fundamentals, software design and construction, requirements analysis, security, verification, and validation