Skip to content

Course Syllabus

SE 4230 Advanced Algorithms

  • Division: Natural Science and Math
  • Department: Computer Science & Engineering
  • Credit/Time Requirement: Credit: 3; Lecture: 3; Lab: 0
  • Prerequisites: CS 2420, MATH 3310
  • Corequisites: SE 4270, SE 4400
  • Semesters Offered: Fall
  • Semester Approved: Spring 2024
  • Five-Year Review Semester: Fall 2028
  • End Semester: Fall 2029
  • Optimum Class Size: 20
  • Maximum Class Size: 24

Course Description

This course explores various key computational problems, landmark algorithms, design paradigms, and analysis techniques, preparing students to create and analyze algorithmic solutions to novel problems. The course leverages mathematics and computing prerequisites and builds significantly beyond the fundamentals of data structures and algorithms introduced in CS 2420.

Justification

This course is required for the bachelor's degree in software engineering. It hones essential skills of thought for any computer scientist or software engineer and also serves as an important bridge for students wishing to pursue advanced degrees in computer science. The course is also used to assess multiple ABET student outcomes (numbers and wording for SLOs referencing "ABET" come from the Criteria for Accrediting Engineering Programs, 2024 -- 2025). For reference, other similar courses offered in Utah at the time of writing include BYU's CS 312 and the University of Utah's CS 4150 which are also junior- or senior-level courses that build upon a prerequisite introductory course on data structures and algorithms.

Student Learning Outcomes

  1. Students will be able to employ algorithm design techniques including brute-force, divide-and-conquer, dynamic programming, greedy approaches, and reductions involving graph algorithms.
  2. Students will be able to analyze the correctness and complexity of algorithms.
  3. Students will be familiar with a variety of key computational problems and know how to identify NP-Hard problems.
  4. Students will demonstrate an ability to identify, formulate, and solve complex engineering problems by applying principles of engineering, science, and mathematics (ABET-SO1).
  5. Students will demonstrate an ability to develop and conduct appropriate experimentation, analyze and interpret data, and use engineering judgment to draw conclusions (ABET-SO6).
  6. Students will demonstrate an ability to acquire and apply new knowledge as needed, using appropriate learning strategies (ABET-SO7).

Course Content

Design approaches highlighted in the course include (but are not limited to):• brute-force• divide-and-conquer• greedy• dynamic programming• reduction-based solutionsHeuristic, approximation, randomization, and learning-based approaches are also considered (although depth may vary).Emphasized analysis techniques may vary but the following should be included:• Big-O notation• Recursion trees and a master theorem for recurrences• Proof by induction• Reduction-based proofs of NP-hardnessComputational problems of focus (with corresponding algorithms, applications, and/or analyses) may include examples such as:• string matching• strongly-connected components• shortest path• spanning trees• self-balancing search trees• encoding and compression• optimal binary search trees• knapsack• network flows• integer and linear programming• Boolean satisfiability• Hamiltonian circuitThe course emphasizes the importance of bringing a variety of ideas and approaches to bear for problem solving.