Spring 2019 
CIS 3223
Basic
Information
· Lecture Time: Tuesday, Thursday
· Instructor: Haibin Ling  SERC 382, 2152046973  2152046973  hbling AT
temple.edu
· Office Hours: Tuesday
· TA: Fengjiao Li  SERC 360  tuj42942 AT temple.edu
· Office Hours: Thursday
1:30pm3:30pm or by appointment
Quick links
Syllabus 
Course Schedule
(NOTE: the
schedule is up to change)
Date 
Content 
Week 1 
Chapter 0.
Prologue 
1/15 
¨
0.1 Books and algorithms ¨
0.2 Enter Fibonacci 
1/19 
¨
0.3 BigO notation 


Week 2 
1. Algorithms with numbers 

¨
1.1 Basic arithmetic Homework
1 (due in class of 1/31) 

¨
1.2 Modular Arithmetic 


Week 3 
Chapter 2. Divideandconquer algorithms 
1/29 
¨
2.1 Multiplication 
1/31 
¨
2.2 Recurrence
relations 


Week 4 
Chapter 2. Divideandconquer algorithms 
2/5 
¨
2.3 Mergesort 
2/7 
¨
2.4 Medians ¨
2.5 Matrix
multiplication Homework
2 (Chapter 2, due in class of 2/14):
2.2, 2.3, 2.5(a,c,e,g,j), 2.11, 2.13 Quiz
1 


Week 5 
Chapter 3. Decompositions of graphs 
2/12 
¨
3.1 Why graphs? 
2/14 
¨
3.2 Depth firstsearch
in undirected graphs 


Week 6 
Chapter 3. Decompositions of graphs 
2/19 
¨
3.3 Depth firstsearch
in directed graphs 
2/21 
¨
3.4 Strongly connected
components Homework 3 (due in class of 2/28): 3.1, 3.2, 3.3, 3.4 (i), 3.7, 3.9, 3.10, 3.16, 3.21 Quiz 2 


Week 7 
Chapter 4. Paths in graphs 
2/26 
¨
4.1 Distances 
2/28 
¨
4.2 Breadthfirst
search 


Week 8 Spring break 



Week 9 
Chapter 4. Paths in graphs 
3/12 
¨
4.3 Lengths on edges Homework
4 (due in class of 3/28): 4.1,
4.3, 4.11, 4.12, 4.16, 4.20 
3/14 
¨
4.4 Dijkstra's
algorithm Quiz
3 


Week 10 
Chapter 4. Paths in graphs 
3/19 
¨
4.5 Priority queue
implementation 
3/21 
¨
4.7 Shortest paths in
dags 


Week 11 
Chapter 5. Greedy algorithms 
3/26 
¨
5.1 Minimum spanning
trees 
3/28 
¨
5.4 Set cover Homework
5 (due in class of 4/9): 5.1, 5.2, 5.3, 5.6, 5.9 (a,c,e,g,i), 5.11, 5.34 


Week 12 
Chapter 6. Dynamic programming 
4/2 
¨
6.1 Shortest paths in
DAGs, revisited 
4/4 
¨
6.7 Independent sets in
trees Quiz 4 


Week 13 
Chapter 7. Linear programming and reductions 
4/9 
¨
7.1 An introduction to
linear programming Homework
6 (due in class of 4/16): 6.1, 6.2, 6.4, 6.21 
4/11 
¨
7.2 Flows in networks 


Week 14 
Chapter 7. Linear programming and reductions 
4/16 
Homework
7 (due in class of 4/23): 7.1 (in
addition, convert the LP problem to standard form), 7.3,
7.7, 7.10, 7.17 
4/18 
¨
7.6 The simplex
algorithm Quiz 5 


Week 15 
Chapter 8. NPcomplete problems 
4/23 
¨
8.2 NPcomplete
problems 
4/25 
Final review Quiz 6 


5/7 
Final
Exam 