CSC 382 Analysis of Algorithms

▪ 01-27 (Tue): Syllabus

Iteration

  • Minimum and Maximum
  • Top-2
  • Polynomial
▪ 01-29 (Thu):
  • Rotate an Array

Recursion

  • Sum an Array Using Recursion
  • Highest Element in an Array Using Recursion

Binary Search

  • First Occurrence
  • Negative Numbers
▪ 02-03 (Tue):
  • Find Peak Element

Vectors

  • Add an Element at the End
  • Circular Queue
  • Address of Element of Matrix

Linked Lists

  • Middle of the Linked List
  • Linked List Cycle
  • Intersection of Two Linked Lists
▪ 02-05 (Thu):
  • Implement Queue using Stacks

Hash Tables

  • Sort Characters by Frequency
  • Two Sum
  • Longest Substring Without Repeating Characters
▪ 02-10 (Tue):
  • Representations of Trees

Binary Search Trees (slides)

  • Range Sum
  • Build from Sorted Array
▪ 02-19 (Thu):

Growth of Functions

  • Asymptotic Notation (O-Notation)
  • Ordering by Asymptotic Growth Rates
▪ 02-24 (Tue):

Simple Sorting Algorithms

  • Insertion Sort
  • Bubble Sort
  • Selection Sort
  • Analysis of Insertion Sort (Code)
▪ 02-26 (Thu):

Heaps

  • Heapsort
  • Heapify
▪ 03-03 (Tue):
  • Priority Queues

Quick Sort and Select

  • Top-k
  • Find Median

Merge Sort

▪ 03-05 (Thu):
  • Merge K Linked Lists

Review I (Last Exam I)

▪ 03-10 (Tue):

Exam I

▪ 03-12 (Thu):

Divide-and-Conquer

  • Maximum-Subarray
▪ 03-17 (Tue):

Probability and Random

  • Randomly Permuting Arrays
▪ 03-19 (Thu):
  • The Hiring Problem

Dynamic Programming

  • Fibonacci
▪ 03-24 (Tue):
  • Rod Cutting
▪ 03-26 (Thu):
▪ 03-31 (Tue):
  • Longest Common Subsequence — Bottom-Up
  • Unique Paths (Top-Left to Bottom-Right Corner)
▪ 04-14 (Tue):

Greedy

  • The Activity Selection Problem
  • Huffman Codes
▪ 04-16 (Thu):
  • The Knapsack Problem

Graph and Search

  • Graph Representation
▪ 04-21 (Tue):