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 (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 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 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 Breadth-first 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

¨   7.6 The simplex algorithm

 

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. NP-complete problems

4/23

¨   8.2 NP-complete problems

4/25

Final review

 

Quiz 6

 

5/7

3:30-5:30pm

Final Exam