|
|
|
General Information
|
|
Lecturer: Wing-Kai Hon
|
|
|
wkhon @ cs
|
|
|
|
|
Tutors : Yiming
Chen, Wisely Ku
Tutors : Foga
Liu, Jenny Liu
|
|
|
yiming @ cs , thku @ cs
fhliu @ cs, hhliu @ cs
|
|
|
|
Meeting Times:
|
|
|
Mon
1010—1200, Wed 0900—0950
|
|
|
Tutorial
(optional): Tue
1900—2000
|
|
|
|
|
Announcements
HW 5 Posted
Deadline: June 15, 2011 (11:59pm)
HW 6 Posted
Deadline: June 08, 2011 (before class)
Project Posted
Deadline: June 26, 2011 (11:59pm)
Quiz 3 is Coming!
Date: June 15, 2011 (8:45am)
Scope: Notes 13 – 15, Chaining,
HW 5,
HW 6
|
|
May 28:
|
Homework 5
[pdf] posted
|
|
May 28:
|
Notes 16 to 18 posted
|
|
Jun 01:
|
Homework 6
[pdf] posted
|
|
 Course Materials
|
Lecture
|
Topics
|
Related
Files
|
|
0
|
Overview
|
[pdf]
|
|
1
|
Getting Started
|
[pdf]
|
|
2
|
Growth of Functions
|
[pdf] [classwork]
|
|
3
|
Recurrence (Skipped)
|
[pdf]
|
|
4
|
Heap
|
[pdf]
|
|
5
|
Sorting in Linear Time
|
[pdf]
|
|
6
|
Lower Bound for Comparison Sorts
|
[pdf]
|
|
7
|
Pointers in C
|
[pdf]
|
|
8
|
Basic Data Structures (List, Stack, Queue)
|
[pdf]
|
|
9
|
Basic Data Structures (Trees, Graphs)
|
[pdf]
|
|
10
|
Graph and Tree Traversals (BFS, DFS)
|
[pdf]
|
|
11
|
Graph and Tree Traversals (Preorder, Inorder, Postorder)
|
[pdf]
|
|
12
|
Graph and Tree Traversals (Topological Sort)
|
[pdf]
|
|
13
|
Searching Set Data (BST)
|
[pdf]
|
|
14
|
Searching Set Data (AVL Tree)
|
[pdf]
|
|
15
|
Searching Set Data (B Tree)
|
[pdf]
|
|
16
|
Probability and Expectation
|
[pdf]
|
|
17
|
Searching Set Data (Hashing I: Chaining, Open
Addressing)
|
[pdf]
|
|
18
|
Searching
Set Data (Hashing II: Choosing a Good Hash Function)
|
[pdf]
|
|
Tutorials
|
Topics
|
Related
Files
|
|
1
|
¨
Practices with Mathematical Induction
¨
Binary Search with Recursion
|
[codes for bsearch]
|
|
2
|
¨
Revision on Insertion Sort and Selection Sort
¨
Recursive + Iterative Binary Search (Coding)
|
[codes for bsearch]
|
|
3
|
¨
Revision on Big-O
¨
Insertion + Selection + Merge Sort (Coding)
|
[example for Big-O]
[codes for sorting]
|
|
4
|
¨
Revision on Heap + Coding
|
[codes for heap]
|
|
5
|
¨
Revision on Sorting Lower Bound
¨
Concept of Problem Reduction
|
|
|
6
|
¨
List + Queue + Stack (Coding)
|
|
|
7
|
¨
Revision on BFS and DFS
|
|
|
8
|
¨
Revision on Topological Sort
|
|
|
9
|
¨
Revision on BST
|
|
|
10
|
¨
Infix to Postfix Conversion
|
[slides]
|
|
11
|
¨
Revision on AVL Tree
|
|
|
Assignment
|
Topics
|
Related
Files
|
|
1
|
Growth of Functions, Heap
|
[pdf]
|
|
2
|
Queue and Stack (Programming)
|
[pdf]
|
|
3
|
Graph and Tree Traversals
|
[pdf]
|
|
4
|
Infix-to-Postfix Conversion (Programming)
|
[pdf]
|
|
5
|
AVL Tree (Programming)
|
[pdf]
|
|
6
|
Searching Set Data
|
[pdf]
|
|
Project
|
Implementing a Contact Book
|
[pdf]
|
 Teaching Plan
|
1
|
Getting Started
|
Lecture 01 – Lecture 02
|
|
2
|
Sorting
|
Lecture 04 – Lecture 06
|
|
3
|
Fundamental Data Structures
|
Lecture 08 – Lecture 09
|
|
4
|
Graph and Tree Traversals
|
Lecture 10 – Lecture 12
|
|
5
|
Searching Set Data
|
Lecture 13 – Lecture 18
|
|
6
|
Advanced Topics
|
Not Covered
|
Last updated: June 08, 2011
|