CMPT307: Data Structures and Algorithms

CMPT 307: Data Structures and Algorithms

Classroom: Monday: C9000; Wednesday, Friday: WMC 3260
Time:9:30 am --- 10:20am

Instructor: Binay Bhattacharya Office: TASC I 8017, e-mail: binay@cs.sfu.ca

Office hours (Binay): MW 1:45 pm-2:30pm

TA: Ermin Hodzic (e-mail) ehodzic@sfu.ca

TA: Yanting Deng (e-mail) yantingd@sfu.ca

Office hours (Ermin): Tuesdays 11:00 am to 12 noon (Room: ASB 9808)
Office hours (Yanting): Fridays 3:00 pm to 4 pm (Room: ASB 9810)

Messages

27/11/2019: Quiz 4 is cancelled.
19/11/2019: Quiz 4 will be held on November 29.
19/11/2019: Homework 6 has been assigned.
02/11/2019: Quiz 3 will be held on November 15.
02/11/2019: Homework 5 has been assigned.
17/10/2019: Homework 4 has been assigned.
07/10/2019: Homework 3 has been assigned.
02/10/2019: Quiz 2 will be held on October 23.

22/09/2019: Homework 2 has been assigned.
18/09/2019: Quiz 1 will be held on October 2.

10/09/2019: Homework 1 has been assigned.
10/09/2019: Analysis of algorithms file is updated.
04/09/2019: All messages to the class will appear here.

Course Outlines in SFU Calendar

Lectures

10:30-11:20, Monday, Wednesday, Friday

Week

Date

Topics

Other Information

1

04/09 Course Organization (Introduction)(.pptx) Read Chapter 0

06/09 Analysis of Algorithms(.pdf)

2
09/09 Analysis of Fibonacci Sequence
Growth of Functions

11/09 Growth of Functions Work on the problems in Growth Of Functions notes

13/05 Complexity issues of multiplications, divisions, exponentiations; modular arithmetic AlgorithmsWithNumbers.pdf Read Chapter 1

3
16/09 Complexity of bit operations

18/09 GCD algorithm and its properties

20/09 Primality Testing

4
23/09 Divide and Conquer Notes Read Chapter 2 of the text

25/09 Solving Recurrences (Master Theorem)

27/09 Megesort; Selection Practice problems: 2.1, 2.2, 2.3, 2.5, 2.14, 2.16

5
30/09 Discussing problems from Chapter 0 through 2.

02/06 Quiz 1 Sorting lower bound

04/10 Sorting lower bound Randomized divide-and-conquer

6
07/10 Randomized divide-and-conquer Read Chapter 3

09/10 Decomposition of Graphs (DFS) DFS-Chapter 3

11/10 Graphs

7
14/10 Thanksgiving

16/10 Chapter 3
18/10 Finishing Ch 3. Starting BFS (Ch 4) Notes Quiz 2: October 23

08
21/10 BFS (contd.)

23/10 Quiz 2 Covers DFS (Ch 3) and part of BFS (Ch 4)

25/10 Shortest Paths

09
28/10 Shortest paths

30/10 Greedy AlgorithmsNotes

01/11 Greedy Algorithms (contd.)

10
04/11 Minimum Spanning Tree Dynamic Programming

06/11 Dynamic Programming DP-Notes

08/11 ProblemSolving

11
11/11 No Class

13/11 Dynamic Programming

15/11 Quiz 3

12
18/11 DP contd.

20/11 DP contd.

22/11 Data Structures Hashing, Priority Search Trees, Suffix Trees

13
25/11 Quiz 3 and 2-3 tree 2-3 Tree

27/11 Hashing Hashing

29/11 Review

Handouts

