Spring 2018 - 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: Chao Han | SERC 336 | chao.han AT temple.edu

·  Office Hours: Monday 10am-12pm or by appointment


Quick links
Syllabus |


Course Schedule (NOTE: the schedule is up to change)

Date

Content

Week 1

Chapter 0. Prologue

1/16/18
 

¨   0.1 Books and algorithms

¨   0.2 Enter Fibonacci

1/20/18

¨   0.3 Big-O notation

 

Week 2

1. Algorithms with numbers

1/23/18

¨   1.1 Basic arithmetic

1/25/18

¨   1.2 Modular Arithmetic

 

Homework 1 (due in class of 2/6):

     Chapter 0: 0.1 (a,c,e,g,i,k,m,o), 0.2 (a,b), 0.3 (a)

     Chapter 1: 1.2, 1.4, 1.12, 1.18, 1.20 (20 mod 79, 21 mod 91), 1.23

 

Week 3

Chapter 2. Divide-and-conquer algorithms

1/30/18

¨   2.1 Multiplication

2/1/18

¨   2.2 Recurrence relations

 

Week 4

Chapter 2. Divide-and-conquer algorithms

2/6/18

¨   2.3 Mergesort

2/8/18

¨   2.4 Medians

 

Quiz 1

 

Week 5

Chapter 2. Divide-and-conquer algorithms | Chapter 3. Decompositions of graphs

2/13/18

¨   2.5 Matrix multiplication

 

Homework 2 (due in class of 2/22)

2/15/18

¨   3.1 Why graphs?

 

Week 6

Chapter 3. Decompositions of graphs

2/20/18

¨   3.2 Depth first-search in undirected graphs

2/22/18

¨   3.3 Depth first-search in directed graphs

 

Week 7

Chapter 3. Decompositions of graphs | Chapter 4. Paths in graphs

2/27/18

¨   3.4 Strongly connected components

3/1/18

¨   4.1 Distances

 

Homework 3 (due in class of 3/13)

Quiz 2

 

Week 8                              Spring break

 

Week 9

Chapter 4. Paths in graphs

3/13/18

¨   4.2 Breadth-first search

3/15/18

¨   4.3 Lengths on edges

 

Homework 4 (due in class of 3/29)

 

Week 10

Chapter 4. Paths in graphs

3/20/18

¨   4.4 Dijkstra's algorithm

3/22/18

¨   4.5 Priority queue implementation

 

Quiz 3

 

Week 11

Chapter 4. Paths in graphs  | Chapter 5. Greedy algorithms

3/27/18

¨   4.7 Shortest paths in dags

3/29/18

¨   5.1 Minimum spanning trees

 

Homework 5 (due in class of 4/10)

 

Week 12

Chapter 5. Greedy algorithms  | Chapter 6. Dynamic programming

4/3/18

¨   5.4 Set cover

4/5/18

¨   6.1 Shortest paths in dags, revisited

 

Quiz 4

 

Week 13

Chapter 6. Dynamic programming | Chapter 7. Linear programming and reductions

4/10/18

¨   6.7 Independent sets in trees

 

Homework 6 (due in class of 4/17)

4/12/18

¨   7.1 An introduction to linear programming

 

Week 14

Chapter 7. Linear programming and reductions

4/17/18

¨   7.2 Flows in networks

 

Homework 7 (due in class of 4/26)

4/19/18

¨   7.6 The simplex algorithm

 

Quiz 5

 

Week 15

Chapter 8. NP-complete problems

4/24/18

¨   8.2 NP-complete problems

4/26/18

Final review

 

Quiz 6

 

5/8/18

3:30-5:30

Final Exam