CST 370

Algorithms

CST 370: Algorithms

Students learn important data structures in computer science and acquire fundamental algorithm design techniques to get the efficient solutions to several computing problems from various disciplines. Topics include the analysis of algorithm efficiency, hash, heap, graph, tree, sorting and searching, brute force, divide-and-conquer, decrease-and-conquer, transform-and-conquer, dynamic programming, and greedy programming.
CST 370's Homework GitHub Repository

Week 1

Topics:

  • Data Structures
  • Analysis Frameworks
  • Non-recursive Algorithms Analysis
  • Recursive Algorithm Analysis
  • Asymptotic Notation

Homework

  1. Displays the the closest distance between two numbers
  2. Checks if two strings are anagrams
  3. Displays the maximum number of events that take place concurrently

Week 2:

Topics:

  • Intro to Recursion
  • Intro to Brute Force

Homework

  1. Converts a user input directed graph into an adjacency matrix
  2. Displays all possible subsets using binary numbers
  3. Collects max number of apples using brute force techniques

Week 3:

Topics:

  • Exhaustive Search
  • Depth-First Search (DFS)
  • Breadth-First Search (BFS)
  • Intro to Divide N Conquer

Homework

  1. Reverses a positive integer
  2. Presents a path for Traveling Salesperson Problem
  3. Implements the Depth-First Search Algorithm

Week 4:

Topics:

  • Merge Sort

Week 5:

Topics:

  • Quick Sort
  • Tree Traversals
  • Intro to Decrease N Conquer
  • Topological Sorting
  • Binary Search N Presorting

Homework

  1. Uses partitioning to place all negative numbers in the first half of the set
  2. Find the max number in an array using the Divide and Conquer technique
  3. Performs topological sorting based on Kahn's algorithm

Week 6:

Topics:

  • AVL Trees
  • 2-3 Trees
  • Heaps
  • Hashing

Homework

  1. Perform head operations (e.g., insert, delete max, display, update)
  2. Displays the performance of 3 sorting algorithms
  3. Bonus: Implements a hash table using Linear Probing

Week 7

Topics:

  • Comparison Sorting
  • Intro to Dynamic Programming
  • Warshall's Algorithm
  • Floyds Algorithm
  • Intro to Greedy Technique and Prim

Homework

  1. Performs Radix Sort
  2. Using Dynamic Programming, collects max number of coins in a board
  3. Implements Floyd's Algorithm to calculate all-pairs shortest paths

Week 8

Topics:

  • Dijkstra's Algorithm