CS501 Lecture Notes

· Ullman’s notes is ps format

· William Jones’s book

· Logic, Probability, Series

• Mathematical Induction
• Complete Induction Example
• ADT, Data Structure
• Algorithm Analysis
• Searching
• Sorting
• Mergesort Example
• Stack
• Stack Applications
• Queue
• Linked List
• Linked List Example1
• Linked List Example 2
• Doubly Linked List
• First Last List
• Linked Queue Example
• Recursive Examples on Linked List
• Binary Tree
• Recursive Examples on Linked Tree
• Tower of Hanoi Example
• Fibonacci Example
• Recurrence Relations
• Analysis with Recurrence Relations
• Measuring Running Time
• Priority Queue
• Trie
• Leftmost-Child-Right-Sibling Representation of Trees
• Binary Search Tree

· Dynamic Programming

· Hashing

· Relational Data Model

· Relational Algebra

· Graph Data Model

• Connected Components of an Undirected Graph and Minimal Spanning Tree
• Depth-First Search and Topological Ordering
• Dijkstra’s Algorithm for Finding Shortest Paths
• Regular Expressions