• lecturer: Prof. Dr. Amr El-Masry
• T.A:
  • Eng. Sami Mamdouh
  • Eng. Mohamed Ibrahim
  • Eng. Mina Shafik

• Complexity Analysis
• Sorting
• Priority Queues
  • implementation with heaps
• Balanced Trees
  • AVL Trees
• Hashing
• File Structure
  • B-Trees
• Graphs
  • Traversal
  • Minimum Spanning Trees
  • Shortest Path

CLRS, Introduction to Algorithms, 3rd Edition
supplmentary reference: [Mathematics for Computer Science][mathcs] [mathcs]: https://www.cs.princeton.edu/courses/archive/fall06/cos341/handouts/mathcs.pdf [asymcheatsheet]: http://web.mit.edu/broder/Public/asymptotics-cheatsheet.pdf

• Course Logistics
  • Course Content
  • Grading Policy
  • References
• Table of Content
• [Week 1](#week 1)
  • Complexity Analysis
• [Week 2](#week 2)
  • Priority Queues
  • Priority Queues implementation with Heaps
  • Solving Recurrence Relations
• [Week 3](#week 3)
  • Sorting Algorithms

Computer scientists make heavy use of a specialized asymptotic notation to describe the growth of functions approximately. The notation involves six weird little symbols.

see the [mathematics for computer science][mathcs] reference section 11.3 and the [asymtotics cheat sheet][asymcheatsheet] for more details

Here is the definition of a priority queue as described in CLRS, section 6.5
A priority queue is a data structure for maintaining a set S of elements, each with an associated value called a key. A max-priority queue supports the following operations:

• INSERT(S, x)
  inserts the element x into the set S, which is equivalent to the operation S = S U {x}. (U means union)
• MAXIMUM(S)
  returns the element of S with the largest key.
• EXTRACT-MAX(S)
  removes and returns the element of S with the largest key.
• INCREASE-KEY(S, x, k)
  increases the value of element x’s key to the new value k, which is assumed to be at least as large as x’s current key value.

• C/C++
• Java

• Selection Sort O(N^2)
• Bubble Sort O(N^2)
• Merge Sort O(N__Lg(N))