Spring 2019 - CIS 3223

Data Structures and Algorithms

Basic Information

·  Lecture Time: Tuesday, Thursday 3:30am 4:50pm, TTLMAN 0401A

·  Instructor: Haibin Ling | SERC 382, 215-204-6973 | 215-204-6973 | hbling AT temple.edu

·  Office Hours: Tuesday 1:30pm-3:30pm or by appointment

·  TA: Fengjiao Li | SERC 360 | tuj42942 AT temple.edu

·  Office Hours: Thursday 1:30pm-3: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 Big-O notation

 

Week 2

1. Algorithms with numbers

1/22/18

¨   1.1 Basic arithmetic

 

Homework 1 (due in class of 1/31)

1/24/18

¨   1.2 Modular Arithmetic

 

Week 3

Chapter 2. Divide-and-conquer algorithms

1/29

¨   2.1 Multiplication

1/31

¨   2.2 Recurrence relations

 

Week 4

Chapter 2. Divide-and-conquer algorithms

2/5

¨   2.3 Mergesort

2/7

¨   2.4 Medians

¨   2.5 Matrix multiplication

 

Homework 2 (due in class of 2/14)

Quiz 1

 

Week 5

Chapter 3. Decompositions of graphs

2/12

¨   3.1 Why graphs?

2/14

¨   3.2 Depth first-search in undirected graphs

 

Week 6

Chapter 3. Decompositions of graphs

2/19

¨   3.3 Depth first-search in directed graphs

2/21

¨   3.4 Strongly connected components

 

Homework 3 (due in class of 3/12)

Quiz 2

 

Week 7

Chapter 4. Paths in graphs

2/26

¨   4.1 Distances

2/28

¨   4.2 Breadth-first search

 

Week 8                              Spring break

 

Week 9

Chapter 4. Paths in graphs

3/12

¨   4.3 Lengths on edges

3/14

¨   4.4 Dijkstra's algorithm

 

Homework 4 (due in class of 3/28)

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/4)

 

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)

4/11

¨   7.2 Flows in networks

 

Week 14

Chapter 7. Linear programming and reductions

4/16

¨   7.6 The simplex algorithm

 

Homework 7 (due in class of 4/23)

4/18

¨   7.6 The simplex algorithm

 

Quiz 5

 

Week 15

Chapter 8. NP-complete problems

4/23

¨   8.2 NP-complete problems

4/25

Final review

 

Quiz 6

 

TBD

Final Exam