02/12/2019: Course overview CourseOverview.pptx
02/12/2019: Data Structure overview DataStructureOverview.pptx
02/12/2019: Homework 6 solution hints Hw6Hints.pdf
28/11/2019: Hints to the text problems. Hints.pdf
28/11/2019: A note on bit complexity. BitComplexity.pdf
28/11/2019: Quiz 4 (for practice only) Quiz4.pdf
28/11/2019: Previous final exams 1 2
22/11/2019: Dictionaries slides Dictionaries.pptx
22/11/2019: Priority Queue and Dictionaries study guide PQ-Dictionaries.pdf
21/11/2019: Quiz 3 solution. Quiz3-sol.pdf
19/11/2019: Homework 6 is assigned. hw6.pdf
14/11/2019: Solution to Homework 5 Homework5-sol.pdf
02/11/2019: Homework 5 hw5.pdf
30/10/2019: Solutions to some selected problems of Chapter 4 Probelms-Ch4.pdf
30/10/2019: Solutions to some selected problems of Chapter 3 sol_ch3.pdf
27/10/2019: Solution to Quiz 2 Quiz2-sol.pdf
27/10/2019: Solution to Homework 3 hw3-sol.pdf
25/10/2019: Programming Project Project Details
25/10/2019: Input Graph Input Graph
17/10/2019: Homework 4 hw4.pdf
07/10/2019: Chapter 2 slides used in the class (D-C-Slides.pptx)

06/10/2019: Homework 3. (hw3.pdf)

04/10/Quiz1 solution (Quiz1 Solution)
29/09/2019: Solution to the homework 2 problems. (hw2 Solution)
29/09/2019: Solution hints to the practice problems of Chapter 1 (Chapter 1 Solution)
29/09/2019: A sample quiz question. (Quiz1.pdf)

29/09/2019: Solution to question Homework 1 (hw1-sol.pdf)

28/09/2019: Solution to question 1.17 of the text (1-17.pdf)

27/09/2019: Slides on Divide-and-Conquer. (D-C-Slides.pptx)

22/09/2019: Homework 2. (hw2.pdf)

16/09/2019: Number Theory slides (Slides)

12/09/2019: Fibonacci Sequence Lecture Slides (Fibonacci.ppt)

10/09/2019: Homework 1. (hw1.pdf)

Week	Date	Topics	Other Information
1
	04/09	Course Organization (Introduction)(.pptx)	Read Chapter 0
	06/09	Analysis of Algorithms(.pdf)
2	09/09	Analysis of Fibonacci Sequence Growth of Functions
	11/09	Growth of Functions	Work on the problems in Growth Of Functions notes
	13/05	Complexity issues of multiplications, divisions, exponentiations; modular arithmetic AlgorithmsWithNumbers.pdf	Read Chapter 1
3	16/09	Complexity of bit operations
	18/09	GCD algorithm and its properties
	20/09	Primality Testing
4	23/09	Divide and Conquer Notes	Read Chapter 2 of the text
	25/09	Solving Recurrences (Master Theorem)
	27/09	Megesort; Selection	Practice problems: 2.1, 2.2, 2.3, 2.5, 2.14, 2.16
5	30/09	Discussing problems from Chapter 0 through 2.
	02/06	Quiz 1	Sorting lower bound
	04/10	Sorting lower bound	Randomized divide-and-conquer
6	07/10	Randomized divide-and-conquer	Read Chapter 3
	09/10	Decomposition of Graphs (DFS)	DFS-Chapter 3
	11/10	Graphs
7	14/10	Thanksgiving
	16/10	Chapter 3
	18/10	Finishing Ch 3. Starting BFS (Ch 4) Notes	Quiz 2: October 23
08	21/10	BFS (contd.)
	23/10	Quiz 2	Covers DFS (Ch 3) and part of BFS (Ch 4)
	25/10	Shortest Paths
09	28/10	Shortest paths
	30/10	Greedy AlgorithmsNotes
	01/11	Greedy Algorithms (contd.)
10	04/11	Minimum Spanning Tree	Dynamic Programming
	06/11	Dynamic Programming	DP-Notes
	08/11	ProblemSolving
11	11/11	No Class
	13/11	Dynamic Programming
	15/11	Quiz 3
12	18/11	DP contd.
	20/11	DP contd.
	22/11	Data Structures	Hashing, Priority Search Trees, Suffix Trees
13	25/11	Quiz 3 and 2-3 tree	2-3 Tree
	27/11	Hashing	Hashing
	29/11	Review