PSU CMPSC 465

Algorithms and Data Structures

---

Sections

• Assignment 1
• Assignment 2
• Assignment 3
• Assignment 4
• Assignment 5
• Midterm
• Assignment 6
• Assignment 7
• Assignment 8
• Final

---

Query Algorithm (e.g., search tree)

• point lookup

• rank query

• range query

Lay out the data in such a way as to facilitate a query, in a way that would be faster than simply scanning unsorted records

Insert Algorithm (for dynamic data structure)

Delete Algorithm (for dynamic data structure)

Analysis

• Proof of correctness

  • formalize inputs and outputs

  • establish properties necessary for correct outputs

  • show that these properties hold for all inputs

• Performance analysis

  • provide upper/lower bounds on space (memory/storage) and time (number of cpu operations, the number of things the algorithm has to do): a function of input size

  • expected case analysis requires statistics

  • can we beat brute force?

• Asymptotic Analysis

• Divide and Conquer - split problem into two or more sub problems and recursively solving those and then merging the results together

  • recursive functions

  • recurrence relations

• Trees - a special case of a graph

• Graphs

• Greedy Algorithms

• Dynamic Programming

• Linear Programming and Flow Networks

• Complexity Theory